Hardware spatial forwarding for widely shared data

ABSTRACT

Applications with widely shared data do not perform well on cc-NUMA multiprocessors due to the hot-spots they create in the system. In this paper we address this problem by enhancing the memory controller with a forwarding mechanism capable of hiding the read latency of widely shared data, while potentially decreasing the memory and network contention. Based on the influx of requests, the memory anticipates the next read references and forwards the data in advance to the processors. To identify the set of processors the data is to be forwarded to we use a heuristic based on the spatial locality of memory blocks. To increase the forwarding effectiveness and minimize the number of messages, we incorporate simple filters combined with a feedback mechanism. We also show that further improvements are possible using a combined software-prefetching/hardware-forwarding approach. Our experimental results obtained with a detailed execution driven simulator with ILP processors show significant improvements in execution time (up to 37%).

REFERENCES

• 1: Hazim Abdel-Shafi , Jonathan Hall , Sarita V. Adve , Vikram S. Adve, An Evaluation of Fine-Grain Producer-Initiated Communication in Cache-Coherent Multiprocessors, Proceedings of the 3rd IEEE Symposium on High-Performance Computer Architecture, p.204, February 01-05, 1997
• 2: Jean-Loup Baer , Tien-Fu Chen, An effective on-chip preloading scheme to reduce data access penalty, Proceedings of the 1991 ACM/IEEE conference on Supercomputing, p.176-186, November 18-22, 1991, Albuquerque, New Mexico, United States [doi>10.1145/125826.125932]
• 3: Dileep Bhandarkar , Jason Ding, Performance Characterization of the Pentium® Pro Processor, Proceedings of the 3rd IEEE Symposium on High-Performance Computer Architecture, p.288, February 01-05, 1997
• 4: B. Brooks, R. Bruccoleri, B. Olafson, D. S. es, S. Swaminathan, and M. Karplus. Charmm: A program for macromolecular energy, minimization, and dynamics calculations. Journal of Computational Chemistry, 4:187, 1983.
• 5: William Y. Chen , Scott A. Mahlke , Pohua P. Chang , Wen-mei W. Hwu, Data access microarchitectures for superscalar processors with compiler-assisted data prefetching, Proceedings of the 24th annual international symposium on Microarchitecture, p.69-73, September 1991, Albuquerque, New Mexico, Puerto Rico [doi>10.1145/123465.123478]
• 6: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 7: A. Krishnamurthy , D. E. Culler , A. Dusseau , S. C. Goldstein , S. Lumetta , T. von Eicken , K. Yelick, Parallel programming in Split-C, Proceedings of the 1993 ACM/IEEE conference on Supercomputing, p.262-273, December 1993, Portland, Oregon, United States [doi>10.1145/169627.169724]
• 8: John W. C. Fu , Janak H. Patel , Bob L. Janssens, Stride directed prefetching in scalar processors, Proceedings of the 25th annual international symposium on Microarchitecture, p.102-110, December 01-04, 1992, Portland, Oregon, United States
• 9: Kourosh Gharachorloo , Anoop Gupta , John Hennessy, Performance evaluation of memory consistency models for shared-memory multiprocessors, Proceedings of the fourth international conference on Architectural support for programming languages and operating systems, p.245-257, April 08-11, 1991, Santa Clara, California, United States
• 10: Kourosh Gharachorloo , Daniel Lenoski , James Laudon , Phillip Gibbons , Anoop Gupta , John Hennessy, Memory consistency and event ordering in scalable shared-memory multiprocessors, Proceedings of the 17th annual international symposium on Computer Architecture, p.15-26, May 28-31, 1990, Seattle, Washington, United States
• 11: A. Gottlieb, R. Grishman, C. P. Kruskal, K. P. McAuliffe, L. Rudolph, and M. Snir. The NYU ultracomputer - designing a MIMD, shared-memory parallel machine. IEEE Trans. on Computers, 32(2):175, Feb. 1983.
• 12: W. Gunsteren and H. Berencisen. GROMOS: GROningen MOlecular Simulation software. Technical report, Laboratory of Physical Chemistry, University of Groningen, 1988.
• 13: Ravi Iyer , Laxmi Narayan Bhuyan, Switch Cache: A Framework for Improving the Remote Memory Access Latency of CC-NUMA Multiprocessors, Proceedings of the 5th International Symposium on High Performance Computer Architecture, p.152, January 09-12, 1999
• 14: Norman P. Jouppi, Improving direct-mapped cache performance by the addition of a small fully-associative cache and prefetch buffers, Proceedings of the 17th annual international symposium on Computer Architecture, p.364-373, May 28-31, 1990, Seattle, Washington, United States
• 15: Stefanos Kaxiras , James R. Goodman, The GLOW cache coherence protocol extensions for widely shared data, Proceedings of the 10th international conference on Supercomputing, p.35-43, May 25-28, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237578.237583]
• 16: David A. Koufaty , Xiangfeng Chen , David K. Poulsen , Josep Torrellas, Data Forwarding in Scalable Shared-Memory Multiprocessors, IEEE Transactions on Parallel and Distributed Systems, v.7 n.12, p.1250-1264, December 1996 [doi>10.1109/71.553274]
• 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: Chi-Keung Luk , Todd C. Mowry, Compiler-based prefetching for recursive data structures, Proceedings of the seventh international conference on Architectural support for programming languages and operating systems, p.222-233, October 01-04, 1996, Cambridge, Massachusetts, United States
• 19: Maged M. Michael , Ashwini K. Nanda, Design and Performance of Directory Caches for Scalable Shared Memory Multiprocessors, Proceedings of the 5th International Symposium on High Performance Computer Architecture, p.142, January 09-12, 1999
• 20: 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]
• 21: Todd Carl Mowry, Tolerating latency through software-controlled data prefetching, Stanford University, Stanford, CA, 1995
• 22: Todd C. Mowry , Monica S. Lam , Anoop Gupta, Design and evaluation of a compiler algorithm for prefetching, Proceedings of the fifth international conference on Architectural support for programming languages and operating systems, p.62-73, October 12-15, 1992, Boston, Massachusetts, United States
• 23: Circular Buffered Switch Design with Wormhole Routing and Virtual Channels, Proceedings of the International Conference on Computer Design, p.466, October 05-05, 1998
• 24: V. S. Pai, P. Ranganathan, and S. V. Adve. RSIM: An Execution-Driven Simulator for ILP-Based Shared- Memory Multiprocessors and Uniprocessors. In Proceedings of the Third Workshop on Computer Architecture Education, February 1997.
• 25: Shlomit S. Pinter , Adi Yoaz, Tango: a hardware-based data prefetching technique for superscalar processors, Proceedings of the 29th annual ACM/IEEE international symposium on Microarchitecture, p.214-225, December 02-04, 1996, Paris, France
• 26: D. K. Poulsen and P.-C. Yew. Data prefetching and data forwarding in shared memory multiprocessors. In Proceedings of the ~Jrd International Conference on Parallel Processing. Volume 2: Software, pages 276- 280, Aug. 1994.
• 27: A. J. Smith. Sequential program prefetching in memory hierarchies. IEBE Computer, 11(12):7-21, Dec. 1978.
• 28: Gurindar S. Sohi , Manoj Franklin, High-bandwidth data memory systems for superscalar processors, Proceedings of the fourth international conference on Architectural support for programming languages and operating systems, p.53-62, April 08-11, 1991, Santa Clara, California, United States
• 29: Dean M. Tullsen , Susan J. Eggers, Limitations of cache prefetching on a bus-based multiprocessor, Proceedings of the 20th annual international symposium on Computer architecture, p.278-288, May 16-19, 1993, San Diego, California, United States
• 30: Kenneth M. Wilson , Kunle Olukotun, Designing high bandwidth on-chip caches, Proceedings of the 24th annual international symposium on Computer architecture, p.121-132, June 01-04, 1997, Denver, Colorado, United States
• 31: Kenneth M. Wilson , Kunle Olukotun , Mendel Rosenblum, Increasing cache port efficiency for dynamic superscalar microprocessors, Proceedings of the 23rd annual international symposium on Computer architecture, p.147-157, May 22-24, 1996, Philadelphia, Pennsylvania, United States

INDEX TERMS

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

Additional Classification:
  B. Hardware
  B.4 INPUT/OUTPUT AND DATA COMMUNICATIONS
      B.4.2 Input/Output Devices
          Subjects: Channels and controllers

  C. Computer Systems Organization

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods

  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.2 Installation Management
          Subjects: Benchmarks

General Terms:
Algorithms, Design, Experimentation, Measurement, Performance, Standardization, Theory