Parallelization of a regionalization heuristic in distributed computing platforms – a case study of parallel-p-compact-regions problem
Parallelization of a regionalization heuristic in distributed computing platforms – a case study of parallel-p-compact-regions problem
复制标题
分布式计算平台中区域化启发式的并行化——并行 p 紧区域问题的案例研究
DOI：
10.1080/13658816.2014.987287
复制
发表时间：
2015
影响因子：
5.7
通讯作者：
L. Anselin
中科院分区：
文献类型：
--
作者：
J. Laura;Wenwen Li;S. Rey;L. Anselin
在本文中，我们报告的努力，以开发一个并行实现的p-紧凑的区域化问题，适用于多核桌面和高性能计算环境。数据聚合的区域化是许多空间分析工作流的关键组成部分，已知这些工作流是NP困难的。我们利用低通信成本的并行实现技术，提供了一个基准更复杂的实现该算法。利用基于存储器的随机贪婪和边缘重新分配（MERGE）算法的初始化阶段和利用模拟退火的局部搜索阶段都分布在可用的计算核心上。我们的研究结果表明，所提出的并行化策略是能够有效地解决紧凑驱动的区域化问题的效率和效果。我们希望这项工作能够推进CyberGIS的研究，将其应用领域扩展到区域化世界，并提出这种并行化策略，有效地解决大型区域化问题，为空间分析社区做出贡献。
In this paper, we report efforts to develop a parallel implementation of the p-compact regionalization problem suitable for multi-core desktop and high-performance computing environments. Regionalization for data aggregation is a key component of many spatial analytical workflows that are known to be NP-Hard. We utilize a low communication cost parallel implementation technique that provides a benchmark for more complex implementations of this algorithm. Both the initialization phase, utilizing a Memory-based Randomized Greedy and Edge Reassignment (MERGE) algorithm, and the local search phase, utilizing Simulated Annealing, are distributed over available compute cores. Our results suggest that the proposed parallelization strategy is capable of solving the compactness-driven regionalization problem both efficiently and effectively. We expect this work to advance CyberGIS research by extending its application areas into the regionalization world and to make a contribution to the spatial analysis community by proposing this parallelization strategy to solve large regionalization problems efficiently.