CACHE-OBLIVIOUS ALGORITHMS

Unlike I/O-efficient algorithms that are efficient in terms of movements of blocks of data between main memory and external memory, cache-oblivious algorithms are algorithms designed to be efficient in terms of movements between all levels of a multilevel memory hierarchy.

More precisely, cache-oblivious algorithms are algorithms designed in the I/O-model – but without knowledge of M and B– and then analyzed as I/O-model algorithms. The beauty of the model is that since the I/O-model analysis holds for any block and memory size, it holds simultaneously on all levels of any multi-level memory hierarchy.

Thus the cache-oblivious model is a way of modeling a complicated (even unknown and/or changing) multi-level hierarchy using the simple two-level I/O-model.

Unlike the I/O-efficient algorithms area, the cache-oblivious algorithms area is relatively new and even though efficient algorithms have been developed for a number of fundamental sorting and searching problems, as well as a few geometric and graph problems, many even very fundamental problems remains open. The center considers a number of problems in the cache-oblivious model, including a number of fundamental geometric data structure and batched problems. Please refer to the centers annual reports for a discussion of obtained result.