Improving data locality with loop transformations

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Improving data locality with loop transformations

Full text

Pdf (411 KB)

Source

ACM Transactions on Programming Languages and Systems (TOPLAS) archive
Volume 18 , Issue 4 (July 1996) table of contents

Pages: 424 - 453

Year of Publication: 1996

ISSN:0164-0925

Authors

Kathryn S. McKinley	Computer Science Department, LGRC, University of Massachusetts, Amherst, MA
Steve Carr	Department of Computer Science, Michigan Technological University, Houghton, MI
Chau-Wen Tseng	Department of Computer Science, University of Maryland, College Park, MD

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 25, Downloads (12 Months): 174, Citation Count: 129

Additional Information:

abstract references cited by index terms review 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/233561.233564 What is a DOI?

ABSTRACT

In the past decade, processor speed has become significantly faster than memory speed. Small, fast cache memories are designed to overcome this discrepancy, but they are only effective when programs exhibit data locality. In the this article, we present compiler optimizations to improve data locality based on a simple yet accurate cost model. The model computes both temporal and spatial reuse of cache lines to find desirable loop organizations. The cost model drives the application of compound transformations consisting of loop permutation, loop fusion, loop distribution, and loop reversal. To validate our optimization strategy, we implemented our algorithms and ran experiments on a large collection of scientific programs and kernels. Experiments illustrate that for kernels our model and algorithm can select and achieve the best loop structure for a nest. For over 30 complete applications, we executed the original and transformed versions and simulated cache hit rates. We collected statistics about the inherent characteristics of these programs and our ability to improve their data locality. To our knowledge, these studies are the first of such breadth and depth. We found performance improvements were difficult to achieve bacause benchmark programs typically have high hit rates even for small data caches; however, our optimizations significanty improved several programs.

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	Walid Abdul-Karim Abu-Sufah, Improving the performance of virtual memory computers., 1979
	2	John R. Allen , Ken Kennedy, Automatic loop interchange, Proceedings of the 1984 SIGPLAN symposium on Compiler construction, p.233-246, June 17-22, 1984, Montreal, Canada
	3	Randy Allen , Ken Kennedy, Automatic translation of FORTRAN programs to vector form, ACM Transactions on Programming Languages and Systems (TOPLAS), v.9 n.4, p.491-542, Oct. 1987 [doi>10.1145/29873.29875]
	4	Utpal Banerjee, A theory of loop permutations, Selected papers of the second workshop on Languages and compilers for parallel computing, p.54-74, May 1990, Urbana, Illinois, United States
	5	David Callahan , Steve Carr , Ken Kennedy, Improving register allocation for subscripted variables, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, p.53-65, June 1990, White Plains, New York, United States
	6	David Callahan , John Cocke , Ken Kennedy, Estimating interlock and improving balance for pipelined architectures, Journal of Parallel and Distributed Computing, v.5 n.4, p.334-358, August 1988 [doi>10.1016/0743-7315(88)90002-0]
	7	Steven Mark Carr, Memory-hierarchy management, Rice University, Houston, TX, 1993
	8	Steve Carr , Ken Kennedy, Improving the ratio of memory operations to floating-point operations in loops, ACM Transactions on Programming Languages and Systems (TOPLAS), v.16 n.6, p.1768-1810, Nov. 1994 [doi>10.1145/197320.197366]
	9	Steve Carr , Ken Kennedy, Scalar replacement in the presence of conditional control flow, Software—Practice & Experience, v.24 n.1, p.51-77, Jan. 1994 [doi>10.1002/spe.4380240104]
	10	CARR, S. AND WU, Q. 1995. An analysis of loop permutation on the HP PA-RISC. Tech. Rep. TR95-03, Michigan Technological Univ., Houghton, Mich. Feb.
	11	Stephanie Coleman , Kathryn S. McKinley, Tile size selection using cache organization and data layout, Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation, p.279-290, June 18-21, 1995, La Jolla, California, United States
	12	COOPER, K., HALL, M. W., HOOD, R. T., KENNEDY, K., MCKINLEY, K. S., MELLOR-CRUMMEY, J. M., TORCZON, L., AND WARREN, S. K. 1993. The ParaScope parallel programming environmerit. Proc. IEEE 81, 2 (Feb.), 244-263.
	13	COOPER, K., HALL, M. W., AND KENNEDY, K. 1993. A methodology for procedure cloning. Comput. Lang. 19, 2 (Feb.), 105-117.
	14	Jeanne Ferrante , Vivek Sarkar , W. Thrash, On Estimating and Enhancing Cache Effectiveness, Proceedings of the Fourth International Workshop on Languages and Compilers for Parallel Computing, p.328-343, August 07-09, 1991
	15	Dennis Gannon , William Jalby , Kyle Gallivan, Strategies for cache and local memory management by global program transformation, Journal of Parallel and Distributed Computing, v.5 n.5, p.587-616, October 1988 [doi>10.1016/0743-7315(88)90014-7]
	16	Gina Goff , Ken Kennedy , Chau-Wen Tseng, Practical dependence testing, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.15-29, June 24-28, 1991, Toronto, Ontario, Canada
	17	Mary W. Hall , Ken Kennedy , Kathryn S. McKinley, Interprocedural transformations for parallel code generation, Proceedings of the 1991 ACM/IEEE conference on Supercomputing, p.424-434, November 18-22, 1991, Albuquerque, New Mexico, United States [doi>10.1145/125826.126055]
	18	F. Irigoin , R. Triolet, Supernode partitioning, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.319-329, January 10-13, 1988, San Diego, California, United States [doi>10.1145/73560.73588]
	19	Ken Kennedy , Kathryn S. McKinley, Optimizing for parallelism and data locality, Proceedings of the 6th international conference on Supercomputing, p.323-334, July 19-24, 1992, Washington, D. C., United States [doi>10.1145/143369.143427]
	20	Ken Kennedy , Kathryn S. McKinley, Maximizing Loop Parallelism and Improving Data Locality via Loop Fusion and Distribution, Proceedings of the 6th International Workshop on Languages and Compilers for Parallel Computing, p.301-320, August 12-14, 1993
	21	KENNEDY, K., MCKINLEY, K. S., AND TSENG, C.-W. 1993. Analysis and transformation in an interactive parallel programming tool. Concurrency Pract. Exper. 5, 7 (Oct.), 575-602.
	22	D. J. Kuck , R. H. Kuhn , D. A. Padua , B. Leasure , M. Wolfe, Dependence graphs and compiler optimizations, Proceedings of the 8th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.207-218, January 26-28, 1981, Williamsburg, Virginia [doi>10.1145/567532.567555]
	23	Monica D. Lam , Edward E. Rothberg , Michael E. Wolf, The cache performance and optimizations of blocked algorithms, Proceedings of the fourth international conference on Architectural support for programming languages and operating systems, p.63-74, April 08-11, 1991, Santa Clara, California, United States
	24	Wei Li , Keshav Pingali, Access normalization: loop restructuring for NUMA compilers, Proceedings of the fifth international conference on Architectural support for programming languages and operating systems, p.285-295, October 12-15, 1992, Boston, Massachusetts, United States
	25	Kathryn Stuart McKinley, Automatic and interactive parallelization, Rice University, Houston, TX, 1992
	26	Joe Warren, A hierarchical basis for reordering transformations, Proceedings of the 11th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.272-282, January 15-18, 1984, Salt Lake City, Utah, United States [doi>10.1145/800017.800539]
	27	Michael Edward Wolf, Improving locality and parallelism in nested loops, Stanford University, Stanford, CA, 1992
	28	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
	29	WOLFE, M. J. 1986. Advanced loop interchanging. In Proceedings of the 1986 International Conference on Parallel Processing. CRC Press, Boca Raton, Fla.
	30	Michael Wolfe, Iteration Space Tiling for Memory Hierarchies, Proceedings of the Third SIAM Conference on Parallel Processing for Scientific Computing, p.357-361, December 01-04, 1987
	31	WOLFE, M. J. 1991. The Tiny loop restructuring research tool. In Proceedings of the 1991 International Conference on Parallel Processing. CRC Press, Boca Raton, Fla.

CITED BY 130

	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
	Induprakas Kodukula , Keshav Pingali, Data-Centric Transformations for Locality Enhancement, International Journal of Parallel Programming, v.29 n.3, p.319-364, June 2001
	Steve Carr , Yiping Guan, Unroll-and-jam using uniformly generated sets, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.349-357, December 01-03, 1997, Research Triangle Park, North Carolina, United States
	M. Kandemir , A. Choudhary , J. Ramanujam , M. Kandaswamy, A unified compiler algorithm for optimizing locality, parallelism and communication in out-of-core computations, Proceedings of the fifth workshop on I/O in parallel and distributed systems, p.79-92, November 17-17, 1997, San Jose, California, United States
	Mahmut Taylan Kandemir, A compiler technique for improving whole-program locality, ACM SIGPLAN Notices, v.36 n.3, p.179-192, March 2001
	Gabriel Rivera , Chau-Wen Tseng, Locality optimizations for multi-level caches, Proceedings of the 1999 ACM/IEEE conference on Supercomputing (CDROM), p.2-es, November 14-19, 1999, Portland, Oregon, United States
	Gerald Roth , John Mellor-Crummey , Ken Kennedy , R. Gregg Brickner, Compiling stencils in high performance Fortran, Proceedings of the 1997 ACM/IEEE conference on Supercomputing (CDROM), p.1-20, November 15-21, 1997, San Jose, CA
	Yonghong Song , Zhiyuan Li, New tiling techniques to improve cache temporal locality, ACM SIGPLAN Notices, v.34 n.5, p.215-228, May 1999
	D. Cociorva , J. W. Wilkins , C. Lam , G. Baumgartner , J. Ramanujam , P. Sadayappan, Loop optimization for a class of memory-constrained computations, Proceedings of the 15th international conference on Supercomputing, p.103-113, June 2001, Sorrento, Italy
	Gabriel Rivera , Chau-Wen Tseng, Eliminating conflict misses for high performance architectures, Proceedings of the 12th international conference on Supercomputing, p.353-360, July 1998, Melbourne, Australia
	Gabriel Rivera , Chau-Wen Tseng, Tiling optimizations for 3D scientific computations, Proceedings of the 2000 ACM/IEEE conference on Supercomputing (CDROM), p.32-es, November 04-10, 2000, Dallas, Texas, United States
	Richard Vuduc , James W. Demmel , Katherine A. Yelick , Shoaib Kamil , Rajesh Nishtala , Benjamin Lee, Performance optimizations and bounds for sparse matrix-vector multiply, Proceedings of the 2002 ACM/IEEE conference on Supercomputing, p.1-35, November 16, 2002, Baltimore, Maryland
	Chen Ding , Ken Kennedy, Improving cache performance in dynamic applications through data and computation reorganization at run time, ACM SIGPLAN Notices, v.34 n.5, p.229-241, May 1999
	M. Kandemir , A. Choudhary , N. Shenoy , P. Banerjee , J. Ramanujam, A hyperplane based approach for optimizing spatial locality in loop nests, Proceedings of the 12th international conference on Supercomputing, p.69-76, July 1998, Melbourne, Australia
	Somnath Ghosh , Margaret Martonosi , Sharad Malik, Automated cache optimizations using CME driven diagnosis, Proceedings of the 14th international conference on Supercomputing, p.316-326, May 08-11, 2000, Santa Fe, New Mexico, United States
	M. Kandemir , J. Ramanujam , A. Choudhary, A compiler algorithm for optimizing locality in loop nests, Proceedings of the 11th international conference on Supercomputing, p.269-276, July 07-11, 1997, Vienna, Austria
	Chit-Te Wang , Nelson Passos, Improving cache hit ratio by extended referencing cache lines, Journal of Computing Sciences in Colleges, v.18 n.4, p.118-123, April 2003
	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
	Somnath Ghosh , Margaret Martonosi , Sharad Malik, Precise miss analysis for program transformations with caches of arbitrary associativity, ACM SIGOPS Operating Systems Review, v.32 n.5, p.228-239, Dec. 1998
	Abdel-Hameed A. Badawy , Aneesh Aggarwal , Donald Yeung , Chau-Wen Tseng, Evaluating the impact of memory system performance on software prefetching and locality optimizations, Proceedings of the 15th international conference on Supercomputing, p.486-500, June 2001, Sorrento, Italy
	Tanja Van Achteren , Francky Catthoor , Rudy Lauwereins , Geert Deconinck, Search space definition and exploration for nonuniform data reuse opportunities in data-dominant applications, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.8 n.1, p.125-139, January 2003
	Kathryn S. McKinley , Olivier Temam, Quantifying loop nest locality using SPEC'95 and the perfect benchmarks, ACM Transactions on Computer Systems (TOCS), v.17 n.4, p.288-336, Nov. 1999
	Mahmut Kandemir , Ismail Kadayif, Compiler-directed selection of dynamic memory layouts, Proceedings of the ninth international symposium on Hardware/software codesign, p.219-224, April 2001, Copenhagen, Denmark
	Mahmut Kandemir, A dynamic locality optimization algorithm for linear algebra codes, Proceedings of the 2001 ACM symposium on Applied computing, p.632-635, March 2001, Las Vegas, Nevada, United States
	Mahmut Kendemir , J. Ramanujam, Data Relation Vectors: A New Abstraction for Data Optimizations, IEEE Transactions on Computers, v.50 n.8, p.798-810, August 2001
	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
	John Mellor-Crummey , David Whalley , Ken Kennedy, Improving memory hierarchy performance for irregular applications, Proceedings of the 13th international conference on Supercomputing, p.425-433, June 20-25, 1999, Rhodes, Greece
	Qing Yi , Vikram Adve , Ken Kennedy, Transforming loops to recursion for multi-level memory hierarchies, ACM SIGPLAN Notices, v.35 n.5, p.169-181, May 2000
	Amir Roth , Andreas Moshovos , Gurindar S. Sohi, Dependence based prefetching for linked data structures, ACM SIGOPS Operating Systems Review, v.32 n.5, p.115-126, Dec. 1998
	Erez Petrank , Dror Rawitz, The hardness of cache conscious data placement, ACM SIGPLAN Notices, v.37 n.1, p.101-112, Jan. 2002
	Somnath Ghosh , Margaret Martonosi , Sharad Malik, Cache miss equations: a compiler framework for analyzing and tuning memory behavior, ACM Transactions on Programming Languages and Systems (TOPLAS), v.21 n.4, p.703-746, July 1999
	P. R. Panda , F. Catthoor , N. D. Dutt , K. Danckaert , E. Brockmeyer , C. Kulkarni , A. Vandercappelle , P. G. Kjeldsberg, Data and memory optimization techniques for embedded systems, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.6 n.2, p.149-206, April 2001
	Gabriel Rivera , Chau-Wen Tseng, Data transformations for eliminating conflict misses, ACM SIGPLAN Notices, v.33 n.5, p.38-49, May 1998
	Antoine Fraboulet , Karen Kodary , Anne Mignotte, Loop fusion for memory space optimization, Proceedings of the 14th international symposium on Systems synthesis, September 30-October 03, 2001, Montréal, P.Q., Canada
	Kamen Yotov , Xiaoming Li , Gang Ren , Michael Cibulskis , Gerald DeJong , Maria Garzaran , David Padua , Keshav Pingali , Paul Stodghill , Peng Wu, A comparison of empirical and model-driven optimization, ACM SIGPLAN Notices, v.38 n.5, May 2003
	Induprakas Kodukula , Nawaaz Ahmed , Keshav Pingali, Data-centric multi-level blocking, ACM SIGPLAN Notices, v.32 n.5, p.346-357, May 1997
	M. F. P. O'Boyle , P. M. W. Knijnenburg, Integrating loop and data transformations for global optimization, Journal of Parallel and Distributed Computing, v.62 n.4, p.563-590, April 2002
	Claudia Leopold, Exploiting non-uniform reuse for cache optimization, Proceedings of the 2001 ACM symposium on Applied computing, p.560-564, March 2001, Las Vegas, Nevada, United States
	Waibhav Tembe , Santosh Pande, Loop Restructuring for Data I/O Minimization on Limited On-Chip Memory Embedded Processors, IEEE Transactions on Computers, v.51 n.10, p.1269-1280, October 2002
	Marta Jiménez , José M. Llabería , Agustín Fernández, Register tiling in nonrectangular iteration spaces, ACM Transactions on Programming Languages and Systems (TOPLAS), v.24 n.4, p.409-453, July 2002
	P. Unnikrishnan , G. Chen , M. Kandemir , D. R. Mudgett, Dynamic compilation for energy adaptation, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.158-163, November 10-14, 2002, San Jose, California
	Min Zhao , Bruce Childers , Mary Lou Soffa, Predicting the impact of optimizations for embedded systems, ACM SIGPLAN Notices, v.38 n.7, July 2003
	Rodric M. Rabbah , Krishna V. Palem, Data remapping for design space optimization of embedded memory systems, ACM Transactions on Embedded Computing Systems (TECS), v.2 n.2, p.186-218, May 2003
	Yijian Wang , David Kaeli, Profile-guided I/O partitioning, Proceedings of the 17th annual international conference on Supercomputing, June 23-26, 2003, San Francisco, CA, USA
	Mahmut Kandemir , Alok Choudhary , Nagaraj Shenoy , Prithviraj Banerjee , J. Ramanujam, A Linear Algebra Framework for Automatic Determination of Optimal Data Layouts, IEEE Transactions on Parallel and Distributed Systems, v.10 n.2, p.115-135, February 1999
	Zhenlin Wang , Doug Burger , Kathryn S. McKinley , Steven K. Reinhardt , Charles C. Weems, Guided region prefetching: a cooperative hardware/software approach, ACM SIGARCH Computer Architecture News, v.31 n.2, May 2003
	Chun-Yuan Lin , Yeh-Ching Chung , Jen-Shiuh Liu, Efficient Data Parallel Algorithms for Multidimensional Array Operations Based on the EKMR Scheme for Distributed Memory Multicomputers, IEEE Transactions on Parallel and Distributed Systems, v.14 n.7, p.625-639, July 2003
	I. Kadayif , M. Kandemir , G. Chen , N. Vijaykrishnan , M. J. Irwin , A. Sivasubramaniam, Compiler-directed high-level energy estimation and optimization, ACM Transactions on Embedded Computing Systems (TECS), v.4 n.4, p.819-850, November 2005
	Meilin Liu , Qingfeng Zhuge , Zili Shao , Edwin H.-M. Sha, General loop fusion technique for nested loops considering timing and code size, Proceedings of the 2004 international conference on Compilers, architecture, and synthesis for embedded systems, September 22-25, 2004, Washington DC, USA
	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
	Victor Delaluz , Mahmut Kandemir , N. Vijaykrishnan , Anand Sivasubramaniam , Mary Jane Irwin, Hardware and Software Techniques for Controlling DRAM Power Modes, IEEE Transactions on Computers, v.50 n.11, p.1154-1173, November 2001
	M. Kandemir , J. Ramanujam , A. Choudhary , P. Banerjee, A Layout-Conscious Iteration Space Transformation Technique, IEEE Transactions on Computers, v.50 n.12, p.1321-1336, December 2001
	Angeles Navarro , Emilio Zapata , David Padua, Compiler Techniques for the Distribution of Data and Computation, IEEE Transactions on Parallel and Distributed Systems, v.14 n.6, p.545-562, June 2003
	Yong Yan , Xiaodong Zhang , Zhao Zhang, Cacheminer: A Runtime Approach to Exploit Cache Locality on SMP, IEEE Transactions on Parallel and Distributed Systems, v.11 n.4, p.357-374, April 2000
	Qing Yi , Ken Kennedy , Vikram Adve, Transforming Complex Loop Nests for Locality, The Journal of Supercomputing, v.27 n.3, p.219-264, March 2004
	Victor De La Luz , Mahmut Kandemir, Array Regrouping and Its Use in Compiling Data-Intensive Embedded Applications, IEEE Transactions on Computers, v.53 n.1, p.1-19, January 2004
	David Callahan , Steve Carr , Ken Kennedy, Improving register allocation for subscripted variables, ACM SIGPLAN Notices, v.39 n.4, April 2004
	Chung-hsing Hsu , Ulrich Kremer, A Quantitative Analysis of Tile Size Selection Algorithms, The Journal of Supercomputing, v.27 n.3, p.279-294, March 2004
	Yutao Zhong , Maksim Orlovich , Xipeng Shen , Chen Ding, Array regrouping and structure splitting using whole-program reference affinity, ACM SIGPLAN Notices, v.39 n.6, May 2004
	Ismail Kadayif , Mahmut Kandemir, Quasidynamic Layout Optimizations for Improving Data Locality, IEEE Transactions on Parallel and Distributed Systems, v.15 n.11, p.996-1011, November 2004
	Paul Marchal , José Ignacio Gómez , Francky Catthoor, Optimizing the memory bandwidth with loop fusion, Proceedings of the 2nd IEEE/ACM/IFIP international conference on Hardware/software codesign and system synthesis, September 08-10, 2004, Stockholm, Sweden
	Kathryn S. McKinley, A Compiler Optimization Algorithm for Shared-Memory Multiprocessors, IEEE Transactions on Parallel and Distributed Systems, v.9 n.8, p.769-787, August 1998
	Mahmut Kandemir , J. Ramanujam , Alok Choudhary, Improving Cache Locality by a Combination of Loop and Data Transformations, IEEE Transactions on Computers, v.48 n.2, p.159-167, February 1999
	J. Hu , M. Kandemir , N. Vijaykrishnan , M. J. Irwin, Analyzing data reuse for cache reconfiguration, ACM Transactions on Embedded Computing Systems (TECS), v.4 n.4, p.851-876, November 2005
	J. S. Hu , M. Kandemir , N. Vijaykrishnan , M. J. Irwin , H. Saputra , W. Zhang, Compiler-directed cache polymorphism, ACM SIGPLAN Notices, v.37 n.7, July 2002
	Mahmut Kandemir , Alok Choudhary , J. Ramanujam , Meenakshi A. Kandaswamy, A Unified Framework for Optimizing Locality, Parallelism, and Communication in Out-of-Core Computations, IEEE Transactions on Parallel and Distributed Systems, v.11 n.7, p.648-668, July 2000
	Changpeng Fang , Steve Carr , Soner Önder , Zhenlin Wang, Reuse-distance-based miss-rate prediction on a per instruction basis, Proceedings of the 2004 workshop on Memory system performance, June 08-08, 2004, Washington, D.C.
	Peizong Lee , Zvi Meir Kedem, Automatic data and computation decomposition on distributed memory parallel computers, ACM Transactions on Programming Languages and Systems (TOPLAS), v.24 n.1, p.1-50, January 2002
	Mahmut Kandemir , Alok Choudhary , J. Ramanujam, An I/O-Conscious Tiling Strategy for Disk-Resident Data Sets, The Journal of Supercomputing, v.21 n.3, p.257-284, March 2002
	Mahmut Taylan Kandemir, Improving whole-program locality using intra-procedural and inter-procedural transformations, Journal of Parallel and Distributed Computing, v.65 n.5, p.564-582, May 2005
	Patrick Carribault , Albert Cohen, Applications of storage mapping optimization to register promotion, Proceedings of the 18th annual international conference on Supercomputing, June 26-July 01, 2004, Malo, France
	Chun-Yuan Lin , Jen-Shiuh Liu , Yeh-Ching Chung, Efficient Representation Scheme for Multidimensional Array Operations, IEEE Transactions on Computers, v.51 n.3, p.327-345, March 2002
	G. Wang , Danesh K. Tafti, Performance Enhancement on Microprocessors with Hierarchical Memory Systems for Solving Large Sparse Linear Systems, International Journal of High Performance Computing Applications, v.13 n.1, p.63-79, February 1999
	Jingling Xue , Xavier Vera, Efficient and Accurate Analytical Modeling of Whole-Program Data Cache Behavior, IEEE Transactions on Computers, v.53 n.5, p.547-566, May 2004
	O. Ozturk , M. Kandemir, Energy management in software-controlled multi-level memory hierarchies, Proceedings of the 15th ACM Great Lakes symposium on VLSI, April 17-19, 2005, Chicago, Illinois, USA
	Mahmut Kandemir , Seung Woo Son , Guangyu Chen, An evaluation of code and data optimizations in the context of disk power reduction, Proceedings of the 2005 international symposium on Low power electronics and design, August 08-10, 2005, San Diego, CA, USA
	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
	Qing Yi , Ken Kennedy, Improving Memory Hierarchy Performance through Combined Loop Interchange and Multi-Level Fusion, International Journal of High Performance Computing Applications, v.18 n.2, p.237-253, May 2004
	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
	Qing Yi , Ken Kennedy , Haihang You , Keith Seymour , Jack Dongarra, Automatic blocking of QR and LU factorizations for locality, Proceedings of the 2004 workshop on Memory system performance, June 08-08, 2004, Washington, D.C.
	Keith D. Cooper , Alexander Grosul , Timothy J. Harvey , Steven Reeves , Devika Subramanian , Linda Torczon , Todd Waterman, ACME: adaptive compilation made efficient, ACM SIGPLAN Notices, v.40 n.7, July 2005
	Mahmut Kandemir , Alok Choudhary , J. Ramanujam , Prith Banerjee, Reducing False Sharing and Improving Spatial Locality in a Unified Compilation Framework, IEEE Transactions on Parallel and Distributed Systems, v.14 n.4, p.337-354, April 2003
	Chengliang Zhang , Chen Ding , Mitsunori Ogihara , Yutao Zhong , Youfeng Wu, A hierarchical model of data locality, ACM SIGPLAN Notices, v.41 n.1, p.16-29, January 2006
	Steve Carr , Soner Önder, A case for a working-set-based memory hierarchy, Proceedings of the 2nd conference on Computing frontiers, May 04-06, 2005, Ischia, Italy
	Richard Vuduc , James W. Demmel , Jeff A. Bilmes, Statistical Models for Empirical Search-Based Performance Tuning, International Journal of High Performance Computing Applications, v.18 n.1, p.65-94, February 2004
	J. C. Pichel , D. B. Heras , J. C. Cabaleiro , F. F. Rivera, Performance optimization of irregular codes based on the combination of reordering and blocking techniques, Parallel Computing, v.31 n.8+9, p.858-876, August 2005
	Srikumar Venugopal , Rajkumar Buyya , Kotagiri Ramamohanarao, A taxonomy of Data Grids for distributed data sharing, management, and processing, ACM Computing Surveys (CSUR), v.38 n.1, p.3-es, 2006
	Erez Petrank , Dror Rawitz, The hardness of cache conscious data placement, Nordic Journal of Computing, v.12 n.3, p.275-307, September 2005
	J. Dongarra , G. Bosilca , Z. Chen , V. Eijkhout , G. E. Fagg , E. Fuentes , J. Langou , P. Luszczek , J. Pjesivac-Grbovic , K. Seymour , H. You , S. S. Vadhiyar, Self-adapting numerical software (SANS) effort, IBM Journal of Research and Development, v.50 n.2/3, p.223-238, March 2006
	Sandhya Krishnan , Sriram Krishnamoorthy , Gerald Baumgartner , Chi-Chung Lam , J. Ramanujam , P. Sadayappan , Venkatesh Choppella, Efficient synthesis of out-of-core algorithms using a nonlinear optimization solver, Journal of Parallel and Distributed Computing, v.66 n.5, p.659-673, May 2006
	Mahmut Kandemir , Prithviraj Banerjee , Alok Choudhary , J. Ramanujam , Eduard Ayguadé, Static and Dynamic Locality Optimizations Using Integer Linear Programming, IEEE Transactions on Parallel and Distributed Systems, v.12 n.9, p.922-941, September 2001
	Xavier Vera , Jaume Abella , Josep Llosa , Antonio González, An accurate cost model for guiding data locality transformations, ACM Transactions on Programming Languages and Systems (TOPLAS), v.27 n.5, p.946-987, September 2005
	Guohua Jin , John Mellor-Crummey , Robert Fowler, Increasing temporal locality with skewing and recursive blocking, Proceedings of the 2001 ACM/IEEE conference on Supercomputing (CDROM), p.43-43, November 10-16, 2001, Denver, Colorado
	Evangelia Athanasaki , Nectarios Koziris, Fast indexing for blocked array layouts to reduce cache misses, International Journal of High Performance Computing and Networking, v.3 n.5/6, p.417-433, March 2005
	David Wonnacott, Achieving Scalable Locality with Time Skewing, International Journal of Parallel Programming, v.30 n.3, p.181-221, June 2002
	Saeed Parsa , Shahriar Lotfi, A New Genetic Algorithm for Loop Tiling, The Journal of Supercomputing, v.37 n.3, p.249-269, September 2006
	Weihua Zhang , Xinglong Qian , Ye Wang , Binyu Zang , Chuanqi Zhu, Optimizing compiler for shared-memory multiple SIMD architecture, ACM SIGPLAN Notices, v.41 n.7, July 2006
	Kristof Beyls , Erik H. D'Hollander, Intermediately executed code is the key to find refactorings that improve temporal data locality, Proceedings of the 3rd conference on Computing frontiers, May 03-05, 2006, Ischia, Italy
	Ozcan Ozturk , Guangyu Chen , Mahmut Kandemir, Multi-compilation: capturing interactions among concurrently-executing applications, Proceedings of the 3rd conference on Computing frontiers, May 03-05, 2006, Ischia, Italy
	Martin Palkovic , Henk Corporaal , Francky Catthoor, Global memory optimisation for embedded systems allowed by code duplication, Proceedings of the 2005 workshop on Software and compilers for embedded systems, p.72-79, September 29-October 01, 2005, Dallas, Texas
	Clemens Grelck , Sven-Bodo Scholz, Merging compositions of array skeletons in SAC, Parallel Computing, v.32 n.7, p.507-522, September 2006
	Apan Qasem , Ken Kennedy, Profitable loop fusion and tiling using model-driven empirical search, Proceedings of the 20th annual international conference on Supercomputing, June 28-July 01, 2006, Cairns, Queensland, Australia
	Ilya Issenin , Erik Brockmeyer , Miguel Miranda , Nikil Dutt, DRDU: A data reuse analysis technique for efficient scratch-pad memory management, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.12 n.2, p.15-es, April 2007
	Min Zhao , Bruce R. Childers , Mary Lou Soffa, An approach toward profit-driven optimization, ACM Transactions on Architecture and Code Optimization (TACO), v.3 n.3, p.231-262, September 2006
	Doosan Cho , Ilya Issenin , Nikil Dutt , Jonghee W. Yoon , Yunheung Paek, Software controlled memory layout reorganization for irregular array access patterns, Proceedings of the 2007 international conference on Compilers, architecture, and synthesis for embedded systems, September 30-October 03, 2007, Salzburg, Austria
	O. Ozturk , G. Chen , M. Kandemir , M. Karakoy, Cache miss clustering for banked memory systems, Proceedings of the 2006 IEEE/ACM international conference on Computer-aided design, November 05-09, 2006, San Jose, California
	Doosan Cho , Sudeep Pasricha , Ilya Issenin , Nikil Dutt , Yunheung Paek , SunJun Ko, Compiler driven data layout optimization for regular/irregular array access patterns, ACM SIGPLAN Notices, v.43 n.7, July 2008
	Ke Ning , David Kaeli, External memory page remapping for embedded multimedia systems, ACM SIGPLAN Notices, v.42 n.7, July 2007
	G. Chen , M. Kandemir , A. Nadgir , U. Sezer, Array Composition and Decomposition for Optimizing Embedded Applications, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.193, November 09-13, 2003
	Min Zhao , Bruce R. Childers , Mary Lou Soffa, A Model-Based Framework: An Approach for Profit-Driven Optimization, Proceedings of the international symposium on Code generation and optimization, p.317-327, March 20-23, 2005
	P. Marchal , J. I. Gomez , L. Pinuel , D. Bruni , L. Benini , F. Catthoor , H. Corporaal, SDRAM-Energy-Aware Memory Allocation for Dynamic Multi-Media Applications on Multi-Processor Platforms, Proceedings of the conference on Design, Automation and Test in Europe, p.10516, March 03-07, 2003
	Tushar Mohan , Bronis R. de Supinski , Sally A. McKee , Frank Mueller , Andy Yoo , Martin Schulz, Identifying and Exploiting Spatial Regularity in Data Memory References, Proceedings of the 2003 ACM/IEEE conference on Supercomputing, p.49, November 15-21, 2003
	Louis-Noel Pouchet , Cedric Bastoul , Albert Cohen , Nicolas Vasilache, Iterative Optimization in the Polyhedral Model: Part I, One-Dimensional Time, Proceedings of the International Symposium on Code Generation and Optimization, p.144-156, March 11-14, 2007
	Ilya Issenin , Erik Brockmeyer , Miguel Miranda , Nikil Dutt, Data Reuse Analysis Technique for Software-Controlled Memory Hierarchies, Proceedings of the conference on Design, automation and test in Europe, p.10202, February 16-20, 2004
	Hwansoo Han , Chau-Wen Tseng, Exploiting Locality for Irregular Scientific Codes, IEEE Transactions on Parallel and Distributed Systems, v.17 n.7, p.606-618, July 2006
	Per Gunnar Kjeldsberg , Francky Catthoor , Sven Verdoolaege , Martin Palkovic , Arnout Vandecappelle , Qubo Hu , Einar J. Aas, Guidance of Loop Ordering for Reduced Memory Usage in Signal Processing Applications, Journal of Signal Processing Systems, v.53 n.3, p.301-321, December 2008
	Mohammed Fellahi , Albert Cohen , Sid Touati, Code-size conscious pipelining of imperfectly nested loops, Proceedings of the 2007 workshop on MEmory performance: DEaling with Applications, systems and architecture, p.49-55, September 16-16, 2007, Brasov, Romania
	Javed Absar , Min Li , Praveen Raghavan , Andy Lambrechts , Murali Jayapala , Arnout Vandecappelle , Francky Catthoor, Locality optimization in wireless applications, Proceedings of the 5th IEEE/ACM international conference on Hardware/software codesign and system synthesis, September 30-October 03, 2007, Salzburg, Austria
	Q. Hu , P. G. Kjeldsberg , A. Vandecappelle , M. Palkovic , F. Catthoor, Incremental hierarchical memory size estimation for steering of loop transformations, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.12 n.4, p.50-es, September 2007
	Van Bui , Boyana Norris , Kevin Huck , Lois Curfman McInnes , Li Li , Oscar Hernandez , Barbara Chapman, A component infrastructure for performance and power modeling of parallel scientific applications, Proceedings of the 2008 compFrame/HPC-GECO workshop on Component based high performance, October 16-17, 2008, Karlsruhe, Germany
	Peng Zhao , Shimin Cui , Yaoqing Gao , Raúl Silvera , José Nelson Amaral, Forma: A framework for safe automatic array reshaping, ACM Transactions on Programming Languages and Systems (TOPLAS), v.30 n.1, p.2-es, November 2007
	Dimitrios S. Nikolopoulos, Dynamic tiling for effective use of shared caches on multithreaded processors, International Journal of High Performance Computing and Networking, v.2 n.1, p.22-35, March 2004
	Nastaran Baradaran , Pedro C. Diniz, A compiler approach to managing storage and memory bandwidth in configurable architectures, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.13 n.4, p.1-26, September 2008
	Xuejun Yang , Jing Du , Xiaobo Yan , Yu Deng, Matrix-based streamization approach for improving locality and parallelism on FT64 stream processor, The Journal of Supercomputing, v.47 n.2, p.171-197, February 2009
	P. Unnikrishnan , G. Chen , M. Kandemir , M. Karakoy , I. Kolcu, Reducing memory requirements of resource-constrained applications, ACM Transactions on Embedded Computing Systems (TECS), v.8 n.3, p.1-37, April 2009
	Lan S. Bai , Lei Yang , Robert P. Dick, MEMMU: Memory expansion for MMU-less embedded systems, ACM Transactions on Embedded Computing Systems (TECS), v.8 n.3, p.1-33, April 2009
	Ioannis E. Venetis , Guang R. Gao, Mapping the LU decomposition on a many-core architecture: challenges and solutions, Proceedings of the 6th ACM conference on Computing frontiers, May 18-20, 2009, Ischia, Italy
	Xiaoming Gu , Ian Christopher , Tongxin Bai , Chengliang Zhang , Chen Ding, A component model of spatial locality, Proceedings of the 2009 international symposium on Memory management, June 19-20, 2009, Dublin, Ireland
	Doosan Cho , Sudeep Pasricha , Ilya Issenin , Nikil D. Dutt , Minwook Ahn , Yunheung Paek, Adaptive scratch pad memory management for dynamic behavior of multimedia applications, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, v.28 n.4, p.554-567, April 2009
	Yutao Zhong , Xipeng Shen , Chen Ding, Program locality analysis using reuse distance, ACM Transactions on Programming Languages and Systems (TOPLAS), v.31 n.6, p.1-39, August 2009

INDEX TERMS

Primary Classification:
D. Software
D.3 PROGRAMMING LANGUAGES
D.3.4 Processors
Subjects: Optimization

General Terms:
Algorithms, Languages, Performance

Keywords:
Cache, compiler optimization, data locality, loop distribution, loop fusion, loop permutation, loop reversal, loop transformations, microprocessors, simulation

REVIEW

"Noah S. Prywes : Reviewer"

When using a processor with a cache memory of limited size, the order of memory referencing in the program can affect the overall computation time. It would be too difficult for a programmer to consider this effect in composing a program. Inst more...

Collaborative Colleagues:

Kathryn S. McKinley: colleagues

Steve Carr: colleagues

Chau-Wen Tseng: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player