Intermediately executed code is the key to find refactorings that improve temporal data locality

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Intermediately executed code is the key to find refactorings that improve temporal data locality

Full text

Pdf (1.41 MB)

Source

Conference On Computing Frontiers archive
Proceedings of the 3rd conference on Computing frontiers table of contents

Ischia, Italy

SESSION: Special session on cache optimization table of contents

Pages: 373 - 382

Year of Publication: 2006

ISBN:1-59593-302-6

Authors

Kristof Beyls	Ghent University, Gent, Belgium
Erik H. D'Hollander	Ghent University, Gent, Belgium

Sponsor

ACM: Association for Computing Machinery

Publisher

ACM New York, NY, USA

Bibliometrics

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

Additional Information:

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

ABSTRACT

The growing speed gap between memory and processor makes an efficient use of the cache ever more important to reach high performance. One of the most important ways to improve cache behavior is to increase the data locality. While many cache analysis tools have been developed, most of them only indicate the locations in the code where cache misses occur. Often, optimizing the program, even after pinpointing the cache bottlenecks in the source code, remains hard with these tools.In this paper, we present two related tools that not only pinpoint the locations of cache misses, but also suggest source code refactorings which improve temporal locality and thereby eliminate the majority of the cache misses. In both tools, the key to find the appropriate refactorings is an analysis of the code executed between a data use and the next use of the same data, which we call the Intermediately Executed Code (IEC). The first tool, the Reuse Distance VISualizer (RDVIS), performs a clustering on the IECs, which reduces the amount of work to find required refactorings. The second tool, SLO (short for "Suggestions for Locality Optimizations"), suggests a number of refactorings by analyzing the call graph and loop structure of the IEC. Using these tools, we have pinpointed the most important optimizations for a number of SPEC2000 programs, resulting in an average speedup of 2.3 on a number of different platforms.

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	Mark Atkins , Ramesh Subramaniam, PC Software Performance Tuning, Computer, v.29 n.8, p.47-54, August 1996 [doi>10.1109/2.532045 ]
	3	C. Bastoul and P. Feautrier. Improving data locality by chunking. In Compiler Construction, LNCS 2622, pages 320--335, 2003.
	4	Erik Berg , Erik Hagersten, SIP: Performance Tuning through Source Code Interdependence, Proceedings of the 8th International Euro-Par Conference on Parallel Processing, p.177-186, August 27-30, 2002
	5	Erik Berg , Erik Hagersten, Fast data-locality profiling of native execution, Proceedings of the 2005 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 06-10, 2005, Banff, Alberta, Canada
	6	Kristof Beyls , Erik H. D'Hollander, Generating cache hints for improved program efficiency, Journal of Systems Architecture: the EUROMICRO Journal, v.51 n.4, p.223-250, April 2005 [doi>10.1016/j.sysarc.2004.09.004]
	7	K. Beyls, E. H. D'Hollander, and F. Vandeputte. RDVIS: A tool that visualizes the causes of low locality and hints program optimizations. In ICCS, volume 3515 of LNCS, pages 166--173, 2005.
	8	Robert Bosch , Chris Stolte , Diane Tang , John Gerth , Mendel Rosenblum , Pat Hanrahan, Rivet: a flexible environment for computer systems visualization, ACM SIGGRAPH Computer Graphics, v.34 n.1, February 2000 [doi>10.1145/604446.604455]
	9	Trishul M. Chilimbi , Bob Davidson , James R. Larus, Cache-conscious structure definition, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.13-24, May 01-04, 1999, Atlanta, Georgia, United States
	10	Albert Cohen , Marc Sigler , Sylvain Girbal , Olivier Temam , David Parello , Nicolas Vasilache, Facilitating the search for compositions of program transformations, Proceedings of the 19th annual international conference on Supercomputing, June 20-22, 2005, Cambridge, Massachusetts [doi>10.1145/1088149.1088169]
	11	Chen Ding , Ken Kennedy, Improving effective bandwidth through compiler enhancement of global cache reuse, Journal of Parallel and Distributed Computing, v.64 n.1, p.108-134, January 2004 [doi>10.1016/j.jpdc.2003.09.005]
	12	Changpeng Fang , Steve Carr , Soner Onder , Zhenlin Wang, Instruction Based Memory Distance Analysis and its Application, Proceedings of the 14th International Conference on Parallel Architectures and Compilation Techniques, p.27-37, September 17-21, 2005 [doi>10.1109/PACT.2005.26]
	13	A. J. Goldberg , J. L. Hennessy, Mtool: An Integrated System for Performance Debugging Shared Memory Multiprocessor Applications, IEEE Transactions on Parallel and Distributed Systems, v.4 n.1, p.28-40, January 1993 [doi>10.1109/71.205651 ]
	14	H. Han, G. Rivera, and C.-W. Tseng. Software support for improving locality in scientific codes. In CPC, January 2000.
	15	Hwansoo Han , Chau-Wen Tseng, Improving Locality for Adaptive Irregular Scientific Codes, Proceedings of the 13th International Workshop on Languages and Compilers for Parallel Computing-Revised Papers, p.173-188, August 10-12, 2000
	16	I. Kadayif , M. Kandemir, Data space-oriented tiling for enhancing locality, ACM Transactions on Embedded Computing Systems (TECS), v.4 n.2, p.388-414, May 2005 [doi>10.1145/1067915.1067922]
	17	M. Kandemir , P. Banerjee , A. Choudhary , J. Ramanujam , E. Ayguadé, An integer linear programming approach for optimizing cache locality, Proceedings of the 13th international conference on Supercomputing, p.500-509, June 20-25, 1999, Rhodes, Greece [doi>10.1145/305138.305247]
	18	Induprakas Kodukula , Keshav Pingali, Data-Centric Transformations for Locality Enhancement, International Journal of Parallel Programming, v.29 n.3, p.319-364, June 2001 [doi>10.1023/A:1011172104768 ]
	19	Chris Lattner , Vikram Adve, Automatic pool allocation: improving performance by controlling data structure layout in the heap, Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation, June 12-15, 2005, Chicago, IL, USA
	20	Alvin R. Lebeck , David A. Wood, Cache Profiling and the SPEC Benchmarks: A Case Study, Computer, v.27 n.10, p.15-26, October 1994 [doi>10.1109/2.318580 ]
	21	Margaret Martonosi , Anoop Gupta , Thomas E. Anderson, Tuning Memory Performance of Sequential and Parallel Programs, Computer, v.28 n.4, p.32-40, April 1995 [doi>10.1109/2.375175 ]
	22	Kathryn S. McKinley , Steve Carr , Chau-Wen Tseng, Improving data locality with loop transformations, ACM Transactions on Programming Languages and Systems (TOPLAS), v.18 n.4, p.424-453, July 1996 [doi>10.1145/233561.233564]
	23	John Mellor-Crummey , Robert J. Fowler , Gabriel Marin , Nathan Tallent, HPCVIEW: A Tool for Top-down Analysis of Node Performance, The Journal of Supercomputing, v.23 n.1, p.81-104, August 2002 [doi>10.1023/A:1015789220266 ]
	24	John Mellor-Crummey , David Whalley , Ken Kennedy, Improving Memory Hierarchy Performance for Irregular Applications Using Data and Computation Reorderings, International Journal of Parallel Programming, v.29 n.3, p.217-247, June 2001 [doi>10.1023/A:1011119519789 ]
	25	B. Quaing, J. Tao, and W. Karl. Yaco: A user conducted visualization tool for supporting cache optimization. In Proceedings of HPCC 2005, volume 3726 of Lecture Notes in Computer Science, pages 694--703, 2005.
	26	Yonghong Song , Zhiyuan Li, New tiling techniques to improve cache temporal locality, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.215-228, May 01-04, 1999, Atlanta, Georgia, United States
	27	Michelle Mills Strout , Larry Carter , Jeanne Ferrante , Barbara Kreaseck, Sparse Tiling for Stationary Iterative Methods, International Journal of High Performance Computing Applications, v.18 n.1, p.95-113, February 2004 [doi>10.1177/1094342004041294]
	28	Eric van der Deijl , Gerco Kanbier , Olivier Temam , Elena D. Granston, A Cache Visualization Tool, Computer, v.30 n.7, p.71-78, July 1997 [doi>10.1109/2.596631 ]
	29	J. Weidendorfer, M. Kowarschik, and C. Trinitis. A tool suite for simulation based analysis of memory access behavior. In ICCS, volume 3038 of LNCS, pages 440--447, 2004.
	30	Michael E. Wolf , Monica S. Lam, A data locality optimizing algorithm, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.30-44, June 24-28, 1991, Toronto, Ontario, Canada
	31	David Wonnacott, Achieving Scalable Locality with Time Skewing, International Journal of Parallel Programming, v.30 n.3, p.181-221, June 2002 [doi>10.1023/A:1015460304860 ]
	32	Visualizing the Impact of the Cache on Program Execution, Proceedings of the Fifth International Conference on Information Visualisation, p.336, July 25-27, 2001
	33	Yutao Zhong , Maksim Orlovich , Xipeng Shen , Chen Ding, Array regrouping and structure splitting using whole-program reference affinity, Proceedings of the ACM SIGPLAN 2004 conference on Programming language design and implementation, June 09-11, 2004, Washington DC, USA