A consistency architecture for hierarchical shared caches

ABSTRACT

Hierarchical Cache Consistency (HCC) is a scalable cache-consistency architecture for chip multiprocessors in which caches are shared hierarchically. HCC's cache-consistency protocol is embedded in the message-routing network that interconnects the caches, providing a distributed and scalable alternative to bus-based and directory-based consistency mechanisms. The HCC consistency protocol is "progressive" in that every message makes monotonic progress without timeouts, retries, negative acknowledgments, or retreating in any way. The latency is at most proportional to the diameter of the network. For HCC with a binary fat-tree network, the protocol requires at most 13 bits of additional state per cache line, no matter how large the system. We prove that the HCC protocol is deadlock free and provides sequential consistency.

REFERENCES

• 1: Manuel E. Acacio , Jose Gonzalez , Jose M. Garcia , Jose Duato, A Two-Level Directory Architecture for Highly Scalable cc-NUMA Multiprocessors, IEEE Transactions on Parallel and Distributed Systems, v.16 n.1, p.67-79, January 2005 [doi>10.1109/TPDS.2005.4]
• 2: Manuel E. Acacio , Jose Gonzalez , Jose M. Garcia , Jose Duato, An Architecture for High-Performance Scalable Shared-Memory Multiprocessors Exploiting On-Chip Integration, IEEE Transactions on Parallel and Distributed Systems, v.15 n.8, p.755-768, August 2004 [doi>10.1109/TPDS.2004.27]
• 3: 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
• 4: Advanced Micro Devices. AMD64 Architecture Programmer's Manual, Volume 2: System Programming, July 2007.
• 5: A. Agarwal, R. Simoni, J. Hennessy, and M. Horowitz. An evaluation of directory schemes for cache coherence. In ISCA, 2008.
• 6: Arvind, Bluespec: A language for hardware design, simulation, synthesis and verification Invited Talk, Proceedings of the First ACM and IEEE International Conference on Formal Methods and Models for Co-Design, p.249, June 24-26, 2003
• 7: J.-L. Baer , W.-H. Wang, On the inclusion properties for multi-level cache hierarchies, Proceedings of the 15th Annual International Symposium on Computer architecture, p.73-80, May 30-June 02, 1988, Honolulu, Hawaii, United States
• 8: Evgeny Bolotin , Zvika Guz , Israel Cidon , Ran Ginosar , Avinoam Kolodny, The Power of Priority: NoC Based Distributed Cache Coherency, Proceedings of the First International Symposium on Networks-on-Chip, p.117-126, May 07-09, 2007 [doi>10.1109/NOCS.2007.42]
• 9: Jichuan Chang , Gurindar S. Sohi, Cooperative Caching for Chip Multiprocessors, Proceedings of the 33rd annual international symposium on Computer Architecture, p.264-276, June 17-21, 2006
• 10: Yeimkuan Chang , Laxmi N. Bhuyan, An Efficient Tree Cache Coherence Protocol for Distributed Shared Memory Multiprocessors, IEEE Transactions on Computers, v.48 n.3, p.352-360, March 1999 [doi>10.1109/12.755001]
• 11: Liqun Cheng , Naveen Muralimanohar , Karthik Ramani , Rajeev Balasubramonian , John B. Carter, Interconnect-Aware Coherence Protocols for Chip Multiprocessors, Proceedings of the 33rd annual international symposium on Computer Architecture, p.339-351, June 17-21, 2006
• 12: D. R. Cheriton , H. A. Goosen , P. D. Boyle, Multi-level shared caching techniques for scalability in VMP-M/C, Proceedings of the 16th annual international symposium on Computer architecture, p.16-24, April 1989, Jerusalem, Israel
• 13: William J. Dally , Brian Towles, Route packets, not wires: on-chip inteconnection networks, Proceedings of the 38th conference on Design automation, p.684-689, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.379048]
• 14: Noel Eisley , Li-Shiuan Peh , Li Shang, In-Network Cache Coherence, Proceedings of the 39th Annual IEEE/ACM International Symposium on Microarchitecture, p.321-332, December 09-13, 2006 [doi>10.1109/MICRO.2006.27]
• 15: M. Frigo. The weakest reasonable memory model. Master's thesis, MIT EECS, 1998.
• 16: James R. Goodman, Using cache memory to reduce processor-memory traffic, Proceedings of the 10th annual international symposium on Computer architecture, p.124-131, June 13-17, 1983, Stockholm, Sweden
• 17: 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]
• 18: Intel Corporation. Intel 64 and IA-32 Architectures Software Developer's Manual, Volume 3A: System Programming Guide, Part 1, October 2006.
• 19: 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]
• 20: Changkyu Kim , Doug Burger , Stephen W. Keckler, An adaptive, non-uniform cache structure for wire-delay dominated on-chip caches, Proceedings of the 10th international conference on Architectural support for programming languages and operating systems, October 05-09, 2002, San Jose, California
• 21: Rakesh Kumar , Victor Zyuban , Dean M. Tullsen, Interconnections in Multi-Core Architectures: Understanding Mechanisms, Overheads and Scaling, Proceedings of the 32nd annual international symposium on Computer Architecture, p.408-419, June 04-08, 2005
• 22: Chat-Yu Lam , Stuart E. Madnick, Propeties of storage hierarchy systems with multiple page sizes and redundant data, ACM Transactions on Database Systems (TODS), v.4 n.3, p.345-367, Sept. 1979 [doi>10.1145/320083.320095]
• 23: L. Lamport, How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Progranm, IEEE Transactions on Computers, v.28 n.9, p.690-691, September 1979 [doi>10.1109/TC.1979.1675439]
• 24: F. Thomson Leighton , Bruce M. Maggs, Fast Algorithms for Routing Around Faults in Multibutterflies and Randomly-Wired Splitter Networks, IEEE Transactions on Computers, v.41 n.5, p.578-587, May 1992 [doi>10.1109/12.142684]
• 25: Charles E. Leiserson, The Networks of the Connection Machine CM-5, Proceedings of the First Heinz Nixdorf Symposium on Parallel Architectures and Their Efficient Use, p.66-67, November 11-13, 1992
• 26: Daniel Lenoski , James Laudon , Truman Joe , David Nakahira , Luis Stevens , Anoop Gupta , John Hennessy, The DASH prototype: implementation and performance, 25 years of the international symposia on Computer architecture (selected papers), p.418-429, June 27-July 02, 1998, Barcelona, Spain [doi>10.1145/285930.286001]
• 27: Milo M. K. Martin , Mark D. Hill , David A. Wood, Token coherence: decoupling performance and correctness, Proceedings of the 30th annual international symposium on Computer architecture, June 09-11, 2003, San Diego, California
• 28: Michael R. Marty , Mark D. Hill, Coherence Ordering for Ring-based Chip Multiprocessors, Proceedings of the 39th Annual IEEE/ACM International Symposium on Microarchitecture, p.309-320, December 09-13, 2006 [doi>10.1109/MICRO.2006.14]
• 29: Michael R. Marty , Mark D. Hill, Virtual hierarchies to support server consolidation, Proceedings of the 34th annual international symposium on Computer architecture, June 09-13, 2007, San Diego, California, USA
• 30: H. E. Mizrahi , J. L. Baer , E. D. Lazowska , J. Zahorjan, Introducing memory into the switch elements of multiprocessor interconnection networks, Proceedings of the 16th annual international symposium on Computer architecture, p.158-166, April 1989, Jerusalem, Israel
• 31: S. Mori , H. Saito , M. Goshima , S. Tomita , M. Yanagihara , T. Tanaka , D. Fraser , K. Joe , H. Nitta, A distributed shared memory multiprocessor ASURA: memory and cache architecture, Proceedings of the 1993 ACM/IEEE conference on Supercomputing, p.740-749, December 1993, Portland, Oregon, United States [doi>10.1145/169627.169825]
• 32: H. Nilsson and P. Stenstrom. The scalable tree protocol-a cache coherence approach for large-scale multiprocessors. In IPDPS, 1992.
• 33: David A. Patterson , John L. Hennessy, Computer organization and design (2nd ed.): the hardware/software interface, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
• 34: S. Przybylski , M. Horowitz , J. Hennessy, Characteristics of performance-optimal multi-level cache hierarchies, Proceedings of the 16th annual international symposium on Computer architecture, p.114-121, April 1989, Jerusalem, Israel
• 35: Alberto Ros , Manuel E. Acacio , José M. García, An efficient cache design for scalable glueless shared-memory multiprocessors, Proceedings of the 3rd conference on Computing frontiers, May 03-05, 2006, Ischia, Italy [doi>10.1145/1128022.1128065]
• 36: X. Shen and Arvind. Specification of memory models and design of provably correct cache coherence protocols. Technical Report 398, MIT Computation Structures Group, 1997.
• 37: Xiaowei Shen , Arvind , Larry Rudolph, CACHET: an adaptive cache coherence protocol for distributed shared-memory systems, Proceedings of the 13th international conference on Supercomputing, p.135-144, June 20-25, 1999, Rhodes, Greece [doi>10.1145/305138.305187]
• 38: Evan Speight , Hazim Shafi , Lixin Zhang , Ram Rajamony, Adaptive Mechanisms and Policies for Managing Cache Hierarchies in Chip Multiprocessors, Proceedings of the 32nd annual international symposium on Computer Architecture, p.346-356, June 04-08, 2005
• 39: Karin Strauss , Xiaowei Shen , Josep Torrellas, Flexible Snooping: Adaptive Forwarding and Filtering of Snoops in Embedded-Ring Multiprocessors, Proceedings of the 33rd annual international symposium on Computer Architecture, p.327-338, June 17-21, 2006
• 40: A. W. Wilson, Jr., Hierarchical cache/bus architecture for shared memory multiprocessors, Proceedings of the 14th annual international symposium on Computer architecture, p.244-252, June 02-05, 1987, Pittsburgh, Pennsylvania, United States [doi>10.1145/30350.30378]
• 41: Q. Yang , G. Thangadurai , L. M. Bhuyan, Design of an Adaptive Cache Coherence Protocol for Large Scale Multiprocessors, IEEE Transactions on Parallel and Distributed Systems, v.3 n.3, p.281-293, May 1992 [doi>10.1109/71.139202]

INDEX TERMS

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

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

  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.4 Parallel Architectures

General Terms:
Design, Performance, Theory

Keywords:
cache consistency, deadlock, fat-tree, mapping collision, memory hierarchy, message race, progressive protocol, sequential consistency, shared caches