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

doi:10.13229/j.cnki.jdxbgxb20200690

摘要/Abstract

摘要：

针对集成电路故障诊断中故障数据缩减方法N-cover存在冗余故障数据的问题，提出了结合格局检测与局部搜索的故障数据缩减方法。通过分析故障数据与端口覆盖次数的逻辑关系，提出了故障频率和故障覆盖度的概念以指导局部搜索。同时，结合格局检测策略以避免重复搜索，进而通过减少冗余迭代来增加搜索广度。在标准测试用例上的实验结果表明，与现有方法相比，本文方法可有效缩减故障数据数目并提高求解效率。

关键词: 人工智能, 故障诊断, 电路测试, 故障数据, 局部搜索, 格局检测

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

中图分类号:

TN407

欧阳丹彤,张必歌,田乃予,张立明. 结合格局检测与局部搜索的故障数据缩减方法[J]. 吉林大学学报(工学版), 2021, 51(6): 2144-2153.

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.

图/表 6

图1

表1

表2

表3

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
$?$	$?$	$?$	$?$

表3

表4

表5

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

表5

参考文献 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.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

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

[1]	杨勇,陈强,曲福恒,刘俊杰,张磊. 基于模拟划分的SP⁃k⁃means-+算法[J]. 吉林大学学报(工学版), 2021, 51(5): 1808-1816.
[2]	院老虎,连冬杉,张亮,刘义. 基于密集连接卷积网络和支持向量机的飞行器机械部件故障诊断[J]. 吉林大学学报(工学版), 2021, 51(5): 1635-1641.
[3]	刘富,梁艺馨,侯涛,宋阳,康冰,刘云. 模糊c-harmonic均值算法在不平衡数据上改进[J]. 吉林大学学报(工学版), 2021, 51(4): 1447-1453.
[4]	吕帅,刘京. 基于深度强化学习的随机局部搜索启发式方法[J]. 吉林大学学报(工学版), 2021, 51(4): 1420-1426.
[5]	赵亚慧,杨飞扬,张振国,崔荣一. 基于强化学习和注意力机制的朝鲜语文本结构发现[J]. 吉林大学学报(工学版), 2021, 51(4): 1387-1395.
[6]	董延华,刘靓葳,赵靖华,李亮,解方喜. 基于BPNN在线学习预测模型的扭矩实时跟踪控制[J]. 吉林大学学报(工学版), 2021, 51(4): 1405-1413.
[7]	李伟,陈剑,陶善勇. 自适应耦合周期势系统随机共振信号增强方法[J]. 吉林大学学报(工学版), 2021, 51(3): 1091-1096.
[8]	欧阳丹彤,刘扬,刘杰. 故障响应指导下基于测试集的故障诊断方法[J]. 吉林大学学报(工学版), 2021, 51(3): 1017-1025.
[9]	潘凤文,弓栋梁,高莹,徐明伟,麻斌. 基于锂离子电池线性化模型的电流传感器故障诊断[J]. 吉林大学学报(工学版), 2021, 51(2): 435-441.
[10]	尚福华,曹茂俊,王才志. 基于人工智能技术的局部离群数据挖掘方法[J]. 吉林大学学报(工学版), 2021, 51(2): 692-696.
[11]	赵海英,周伟,侯小刚,张小利. 基于多任务学习的传统服饰图像双层标注[J]. 吉林大学学报(工学版), 2021, 51(1): 293-302.
[12]	张根保,李浩,冉琰,李裘进. 一种用于轴承故障诊断的迁移学习模型[J]. 吉林大学学报(工学版), 2020, 50(5): 1617-1626.
[13]	欧阳丹彤,马骢,雷景佩,冯莎莎. 知识图谱嵌入中的自适应筛选[J]. 吉林大学学报(工学版), 2020, 50(2): 685-691.
[14]	李贻斌,郭佳旻,张勤. 人体步态识别方法与技术[J]. 吉林大学学报(工学版), 2020, 50(1): 1-18.
[15]	徐谦,李颖,王刚. 基于深度学习的行人和车辆检测[J]. 吉林大学学报(工学版), 2019, 49(5): 1661-1667.