Towards a theory of cache-efficient algorithms
From MaRDI portal
Abstract: We describe a model that enables us to analyze the running time of an algorithm in a computer with a memory hierarchy with limited associativity, in terms of various cache parameters. Our model, an extension of Aggarwal and Vitter's I/O model, enables us to establish useful relationships between the cache complexity and the I/O complexity of computations. As a corollary, we obtain cache-optimal algorithms for some fundamental problems like sorting, FFT, and an important subclass of permutations in the single-level cache model. We also show that ignoring associativity concerns could lead to inferior performance, by analyzing the average-case cache behavior of mergesort. We further extend our model to multiple levels of cache with limited associativity and present optimal algorithms for matrix transpose and sorting. Our techniques may be used for systematic exploitation of the memory hierarchy starting from the algorithm design stage, and dealing with the hitherto unresolved problem of limited associativity.
Recommendations
- scientific article; zbMATH DE number 1445384
- scientific article; zbMATH DE number 2011837
- Cache-oblivious algorithms
- On the limits of cache-obliviousness
- Algorithm Theory - SWAT 2004
- The cache complexity of multithreaded cache oblivious algorithms
- Cache and I/O efficent functional algorithms
- Cache-independent algorithms
- Cache-adaptive algorithms
- scientific article; zbMATH DE number 2086622
Cited in
(29)- Cache-independent algorithms
- An algorithm for the sequence alignment with gap penalty problem using multiway divide-and-conquer and matrix transposition
- On a model of virtual address translation
- Cache and I/O efficent functional algorithms
- Universal cycles for minimum coverings of pairs by triples, with application to 2-radius sequences
- Cache-oblivious algorithms
- Engineering a cache-oblivious sorting algorithm
- An Experimental Evaluation of Global Caching for $\mathcal {ALC}$ (System Description)
- scientific article; zbMATH DE number 1305454 (Why is no real title available?)
- An analytical model for designing memory hierarchies
- Measuring cache and TLB performance and their effect on benchmark runtimes
- scientific article; zbMATH DE number 2011837 (Why is no real title available?)
- scientific article; zbMATH DE number 1756010 (Why is no real title available?)
- Efficient algorithms with asymmetric read and write costs
- scientific article; zbMATH DE number 2086622 (Why is no real title available?)
- Memory cache and lisp
- scientific article; zbMATH DE number 1445384 (Why is no real title available?)
- On the Optimal Load-Memory Tradeoff of Cache-Aided Scalar Linear Function Retrieval
- The cost of address translation
- Algorithm Theory - SWAT 2004
- Cache-adaptive algorithms
- Optimal cache-aware suffix selection
- Cache miss analysis of WHT algorithms
- The combinatorics of cache misses during matrix multiplication
- The cost of cache-oblivious searching
- The cache complexity of multithreaded cache oblivious algorithms
- A short proof of optimality for the MIN cache replacement algorithm
- On the limits of cache-oblivious rational permutations
- Another short proof of optimality for the MIN cache replacement algorithm
This page was built for publication: Towards a theory of cache-efficient algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3455551)
