Technical Report CMU-CS-TR-134, Computer Science Department, Carnegie Mellon University, 2009. Brief announcement: Low-depth cache oblivious sorting. Provably efficient scheduling for languages with fine-grained parallelism. Effectively sharing a cache among threads. Provably good multicore cache performance for divide-and-conquer algorithms. Models for parallel and hierarchical computation. Computing Research Repository (CoRR) abs/0705.1033, 2007. Optimal sparse matrix dense vector multiplication in the I/O-model. Thread scheduling for multiprogrammed multiprocessors. Parallel external memory graph algorithms. Fundamental parallel algorithms for private-cache chip multiprocessors. Sahni, editors, Handbook of Data Structures and Applications. Cache-oblivious priority queue and graph algorithm applications. on Programming Models for Massively Parallel Computers, 1993. Modeling parallel computers as memory hierarchies. The uniform memory hierarchy model of computation. Theory of Computing Systems, 35(3), 2002. The key factor in obtaining these low parallel cache complexities is the low depth of the algorithms we propose.

We generalize these mappings to multi-level cache hierarchies of private or shared caches, implying that our algorithms also have low cache complexities on such hierarchies. Using known mappings, our results lead to low cache complexities on shared-memory multiprocessors with a single level of private caches or a single shared cache. We describe several cache-oblivious algorithms with optimal work, polylogarithmic depth, and sequential cache complexities that match the best sequential algorithms, including the first such algorithms for sorting and for sparse-matrix vector multiply on matrices with good vertex separators. The approach is to design nested-parallel algorithms that have low depth (span, critical path length) and for which the natural sequential evaluation order has low cache complexity in the cache-oblivious model. In this paper we explore a simple and general approach for developing parallel algorithms that lead to good cache complexity on parallel machines with private or shared caches.

Lowest level private cache