结合格局检测与局部搜索的故障数据缩减方法

doi:10.13229/j.cnki.jdxbgxb20200690

Abstract

Abstract:

Aiming at the problem of redundant fail data in the existing N-cover fail data reduction method, a fail data reduction method combining pattern detection and local search is proposed. A local search method combining configuration checking strategy was proposed. By analyzing the logical relationship between fail data and the coverage time of ports, the concepts of fail frequency and defect coverage degree were proposed. Meanwhile, the configuration checking strategy is combined to avoid visiting the same solution space, and the search breadth is increased by reducing redundant iterations. The experimental results for benchmark circuits demonstrate that, compared with existing methods, the proposed method effectively reduces the amount of fail data and improves efficiency while ensuring the quality of diagnosis.

Key words: atificial intelligence, fault diagnosis, circuit test, fail data, local search, configuration checking

CLC Number:

TN407

Dan-tong OUYANG,Bi-ge ZHANG,Nai-yu TIAN,Li-ming ZHANG. Fail data reduction algorithm combining configuration checking with local search[J].Journal of Jilin University(Engineering and Technology Edition), 2021, 51(6): 2144-2153.

Figures/Tables 6

Fig.1

Table 1

Table 2

Table 3

Process of FDRLS"

迭代过程		数值类型	自变量z_i（tar（z_i））
整体过程	局部过程	数值类型	z₁（1）	z₂（3）	z₃（1）	z₄（1）	z₅（3）	z₆（3）	z₇（3）	z₈（2）	z₉（2）	z₁₀（1）
第1轮迭代		H（z_i）	0	9/9	0	0	9/6	9/5	9/8	9/3	9/2	0
	D_temp=｛d_5，d_1，d₄｝	tar（z_i）-num（z_i）	0	0	0	0	0	1	0	1	1	0
	D_temp=｛d_5，d_1，d_4，d₂｝		0	-1	0	0	-1	0	-1	0	0	0
	D_temp=｛d₅，d₄，d₂｝		0	0	1	1	0	0	0	0	0	0
	D_temp=｛d₅，d₂｝		0	1	1	1	1	1	1	0	0	1
	D_temp=｛d₅，d₂，d₉｝		0	0	1	1	0	0	0	0	-1	1
第2轮迭代		H（z_i）	0	9/9	1	1	9/6	9/5	9/8	9/3	9/2	1
	D_temp=｛d₅，d₂｝	tar（z_i）-num（z_i）	0	1	1	1	1	1	1	0	0	1
	D_temp=｛d₅，d₂，d₄｝	tar（z_i）-num（z_i）	0	0	1	1	0	0	0	0	0	0
$?$	$?$	$?$	$?$

Table 3

Table 4

Table 5

Experimental results and comparison of ISCAS89"

name	gold	new	int	Fail data/bytes		o_time /ms	r_time /ms	DA			DDR			FSR			DS
name	gold	new	int	before	after	o_time /ms	r_time /ms	RLS	Cov	HS	RLS	Cov	HS	RLS	Cov	HS	RLS	Cov	HS
ave	-	-	-	-	-	-	-	79.2	77.9	81.0	15.6	17.6	11.7	63.5	60.1	54.8	67.0	65.2	58.3
s27	7	7.1	6	1 056	422	50.5	12.2	85.7	57.1	100.0	15.7	14.3	28.6	60.0	60.0	40.1	75.8	72.9	37.0
s208_1	30	26.8	19	10 764	2 574	1 134.8	180.2	63.3	63.3	96.7	26.0	30.0	30.0	76.1	71.7	45.6	84.1	84.2	45.7
s298	61	59.3	48.3	13 397	4 985	4 864.8	1512.3	79.2	65.6	70.5	18.0	18.0	8.2	62.8	60.5	53.5	68.9	68.5	52.4
s344	21	15.3	14.3	14 552	5 821	5 987.7	2032.7	68.1	66.7	66.7	4.8	4.8	4.8	60.0	54.3	51.4	66.1	60.6	49.3
s349	31	31	28	14 968	4 989	6 866.2	2 062.3	90.3	74.2	93.5	9.7	9.7	6.5	66.7	61.1	50.0	70.0	64.1	48.3
s382	55	39	35	18 642	6 779	11 001.0	4 574.2	63.6	70.9	70.9	7.3	5.5	5.5	63.6	56.8	63.6	58.4	63.0	62.7
s386	94	78.5	77.5	19 040	5 600	8 610.1	2 011.1	82.4	94.7	79.8	1.1	7.4	19.1	70.6	69.4	70.6	76.6	74.5	68.4
s400	68	52	46	20 337	8 050	12 597.8	4 125.2	67.6	67.6	47.1	8.8	8.8	13.2	60.4	56.3	66.7	67.3	62.6	66.9
s420	42	34	29.5	32 701	11 489	13 791.4	4 692.2	70.2	69.0	76.2	10.7	33.3	11.9	64.9	62.2	40.5	66.0	63.9	39.7
s420_1	30	40.4	28.2	38 340	8 946	14 840.9	2 892.9	94.0	90.0	100	40.7	40.0	23.3	76.7	74.4	44.4	80.5	81.0	40.3
s444	47	57.1	43	18 642	8 050	14 471.7	6 245.6	91.5	91.5	93.6	30.0	25.5	17.0	56.8	47.7	65.9	56.8	48.6	65.1
s510	67	59.9	52	22 531	6 115	12 784.7	3 752.3	77.6	71.6	89.5	11.8	10.4	11.9	72.9	68.6	31.4	70.7	71.4	27.2
s526	51	51.1	47.3	35 590	11 863	42 205.6	12 005.5	92.7	92.2	82.3	7.5	11.8	0	66.7	65.5	65.5	71.6	71.6	70.0
s526n	52	65.3	47.6	33 471	13 558	34 293.5	13 883.6	91.5	98.1	94.2	34.0	36.5	7.7	59.5	55.7	63.3	59.5	56.5	92.9
s641	16	14	14	65 914	32 172	53 264.5	23 353.7	87.5	87.5	87.5	0	0	0	51.2	48.8	70.2	56.2	54.3	79.4
s713	75	65.9	51.3	65 914	29 033	81 307.5	34 366.5	68.4	81.3	65.3	19.5	17.3	9.3	56.0	54.8	66.7	57.7	58.2	76.4
s820	134	85	84	54 472	19 986	164 508.3	56 617.5	62.7	61.9	67.2	0.7	17.9	0	63.3	63.3	55.4	65.6	65.6	51.2
s832	171	168.7	120.4	55 648	20 770	155 147.3	57 119.6	70.4	69.6	59.1	28.2	59.1	24.0	62.7	56.3	54.9	63.2	58.2	60.2
s838	24	24	24	105 722	36 342	221 197.2	72 192.2	100	100.0	100.0	0	0	4.2	65.6	64.1	32.8	67.4	66.9	62.9
s838_1	48	49.1	33.9	150 660	41 309	323 591.3	77 246.4	70.6	68.8	100	31.7	31.3	22.9	72.6	69.4	46.8	76.1	74.2	52.0
s953	56	44.9	39.9	48 256	18 625	259 815.5	88 192.4	71.3	71.4	82.1	8.9	12.5	1.8	61.4	60.5	53.5	66.1	68.0	34.0
s1196	55	50.2	46.6	96 768	36 352	613 460.5	218 912.4	84.7	85.5	90.9	6.5	1.8	9.1	62.4	58.7	60.3	64.3	61.4	82.3
s1423	88	89.8	81.5	147 273	60 560	1364 428.9	572 061.5	92.6	90.9	83	9.4	10.2	4.5	58.9	53.3	59.8	58.1	58.8	70.3
s1488	258	217.9	210.9	56 179	23 517	642 157.7	226 094.0	81.7	82.2	62.4	2.7	3.5	1.6	58.1	55.2	59.3	64.8	63.1	61.5
s1494	246	320.5	181.1	54 873	22 210	619 257.5	214 570.8	73.6	76.8	67.5	56.7	31.7	29.3	59.5	55.4	58.3	65.4	58.3	63.2

Table 5

References 25

1	Chakraborty T J, Chiang C H, van Treuren B G. A practical approach to comprehensive system test & debug using boundary scan based test architecture[C]∥Proceedings of 2007 IEEE International Test Conference, Santa Clara, CA, USA, 2007: 1-10.
2	欧阳丹彤,刘伯文,刘梦,等. 结合电路结构基于分块的诊断方法[J]. 电子学报, 2018, 46(7): 1571-1577.
	Ouyang Dan-tong, Liu Bo-wen, Liu Meng, et al. A block-based diagnostic method combining with the circuit structure[J]. Acta Electronica Sinica, 2018, 46(7): 1571-1577.
3	欧阳丹彤,苏静,叶育鑫,等. 基于模型诊断的本体调试局部定位[J]. 吉林大学学报:工学版, 2014, 44(6): 1757-1763.
	Ouyang Dan-tong, Su Jing, Ye Yu-xin, et al. Local pinpointing of ontology debugging based on model-based diagnosis[J]. Journal of Jilin University(Engineering and Technology Edition), 2014, 44(6): 1757-1763.
4	欧阳丹彤,刘扬,刘杰. 故障响应指导下基于测试集的故障诊断方法[J]. 吉林大学学报:工学版, 2021, 51(3): 1017-1025.
	Ouyang Dan-tong, Liu Yang, Liu Jie. Fault diagnosis method based on test set under fault response guidance[J]. Journal of Jilin University(Engineering and Technology Edition), 2021, 51(3): 1017-1025.
5	Song J, Ouyang D T, Liu Y, et al. Improving the accuracy of defect diagnosis by test score based on fault free[J]. Electronics Letters, 2020, 56(16): 845-848.
6	Pomeranz I. Test scores for improving the accuracy of logic diagnosis for multiple defects[J]. IEEE Transactions on Very Large Scale Integration Systems, 2019, 27(7): 1720-1724.
7	Pomeranz I, Venkataraman S. LFSR-based test generation for reduced fail data volume[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2020, 39(12): 5261-5266.
8	Huang Y, Milewski S, Rajski J, et al. Hypercompression of test patterns[C]∥IEEE International Test Conference, Phoenix, AZ, USA, 2018: 1-9.
9	欧阳丹彤,陈晓艳,叶靖,等. 基于极小碰集求解算法的测试向量集约简[J]. 计算机研究与发展, 2019, 56(11): 2448-2457.
	Ouyang Dan-tong, Chen Xiao-yan, Ye Jing, et al. Test pattern set reduction based on the method of computing minimal hitting set[J]. Journal of Computer Research and Development, 2019, 56(11): 2448-2457.
10	Amati L, Bolchini C, Frigerio L, et al. An incremental approach to functional diagnosis[C]∥Proceedings of 24th IEEE International Symposium on Defect and Fault Tolerance in VLSI Systems, Chicago, IL, USA, 2009: 392-400.
11	Wang H F, Poku O, Yu X C, et al. Test-data volume optimization for diagnosis[C]∥Proceedings of the 49th Annual Design Automation Conference, San Francisco, USA, 2012: 567-572.
12	Bolchini C, Cassano L. A novel approach to incremental functional diagnosis for complex electronic boards[J]. IEEE Transactions on Computers, 2015, 65(1): 42-52.
13	Liu M Y, Pan R J, Ye F M, et al. Fine-grained adaptive testing based on quality prediction[C]∥Proceedings of 2018 IEEE International Test Conference, Phoenix, AZ, USA, 2018: 1-10.
14	吕洪武, 赵航, 王宏志, 等. 基于模糊神经网络的MVB故障诊断算法[J]. 吉林大学学报:理学版, 2020, 58(1): 104-108.
	Lv Hong-wu, Zhao Hang, Wang Hong-zhi, et al. Fault diagnosis algorithm for MVB based on fuzzy neural network[J]. Journal of Jilin University Science Edition, 2020, 58(1): 104-108.
15	李家伟. 基于证据理论和支持向量机的风机故障智能诊断[J]. 吉林大学学报:理学版, 2016, 54(3): 609-612.
	Li Jia-wei. Intelligent diagnosis of fan fault based on evidence theory and support vector machine[J]. Journal of Jilin University Science Edition, 2016, 54(3): 609-612.
16	Bodhe S, Amyeen M E, Pomeranz I, et al. Diagnostic fail data minimization using an N-Cover algorithm[J]. IEEE Transactions on Very Large Scale Integration Systems, 2016, 24(3): 1198-1202.
17	Bodhe S, Amyeen M E, Galendez C, et al. Reduction of diagnostic fail data volume and tester time using a dynamic N-cover algorithm[C]∥Proceedings of the 34th IEEE VLSI Test Symposium, Las Vegas, NV, USA, 2016: 1-6.
18	Cai S W, Luo C, Thornton J, et al. Tailoring local search for partial MaxSAT[C]∥Proceedings of the 28th AAAI Conference on Artificial Intelligence, Québec, Canada, 2014: 2623-2629.
19	欧阳丹彤, 罗知雨, 耿雪娜, 等. 分布式离散事件系统的安全可诊断性算法[J]. 吉林大学学报:理学版, 2018, 56(3): 594-600.
	Ouyang Dan-tong, Luo Zhi-yu, Geng Xue-na, et al. Algorithm of safe diagnosability for distributed discrete event systems[J]. Journal of Jilin University Science Edition, 2018, 56(3): 594-600.
20	张子成, 韩伟, 毛波. 基于模拟退火的自适应离散型布谷鸟算法求解旅行商问题[J]. 电子学报, 2018, 46(8): 1849-1857.
	Zhang Zi-cheng, Han Wei, Mao Bo. Adaptive discrete cuckoo algorithm based on simulated annealing for solving TSP[J]. Acta Electronica Sinica, 2018, 46(8): 1849-1857.
21	Pomeranz I. OBO: an output-by-output scoring algorithm for fault diagnosis[C]∥Proceedings of IEEE Computer Society Annual Symposium on VLSI, Tampa, FL, USA, 2014: 314-319.
22	Wang Y Y, Cai S W, Chen J J, et al. SCCWalk: an efficient local search algorithm and its improvements for maximum weight clique problem[J]. Artificial Intelligence, 2020, 280(C): No.103230.
23	Cai S W, Su K L. Local search for boolean satisfiability with configuration checking and subscore[J]. Artificial Intelligence, 2013, 204: 75-98.
24	Brglez F, Fujiwara H. A neutral netlist of 10 combinational benchmark circuits and a target translator in fortran[C]∥Proceedings of IEEE International Symposium on Circuits and Systems, Kyoto, Japan, 1985: 695-698.
25	Brglez F, Bryand D, Kozminski K. Combinational profiles of sequential benchmark circuits[C]∥Proceedings of IEEE International Symposium on Circuits and Systems, Portland, OR, USA, 1989: 1929-1934.

Related Articles 15

[1]	Lao-hu YUAN,Dong-shan LIAN,Liang ZHANG,Yi LIU. Fault diagnosis of key mechanical components of aircraft based on densenet and support vector machine [J]. Journal of Jilin University(Engineering and Technology Edition), 2021, 51(5): 1635-1641.
[2]	Shuai LYU,Jing LIU. Stochastic local search heuristic method based on deep reinforcement learning [J]. Journal of Jilin University(Engineering and Technology Edition), 2021, 51(4): 1420-1426.
[3]	Wei LI,Jian CHEN,Shan-yong TAO. Method of enhancing stochastic resonance signal of self⁃adaptive coupled periodic potential system [J]. Journal of Jilin University(Engineering and Technology Edition), 2021, 51(3): 1091-1096.
[4]	Dan-tong OUYANG,Yang LIU,Jie LIU. Fault diagnosis method based on test set under fault response guidance [J]. Journal of Jilin University(Engineering and Technology Edition), 2021, 51(3): 1017-1025.
[5]	Feng-wen PAN,Dong-liang GONG,Ying GAO,Ming-wei XU,Bin MA. Fault diagnosis of current sensor based on linearization model of lithium ion battery [J]. Journal of Jilin University(Engineering and Technology Edition), 2021, 51(2): 435-441.
[6]	Gen-bao ZHANG,Hao LI,Yan RAN,Qiu-jin LI. A transfer learning model for bearing fault diagnosis [J]. Journal of Jilin University(Engineering and Technology Edition), 2020, 50(5): 1617-1626.
[7]	WANG De-jun, WEI Wei-li, BAO Ya-xin. Actuator fault diagnosis of ESC system considering crosswind interference [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(5): 1548-1555.
[8]	SUN Liang, XU Hai-lang, GE Hong-wei. Novel global convergence stochastic particle swarm optimizers [J]. 吉林大学学报(工学版), 2017, 47(2): 615-623.
[9]	SONG Da-feng, LI Guang-han, ZHANG Lin, PAN Bing, ZENG Xiao-hua, PENG Yu-jun, WANG Qing-nian. Application of fuzzy mathematics in fault diagnosis of motor of hybrid vehicle [J]. 吉林大学学报(工学版), 2016, 46(2): 354-359.
[10]	OUYANG Dan-tong,CHI Jin-jin,WANG Xiao-yu,ZHAO Xiang-fu ,MENG Xiang-yu. Approach of diagnosis of higher-order discrete event systems [J]. 吉林大学学报(工学版), 2015, 45(2): 562-568.
[11]	SONG Bao-yu,XIE Zhi-jie,ZHANG Feng,WANG Rui-ze,HAO Ming-hui,SU Dai-zhong. Fault diagnosis algorithm for helical gear rotating at low speed on angular domain synchronous average and order tracking analysis [J]. 吉林大学学报(工学版), 2015, 45(2): 454-459.
[12]	WU Jian, ZHAO Yang, HE Rui. Fault detection and diagnosis of EMB sensor system based on SVR [J]. 吉林大学学报(工学版), 2013, 43(05): 1178-1183.
[13]	HAO Yan, WANG Tai-yong, WAN Jian, ZHANG Pan, LIU Lu. Mechanical fault diagnosis based on empirical mode decomposition and generalized dimension [J]. 吉林大学学报(工学版), 2012, 42(02): 392-396.
[14]	CHEN Yun-han, QIN Gui-he, YU He, HUANG Yue. In-vehicle network management system complied with OSEK/VDX direct NM [J]. 吉林大学学报(工学版), 2011, 41(05): 1407-1413.
[15]	KONG Fan-sen,WU Ya-fu,LI Cong. Assessment of fault diagnosis complexity about electrical fault diagnosis of equipment based on information entropy [J]. 吉林大学学报(工学版), 2011, 41(03): 697-701.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

Comments

Recommended 0

No Suggested Reading articles found!

name	gold	new	int	Fail data/ytes		o_time /ms	r_time /ms	DA			DDR			FSR			DS
name	gold	new	int	before	after	o_time /ms	r_time /ms	RLS	Cov	HS	RLS	Cov	HS	RLS	Cov	HS	RLS	Cov	HS
ave	-	-	-	-	-	-	-	79.3	79.7	82.8	20.9	21.7	15.0	55.4	46.9	31.7	57.9	52.3	30.9
c17	3	3.6	2.7	522	149	24.1	9.2	90.0	100.0	66.7	30.0	66.7	0	71.5	71.5	14.2	61.8	58.1	33.3
c432	17	16	9	8 386	2 187	133.3	23.1	52.9	52.9	70.6	41.2	41.2	5.9	73.9	73.9	17.4	82.7	83.4	22.1
c499	22	21	21	9 610	4 805	727.7	343.1	95.5	95.5	86.4	0	0	50.0	50.0	37.5	37.5	52.9	43.2	32.0
c880	25	21	21	15 541	7 064	1 026.1	422.1	84.0	84.0	84.0	0	12.0	12.0	54.5	50.0	45.5	58.9	57.1	39.1
c1355	19	22.6	16.9	9 010	4 805	769.3	352.3	88.9	89.5	94.7	30.0	31.6	15.8	46.7	46.7	33.3	54.2	54.3	32.3
c1908	19	22	17	6 730	2 884	338.4	126.1	89.5	78.9	100	26.3	5.3	0	57.1	42.9	28.6	62.7	55.1	26.0
c2670	25	33.5	20.5	85 757	39 305	37 279.4	18 153.4	82.0	80.0	84.0	52.0	20.0	12.0	54.2	47.9	27.1	51.3	45.8	22.4
c3540	35	25	21	21 397	7 726	1 116.0	360.7	60.0	54.3	71.4	11.4	11.4	17.1	63.9	50.0	44.5	67.7	60.6	41.9
c5315	20	20	19	92 151	50 925	112 953.6	61 555.9	95.0	100.0	95.0	5.0	5.0	10.0	44.7	36.8	44.7	45.5	38.0	43.9
c6288	29	20	16	4 224	2 640	456.5	267.5	55.2	62.1	75.9	13.8	24.1	27.6	37.5	12.5	25.0	41.4	27.8	16.1

Fail data reduction algorithm combining configuration checking with local search

RICH HTML

PDF (PC)