CoChat
Sign Up
Cited by 155Parallel Computing and Optimization TechniquesLogic, programming, and type systemsEmbedded Systems Design Techniques

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 access
Carr, Steve, Kennedy, Ken·1994·ACM Transactions on Programming Languages and Systems
DOI 10.1145/197320.197366
Open this paper in CoChat — free accountOpen PDF

Abstract

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.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.1145/197320.197366

Cites

30 of 30 references verified0 citation errors · 0 not checkable

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.

A few free checks a day · papers already verified open instantly · results are public

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

Research works printed but not linked: 4

  1. 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.]]
  2. 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
  3. 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]]
  4. 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

See all 155

Related

See all

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
Publisher
Association for Computing Machinery (ACM)
Published
1994-11
Volume
16
Issue
6
Pages
1768-1810
ISSN
  • 0164-0925 (ISSN-L)
  • 1558-4593
DOI
10.1145/197320.197366
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
Licence
www.acm.org/publications/policies/copyright_policy#Background (vor)
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