The Wisconsin Wind Tunnel: virtual prototyping of parallel computers

ABSTRACT

We have developed a new technique for evaluating cache coherent, shared-memory computers. The Wisconsin Wind Tunnel (WWT) runs a parallel shared-memory program on a parallel computer (CM-5) and uses execution-driven, distributed, discrete-event simulation to accurately calculate program execution time. WWT is a virtual prototype that exploits similarities between the system under design (the target) and an existing evaluation platform (the host). The host directly executes all target program instructions and memory references that hit in the target cache. WWT's shared memory uses the CM-5 memory's error-correcting code (ECC) as valid bits for a fine-grained extension of shared virtual memory. Only memory references that miss in the target cache trap to WWT, which simulates a cache-coherence protocol. WWT correctly interleaves target machine events and calculates target program execution time. WWT runs on parallel computers with greater speed and memory capacity than uniprocessors. WWT's simulation time decreases as target system size increases for fixed-size problems and holds roughly constant as the target system and problem scale.

REFERENCES

• 1: A. Agarwal , R. Simoni , J. Hennessy , M. Horowitz, An evaluation of directory schemes for cache coherence, Proceedings of the 15th Annual International Symposium on Computer architecture, p.280-298, May 30-June 02, 1988, Honolulu, Hawaii, United States
• 2: Robert Alverson , David Callahan , Daniel Cummings , Brian Koblenz , Allan Porterfield , Burton Smith, The Tera computer system, Proceedings of the 4th international conference on Supercomputing, p.1-6, June 11-15, 1990, Amsterdam, The Netherlands
• 3: Rassul Ayanl. A Parallel Simulation Scheme Based on the Distance Between Objects. In Proceedings of the SCS Multiconfcrcnc~ on Distributed Simulation, pages 113- 118, March 1989.
• 4: Thomas Ball , James R. Larus, Optimally profiling and tracing programs, Proceedings of the 19th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.59-70, January 19-22, 1992, Albuquerque, New Mexico, United States [doi>10.1145/143165.143180]
• 5: Robert F Boothe, Fast Accurate Simulation of Large Shared Memory Multiprocessors, University of California at Berkeley, Berkeley, CA, 1993
• 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: David Chaiken , John Kubiatowicz , Anant Agarwal, LimitLESS directories: A scalable cache coherence scheme, Proceedings of the fourth international conference on Architectural support for programming languages and operating systems, p.224-234, April 08-11, 1991, Santa Clara, California, United States
• 8: Robert F. Cmelik , Shing I. Kong , David R. Ditzel , Edmund J. Kelly, An analysis of MIPS and SPARC instruction set utilization on the SPEC benchmarks, Proceedings of the fourth international conference on Architectural support for programming languages and operating systems, p.290-302, April 08-11, 1991, Santa Clara, California, United States
• 9: Thinking Machines Corporation. The Connection Machine CM-5 Technical Summary, 1991.
• 10: R. C. Covington , S. Madala , V. Mehta , J. R. Jump , J. B. Sinclair, The rice parallel processing testbed, Proceedings of the 1988 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.4-11, May 24-27, 1988, Santa Fe, New Mexico, United States
• 11: William J. Dally, Andrew Chien, Stuart Fiske, Waldemar Horwat, John Keen, Michael Larivee, Rich Nuth, Scott Wills, Paul Carrick, and Greg Flyer. The J-Machine: A Fine-Grain Concurrent Computer. In G. X. Ritter, editor, Proe. Information Processing 89. Elsevier North-Holland, Inc., 1989.
• 12: Helen Davis, Stephen R. Goldschmidt, and John Hennessy. Multiprocessor Simulation artd Tracing Using Tango. In Proceedings of the 1991 International Con- }erence on Parallel Processing (Vol. Ii Software), pages Ii99--107, August 1991.
• 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: James R. Goodman, Coherency for multiprocessor virtual address caches, Proceedings of the second international conference on Architectual support for programming languages and operating systems, p.72-81, October 1987, Palo Alto, California, United States
• 15: John L. Gustafson, Reevaluating Amdahl's law, Communications of the ACM, v.31 n.5, p.532-533, May 1988 [doi>10.1145/42411.42415]
• 16: Mark D. Hill , James R. Larus , Steven K. Reinhardt , David A. Wood, Cooperative shared memory: software and hardware for scalable multiprocessor, Proceedings of the fifth international conference on Architectural support for programming languages and operating systems, p.262-273, October 12-15, 1992, Boston, Massachusetts, United States
• 17: David R. Jefferson, Virtual time, ACM Transactions on Programming Languages and Systems (TOPLAS), v.7 n.3, p.404-425, July 1985 [doi>10.1145/3916.3988]
• 18: Kendall Square Research. Kendall Square Research Technical Summary, 1992.
• 19: Pavlos Konas , Pen-Chung Yew, Parallel discrete event simulation on shared-memory multiprocessors, Proceedings of the 24th annual symposium on Simulation, p.134-148, April 1991, New Orleans, Louisiana, United States
• 20: Pavlos Konas and Pen-Chung Yew. Synchronous Parallel Discrete Event Simulation on Shared-Memory Multiproeessors, in Proceedings of 6th Workshop on Parallel and Distributed Simulation, pages 12-21, January 1992.
• 21: Daniel Lenoski , James Laudon , Kourosh Gharachorloo , Wolf-Dietrich Weber , Anoop Gupta , John Hennessy , Mark Horowitz , Monica S. Lam, The Stanford Dash Multiprocessor, Computer, v.25 n.3, p.63-79, March 1992 [doi>10.1109/2.121510]
• 22: Kai Li , Paul Hudak, Memory coherence in shared virtual memory systems, ACM Transactions on Computer Systems (TOCS), v.7 n.4, p.321-359, Nov. 1989 [doi>10.1145/75104.75105]
• 23: Y.-B. Lin, J.-L. Baer, and E. D. Lazowska. Tailoring a Parallel Trace-Driven Simulation Tedmique to Specific Multlprocessor Cache Coherence Protocols. Technical Report 88-01-02, Department of Computer Science, University of Washington, March 1988.
• 24: J. S. Liptay. Structural Aspects of the System/360 Model 85, Part II: The Cache. IBM Systems Journal, 7(1):15-21, 1968.
• 25: B. D. Lubachevsky, Efficient distributed event-driven simulations of multiple-loop networks, Communications of the ACM, v.32 n.1, p.111-123, Jan. 1989 [doi>10.1145/63238.63247]
• 26: Jayadev Misra, Distributed discrete-event simulation, ACM Computing Surveys (CSUR), v.18 n.1, p.39-65, March 1986 [doi>10.1145/6462.6485]
• 27: Todd Mowry , Anoop Gupta, Tolerating latency through software-controlled prefetching in shared-memory multiprocessors, Journal of Parallel and Distributed Computing, v.12 n.2, p.87-106, June 1991 [doi>10.1016/0743-7315(91)90014-Z]
• 28: D. Nicol, Conservative Parallel Simulation of Priority Class Queuing Networks, IEEE Transactions on Parallel and Distributed Systems, v.3 n.3, p.294-303, May 1992 [doi>10.1109/71.139203]
• 29: 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]
• 30: Jaswinder Pal Singh , Wolf-Dietrich Weber , Anoop Gupta, SPLASH: Stanford parallel applications for shared-memory, ACM SIGARCH Computer Architecture News, v.20 n.1, p.5-44, March 1992 [doi>10.1145/130823.130824]
• 31: Richard L. Sites , Anton Chernoff , Matthew B. Kirk , Maurice P. Marks , Scott G. Robinson, Binary translation, Communications of the ACM, v.36 n.2, p.69-81, Feb. 1993 [doi>10.1145/151220.151227]
• 32: SPEC. SPEC Benchmark Suite Release 1.0, Winter 1990.
• 33: Yuval Tamir and G. Janakiraman. Hierarchical Coherency Management for Shared Virtual Memory Multicomputers. Journal of Parallel and Distributed Computing, 15(4):408-419, August 1992.
• 34: David A. Wood , Satish Chandra , Babak Falsafi , Mark D. Hill , James R. Larus , Alvin R. Lebeck , James C. Lewis , Shubhendu S. Mukherjee , Subbarao Palacharla , Steven K. Reinhardt, Mechanisms for cooperative shared memory, Proceedings of the 20th annual international symposium on Computer architecture, p.156-167, May 16-19, 1993, San Diego, California, United States

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Parallel processors**

Additional Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.2 Design Styles
          Subjects: Shared memory

  C. Computer Systems Organization
  C.0 GENERAL
      Subjects: Hardware/software interfaces
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.8 Types of Simulation
          Subjects: Discrete event

General Terms:
Design, Performance, Verification