Efficient Scheduling for Parallel Memory Hierarchies
parameters) and analyzed using a single level of cache with parameters $Z$ (cache size) and $L$ (cache line size), and a parameter $\alpha$ specifying the computation's parallelism (for input size $n$, $n^{\alpha}$ represents the number of processors that can be effectively used). For several fundamental algorithms, this cache cost in the parallel ideal cache model is optimal, matching the sequential bounds, with a parallelism $\alpha\rightarrow 1$.