Cache coherence in large-scale shared-memory multiprocessors

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Cache coherence in large-scale shared-memory multiprocessors: issues and comparisons

Full text

Pdf (3.12 MB)

Source

ACM Computing Surveys (CSUR) archive
Volume 25 , Issue 3 (September 1993) table of contents

Pages: 303 - 338

Year of Publication: 1993

ISSN:0360-0300

Author

David J. Lilja

Univ. of Minnesota, Minneapolis

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 14, Downloads (12 Months): 161, Citation Count: 22

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions 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/158439.158907 What is a DOI?

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	Sarita V. Adve , Vikram S. Adve , Mark D. Hill , Mary K. Vernon, Comparison of hardware and software cache coherence schemes, Proceedings of the 18th annual international symposium on Computer architecture, p.298-308, May 27-30, 1991, Toronto, Ontario, Canada
	2	A. Agawal , A. Gupta, Memory-reference characteristics of multiprocessor applications under MACH, Proceedings of the 1988 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.215-225, May 24-27, 1988, Santa Fe, New Mexico, United States
	3	A. Agarwal , R. Simoni , J. Hennessy , M. Horowitz, An evaluation of directory schemes for cache coherence, Proceedings of the 15th Annual International Symposium on Computer architecture, p.280-298, May 30-June 02, 1988, Honolulu, Hawaii, United States
	4	T. E. Anderson, The Performance of Spin Lock Alternatives for Shared-Money Multiprocessors, IEEE Transactions on Parallel and Distributed Systems, v.1 n.1, p.6-16, January 1990 [doi>10.1109/71.80120]
	5	J. K. Archibald, A cache coherence approach for large multiprocessor systems, Proceedings of the 2nd international conference on Supercomputing, p.337-345, June 1988, St. Malo, France [doi>10.1145/55364.55397]
	6	James Archibald , Jean Loup Baer, An economical solution to the cache coherence problem, Proceedings of the 11th annual international symposium on Computer architecture, p.355-362, January 1984
	7	Utpal K. Banerjee, Dependence Analysis for Supercomputing, Kluwer Academic Publishers, Norwell, MA, 1988
	8	John K. Bennett , John B. Carter , Willy Zwaenepoel, Adaptive software cache management for distributed shared memory architectures, Proceedings of the 17th annual international symposium on Computer Architecture, p.125-134, May 28-31, 1990, Seattle, Washington, United States
	9	BnUYAN, L. N., LIu, B.-C., ANU AnnEu, I. 1989. Analysis of MIN-based nmltiprocessors with private cache memories. In the International Conference on Parallel Processing. Vol. 1. Archztecture, 51 58.
	10	BRANTLEY, W. C., MCAULIFFE, K. P., AND WEISS, J. 1985. RP3 processor-memory element. In the International Conference on Parallel Processlng, 782 789.
	11	CENS{ER, L. M., AND FEAUTmEn, P. 1978. A new solution to coherence problems m multlcache systems. IEEE Trans. Comput. C-27, (Dec.), 1112-1118.
	12	David Chaiken , John Kubiatowicz , Anant Agarwal, LimitLESS directories: A scalable cache coherence scheme, Proceedings of the fourth international conference on Architectural support for programming languages and operating systems, p.224-234, April 08-11, 1991, Santa Clara, California, United States
	13	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 [doi>10.1145/109025.109095]
	14	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 [doi>10.1145/318789.318824]
	15	H. Cheong , A. V. Vaidenbaum, A cache coherence scheme with fast selective invalidation, Proceedings of the 15th Annual International Symposium on Computer architecture, p.299-307, May 30-June 02, 1988, Honolulu, Hawaii, United States
	16	CHEONG, H , AND VEIDENBAUM, A V 1988b Stale data detectmn and coherence enforcement using flow analysm. In the International Conference on Parallel Processing. Vo}. I, Archttecture, 138-145
	17	Michel, Dubois , Christoph Scheurich , Fayé A. Briggs, Synchronization, Coherence, and Event Ordering in Multiprocessors, Computer, v.21 n.2, p.9-21, February 1988 [doi>10.1109/2.15]
	18	Jan Edler , Allan Gottlieb , Clyde P. Kruskal , Kevin P. McAuliffe , Larry Rudolph , Marc Snir , Patricia J. Teller , James Wilson, Issues related to MIMD shared-memory computers: the NYU ultracomputer approach, Proceedings of the 12th annual international symposium on Computer architecture, p.126-135, June 17-19, 1985, Boston, Massachusetts, United States
	19	S. J. Eggers , R. H. Katz, The effect of sharing on the cache and bus performance of parallel programs, Proceedings of the third international conference on Architectural support for programming languages and operating systems, p.257-270, April 03-06, 1989, Boston, Massachusetts, United States
	20	S. J. Eggers , R. H. Katz, Evaluating the performance of four snooping cache coherency protocols, Proceedings of the 16th annual international symposium on Computer architecture, p.2-15, April 1989, Jerusalem, Israel
	21	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
	22	Kourosh Gharachorloo , Anoop Gupta , John Hennessy, Performance evaluation of memory consistency models for shared-memory multiprocessors, Proceedings of the fourth international conference on Architectural support for programming languages and operating systems, p.245-257, April 08-11, 1991, Santa Clara, California, United States
	23	Kourosh Gharachorloo , Daniel Lenoski , James Laudon , Phillip Gibbons , Anoop Gupta , John Hennessy, Memory consistency and event ordering in scalable shared-memory multiprocessors, Proceedings of the 17th annual international symposium on Computer Architecture, p.15-26, May 28-31, 1990, Seattle, Washington, United States
	24	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
	25	J. R. Goodman , P. J. Woest, The Wisconsin multicube: a new large-scale cache-coherent multiprocessor, Proceedings of the 15th Annual International Symposium on Computer architecture, p.422-431, May 30-June 02, 1988, Honolulu, Hawaii, United States
	26	James R. Goodman , Mary K. Vernon , Philip J. Woest, Efficient synchronization primitives for large-scale cache-coherent multiprocessors, Proceedings of the third international conference on Architectural support for programming languages and operating systems, p.64-75, April 03-06, 1989, Boston, Massachusetts, United States
	27	Allan Gottlieb , Ralph Grishman , Clyde P. Kruskal , Kevin P. McAuliffe , Larry Rudolph , Marc Snir, The NYU Ultracomputer—designing a MIMD, shared-memory parallel machine (Extended Abstract), Proceedings of the 9th annual symposium on Computer Architecture, p.27-42, April 26-29, 1982, Austin, Texas, United States
	28	Anoop Gupta , John Hennessy , Kourosh Gharachorloo , Todd Mowry , Wolf-Dietrich Weber, Comparative evaluation of latency reducing and tolerating techniques, Proceedings of the 18th annual international symposium on Computer architecture, p.254-263, May 27-30, 1991, Toronto, Ontario, Canada
	29	GUPTA, A., WEBER, W.-D., AND MOWRY, T. 1990. Reducing memory and traffic reqmrements for scalable directory-based cache coherence schemes. In the International Conference on Parallel Processing Vol. I, Archzteeture, 312-321.
	30	David V. James , Anthony T. Laundrie , Stein Gjessing , Gurindar Sohi, Scalable coherent interface, Computer, v.23 n.6, p.74-77, June 1990 [doi>10.1109/2.55503]
	31	KARLINE, A. R., MANASS, M S., RUDOLPH, L., AND SENATOR, D. D 1986. Competitive snoopy cachemg. In the Symposmm on Foundatmns of Computer Sczence, 244-254.
	32	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
	33	Clyde P Kruskal , Larry Rudolph , Marc Snir, Efficient synchronization of multiprocessors with shared memory, Proceedings of the fifth annual ACM symposium on Principles of distributed computing, p.218-228, August 11-13, 1986, Calgary, Alberta, Canada [doi>10.1145/10590.10609]
	34	KUCK, D J, DAVIDSON, E S., LAWRIE, D. J., AND SAMEH, A.H. 1986. Parallel supercomputing today and the Cedar approach Science 231 (Feb. 28l, 967-974.
	35	LAMPORT, L. 1979 How to make a multiprocessot computer that correctly executes multiprocess programs. IEEE Trans. Comput. C-28, 9, {Sept ), 690-691
	36	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 [doi>10.1145/30350.30379]
	37	Daniel Lenoski , James Laudon , Kourosh Gharachorloo , Wolf-Dietrich Weber , Anoop Gupta , John Hennessy , Mark Horowitz , Monica S. Lam, The Stanford Dash Multiprocessor, Computer, v.25 n.3, p.63-79, March 1992 [doi>10.1109/2.121510]
	38	Daniel Lenoski , James Laudon , Kourosh Gharachorloo , Anoop Gupta , John Hennessy, The directory-based cache coherence protocol for the DASH multiprocessor, Proceedings of the 17th annual international symposium on Computer Architecture, p.148-159, May 28-31, 1990, Seattle, Washington, United States
	39	Z. Li , P. C. Yew , C. Q. Zhu, An Efficient Data Dependence Analysis for Parallelizing Compilers, IEEE Transactions on Parallel and Distributed Systems, v.1 n.1, p.26-34, January 1990 [doi>10.1109/71.80122]
	40	A. Lichnewsky , F. Thomasset, Introducing symbolic problem solving techniques in the dependence testing phases of a vectorizer, Proceedings of the 2nd international conference on Supercomputing, p.396-406, June 1988, St. Malo, France [doi>10.1145/55364.55403]
	41	LmJA, D.J. 1992. Prefetching and scheduling interactions m shared memory multlprocessors. In the Midwest Electrotechnology Con/erence, 84 87.
	42	IAIAA, D. J. 1991. Processor parallehsm consideratnms and memory latency reductmn in shared memory multiprocessors Rep. No. 1136, Center for Supercomputing Research and Development, Univ of I}linms, Urbana.
	43	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 [doi>10.1145/109025.109093]
	44	LILJA, D. J., MAR('.(>VlTZ. D. M., AND YEW, P.-C. 1989 Memory referencing' behavior and a cache performance metric in a shared memory multiprocessor Rep. No. 836, Center for Supercomputing Research and Development, Univ. of Illlnms, Urbana.
	45	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 [doi>10.1145/76263.76315]
	46	McCImICHT, E. M 1984. The Dragon Computer System, an early overview. In the NATO Advanced Study blstitute on Mwroarchztecture VLSI Camp uters, 83-101.
	47	MIN, S. L., AND BAER, J -L. 1990. A performance comparison of directory-based and timestampbased cache coherence schemes. In the International Conference on Parallel Processing. Vol. I, Architecture, 305 311.
	48	MIN. S. L., AND BAER J.-L. 1989. A timestampbased cache coherence scheme. In the International Con/Frencc on Parallel Processing. Vol. I, Architecture, 23 32
	49	MIZRAHI, H. E, BAER, J.-L., LAZOWSKA, E. D., AND ZAHORJAN, J. 1989. Extending- the memory hierarchy into multiprocessor lnterconnectian networks A performance analysis, in the Internattonal Conference on Parallel Processing. Vol. I, Architecture, 41-50.
	50	MOUNES-ToussI, F. 1993 An adaptive cache coherence enforcement strategy with compiler assistance. M S. Thesis, Dept. of Electrical Engineering, Univ of Minnesota, Minneapolis.
	51	Nt:UYEN, T. N., LL Z., AND Lm,IA, D.J. 1993. Efficxent use of dynamically tagged directories through compiler analysis. In the Internatwnal Conference on Parallel Processing.
	52	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
	53	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
	54	PERRON, R., AND MUNDIE, C. 1986. The architecture of the Alliant FX/8 Computer In IEEE COMPCON. IEEE, New York, 390 393.
	55	PFISTER, G. F., BRANTLEY, W. C., GEORGE, D. A., HARVEY, S. L, KLEINFELDER, W. J., McAULIFFE, K. P., MELTON, E. A., NORTON, V. A., AND WEISS, J. 1985. The IBM research parallel processor prototype (RP3): Introduction and Architecture. In the International Conference on Parallel Processing, 764 771.
	56	POLYCHRONOPOULOS, C. D. 1988. Toward autoscheduling compfiers. J. Supercomput., 2, 297 330.
	57	S. Prybylski , M. Horowitz , J. Hennessy, Performance tradeoffs in cache design, Proceedings of the 15th Annual International Symposium on Computer architecture, p.290-298, May 30-June 02, 1988, Honolulu, Hawaii, United States
	58	A. J. Smith, Line (block) size choice for CPU cache memories, IEEE Transactions on Computers, v.36 n.9, p.1063-1076, Sept. 1987 [doi>10.1109/TC.1987.5009537]
	59	Alan Jay Smith, Cache Memories, ACM Computing Surveys (CSUR), v.14 n.3, p.473-530, Sept. 1982 [doi>10.1145/356887.356892]
	60	Craig B. Stunkel , Bob Janssens , W. Kent Fuchs, Address Tracing for Parallel Machines, Computer, v.24 n.1, p.31-38, January 1991 [doi>10.1109/2.67191]
	61	TANIL C. K. 1976. Cache design In the tightly coupled multiprocessor system. In the AFIPS Conference Proceedings. National Computer Con{erence. AFIPS, Arlington, Va., 749-753.
	62	Charles P. Thacker , Lawrence C. Stewart , Edwin H. Satterthwaite, Jr., Firefly: A Multiprocessor Workstation, IEEE Transactions on Computers, v.37 n.8, p.909-920, August 1988 [doi>10.1109/12.2243]
	63	TORRELLAS, J., AND HENNESSY, J 1990 Estimating the perfbrmance advantages of relaxing consistency in a shared-memory multiproeessor. In the Internatzonal Confi, rence on Parallel Processing. Vol. I, Architecture, 26-33.
	64	VEII)ENBAUM, A. V. 1986 A compiler-assisted cache coherence solution for multlprocessors. In the Internatzonal Conference on Parallel Processzng, 1029 1036.
	65	W. Weber , A. Gupta, Analysis of cache invalidation patterns in multiprocessors, Proceedings of the third international conference on Architectural support for programming languages and operating systems, p.243-256, April 03-06, 1989, Boston, Massachusetts, United States
	66	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]
	67	YEN, W. C., YEN, D. W. L, AND FU, K.-S. 1985. Data coherence problem m a multlcache system. IEEE Trans Comput. C-34, 1 (Jan), 56-65.
	68	Richard N. Zucker , Jean-Loup Baer, A performance study of memory consistency models, Proceedings of the 19th annual international symposium on Computer architecture, p.2-12, May 19-21, 1992, Queensland, Australia

CITED BY 22

	Craig Williams , Paul F. Reynolds , Bronis R. de Supinski, Delta Coherence Protocols, IEEE Concurrency, v.8 n.3, p.23-29, July 2000
	Lynn Choi , Pen-Chung Yew, Compiler and hardware support for cache coherence in large-scale multiprocessors: design considerations and performance study, ACM SIGARCH Computer Architecture News, v.24 n.2, p.283-294, May 1996
	Akhilesh Kumar , Phanindra K. Mannava , Laxmi N. Bhuyan, Efficient and scalable cache coherence schemes for shared memory hypercube multiprocessors, Proceedings of the 1994 conference on Supercomputing, p.498-507, December 1994, Washington, D.C., United States
	Michał Cierniak , Wei Li, Unifying data and control transformations for distributed shared-memory machines, ACM SIGPLAN Notices, v.30 n.6, p.205-217, June 1995
	Tao Li , Lizy Kurian John, ADir_pNB: A Cost-Effective Way to Implement Full Map Directory-Based Cache Coherence Protocols, IEEE Transactions on Computers, v.50 n.9, p.921-934, September 2001
	Lory D. Molesky , Krithi Ramamritham, Recovery protocols for shared memory database systems, ACM SIGMOD Record, v.24 n.2, p.11-22, May 1995
	Michael J. Franklin , Michael J. Carey , Miron Livny, Transactional client-server cache consistency: alternatives and performance, ACM Transactions on Database Systems (TODS), v.22 n.3, p.315-363, Sept. 1997
	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
	Steven P. Vanderwiel , David J. Lilja, Data prefetch mechanisms, ACM Computing Surveys (CSUR), v.32 n.2, p.174-199, June 2000
	Akhilesh Kumar , Phanindra K. Mannava , Laxmi N. Bhuyan, Efficient and scalable cache coherence schemes for shared memory hypercube multiprocessors, Proceedings of the 1994 ACM/IEEE conference on Supercomputing, November 14-18, 1994, Washington, D.C.
	Steven M. German, Formal Design of Cache Memory Protocols in IBM, Formal Methods in System Design, v.22 n.2, p.133-141, March 2003
	Yong Woo Lee, A virtual server queueing network method for component based performance modelling of metacomputing, Future Generation Computer Systems, v.20 n.1, p.145-155, January 2004
	Fayé Briggs , Suresh Chittor , Kai Cheng, Micro-architecture techniques in the intel® E8870 scalable memory controller, Proceedings of the 3rd workshop on Memory performance issues: in conjunction with the 31st international symposium on computer architecture, p.30-36, June 20-20, 2004, Munich, Germany
	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
	Xubin He , Ming Zhang , Qing Yang, STICS: SCSI-to-IP cache for storage area networks, Journal of Parallel and Distributed Computing, v.64 n.9, p.1069-1085, September 2004
	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
	Babak Hamidzadeh , Lau Ying Kit , David J. Lilja, Dynamic Task Scheduling Using Online Optimization, IEEE Transactions on Parallel and Distributed Systems, v.11 n.11, p.1151-1163, November 2000
	L. N. Bhuyan , H. Wang , R. Iyer, Impact of CC-NUMA Memory Management Policies on the Application Performance of Multistage Switching Networks, IEEE Transactions on Parallel and Distributed Systems, v.11 n.3, p.230-246, March 2000
	H. Sarojadevi , S. K. Nandy , S. Balakrishnan, On the correctness of program execution when cache coherence is maintained locally at data-sharing boundaries in distributed shared memory multiprocessors, International Journal of Parallel Programming, v.32 n.5, p.415-446, October 2004
	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
	Shahram Ghandeharizadeh , Shahin Shayandeh, Cooperative caching techniques for continuous media in wireless home networks, Proceedings of the 1st international conference on Ambient media and systems, p.1-8, February 11-14, 2008, Quebec, Canada
	Alan Jay Smith, Cache memory, Encyclopedia of Computer Science, 4th edition, John Wiley and Sons Ltd., Chichester, 2003