An integer linear programming approach for optimizing cache locality

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.

An integer linear programming approach for optimizing cache locality

Full text

Pdf (1.37 MB)

Source

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

Rhodes, Greece

Pages: 500 - 509

Year of Publication: 1999

ISBN:1-58113-164-X

Authors

M. Kandemir	CPDC, Department of Electrical and Computer Engineering, Northwestern University, Evanston, IL
P. Banerjee	CPDC, Department of Electrical and Computer Engineering, Northwestern University, Evanston, IL
A. Choudhary	CPDC, Department of Electrical and Computer Engineering, Northwestern University, Evanston, IL
J. Ramanujam	Department of Electrical and Computer Engineering, Louisiana State University, Baton Rouge, LA
E. Ayguadé	Centre Europeu de Parallelisme de Barcelona (CEPBA) Dept d'Arquitectura de Computadors, Univ. Politecnica de Catalunya, Jordi Girona 1-3, Modul D6, Barcelona 08034, Spain

Sponsor

SIGARCH: ACM Special Interest Group on Computer Architecture

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 20, Citation Count: 8

Additional Information:

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

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	Berkelaar, Ip_solve version 2.1, Available through anonymous fi-p from ftp://fip.es.ele, me.nl/pub/Ip_solve.
	2	Steve Carr, Combining Optimization for Cache and Instruction-Level Parallelism, Proceedings of the 1996 Conference on Parallel Architectures and Compilation Techniques, p.238, October 20-23, 1996
	3	Frederic T. Chong , Beng-Hong Lim , Ricardo Bianchini , John Kubiatowicz , Anant Agarwal, Application Performance on the MIT Alewife Machine, Computer, v.29 n.12, p.57-64, December 1996 [doi>10.1109/2.546610]
	4	Michał Cierniak , Wei Li, Unifying data and control transformations for distributed shared-memory machines, Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation, p.205-217, June 18-21, 1995, La Jolla, California, United States [doi>10.1145/207110.207145]
	5	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
	6	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]
	7	Jordi Garcia , Eduard Ayguadé , Jesus Lebarta, A novel approach towards automatic data distribution, Proceedings of the 1995 ACM/IEEE conference on Supercomputing (CDROM), p.78-es, December 04-08, 1995, San Diego, California, United States [doi>10.1145/224170.224500]
	8	David A. Patterson , John L. Hennessy, Computer architecture: a quantitative approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1990
	9	High Performance Computational Chemistry Group. NWChem: A computational chemistry package for parallel computers, version 1.1, Pacific Northwest Laboratory, Richland, WA 99352, 1995.
	10	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 [doi>10.1145/277830.277849]
	11	M. Kandemir , A. Choudhary , P. Banerjee , J. Ramanujam, A Matrix-Based Approach to the Global Locality Optimization Problem, Proceedings of the 1998 International Conference on Parallel Architectures and Compilation Techniques, p.306, October 12-18, 1998
	12	M. Kandemir , A. Choudhary , J. Ramanujam , P. Banerjee, Improving locality using loop and data transformations in an integrated framework, Proceedings of the 31st annual ACM/IEEE international symposium on Microarchitecture, p.285-297, November 1998, Dallas, Texas, United States
	13	Mahmut T. Kandemir , Alok N. Choudhary , J. Ramanujam , Prithviraj Banerjee, A Graph Based Framework to Detect Optimal Memory Layouts for Improving Data Locality, Proceedings of the 13th International Symposium on Parallel Processing and the 10th Symposium on Parallel and Distributed Processing, p.738-743, April 12-16, 1999
	14	Wayne Kelly , Vadim Maslov , William Pugh , Evan Rosser , Tatiana Shpeisman , David Wonnacott, The Omega Library interface guide, University of Maryland at College Park, College Park, MD, 1995
	15	Ken Kennedy , Ulrich Kremer, Automatic data layout for high performance Fortran, Proceedings of the 1995 ACM/IEEE conference on Supercomputing (CDROM), p.76-es, December 04-08, 1995, San Diego, California, United States [doi>10.1145/224170.224495]
	16	Induprakas Kodukula , Nawaaz Ahmed , Keshav Pingali, Data-centric multi-level blocking, Proceedings of the ACM SIGPLAN 1997 conference on Programming language design and implementation, p.346-357, June 16-18, 1997, Las Vegas, Nevada, United States [doi>10.1145/258915.258946]
	17	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 [doi>10.1145/106972.106981]
	18	S.-T Leung and J. Zahorjan. Optimizing data locality by array restructuring. Technical Report TR 95-09-01, Dept. of Computer Science and Engineering, University of Washington, September 1995.
	19	Wei Li, Compiling for numa parallel machines, Cornell University, Ithaca, NY, 1993
	20	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]
	21	M. O'Boyle and P. Knijnenburg. Non-singular data transformations: definition, validity, applications. In Proc. 6th Workshop on Compilers for Parallel Computers (CPC'96), pages 287-297, Aachen, Germany, 1996.
	22	M. F. P. O'Boyle , P. M. W. Knijnenburg, Integrating Loop and Data Transformations for Global Optimisation, Proceedings of the 1998 International Conference on Parallel Architectures and Compilation Techniques, p.12, October 12-18, 1998
	23	Rafael H. Saavedra-Barrera , Weihua Mao , Daeyeon Park , Jacqueline Chame , Sungdo Moon, The Combined Effectiveness of Unimodular Transformations, Tiling, and Software Prefetching, Proceedings of the 10th International Parallel Processing Symposium, p.39-45, April 15-19, 1996
	24	Vivek Sarkar , Guang R. Gao , Shaohua Han, Locality Analysis for Distributed Shared-Memory Multiprocessors, Proceedings of the 9th International Workshop on Languages and Compilers for Parallel Computing, p.20-40, August 08-10, 1996
	25	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 [doi>10.1145/113445.113449]
	26	Michael Joseph Wolfe , Carter Shanklin , Leda Ortega, High Performance Compilers for Parallel Computing, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995

CITED BY 7

	Mahmut Taylan Kandemir, A compiler technique for improving whole-program locality, ACM SIGPLAN Notices, v.36 n.3, p.179-192, March 2001
	Jan Sjödin , Carl von Platen, Storage allocation for embedded processors, Proceedings of the 2001 international conference on Compilers, architecture, and synthesis for embedded systems, November 16-17, 2001, Atlanta, Georgia, USA
	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
	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
	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
	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
	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