Parallelizing Cache-Oblivious algorithms
April 1, 2009
Cache-Oblivious algorithms have the advantage of achieving good cache
complexity (number of I/O operations) across all levels of a multi-level
cache hierarchy, regardless of the cache size and cache line size of each
level. We will look at the basic cache-oblivious memory model and a few
cache oblivious algorithms that have optimal I/O complexities and observe
that these algorithms have low depth. We will then see how such low depth
algorithms can be scheduled with provably small overheads in terms of cache
complexity on parallel machines with shared and distributed caches.