A Synchronization-Avoiding Distance-1 Grundy Coloring Algorithm for Power-Law Graphs
A Synchronization-Avoiding Distance-1 Grundy Coloring Algorithm for Power-Law Graphs
复制标题
DOI：
10.1109/pact.2019.00040
复制
发表时间：
2019-09
期刊：
影响因子：
--
通讯作者：
J. Firoz;Marcin Zalewski;A. Lumsdaine
中科院分区：
文献类型：
--
作者：
J. Firoz;Marcin Zalewski;A. Lumsdaine
在本文中，我们提出了一种分布式，无序的，标签的距离-1 grundy（顶点）着色算法，即分布式控制（DC）着色算法。我们的算法消除了对以顶点为中心的屏障和颜色改进的全局同步的需求，仅依靠原子操作和局部终止检测来更新顶点颜色。 DC乐观地进行，随着算法的进展，校正颜色异步并取决于任务的本地排序，以最大程度地减少次优工作的执行。我们实现了DC着色算法和著名的Jones-Plassmann算法，并将其性能与4种不同类型的标准RMAT图和真实图形进行比较。我们表明，消除了以全球和顶点为中心的障碍的等待时间，并将这次投资于本地订购，从而改善了具有突出的幂律特征和密集互连的本地子图的图表的缩放。
In this paper, we propose a distributed, unordered, label-correcting distance-1 Grundy (vertex) coloring algorithm, namely, Distributed Control (DC) coloring algorithm. Our algorithm eliminates the need for vertex-centric barriers and global synchronization for color refinement, relying only on atomic operations and local termination detection to update vertex color. DC proceeds optimistically, correcting the colors asynchronously as the algorithm progresses and depends on local ordering of tasks to minimize the execution of sub-optimal work. We implement our DC coloring algorithm and the well-known Jones-Plassmann algorithm and compare their performance with 4 different types of standard RMAT graphs and real-world graphs. We show that the elimination of waiting time of global and vertex-centric barriers and investing this time for local ordering leads to improved scaling for graphs with prominent power-law characteristics and densely interconnected local subgraphs.