一、目的及意义

当前，随着互联网的快速普及，社会的数字化变革以及经济的快速发展，表达数据关联性的图数据的规模正在呈爆发式增长。由于图计算能够用于分析数据之间的关联关系，因此其在互联网应用、科学计算、社会计算、商业计算等诸多领域得到应用广泛，已经成为大数据处理的主流模式之一。而图的染色算法便是其中的一种，其在时间规划调度，频道分配问题安全装箱问题等实际问题方面有着极为重要的作用，其中与图着色联系最紧密，实际应用最为广泛的即为寄存器分配技术。利用相交图（interference graph）来表示程序变量的生命期是否相交，将寄存器分配给变量的问题，可近似地看成是给相交图着色：相交图中，相交的节点不能着同一颜色；每一种颜色对应一个寄存器。Chaitin等人最早提出了基于图着色的寄存器分配方法其着色思路采用了Kempe的着色方法。而图平衡着色的意义在于均衡每一种颜色染色的顶点的数量，使得数量尽可能的平均，任务负载尽可能多的平衡，图平衡着色算法的效率的提升也会极大提升该算法在这些领域内的实际应用价值。

本课题旨在重新审视并行计算环境中均衡着色的问题，拟提出并设计一种基于并行计算架构的平衡图着色算法，在不增加颜色数的前提下保证各颜色块中顶点数量的均衡，帮助程序开发人员提高应用程序的并行性能。

二、国内外研究现况及发展趋势

图着色问题是一个典型的NP问题，即寻找一种染色方案使得途中相邻的顶点染色不同，在保证正确性的条件尽可能减少染色数目。在非并行情况下，经典的算法为按照顶点编号对顶点进行依次染色，对于无法进行下去的情况进行一定的回溯，能够进行优化就是进行一定的剪枝。

近年来，国内外许多学者提出各种求解图着色问题的算法，如隐式枚举算法，割平面算法等，这类精确算法在当图规模较小的时候效果较好，但是一旦问题规模变大，无法避免指数爆炸问题。除了精确算法，遗传算法，蚁群算法等也被用于求解图着色问题。然而，由于图着色问题具有指数级的解空间规模，无论是精确算法还是近似算法，都需要花费大量的时间进行计算，无法在让人满意的时间内求解出问题的解。

在当前图在现实生活中日益广泛，图的规模日益增大的趋势下，并行图着色算法的优势也会日益明显。而经典的图着色并行算法中，除了会有大图算法普遍具有的随机访存和负载不均衡的缺点外，还有需要记录中间状态，导致迭代过程中数据膨胀，而GPU储存空间有限的问题；其次是线程之间的不可见性，可能导致死循环。

传统的启发式（一个基于直观或经验构造的算法，在可接受的花费（指计算时间和空间）下给出待解决组合优化问题每一个实例的一个可行解，该可行解与最优解的偏离程度一般不能被预计。）着色方法旨在减少颜色的数量，因为该数量也对应于应用程序中迭代步骤的数量。但是，如果生成的颜色类存在明显的差异，则会导致计算负载不均、硬件资源的利用效率低下等问题。均匀着色是一种理论上的着色公式，它保证了颜色类之间的完美平衡，在实际应用中往往会对均匀着色进行一定的松弛处理，这种被松弛处理的均匀着色被称为平衡着色。

当前的发展趋势大致为：由于GPU内存有限，如何使用GPU处理更大规模的图是另一个主要的挑战。目前，支持GPU的云，GPU集群,CPU/GPU混合系统等具有较大的内存空间的方案，在各种应用中得到了广泛的应用。将图处理算法移植到这些系统中是大规模图形处理的一个有前途的研究方向。

三、目标及方案

对于实现该课题，预计步骤是先熟悉对应的基础知识，然后了解对应的编程算法，最后提出自己的想法并加以实现。而整体的预期目标为：

1. 了解GPU体系结构，开发环境的配置以及CUDA编程方法

2. 理解大规模图平衡着色算法

3. 掌握需求分析和系统设计方法

4. 掌握项目研发流程和规范，熟悉系统项目的研发生命周期，掌握开发的过程和方法

5. 设计并实现一种基于并行计算架构的平衡着色算法（基于GPU的平衡着色算法，并能照顾到GPU访存模式，尽可能充分利用GPU的计算能力）

预期目标中的前四点为基本的知识储备，具体实现只需要寻找和阅读对应的参考文献即可，而最重要的一点为设计并实现一种对应的算法，要求该算法相对于现有的工作有一定的效率提升。为了实现该目标，预计采取的步骤为：

1. 详细了解GPU的架构和在其上编程应注意到的特点，充分利用其能高性能并行计算等特点。

2. 理解对应的并行染色算法及相关的并行的图的算法，观察其改进的方向及具体实施的方案。

3. 整合现有思路，选取当前贴合与实际情况的可能的改进方向，并加以细化和修正，形成完整的思路。

4. 熟悉并行编程相关的编程语言和编程方式，实现对应思路并计算对应代码的效率。

当前欲实现的并行染色算法的大致流程为：串行描述为染色数目是作为输入给出。首先用第一种颜色将图中所有可以染第一种颜色的顶点进行染色（互不直接相连），然后将没染色的顶点的集合作为第二种颜色染色的输入，以此类推，直至染色完毕。如果颜色数目不够，不足以满足相邻点颜色互不相同的要求，则在最后一轮染色中，将所有的剩余未染色的结点都染上相同颜色。

而并行的思路为开启多个染色线程，同时对图进行染色（以颜色为中心）。其中的难点在于，整个染色过程应该是串行的，每一次染色都是以上一次染色后的子图作为输入的。第一个难点在于如何并行的实现这个过程，并保证点标注的正确性。第二个难点在于如何识别状态队列中的顶点应该被染的颜色和应该所属的线程。第三个难点在于在图的规模极其大时，如何尽可能的提高线程并行度和读取数据的连续性，及读取数据的利用率。

而当前解决办法的思路为：1.第一个难点，采用一个多个线程共用的记录顶点染色状态的状态数组，这样就可以同时进行染色操作。2.第二个难点，考虑串行中是先染颜色1再颜色2递推的，那么可以得出，颜色1的线程必定需要遍历所有顶点，颜色2的线程必定要遍历除了染色为1外的所有顶点，以此类推。且颜色2的线程不可在顶点未被颜色1的线程遍历前，确定将其染色为2。可考虑实现维护一个活跃队列，确定染颜色1的顶点的所有邻居作为颜色2的活跃队列中的点，以此类推。3。第三个难点在于如何设计图数据的存储方式和存储结构，使得可连续读取。其次可以在多个线程对点的染色完毕后，将修改邻居状态的操作合并，因为多个点的所有邻居必定有重复的，这样可以减少写数据的操作。

在具体实现时，还需要考虑内存读取，线程分配等具体的可能影响效率的问题，主体思路可以参考iBFS论文中共享队列中的实现方法，最好在有比较完善的思路后再开始着手代码。

在完成代码后，测试用图可以选取现实生活中的图的数据，比如facebook的社交网络图，也可以选取常用的图生成器Kronecker来自己生成数据，作为代码效率测试的基准图。以上两种方式生成的图都具有微型世界的特征——由于大多数顶点的出度数较小，占总边数的百分比较小，因此存在大量的有较多出度的顶点。

最终目标为，对以上思路进行分析比较，选取可行性较高的思路进行细化和具体实现，并确保算法的正确性。最后在对比现有算法时，有一定的效率提升。

四、课题研究进度安排

表一 课题研究进度安排表

五、主要参考文献

[1]. Hao Lu, Mahantesh Halappanavar, Daniel G. Chavarría-Miranda, Assefaw Hadish Gebremedhin, Ajay Panyala, Ananth Kalyanaraman: Algorithms for Balanced Graph Colorings with Applications in Parallel Computing. IEEE Trans. Parallel Distrib. Syst. 28(5): 1240-1256 (2017)

[2]. Hao Lu, Mahantesh Halappanavar, Daniel G. Chavarría-Miranda, Assefaw Hadish Gebremedhin, Ananth Kalyanaraman: Balanced Coloring for Parallel Computing Applications. IPDPS 2015: 7-16

[3]. Aijun Dong, Xin Zhang: Equitable coloring and equitable choosability of graphs with small maximum average degree. Discussiones Mathematicae Graph Theory 38(3): 829-839 (2018)

[4]. Hang Liu and H. Howie Huang. Enterprise:Breadth-first graph traversal on gpu servers. In International Conference for High Performance Computing, Networking, Storage and Analysis (SC), 2015.

[5]. Sudev Naduvath, K. P. Chithra, S. Satheesh, Johan Kok: On certain parameters of equitable coloring of graphs. Discrete Mathematics Algorithms and Applications 9(4): 1-11 (2017)

[6]. Graph500. http://www.graph500.org/.

[7]. R.M.R. Lewis. A guide to graph coloring: algorithms and applications. Springer. 2015

[8]. 邱明. 基于CUDA的图顶点着色问题的并行遗传算法研究[D].武汉科技大学,2015.