Article

Free access

An integer linear programming approach for optimizing cache locality

Authors:

E. AyguadéAuthors Info & Claims

ICS '99: Proceedings of the 13th international conference on Supercomputing

Pages 500 - 509

https://doi.org/10.1145/305138.305247

Published: 01 May 1999 Publication History

PDF eReader

References

[1]

Berkelaar, Ip_solve version 2.1, Available through anonymous fi-p from ftp://fip.es.ele, me.nl/pub/Ip_solve.

Google Scholar

[2]

S. Can-. Combining optimization for cache and instructionlevel parallelism. In Proc. the 1996 International Conference on Parallel Architectures and Compiler Techniques (PA CT'96), Boston MA, Oct 1996.

Digital Library

Google Scholar

[3]

F. T. Chong, B-H. Lira, R. Bianchini, J. Kubiatowicz, and A. Agarwal. Application performance on the MIT Alewife machine. IEEE Computer, Vol. 29, No. 12, December 1996, pp. 57-64.

Digital Library

Google Scholar

[4]

M. Cierniak and W. Li. Unifying data and control transformations for distributed shared memory machines. Proc. SIG- PLAN Conf. Programming Language Design & Implementation (PLDI'95), La Jolla, CA, pages 205-217, June 1995.

Digital Library

Google Scholar

[5]

J. Ferrante, V. Sarkar, and W. Thrash. On estimating and enhancing cache effectiveness. In Proc. Languages and Compilers for Parallel Computing (LCPC'91), pages 328-343, 1991.

Digital Library

Google Scholar

[6]

D. Gannon, W. Jalby, and K. Gallivan. Strategies for cache and local memory management by global program transformations. Journal of Parallel & Distributed Computing, 5(5):587-616, October 1988.

Digital Library

Google Scholar

[7]

J. Garcia, E. Ayguade, and J. Labarta. A novel approach towards automatic data distribution. In Proc. Supercomputing'95, San Diego, December 1995.

Digital Library

Google Scholar

[8]

J. Hennessy and D. Patterson. Computer Architecture: A Quantitative Approach. Second edition, Morgan Kaufmann Publishers, San Mateo, CA, 1995.

Digital Library

Google Scholar

[9]

High Performance Computational Chemistry Group. NWChem: A computational chemistry package for parallel computers, version 1.1, Pacific Northwest Laboratory, Richland, WA 99352, 1995.

Google Scholar

[10]

M. Kandernir, A. Choudhary, N. Shenoy, P. Banerjee, and J. Ramanujam. A hyperplane based approach for optimizing spatial locality in loop nests, in Proc. 1998 A CMlnternational Conference on Supercomputing (ICS'98), pages 69-76, Melbourne, Australia, July 1998.

Digital Library

Google Scholar

[11]

M. Kandemir, A. Choudhary, J. Ramanujam, and P. Banerjee. A matrix-based approach to the global locality optimization problem. In Proc. 1998 Intl. Conf. Parallel Architectures & Compilation Techniques (PACT'98), Paris, France, October 1998.

Digital Library

Google Scholar

[12]

M. Kandemir, A. Choudhary, J. Ramanujam, and P. Banerjee. Improving locality using loop and data transformations in an integrated approach. In Proc. MICRO-31, Dallas, TX, December 1998.

Digital Library

Google Scholar

[13]

M. Kandemir, A. Choudhary, J. Ramanujam, and P. Banerjee. A graph based framework to detect optimal memory layouts for improving data locality. In Proc. IPPS 99, San Juan, Puerto Rico, April 1999.

Digital Library

Google Scholar

[14]

W. Kelly, V. Maslov, W. Pugh, E. Rosser, T. Shpeisman, and D. Wonnacott. The Omega Library interface guide. Technical Report CS-TR-3445, CS Dept., University of Maryland, College Park, March 1995.

Digital Library

Google Scholar

[15]

K. Kennedy and U. Kremer. Automatic data layout for High Performance Fortran. in Proc. $upercomputing'95, San Diego, CA, December 1995.

Digital Library

Google Scholar

[16]

I. Kodukula, N. Armed, and K. Pingali. Data-centric multilevel blocking. In Proc. Programming Language Design and Implementation (PLDI'97), June 1997.

Digital Library

Google Scholar

[17]

M. Lam, E. Rothberg, and M. Wolf. The cache performance and optimizations of blocked algorithms. In Proc. the 4th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS'91), ACM, New York.

Digital Library

Google Scholar

[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.

Google Scholar

[19]

W. Li. Compiling for NUMA ParalleIMachines. Ph.D. Thesis, Comell University, Ithaca, NY, 1993.

Digital Library

Google Scholar

[20]

K. McKinley, S. Carr, and C. Tseng. Improving data locality with loop transformations, ttCM Transactions on Programming Languages & Systems, 18(4):424-453, July 1996.

Digital Library

Google Scholar

[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.

Google Scholar

[22]

M. O'Boyte and P. Knijnenburg. Integrating loop and data transformations for global optimisation. In Proc. International Conference on Parallel Architectures and Compilation Techniques (PA CT'98), October 14-17, 1998, Paris, France.

Digital Library

Google Scholar

[23]

R.H. Saavedra, W. Mao, D. Park, J. Chame, and S. Moon. The combined effectiveness of unimodular transformations, filing, and software prefetching. In Proc. 10th International Parallel Processing Symposium (IPPS'96), Honolulu, Hawaii, April 15-19, 1996, pp. 39-46.

Digital Library

Google Scholar

[24]

V. Sarkar, G. Gao, and S. Han. Locality analysis for distributed shared-memory multiprocessors. In Proc. the Ninth International Workshop on Languages & Compilers for Parallel Computing (LCPC'96), Santa Clara, California, August 1996.

Digital Library

Google Scholar

[25]

M. Wolf and M. Lam. A data locality optimizing algorithm. In Proc. SIGPLAN Conf. Programming Language Design & Implementation (PLDI'91), pages 30-44, Toronto, Canada, June 1991.

Digital Library

Google Scholar

[26]

M. Wolfe. High Performance Compilers for Parallel Computing, Addison-Wesley, CA, 1996.

Digital Library

Google Scholar

Cited By

View all

Herruzo EPlata OZapata E(2008)Using Padding to Optimize Locality in Scientific ApplicationsProceedings of the 8th international conference on Computational Science, Part I10.1007/978-3-540-69384-0_91(863-872)Online publication date: 23-Jun-2008
https://dl.acm.org/doi/10.1007/978-3-540-69384-0_91
Herruzo EZapata EPlata O(2007)Maximum and Sorted Cache Occupation Using Array Padding2007 International Conference on Embedded Computer Systems: Architectures, Modeling and Simulation10.1109/ICSAMOS.2007.4285749(178-185)Online publication date: Jul-2007
https://doi.org/10.1109/ICSAMOS.2007.4285749
Beyls KD'Hollander EAlderighi MSalapura VMcKee S(2006)Intermediately executed code is the key to find refactorings that improve temporal data localityProceedings of the 3rd conference on Computing frontiers10.1145/1128022.1128071(373-382)Online publication date: 3-May-2006
https://dl.acm.org/doi/10.1145/1128022.1128071
Show More Cited By

Index Terms

An integer linear programming approach for optimizing cache locality

Recommendations

Locality-Driven Dynamic GPU Cache Bypassing
ICS '15: Proceedings of the 29th ACM on International Conference on Supercomputing

This paper presents novel cache optimizations for massively parallel, throughput-oriented architectures like GPUs. L1 data caches (L1 D-caches) are critical resources for providing high-bandwidth and low-latency data accesses. However, the high number of ...
Reshaping cache misses to improve row-buffer locality in multicore systems
PACT '13: Proceedings of the 22nd international conference on Parallel architectures and compilation techniques

Optimizing cache locality has always been important since the emergence of caches, and numerous cache locality optimization schemes have been published in compiler literature. However, in modern architectures, cache locality is not the only factor that ...
Co-optimizing memory-level parallelism and cache-level parallelism
PLDI 2019: Proceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation

Minimizing cache misses has been the traditional goal in optimizing cache performance using compiler based techniques. However, continuously increasing dataset sizes combined with large numbers of cache banks and memory banks connected using on-chip ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

ICS '99: Proceedings of the 13th international conference on Supercomputing

June 1999

509 pages

ISBN:158113164X

DOI:10.1145/305138

Chairmen:
Theodore Papatheodorou
Univ. of Patras, Patras, Greece
,
Mateo Valero
Univ. Politècnica de Catalunya, Barcelona, Spain
,
Constantine D. Polychronopoulos
Univ. of Illinois
,
Yoichi Muraoka
Waseda Univ.
,
Jesus Labarta
Univ. Politècnica de Catalunya, Barcelona, Spain

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 May 1999

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

ICS99

Sponsor:

SIGARCH

ICS99: The 13th ACM International Conference on Supercomputing

June 20 - 25, 1999

Rhodes, Greece

Acceptance Rates

ICS '99 Paper Acceptance Rate 57 of 180 submissions, 32%;

Overall Acceptance Rate 629 of 2,180 submissions, 29%

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
469
Total Downloads

Downloads (Last 12 months)58
Downloads (Last 6 weeks)9

Reflects downloads up to 06 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Herruzo EPlata OZapata E(2008)Using Padding to Optimize Locality in Scientific ApplicationsProceedings of the 8th international conference on Computational Science, Part I10.1007/978-3-540-69384-0_91(863-872)Online publication date: 23-Jun-2008
https://dl.acm.org/doi/10.1007/978-3-540-69384-0_91
Herruzo EZapata EPlata O(2007)Maximum and Sorted Cache Occupation Using Array Padding2007 International Conference on Embedded Computer Systems: Architectures, Modeling and Simulation10.1109/ICSAMOS.2007.4285749(178-185)Online publication date: Jul-2007
https://doi.org/10.1109/ICSAMOS.2007.4285749
Beyls KD'Hollander EAlderighi MSalapura VMcKee S(2006)Intermediately executed code is the key to find refactorings that improve temporal data localityProceedings of the 3rd conference on Computing frontiers10.1145/1128022.1128071(373-382)Online publication date: 3-May-2006
https://dl.acm.org/doi/10.1145/1128022.1128071
Kadayif IKandemir M(2004)Quasidynamic Layout Optimizations for Improving Data LocalityIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2004.7015:11(996-1011)Online publication date: 1-Nov-2004
https://dl.acm.org/doi/10.1109/TPDS.2004.70
Navarro AZapata EPadua D(2003)Compiler Techniques for the Distribution of Data and ComputationIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2003.120650314:6(545-562)Online publication date: 1-Jun-2003
https://dl.acm.org/doi/10.1109/TPDS.2003.1206503
Sjödin Jvon Platen CGao GMudge TPalem K(2001)Storage allocation for embedded processorsProceedings of the 2001 international conference on Compilers, architecture, and synthesis for embedded systems10.1145/502217.502221(15-23)Online publication date: 16-Nov-2001
https://dl.acm.org/doi/10.1145/502217.502221
Kandemir M(2001)A compiler technique for improving whole-program localityACM SIGPLAN Notices10.1145/373243.36021936:3(179-192)Online publication date: 1-Jan-2001
https://dl.acm.org/doi/10.1145/373243.360219
Kandemir MHankin CSchmidt D(2001)A compiler technique for improving whole-program localityProceedings of the 28th ACM SIGPLAN-SIGACT symposium on Principles of programming languages10.1145/360204.360219(179-192)Online publication date: 1-Jan-2001
https://dl.acm.org/doi/10.1145/360204.360219
Kandemir MBanerjee PChoudhary ARamanujam JAyguadé E(2001)Static and Dynamic Locality Optimizations Using Integer Linear ProgrammingIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2001.118418612:9(922-941)Online publication date: 1-Sep-2001
https://dl.acm.org/doi/10.1109/TPDS.2001.1184186

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Locality-Driven Dynamic GPU Cache Bypassing

Reshaping cache misses to improve row-buffer locality in multicore systems

Co-optimizing memory-level parallelism and cache-level parallelism