基于FPGA的图着色问题求解

作者：张益豪; 张子超; 刘小青; 冷煌; 王之元^*; 许进

来源：电子与信息学报, 2022, 44(09): 3328-3334.

• 图着色问题
• 回溯法
• FPGA

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

• 单位
  北京大学