The DOI matches its Crossref record; 31 of the 31 references it cites were found in a registry or an index.
Cache-oblivious algorithms
Abstract
This paper presents asymptotically optimal algorithms for rectangular matrix transpose, FFT, and sorting on computers with multiple levels of caching. Unlike previous optimal algorithms, these algorithms are cache oblivious: no variables dependent on hardware parameters, such as cache size and cache-line length, need to be tuned to achieve optimality. Nevertheless, these algorithms use an optimal amount of work and move data optimally among multiple levels of cache. For a cache with size Z and cache-line length L where Z=/spl Omega/(L/sup 2/) the number of cache misses for an m/spl times/n matrix transpose is /spl Theta/(1+mn/L). The number of cache misses for either an n-point FFT or the sorting of n numbers is /spl Theta/(1+(n/L)(1+log/sub Z/n)). We also give an /spl Theta/(mnp)-work algorithm to multiply an m/spl times/n matrix by an n/spl times/p matrix that incurs /spl Theta/(1+(mn+np+mp)/L+mnp/L/spl radic/Z) cache faults. We introduce an "ideal-cache" model to analyze our algorithms. We prove that an optimal cache-oblivious algorithm designed for two levels of memory is also optimal for multiple levels and that the assumption of optimal replacement in the ideal-cache model. Can be simulated efficiently by LRU replacement. We also provide preliminary empirical results on the effectiveness of cache-oblivious algorithms in practice.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
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
Golub, G. (2012) · doi:10.56021/9781421407944 · Cited by 34,505
Rayward-Smith, V. J. (1991) · Journal of the Operational Research Society · doi:10.1057/jors.1991.155 · Cited by 16,821
An algorithm for the machine calculation of complex Fourier series
Cooley, J. W., & Tukey, J. W. (1965) · Mathematics of Computation · doi:10.1090/s0025-5718-1965-0178586-1 · Cited by 13,154
The Design and Analysis of Computer Algorithms
Aho, A. V., & Hopcroft, J. E. (1974) · CERN Document Server (European Organization for Nuclear Research) · Cited by 9,403
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
Motwani, R., & Raghavan, P. (1995) · Cambridge University Press eBooks · doi:10.1017/cbo9780511814075 · Cited by 5,123
Computer architecture: a quantitative approach
Shute, M. (1993) · Microelectronics Journal · doi:10.1016/0026-2692(93)90111-q · Cited by 3,336
Gaussian elimination is not optimal
Strassen, V. (1969) · Numerische Mathematik · doi:10.1007/bf02165411 · Cited by 2,509
Online Computation and Competitive Analysis
Borodin, A., & El‐Yaniv, R. (1998) · Cited by 2,333
Amortized efficiency of list update and paging rules
Sleator, D. D., & Tarjan, R. E. (1985) · Communications of the ACM · doi:10.1145/2786.2793 · Cited by 2,123
FFTW: an adaptive software architecture for the FFT
Frigo, M., & Johnson, S. G. (2002) · Proceedings of the 1998 IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP '98 (Cat. No.98CH36181) · doi:10.1109/icassp.1998.681704 · Cited by 1,801
Self-citationKnuth, D. E. (1973) · Cumulative Index of Computer Aided Architectural Design · Cited by 1,719
A study of replacement algorithms for a virtual-storage computer
Belady, L. A. (1966) · IBM Systems Journal · doi:10.1147/sj.52.0078 · Cited by 1,659
Fast fourier transforms: A tutorial review and a state of the art
Duhamel, P., & Vetterli, M. (1990) · Signal Processing · doi:10.1016/0165-1684(90)90158-u · Cited by 1,143
Computer Architecture: A Quantitative Approach, 2nd Edition
Hennessy, J. L., & Patterson, D. A. (1996) · Cited by 1,015
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
Sedgewick, R. (1990) · CERN Document Server (European Organization for Nuclear Research) · Cited by 730
An algorithm for computing the mixed radix fast Fourier transform
Singleton, R. (1969) · IEEE Transactions on Audio and Electroacoustics · doi:10.1109/tau.1969.1162042 · Cited by 539
I/O complexity: The red-blue pebble game
Hong, J., & Kung, H. T. (1981) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/800076.802486 · Cited by 474
A fast Fourier transform compiler
Frigo, M. (1999) · Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation · doi:10.1145/301618.301661 · Cited by 438
Self-citationFFTs in external or hierarchical memory
Bailey, D. H. (1990) · The Journal of Supercomputing · doi:10.1007/bf00162341 · Cited by 290
A model for hierarchical memory
Aggarwal, A., Alpern, B., Chandra, A., & Snir, M. (1987) · Proceedings of the nineteenth annual ACM conference on Theory of computing - STOC '87 · doi:10.1145/28395.28428 · Cited by 219
Locality of Reference in LU Decomposition with Partial Pivoting
Toledo, S. (1997) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/s0895479896297744 · Cited by 163
Nonlinear array layouts for hierarchical memory systems
Chatterjee, S., Jain, V. V., Lebeck, A. R., Mundhra, S., & Thottethodi, M. (1999) · Proceedings of the 13th international conference on Supercomputing · doi:10.1145/305138.305231 · Cited by 163
Recursive array layouts and fast parallel matrix multiplication
Chatterjee, S., Lebeck, A. R., Patnala, P. K., & Thottethodi, M. S. (1999) · ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) · doi:10.1145/305619.305645 · Cited by 116
An analysis of dag-consistent distributed shared-memory algorithms
Blumofe, R. D., Frigo, M., Joerg, C. F., Leiserson, C. E., & Randall, K. H. (1996) · ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) · doi:10.1145/237502.237574 · Cited by 115
Self-citationAuto-blocking matrix-multiplication or tracking BLAS3 performance from source code
Frens, J. D., & Wise, D. S. (1997) · ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming · doi:10.1145/263764.263789 · Cited by 112
Automatic parallelization of divide and conquer algorithms
Rugina, R., & Rinard, M. (1999) · Proceedings of the seventh ACM SIGPLAN symposium on Principles and practice of parallel programming · doi:10.1145/301104.301111 · Cited by 103
(1991) · The MIT Press eBooks · doi:10.7551/mitpress/2278.003.0007 · Cited by 103
Kumar, P. (2003) · Lecture notes in computer science · doi:10.1007/3-540-36574-5_9 · Cited by 43
Cited by
The Design and Implementation of FFTW3
Frigo, M., & Johnson, S. G. (2005) · Proceedings of the IEEE · doi:10.1109/jproc.2004.840301 · Cited by 5,086
Self-citationX-Stream: edge-centric graph processing using streaming partitions
Roy, A., Mihailovic, I., & Zwaenepoel, W. (2013) · Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles · doi:10.1145/2517349.2522740 · Cited by 673
Memory---Sequoia: programming the memory hierarchy
Fatahalian, K., Dally, W. J., Hanrahan, P., Horn, D. R., Knight, T. J., Leem, L., Houston, M., Park, J. Y., Erez, M., Ren, M., et al. (2006) · Proceedings of the 2006 ACM/IEEE conference on Supercomputing - SC '06 · doi:10.1145/1188455.1188543 · Cited by 452
Simple Linear Work Suffix Array Construction
Kärkkäinen, J., & Sanders, P. (2003) · Lecture Notes in Computer Science · doi:10.1007/3-540-45061-0_73 · Cited by 404
Minimizing Communication in Numerical Linear Algebra
Ballard, G., Demmel, J., Holtz, O., & Schwartz, O. (2011) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/090769156 · Cited by 276
Metadata
- Authors
- Frigo, M., Leiserson, C. E., Prokop, H., & Ramachandran, S.
- Venue
- 40th Annual Symposium on Foundations of Computer Science (Cat. No.99CB37039)
- Publisher
- IEEE Comput. Soc
- Published
- 1999-01-01
- Pages
- 285-297
- ISSN
- 0272-5428 (ISSN-L)
- OpenAlex
- W2095875205
- Cited by
- 803
- References
- 31
- FWCI
- 13.16
- Type
- conference paper
- Language
- en
- Open access
- closed
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
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.