A cache coherence approach for large multiprocessor systems

ABSTRACT

This paper explores the architecture of high-performance large scale multiprocessors using private caches for each processor. The caches reduce the average memory access time, but they also result in the well known cache coherence problem. Multiple copies of each memory location are allowed to exist but they must be kept consistent with each other. In this paper, we present a solution to the cache coherence problem specifically for shared bus multiprocessors that adapts dynamically to the reference pattern. Simulation results are presented that demonstrate the high level of performance relative to other protocols particularly during intervals with high levels of sharing. The paper then presents a coherence solution for large multiprocessor systems organized around a hierarchy of buses. One of the first solutions of this kind, the hierarchical protocol is an extension of the adaptive shared bus approach described in this paper.

REFERENCES

• 1: J. K. Archibald, The cache coherence problem in shared-memory multiprocessors, University of Washington, Seattle, WA, 1987
• 2: J. Archibald. High Performance Cache Coherence Protocols For Shared-Bus Multiprocessors. Technical Report Tit 86-06-02, Department of Computer Science, University of Washington, Seattle, WA 98195, June 1986.
• 3: James Archibald , Jean-Loup Baer, Cache coherence protocols: evaluation using a multiprocessor simulation model, ACM Transactions on Computer Systems (TOCS), v.4 n.4, p.273-298, Nov. 1986 [doi>10.1145/6513.6514]
• 4: J.-L. Boer and W.-H. Wang. Architectural choices for multi-level cache hierarchies. In Proc. of 16th Int. Conf. on Parallel Processing, pages 258-261, IEEE, 1987.
• 5: J.-L. Baer and W.-H. Wang. On the Inclusion Properties for Multi-Level Cache Hierarchies. Technical Report TR- 87-11-08, Dept. of Computer Science, University of Washiugton, Seattle, WA 98195, November 1987.
• 6: M. Dubois and F. B riggs. Effects of cache coherency in multiprocessors. IEEE Transactions on Computers, C- 31(11):1083-1099, November 1982.
• 7: S. J. Eggers , R. H. Katz, A characterization of sharing in parallel programs and its application to coherency protocol evaluation, Proceedings of the 15th Annual International Symposium on Computer architecture, p.373-382, May 30-June 02, 1988, Honolulu, Hawaii, United States
• 8: S. J. Frank. Tightly coupled multiprocessor systems speed memory access times. Electronics, 57(1):164-169, January 1984.
• 9: 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
• 10: R. H. Katz , S. J. Eggers , D. A. Wood , C. L. Perkins , R. G. Sheldon, Implementing a cache consistency protocol, Proceedings of the 12th annual international symposium on Computer architecture, p.276-283, June 17-19, 1985, Boston, Massachusetts, United States
• 11: E. McCreight. The Dragon Computer System: An Early Overview. Technical Report, Xerox Corp., September 1984.
• 12: Mark S. Papamarcos , Janak H. Patel, A low-overhead coherence solution for multiprocessors with private cache memories, Proceedings of the 11th annual international symposium on Computer architecture, p.348-354, January 1984
• 13: Larry Rudolph , Zary Segall, Dynamic decentralized cache schemes for mimd parallel processors, Proceedings of the 11th annual international symposium on Computer architecture, p.340-347, January 1984
• 14: M. C. Shebanow and Y. N. Patt. The adaptive cache coherence protocol-a predictive based solution to the cache coherence problem. Forthcoming paper.
• 15: 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]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Interconnection architectures (e.g., common bus, multiport memory, crossbar switch)

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

  C. Computer Systems Organization
  C.5 COMPUTER SYSTEM IMPLEMENTATION
      C.5.1 Large and Medium ("Mainframe") Computers
          Subjects: Super (very large) computers

General Terms:
Design, Performance