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. 1.J. Archibald. The Cache Coherence Problem in Shared- Memory Multiprocessors. PhD Thesis~ University of Washington, March 1987.
2. 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. 3.J. Archibald and J.-L. Boer. Cache coherence protocols: evaluation using a multiprocessor simulation model. A CM Transactions or, Computer Systems, 4(4):273-298, November 1986.
4. 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. 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. 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. 7.S. Eggers and It. Katz. Characterization of sharing in parallel programs and its applicability to coherency protocol evaluation. In Proc. of 15th Int. Syrup. on Computer Architecture, IEEE, 1988.
8. 8.S. J. Frank. Tightly coupled multiprocessor systems speed memory access times. Electronics, 57(1):164-169, January 1984.
9. 9.J. R. Goodman. Using cache memory to reduce processormemory traffic, in Proc. of l Oth Int. Syrup. on Computer Architecture, pages 124-131, IEEE, 1983.
10. 10.R. Katz, S. Eggers, D. A. Wood, C. Perkins, and R. G. Sheldon. Implementing a cache consistency protocol. In Proc. of 12th Int. Syrup. on Computer Architecture, pages 276-283, IEEE, 1985.
11. 11.E. McCreight. The Dragon Computer System: An Early Overview. Technical Report, Xerox Corp., September 1984.
12. 12.M. Papamarcos and J. Patel. A low overhead coherence solution for multiprocessors with private cache memories. In Proc. of 11th Int. Syrup. on Computer Architecture, pages 348-354, IEEE, 1984.
13. 13.L. Rudolph and Z. Segall. Dynamic decentralized cache schemes for MIMD parallel processors, in Proc. o.f 11th Int. Syrup. on Computer Architecture, pages 340-347, IEEE, 1984.
14. 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. 15.A. W. Wilson Jr. Hierarchical cache/bus architecture for shared memory multiprocessors. In Proc. o} 14th Int. Syrup. on Computer Architecture, pages 244-252, IEEE, 1987.

Index Terms

• Computer systems organization

  • Architectures

    • Distributed architectures

      • Grid computing

    • Parallel architectures

      • Interconnection architectures

      • Multicore architectures

    • Serial architectures

      • Superscalar architectures

• Computing methodologies

  • Modeling and simulation

    • Simulation types and techniques

      • Massively parallel and high-performance simulations

• Hardware

  • Integrated circuits

    • Semiconductor memory

      • Dynamic memory

• Software and its engineering

  • Software organization and properties

    • Software system structures

      • Distributed systems organizing principles

        • Grid computing