Loading...
Please wait, while we are loading the content...
Similar Documents
Towards a Theory of Cache-Efficient Algorithms ( Extended Abstract )
| Content Provider | Semantic Scholar |
|---|---|
| Author | Sen, Sandeep Chatterjee, Siddhartha |
| Copyright Year | 1999 |
| 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. 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. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://www.cse.iitd.ernet.in/~ssen/papers/cache.ps.gz |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
