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.