Provably good multicore cache performance for divide-and-conquer algorithms

This paper presents a multicore-cache model that reflects the reality that multicore processors have both per-processor private (L ₁) caches and a large shared (L ₂) cache on chip. We consider a broad class of parallel divide-andconquer algorithms and present a new on-line scheduler, CONTROLLED-PDF, that is competitive with the standard sequential scheduler in the following sense. Given any dynamically unfolding computation DAG from this class of algorithms, the cache complexity on the multicore-cache model under our new scheduler is within a constant factor of the sequential cache complexity for both L ₁ and L ₂, while the time complexity is within a constant factor of the sequential time complexity divided by the number of processors p. These are the first such asymptoticallyoptimal results for any multicore model. Finally, we show that a separator-based algorithm for sparse-matrix-densevector-multiply achieves provably good cache performance in the multicore-cache model, as well as in the well-studied sequential cache-oblivious model.