Parallel Write-Efficient Algorithms and Data Structures for Computational Geometry
Parallel Write-Efficient Algorithms and Data Structures for Computational Geometry
复制标题
DOI：
10.1145/3210377.3210380
复制
发表时间：
2018-05
期刊：
影响因子：
--
通讯作者：
G. Blelloch;Yan Gu;Yihan Sun;Julian Shun
中科院分区：
文献类型：
--
作者：
G. Blelloch;Yan Gu;Yihan Sun;Julian Shun
在本文中，我们设计了平行的写入几何算法，这些算法的执行方式比标准算法少于同一问题的标准算法。在能量和延迟方面，我们设计了用于平面三角剖分，K -D树以及静态和动态的增强树的算法。有一个很小的对称记忆，读取和写入是单位成本以及一个大的不对称记忆，其中写入为$Ømega$ $ $倍，在设计这些算法时，我们介绍了几种用于获得写入效率的技术，前缀加倍和α标记，我们认为这对于设计其他平行的写入算法将很有用。
In this paper, we design parallel write-efficient geometric algorithms that perform asymptotically fewer writes than standard algorithms for the same problem. This is motivated by emerging non-volatile memory technologies with read performance being close to that of random access memory but writes being significantly more expensive in terms of energy and latency. We design algorithms for planar Delaunay triangulation, k -d trees, and static and dynamic augmented trees. Our algorithms are designed in the recently introduced Asymmetric Nested-Parallel Model, which captures the parallel setting in which there is a small symmetric memory where reads and writes are unit cost as well as a large asymmetric memory where writes are $ømega$ times more expensive than reads. In designing these algorithms, we introduce several techniques for obtaining write-efficiency, including DAG tracing, prefix doubling, and α-labeling, which we believe will be useful for designing other parallel write-efficient algorithms.