Parallel Vertex Color Update on Large Dynamic Networks
Parallel Vertex Color Update on Large Dynamic Networks
复制标题
DOI：
10.1109/hipc56025.2022.00027
复制
发表时间：
2022-12
期刊：
影响因子：
--
通讯作者：
Arindam Khanda;S. Bhowmick;Xin Liang;Sajal K. Das
中科院分区：
文献类型：
--
作者：
Arindam Khanda;S. Bhowmick;Xin Liang;Sajal K. Das
我们提出了第一个基于GPU的并行算法，以有效地更新大型动态网络上的顶点着色。对于单个GPU，我们引入了松散维护的顶点颜色更新的概念，减少了计算和内存需求。对于多个GPU，在分布式环境中，我们提出了基于优先级的顶点排序，以减少通信时间。我们证明了我们的算法的正确性，并通过实验证明，对于单个GPU上超过1600万个顶点和超过1.34亿条边的图形，我们的动态算法比静态图形上最先进的算法快20倍。对于具有超过1.3亿个顶点和超过2.6亿条边的较大图形，我们使用8个GPU的分布式实现在160毫秒内生成更新的颜色分配。在所有情况下，所提出的并行算法产生可比或更少的颜色比国家的最先进的算法。
We present the first GPU-based parallel algorithm to efficiently update vertex coloring on large dynamic networks. For single GPU, we introduce the concept of loosely maintained vertex color update that reduces computation and memory requirements. For multiple GPUs, in distributed environments, we propose priority-based ordering of vertices to reduce the communication time. We prove the correctness of our algorithms and experimentally demonstrate that for graphs of over 16 million vertices and over 134 million edges on a single GPU, our dynamic algorithm is as much as 20x faster than state-of-the-art algorithm on static graphs. For larger graphs with over 130 million vertices and over 260 million edges, our distributed implementation with 8 GPUs produces updated color assignments within 160 milliseconds. In all cases, the proposed parallel algorithms produce comparable or fewer colors than state-of-the-art algorithms.