Header menu link for other important links
Towards a theory of cache-efficient algorithms
, S. Chatterjee
Published in
Pages: 829 - 838
We describe a model that enables us to analyze the run-nine 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 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. Our techniques may be used for systematic exploitation of the memory hierarchy at the algorithm design stage, and dealing with the hitherto unresolved problem of limited associativity.
About the journal
Published in
Open Access
Impact factor