The DOI matches its Crossref record; 27 of the 27 references it cites were found in a registry or an index.
Cache miss equations: a compiler framework for analyzing and tuning memory behavior
Open accessAbstract
With the ever-widening performance gap between processors and main memory, cache memory, which is used to bridge this gap, is becoming more and more significant. Caches work well for programs that exhibit sufficient locality. Other programs, however, have reference patterns that fail to exploit the cache, thereby suffering heavily from high memory latency. In order to get high cache efficiency and achieve good program performance, efficient memory accessing behavior is necessary. In fact, for many programs, program transformations or source-code changes can radically alter memory access patterns, significantly improving cache performance. Both hand-tuning and compiler optimization techniques are often used to transform codes to improve cache utilization. Unfortunately, cache conflicts are difficult to predict and estimate, precluding effective transformations. Hence, effective transformations require detailed knowledge about the frequency and causes of cache misses in the code. This article describes methods for generating and solving Cache Miss Equations (CMEs) that give a detailed representation of cache behavior, including conflict misses, in loop-oriented scientific code. Implemented within the SUIF compiler framework, our approach extends traditional compiler reuse analysis to generate linear Diophantine equations that summarize each loop's memory behavior. While solving these equations is in general difficult, we show that is also unnecessary, as mathematical techniques for manipulating Diophantine equations allow us to relatively easily compute and/or reduce the number of possible solutions, where each solution corresponds to a potential cache miss. The mathematical precision of CMEs allows us to find true optimal solutions for transformations such as blocking or padding. The generality of CMEs also allows us to reason about interactions between transformations applied in concert. The article also gives examples of their use to determine array padding and offset amounts that minimize cache misses, and to determine optimal blocking factors for tiled code. Overall, these equations represent an analysis framework that offers the generality and precision needed for detailed compiler optimizations.
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
Computer Architecture: A Quantitative Approach
Hennessy, J. L., & Patterson, D. A. (1989) · UCLA - Biblioteca de Ciencias y Tecnologia Felix Morales Bueno · Cited by 9,370
Computer architecture: a quantitative approach
Shute, M. (1993) · Microelectronics Journal · doi:10.1016/0026-2692(93)90111-q · Cited by 3,336
A data locality optimizing algorithm
Wolf, M. E., & Lam, M. S. (1991) · Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation - PLDI '91 · doi:10.1145/113445.113449 · Cited by 1,331
The cache performance and optimizations of blocked algorithms
Lam, M. D., Rothberg, E. E., & Wolf, M. E. (1991) · Proceedings of the fourth international conference on Architectural support for programming languages and operating systems - ASPLOS-IV · doi:10.1145/106972.106981 · Cited by 921
Computer architecture (2nd ed.): a quantitative approach
Hennessy, J. L., & Patterson, D. A. (1996) · Morgan Kaufmann Publishers Inc. eBooks · Cited by 876
Design and evaluation of a compiler algorithm for prefetching
Mowry, T. C., Lam, M. S., & Gupta, A. (1992) · Proceedings of the fifth international conference on Architectural support for programming languages and operating systems · doi:10.1145/143365.143488 · Cited by 767
The Omega test: a fast and practical integer programming algorithm for dependence analysis
Pugh, W. (1991) · Proceedings of the 1991 ACM/IEEE conference on Supercomputing - Supercomputing '91 · doi:10.1145/125826.125848 · Cited by 750
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 734
Evaluating associativity in CPU caches
Hill, M. D., & Smith, A. J. (1989) · IEEE Transactions on Computers · doi:10.1109/12.40842 · Cited by 606
A practical algorithm for exact array dependence analysis
Pugh, W. (1992) · Communications of the ACM · doi:10.1145/135226.135233 · Cited by 568
Cited by
Self-Adapting Linear Algebra Algorithms and Software
Demmel, J., Dongarra, J., Eijkhout, V., Fuentes, E., Petitet, A., Vuduc, R., Whaley, R. C., & Yelick, K. (2005) · Proceedings of the IEEE · doi:10.1109/jproc.2004.840848 · Cited by 204
Tiling Optimizations for 3D Scientific Computations
Rivera, G., & Tseng, C.-W. (2000) · ACM/IEEE SC 2000 Conference (SC'00) · doi:10.1109/sc.2000.10015 · Cited by 127
(2002) · doi:10.5555/762761.762822 · Cited by 115
Performance Optimizations and Bounds for Sparse Matrix-Vector Multiply
Vuduc, R., Demmel, J. W., Yelick, K. A., Kamil, S., Nishtala, R., & Lee, B. (2002) · ACM/IEEE SC 2002 Conference (SC'02) · doi:10.1109/sc.2002.10025 · Cited by 66
Metadata
- Authors
- Ghosh, S., Martonosi, M., & Malik, S.
- Venue
- ACM Transactions on Programming Languages and Systems
- Published
- 1999-07
- Volume
- 21
- Issue
- 4
- Pages
- 703-746
- ISSN
- 0164-0925 (ISSN-L)
- 1558-4593
- OpenAlex
- W2158737060
- Cited by
- 269
- References
- 27
- FWCI
- 21.85
- Type
- journal article
- Language
- en
- Open access
- bronze
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
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Cache miss equations: a compiler framework for analyzing and tuning memory behavior. https://app.cochat.ai/papers/10.1145/325478.325479
- The paper
- Ghosh, S., Martonosi, M., & Malik, S. (1999). Cache miss equations: a compiler framework for analyzing and tuning memory behavior. ACM Transactions on Programming Languages and Systems. https://doi.org/10.1145/325478.325479
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.