基于SAT的通路时延故障测试生成技术的研究
摘要
多年来,集成电路测试是制约我国集成电路工业的“瓶颈”。在半导体技术工艺跨入深亚微米甚至纳米时代的今天,仅仅基于固定型故障的测试已经不再满足测试与可靠性的要求。对时延故障进行有效测试,已经成为生产测试的核心环节和集成电路测试领域的热点问题。
本文基于布尔可满足性(SAT-based)从以下几个方面对通路时延故障的自动向量测试生成技术进行了研究,包括非鲁棒性测试,鲁棒性测试和跳变通路时延故障(transition path delay fault)测试,并提出了一种基于布尔可满足性的方法求解跳变通路时延故障模型下的测试问题。
一、研究了通路时延故障模型的测试生成算法。通过七值逻辑系统及其编码,将电路中的逻辑蕴含关系以合取范式(CNF)的形式表示出来,以达到将ATPG问题公式化为可满足性问题的目的。在电路公式化的基础上,添加相应的通路敏化条件形成最终的合取范式,并使用SAT求解器来求解。这种方式比传统方法更加方便,效率更高。
二、对跳变通路时延故障模型进行了研究。该模型是I. Pomeranz在2008年提出的新故障模型,本文对其进行了详细研究和分析,并且将之与通路时延故障模型进行了对比。这种模型是将通路时延故障模型和跳变时延故障模型结合起来的故障模型,主要用于测试通路子路径上小时延的积累所引起的跳变故障(transition faults)。跳变通路时延故障模型下的测试能够同时检测一条被测通路上的通路时延故障和所有的跳变故障。
三、在跳变通路时延故障模型下,提出了一种基于布尔可满足性的测试生成算法。该算法借鉴了非鲁棒性测试生成算法,增加了部份约束条件。使用该算法对ISCAS'85基准电路进行测试,其结果显示了该算法的有效性。
With the growing size and increasing complexity of VLSI circuits, the test generation for integrated circuit(IC) has been the bottleneck of IC industry of our country for years. The requirement of reliability can not be satisfied only by tests for stuck-at faults today, resulting in that Automatic test pattern generation (ATPG) for delay faults is becoming more and more significant.
In this paper, ATPG problems for path delay faults are researched based on Boolean satisfiability (SAT), including non-robust tests, robust tests and transition path delay fault model. Meanwhile, the corresponding algorithms are presented and implemented. The contents of this paper are outlined as follow.
1. Algorithms for test generation for path delay fault model are presented first. We discuss how to convert an ATPG problem to a SAT formula where both non-robust and robust test are considered. Based on the formulation of a circuit, constrains for sensitization of the circuit according to non-robust or robust tests are added, and the structured CNF formula is solved by a SAT-solver. Compare to the traditional algorithms, this approach is more convenient and efficient.
2. A new fault model:transition path delay fault model presented by I. Promeranz in 2008, which is used for the detection of the faulty behavior caused by cumulated effects of small extra delays along a sub path, is analyzed in detail and compared with the path delay fault model in this paper. A test for a transition path delay fault satisfies the additional requirement that it detects all the transition faults along the path.
3. An SAT-based algorithm for the test generation for transition path delay faults is proposed and compared with the path delay faults. Compared to an arbitrary non-robust test, a test for a transition path delay fault satisfies the additional requirement that it detects all the transition faults along the path. As a result, both the path delay fault and all the transition faults on the path are detected when an expected transition does not occur at the path output. The effectiveness of the algorithm is demonstrated on a set of ISCAS'85 benchmarks.
本文基于布尔可满足性(SAT-based)从以下几个方面对通路时延故障的自动向量测试生成技术进行了研究,包括非鲁棒性测试,鲁棒性测试和跳变通路时延故障(transition path delay fault)测试,并提出了一种基于布尔可满足性的方法求解跳变通路时延故障模型下的测试问题。
一、研究了通路时延故障模型的测试生成算法。通过七值逻辑系统及其编码,将电路中的逻辑蕴含关系以合取范式(CNF)的形式表示出来,以达到将ATPG问题公式化为可满足性问题的目的。在电路公式化的基础上,添加相应的通路敏化条件形成最终的合取范式,并使用SAT求解器来求解。这种方式比传统方法更加方便,效率更高。
二、对跳变通路时延故障模型进行了研究。该模型是I. Pomeranz在2008年提出的新故障模型,本文对其进行了详细研究和分析,并且将之与通路时延故障模型进行了对比。这种模型是将通路时延故障模型和跳变时延故障模型结合起来的故障模型,主要用于测试通路子路径上小时延的积累所引起的跳变故障(transition faults)。跳变通路时延故障模型下的测试能够同时检测一条被测通路上的通路时延故障和所有的跳变故障。
三、在跳变通路时延故障模型下,提出了一种基于布尔可满足性的测试生成算法。该算法借鉴了非鲁棒性测试生成算法,增加了部份约束条件。使用该算法对ISCAS'85基准电路进行测试,其结果显示了该算法的有效性。
With the growing size and increasing complexity of VLSI circuits, the test generation for integrated circuit(IC) has been the bottleneck of IC industry of our country for years. The requirement of reliability can not be satisfied only by tests for stuck-at faults today, resulting in that Automatic test pattern generation (ATPG) for delay faults is becoming more and more significant.
In this paper, ATPG problems for path delay faults are researched based on Boolean satisfiability (SAT), including non-robust tests, robust tests and transition path delay fault model. Meanwhile, the corresponding algorithms are presented and implemented. The contents of this paper are outlined as follow.
1. Algorithms for test generation for path delay fault model are presented first. We discuss how to convert an ATPG problem to a SAT formula where both non-robust and robust test are considered. Based on the formulation of a circuit, constrains for sensitization of the circuit according to non-robust or robust tests are added, and the structured CNF formula is solved by a SAT-solver. Compare to the traditional algorithms, this approach is more convenient and efficient.
2. A new fault model:transition path delay fault model presented by I. Promeranz in 2008, which is used for the detection of the faulty behavior caused by cumulated effects of small extra delays along a sub path, is analyzed in detail and compared with the path delay fault model in this paper. A test for a transition path delay fault satisfies the additional requirement that it detects all the transition faults along the path.
3. An SAT-based algorithm for the test generation for transition path delay faults is proposed and compared with the path delay faults. Compared to an arbitrary non-robust test, a test for a transition path delay fault satisfies the additional requirement that it detects all the transition faults along the path. As a result, both the path delay fault and all the transition faults on the path are detected when an expected transition does not occur at the path output. The effectiveness of the algorithm is demonstrated on a set of ISCAS'85 benchmarks.
引文
[1]N. K. Jha and S. Gupta, Testing of Digital Systems, Cambridge University Press,2003.
[2]Breuer M A. The effect of races, delays and delay faults on test generation. IEEE Transactions on Computers,1974,22 (10):1078-1092.
[3]李华伟,闵应骅,李忠诚.通路时延测试综述[J].计算机工程与科学,2002,24(2)：80-83.
[4]S. Eggersgluss, G. Fey, and R. Drechsler, "SAT-based ATPG for path delay Faults in sequential circuits", IEEE International Symposium on Circuits and Systems,2007, pp.3671-3674.
[5]I. Pomeranz and S. M. Reddy, "Transition path delay faults:A new path delay fault model for small and large delay defects", IEEE Transactions on VLSI, vol.16, no.1,2008, pp.98-107.
[6]I. Pomeranz and S. M. Reddy, "Hazard-Based Detection Conditions for Improved Transition Path Delay Fault Coverage," IEEE Trans, on Computer-Aided Design of Integrated Circuits and Systems,2008, vol.29, pp.1449-1453.
[7]Chih-Ang Chen and S. K. Gupta, "A satisfiability-based test generator for path delay faults in combinational circuits", Design Automation Conference,1996, pp.209-214.
[8]S. Eggersgluss, R. Drechsler, "On the influence of boolean encodings in SAT-based ATPG for path delay faults", Multiple Valued Logic,2008, pp.94-99.
[9]J. Kim, J. Whittemore, J. P. Marques-Silva, and K. Sakallah, "On applying incremental satisfiability to delay fault testing", Design, automation and test in Europe,2000, pp.380-384.
[10]张月,李华伟,宫云战等.考虑串扰影响的时延测试[J].微电子学与计算机,2003,(11)：73-76.
[11]杨德才.算术运算电路的通路时延故障测试[D].成都：电子科技大学,2008.
[12]杨德才,谢永乐,陈光.并行前置树型加法器的通路时延故障测试[J].电子测量与仪器学报,2008,22(4)：12-16.
[13]杨德才,陈光,谢永乐.阵列乘法器通路时延故障的内建自测试[J].电子与信息学报,2009,31(1)：238-241.
[14]杨德才,谢永乐,陈光.基于累加器的时延故障单跳变测试序列生成[J].电子测量与仪器学报,2007,21(6)：1-4.
[15]C. J. Lin, S. M. Reddy, "On delay fault testing in logic circuits", IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol.6, no.5,1987, pp.694-703.
[16]E. S. Park, M. R. Mercer, "The total delay fault model and statistical delay fault coverage", IEEE Transaction on Computers,1992, vol.41, no.6, pp.688-698.
[17]A. K. Pramanick, S. M. Reddy, "On the fault coverage of gate delay fault detecting tests", IEEE Transaction on Computer-Aided Design of Integrated Circuits and Systems,1997, vol.16, no.1, pp.78-94.
[18]A. K. Pramanick, S. M. Reddy, "On the detection of delay faults", Proceedings of IEEE International Test Conference,1988, pp.845-856.
[19]G. L. Smith, "Model for delay faults based upon paths", Proceedings of IEEE International Test Conference,1985, pp.342-349.
[20]K. T. Cheng, "Transition fault testing for sequential circuits", IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems,1993, vol.12, no.12, pp. 1971-1983.
[21]J. A. Waicukauski, E. Lindbloom, "Transition fault simulation", IEEE Design & Test of Computers,1987, vol.4, no.2, pp.32-38.
[22]Y. Levendel, P. R. Menon, "Transition faults in combinational circuits:input transition test generation and fault simulation", Proceeding of International Fault Tolerant Computing Symposium,1986, pp.278-283.
[23]K. Heragu, J. H. Patel, "Segment delay faults:a new fault model", Proceedings of VLSI Testing Symposium,1996, pp.32-39.
[24]K. Heragu, J. H. Patel, "SIGMA:a simulator for segment delay faults", Proceedings of IEEE/ACM International Conference on Computer-Aided Design,1996, pp.502-508.
[25]K. Hyungwon, J. P. Hayes, "Delay fault testing of IP-based designs via symbolic path modeling", IEEE Transactions on Very Large Scale Integration (VLSI) Systems,2001, vol.9, no.5, pp.661-678.
[26]J. Yi, J. P. Hayes, "A fault model for function and delay testing", Proceedings of the IEEE European Test Workshop,2001, pp.27-34.
[27]J. Yi, J. P. Hayes, "The coupling fault model for function and delay faults", Journal of Electronic Testing:Theory and Applications,2005, vol.21, no.6, pp.631-649.
[28]X. J. Lin, J. Rajski, "Propagation delay fault:a new fault model to test delay faults", Proceedings of Asia and South Pacific Design Automation Conference,2005, pp.178-183.
[29]M. Favalli, "A fuzzy model for path delay fault detection", IEEE Transactions on Very Large Scale Integration (VLSI) Systems,2005, vol.13, no.8, pp.943-956.
[30]K. T. Cheng, C. H. Chen, "Generation of high quality non-robust tests for path delay faults", Proceedings of Design Automation Conference,1994, pp.365-369.
[31]K. T. Cheng, C. H. Chen, "Classification and identification of non-robust untestable path delay faults", IEEE Transactions Computer-Aided Design of Integrated Circuits and Systems,1996, pp.845-853.
[32]A. Krstic and K-T Cheng, Delay Fault Testing for VLSI Circuits, Kluwer Academic Publishers, 1998.
[33]L. Bushnell, D. Agrawal, Essentials and Electronic Testing for Digital, Memory and Mixed-Signal VLSI Circuits, Kluwer Acdemic Publishers,2002.
[34]Z. Lintao, M. Sharad, The Quest for Efficient Boolean Satisfiability Solvers. CAV2002, pp.17-36.
[35]刘歆.数字电路的故障测试模式生成方法研究[D].武汉：华中科技大学,2004.
[36]杨德才,谢永乐,陈光.基于布尔可满足性的层次化通路时延故障测试[J].电子测量与仪器学报,2008,22(3)：6-10.
[37]T. Larrabee, "Test pattern generation using Boolean satisfiability", IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol.11, no.1,1992, pp.4-15.
[38]P. Stephen, R. K. Brayton, and A. L. Sangiovanni-Vincentelli, "Combinational test generation using satisfiability", vol.15, no.9,1996, pp.1167-1176.
[39]K. Chandrasekar and M. S. Hsiao, "Integration of learning techniques into incremental satisfiability for efficient path-delay fault test generation", Design, Automation and Test in Europe,2005, pp.1002-1007.
[40]J. Balcarek, P. Fiser, and J. Schmidt, "On properties of SAT instances produced by SAT-based ATPGs", Multiple Valued Logic,2008, pp.94-99.
[41]L. Chichen, S. K. Gupta, and M. A. Breuer, "High quality robust tests for path delay faults", VLSI Test Symposium,1997, pp.88-93.
[42]D. Tille, R. Drechsler, "Incremental SAT instance generation for SAT-based ATPG", IEEE Workshop on Design and Diagnostics of Electronic Circuits and Systems,2008, pp.1-6.
[43]I. Pomeranz, S. M. Reddy, "Path selection for transition path delay faults", IEEE Transactions on Very Large Scale Integration(VLSI) Systems, vol.18, no.3,2010, pp.401.
[44]S. Stoica, "Robust test methods applied to functional design verification", Proceedings of IEEE International Test Conference,1999, pp.848-857.
[45]A. Volker Meyer, B. Walter Anheier, "Non-robust delay test pattern enhancement", Proceedings of International Conference on Electronics, Circuits and Systems,2002, vol.2, pp.453-456.
[46]A. Grastien, Anbulagan, "Incremental diagnosis of DES by satisfiability", Proceedings of European Conference on Artificial Intelligence,2008, vol.178, pp.787-788.
[47]B. S. So, C. R. Kime, "ICAT:incremental combinational ATPG", Proceedings of VLSI Test Symposium,1994, pp.106-113.
[48]S. Tragoudas, M. Michael, "Functional ATPG for delay faults", Proceeding of Ninth Great Lakes Symposium on VLSI,1999, pp.16-19.
[49]P. Mishra, C. Mingsong, "Efficient techniques for directed test generation using incremental satisfiability", IEEE International Conference on VLSI Design,2009, pp.65-70.
[50]D. Brand, V. S. Iyengar, "Identification of redundant delay faults", IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems,1994, vol.13, no.5, pp.553-565.
[2]Breuer M A. The effect of races, delays and delay faults on test generation. IEEE Transactions on Computers,1974,22 (10):1078-1092.
[3]李华伟,闵应骅,李忠诚.通路时延测试综述[J].计算机工程与科学,2002,24(2)：80-83.
[4]S. Eggersgluss, G. Fey, and R. Drechsler, "SAT-based ATPG for path delay Faults in sequential circuits", IEEE International Symposium on Circuits and Systems,2007, pp.3671-3674.
[5]I. Pomeranz and S. M. Reddy, "Transition path delay faults:A new path delay fault model for small and large delay defects", IEEE Transactions on VLSI, vol.16, no.1,2008, pp.98-107.
[6]I. Pomeranz and S. M. Reddy, "Hazard-Based Detection Conditions for Improved Transition Path Delay Fault Coverage," IEEE Trans, on Computer-Aided Design of Integrated Circuits and Systems,2008, vol.29, pp.1449-1453.
[7]Chih-Ang Chen and S. K. Gupta, "A satisfiability-based test generator for path delay faults in combinational circuits", Design Automation Conference,1996, pp.209-214.
[8]S. Eggersgluss, R. Drechsler, "On the influence of boolean encodings in SAT-based ATPG for path delay faults", Multiple Valued Logic,2008, pp.94-99.
[9]J. Kim, J. Whittemore, J. P. Marques-Silva, and K. Sakallah, "On applying incremental satisfiability to delay fault testing", Design, automation and test in Europe,2000, pp.380-384.
[10]张月,李华伟,宫云战等.考虑串扰影响的时延测试[J].微电子学与计算机,2003,(11)：73-76.
[11]杨德才.算术运算电路的通路时延故障测试[D].成都：电子科技大学,2008.
[12]杨德才,谢永乐,陈光.并行前置树型加法器的通路时延故障测试[J].电子测量与仪器学报,2008,22(4)：12-16.
[13]杨德才,陈光,谢永乐.阵列乘法器通路时延故障的内建自测试[J].电子与信息学报,2009,31(1)：238-241.
[14]杨德才,谢永乐,陈光.基于累加器的时延故障单跳变测试序列生成[J].电子测量与仪器学报,2007,21(6)：1-4.
[15]C. J. Lin, S. M. Reddy, "On delay fault testing in logic circuits", IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol.6, no.5,1987, pp.694-703.
[16]E. S. Park, M. R. Mercer, "The total delay fault model and statistical delay fault coverage", IEEE Transaction on Computers,1992, vol.41, no.6, pp.688-698.
[17]A. K. Pramanick, S. M. Reddy, "On the fault coverage of gate delay fault detecting tests", IEEE Transaction on Computer-Aided Design of Integrated Circuits and Systems,1997, vol.16, no.1, pp.78-94.
[18]A. K. Pramanick, S. M. Reddy, "On the detection of delay faults", Proceedings of IEEE International Test Conference,1988, pp.845-856.
[19]G. L. Smith, "Model for delay faults based upon paths", Proceedings of IEEE International Test Conference,1985, pp.342-349.
[20]K. T. Cheng, "Transition fault testing for sequential circuits", IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems,1993, vol.12, no.12, pp. 1971-1983.
[21]J. A. Waicukauski, E. Lindbloom, "Transition fault simulation", IEEE Design & Test of Computers,1987, vol.4, no.2, pp.32-38.
[22]Y. Levendel, P. R. Menon, "Transition faults in combinational circuits:input transition test generation and fault simulation", Proceeding of International Fault Tolerant Computing Symposium,1986, pp.278-283.
[23]K. Heragu, J. H. Patel, "Segment delay faults:a new fault model", Proceedings of VLSI Testing Symposium,1996, pp.32-39.
[24]K. Heragu, J. H. Patel, "SIGMA:a simulator for segment delay faults", Proceedings of IEEE/ACM International Conference on Computer-Aided Design,1996, pp.502-508.
[25]K. Hyungwon, J. P. Hayes, "Delay fault testing of IP-based designs via symbolic path modeling", IEEE Transactions on Very Large Scale Integration (VLSI) Systems,2001, vol.9, no.5, pp.661-678.
[26]J. Yi, J. P. Hayes, "A fault model for function and delay testing", Proceedings of the IEEE European Test Workshop,2001, pp.27-34.
[27]J. Yi, J. P. Hayes, "The coupling fault model for function and delay faults", Journal of Electronic Testing:Theory and Applications,2005, vol.21, no.6, pp.631-649.
[28]X. J. Lin, J. Rajski, "Propagation delay fault:a new fault model to test delay faults", Proceedings of Asia and South Pacific Design Automation Conference,2005, pp.178-183.
[29]M. Favalli, "A fuzzy model for path delay fault detection", IEEE Transactions on Very Large Scale Integration (VLSI) Systems,2005, vol.13, no.8, pp.943-956.
[30]K. T. Cheng, C. H. Chen, "Generation of high quality non-robust tests for path delay faults", Proceedings of Design Automation Conference,1994, pp.365-369.
[31]K. T. Cheng, C. H. Chen, "Classification and identification of non-robust untestable path delay faults", IEEE Transactions Computer-Aided Design of Integrated Circuits and Systems,1996, pp.845-853.
[32]A. Krstic and K-T Cheng, Delay Fault Testing for VLSI Circuits, Kluwer Academic Publishers, 1998.
[33]L. Bushnell, D. Agrawal, Essentials and Electronic Testing for Digital, Memory and Mixed-Signal VLSI Circuits, Kluwer Acdemic Publishers,2002.
[34]Z. Lintao, M. Sharad, The Quest for Efficient Boolean Satisfiability Solvers. CAV2002, pp.17-36.
[35]刘歆.数字电路的故障测试模式生成方法研究[D].武汉：华中科技大学,2004.
[36]杨德才,谢永乐,陈光.基于布尔可满足性的层次化通路时延故障测试[J].电子测量与仪器学报,2008,22(3)：6-10.
[37]T. Larrabee, "Test pattern generation using Boolean satisfiability", IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol.11, no.1,1992, pp.4-15.
[38]P. Stephen, R. K. Brayton, and A. L. Sangiovanni-Vincentelli, "Combinational test generation using satisfiability", vol.15, no.9,1996, pp.1167-1176.
[39]K. Chandrasekar and M. S. Hsiao, "Integration of learning techniques into incremental satisfiability for efficient path-delay fault test generation", Design, Automation and Test in Europe,2005, pp.1002-1007.
[40]J. Balcarek, P. Fiser, and J. Schmidt, "On properties of SAT instances produced by SAT-based ATPGs", Multiple Valued Logic,2008, pp.94-99.
[41]L. Chichen, S. K. Gupta, and M. A. Breuer, "High quality robust tests for path delay faults", VLSI Test Symposium,1997, pp.88-93.
[42]D. Tille, R. Drechsler, "Incremental SAT instance generation for SAT-based ATPG", IEEE Workshop on Design and Diagnostics of Electronic Circuits and Systems,2008, pp.1-6.
[43]I. Pomeranz, S. M. Reddy, "Path selection for transition path delay faults", IEEE Transactions on Very Large Scale Integration(VLSI) Systems, vol.18, no.3,2010, pp.401.
[44]S. Stoica, "Robust test methods applied to functional design verification", Proceedings of IEEE International Test Conference,1999, pp.848-857.
[45]A. Volker Meyer, B. Walter Anheier, "Non-robust delay test pattern enhancement", Proceedings of International Conference on Electronics, Circuits and Systems,2002, vol.2, pp.453-456.
[46]A. Grastien, Anbulagan, "Incremental diagnosis of DES by satisfiability", Proceedings of European Conference on Artificial Intelligence,2008, vol.178, pp.787-788.
[47]B. S. So, C. R. Kime, "ICAT:incremental combinational ATPG", Proceedings of VLSI Test Symposium,1994, pp.106-113.
[48]S. Tragoudas, M. Michael, "Functional ATPG for delay faults", Proceeding of Ninth Great Lakes Symposium on VLSI,1999, pp.16-19.
[49]P. Mishra, C. Mingsong, "Efficient techniques for directed test generation using incremental satisfiability", IEEE International Conference on VLSI Design,2009, pp.65-70.
[50]D. Brand, V. S. Iyengar, "Identification of redundant delay faults", IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems,1994, vol.13, no.5, pp.553-565.