Parallelization of a regionalization heuristic in distributed computing platforms – a case study of parallel-p-compact-regions problem

Abstract

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.

Keywords:

• CyberGIS
• cyberinfrastructure
• heuristic
• performance
• spatial optimization

Notes

1. Utilizing Dell Precision T3400 running 64-bit Windows XP operating system with a 2.99 GHz Intel Core 2 Extreme processor and 8 GB of RAM.

2. A minima or maxima within a local neighborhood from which the algorithm may or may not be able to escape, that is, a sub-optimal solution that is erroneously computed to be optimal.

3. A marker value entered into a processing queue, or a message passed from a managing process that alerts all worker process that (1) the queue is empty and (2) all workers must terminate.

4. The sample clustered data, regionalization results, and performance test results will be provided upon request.

Additional information

Funding

This work was supported by the National Institutes of Health [grant number R37AG009253]; and the Yale University FAS Imaging Fund.