Accelerating Spatial Autocorrelation Computation with Parallelization, Vectorization and Memory Access Optimization: With a focus on rapid recalculation of COVID related spatial statistics for faster geospatial analysis and response
Accelerating Spatial Autocorrelation Computation with Parallelization, Vectorization and Memory Access Optimization: With a focus on rapid recalculation of COVID related spatial statistics for faster geospatial analysis and response
复制标题
通过并行化、矢量化和内存访问优化加速空间自相关计算：重点是快速重新计算与新冠病毒相关的空间统计数据，以实现更快的地理空间分析和响应
DOI：
10.1109/ccgrid54584.2022.00064
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
S. Puri
中科院分区：
文献类型：
--
作者：
Anmol Paudel;S. Puri
地理信息系统处理空间数据及其分析。空间数据包含许多具有位置信息的属性。空间自相关是空间分析中的一个基本概念。这表明相似的物体在地理空间上倾向于聚集。热点是自相关的一个例子，是统计上显著的空间数据集群。其他自相关措施，如莫兰的我被用来量化空间依赖。大规模空间自相关方法是计算密集型的。在最近的COVID-19大流行时期，热点检测和分析的快速方法至关重要。因此，我们开发了异构CPU和GPU环境上的并行化方法。据我们所知，这是第一个基于GPU和SIMD的自相关内核设计和实现。文献中的早期方法介绍了基于聚类和基于Map Reduce的并行化。我们已经使用Intrinsics在x86 CPU架构上开发SIMD并行性。我们使用MPI图形拓扑来最小化进程间的通信.与基准顺序实现相比，我们的CPU/GPU优化基准在8 GPU设置下获得了高达750倍的相对加速。与在单个计算节点上使用OpenMP + R-tree数据结构的最佳实现相比，我们的加速热点基准测试获得了25倍的加速比。对于真实的世界美国县和COVID数据演变计算超过500天，我们获得了高达110倍的加速，将时间从33分钟减少到0.3分钟。
Geographic information systems deal with spatial data and its analysis. Spatial data contains many attributes with location information. Spatial autocorrelation is a fundamental concept in spatial analysis. It suggests that similar objects tend to cluster in geographic space. Hotspots, an example of autocorrelation, are statistically significant clusters of spatial data. Other autocorrelation measures like Moran's I are used to quantify spatial dependence. Large scale spatial autocorrelation methods are compute-intensive. Fast methods for hotspots detection and analysis are crucial in recent times of COVID-19 pandemic. Therefore, we have developed parallelization methods on heterogeneous CPU and GPU environments. To the best of our knowledge, this is the first GPU and SIMD-based design and implementation of autocorrelation kernels. Earlier methods in literature intro-duced cluster-based and Map Reduce-based parallelization. We have used Intrinsics to exploit SIMD parallelism on x86 CPU architecture. We have used MPI Graph Topology to minimize inter- process communication. Our benchmarks for CPU/GPU optimizations gain upto 750X relative speedup with a 8 GPU setup when compared to baseline sequential implementation. Compared to the best implementation using OpenMP + R-tree data structure on a single compute node, our accelerated hotspots benchmark gains a 25X speedup. For real world US counties and COVID data evolution calculated over 500 days, we gain upto 110X speedup reducing time from 33 minutes to 0.3 minutes.
登录
查看更多内容
DOI：
10.1109/compsac.2019.00136
发表时间：
2019-07
期刊：
2019 IEEE 43rd Annual Computer Software and Applications Conference (COMPSAC)
影响因子：
--
作者：
Anmol Paudel;Jie Yang;S. Puri
通讯作者：
Anmol Paudel;Jie Yang;S. Puri
DOI：
10.1109/hipc.2019.00027
发表时间：
2019-12
期刊：
2019 IEEE 26th International Conference on High Performance Computing, Data, and Analytics (HiPC)
影响因子：
--
作者：
Yiming Liu;Jie Yang;S. Puri
通讯作者：
Yiming Liu;Jie Yang;S. Puri
用于空间连接中负载平衡的高效并行和自适应分区
DOI：
--
发表时间：
2020
期刊：
34th IEEE International Parallel & Distributed Processing Symposium
影响因子：
--
作者：
Yang, Jie;Puri, Satish
通讯作者：
Puri, Satish
HPC 平台上的空间数据分解和负载均衡
DOI：
10.1145/3332186.3333266
发表时间：
2019
期刊：
Proceedings of the Practice and Experience in Advanced Research Computing on Rise of the Machines (learning
影响因子：
--
作者：
Yang, Jie;Paudel, Anmol;Puri, Satish
通讯作者：
Puri, Satish