Fine-grained dynamic load balancing in spatial join by work stealing on distributed memory
Fine-grained dynamic load balancing in spatial join by work stealing on distributed memory
复制标题
通过分布式内存上的工作窃取实现空间连接中的细粒度动态负载平衡
DOI：
10.1145/3557915.3560936
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Zhou, Hui
中科院分区：
文献类型：
--
作者：
Yang, Jie;Puri, Satish;Zhou, Hui
空间连接是组合空间数据的一种重要操作。并行化是提高空间连接性能的关键。然而，由于数据倾斜导致的负载不平衡限制了并行空间连接的可扩展性。有许多工作共享技术可以在并行环境中解决此问题。其中一种技术是使用数据和空间分区，然后在线程/进程之间调度分区，以最小化线程/进程之间的工作负载差异。然而，由于分区中不同输入几何对的连接代价不同，负载不平衡问题仍然存在，针对负载不平衡问题，设计了一个基于分布式存储环境的工作窃取空间连接系统(WSSJ-DM)。工作窃取是一种动态负载平衡方法，其中空闲的处理器从其他处理器窃取计算任务[5]。这是第一个使用工作窃取概念(而不是工作共享)在大型计算集群上并行化空间连接计算的工作。我们对系统在共享和分布式存储上的可扩展性进行了评估。我们的实验评估表明，窃取工作是一种有效的策略。在使用分区和未分区数据集的高性能计算环境中，我们比较了WSSJ-DM和空间连接的工作共享实现。使用静态和动态负载均衡方法进行比较。研究了内存亲和力对多核处理器空间连接涉及的工作窃取操作的影响.在一个集群(1260个CPU核)上，使用35个计算节点，WSSJ-DM在30秒内完成了对湖泊(84M个多边形)和公园(10M个多边形)的ST_Intersection.相比之下，实现工作共享Master-Worker只需160秒。
Spatial join is an important operation for combining spatial data. Parallelization is essential for improving spatial join performance. However, load imbalance due to data skew limits the scalability of parallel spatial join. There are many work sharing techniques to address this problem in a parallel environment. One of the techniques is to use data and space partitioning and then scheduling the partitions among threads/processes with the goal of minimizing workload differences across threads/processes. However, load imbalance still exists due to differences in join costs of different pairs of input geometries in the partitions.For the load imbalance problem, we have designed a work stealing spatial join system (WSSJ-DM) on a distributed memory environment. Work stealing is an approach for dynamic load balancing in which an idle processor steals computational tasks from other processors [5]. This is the first work that uses work stealing concept (instead of work sharing) to parallelize spatial join computation on a large compute cluster. We have evaluated the scalability of the system on shared and distributed memory. Our experimental evaluation shows that work stealing is an effective strategy. We compared WSSJ-DM with work sharing implementations of spatial join on a high performance computing environment using partitioned and un-partitioned datasets. Static and dynamic load balancing approaches were used for comparison. We study the effect of memory affinity in work stealing operations involved in spatial join on a multi-core processor.WSSJ-DM performed spatial join usingST_IntersectiononLakes(8.4M polygons) andParks(10M polygons) in 30 seconds using 35 compute nodes on a cluster (1260 CPU cores). A work sharing Master-Worker implementation took 160 seconds in contrast.
登录
查看更多内容
DOI：
10.1007/3-540-60159-7_13
发表时间：
1995-08
期刊：
--
影响因子：
--
作者：
S. Shekhar;S. Ravada;Vipin Kumar;Douglas Chubb;Greg Turner
通讯作者：
S. Shekhar;S. Ravada;Vipin Kumar;Douglas Chubb;Greg Turner
基于 MPI 的异构分布式系统空间矢量数据处理框架
DOI：
--
发表时间：
2016
期刊：
International Symposium on Computing and Networking - Across Practical Development and Theoretical Research
影响因子：
--
作者：
Kouichi Araki;Taiki Shimbo
通讯作者：
Taiki Shimbo
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：
10.1109/ccgrid54584.2022.00064
发表时间：
2022
期刊：
2022 22nd IEEE International Symposium on Cluster, Cloud and Internet Computing (CCGrid)
影响因子：
--
作者：
Anmol Paudel;S. Puri
通讯作者：
S. Puri
用于空间连接中负载平衡的高效并行和自适应分区
DOI：
--
发表时间：
2020
期刊：
34th IEEE International Parallel & Distributed Processing Symposium
影响因子：
--
作者：
Yang, Jie;Puri, Satish
通讯作者：
Puri, Satish