基于改进EK算法的FPGA内部互联自动化测试方法

doi:10.16180/j.cnki.issn1007-7820.2025.02.002

电子科技 ›› 2025, Vol. 38 ›› Issue (2): 10-16.doi: 10.16180/j.cnki.issn1007-7820.2025.02.002

基于改进EK算法的FPGA内部互联自动化测试方法

傅僈喃¹^,²(), 陈苏婷¹, 解维坤², 林晓会²

1.南京信息工程大学电子与信息工程学院,江苏南京 210042
2.中国电子科技集团公司第58研究所,江苏无锡 214035

收稿日期:2023-06-29 修回日期:2023-07-16 出版日期:2025-02-15 发布日期:2025-01-16
通讯作者: 傅僈喃(1999-),女, E-mail:fmn5263de@163.com,硕士研究生。研究方向:FPGA内部互联自动化测试方法。
作者简介:陈苏婷(1980-),女,博士,教授。研究方向:图像处理和人工智能。
基金资助:
国家自然科学基金(62272234)

An Automatic Test Method for FPGA Interconnect Resource Based on An Improved EK Algorithm

FU Mannan¹^,²(), CHEN Suting¹, XIE Weikun², LIN Xiaohui²

1. School of Electronics and Information Engineering,Nanjing University of Information Science and Technology,Nanjing 210042,China
2. The 58th Research Institute,China Electronics Technology Group Corporation,Wuxi 214035,China

Received:2023-06-29 Revised:2023-07-16 Online:2025-02-15 Published:2025-01-16
Supported by:
National Natural Science Foundation of China(62272234)

摘要/Abstract

摘要：

在现场可编程门阵列(Field Programmable Gate Array, FPGA)互联资源(Interconnect Resource, IR)测试中,现存测试方法存在测试向量配置次数多、测试复杂度高且测试效率低等问题。为减少配置次数和提高测试效率,文中提出一种基于改进EK(Edmonds-Karp)算法的FPGA内部互联自动化测试方法。该方法将EK算法中寻找从源点s到终点t最短路径的增广路径改为寻找s到t最长路径的增广路径,以此减少配置次数。根据FPGA内部底层互联资源结构建立模型,将改进EK算法应用到Kintex-7系列FPGA中进行自动化布线路径搜索,并将布线路径配置进FPGA进行仿真实验。实验结果表明,相较于现存测试方法,所提方法在不减小故障覆盖率的同时能够以较少的配置次数检测出FPGA内互联资源的开路故障、短路故障和固定型故障。

关键词: FPGA互联资源, 配置次数, 测试向量, 自动化测试, Edmonds-Karp算法, 增广路径, 故障覆盖率, 测试效率

Abstract:

In the FPGA(Field Programmable Gate Array) IR(Interconnect Resource) testing, existing testing methods have problems such as multiple test vector configurations, high testing complexity,and low testing efficiency. In order to reduce the number of configurations and improve the efficiency of testing,an automatic test method for FPGA IR based on an improved EK(Edmonds-Karp) algorithm is proposed. This method achieves the goal of reducing the number of configurations by changing the search for the shortest path from the source point s to the endpoint t in the EK algorithm to the search for the longest path from s to t. A model based on the internal underlying IR structure of the FPGA is established,the improved EK algorithm is applied to the Kinex-7 series FPGA for automated routing path search,and the routing path is configured into the FPGA for simulation experiments. The experimental results show that the proposed method can detect the open circuit fault, short circuit fault and fixed fault in FPGA with less configuration times without reducing the fault coverage.

Key words: FPGA interconnect resource, number of configurations, test vector, automated testing, Edmonds-Karp algorithm, augmentation path, fault coverage rate, testing efficiency

中图分类号:

TN47

傅僈喃, 陈苏婷, 解维坤, 林晓会. 基于改进EK算法的FPGA内部互联自动化测试方法[J]. 电子科技, 2025, 38(2): 10-16.

FU Mannan, CHEN Suting, XIE Weikun, LIN Xiaohui. An Automatic Test Method for FPGA Interconnect Resource Based on An Improved EK Algorithm[J]. Electronic Science and Technology, 2025, 38(2): 10-16.

图/表 10

图1

图2

图3

图4

图5

图6

图7

图8

表1

表2

参考文献 19

[1]	葛云侠, 武乾文, 赵益波, 等. 一种优化FPGA内嵌BRAM自检测March C+算法[J]. 国外电子测量技术, 2022, 41(4):1-7.
	Ge Yunxia, Wu Qianwen, Zhao Yibo, et al. Optimized March C+ algorithm for embedded BRAM self-test in FPGA[J]. Foreign Electronic Measurement Technology, 2022, 41(4):1-7.
[2]	Rupanetti D, Nepal K, Salamy H, et al. Cost-effective,reconfigurable cluster approach for resource constricted FPGA based machine learning and AI applications[C]. Las Vegas: The Tenth Annual Computing and Communication Workshop and Conference,2020:228-233.
[3]	张锋印, 高博, 冀亚玮. 基于FPGA的多应用任务流量管理算法[J]. 电子科技, 2022, 35(12):43-48.
	Zhang Fengyin, Gao Bo, Ji Yawei. Multi-task traffic management algorithm based on FPGA[J]. Electronic Science and Technology, 2022, 35(12):43-48.
[4]	天野英晴. FPGA原理和结构[M].赵谦,译. 北京: 人民邮电出版社,2019:1-12.
	Amano Hideharu. FPGA principle and structure[M].Translated by ZhaoQian. Beijing: Press of People's Posts and Telecommunications,2019:1-12.
[5]	Fibich C, Horauer M, Obermaisser R. Characterization of interconnect fault effects in SRAM-based FPGAs[C]. Tallinn: The Twenty-sixth International Symposium on Design and Diagnostics of Electronic Circuits and Systems,2023:65-68.
[6]	毛志明, 张颖, 姚嘉祺, 等. FPGA互连测试中的反馈桥接故障覆盖问题[J]. 计算机测量与控制, 2022, 30(4):23-49.
	Mao Zhiming, Zhang Ying, Yao Jiaqi, et al. Coverage problem of feedback-bridging fault in the FPGA interconnection test[J]. Computer Measurement and Control, 2022, 30(4):23-49.
[7]	李光, 谢达, 董宜平, 等. 基于Virtex5的FPGA全覆盖五倍线确定性布线测试[J]. 电子与封装, 2018, 18(5):15-18.
	Li Guang, Xie Da, Dong Yiping, et al. A full coverage deterministic routing test of pent lines based on FPGA Virtex5[J]. Electronics and Packaging, 2018, 18(5):15-18.
[8]	Ruan A, Huang H, Wang J, et al. A routability aware algorithm for both global and local interconnect resource test and diagnosis of Xilinx SRAM-FPGAs[J]. Journal of Electronic Testing, 2016, 32(7):749-762.
[9]	Kumar T N, Almurib H A F. Fine grain faults diagnosis of FPGA interconnect[J]. Microprocessors and Microsystems, 2013, 37(1):33-40.
[10]	Pereira I G, Dias L A, Souza C P. A shift-register based BIST architecture for FPGA global interconnect testing and diagnosis[J]. Journal of Electronic Testing, 2015, 31(2):207-215.
[11]	Jahanirad H, Karam H. BIST-based online test approach for SRAM-based FPGAs[C]. Mashhad: Iranian Conference on Electrical Engineering,2018:178-183.
[12]	Banik S, Roy S, Sen B. Test configuration generation for different FPGA architectures for application independent testing[C]. Delhi: The Thirty-second International Conference on VLSI Design and the Eighteenth International Conference on Embedded Systems,2019:395-400.
[13]	余浩然, 肖昊. 基于LDL算法的大规模矩阵求逆加速器设计及其FPGA实现[J]. 电子科技, 2023, 36(7):1-7.
	Yu Haoran, Xiao Hao. Design and FPGA implementation of large scale matrix inversion accelerator based on LDL algorithm[J]. Electonic Science and Technology, 2023, 36(7):1-7.
[14]	Banik S, Roy S, Sen B. Application dependent testing of FPGA interconnect network[J]. IEEE Transactions on Very Large Scale Integration Systems, 2019, 27(10):2296-2304.
[15]	王林, 朱建华, 罗前. 一种用于FPGA互联资源测试的新方法[J]. 电子元器件应用, 2012, 14(1):42-45.
	Wang Lin, Zhu Jianhua, Luo Qian. A new method for FPGA interconnection resource testing[J]. Electronic Component and Device Applications, 2012, 14(1):42-45.
[16]	刘沛文. 基于有向图理论的FPGA互联资源测试方法的研究[D]. 上海: 上海交通大学,2018:11-17.
	Liu Peiwen. Research of testing method for interconnect resources in FPGAs based on directed graph theory[D]. Shanghai: Shanghai Jiao Tong University,2018:11-17.
[17]	徐俊明. 图论及其应用[M]. 合肥: 中国科学技术大学出版社,2019:163-166.
	Xu Junming. Graph theory and its applications[M]. Hefei: Press of University of Science and Technology of China,2019:163-166.
[18]	汪荣贵. 算法设计与应用[M]. 北京: 北京机械工业出版社,2017:182-188.
	Wang Ronggui. Algorithm design and application[M]. Beijing: Press of Mechanical Industry,2017:182-188.
[19]	Beckhoff C, Koch D, Torresen J. The Xilinx design language:Tutorial and use cases[C]. Montpellier: The Sixth International Workshop on Reconfigurable Communication Centric Systems on Chip,2011:1-8.

模型类型	IR类型	配置次数	故障覆盖率/%
水平	二倍线和四倍线	4	100
垂直	二倍线和六倍线	4	100
左对角线	二倍线和六倍线	16	100
右对角线	二倍线和六倍线	16	100
总计	二倍线和四倍线和六倍线	40	100

测试方法	IR类型	配置次数	故障覆盖率/%
文献[8]	二倍线和四倍线和六倍线	≥100	100
文献[12]	二倍线和四倍线和六倍线	59	100
本文	二倍线和四倍线和六倍线	40	100

基于改进EK算法的FPGA内部互联自动化测试方法

An Automatic Test Method for FPGA Interconnect Resource Based on An Improved EK Algorithm

RichHTML

PDF (PC)

赞

可视化

摘要/Abstract

引用本文

使用本文

图/表 10

参考文献 19

相关文章 5

Metrics

本文评价

推荐阅读 0

[1]	杨进成，夏春蕾，戴曙光. 基于LabVIEW的无线遥控汽车检测台设计[J]. , 2016, 29(10): 129-.
[2]	陈施杰,魏国亮. 汽车总线自动化测试系统设计[J]. , 2015, 28(9): 120-.
[3]	陈志强, 林平分, 任威丽. SOC芯片的可测试性设计与功耗优化[J]. , 2012, 25(8): 23-.
[4]	范振军. 多路三轴光纤陀螺自动化测试系统设计与实现[J]. , 2012, 25(2): 82-.
[5]	邵作镇, 万晓冬. 基于STAF的软件自动化测试研究与应用[J]. , 2010, 23(7): 9-12.