Improving the Speed and Quality of Parallel Graph Coloring
Improving the Speed and Quality of Parallel Graph Coloring
复制标题
DOI：
10.1145/3543545
复制
发表时间：
2022-07
影响因子：
1.6
通讯作者：
Ghadeer Alabandi;Martin Burtscher
中科院分区：
文献类型：
--
作者：
Ghadeer Alabandi;Martin Burtscher
图着色为图的每个顶点指定一种颜色，这样相邻的两个顶点都不会获得相同的颜色。它是许多应用程序中的关键构建块。在实践中，通常首选需要较少不同颜色且计算速度较快的解决方案。存在各种着色试探法，它们提供了不同的质量和速度权衡。最高质量的启发式方法往往很慢。为了提高性能，已经提出了几种并行实现。本文描述了广泛使用的LDF启发式算法的两个改进。首先，我们提出了一种“捷径”方法，通过非投机性地破坏数据依赖来提高并行度。其次，我们提出了“色彩还原”技术来提高LDF的解决方案。在来自不同领域的18个图形上，捷径方法的平均并行度提高了2.5倍，颜色约简技术将结果质量提高了20%。我们在Titan V上运行的确定性CUDA实现平均速度快2.9倍，并且使用的颜色与文献中最好的GPU代码一样少或更少。
Graph coloring assigns a color to each vertex of a graph such that no two adjacent vertices get the same color. It is a key building block in many applications. In practice, solutions that require fewer distinct colors and that can be computed faster are typically preferred. Various coloring heuristics exist that provide different quality versus speed tradeoffs. The highest-quality heuristics tend to be slow. To improve performance, several parallel implementations have been proposed. This paper describes two improvements of the widely used LDF heuristic. First, we present a “shortcutting” approach to increase the parallelism by non-speculatively breaking data dependencies. Second, we present “color reduction” techniques to boost the solution of LDF. On 18 graphs from various domains, the shortcutting approach yields 2.5 times more parallelism in the mean, and the color-reduction techniques improve the result quality by up to 20%. Our deterministic CUDA implementation running on a Titan V is 2.9 times faster in the mean and uses as few or fewer colors as the best GPU codes from the literature.