LOGO LOGO
博士生郑志高的论文被TPDS录用
时间:2020-08-17 08:34:19

近日,实验室博士生郑志高的论文被IEEE Transactions on Parallel and Distributed Systems (TPDS) 录用,论文题目为“Feluca: A Two-Stage Graph Coloring Algorithm with Color-centric Paradigm on GPU”。

现有的主流图着色算法可以被分为迭代型和扩展型两大类,迭代型着色算法具有速度快,但着色数过多的问题,扩展型着色算法能够有效降低着色数,但存在收敛速度慢的问题。论文首先分析了迭代型和扩展型着色算法的特点,结合GPU高度并行的特性,提出了一种两阶段的图着色算法Feluca。Feluca算法首先采用迭代的思路对大部分顶点进行着色,然后利用扩展型算法的思想,在对剩余顶点进行着色的同时,对着色结果进行修正,降低颜色数。

论文包含如下创新点:(1)提出了一种融合迭代型和扩展型两种着色思想的两阶段图着色算法。(2)设计了一种环消除策略,将无向图转换成有向图,并规定图数据中边的方向只能从小顶点指向大顶点来消除环结构,从而减少环结构带来的局部死循环,进而加速了着色过程。同时,论文还设计了一种自顶向下的图着色机制给活跃顶点分配适当的颜色值,尽可能减少着色数。(3)设计了一种以颜色为中心的着色机制来分配扩展型算法的线程分布,通过pipeline的方式组织处理不同颜色的线程组,提高扩展型算法的并行度。(4)通过在多个数据集上的广泛实验,Feluca算法在计算时间和颜色数两个方面均优于已有工作。此外,论文还验证了以颜色为中心的着色机制对整个算法的性能影响。

IEEE Transactions on Parallel and Distributed Systems期刊每月出版一期,每期录用论文20篇左右,今年的影响因子是2.6,主要关注并行与分布式架构、并行与分布式算法、并行与分布式计算应用、及并行与分布式系统软件等方面的研究。



(通讯员:郑志高)