基于FPGA的图着色问题求解

Solution of Graph Coloring Problem Based on FPGA

图着色问题是在满足相邻顶点不能分配相同颜色且颜色数最少的约束条件下,将图的顶点划分为不相交的集合,且每个集合中的顶点分配相同的颜色。由于图着色问题属于NP-完全问题,求解图着色问题的算法复杂度会随顶点个数的增加呈指数级增长。当顶点个数非常大时,通用处理器求解图着色问题的性能将会显著下降。因此,该文基于现场可编程逻辑门阵列(FPGA)实现求解图着色算法的专用硬件加速器。首先依据FPGA模块化的设计思路提出并实现了基于回溯法的图着色问题求解的硬件架构;其次分析了FPGA内部消耗资源与图着色顶点数之间的关系;最后利用通用异步收发传输器协议实现了通用处理器与FPGA的通信。实验结果表明,相比于在通用处理器上利用软件实现图着色算法,基于FPGA所实现的图着色算法运行时间减少了一个数量级。除此之外,FPGA内部消耗资源数与顶点个数呈线性关系,且每次迭代时FPGA运算所消耗的时间与顶点个数无关。

Graph coloring problem divides the vertices of the graph into disjoint sets and the vertices in each set are assigned by the same color under the constraints that adjacent vertices can not be assigned the same color and the number of colors is the smallest.Since graph coloring problem belongs to the class of NP-complete problems,the complexity for solving the graph coloring problem increases exponentially with the number of vertices.The performance of solving graph coloring problem by general-purpose processors decreases significantly when the number of vertices is large enough.This paper implements a dedicated hardware accelerator for solving graph coloring problem based on Field Programmable Gate Array(FPGA).Firstly,by utilizing the rule of FPGA modular design,the hardware architecture for solving graph coloring problem based on the backtracking is proposed and implemented.Secondly,the relationship between the resource consumption of FPGA and the number of vertices is analyzed.Finally,the general-purpose processor and FPGA can communicate through universal asynchronous transmitter-receiver protocol.The experimental results show that the running time of graph coloring algorithm based on FPGA is about an order of magnitude smaller than that of graph coloring algorithm based on software on general-purpose processors.Besides,the resource consumption of FPGA is linear with the number of vertices and the time consumption at each iteration is independent of the number of vertices.