期刊
PARALLEL COMPUTING
卷 115, 期 -, 页码 -出版社
ELSEVIER
DOI: 10.1016/j.parco.2023.102995
关键词
Computational geometry; Voronoi tessellation; Parallel algorithm; Distributed-memory
This paper proposes a scalable parallel algorithm for constructing 3D Voronoi tessellations. The algorithm evenly distributes input particles between blocks using kd-tree decomposition to construct the correct global Voronoi topology. Experimental results demonstrate the high efficiency of the algorithm on large datasets.
The Voronoi tessellation is a fundamental geometric data structure which has numerous applications in various scientific and technological fields. For large particle datasets, computing Voronoi tessellations must be conducted in parallel on a distributed-memory supercomputer in order to satisfy time and memory-size constraints. However, due to load balance and communication, the parallelization of the Voronoi tessellation renders a challenge. In this paper, we present a scalable parallel algorithm for constructing 3D Voronoi tessel-lations, which evenly distributes the input particles between blocks through kd-tree decomposition. In order to construct the correct global Voronoi topology, we investigate both parametric and non-parametric methods for particle communication among the blocks of a spatial decomposition. The algorithm is implemented exploiting process-level and thread-level parallelization and can be used in a diverse architectural landscape. Using datasets containing up to 330 million particles, we show that our algorithm achieves parallel efficiency up to 57% using 4096 cores on a distributed-memory computer. Moreover, we compare our algorithm with previous attempts to parallelize Voronoi tessellations showing encouraging improvements in terms of computation time.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据