The DOI matches its Crossref record; 30 of the 30 references it cites were found in a registry or an index.
Improving the ratio of memory operations to floating-point operations in loops
Open accessAbstract
Over the past decade, microprocessor design strategies have focused on increasing the computational power on a single chip. Because computations often require more data from cache per floating-point operation than a machine can deliver and because operations are pipelined, idle computational cycles are common when scientific applications are executed. To overcome these bottlenecks, programmers have learned to use a coding style that ensures a better balance between memory references and floating-point operations. In our view, this is a step in the wrong direction because it makes programs more machine-specific. A programmer should not be required to write a new program version for each new machine; instead, the task of specializing a program to a target machine should be left to the compiler. But is our view practical? Can a sophisticated optimizing compiler obviate the need for the myriad of programming tricks that have found their way into practice to improve the performance of the memory hierarchy? In this paper we attempt to answer that question. To do so, we develop and evaluate techniques that automatically restructure program loops to achieve high performance on specific target architectures. These methods attempt to balance computation and memory accesses and seek to eliminate or reduce pipeline interlock. To do this, they estimate statically the balance between memory operations and floating-point operations for each loop in a particular program and use these estimates to determine whether to apply various loop transformations. Experiments with our automatic techniques show that integer-factor speedups are possible on kernels. Additionally, the estimate of the balance between memory operations and computation, and the application of the estimate are very accurate—experiments reveal little difference between the balance achieved by our automatic system that is made possible by hand optimization.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Lecture Notes in Computer Science 1205
(1999) · Industrial Robot the international journal of robotics research and application · doi:10.1108/ir.1999.04926fae.001 · Cited by 39,209
A data locality optimizing algorithm
Wolf, M. E., & Lam, M. S. (1991) · ACM-SIGPLAN Symposium on Programming Language Design and Implementation · doi:10.1145/113445.113449 · Cited by 1,272
The cache performance and optimizations of blocked algorithms
Lam, M. D., Rothberg, E. E., & Wolf, M. E. (1991) · doi:10.1145/106972.106981 · Cited by 926
Automatic translation of FORTRAN programs to vector form
Allen, R., & Kennedy, K. (1987) · ACM Transactions on Programming Languages and Systems · doi:10.1145/29873.29875 · Cited by 735
Self-citationRegister allocation via coloring
Chaitin, G. J., Auslander, M. A., Chandra, A. K., Cocke, J., Hopkins, M. E., & Markstein, P. W. (1981) · Computer Languages · doi:10.1016/0096-0551(81)90048-5 · Cited by 729
The Structure of Computers and Computations
Kuck, D. L. (1978) · UCLA - Biblioteca de Ciencias y Tecnologia Felix Morales Bueno · Cited by 500
Strategies for cache and local memory management by global program transformation
Gannon, D. B., Jalby, W., & Gallivan, K. A. (1988) · Journal of Parallel and Distributed Computing · doi:10.1016/0743-7315(88)90014-7 · Cited by 350
The Generation of Optimal Code for Arithmetic Expressions
Sethi, R., & Ullman, J. D. (1970) · Journal of the ACM · doi:10.1145/321607.321620 · Cited by 289
Register allocation via graph coloring
Briggs, P. (1992) · Cited by 244
Improving register allocation for subscripted variables
Callahan, D. P., Carr, S., & Kennedy, K. (2004) · ACM SIGPLAN Notices · doi:10.1145/989393.989428 · Cited by 244
Self-citation
Research works printed but not linked: 4
- ALLEN , F. AND COCKE , J. 1972 . A catalogue of optimizing transformations. In Design and Opttmzzation of Compilers. Prentice-Hail, Englewood Cliffs , N.J. , 1 - 30 .]] ALLEN, F. AND COCKE, J. 1972. A catalogue of optimizing transformations. In Design and Opttmzzation of Compilers. Prentice-Hail, Englewood Cliffs, N.J., 1-30.]]
- KENNEDY , K. AND MCKJNLEY , K. 1992 . Optimizing for parallelism and memory hierarchy . In Proceedings of the 1992 International Conference on Supercomputing. ACM , New York , 323 - 334 .]] 10.1145/143369.143427 KENNEDY, K. AND MCKJNLEY, K. 1992. Optimizing for parallelism and memory hierarchy. In Proceedings of the 1992 International Conference on Supercomputing. ACM, New York, 323-334.]] 10.1145/143369.143427 · DOI
- KUCK , D. , KUHN , R. , LEASURE , B. , AND WOLFE , M. 1984. The structure of an advanced retargetable vectorizer . In Supercomputers: Destgn and Apphcattons . IEEE Computer Society Press , Los Alamitos , Calif., 163-178]] KUCK, D., KUHN, R., LEASURE, B., AND WOLFE, M. 1984. The structure of an advanced retargetable vectorizer. In Supercomputers: Destgn and Apphcattons. IEEE Computer Society Press, Los Alamitos, Calif., 163-178]]
- MEADOWS , L , NAKAMOTO , S. , AND SCHUSTER , V 1992. A vectonzing, sot~ware pipelinmg campller for LIW and superscalar architectures In Proceedings of RISC '92.]] MEADOWS, L, NAKAMOTO, S., AND SCHUSTER, V 1992. A vectonzing, sot~ware pipelinmg campller for LIW and superscalar architectures In Proceedings of RISC '92.]]
Cited by
Items 101–153 of 153
Uniform lease vs. LRU cache: analysis and evaluation
Chen, D., Ding, C., Liu, F., Reber, B., Smith, W., & Li, P. (2021) · ACM SIGPLAN International Symposium on Memory Management (ISMM) · doi:10.1145/3459898.3463908 · Cited by 8
Optimizing loop performance for clustered VLIW architectures
Yi, Q., Carr, S., & Sweany, P. H. (2003) · International Conference on Parallel Architectures and Compilation Techniques (PACT) · doi:10.1109/pact.2002.1106026 · Cited by 8
Self-citationExploiting instruction-level parallelism for memory system performance
Pai, V. S., & Adve, S. V. (2000) · Rice Research Repository (Rice University) · Cited by 8
Computational Capacity-Based Codesign of Computer Systems
Kuck, D. J. (2012) · Springer eBooks · doi:10.1007/978-1-4471-2437-5_2 · Cited by 7
Compiler-assisted performance tuning
Chen, C., Chame, J., Nelson, Y. L., Diniz, P. C., Hall, M. W., & Lucas, R. F. (2007) · Journal of Physics Conference Series · doi:10.1088/1742-6596/78/1/012024 · Cited by 7
Scalarization on Short Vector Machines
Zhao, Y. F., & Kennedy, K. (2005) · IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS) · doi:10.1109/ispass.2005.1430573 · Cited by 7
Self-citationLoop Transformations for Architectures with Partitioned Register Banks
Huang, X., Carr, S., & Sweany, P. H. (2001) · ACM SIGPLAN Notices · doi:10.1145/384196.384206 · Cited by 7
Self-citationA quantitative analysis of loop nest locality
McKinley, K. S., & Temam, O. (1996) · ACM SIGPLAN Notices · doi:10.1145/248209.237161 · Cited by 6
Loop Transformations for Architectures with Partitioned Register Banks
Huang, X., Carr, S., & Sweany, P. H. (2001) · ACM SIGPLAN/SIGBED Conference on Languages, Compilers, and Tools for Embedded Systems (LCTES) · doi:10.1145/384197.384206 · Cited by 6
Self-citationCombined ILP and Register Tiling: Analytical Model and Optimization Framework
Renganarayana, L., Upadrasta, R., & Rajopadhye, S. V. (2006) · Lecture notes in computer science · doi:10.1007/978-3-540-69330-7_17 · Cited by 5
Malas, T., Ahmadia, A. J., Brown, J., Gunnels, J. A., & Keyes, D. E. (2012) · The International Journal of High Performance Computing Applications · doi:10.1177/1094342012444795 · Cited by 5
Loop Acceleration Exploration for ASIP Architecture
Mbaye, M. M., Bélanger, N., Savaria, Y., & Pierre, S. (2011) · IEEE Transactions on Very Large Scale Integration (VLSI) Systems · doi:10.1109/tvlsi.2011.2107923 · Cited by 5
Loffeld, J. J., & Hittinger, J. (2017) · The International Journal of High Performance Computing Applications · doi:10.1177/1094342017691876 · Cited by 5
Comparing and combining read miss clustering and software prefetching
Pai, V. S., & Adve, S. V. (2002) · International Conference on Parallel Architectures and Compilation Techniques (PACT) · doi:10.1109/pact.2001.953310 · Cited by 5
Wang, X., Zhao, K., Huang, H., Zhou, A., & Chen, H. (2025) · Atmospheric measurement techniques · doi:10.5194/amt-18-5457-2025 · Cited by 4
Applications of storage mapping optimization to register promotion
Carribault, P., & Cohen, A. (2004) · International Conference on Supercomputing · doi:10.1145/1006209.1006244 · Cited by 4
Advances in Software Pipelining
Rong, H., & Govindarajan, R. (2007) · CRC Press eBooks · doi:10.1201/9781420043839.ch20 · Cited by 4
Search Space Properties for Mapping Coarse-Grain Pipelined FPGA Applications
Ziegler, H. E., Hall, M. W., & So, B. (2004) · Lecture notes in computer science · doi:10.1007/978-3-540-24644-2_1 · Cited by 4
Mapping Imperfect Loops to Coarse-Grained Reconfigurable Architectures
Sim, H., Lee, H., Seo, S., & Lee, J. (2015) · IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems · doi:10.1109/tcad.2015.2504918 · Cited by 3
An operation stacking framework for large ensemble computations
Belgin, M., Ribbens, C. J., & Back, G. (2007) · International Conference on Supercomputing · doi:10.1145/1274971.1274986 · Cited by 3
Compiling multimedia applications on VLIW architecture
Sakellariou, R., Stöhr, E. A., & O’boyle, M. F. P. (2002) · IEEE International Conference on Digital Signal Processing (DSP) · doi:10.1109/icdsp.1997.628534 · Cited by 3
Loop transformations for clustered VLIW architectures
Yi, Q. (2002) · doi:10.37099/mtu.dc.etds/181 · Cited by 3
LEGO: A Layout Expression Language for Code Generation of Hierarchical Mapping
Tavakkoli, A. M., Oancea, C. E., & Hall, M. W. (2026) · Proceedings of the CGO/Proceedings of the ... CGO · doi:10.1109/cgo68049.2026.11394846 · Cited by 2
Register Blocking: An Analytical Modelling Approach for Affine Loop Kernels
Anthimopoulos, T., Κεραμίδας, Γ., Kelefouras, V. I., & Stamoulis, I. (2024) · ACM International Conference on Computing Frontiers (CF) · doi:10.1145/3649153.3649194 · Cited by 2
Overview of Multicore Requirements towards Real-Time Communication
Podolski, I., & Rettberg, A. (2009) · Lecture notes in computer science · doi:10.1007/978-3-642-10265-3_32 · Cited by 2
Array scalarization in high level synthesis
Panda, P. R., Sharma, N., Pilania, A. K., Gummidipudi, K., Subramoney, S., & Jagannathan, A. (2014) · Asia and South Pacific Design Automation Conference (ASP-DAC) · doi:10.1109/aspdac.2014.6742960 · Cited by 2
Predicting Unroll Factors Using Nearest Neighbors
Stephenson, M. W., & Amarasinghe, S. P. (2004) · DSpace@MIT (Massachusetts Institute of Technology) · Cited by 2
Interactive Composition of Compiler Optimizations
Nesterenko, B., Wang, W., & Yi, Q. (2016) · Lecture notes in computer science · doi:10.1007/978-3-319-29778-1_6 · Cited by 2
Improving Performance by Reducing the Memory Footprint of Scientific Applications
Jin, G., & Mellor‐Crummey, J. (2005) · The International Journal of High Performance Computing Applications · doi:10.1177/1094342005056138 · Cited by 2
Loop fusion for clustered VLIW architectures
Yi, Q., Carr, S., & Sweany, P. H. (2002) · ACM SIGPLAN Notices · doi:10.1145/566225.513850 · Cited by 2
Self-citationBlock size selection of parallel LU and QR on PVP-based and RISC-based supercomputers
Zhang, Y., Chen, Y., & Tang, Y. (2007) · ATIP Workshop on High Performance Computing in China · doi:10.1145/1375783.1375809 · Cited by 2
Shi, Z., Gao, J., & Guan, X. (2024) · Journal of Circuits Systems and Computers · doi:10.1142/s0218126625500355 · Cited by 1
REPTILE: Performant Tiling of Recurrences
Tariq, M. U., Sundram, S., & Kjølstad, F. (2025) · Proceedings of the ACM on Programming Languages · doi:10.1145/3763074 · Cited by 1
Register Blocking: A Source-to-Source Analytical Modelling Approach for Affine Loop Kernels
Anthimopoulos, T., Κεραμίδας, Γ., Kelefouras, V. I., & Stamoulis, I. (2025) · ACM Transactions on Embedded Computing Systems · doi:10.1145/3747183 · Cited by 1
Worley, P. H. (2010) · Chapman & Hall/CRC computational science series/Chapman & Hall/CRC computational science · doi:10.1201/b10509-18 · Cited by 1
The energy impact of aggressive loop fusion
Zhu, Y., Magklis, G., Scott, M. L., Ding, C., & Albonesi, D. H. (2004) · International Conference on Parallel Architectures and Compilation Techniques (PACT) · doi:10.1109/pact.2004.1342550 · Cited by 1
Loop Transformations for Architectures with Partitioned Register Banks
Huang, X., Carr, S., & Sweany, P. H. (2001) · ACM SIGPLAN Workshop on Optimization of Middleware and Distributed Systems (OM) · doi:10.1145/384198.384206 · Cited by 1
Self-citationA quantitative analysis of loop nest locality
McKinley, K. S., & Temam, O. (1996) · ACM SIGOPS Operating Systems Review · doi:10.1145/248208.237161 · Cited by 1
Multilevel tiling for non-rectangular interation spaces
Castells, M. J. (1999) · doi:10.5821/dissertation-2117-93321
WCET-Aware Source Code Level Optimizations
Lokuciejewski, P., & Marwedel, P. (2010) · Embedded systems · doi:10.1007/978-90-481-9929-7_4
A Thread Merging Transformation to Improve Throughput of Multiple Programs
Chen, Y., & Li, X. (2015) · International Conference on Advanced Information Networking and Applications (AINA) · doi:10.1109/aina.2015.175
Automatic analysis for managing and optimizing performance-code quality
Djoudi, L. A., & Jalby, W. (2008) · doi:10.1145/1394504.1394508
Kondo, N., Koseki, A., Komatsu, H., & Fukazawa, Y. (1998) · Systems and Computers in Japan · doi:10.1002/(sici)1520-684x(199808)29:9
An experimental study of improving performance by scalar replacement
Hayder, M. E. (2000) · Advances in Engineering Software · doi:10.1016/s0965-9978(00)00011-9
A program optimization strategy for vector architectures with cache mechanisms
佐藤, 義. (2012) · Institutional Repositories DataBase (IRDB)
Fernando, C., & Castañeda, F. (2011)
Standardized Computational Complexity Evaluation for Battery State-of-Charge Estimation Algorithms
von Liebenstein, A., Donkers, M. C. F., & Kollmeyer, P. J. (2025) · IEEE Transportation Electrification Conference and Expo · doi:10.1109/itec63604.2025.11098050
LSR: Eliminating Loop Control Overhead for Energy-Efficient Processors
Yang, L. M., Huang, L., Zheng, Z., Sui, B., Wang, Y., Shen, L., Ma, S., Yang, Q., Chen, G., Pei, S., et al. (2026) · ACM Transactions on Architecture and Code Optimization · doi:10.1145/3857804
Performance and Scalability Analysis of a Chip Multi Vector Processor
Sato, Y., Musa, A., Egawa, R., Takizawa, H., Okabe, K., & Kobayashi, H. (2011) · Springer eBooks · doi:10.1007/978-3-642-22244-3_1
Metadata
- Authors
- Carr, S., & Kennedy, K.
- Affiliations
- Michigan Technological University (US)
- Rice University (US)
- ORCID
- Carr, Steve
- Venue
- ACM Transactions on Programming Languages and Systems
- Published
- 1994-11
- Volume
- 16
- Issue
- 6
- Pages
- 1768-1810
- ISSN
- 0164-0925 (ISSN-L)
- 1558-4593
- OpenAlex
- W2138007781
- Cited by
- 155
- References
- 30
- Citations by year
- 2026: 2 · 2025: 5 · 2024: 3 · 2023: 1 · 2021: 1 · 2020: 1 · 2018: 1 · 2017: 1 · 2016: 2 · 2015: 2 · 2014: 4 · 2013: 1 · 2012: 8
- FWCI
- 3.90
- Type
- journal article
- Language
- en
- Open access
- bronze
- doi.org
- Locations
- ACM Transactions on Programming Languages and Systems (publishedVersion)
- Digital Commons - Michigan Tech (Michigan Technological University) (submittedVersion)
- Topics
- Physical Sciences › Computer Science › Hardware and Architecture › Parallel Computing and Optimization Techniques
- Physical Sciences › Computer Science › Software › Logic, programming, and type systems
- Physical Sciences › Computer Science › Hardware and Architecture › Embedded Systems Design Techniques
- Keywords
- loop transformation, memory hierarchy, compiler optimization, floating-point performance, scientific kernels
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
