• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Parallel and Distributed Systems, IEEE Transactions on >Multi-Jagged: A Scalable Parallel Spatial Partitioning Algorithm
【24h】

Multi-Jagged: A Scalable Parallel Spatial Partitioning Algorithm

机译：多锯齿：一种可扩展的并行空间分区算法

获取原文
获取原文并翻译 | 示例
       
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

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.
机译：几何分区对于负载平衡动态应用程序是快速而有效的，尤其是那些需要数据具有几何局部性的应用程序（粒子方法，崩溃模拟）。据我们所知，我们提出了多维锯齿形几何分区器的第一个并行实现。与传统的递归坐标对分算法（RCB）递归地将垂直于其最长维度的子域一分为二，直到获得所需的零件数量，我们的算法会在每个维中使用给定数量的零件进行递归多部分划分。通过同时计算多条切割线并智能地确定在计算分区时何时迁移数据，与递归二等分的有效实现相比，我们最大程度地减少了数据移动。我们在实数据集和综合数据集上都证明了算法相对于Zoltan中RCB实施的可扩展性和质量。我们的实验表明，在不降低负载平衡的情况下，所提算法在运行时方面的性能和扩展性均优于RCB。我们的实现在几秒钟​​内将240亿个点划分为65,536个部分，并展现出近乎完美的弱扩展性，扩展到6K内核。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号