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

doi:10.16180/j.cnki.issn1007-7820.2025.02.002

Abstract

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

CLC Number:

TN47

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.

Figures/Tables 10

Figure 1.

Figure 2.

Figure 3.

Figure 4.

Figure 5.

Figure 6.

Figure 7.

Figure 8.

Table 1.

Table 2.

References 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

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

RichHTML

PDF (PC)

Like

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 10

References 19

Related Articles 15

Metrics

Comments

Recommended 0

[1]	YE Xiangyu, LIN Xiaohui, DING Jiangqiao, XIE Weikun. Total Jitter Prediction Method of FPGA Embedded High-Speed Interface Based on Optimized BPNN [J]. Electronic Science and Technology, 2025, 38(2): 70-77.
[2]	CHENG Tiantian,SONG Yukun. Optimization and Implementation of 2-Base Exponential Function Algorithm Based on FPGA [J]. Electronic Science and Technology, 2023, 36(9): 66-72.
[3]	HU Yongyang,LI Miao,MENG Fankai,ZHANG Feng,MENG Yiwei,SONG Yukun. Structured Compression and Acceleration of Network Based on Tiny-YOLOv3 [J]. Electronic Science and Technology, 2023, 36(8): 43-48.
[4]	YUAN Ziang,NI Wei,RAN Jingnan. Reconfigurable Convolutional Neural Network Accelerator Based on Winograd Algorithm [J]. Electronic Science and Technology, 2022, 35(12): 35-42.
[5]	CHEN Wenjie,SONG Yukun,ZHANG Duoli. Design of Matrix Decomposer Based on Improved QR Algorithm [J]. Electronic Science and Technology, 2022, 35(11): 21-28.
[6]	WANG Chunhua,LI Bin,DU Gaoming,LI Zhenmin. Design and Implement of a High-Performance RLWE Cryptoprocessor [J]. Electronic Science and Technology, 2022, 35(11): 13-20.
[7]	ZHANG Xuan,ZHANG Duoli,SONG Yukun. Optimization of the Internal Memory Architecture of Heterogeneous Multi-Core SoC Processors [J]. Electronic Science and Technology, 2022, 35(9): 44-51.
[8]	WANG Xiaolei,DAI Wujun,DU Gaoming,LI Zhenmin,ZHANG Duoli. Design of a High-Performance SC Decoder for Polar Codes [J]. Electronic Science and Technology, 2022, 35(8): 14-20.
[9]	Weiyi LIU,Yanan SUN,Weifeng HE. Design of Ternary Logic-in-Memory Based on RRAM Dual-Crossbars [J]. Electronic Science and Technology, 2022, 35(4): 8-13.
[10]	XIANG Yang,SUN Xiaoxia,SONG Yukun. A Fault-tolerant Scheme for Data Flow Driven Computing Channels [J]. Electronic Science and Technology, 2020, 33(7): 6-11.
[11]	SUN Yuanxin, QIN Shuijie. Design of DFT Hardware Accelerator Used in LTE Uplink [J]. , 2018, 31(4): 52-.
[12]	QUAN Zhaofeng. Hardware Design of NoC Boundary Scan Test System [J]. , 2015, 28(9): 63-.
[13]	CHEN Maoqiang. A Task Scheduling Algorithm for Parallel System Based on DAG [J]. , 2014, 27(9): 29-.
[14]	SONG Yukun,CHEN Xiaobo. VLSI Implementation of Fast Half-Pixel Interpolation Algorithm Based on H.264 [J]. , 2014, 27(7): 1-.
[15]	LIU Zong-Fu, MA Dong-Dong, ZHAO Dan-Hui. Design of a Bandgap Voltage Reference with High Accuracy and Low Power Voltage [J]. , 2010, 23(11): 41-43.