Owner prediction for accelerating cache-to-cache transfer misses in a cc-NUMA architecture

ABSTRACT

Cache misses for which data must be obtained from a remote cache (cache-to-cache transfer misses) account for an important fraction of the total miss rate. Unfortunately, cc-NUMA designs put the access to the directory information into the critical path of 3-hop misses, which significantly penalizes them compared to SMP designs. This work studies the use of owner prediction as a means of providing cc-NUMA multiprocessors with a more efficient support for cache-to-cache transfer misses. Our proposal comprises an effective prediction scheme as well as a coherence protocol designed to support the use of prediction. Results indicate that owner prediction can significantly reduce the latency of cache-to-cache transfer misses, which translates into speed-ups on application performance up to 12%. In order to also accelerate most of those 3-hop misses that are either not predicted or mispredicted, the inclusion of a small and fast directory cache in every node is evaluated, leading to improvements up to 16% on the final performance.

REFERENCES

• 1: Manuel E. Acacio , José González , José M. García , José Duato, A New Scalable Directory Architecture for Large-Scale Multiprocessors, Proceedings of the 7th International Symposium on High-Performance Computer Architecture, p.97, January 20-24, 2001
• 2: Manuel E. Acacio , José González , José M. García , José Duato, A Novel Approach to Reduce L2 Miss Latency in Shared-Memory Multiprocessors, Proceedings of the 16th International Parallel and Distributed Processing Symposium, p.25, April 15-19, 2002
• 3: Luiz André Barroso , Kourosh Gharachorloo , Edouard Bugnion, Memory system characterization of commercial workloads, Proceedings of the 25th annual international symposium on Computer architecture, p.3-14, June 27-July 02, 1998, Barcelona, Spain
• 4: E. Ender Bilir , Ross M. Dickson , Ying Hu , Manoj Plakal , Daniel J. Sorin , Mark D. Hill , David A. Wood, Multicast snooping: a new coherence method using a multicast address network, Proceedings of the 26th annual international symposium on Computer architecture, p.294-304, May 01-04, 1999, Atlanta, Georgia, United States
• 5: Alan Charlesworth, Starfire: Extending the SMP Envelope, IEEE Micro, v.18 n.1, p.39-49, January 1998 [doi>10.1109/40.653032]
• 6: David E. Culler , Anoop Gupta , Jaswinder Pal Singh, Parallel Computer Architecture: A Hardware/Software Approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1997
• 7: Kourosh Gharachorloo , Madhu Sharma , Simon Steely , Stephen Van Doren, Architecture and design of AlphaServer GS320, Proceedings of the ninth international conference on Architectural support for programming languages and operating systems, p.13-24, November 2000, Cambridge, Massachusetts, United States
• 8: Antonio González , Mateo Valero , Nigel Topham , Joan M. Parcerisa, Eliminating cache conflict misses through XOR-based placement functions, Proceedings of the 11th international conference on Supercomputing, p.76-83, July 07-11, 1997, Vienna, Austria [doi>10.1145/263580.263599]
• 9: A. Gupta, W.-D. Weber and T. Mowry. "Reducing Memory and Traffic Requirements for Scalable Directory-Based Cache Coherence Schemes". Proc. Int'l Conference on Parallel Processing (ICPP'90), pp. 312--321, August 1990.
• 10: L. Gwennap. "Alpha 21364 to Ease Memory Bottleneck". Microprocessor Report, pp. 12--15, October 1998.
• 11: Mark D. Hill, Multiprocessors Should Support Simple Memory-Consistency Models, Computer, v.31 n.8, p.28-34, August 1998 [doi>10.1109/2.707614]
• 12: Christopher J. Hughes , Vijay S. Pai , Parthasarathy Ranganathan , Sarita V. Adve, RSIM: Simulating Shared-Memory Multiprocessors with ILP Processors, Computer, v.35 n.2, p.40-49, February 2002 [doi>10.1109/2.982915]
• 13: Using Switch Directories to Speed Up Cache-to-Cache Transfers in CC-NUMA Multiprocessors, Proceedings of the 14th International Symposium on Parallel and Distributed Processing, p.721, May 01-05, 2000
• 14: Stefanos Kaxiras , James R. Goodman, Improving CC-NUMA Performance Using Instruction-Based Prediction, Proceedings of the 5th International Symposium on High Performance Computer Architecture, p.161, January 09-12, 1999
• 15: S. Kaxiras and C. Young. "Coherence Communication Prediction in Shared-Memory Multiprocessors". Proc. of the 6th Int'l High Performance Computer Architecture (HPCA-6), pp. 156--167, January 2000.
• 16: An-Chow Lai , Babak Falsafi, Memory sharing predictor: the key to a speculative coherent DSM, Proceedings of the 26th annual international symposium on Computer architecture, p.172-183, May 01-04, 1999, Atlanta, Georgia, United States
• 17: 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
• 18: 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
• 19: Shubhendu S. Mukherjee , Mark D. Hill, Using prediction to accelerate coherence protocols, Proceedings of the 25th annual international symposium on Computer architecture, p.179-190, June 27-July 02, 1998, Barcelona, Spain
• 20: Brian W. O'Krafka , A. Richard Newton, An empirical evaluation of two memory-efficient directory methods, Proceedings of the 17th annual international symposium on Computer Architecture, p.138-147, May 28-31, 1990, Seattle, Washington, United States
• 21: Vijay S. Pai , Parthasarathy Ranganathan , Hazim Abdel-Shafi , Sarita Adve, The Impact of Exploiting Instruction-Level Parallelism on Shared-Memory Multiprocessors, IEEE Transactions on Computers, v.48 n.2, p.218-226, February 1999 [doi>10.1109/12.752663]
• 22: 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]
• 23: 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
• 24: Z. Zhang. "Architectural Sensitive Application Characterization: The Approach of High-Performance Index-Set (HP-Set)". Technical Report HPL-2001--75, HP Laboratories Palo Alto, March 2001.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.2 Design Styles
          Subjects: Cache memories

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Multiple-instruction-stream, multiple-data-stream processors (MIMD)
  C.5 COMPUTER SYSTEM IMPLEMENTATION
      C.5.1 Large and Medium ("Mainframe") Computers

General Terms:
Design, Performance