高级搜索

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

基于FPGA的图着色问题求解

张益豪 张子超 刘小青 冷煌 王之元 许进

张益豪, 张子超, 刘小青, 冷煌, 王之元, 许进. 基于FPGA的图着色问题求解[J]. 电子与信息学报, 2022, 44(9): 3328-3334. doi: 10.11999/JEIT210646
引用本文: 张益豪, 张子超, 刘小青, 冷煌, 王之元, 许进. 基于FPGA的图着色问题求解[J]. 电子与信息学报, 2022, 44(9): 3328-3334. doi: 10.11999/JEIT210646
ZHANG Yihao, ZHANG Zichao, LIU Xiaoqing, LENG Huang, WANG Zhiyuan, XU Jin. Solution of Graph Coloring Problem Based on FPGA[J]. Journal of Electronics & Information Technology, 2022, 44(9): 3328-3334. doi: 10.11999/JEIT210646
Citation: ZHANG Yihao, ZHANG Zichao, LIU Xiaoqing, LENG Huang, WANG Zhiyuan, XU Jin. Solution of Graph Coloring Problem Based on FPGA[J]. Journal of Electronics & Information Technology, 2022, 44(9): 3328-3334. doi: 10.11999/JEIT210646

基于FPGA的图着色问题求解

doi: 10.11999/JEIT210646
基金项目: 国家重点研发计划(2019YFA0706401),国家自然科学基金(61632002, 61872166, 61902005, 62002002)
详细信息
    作者简介:

    张益豪:男,博士,研究方向为信号处理、非凸优化、组合优化

    张子超:男,博士生,研究方向为社交网络、图神经网络与生物信息网络等

    刘小青:女,特聘副研究员,研究方向为图论与组合优化、新型计算

    冷煌:男,特聘副研究员,研究方向为新型计算、生物计算、组合优化

    王之元:女,副研究员,研究方向为智能模型、智能算法

    许进:男,教授,研究方向为图论与组合优化、生物计算机、社交网络与信息安全等

    通讯作者:

    王之元 alice_zyw@foxmail.com

  • 中图分类号: O157.6

Solution of Graph Coloring Problem Based on FPGA

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

    图  2  四顶点平面图的着色方案

    图  3  回溯法算法流程图

    图  4  基于FPGA的图着色实现方案

    图  5  顶点着色方案验证的功能仿真

    图  6  12顶点图的邻接矩阵

    表  1  FPGA资源消耗

    图的顶点个数
    12163264128256512
    LE4995477171045170029975580
    寄存器262323439667111920193815
    下载: 导出CSV
  • [1] GUO Jianding. Theoretical research on graph coloring: Application to resource allocation in device-to-device 4G radio system (LTE)[D]. [Ph. D. dissertation], Université Bourgogne Franche-Comté, 2018.
    [2] ELUMALAI A. Graph theory applications in computer science and engineering[J]. Malaya Journal of Matematik, 2020, S(2): 4025–4027. doi: 10.26637/MJM0S20/1043
    [3] PODDAR N and MONDAL B. An instruction on course timetable scheduling applying graph coloring approach[J]. International Journal of Recent Scientific Research, 2018, 9(2): 23939–23945. doi: 10.24327/ijrsr.2018.0902.1567
    [4] DE LIMA A M and CARMO R. Exact algorithms for the graph coloring problem[J]. Revista de Informática Teórica e Aplicada, 2018, 25(4): 57–73. doi: 10.22456/2175-2745.80721
    [5] VENKATASUBRAMANIAN M. Failure evasion: Statistically solving the NP complete problem of testing difficult-to-detect faults[D]. [Ph. D. dissertation], Auburn University, 2016.
    [6] LAWLER E L. A note on the complexity of the chromatic number problem[J]. Information Processing Letter, 1976, 5(3): 66–67. doi: 10.1016/0020-0190(76)90065-X
    [7] EPPSTEIN D. Small maximal independent sets and faster exact graph coloring[J]. Journal of Graph Algorithms and Applications, 2003, 7(2): 131–140. doi: 10.7155/jgaa.00064
    [8] BYSKOV J M. Chromatic number in time O(2.4023n): Using maximal independent sets[R]. BRICS Report Series RS-02-45, 2002.
    [9] BRÉLAZ D. New methods to color the vertices of a graph[J]. Communications of the ACM, 1979, 22(4): 251–256. doi: 10.1145/359094.359101
    [10] MEHROTRA A and TRICK M A. A column generation approach for graph coloring[J]. Informs Journal on Computing, 1996, 8(4): 344–354. doi: 10.1287/ijoc.8.4.344
    [11] MARAPPAN R and SETHUMADHAVAN G. Complexity analysis and stochastic convergence of some well-known evolutionary operators for solving graph coloring problem[J]. Mathematics, 2020, 8(3): 303. doi: 10.3390/math8030303
    [12] GUI Chuangyi, ZHENG Long, HE Bingsheng, et al. A survey on graph processing accelerators: Challenges and opportunities[J]. Journal of Computer Science and Technology, 2019, 34(2): 339–371. doi: 10.1007/s11390-019-1914-z
    [13] BROWN S. FPGA architectural research: A survey[J]. IEEE Design & Test of Computers, 1996, 13(4): 9–15. doi: 10.1109/54.544531
    [14] CHINNERY D and KEUTZER K. Closing the Gap Between ASIC & Custom: Tools and Techniques for High-Performance ASIC Design[M]. Boston, USA: Springer, 2002: 1–414.
    [15] BESTA M, STANOJEVIC D, DE FINE LICHT J, et al. Graph processing on FPGAs: Taxonomy, survey, challenges[EB/OL]. https://arxiv.org/pdf/1903.06697.pdf, 2021.
    [16] 许进. 极大平面图理论(上册: 结构-构造-着色)[M]. 北京: 科学出版社, 2019.

    XU Jin. Theory of Maximal Planar Graph (Volume One: Structure-Construction-Colorings)[M]. Beijing: Science Press, 2019.
    [17] FAZAKAS A, NEAG M, and FESTILA L. Block RAM versus distributed RAM implementation of SVM Classifier on FPGA[C]. Proceedings of 2006 International Conference on Applied Electronics, Pilsen, Czech Republic, 2006: 43–46.
    [18] JUNGK B and STÖTTINGER M. Serialized lightweight SHA-3 FPGA implementations[J]. Microprocessors and Microsystems, 2019, 71: 102857. doi: 10.1016/j.micpro.2019.102857
    [19] CLIFFORD W. Introduction to FPGA acceleration[EB/OL]. https://www.stemmer-imaging.com/media/uploads/websites/documents-/tech-tips/en_GB-TechTip-_Intoduction-to-FPGA-acceleration-20110211.pdf, 2021.
    [20] TRIMBERGER S, ROWSON J, LANG C, et al. A structured design methodology and associated software tools[J]. IEEE Transactions on Circuits and Systems, 1981, 28(7): 618–634. doi: 10.1109/TCS.1981.1085035
    [21] LEWIS D, AHMED E, BAECKLER G, et al. The stratix II logic and routing architecture[C]. Proceedings of the 2005 ACM/SIGDA 13th International Symposium on Field-Programmable Gate Arrays, Monterey, USA, 2005: 14–20.
    [22] Intel stratix 10 GX/SX product table[EB/OL]. https://www.intel.com/content/dam/www/programmable/us/en/pdfs/literature/pt/stratix-10-product-table.pdf, 2021.
  • 加载中
图(6) / 表(1)
计量
  • 文章访问数:  784
  • HTML全文浏览量:  552
  • PDF下载量:  139
  • 被引次数: 0
出版历程
  • 收稿日期:  2021-06-25
  • 修回日期:  2022-02-28
  • 录用日期:  2022-01-20
  • 网络出版日期:  2022-02-19
  • 刊出日期:  2022-09-19

目录

    /

    返回文章
    返回