聚合国内IT技术精华文章,分享IT技术精华,帮助IT从业人士成长

Feluca:以颜色为中心的两阶段GPU图着色算法

2022-01-06 10:45 浏览: 2848266 次 我要评论(0 条) 字号:

在GPU上实现着色算法存在着几个方面的挑战:一、迭代式着色方法中由于颜色冲突带来的长尾问题随着迭代轮次的增加变得越发严重;二、遍历式着色方法由于颜色之间的相互依赖导致算法并行化困难;三、在颜色队列的维护过程中,大量的原子操作极大地制约了GPU的性能。为了解决GPU上实现着色算法的上述问题,本文提出了一种两阶段的着色算法Feluca。Feluca融合了迭代式和扩展式着色方法的基本思想,首先采用迭代的方法对大部分顶点进行快速着色并监测算法执行过程中冲突顶点的占比,当冲突顶点的比例高于阈值时算法切换成遍历式的执行方式对剩余顶点进行着色,并对冲突顶点进行重着色。同时论文还提出了以下几种优化策略:(1)设计了一种环消除策略,将无向图转换成有向图,并规定图数据中边的方向只能从小顶点指向大顶点来消除环结构,从而减少环结构带来的局部死循环,进而加速了着色过程;(2)设计了一种自顶向下的颜色选择机制给活跃顶点分配适当的颜色值,尽可能减少着色数;(3)设计了一种以颜色为中心的线程管理机制来分配扩展式着色方法的线程分布,通过pipeline的方式组织处理不同颜色的线程组,提高扩展式着色方法的并行度。实验表明,相比于当前主流的GPU图着色算法,Feluca可以达到1.19-8.39倍加速。

该成果“Feluca: A Two-Stage Graph Coloring Algorithm with Color-centric Paradigm on GPU”,发表于IEEE Transactions on Parallel and Distributed Systems (TPDS)(vol. 32, no. 1, pp. 160-173, 1 Jan. 2021)。该期刊2020年的影响因子为2.687,是计算机系统领域的顶级期刊之一,是中国计算机学会(CCF)推荐的A类国际学术期刊。
  • 论文链接:

    https://ieeexplore.ieee.org/document/9162529


背景与动机

图着色算法是用颜色队列中的颜色值对给定图的顶点进行着色,每个顶点采用一种颜色进行着色并确保每条边的两个顶点的颜色不同。着色过程中所使用的总的颜色数记为|C|,所需要的最少颜色数记为X(G)大规模图上X(G)的求解是一个NP难问题,因此在实际求解过程中往往退而求其次,采用最优性约束的方法来寻找近似解。当前已有工作可在线性时间内求解给定图数据的近似解。但是,随着互联网的快速发展,现实世界中图的规模也在不断扩大,即使线性时间的算法也需要借助并行计算来进行加速才能满足实际应用对计算时间的要求。此外,近似求解的速度通常与它的求解质量矛盾。因此,如何设计一种高效的着色算法,能够在着色质量和着色速度之间取得平衡就显得尤为重要。

当前主流的图着色方法可分为迭代式和遍历式两种。遍历式着色方法的基本思想是遍历整个图结构,并逐一对顶点进行着色。贪心法就是最典型的遍历式着色方法之一。在遍历式着色方法中,已经被着色的顶点需要将其颜色发送到其相邻的顶点,邻居节点根据接收到的已经被着色顶点的消息从颜色队列中选择适合自己的颜色并着色。这种计算模式天然地与同步计算模型相吻合,因此,当前遍历式着色方法大都采用同步计算的执行方法,并且每一轮同步过程中线程只对活跃顶点进行处理。我们从基准测试实验中观察到,每个步骤中只有很少数量的活跃顶点严重拖慢了算法执行的时间。此外,由于邻居节点之间的颜色依赖,导致算法难以并行。

在迭代式着色方法中,所有的顶点在每一轮计算中都会获得一个颜色值。在这种计算模式下,被着色的顶点需要将自己的颜色值发送给邻居顶点进行比较,发生颜色冲突的顶点会在下一轮迭代中被重新着色。所有的顶点都是活跃顶点,算法的并行度可以极大提升。但是,算法执行过程中存在大量的颜色冲突,进而降低算法效率。另一方面,对冲突顶点的重着色会引入一定数量的新颜色,导致算法所使用的颜色数量急剧增加。图1展示了迭代式着色方法每一轮计算中被着色的顶点数以及冲突发生的情况。

本文旨在设计一种高效的并行着色算法,该算法在控制颜色数量的前提下能够大幅度提高着色速度


设计与实现

为了解决遍历着色方法和迭代着色方法难以平衡颜色数量和着色速度的问题,本文提出一种两阶段的图着色算法Feluca在第一阶段,Feluca采用迭代的思路对大部分顶点进行快速着色为了避免使用迭代式着色方法产生长尾现象,Feluca监测到一定数量的冲突顶点之后切换成遍历式的着色方法此外,Feluca还提出了以下几项优化方法,以进一步提高图着色性能。

本文设计了一种环消除策略以简化Feluca中颜色值的传播。在这一策略中Feluca首先将节点编号i>j的有向边<vi,vj>转换为<vj,vi>来消除图数据中的环结构,从而避免环结构带来的局部死循环。基于环消除技术,我们设计了一种自上而下的颜色选择方案,根据邻居顶点的颜色值从颜色阵列中顺序选择合适当前顶点的颜色。大多数现有的颜色选择方案需要大量的原子操作来确保算法的正确性。但是原子操作开销巨大,同时也严重限制了算法性能。本文提出的自顶向下的颜色选择方案从构建的DAG图的顶层(根)开始对顶点进行逐层着色,直到所有顶点完全着色。由于每一层级中往往有多个顶点,这些顶点可以由不同的线程并行着色。在本文所提出的自顶向下颜色选择方案中,我们采用颜色数组COLORS保存所有使用的颜色,固定长度的临时数组NeighborColors保存当前顶点的邻居使用的颜色。在本文的实现中,我们为NeighborColors数组分配两个字节,以存储邻居的最小和最大颜色(即具有最小和最大ID的颜色)。通过仅遍历COLORS数组,Feluca可以找到COLORS数组中当前顶点的候选颜色。当COLORS颜色分配失败时,算法引入一个新的颜色给当前顶点着色,并将新引入的颜色值存储在颜色数组的末尾。

在遍历式着色阶段,我们设计了一个以颜色为中心的线程管理机制来提高遍历式着色阶段的并行度。在这一阶段我们给每一种颜色分配一个线程块,然后查找出可以被每一种颜色着色的顶点,并对所有活跃顶点进行着色。在这种着色方式中,后续线程块只有获取前序线程块的计算结果之后才能继续执行。本文将不同的线程块按照流水线的方式进行组织,尽最大可能提高了算法的并行度。

假设Feluca第一阶段的执行时间为sr,第二阶段的执行时间为ss为Feluca转换时已经被着色顶点与图顶点数的比值,那么Feluca的计算时间可以用公式表示为  ,其中tstr分别为遍历式和迭代式着色方法中每一轮次的执行时间。
Feluca计算时间是的凸函数,因此存在使得Feluca的执行时间最短。由于第二阶段的遍历式着色方法所使用的颜色数远少于第一阶段的迭代式着色方法,因此,第二阶段遍历式着色方法的顶点越多,Feluca所使用的颜色数也越少。为了平衡颜色数量和着色时间,本文设=0为T的最优解,=5%表示第二阶段遍历式着色方法比第一阶段迭代式着色方法多着色5%的顶点,以此类推。Feluca在不同的转换点下对应的执行时间和颜色数如下表所示。
为了平衡着色时间和颜色数量,本文取=10%Feluca与当前已有工作的性能对比如下表所示。

详细内容参见:

Zhigao Zheng; Xuanhua Shi; Ligang He; Hai Jin; Shuo Wei; Hulin Dai; Xuan Peng, "Feluca: A Two-Stage Graph Coloring Algorithm With Color-Centric Paradigm on GPU," in IEEE Transactions on Parallel and Distributed Systems, vol. 32, no. 1, pp. 160-173, 1 Jan. 2021, doi: 10.1109/TPDS.2020.3014173.



网友评论已有0条评论, 我也要评论

发表评论

*

* (保密)

Ctrl+Enter 快捷回复