Graduation-Project-final

Parallel graph coloring algorithm 优化的新的基于并行架构的图着色算法，解决了反复着色，并行度不够以及长尾的问题。首先，预处理图数据，将其变成只有小编号顶点指向大编号顶点的有向图，避免了反复着色，也确保了算法能在有限轮次后终止。此外，配合使用CSR和CSC的存储格式保存图数据，可以做到一定程度的连续访存，并减少修正工作一半的工作量。其次，着色过程采用无冲突的并行着色思路，每一轮分为着色和修正两个步骤，提高了并行度，并可以避免原子操作。最后，在未着色顶点数剩余极少时，避免多次迭代，将着色策略变成串行，解决长尾问题。将其与一种典型的以边为中心的的算法融合互补，形成的组合算法解决了各自的主要缺点。