Multi-Jagged: A Scalable Parallel Spatial Partitioning Algorithm
Multi-Jagged: A Scalable Parallel Spatial Partitioning Algorithm
复制标题
多锯齿：一种可扩展的并行空间分区算法
DOI：
10.1109/tpds.2015.2412545
复制
发表时间：
2016
影响因子：
5.3
通讯作者：
Ümit V. Çatalyürek
中科院分区：
文献类型：
--
作者：
Mehmet Deveci;S. Rajamanickam;K. Devine;Ümit V. Çatalyürek
几何分区对于负载平衡动态应用程序是快速有效的，特别是那些需要数据的几何局部性的应用程序（粒子方法、崩溃模拟）。我们提出，据我们所知，第一个并行实现的多维锯齿几何分区。传统的递归坐标对分算法（RCB）是将垂直于最长维度的子域递归地对分，直到得到所需的零件数为止，而我们的算法是在每个维度上对给定数量的零件进行递归多分割。通过并发计算多条切线，并在计算分区时智能决定何时迁移数据，与有效的递归等分实现相比，我们最大限度地减少了数据移动。我们在真实和合成数据集上演示了该算法相对于Zoltan中RCB实现的可扩展性和质量。我们的实验表明，在不降低负载平衡的情况下，所提出的算法在运行时间方面的性能和可扩展性优于RCB。我们的实现在几秒钟内将240亿个点划分为65,536个部分，并且显示出接近完美的弱扩展到6K核。
Geometric partitioning is fast and effective for load-balancing dynamic applications, particularly those requiring geometric locality of data (particle methods, crash simulations). We present, to our knowledge, the first parallel implementation of a multidimensional-jagged geometric partitioner. In contrast to the traditional recursive coordinate bisection algorithm (RCB), which recursively bisects subdomains perpendicular to their longest dimension until the desired number of parts is obtained, our algorithm does recursive multi-section with a given number of parts in each dimension. By computing multiple cut lines concurrently and intelligently deciding when to migrate data while computing the partition, we minimize data movement compared to efficient implementations of recursive bisection. We demonstrate the algorithm's scalability and quality relative to the RCB implementation in Zoltan on both real and synthetic datasets. Our experiments show that the proposed algorithm performs and scales better than RCB in terms of run-time without degrading the load balance. Our implementation partitions 24 billion points into 65,536 parts within a few seconds and exhibits near perfect weak scaling up to 6K cores.