The MIT Alewife machine: architecture and performance

ABSTRACT

Alewife is a multiprocessor architecture that supports up to 512 processing nodes connected over a scalable and cost-effective mesh network at a constant cost per node. The MIT Alewife machine, a prototype implementation of the architecture, demonstrates that a parallel system can be both scalable and programmable. Four mechanisms combine to achieve these goals: software-extended coherent shared memory provides a global, linear address space; integrated message passing allows compiler and operating system designers to provide efficient communication and synchronization; support for fine-grain computation allows many processors to cooperate on small problem sizes; and latency tolerance mechanisms --- including block multithreading and prefetching --- mask unavoidable delays due to communication.Microbenchmarks, together with over a dozen complete applications running on the 32-node prototype, help to analyze the behavior of the system. Analysis shows that integrating message passing with shared memory enables a cost-efficient solution to the cache coherence problem and provides a rich set of programming primitives. Block multithreading and prefetching improve performance by up to 25% individually, and 35% together. Finally, language constructs that allow programmers to express fine-grain synchronization can improve performance by over a factor of two.

REFERENCES

• 1: A. Agarwal, D. Kranz, and V Natarajan. Automatic Partitioning of Parallel Loops for Cache-Coherent Mult~processors. In The 22rid International Con/erence on Parallel Processing, August 1993.
• 2: Anant Agarwal , John Kubiatowicz , David Kranz , Beng-Hong Lim , Donald Yeung , Godfrey D'Souza , Mike Parkin, Sparcle: An Evolutionary Processor Design for Large-Scale Multiprocessors, IEEE Micro, v.13 n.3, p.48-61, May 1993 [doi>10.1109/40.216748]
• 3: Anant Agarwal , Beng-Hong Lim , David Kranz , John Kubiatowicz, APRIL: a processor architecture for multiprocessing, Proceedings of the 17th annual international symposium on Computer Architecture, p.104-114, May 28-31, 1990, Seattle, Washington, United States
• 4: Gail Alverson , Robert Alverson , David Callahan , Brian Koblenz , Allan Porterfield , Burton Smith, Exploiting heterogeneous parallelism on a multithreaded multiprocessor, Proceedings of the 6th international conference on Supercomputing, p.188-197, July 19-24, 1992, Washington, D. C., United States [doi>10.1145/143369.143408]
• 5: ANSI/IEEE Std 1596-1992 Scalable Coherent Interface, 1992.
• 6: Arvind , Rishiyur S. Nikhil , Keshav K. Pingali, I-structures: data structures for parallel computing, ACM Transactions on Programming Languages and Systems (TOPLAS), v.11 n.4, p.598-632, Oct. 1989 [doi>10.1145/69558.69562]
• 7: D. Bmley et al. The NAS Parallel Benchmarks Technical Report RNR-94-007, NASA Ames Research Center, March 1994.
• 8: D. Chaiken , A. Agarwal, Software-extended coherent shared memory: performance and cost, Proceedings of the 21ST annual international symposium on Computer architecture, p.314-324, April 18-21, 1994, Chicago, Illinois, United States
• 9: 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
• 10: F. Chong, S. Sharma, E. Brewer, and J. Saltz. Multlprocessor Runtime Support for Irregular DAGs In R. Kalia and P. Vash~shta, editors, Toward Teraflop Computing attd New Grand Challenge Apphcations. Nova Science Publishers, Inc., 1995.
• 11: I Duff, R. Grimes, and J. Lewis. User's Guide for the Harwell-Boemg Sparse Matrix Collection Technical Report TR/PA/92/86, CERFACS, October 1992.
• 12: Erik Hagersten , Anders Landin , Seif Haridi, DDM: A Cache-Only Memory Architecture, Computer, v.25 n.9, p.44-54, September 1992 [doi>10.1109/2.156381]
• 13: D. A. Kranz , R. H. Halstead, Jr. , E. Mohr, Mul-T: a high-performance parallel Lisp, Proceedings of the ACM SIGPLAN 1989 Conference on Programming language design and implementation, p.81-90, June 19-23, 1989, Portland, Oregon, United States
• 14: David Kranz , Kirk Johnson , Anant Agarwal , John Kubiatowicz , Beng-Hong Lim, Integrating message-passing and shared-memory: early experience, Proceedings of the fourth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.54-63, May 19-22, 1993, San Diego, California, United States
• 15: David Kroft, Lockup-free instruction fetch/prefetch cache organization, Proceedings of the 8th annual symposium on Computer Architecture, p.81-87, May 12-14, 1981, Minneapolis, Minnesota, United States
• 16: John Kubiatowicz , Anant Agarwal, Anatomy of a message in the Alewife multiprocessor, Proceedings of the 7th international conference on Supercomputing, p.195-206, July 19-23, 1993, Tokyo, Japan [doi>10.1145/165939.165970]
• 17: John Kubiatowicz , David Chaiken , Anant Agarwal, Closing the window of vulnerability in multiphase memory transactions, Proceedings of the fifth international conference on Architectural support for programming languages and operating systems, p.274-284, October 12-15, 1992, Boston, Massachusetts, United States
• 18: J. Kubiatowicz, D. Chaiken, A. Agarwal, A Altman, J Babb, D Kranz, B H. Llm, K. Mackenzie, J, Piscitello, and D Yeung The Alewife CMMU' Addressing the Multiprocessor Commumcations Gap In HOTCHIPS, August 1994.
• 19: J. Kuskin , D. Ofelt , M. Heinrich , J. Heinlein , R. Simoni , K. Gharachorloo , J. Chapin , D. Nakahira , J. Baxter , M. Horowitz , A. Gupta , M. Rosenblum , J. Hennessy, The Stanford FLASH multiprocessor, Proceedings of the 21ST annual international symposium on Computer architecture, p.302-313, April 18-21, 1994, Chicago, Illinois, United States
• 20: D. Lenoski , J. Laudon , T. Joe , D. Nakahira , L. Stevens , A. Gupta , J. Hennessy, The DASH Prototype: Logic Overhead and Performance, IEEE Transactions on Parallel and Distributed Systems, v.4 n.1, p.41-61, January 1993 [doi>10.1109/71.205652]
• 21: K. Mackenzie , J. Kubiatowicz , A. Agarwal , M. F. Kaashoek, FUGU: Implementing Translation and Protection in a Multiuser, Multimodel Multiprocessor, Massachusetts Institute of Technology, Cambridge, MA, 1994
• 22: E. Mohr , D. A. Kranz , R. H. Halstead, Jr., Lazy Task Creation: A Technique for Increasing the Granularity of Parallel Programs, IEEE Transactions on Parallel and Distributed Systems, v.2 n.3, p.264-280, July 1991 [doi>10.1109/71.86103]
• 23: R. S. Nikhil , G. M. Papadopoulos , Arvind, T: a multithreaded massively parallel architecture, Proceedings of the 19th annual international symposium on Computer architecture, p.156-167, May 19-21, 1992, Queensland, Australia
• 24: Michael D. Noakes , Deborah A. Wallach , William J. Dally, The J-machine multicomputer: an architectural evaluation, Proceedings of the 20th annual international symposium on Computer architecture, p.224-235, May 16-19, 1993, San Diego, California, United States
• 25: Gregory M. Papadopoulos , David E. Culler, Monsoon: an explicit token-store architecture, Proceedings of the 17th annual international symposium on Computer Architecture, p.82-91, May 28-31, 1990, Seattle, Washington, United States
• 26: S. K. Reinhardt , J. R. Larus , D. A. Wood, Tempest and typhoon: user-level shared memory, Proceedings of the 21ST annual international symposium on Computer architecture, p.325-336, April 18-21, 1994, Chicago, Illinois, United States
• 27: Charles L. Seitz , Nanette J. Boden , Jakov Seizovic , Wen-King Su, The design of the Caltech Mosaic C multicomputer, Proceeding of the 1993 symposium on Research on integrated systems, p.1-22, February 1993, Seattle, Washington, United States
• 28: 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]
• 29: B.J. Smith. Architecture and Applications of the HEP Multiprocessor Computer System. Society of Photo-opttcal hlstrumen ration Engineers, 298:241-248, 1981.
• 30: Thorsten von Eicken , David E. Culler , Seth Copen Goldstein , Klaus Erik Schauser, Active messages: a mechanism for integrated communication and computation, Proceedings of the 19th annual international symposium on Computer architecture, p.256-266, May 19-21, 1992, Queensland, Australia
• 31: Donald Yeung , Anant Agarwal, Experience with fine-grain synchronization in MIMD machines for preconditioned conjugate gradient, Proceedings of the fourth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.187-192, May 19-22, 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:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes

  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Parallel programming
  D.2 SOFTWARE ENGINEERING
  D.4 OPERATING SYSTEMS

General Terms:
Design, Languages, Performance