An economical solution to the cache coherence problem

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

An economical solution to the cache coherence problem

Full text

Pdf (729 KB)

Source

International Symposium on Computer Architecture archive
Proceedings of the 11th annual international symposium on Computer architecture table of contents

Pages: 355 - 362

Year of Publication: 1984

ISBN:0-8186-0538-3

Also published in ...

Authors

James Archibald	Department of Computer Science, FR-35, University of Washington, Seattle, Wa
Jean Loup Baer	Department of Computer Science, FR-35, University of Washington, Seattle, Wa

Sponsors

ACM: Association for Computing Machinery
IEEE-CS : Computer Society

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 14, Downloads (12 Months): 78, Citation Count: 47

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/800015.808205 What is a DOI?

ABSTRACT

In this paper we review and qualitatively evaluate schemes to maintain cache coherence in tightly-coupled multiprocessor systems. This leads us to propose a more economical (hardware-wise), expandable and modular variation of the “global directory” approach. Protocols for this solution are described. Performance evaluation studies indicate the limits (number of processors, level of sharing) within which this approach is viable.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Bell,J.,Casasent,D. and C.G.Bell. "An Investigation of Alternative Cache Organizations." IEEE TC C-23, 4 (1974),346-351.
	2	Censier,L.M. and P.Feautrier. "A New Solution to Coherence Problems in Multicache Systems." IEEE TC C-27, 12 (Dec. 1978), 1112-1118.
	3	Dubois,M. and F.Briggs. "Effects of Cache Coherency in Multiprocessors." IEEE TC C-31, 11 (Nov.1982), 1083-1099.
	4	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
	5	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
	6	Satyanaranayan,M. "Commercial Multiprocessing Systems." Computer 13, 5 (1980), 75-96.
	7	Alan Jay Smith, Cache Memories, ACM Computing Surveys (CSUR), v.14 n.3, p.473-530, Sept. 1982 [doi>10.1145/356887.356892]
	8	Tang,C.K. Cache System Design in the Tightly Coupled Multiprocessor System. Proc. 1976 AFIPS Nat. Comp. Conf., AFIPS, 1976, pp. 749-753.
	9	Widdoes,L.C. High-Performance Digital Computer Development in the S-1 Project. Proc. of IEEE Compcon, IEEE, 1980, pp. 282-291.
	10	Yen,W.C. and K.S.Fu. Coherence Problem in a Multicache System. Proc. of 1982 Int. Conf. on Parallel Processing, IEEE, 1982, pp. 332-339.

CITED BY 47

	John C. Willis , Arthur C. Sanderson , Charles R. Hill, Cache coherence in systems with parallel communication channels & many processors, Proceedings of the 1990 conference on Supercomputing, p.554-563, October 1990, New York, New York, United States
	Yung-Chin Chen , Alexander V. Veidenbaum, Comparison and analysis of software and directory coherence schemes, Proceedings of the 1991 ACM/IEEE conference on Supercomputing, p.818-829, November 18-22, 1991, Albuquerque, New Mexico, United States
	Hoichi Cheong, Life span strategy—a compiler-based approach to cache coherence, Proceedings of the 6th international conference on Supercomputing, p.139-148, July 19-24, 1992, Washington, D. C., United States
	Brian W. O'Krafka , A. Richard Newton, An empirical evaluation of two memory-efficient directory methods, ACM SIGARCH Computer Architecture News, v.18 n.3a, p.138-147, June 1990
	D. R. Cheriton , H. A. Goosen , P. D. Boyle, Multi-level shared caching techniques for scalability in VMP-M/C, ACM SIGARCH Computer Architecture News, v.17 n.3, p.16-24, June 1989
	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
	P. Sweazey , A. J. Smith, A class of compatible cache consistency protocols and their support by the IEEE futurebus, ACM SIGARCH Computer Architecture News, v.14 n.2, p.414-423, June 1986
	Sang L. Min , Jong-Deok Choi, An efficient cache-based access anomaly detection scheme, ACM SIGARCH Computer Architecture News, v.19 n.2, p.235-244, Apr. 1991
	Anant Agarwal , Richard Simoni , John Hennessy , Mark Horowitz, An evaluation of directory schemes for cache coherence, 25 years of the international symposia on Computer architecture (selected papers), p.353-362, June 27-July 02, 1998, Barcelona, Spain
	R. L. Lee , P. C. Yew , D. H. Lawrie, Multiprocessor cache design considerations, Proceedings of the 14th annual international symposium on Computer architecture, p.253-262, June 02-05, 1987, Pittsburgh, Pennsylvania, United States
	A. Agarwal , R. Simoni , J. Hennessy , M. Horowitz, An evaluation of directory schemes for cache coherence, ACM SIGARCH Computer Architecture News, v.16 n.2, p.280-298, May 1988
	H. Cheong , A. V. Vaidenbaum, A cache coherence scheme with fast selective invalidation, ACM SIGARCH Computer Architecture News, v.16 n.2, p.299-307, May 1988
	Kai Li , Paul Hudak, Memory coherence in shared virtual memory systems, ACM Transactions on Computer Systems (TOCS), v.7 n.4, p.321-359, Nov. 1989
	Daniel Lenoski , James Laudon , Kourosh Gharachorloo , Anoop Gupta , John Hennessy, The directory-based cache coherence protocol for the DASH multiprocessor, ACM SIGARCH Computer Architecture News, v.18 n.3a, p.148-159, June 1990
	J.-L. Baer , W.-H. Wang, On the inclusion properties for multi-level cache hierarchies, ACM SIGARCH Computer Architecture News, v.16 n.2, p.73-80, May 1988
	D. E. Marquardt , H. S. Alkhatib, C²MP: a cache-coherent, distributed memory multiprocessor-system, Proceedings of the 1989 ACM/IEEE conference on Supercomputing, p.466-475, November 12-17, 1989, Reno, Nevada, United States
	D. R. Cheriton , A. Gupta , P. D. Boyle , H. A. Goosen, The VMP multiprocessor: initial experience, refinements, and performance evaluation, ACM SIGARCH Computer Architecture News, v.16 n.2, p.410-421, May 1988
	Kazuaki Murakami , Shin-ichiro Mori , Akira Fukuda , Toshinori Sueyoshi , Shinji Tomita, The Kyushu University reconfigurable parallel processor: design of memory and intercommunicaiton architectures, Proceedings of the 3rd international conference on Supercomputing, p.351-360, June 05-09, 1989, Crete, Greece
	Yung-Chin Chen , Alexander V. Veidenbaum, A software coherence scheme with the assistance of directories, Proceedings of the 5th international conference on Supercomputing, p.284-294, June 17-21, 1991, Cologne, West Germany
	Mark D. Hill , James R. Larus , Steven K. Reinhardt , David A. Wood, Cooperative shared memory: software and hardware for scalable multiprocessor, ACM SIGPLAN Notices, v.27 n.9, p.262-273, Sept. 1992
	Farnaz Mounes-Toussi , David J. Lilja , Zhiyuan Li, An evaluation of a compiler optimization for improving the performance of a coherence directory, Proceedings of the 8th international conference on Supercomputing, p.75-84, July 11-15, 1994, Manchester, England
	Feipei Lai , Chyuan-Yow Wu , Tai-Ming Parng, A memory management unit and cache controller for the MARS system, Proceedings of the 23rd annual workshop and symposium on Microprogramming and microarchitecture, p.200-208, November 27-29, 1990, Orlando, Florida, United States
	David J. Lilja , Pen-Chung Yew, Combining hardware and software cache coherence strategies, Proceedings of the 5th international conference on Supercomputing, p.274-283, June 17-21, 1991, Cologne, West Germany
	Mark D. Hill , James R. Larus , Steven K. Reinhardt , David A. Wood, Cooperative shared memory: software and hardware for scalable multiprocessors, ACM Transactions on Computer Systems (TOCS), v.11 n.4, p.300-318, Nov. 1993
	Ashwini K. Nanda , Hong Jiang, Analysis of directory based cache coherence schemes with multistage networks, Proceedings of the 1992 ACM annual conference on Communications, p.485-492, March 03-05, 1992, Kansas City, Missouri, United States
	P. Bitar , A. M. Despain, Multiprocessor cache synchronization: issues, innovations, evolution, ACM SIGARCH Computer Architecture News, v.14 n.2, p.424-433, June 1986
	S. J. Eggers , R. H. Katz, A characterization of sharing in parallel programs and its application to coherency protocol evaluation, ACM SIGARCH Computer Architecture News, v.16 n.2, p.373-382, May 1988
	Cosimo Antonio Prete, A process cache memory for tightly coupled multiprocessor systems, Proceedings of the 30th annual Southeast regional conference, April 08-10, 1992, Raleigh, North Carolina
	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
	Seungjoon Park , David L. Dill, Verification of FLASH cache coherence protocol by aggregation of distributed transactions, Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.288-296, June 24-26, 1996, Padua, Italy
	Sang Lyul Min , Jean-Loup Baer , Hyoung-Joo Kim, An efficient caching support for critical sections in large-scale shared-memory multiprocessors, ACM SIGARCH Computer Architecture News, v.18 n.3b, p.34-47, Sept. 1990
	David Chaiken , John Kubiatowicz , Anant Agarwal, LimitLESS directories: A scalable cache coherence scheme, ACM SIGPLAN Notices, v.26 n.4, p.224-234, Apr. 1991
	Cosimo A. Prete, RST Cache Memory Design for a Highly Coupled Multiprocessor System, IEEE Micro, v.11 n.2, p.16-19, 40-52, March 1991
	John M. Mellor-Crummey , Michael L. Scott, Algorithms for scalable synchronization on shared-memory multiprocessors, ACM Transactions on Computer Systems (TOCS), v.9 n.1, p.21-65, Feb. 1991
	David J. Lilja, Cache coherence in large-scale shared-memory multiprocessors: issues and comparisons, ACM Computing Surveys (CSUR), v.25 n.3, p.303-338, Sept. 1993
	Jean-Loup Baer , Wen-Hann Wang, On the inclusion properties for multi-level cache hierarchies, 25 years of the international symposia on Computer architecture (selected papers), p.345-352, June 27-July 02, 1998, Barcelona, Spain
	K. L. Wu , W. K. Fuchs , J. H. Patel, Error Recovery in Shared Memory Multiprocessors Using Private Caches, IEEE Transactions on Parallel and Distributed Systems, v.1 n.2, p.231-240, April 1990
	A. K. Nanda , L. N. Bhuyan, Design and Analysis of Cache Coherent Multistage Interconnection Networks, IEEE Transactions on Computers, v.42 n.4, p.458-470, April 1993
	D. J. Lilja , P. C. Yew, Improving Memory Utilization in Cache Coherence Directories, IEEE Transactions on Parallel and Distributed Systems, v.4 n.10, p.1130-1146, October 1993
	Hoichi Cheong , Alex Veidenbaum, A version control approach to Cache coherence, Proceedings of the 3rd international conference on Supercomputing, p.322-330, June 05-09, 1989, Crete, Greece
	Lynn Choi , Pen-Chung Yew, Hardware and Compiler-Directed Cache Coherence in Large-Scale Multiprocessors: Design Considerations and Performance Study, IEEE Transactions on Parallel and Distributed Systems, v.11 n.4, p.375-394, April 2000
	Farnaz Mounes-Toussi , David J. Lilja, The Potential of Compile-Time Analysis to Adapt the Cache Coherence Enforcement Strategy to the Data Sharing Characteristics, IEEE Transactions on Parallel and Distributed Systems, v.6 n.5, p.470-481, May 1995
	Trung N. Nguyen , Farnaz Mounes-Toussi , David J. Lilja , Zhiyuan Li, A Compiler-Assisted Scheme for Adaptive Cache Coherence Enforcement, Proceedings of the IFIP WG10.3 Working Conference on Parallel Architectures and Compilation Techniques, p.69-78, August 24-26, 1994
	Hoichi Cheong , Alexander V. Viedenbaum, Compiler-Directed Cache Management in Multiprocessors, Computer, v.23 n.6, p.39-47, June 1990
	Benjamin Maytal , Dan Biran , Sorin Iacobovici , Jonathan Levy , Donald B. Alpert , Sidi Yom Tov, Design Considerations for a General-Purpose Microprocessor, Computer, v.22 n.1, p.66-76, January 1989
	R. H. Katz , S. J. Eggers , D. A. Wood , C. L. Perkins , R. G. Sheldon, Implementing a cache consistency protocol, ACM SIGARCH Computer Architecture News, v.13 n.3, p.276-283, June 1985
	Reinder J. Bril, On cacheability of lock-variables in tightly coupled multiprocessor systems, ACM SIGARCH Computer Architecture News, v.15 n.3, p.25-32, June 1987