计算机科学技术学报 ›› 2019,Vol. 34 ›› Issue (5): 1136-1151.doi: 10.1007/s11390-019-1965-1

所属专题： Computer Architecture and Systems

• • 上一篇    下一篇

一种基于并行结构遗传算法的敏感性电路单元定位方法

Jie Xiao1, Member, CCF, Zhan-Hui Shi1, Member, CCF, Jian-Hui Jiang2,*, Senior Member, CCF, Xu-Hua Yang1, Yu-Jiao Huang1, Hai-Gen Hu1, Member, CCF   

  1. 1 College of Computer Science and Technology, Zhejiang University of Technology, Hangzhou 310023, China;
    2 School of Software Engineering, Tongji University, Shanghai 201804, China
  • 收稿日期:2019-01-11 修回日期:2019-06-03 出版日期:2019-08-31 发布日期:2019-08-31
  • 通讯作者: Jian-Hui Jiang E-mail:jhjiang@tongji.edu.cn
  • 作者简介:Jie Xiao received his Ph.D. degree in computer system architecture from Tongji University, Shanghai, in 2013. He is currently working with the College of Computer Science and Technology, Zhejiang University of Technology, Hangzhou. His current research interests include reliability evaluation and fault-tolerant design, deep learning and combinatorial optimization-computation. He also serves as a consultant and technical adviser for a research institute in electronic information fields. He is a member of CCF.
  • 基金资助:
    The work was supported by the National Natural Science Foundation of China under Grant Nos. 61972354, 61502422, 61432017, 61772199, 61773348, and 61503338, the Natural Science Foundation of Zhejiang Province of China under Grant Nos. LY18F020028, LY18F030023, LY18F030084, and LY17F030016, and the Innovative Experiment Project of Zhejiang University of Technology of China under Grant No. PX-68182112.

A Locating Method for Reliability-Critical Gates with a Parallel-Structured Genetic Algorithm

Jie Xiao1, Member, CCF, Zhan-Hui Shi1, Member, CCF, Jian-Hui Jiang2,*, Senior Member, CCF, Xu-Hua Yang1, Yu-Jiao Huang1, Hai-Gen Hu1, Member, CCF   

  1. 1 College of Computer Science and Technology, Zhejiang University of Technology, Hangzhou 310023, China;
    2 School of Software Engineering, Tongji University, Shanghai 201804, China
  • Received:2019-01-11 Revised:2019-06-03 Online:2019-08-31 Published:2019-08-31
  • Contact: Jian-Hui Jiang E-mail:jhjiang@tongji.edu.cn
  • About author:Jie Xiao received his Ph.D. degree in computer system architecture from Tongji University, Shanghai, in 2013. He is currently working with the College of Computer Science and Technology, Zhejiang University of Technology, Hangzhou. His current research interests include reliability evaluation and fault-tolerant design, deep learning and combinatorial optimization-computation. He also serves as a consultant and technical adviser for a research institute in electronic information fields. He is a member of CCF.
  • Supported by:
    The work was supported by the National Natural Science Foundation of China under Grant Nos. 61972354, 61502422, 61432017, 61772199, 61773348, and 61503338, the Natural Science Foundation of Zhejiang Province of China under Grant Nos. LY18F020028, LY18F030023, LY18F030084, and LY17F030016, and the Innovative Experiment Project of Zhejiang University of Technology of China under Grant No. PX-68182112.

PDF (PC)

138

补充材料

1

随着集成度的增加以及新工艺与新材料的应用，电路的可靠性容限也随之下降，而面向电路单元的加固方案是一种有效的可靠性改善方法，但这需要有单元定位方法的支持。因此，本文提出了一种基于并行结构遗传算法的敏感性电路单元定位方法以实现有针对性的单元加固策略。首先，设计了一种基于二进制策略的敏感性单元编码方法，并构建了由优势个体组成的有序初始种群以压缩解空间。接着，构建了一种基于并行结构的自带导向性功能的交叉与变异操作方法以补偿遗传算法局部搜索能力不足的缺陷。然后，结合种群的多样性检测策略，构建了一种基于精英保留策略的选择方法以加快收敛速度并避免陷入局部最优。最后，基于评分机制设计了一种有序的面向电路单元的综合敏感性排序方法以保证所提方法的鲁棒性。在基准电路上的实验结果表明，所提方法是一种有效的敏感性电路单元定位方法，它有着较快的收敛速度与较高的定位精度。

关键词: 门级电路可靠性, 敏感性电路单元定位, 并行结构遗传算法, 导向性策略, 评分机制

Abstract: The reliability allowance of circuits tends to decrease with the increase of circuit integration and the application of new technology and materials, and the hardening strategy oriented toward gates is an effective technology for improving the circuit reliability of the current situations. Therefore, a parallel-structured genetic algorithm (GA), PGA, is proposed in this paper to locate reliability-critical gates to successfully perform targeted hardening. Firstly, we design a binary coding method for reliability-critical gates and build an ordered initial population consisting of dominant individuals to improve the quality of the initial population. Secondly, we construct an embedded parallel operation loop for directional crossover and directional mutation to compensate for the deficiency of the poor local search of the GA. Thirdly, for combination with a diversity protection strategy for the population, we design an elitism retention based selection method to boost the convergence speed and avoid being trapped by a local optimum. Finally, we present an ordered identification method oriented toward reliability-critical gates using a scoring mechanism to retain the potential optimal solutions in each round to improve the robustness of the proposed locating method. The simulation results on benchmark circuits show that the proposed method PGA is an efficient locating method for reliability-critical gates in terms of accuracy and convergence speed.

Key words: gate-level circuit reliability, locating reliability-critical gate, parallel-structured genetic algorithm, directing strategy, scoring mechanism

[1] Xiao J, Jiang J H, Li X X et al. A novel trust evaluation method for logic circuits in IoT applications based on the E-PTM model. IEEE Access, 2018, 6:35683-35696.
[2] Zhang Y, Li H W, Li X W. Automatic test program generation using executing-trace-based constraint extraction for embedded processors. IEEE Transactions on Very Large Scale Integration Systems, 2013, 21(7):1220-1233.
[3] Srinivasu B, Sridharan K. A transistor-level probabilistic approach for reliability analysis of arithmetic circuits with applications to emerging technologies. IEEE Transactions on Reliability, 2017, 66(2):440-457.
[4] Xiao J, Lee W, Jiang J H et al. Sensitivity evaluation of input vectors with masking effects in digital circuits. Chinese Journal of Computers, 2018, 41(10):2282-2294. (in Chinese)
[5] Bickford J, Habib N, Li B et al. Integrated circuit chip reliability qualification using a sample-specific expected fail rate. United States Patent, http://www.freepatentsonline.com/9639645.pdf, May 2019.
[6] Han J, Hao C, Liang J H et al. A stochastic computational approach for accurate and efficient reliability evaluation. IEEE Transactions on Computers, 2014, 63(6):1336-1350.
[7] Mittal S, Vetter J S. A survey of techniques for modeling and improving reliability of computing systems. IEEE Transactions on Parallel and Distributing Systems, 2016, 27(4):1226-1238.
[8] Xiao J, Lee W, Jiang J H et al. Circuit reliability estimation based on an iterative PTM model with hybrid coding. Microelectronics Journal, 2016, 52:117-123.
[9] Bernardini A, Schlichtmann U. Symbolic fault modeling and model counting for the identification of critical gates in digital circuits. In Proc. IEEE GMM/ITG/GI-Symposium Reliability by Design, Sept. 2015, pp.15-22.
[10] Xiao J, Lou J G, Jiang J H et al. Blockchain architecture reliability-based measurement for circuit unit importance. IEEE Access, 2018, 6:15326-15334.
[11] Ibrahim W. Identifying the worst reliability input vectors and the associated critical logic gates. IEEE Transactions on Computers, 2016, 65(6):1748-1760.
[12] Ibrahim W, Beiu V, Amer H. Why should we care about input vectors? In Proc. the 2009 Joint IEEE North-East Workshop on Circuits and Systems and TAISA Conference, Jun. 2009, Article No. 60.
[13] Janssen H. Monte-Carlo based uncertainty analysis:Sampling efficiency and sampling convergence. Reliability Engineering & System Safety, 2013, 109:123-132.
[14] Rubinstein R Y, Kroese D P. Simulation and the Monte Carlo Method (3rd edition). Wiley, 2016.
[15] Han J, Chen H, Boykin E et al. Reliability evaluation of logic circuits using probabilistic gate models. Microelectronics Reliability, 2011, 51(2):468-476.
[16] Tang A, Jha N K. GenFin:Genetic algorithm-based multiobjective statistical logic circuit optimization using incremental statistical analysis. IEEE Transactions on Very Large Scale Integration Systems, 2016, 24(3):1126-1139.
[17] Srinivas M, Patnaik L. On generating optimal signal probabilities for random tests:A genetic approach. VLSI Design, 1996, 4(3):207-215.
[18] Nagamani A, Nayak A, Nanditha N et al. A genetic algorithm based heuristic method for test set generation in reversible circuits. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2018, 37(2):324-336.
[19] Liliakadri R, Boctor F. An efficient genetic algorithm to solve the resource-constrained project scheduling problem with transfer times:The single mode case. European Journal of Operational Research, 2018, 265(2):454-462.
[20] Kvassay M, Zaitseva E, Levashenko V et al. Reliability analysis of multiple-outputs logic circuits based on structure function approach. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2017, 36(3):398-411.
[21] Xiao J, Lou J G, Jiang J H. A fast and effective sensitivity calculation method for circuit input vectors. IEEE Transactions on Reliability. doi:10.1109/TR. 2019.2897455.
[22] Corus D, Dang D, Eremeev A et al. Level-based analysis of genetic algorithms and other search processes. IEEE Transactions on Evolutionary Computation, 2018, 22(5):707-719.
[23] Bito J, Jeong S, Tentzeris M. A novel heuristic passive and active matching circuit design method for wireless power transfer to moving objects. IEEE Transactions on Microwave Theory Techniques, 2017, 65(4):1094-1102.
[24] Ye Z, Li Z, Xie M. Some improvements on adaptive genetic algorithms for reliability-related applications. Reliability Engineering & System Safety, 2017, 95(2):120-126.
[25] Silver D, Huang A, Maddison C J et al. Mastering the game of Go with deep neural networks and tree search. Nature, 2016, 529(7587):484-489.
[26] Sivaraj R, Ravichandran D. A review of selection methods in genetic algorithms. International Journal of Engineering Science and Technology, 2011, 3(5):3792-3797.
[27] Pandey H M, Shukla A, Chaudhary A et al. Evaluation of genetic algorithm's selection methods. In Proc. the 3rd International Conference on Information Systems Design and Intelligent Applications, January 2016, pp.731-738.
[28] Krishnaswamy S, Viamontes G F, Markov I L et al. Accurate reliability evaluation and enhancement via probabilistic transfer matrices. In Proc. the 2005 Design, Automation and Test in Europe, March 2005, pp.282-287.
[29] Ji Z, Xia Q, Meng G. A review of parameter learning methods in Bayesian network. In Proc. the 11th International Conference on Intelligent Computing, Part Ⅲ, Aug. 2015, pp.3-12.
[30] Shahani A, Natu N, Badami A. A Genetic Algorithm for VLSI Floorplanning:An Intuitive Approach to Optimisation and Miniaturisation of IC. LAP LAMBERT Academic Publishing, 2012.
No related articles found!
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] 戴汝为; 王珏; 陈欣;. A Syntactic-Semantic Approach for Pattern Recognition and Knowledge Representation[J]. , 1988, 3(3): 161 -172 .
[2] 蔡士杰; 张福炎;. A Fast Algorithm for Polygon Operations[J]. , 1991, 6(1): 91 -96 .
[3] 林作铨; 石纯一;. A Generalization of Circumscription[J]. , 1992, 7(2): 97 -104 .
[4] 廖先湜; 金兰;. Rendezvous Facilities in a Distributed Computer System[J]. , 1995, 10(2): 188 -192 .
[5] 王显著; 廖恒; 李三立;. DYNAMEM-A Microarchitecture for Improving Memory Disambiguation at Run-Time[J]. , 1996, 11(6): 589 -600 .
[6] 高文; 陈熙霖;. A Stochastic Approach for Blurred Image Restoration and Optical Flow Computation on Field Image Sequence[J]. , 1997, 12(5): 385 -399 .
[7] 傅育熙;. Reaction Graph[J]. , 1998, 13(6): 510 -530 .
[8] 李晓山;. Decidability of Mean Value Calculus[J]. , 1999, 14(2): 173 -180 .
[9] 刘斌; 卢增祥; 甘泉; 冯翱; 王普;. Infomarker—A New Internet Information Service System[J]. , 2000, 15(3): 300 -304 .
[10] 刘喜成; 李仲同;. Implementation of a Prototype VoIP System[J]. , 2000, 15(5): 480 -484 .
版权所有 © 《计算机科学技术学报》编辑部
本系统由北京玛格泰克科技发展有限公司设计开发 技术支持：support@magtech.com.cn
总访问量：