Low depth cache-oblivious algorithms
Low depth cache-oblivious algorithms
复制标题
DOI：
10.1145/1810479.1810519
复制
发表时间：
2010-06
影响因子：
0.5
通讯作者：
G. Blelloch;Phillip B. Gibbons;H. Simhadri
中科院分区：
文献类型：
--
作者：
G. Blelloch;Phillip B. Gibbons;H. Simhadri
在本文中，我们探讨了一个简单的和一般的方法来开发并行算法，导致良好的缓存复杂性的并行机与私人或共享缓存。该方法是设计嵌套并行算法，具有低的深度（跨度，关键路径长度）和自然顺序评估顺序具有低的高速缓存复杂度的高速缓存不经意模型。我们描述了几个高速缓存不经意的算法，最佳的工作，多对数深度，顺序缓存的复杂性，匹配最好的顺序算法，包括第一个这样的算法排序和稀疏矩阵向量乘矩阵良好的顶点分隔符。使用已知的映射，我们的研究结果导致低缓存复杂性的共享内存多处理器与一个单一的私人缓存或一个共享缓存的水平。我们将这些映射推广到私有或共享缓存的多级缓存层次结构，这意味着我们的算法在这种层次结构上也具有较低的缓存复杂度。在获得这些低并行高速缓存复杂性的关键因素是我们提出的算法的深度低。
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. 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. 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. 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 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. The key factor in obtaining these low parallel cache complexities is the low depth of the algorithms we propose.