A version control approach to Cache coherence

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A version control approach to Cache coherence

Full text

Pdf (1.03 MB)

Source

International Conference on Supercomputing archive
Proceedings of the 3rd international conference on Supercomputing table of contents

Crete, Greece

Pages: 322 - 330

Year of Publication: 1989

ISBN:0-89791-309-4

Authors

Hoichi Cheong	Center for Supercomputing Research and Development, University of Illinois at Urbana-Champaign, 104 South Wright Street, Urbana, Illinois
Alex Veidenbaum	Center for Supercomputing Research and Development, University of Illinois at Urbana-Champaign, 104 South Wright Street, Urbana, Illinois

Sponsors

Computer Tech Inst. : Computer Technology Institute
SIGARCH: ACM Special Interest Group on Computer Architecture
SIAM : Society for Industrial and Applied Mathematics
AICA : Assoc Italianai de Calcolo Automatico

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 20, Citation Count: 17

Additional Information:

abstract 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/318789.318824 What is a DOI?

ABSTRACT

A version control approach to maintain cache coherence is proposed for large-scale shared-memory multiprocessor systems with interconnection networks. The new approach, unlike existing approaches for such class of systems, makes it possible to exploit temporal locality across synchronization boundaries. As with the other software-directed approaches, each processor independently manages its cache, i.e., there is no interprocessor communication involved in maintaining cache coherence. The hardware required per processor in the version control approach stays constant as the number of processors increases; hence, it scales up to larger systems. Furthermore, the new approach incurs low overhead. The simulated results of several schemes for large-scale systems show that the new approach achieves a data cache hit ratio closest to maximum possible.

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	Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
	2	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
	3	Utpal Banerjee. Data dependence in ordinary programs. Technical Report Rpt. No. 76-837, Univ. of Illinois at Urbana-Champaign, Dept. of Computer Sci., Nov., 1976. M.S. thesis.
	4	W. C. Brantley, K. P. McAuliffe, and A. J. Weiss. Rp3 processor-memory element. Proc. of the 1985 Int'l. Conf. on Parallel Processing, pages 782-789, August, 1985.
	5	L.M. Censier and P. Feautrier. A new solution to coherence problems in multicache systems. IEEE Trans. Computers, C-27(12):1112-1118, December, 1978.
	6	Hoichi Cheong. Towards efficient software-based cache coherence strategies. Technical report, University of Illinois at Urbana-Champaign, 1989. Ph.D. Thesis in progress.
	7	Hoiehi Cheong and Alex Veidenbaum. A version control approach to cache coherence in hierarchical cache multiprocessot systems. Technical Report CSRD No. 848, University of Illinois at Urbana-Champaign, Jan 1989.
	8	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
	9	Hoichi Cheong and Alexander V. Veidenbaum. Stale data detection and coherence enforcement using flow analysis. Proceedings of the j988 international Conference on Parallel Processing, I, Architecture: 138-145, August 1988.
	10	Ron Cytron, Steve Karlovsky, and Kevin P. McAuliffe. Automatic management of programmable caches. Proceedings of the 1988 International Conference on Parallel Processing, II, Software:229-238, August 1988.
	11	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
	12	Daniel Gajski, David Kuck, Duncan Lawrie, and Ahmed Sarneh. Cedar - a large scale multiprocessors. Proc. of the 1983 International Conf. on Parallel Processing, Aug. 1983.
	13	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
	14	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
	15	David J. Kuck, Robert H. Kuhn, Bruce Leasure, and Michael Wolfe. The structure of an advanced vectorizer for pipelined processors. Computer Software and Applications Conference (COMPSACSO), pages 709-715, October 1980.
	16	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]
	17	Roland L. Lee. The effectiveness of caches and data prefetch bufffers in large-scale shared memory multiprocessors. Technical Report CSRD No. 670, CSRD, University of Illinois at Urbana-Champaign, August 1987.
	18	K P McAuliffe, Analysis of cache memories in highly parallel systems, New York University, New York, NY, 1986
	19	E. McCreight. The dragon computer system: An early overview. Technical report, Xerox Corp, September 1984.
	20	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
	21	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
	22	Alan Jay Smith. Cpu cache consistency with software support and using "one time identifiers". Proc. Pacific Computer Communications Symp., pages 153-161, Oct. 22- 24, 2985.
	23	C. K. Tang. Cache system design in the tightly coupled multiprocessor system. Proc. NCC, 45:749-753, 1976.
	24	Alexander Veidenbaum. A compiler-assisted cache coherence solution for multiprocesso~s. Proc. of the 1986 lnt'l. Conf. on Parallel Processing, pages 1029-1036, Aug., 1986.

CITED BY 17

	Lynn Choi , Pen-Chung Yew, A compiler-directed cache coherence scheme with improved intertask locality, Proceedings of the 1994 conference on Supercomputing, p.773-782, December 1994, Washington, D.C., 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
	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
	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
	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
	Y.-C. Chen , A. V. Veidenbaum, An effective write policy for software coherence schemes, Proceedings of the 1992 ACM/IEEE conference on Supercomputing, p.661-672, November 16-20, 1992, Minneapolis, Minnesota, 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
	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
	Lynn Choi , Pen Chung Yew, A compiler-directed cache coherence scheme with improved intertask locality, Proceedings of the 1994 ACM/IEEE conference on Supercomputing, November 14-18, 1994, Washington, D.C.
	S. L. Min , J. L. Baer, Design and Analysis of a Scalable Cache Coherence Scheme Based on Clocks and Timestamps, IEEE Transactions on Parallel and Distributed Systems, v.3 n.1, p.25-44, January 1992
	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 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
	Igor Tartalja , Veljko ${\bf Milutinovi \acute c}$, Classifying Software-Based Cache Coherence Solutions, IEEE Software, v.14 n.3, p.90-101, May 1997
	Milo Tomasevic , Veljko Milutinovic, Hardware Approaches to Cache Coherence in Shared-Memory Multiprocessors Part 2, IEEE Micro, v.14 n.6, p.61-66, December 1994
	Shin-ichiro Mori , Masahiro Goshima , Hiroshi Nakashima , Shinji Tomita, A proposal of self-cleanup cache, Proceedings of the IFIP WG10.3 working conference on Parallel architectures and compilation techniques, p.298-301, June 27-29, 1995, Limassol, Cyprus
	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
	Hoichi Cheong , Alexander V. Viedenbaum, Compiler-Directed Cache Management in Multiprocessors, Computer, v.23 n.6, p.39-47, June 1990