Efficient procedure mapping using cache line coloring

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback
Take a look at the new version of this page: [ beta version ]. Tell us what you think.

Efficient procedure mapping using cache line coloring

Full text

Pdf (1.70 MB)

Source

ACM SIGPLAN Notices archive
Volume 32 , Issue 5 (May 1997) table of contents

Pages: 171 - 182

Year of Publication: 1997

ISSN:0362-1340

Also published in ...

Authors

Amir H. Hashemi	Dept. of Electrical and Computer Engineering, Northeastern University, Boston, MA
David R. Kaeli	Dept. of Electrical and Computer Engineering, Northeastern University, Boston, MA
Brad Calder	Dept. of Computer Science and Engineering, University of California, San Diego, La Jolla, CA

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 38, Citation Count: 25

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

ABSTRACT

As the gap between memory and processor performance continues to widen, it becomes increasingly important to exploit cache memory eflectively. Both hardware and aoftware approaches can be explored to optimize cache performance. Hardware designers focus on cache organization issues, including replacement policy, associativity, line size and the resulting cache access time. Software writers use various optimization techniques, including software prefetching, data scheduling and code reordering. Our focus is on improving memory usage through code reordering compiler techniques.In this paper we present a link-time procedure mapping algorithm which can significantly improve the eflectiveness of the instruction cache. Our algorithm produces an improved program layout by performing a color mapping of procedures to cache lines, taking into consideration the procedure size, cache size, cache line size, and call graph. We use cache line coloring to guide the procedure mapping, indicating which cache lines to avoid when placing a procedure in the program layout. Our algorithm reduces on average the instruction cache miss rate by 40% over the original mapping and by 17% over the mapping algorithm of Pettis and Hansen [12].

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	Thomas Ball , James R. Larus, Efficient path profiling, Proceedings of the 29th annual ACM/IEEE international symposium on Microarchitecture, p.46-57, December 02-04, 1996, Paris, France
	2	L. Belady. A study of replacement algorithms for a virtualstorage computer. IBM Systems Journal, 5(2):78-101, 1966.
	3	Brian N. Bershad , Dennis Lee , Theodore H. Romer , J. Bradley Chen, Avoiding conflict misses dynamically in large direct-mapped caches, Proceedings of the sixth international conference on Architectural support for programming languages and operating systems, p.158-170, October 05-07, 1994, San Jose, California, United States
	4	Brad Calder , Dirk Grunwald, Reducing branch costs via branch alignment, Proceedings of the sixth international conference on Architectural support for programming languages and operating systems, p.242-251, October 05-07, 1994, San Jose, California, United States
	5	Brad Calder , Dirk Grunwald , Amitabh Srivastava, The predictability of branches in libraries, Proceedings of the 28th annual international symposium on Microarchitecture, p.24-34, November 29-December 01, 1995, Ann Arbor, Michigan, United States
	6	B. Calder, D. Grunwald, and B. Zorn. Quantifying behavioral differences between C and G++ programs. Journal of Programming Languages, 2(4), 1994.
	7	Peter J. Denning , Stuart C. Schwartz, Properties of the working-set model, Communications of the ACM, v.15 n.3, p.191-198, March 1972 [doi>10.1145/361268.361281]
	8	Joseph A. Fisher , Stefan M. Freudenberger, Predicting conditional branch directions from previous runs of a program, Proceedings of the fifth international conference on Architectural support for programming languages and operating systems, p.85-95, October 12-15, 1992, Boston, Massachusetts, United States
	9	W. W. Hwu , P. P. Chang, Achieving high instruction cache performance with an optimizing compiler, Proceedings of the 16th annual international symposium on Computer architecture, p.242-251, April 1989, Jerusalem, Israel
	10	David R. Kaeli, Issues in Trace-Driven Simulation, Performance Evaluation of Computer and Communication Systems, Joint Tutorial Papers of Performance '93 and Sigmetrics '93, p.224-244, May 10-14, 1993
	11	S. McFarling, Program optimization for instruction caches, Proceedings of the third international conference on Architectural support for programming languages and operating systems, p.183-191, April 03-06, 1989, Boston, Massachusetts, United States
	12	Karl Pettis , Robert C. Hansen, Profile guided code positioning, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, p.16-27, June 1990, White Plains, New York, United States
	13	Steven A. Przybylski, Cache and memory hierarchy design: a performance-directed approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1990
	14	Thomas Roberts Puzak, Analysis of cache replacement-algorithms, 1985
	15	R. W. Quong, Expected I-cache miss rates via the gap model, Proceedings of the 21ST annual international symposium on Computer architecture, p.372-383, April 18-21, 1994, Chicago, Illinois, United States
	16	Alan D Samples , Paul N. Hilfinger, Code Reorginazation for Instruction Caches, University of California at Berkeley, Berkeley, CA, 1988
	17	A. Sampoga. Architectural Implications of C and C-t-4- Programming Models. MS Thesis, Northeastern University, August 1995.
	18	Amitabh Srivastava , Alan Eustace, ATOM: a system for building customized program analysis tools, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.196-205, June 20-24, 1994, Orlando, Florida, United States
	19	James Gordon Thompson , Alan Jay Smith, Efficient analysis of caching systems, 1987
	20	J. Torrellas , Chun Xia , R. Daigle, Optimizing instruction cache performance for operating system intensive workloads, Proceedings of the 1st IEEE Symposium on High-Performance Computer Architecture, p.360, January 22-25, 1995
	21	David W. Wall, Predicting program behavior using real or estimated profiles, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.59-70, June 24-28, 1991, Toronto, Ontario, Canada
	22	Cliff Young , Michael D. Smith, Improving the accuracy of static branch prediction using branch correlation, Proceedings of the sixth international conference on Architectural support for programming languages and operating systems, p.232-241, October 05-07, 1994, San Jose, California, United States

CITED BY 25

	Nikolas Gloy , Trevor Blackwell , Michael D. Smith , Brad Calder, Procedure placement using temporal ordering information, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.303-313, December 01-03, 1997, Research Triangle Park, North Carolina, United States
	Alex Ramirez , Oliverio J. Santana , Josep L. Larriba-Pey , Mateo Valero, Fetching instruction streams, Proceedings of the 35th annual ACM/IEEE international symposium on Microarchitecture, November 18-22, 2002, Istanbul, Turkey
	A. B. Kahng , J. Lach , W. H. Mangione-Smith , S. Mantik , I. L. Markov , M. Potkonjak , P. Tucker , H. Wang , G. Wolfe, Watermarking techniques for intellectual property protection, Proceedings of the 35th annual conference on Design automation, p.776-781, June 15-19, 1998, San Francisco, California, United States
	Brad Calder , Chandra Krintz , Simmi John , Todd Austin, Cache-conscious data placement, ACM SIGPLAN Notices, v.33 n.11, p.139-149, Nov. 1998
	Alex Ramirez , Luiz André Barroso , Kourosh Gharachorloo , Robert Cohn , Josep Larriba-Pey , P. Geoffrey Lowney , Mateo Valero, Code layout optimizations for transaction processing workloads, ACM SIGARCH Computer Architecture News, v.29 n.2, p.155-164, May 2001
	Architectural and compiler support for effective instruction prefetching: a cooperative approach, ACM Transactions on Computer Systems (TOCS), v.19 n.1, p.71-109, Feb. 2001
	Nikolas Gloy , Michael D. Smith, Procedure placement using temporal-ordering information, ACM Transactions on Programming Languages and Systems (TOPLAS), v.21 n.5, p.977-1027, Sept. 1999
	Timothy Sherwood , Brad Calder , Joel Emer, Reducing cache misses using hardware and software page placement, Proceedings of the 13th international conference on Supercomputing, p.155-164, June 20-25, 1999, Rhodes, Greece
	Chandra Krintz , Brad Calder , Han Bok Lee , Benjamin G. Zorn, Overlapping execution with transfer using non-strict execution for mobile programs, ACM SIGOPS Operating Systems Review, v.32 n.5, p.159-169, Dec. 1998
	Murali Annavaram , Jignesh M. Patel , Edward S. Davidson, Call graph prefetching for database applications, ACM Transactions on Computer Systems (TOCS), v.21 n.4, p.412-444, November 2003
	Christophe Guillon , Fabrice Rastello , Thierry Bidault , Florent Bouchez, Procedure placement using temporal-ordering information: dealing with code size expansion, Proceedings of the 2004 international conference on Compilers, architecture, and synthesis for embedded systems, September 22-25, 2004, Washington DC, USA
	Alex Ramirez , Josep L. Larriba-Pey , Mateo Valero, Software Trace Cache, IEEE Transactions on Computers, v.54 n.1, p.22-35, January 2005
	John Kalamatianos , Alireza Khalafi , David R. Kaeli , Waleed Meleis, Analysis of Temporal-Based Program Behavior for Improved Instruction Cache Performance, IEEE Transactions on Computers, v.48 n.2, p.168-175, February 1999
	Jingren Zhou , Kenneth A. Ross, Buffering databse operations for enhanced instruction cache performance, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France
	S. Bartolini , C. A. Prete, Optimizing instruction cache performance of embedded systems, ACM Transactions on Embedded Computing Systems (TECS), v.4 n.4, p.934-965, November 2005
	Tohru Ishihara , Farzan Fallah, A non-uniform cache architecture for low power system design, Proceedings of the 2005 international symposium on Low power electronics and design, August 08-10, 2005, San Diego, CA, USA
	Rakesh Kumar , Dean M. Tullsen, Compiling for instruction cache performance on a multithreaded architecture, Proceedings of the 35th annual ACM/IEEE international symposium on Microarchitecture, November 18-22, 2002, Istanbul, Turkey
	Stephen S. Brown , Jeet Asher , William H. Mangione-Smith, Offline program re-mapping to improve branch prediction efficiency in embedded systems, Proceedings of the 2000 conference on Asia South Pacific design automation, p.111-116, January 2000, Yokohama, Japan
	Alex Ramírez , Josep-L. Larriba-Pey , Carlos Navarro , Josep Torrellas , Mateo Valero, Software trace cache, Proceedings of the 13th international conference on Supercomputing, p.119-126, June 20-25, 1999, Rhodes, Greece
	Xianglong Huang , Stephen M. Blackburn , David Grove , Kathryn S. McKinley, Fast and efficient partial code reordering: taking advantage of dynamic recompilatior, Proceedings of the 2006 international symposium on Memory management, June 10-11, 2006, Ottawa, Ontario, Canada
	Ke Ning , David Kaeli, External memory page remapping for embedded multimedia systems, ACM SIGPLAN Notices, v.42 n.7, July 2007
	Yu Chen , Fuxin Zhang, Code reordering on limited branch offset, ACM Transactions on Architecture and Code Optimization (TACO), v.4 n.2, p.10-es, June 2007
	Christophe Guillon , Fabrice Rastello , Thierry Bidault , Florent Bouchez, Procedure placement using temporal-ordering information: Dealing with code size expansion, Journal of Embedded Computing, v.1 n.4, p.437-459, December 2005
	T. Ishihara , F. Fallah, A cache-defect-aware code placement algorithm for improving the performance of processors, Proceedings of the 2005 IEEE/ACM International conference on Computer-aided design, p.995-1001, November 06-10, 2005, San Jose, CA
	Alex Ramirez , Josep Ll. Larriba-Pey , Carlos Navarro , Mateo Valero , Josep Torrellas, Software Trace Cache for Commercial Applications, International Journal of Parallel Programming, v.30 n.5, p.373-395, October 2002