An evaluation of a compiler optimization for improving the performance of a coherence directory

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

An evaluation of a compiler optimization for improving the performance of a coherence directory

Full text

Pdf (1.01 MB)

Source

International Conference on Supercomputing archive
Proceedings of the 8th international conference on Supercomputing table of contents

Manchester, England

Pages: 75 - 84

Year of Publication: 1994

ISBN:0-89791-665-4

Authors

Farnaz Mounes-Toussi	Department of Electrical Engineering, 200 Union Street S. E., University of Minnesota, Minneapolis, MN
David J. Lilja	Department of Electrical Engineering, 200 Union Street S. E., University of Minnesota, Minneapolis, MN
Zhiyuan Li	Department of Computer science, 200 Union Street S. E., University of Minnesota, Minneapolis, MN

Sponsor

SIGARCH: ACM Special Interest Group on Computer Architecture

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 12, Citation Count: 0

Additional Information:

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

ABSTRACT

Both hardware-controlled and compiler-directed mechanisms have been proposed for maintaining cache coherence in large-scale shared-memory multiprocessors, but both of these approaches have significant limitations. We examine the potential performance improvement of a new software-hardware controlled cache coherence mechanism. This approach augments the run-time information available to a directory-based coherence mechanism with compile-time analysis that statically identifies write references that cannot cause coherence problems and writes that should be written through to memory. These references are marked as not needing to send invalidation messages to thereby reduce the network traffic produced by the directory while maintaining cache consistency. For those memory references that are ambiguous, due to conditional branches, or due to the need for complex data flow analysis, for instance, the compiler conservatively marks the references and relies on the hardware directory to ensure coherence. Trace-driven simulations are used to emulate the compile-time analysis on memory traces and to estimate potential performance improvement that could be expected from a compiler performing this optimization on the Perfect Club benchmark programs. By reducing the number of invalidations, this optimized directory scheme is capable of reducing the processor-memory network traffic by up to 54 percent compared to an unoptimized directory mechanism. In addition, the overall miss ratio can be reduced up to 42 percent due to a corresponding reduction in the number of write misses.

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	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
	2	M. Berry, D. Chen, P. Koss, D. Kuck, and S. Lo. The Perfect Club benchmarks: Effective performance evaluation of supercomputers. CSRD report 827, University of Illinois, Urbana, IL, May 1989.
	3	L. M. Censier and P. Feautrier. A new solution to coherence problems in multicache coherency schemes. IEEE Transactzons on Computers, C-27(12):1112-1118, December 1978.
	4	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
	5	Y. Chen and M. Dubois. Cache protocol with partial block invalidation. 7th International Parallel Processing Symposium, pages 16-23, 1993.
	6	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 [doi>10.1145/125826.126200]
	7	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]
	8	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]
	9	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
	10	D. R. Cheriton, It. A. Goosen, and P. Machanick. Restructuring a parallel simulation to improve cache behaviour in a shared-memory multiprocessor: A first experience. Internatsonal Symposium on Shared Memory Multiprocessors, 1989.
	11	M. Dubois , C. Scheurich , F. Briggs, Memory access buffering in multiprocessors, Proceedings of the 13th annual international symposium on Computer architecture, p.434-442, June 02-05, 1986, Tokyo, Japan
	12	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
	13	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
	14	T. Gross , P. Steenkiste, Structured dataflow analysis for arrays and its use in an optimizing complier, Software—Practice & Experience, v.20 n.2, p.133-155, February 1990 [doi>10.1002/spe.4380200203]
	15	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
	16	A. Gupta, W. Weber, and T. Mowry. Reducing memory and traffic requirements for scalable directory-based cache coherence schemes. International Conference on Parallel Processing, pages 312-321, 1990.
	17	Zhiyuan Li, Array privatization for parallel execution of loops, Proceedings of the 6th international conference on Supercomputing, p.313-322, July 19-24, 1992, Washington, D. C., United States [doi>10.1145/143369.143426]
	18	Zhiyuan Li, Software Assistance for Directory-Based Caches, Proceedings of the 8th International Symposium on Parallel Processing, p.151-157, April 01, 1994
	19	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 [doi>10.1145/158439.158907]
	20	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]
	21	S. L. Min and J. Baer. A performance comparison of directory-based and timestamp-based cache coherence schemes. International Conference on Parallel Process- ,ng, pages 305-311, 1990.
	22	S. L. Min and J. L. Baer. A timestamp-based cache coherence scheme. International Conference on Parallel Processing, pages 23-32, 1989.
	23	F. Mounes-Toussi and D. J. Lilja. Performance limits of compiler-directed multiprocessor cache coherence enforcement, in The Interaction of Compilation Technology and Computer Architecture, pages }61-190, 1994. D.J. Lilja and P. Bird (eds.), Kluwer Academic Publishers.
	24	T. N. Nguyen, Z. Li, and D. 3. Lilja. Efficient use of dynamically tagged directories through compiler analysis. international Conference on Para,llel Processing, pages 112-119, 1993.
	25	T. N. Nguyen, F. Toussi, D. J. Lilja, and Z. Li. A compiler-assisted adaptive scheme for coherence caches. Parallel Architectures and Compilation Techniques, 1994.
	26	S. Owicki , A. Agarwal, Evaluating the performance of software cache coherence, Proceedings of the third international conference on Architectural support for programming languages and operating systems, p.230-242, April 03-06, 1989, Boston, Massachusetts, United States
	27	C. D. Polychronopoulos, M. B. Girkar, M. R. Haghighat, L. Lee, B. P. Leung, and D. A. Schouten. Parafrase-2: An environment for parallelizing, partitioning, synchronizing, and scheduling programs on multiprocessors, international Conference on Parallel Process,ng, pages 39-48, August 1989.
	28	Carl M. Rosene , Ken W. Kennedy, Incremental dependence analysis, 1990
	29	P. Stenström, A cache consistency protocol for multiprocessors with multistage networks, Proceedings of the 16th annual international symposium on Computer architecture, p.407-415, April 1989, Jerusalem, Israel
	30	J. Torrellas, M. S. Lam, and J. L. Hennessy. Shared data placement optimizations to reduce multiprocessor cache miss rates. International Conference on Parallel Processing, pages 266-270, 1990.