Parallel Algorithms for Asymmetric Read-Write Costs
Parallel Algorithms for Asymmetric Read-Write Costs
复制标题
DOI：
10.1145/2935764.2935767
复制
发表时间：
2016-07
期刊：
影响因子：
--
通讯作者：
N. Ben-David;G. Blelloch;Jeremy T. Fineman;Phillip B. Gibbons;Yan Gu;Charles McGuffey;Julian Shun
中科院分区：
文献类型：
--
作者：
N. Ben-David;G. Blelloch;Jeremy T. Fineman;Phillip B. Gibbons;Yan Gu;Charles McGuffey;Julian Shun
由于新兴存储技术中写入成本明显高于读取成本，我们考虑在这种非对称读写成本下进行并行算法设计，目的是在保持工作效率和低跨度的同时减少写入次数。我们提出了一种嵌套并行计算模型，它结合了（i）具有对称读写成本的每个任务小的栈分配内存和（ii）具有非对称读写成本的无界堆分配共享内存，并展示了在工作窃取调度器下该模型中的成本如何有效地映射到一个更具体的机器模型上。我们使用新模型为一些基本问题（如归约、列表收缩、树收缩、广度优先搜索、有序过滤器和平面凸包）设计了减少写入、工作高效、低跨度的并行算法。对于后两个问题，我们的算法是输出敏感的，即工作和写入次数随着输出大小而减少。我们还提出了一种减少写入、低跨度的最小生成树算法，该算法几乎是工作高效的（与逆阿克曼函数有偏差）。我们的算法揭示了几种有趣的技术，可在不渐近增加共享内存读取次数的情况下显著减少并行算法中的共享内存写入。
Motivated by the significantly higher cost of writing than reading in emerging memory technologies, we consider parallel algorithm design under such asymmetric read-write costs, with the goal of reducing the number of writes while preserving work-efficiency and low span. We present a nested-parallel model of computation that combines (i) small per-task stack-allocated memories with symmetric read-write costs and (ii) an unbounded heap-allocated shared memory with asymmetric read-write costs, and show how the costs in the model map efficiently onto a more concrete machine model under a work-stealing scheduler. We use the new model to design reduced write, work-efficient, low span parallel algorithms for a number of fundamental problems such as reduce, list contraction, tree contraction, breadth-first search, ordered filter, and planar convex hull. For the latter two problems, our algorithms are output-sensitive in that the work and number of writes decrease with the output size. We also present a reduced write, low span minimum spanning tree algorithm that is nearly work-efficient (off by the inverse Ackermann function). Our algorithms reveal several interesting techniques for significantly reducing shared memory writes in parallel algorithms without asymptotically increasing the number of shared memory reads.