Parallel simulation of chip-multiprocessor architectures

ABSTRACT

Chip-multiprocessor (CMP) architectures present a challenge for efficient simulation, combining the requirements of a detailed microprocessor simulator with that of a tightly-coupled parallel system. In this paper, a distributed simulator for target CMPs is presented based on the Message Passing Interface (MPI) designed to run on a host cluster of workstations. Microbenchmark-based evaluation is used to narrow the parallelization design space concerning the performance impact of distributed vs. centralized target L2 simulation, blocking vs. non-blocking remote cache accesses, null-message vs. barrier techniques for clock synchronization, and network interconnect selection. The best combination is shown to yield speedups of up to 16 on a 9-node cluster of dual-CPU workstations, partially due to cache effects.

REFERENCES

• 1: Vikas Agarwal , M. S. Hrishikesh , Stephen W. Keckler , Doug Burger, Clock rate versus IPC: the end of the road for conventional microarchitectures, Proceedings of the 27th annual international symposium on Computer architecture, p.248-259, June 2000, Vancouver, British Columbia, Canada
• 2: Thomas E. Anderson , David E. Culler , David A. Patterson , and the NOW team, A Case for NOW (Networks of Workstations), IEEE Micro, v.15 n.1, p.54-64, February 1995 [doi>10.1109/40.342018]
• 3: Luiz André Barroso , Kourosh Gharachorloo , Robert McNamara , Andreas Nowatzyk , Shaz Qadeer , Barton Sano , Scott Smith , Robert Stets , Ben Verghese, Piranha: a scalable architecture based on single-chip multiprocessing, Proceedings of the 27th annual international symposium on Computer architecture, p.282-293, June 2000, Vancouver, British Columbia, Canada
• 4: Nanette J. Boden , Danny Cohen , Robert E. Felderman , Alan E. Kulawik , Charles L. Seitz , Jakov N. Seizovic , Wen-King Su, Myrinet: A Gigabit-per-Second Local Area Network, IEEE Micro, v.15 n.1, p.29-36, February 1995 [doi>10.1109/40.342015]
• 5: Burger, D. and Austin, T. 1997. The SimpleScalar tool set, version 2.0. Tech. Rep. TR-1342, University of Wisconsin-Madison Computer Sciences Department.
• 6: Chandy, K. and Misra, J. 1979. Distributed simulation: A case study in design and verification of distributed programs. IEEE Trans. Soft. Eng., 5(5) 440--452.
• 7: Chidester, M., George, A., and Radlinski, M. 2001. Multiple-path execution for chip-multiprocessors. Tech. Rep., HCS Research Lab, Department of Electrical and Computer Engineering, University of Florida.
• 8: David E. Culler , Anoop Gupta , Jaswinder Pal Singh, Parallel Computer Architecture: A Hardware/Software Approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1997
• 9: Lucian Codrescu , D. Scott Wills , James Meindl, Architecture of the Atlas Chip-Multiprocessor: Dynamically Parallelizing Irregular Applications, IEEE Transactions on Computers, v.50 n.1, p.67-82, January 2001 [doi>10.1109/12.902753]
• 10: Ronald C. De Vries, Reducing Null Messages in Misra's Distributed Discrete Event Simulation Method, IEEE Transactions on Software Engineering, v.16 n.1, p.82-91, January 1990 [doi>10.1109/32.44366]
• 11: Murthy Durbhakula , Vijay S. Pai , Sarita Adve, Improving the Accuracy vs. Speed Tradeoff for Simulating Shared-Memory Multiprocessors with ILP Processors, Proceedings of the 5th International Symposium on High Performance Computer Architecture, p.23, January 09-12, 1999
• 12: Babak Falsafi , David A. Wood, Modeling cost/performance of a parallel computer simulator, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.7 n.1, p.104-130, Jan. 1997 [doi>10.1145/244804.244808]
• 13: Marco Fillo , Stephen W. Keckler , William J. Dally , Nicholas P. Carter , Andrew Chang , Yevgeny Gurevich , Whay S. Lee, The M-Machine multicomputer, International Journal of Parallel Programming, v.25 n.3, p.183-212, June 1997 [doi>10.1007/BF02700035]
• 14: Richard M. Fujimoto, Parallel and Distribution Simulation Systems, John Wiley & Sons, Inc., New York, NY, 1999
• 15: Alan D. George , Steven W. Cook, Jr., Distributed simulation of parallel DSP architectures on workstation clusters, Simulation, v.67 n.2, p.94-105, Aug. 1996 [doi>10.1177/003754979606700204]
• 16: George, A., Fogarty, R., Markwell, J., and Miars, M. 1999. An Integrated Simulation Environment for parallel and distributed system prototyping. Simulation 75(5), 283--294.
• 17: Lance Hammond , Basem A. Nayfeh , Kunle Olukotun, A Single-Chip Multiprocessor, Computer, v.30 n.9, p.79-85, September 1997 [doi>10.1109/2.612253]
• 18: John L. Hennessy , David A. Patterson, Computer architecture (2nd ed.): a quantitative approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1996
• 19: Johnson, D. 2001. HP's Mako processor. Microprocessor Forum 2001.
• 20: Kahle, J. 1999. Power4: A dual-CPU processor chip. Microprocessor Forum 1999.
• 21: E. J. McLellan , D. A. Webb, The Alpha 21264 Microprocessor Architecture, Proceedings of the International Conference on Computer Design, p.90, October 05-05, 1998
• 22: Venkata Krishnan , Josep Torrellas, Hardware and software support for speculative execution of sequential binaries on a chip-multiprocessor, Proceedings of the 12th international conference on Supercomputing, p.85-92, July 1998, Melbourne, Australia [doi>10.1145/277830.277852]
• 23: MPI Forum 1994. MPI: A Message-Passing Interface Standard. Message-Passing Interface Forum, www.mpi-forum.org.
• 24: Shubhendu S. Mukherjee , Steven K. Reinhardt , Babak Falsafi , Mike Litzkow , Mark D. Hill , David A. Wood , Steven Huss-Lederman , James R. Larus, Wisconsin Wind Tunnel II: A Fast, Portable Parallel Architecture Simulator, IEEE Concurrency, v.8 n.4, p.12-20, October 2000 [doi>10.1109/4434.895100]
• 25: Kunle Olukotun , Basem A. Nayfeh , Lance Hammond , Ken Wilson , Kunyung Chang, The case for a single-chip multiprocessor, Proceedings of the seventh international conference on Architectural support for programming languages and operating systems, p.2-11, October 01-04, 1996, Cambridge, Massachusetts, United States
• 26: Pai, V., Ranganathan, P., and Adve, S. 1997. RSIM Reference Manual version 1.0, Tech. Rep. 9705, Department of Electrical and Computer Engineering, Rice University.
• 27: Price, C. 1995. MIPS IV Instruction Set, Revision 3.1. MIPS Technologies, Inc., Mountain View, CA.
• 28: Matt Reilly , John Edmondson, Performance Simulation of an Alpha Microprocessor, Computer, v.31 n.5, p.50-58, May 1998 [doi>10.1109/2.675634]
• 29: 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
• 30: Scali Computer AS 2000. Scali System Guide version 2.0, white paper. Scali Computer AS, www.scali.com.
• 31: IEEE 1993. Scalable Coherent Interface: ANSI/IEEE Standard 1596-1992. IEEE Service Center, Piscataway, NJ.
• 32: Kevin Skadron , Pritpal S. Ahuja , Margaret Martonosi , Douglas W. Clark, Branch Prediction, Instruction-Window Size, and Cache Size: Performance Trade-Offs and Simulation Techniques, IEEE Transactions on Computers, v.48 n.11, p.1260-1281, November 1999 [doi>10.1109/12.811115]
• 33: Jack E. Veenstra, Mint Tutorial and User Manual, University of Rochester, Rochester, NY, 1993
• 34: Steven Cameron Woo , Moriyoshi Ohara , Evan Torrie , Jaswinder Pal Singh , Anoop Gupta, The SPLASH-2 programs: characterization and methodological considerations, Proceedings of the 22nd annual international symposium on Computer architecture, p.24-36, June 22-24, 1995, S. Margherita Ligure, Italy

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.0 GENERAL
      Subjects: Modeling of computer architecture

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.4 Model Validation and Analysis
      I.6.8 Types of Simulation
          Subjects: Parallel

General Terms:
Algorithms, Design, Experimentation, Performance

Keywords:
Chip multiprocessors (CMP), Myrinet, Scalable Coherent Interface (SCI), microbenchmarks