基于并行架构的大规模图着色算法
完整资料进入【数字空间】查看——baidu搜索"writebug"
摘 要
随着当前信息时代的日益发展，数据量的逐渐增大，大规模图数据的处理在网页搜索应用，社交网络和交通网络等场景中作用也愈发明显。因此，大规模图着色的研究也开始成为高性能计算领域的热点。而通用GPU（Graphics Processing Unit）的发展使其作用逐渐广泛，用于图着色的加速也成了一种研究的趋势。但调研后，现有的较广泛的并行图着色均存在以下问题中的部分或全部：反复着色，在着色时，后续迭代轮次中顶点颜色会导致已着色顶点颜色出错，需要重新修改；并行度不够，每轮着色中，正确的着色顶点比例稀少；长尾问题，在着色最后，每轮着色顶点数大幅度减少；负载不均衡，每个线程运行时间开销相差过大，导致整体性能较差。
设计的新的基于并行架构的图着色算法，解决了反复着色，并行度不够以及长尾的问题。首先，预处理图数据，将其变成只有小编号顶点指向大编号顶点的有向图，避免了反复着色，也确保了算法能在有限轮次后终止。此外，配合使用CSR和CSC的存储格式保存图数据，可以做到一定程度的连续访存，并减少修正工作一半的工作量。其次，着色过程采用无冲突的并行着色思路，每一轮分为着色和修正两个步骤，提高了并行度，并可以避免原子操作。最后，在未着色顶点数剩余极少时，避免多次迭代，将着色策略变成串行，解决长尾问题。
本算法使用CUDA C语言编程设计完成，提供了针对不同的图数据的接口参数。通过在相同环境下针对普遍的大规模图数据进行的实验，结果表明，该算法相较于CPU下的贪心着色算法有1.51-125.81倍的性能提升，相较于JPL（Jones-Plassman-Luby）有8.37-71.07倍的性能提升。
关键词：图着色；图形处理器；并行运算技术；两阶段
一、绪 论
本章我们首先介绍了当前发展图着色算法的目的以及意义，介绍了国内外在图着色领域的相关研究工作，并对算法的主要研究内容及工作意义作了具体说明，最后简略介绍了论文的整体结构。
1.1 课题背景
当前，随着互联网的大规模普及，社会面向数字化的变迁以及经济的迅猛发展，表达数据之间关联性的图数据的规模正在呈指数级增长。由于图计算能够用于分析数据之间的关联关系，因此其在互联网应用、科学计算、社会计算、商业计算等诸多领域得到应用广泛，已经成为大数据处理的主流模式之一。而图的着色算法便是其中的一种，其在时间规划调度，频道分配问题安全装箱问题等实际问题方面有着极为重要的作用，其中与图着色联系最紧密，实际应用最为广泛的即为寄存器分配技术。比如，相交图（interference graph）是用来表示程序变量是否拥有相交的生命期的。而一个寄存器同时只能被一个变量使用，如果用颜色表示寄存器，用顶点表示变量，该问题可抽象成一个图着色问题。
研究表明，在众多的图着色算法中，启发式算法和基于贪婪法的算法能够获得较好的着色数。然而，基于贪婪法的图着色算法具有O(n^2)的时间复杂度。由于实际图的大小不断增长，即使是具有线性时间的算法也需要求助于并行计算来缩减实际的求解时间。
