基于FPGA的图着色问题求解

作     者：张益豪 张子超 刘小青 冷煌 王之元 许进 ZHANG Yihao;ZHANG Zichao;LIU Xiaoqing;LENG Huang;WANG Zhiyuan;XU Jin

作者机构：北京大学信息科学技术学院北京100871 北京大学高可信软件技术教育部重点实验室北京100871 国防科技创新研究院人工智能研究中心北京100073 

基　　金：国家重点研发计划(2019YFA0706401) 国家自然科学基金(61632002,61872166,61902005,62002002) 

出 版 物：《电子与信息学报》 (Journal of Electronics & Information Technology)

年 卷 期：2022年第44卷第9期

页      码：3328-3334页

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

主 题 词：图着色问题 回溯法 FPGA 

学科分类：0808[工学-自动化类] 07[理学] 070104[070104] 0701[理学-数学类] 

核心收录：

D　O　I：10.11999/JEIT210646

馆 藏 号：203114451...