Flexible use of memory for replication/migration in cache-coherent DSM multiprocessors

ABSTRACT

Given the limitations of bus-based multiprocessors, CC-NUMA is the scalable architecture of choice for shared-memory machines. The most important characteristic of the CC-NUMA architecture is that the latency to access data on a remote node is considerably larger than the latency to access local memory. On such machines, good data locality can reduce memory stall time and is therefore a critical factor in application performance.In this paper we study the various options available to system designers to transparently decrease the fraction of data misses serviced remotely. This work is done in the context of the Stanford FLASH multiprocessor. FLASH is unique in that each node has a single pool of DRAM that can be used in a variety of ways by the programmable memory controller. We use the programmability of FLASH to explore different options for cache-coherence and data-locality in compute-server workloads. First, we consider two protocols for providing base cache-coherence, one with centralized directory information (dynamic pointer allocation) and another with distributed directory information (SCI). While several commercial systems are based on SCI, we find that a centralized scheme has superior performance. Next, we consider different hardware and software techniques that use some or all of the local memory in a node to improve data locality. Finally, we propose a hybrid scheme that combines hardware and software techniques. These schemes work on the same base platform with both user and kernel references from the workloads. The paper thus offers a realistic and fair comparison of replication/migration techniques that has not previously been feasible.

REFERENCES

• 1: A. Agarwal , D. Chaiken , K. Johnson , D. Kranz , J. Kubiatowicz , K. Kurihara , B. H. Lim , G. Maa , D. Nussbaum , M. Parkin , D. Yeung, THE MIT ALEWIFE MACHINE: A LARGE-SCALE DISTRIBUTED-MEMORY MULTIPROCESSOR, Massachusetts Institute of Technology, Cambridge, MA, 1991
• 2: Thomas E. Anderson , Brian N. Bershad , Edward D. Lazowska , Henry M. Levy, Scheduler activations: effective kernel support for the user-level management of parallelism, Proceedings of the thirteenth ACM symposium on Operating systems principles, p.95-109, October 13-16, 1991, Pacific Grove, California, United States
• 3: W. Bolosky , R. Fitzgerald , M. Scott, Simple but effective techniques for NUMA memory management, ACM SIGOPS Operating Systems Review, v.23 n.5, p.19-31, Dec. 3–6, 1989
• 4: T. Brewer , G. Astfalk, The evolution of the HP/Convex Exemplar, Proceedings of the 42nd IEEE International Computer Conference, p.81, February 23-26, 1997
• 5: A. Cox , R. Fowler, The implementation of a coherent memory abstraction on a NUMA multiprocessor: experiences with platinum, Proceedings of the twelfth ACM symposium on Operating systems principles, p.32-44, November 1989
• 6: Data General Corporation. Aviion AV 20000 Server Technical Overview. Data General White Paper, http ://www. dg. corn/about/htm I/aviion_av2OOOO_se rye r tech nical_overview.html, 1997.
• 7: Babak Falsafi , David A. Wood, Reactive NUMA: a design for unifying S-COMA and CC-NUMA, Proceedings of the 24th annual international symposium on Computer architecture, p.229-240, June 01-04, 1997, Denver, Colorado, United States
• 8: Steven Frank, Henry Burkhardt III and Dr. James Rothnie. The KSR 1: Bridging the Gap Between Shared Memory and MPPs. Compcon '93 Proceedings.
• 9: 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]
• 10: Erik Hagersten, Ashley Saulsbury, and Anders Landin. Simple COMA Node Implementations. In Proceedings of the 27th Hawaii International Conference on System Sciences, January. I994.
• 11: Mark Heinrich , Jeffrey Kuskin , David Ofelt , John Heinlein , Joel Baxter , Jaswinder Pal Singh , Richard Simoni , Kourosh Gharachorloo , David Nakahira , Mark Horowitz , Anoop Gupta , Mendel Rosenblum , John Hennessy, The performance impact of flexibility in the Stanford FLASH multiprocessor, Proceedings of the sixth international conference on Architectural support for programming languages and operating systems, p.274-285, October 05-07, 1994, San Jose, California, United States
• 12: M. Heinnch, V. Soundararajan, A. Gupta. and J. Hennessy. A Quantitative Analysis of the Performance and Scalability of Cache Coherence Protocols. Submitted for publication.
• 13: David A. Patterson , John L. Hennessy, Computer architecture: a quantitative approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1990
• 14: T. Joe , J. L. Hennessy, Evaluating the memory overhead required for COMA architectures, Proceedings of the 21ST annual international symposium on Computer architecture, p.82-93, April 18-21, 1994, Chicago, Illinois, United States
• 15: 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
• 16: James Laudon , Daniel Lenoski, The SGI Origin: a ccNUMA highly scalable server, Proceedings of the 24th annual international symposium on Computer architecture, p.241-251, June 01-04, 1997, Denver, Colorado, United States
• 17: Daniel Lenoski , James Laudon , Truman Joe , David Nakahira , Luis Stevens , Anoop Gupta , John Hennessy, The DASH prototype: implementation and performance, Proceedings of the 19th annual international symposium on Computer architecture, p.92-103, May 19-21, 1992, Queensland, Australia
• 18: Tom Lovett , Russell Clapp, STiNG: a CC-NUMA computer system for the commercial marketplace, Proceedings of the 23rd annual international symposium on Computer architecture, p.308-317, May 22-24, 1996, Philadelphia, Pennsylvania, United States
• 19: A. Nowatzyk, G. Aybay, M. Browne, E. Kelly, M. Parkin, B. Radke, and S. Vishi. The S3.mp Scalable Shared Memory Multiprocessor. In Proceedings of the 1995 International Conference on Parallel Processing, pages I1-I10, August 1995.
• 20: 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
• 21: Mendel Rosenblum , Stephen A. Herrod , Emmett Witchel , Anoop Gupta, Complete Computer System Simulation: The SimOS Approach, IEEE Parallel & Distributed Technology: Systems & Technology, v.3 n.4, p.34-43, December 1995 [doi>10.1109/88.473612]
• 22: Scalable Coherent interface. IEEE Standard 1596-1992. August 1993.
• 23: Richard Thomas Simoni, Jr., Cache coherence directories for scalable multiprocessors, Stanford University, Stanford, CA, 1992
• 24: 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]
• 25: Per Stenström , Truman Joe , Anoop Gupta, Comparative performance evaluation of cache-coherent NUMA and COMA architectures, Proceedings of the 19th annual international symposium on Computer architecture, p.80-91, May 19-21, 1992, Queensland, Australia
• 26: A. Tucker , A. Gupta, Process control and scheduling issues for multiprogrammed shared-memory multiprocessors, Proceedings of the twelfth ACM symposium on Operating systems principles, p.159-166, November 1989
• 27: Raj Vaswani , John Zahorjan, The implications of cache affinity on processor scheduling for multiprogrammed, shared memory multiprocessors, Proceedings of the thirteenth ACM symposium on Operating systems principles, p.26-40, October 13-16, 1991, Pacific Grove, California, United States
• 28: Ben Verghese , Scott Devine , Anoop Gupta , Mendel Rosenblum, Operating system support for improving data locality on CC-NUMA compute servers, Proceedings of the seventh international conference on Architectural support for programming languages and operating systems, p.279-289, October 01-04, 1996, Cambridge, Massachusetts, United States
• 29: Zheng Zhang , Josep Torrellas, Reducing Remote Conflict Misses: NUMA with Remote Cache versus COMA, Proceedings of the 3rd IEEE Symposium on High-Performance Computer Architecture, p.272, February 01-05, 1997

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES

Additional Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.2 Design Styles
          Subjects: Shared memory
  B.8 Performance and Reliability