Reducing synchronization overhead in parallel simulation

ABSTRACT

Synchronization is often the dominant cost in conservative parallel simulation, particularly in simulations of parallel computers, in which low-latency simulated communication requires frequent synchronization. We present and evaluate LOCAL BARRIERS and PREDICTIVE BARRIER SCHEDULING, two techniques for reducing synchronization overhead in the simulation of message-passing multicomputers. Local barriers use nearest-neighbor synchronization to reduce waiting time at synchronization points. Predictive barrier scheduling, a novel technique that schedules synchronizations using both compile-time and runtime analysis, reduces the frequency of synchronization operations. In contrast to other work in this area, both techniques reduce synchronization overhead without decreasing the accuracy of network simulation. These techniques were evaluated by comparing their performance to that of periodic global synchronization. Experiments show that local barriers improve performance by up to 24% for communication-bound applications, while predictive barrier scheduling improves performance by up to 65% for applications with long local computation phases. Because the two techniques are complementary, we advocate a combined approach. This work was done in the context of PARALLEL PROTEUS, a new parallel simulator of message-passing multicomputers.

REFERENCES

• 1: Anant Agarwal , Ricardo Bianchini , David Chaiken , Kirk L. Johnson , David Kranz , John Kubiatowicz , Beng-Hong Lim , Kenneth Mackenzie , Donald Yeung, The MIT Alewife machine: architecture and performance, Proceedings of the 22nd annual international symposium on Computer architecture, p.2-13, June 22-24, 1995, S. Margherita Ligure, Italy
• 2: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 3: Robert C. Bedichek, Talisman: fast and accurate multicomputer simulation, Proceedings of the 1995 ACM SIGMETRICS joint international conference on Measurement and modeling of computer systems, p.14-24, May 15-19, 1995, Ottawa, Ontario, Canada
• 4: Dimitri P. Bertsekas , John N. Tsitsiklis, Parallel and distributed computation: numerical methods, Prentice-Hall, Inc., Upper Saddle River, NJ, 1989
• 5: Guy E. Blelloch , Charles E. Leiserson , Bruce M. Maggs , C. Greg Plaxton , Stephen J. Smith , Marco Zagha, A comparison of sorting algorithms for the connection machine CM-2, Proceedings of the third annual ACM symposium on Parallel algorithms and architectures, p.3-16, July 21-24, 1991, Hilton Head, South Carolina, United States [doi>10.1145/113379.113380]
• 6: E. A. Brewer , C. N. Dellarocas , A. Colbrook , W. E. Weihl, PROTEUS: A HIGH-PERFORMANCE PARALLEL-ARCHITECTURE SIMULATOR, Massachusetts Institute of Technology, Cambridge, MA, 1991
• 7: Doug Burger , David A. Wood, Accuracy vs. performance in parallel simulation of interconnection networks, Proceedings of the 9th International Symposium on Parallel Processing, p.22-31, April 25-28, 1995
• 8: David R. Cheriton , Hendrik A. Goosen , Hugh Holbrook , Philip Machanick, Restructuring a parallel simulation to improve cache behavior in a shared-memory multiprocessor: the value of distributed synchronization, Proceedings of the seventh workshop on Parallel and distributed simulation, p.159-162, May 16-19, 1993, San Diego, California, United States
• 9: Thinking Machines Corporation. CM-5 technical summary, 1992.
• 10: Philip M. Dickens. Personal communication. January 1996.
• 11: Phillip M. Dickens , Philip Heidelberger , David M. Nicol, PARALLELIZED DIRECT EXECUTION SIMULATION OF MESSAGE-PASSING PARALLEL PROGRAMS, Institute for Computer Applications in Science and Engineering (ICASE), 1994
• 12: Phillip M. Dickens , Philip Heidelberger , David M. Nicol, Parallelized Network Simulators for Message-Passing Parallel Programs, Proceedings of the 3rd International Workshop on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems, p.72-76, January 10-18, 1995
• 13: Richard M. Fujimoto, Parallel discrete event simulation, Communications of the ACM, v.33 n.10, p.30-53, Oct. 1990 [doi>10.1145/84537.84545]
• 14: Stephen R. Goldschmidt, Simulation of multiprocessors: accuracy and performance, Stanford University, Stanford, CA, 1993
• 15: Kirk Johnson, David Chaiken, and Alan Mainwaring. NWO-P: Parallel simulation of the Alewife machine. In Proceedings of the 1993 MIT Student Workshop on Supercomputing Technolo. gies, August 1993.
• 16: Pavlos Konas , Pen-Chung Yew, Improved parallel architectural simulations on shared-memory multiprocessors, Proceedings of the eighth workshop on Parallel and distributed simulation, p.156-159, July 06-08, 1994, Edinburgh, Scotland, United Kingdom
• 17: U. Legedza, Reducing Synchronization Overhead in Parallel Simulation, Massachusetts Institute of Technology, Cambridge, MA, 1995
• 18: David Nicol and Richard Fujimoto. Parallel simulation today. Technical Report 92-62, ICASE, 1992.
• 19: David M. Nicol, Performance bounds on parallel self-initiating discrete-event simulations, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.1 n.1, p.24-50, Jan. 1991 [doi>10.1145/102810.102812]
• 20: David M. Nicol, The cost of conservative synchronization in parallel discrete event simulations, Journal of the ACM (JACM), v.40 n.2, p.304-333, April 1993 [doi>10.1145/151261.151266]
• 21: Steven K. Reinhardt , Mark D. Hill , James R. Larus , Alvin R. Lebeck , James C. Lewis , David A. Wood, The Wisconsin Wind Tunnel: virtual prototyping of parallel computers, Proceedings of the 1993 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.48-60, May 10-14, 1993, Santa Clara, California, United States

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.8 Types of Simulation
          Subjects: Parallel

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Synchronization

General Terms:
Measurement, Performance, Theory

Keywords:
parallel simulation, synchronization, network simulation