|
|||
|
IMADA - Department of Mathematics and Computer Science |
|
Modern computers contain a hierarchy of memory levels, with each level acting as a cache for the next. Typical components of the memory hierarchy are registers, L1 cache, L2 cache, main memory, and disk. The time for access increases with each new level, often by an order of magnitude or more. This makes the cost of a memory access depend highly on where in the hierarchy it is taking place. As an example, access to disk is currently 10^7 times slower than access to L1 cache. Consequently, the memory access pattern of an algorithm has a major impact on its running time in practice, and often memory accesses, not CPU cycles, constitute the bottleneck in computation. Since analysis of algorithms in the standard RAM model is unable to capture this, a number of more elaborate models have been defined. Most widely used is the I/O model of Aggarwal and Vitter, which models a memory hierarchy with two levels. Over the last decade, a large body of results for the I/O model has appeared. Recently, a generalization of the I/O model was proposed by Frigo, Leiserson, Prokop, and Ramachandran. This so-called cache-oblivious model in a very elegant way generalizes the I/O model to cover multi-level memory hierarchies, and appears to be a promising way of designing algorithms adapting to the entire memory hierarchy on computers. In this talk, we give an introduction to the cache-oblivious model, and survey the current knowledge about its power, both in theory and practice. Host: Kim Skak Larsen
SDU HOME | IMADA HOME | Previous Page Last modified: February 6, 2004. Joan Boyar (joan@imada.sdu.dk) |