Effectively sharing a cache among threads
Effectively sharing a cache among threads
复制标题
DOI：
10.1145/1007912.1007948
复制
发表时间：
2004-06
期刊：
影响因子：
--
通讯作者：
G. Blelloch;Phillip B. Gibbons
中科院分区：
文献类型：
--
作者：
G. Blelloch;Phillip B. Gibbons
当使用p个处理器或线程以及大小为Cp的共享高速缓存时，我们将用于在具有高速缓存大小c1的单个处理器上运行计算的高速缓存未命中数量M1与用于相同计算的未命中总数MP进行比较。我们证明了对于任何计算，在适当的(贪婪)并行调度下，如果CP≥C1+PD，则MP≤M1。计算深度d是依赖关系的关键路径的长度。这给出了一个可能令人惊讶的结果，即对于足够并行的计算，共享高速缓存只需要大于单处理器高速缓存的附加大小，并为设计具有共享高速缓存的机器提供了一些理论依据。我们研究的并行调度是一种基于顺序调度的并行深度优先调度(PDF Scheduling)。这个时间表很贪婪，因此工作效率很高。我们的主要结果假设了理想的缓存模型，但我们也给出了其他更现实的缓存模型的结果。
We compare the number of cache misses M1 for running a computation on a single processor with cache size C1 to the total number of misses Mp for the same computation when using p processors or threads and a shared cache of size Cp. We show that for any computation, and with an appropriate (greedy) parallel schedule, if Cp ≥ C1 + pd then Mp ≤ M1. The depth d of the computation is the length of the critical path of dependences. This gives the perhaps surprising result that for sufficiently parallel computations the shared cache need only be an additive size larger than the single-processor cache, and gives some theoretical justification for designing machines with shared caches.We model a computation as a DAG and the sequential execution as a depth first schedule of the DAG. The parallel schedule we study is a parallel depth-first schedule (PDF schedule) based on the sequential one. The schedule is greedy and therefore work-efficient. Our main results assume the Ideal Cache model, but we also present results for other more realistic cache models.