A TPG system, SABATPG, is given based on a generic structural model of large circuits. Three techniques of partial implication, aftereffect of identified undetectable faults and shared sensitization with new concepts ...A TPG system, SABATPG, is given based on a generic structural model of large circuits. Three techniques of partial implication, aftereffect of identified undetectable faults and shared sensitization with new concepts of localization and aftereffect are employed in the system to improve FAN algorithm. Experiments for the 10 ISCAS benchmark circuits show that the computing time of SABATPG for test generation is 19.42% less than that of FAN algorithm.展开更多
This paper presents modeling tools based on Boolean satisfiability (SAT) to solve problems of test generation for combinational circuits. It exploits an added layer to maintain circuit-related information and value ju...This paper presents modeling tools based on Boolean satisfiability (SAT) to solve problems of test generation for combinational circuits. It exploits an added layer to maintain circuit-related information and value justification relations to a generic SAT algorithm. It dovetails binary decision graphs (BDD) and SAT techniques to improve the efficiency of automatic test pattern generation (ATPG). More specifically, it first exploits inexpensive reconvergent fanout analysis of circuit to gather information on the local signal correlation by using BDD learning, then uses the above learned information to restrict and focus the overall search space of SAT-based ATPG. Its learning technique is effective and lightweight. The experimental results demonstrate the effectiveness of the approach.展开更多
Line justification is a basic factor in affecting the efficiency of algorithms for test generation.The existence of reconvergent fanouts in the circuit under test resalts in backtracks in the process of line justifica...Line justification is a basic factor in affecting the efficiency of algorithms for test generation.The existence of reconvergent fanouts in the circuit under test resalts in backtracks in the process of line justification.In order to reduce the number of backtracks and shorten the processing time between backtracks,we present a new algorithm called DLJ(dynamic line justification)in which two techniques are employed.1.A cost function called“FOCOST”is proposed as heuristic information to represent the cost of justifying a certain line.When the relations among the lines being justified are“and”,the line having the highest FOCOST should be chosen.When the relations are“or”,the line having the lowest FOCOST should be chosen.The computing of the FOCOST of lines is very simple.2. Disjoint justification cubes dynamically generated to perform backtracks make the backtrack number of the algorithm minimal.When the backtrace with cube C_1 does not yield a solution,the next cube to be chosen is C′_2=C_2-{C_1,C_2}.Experimental results demonstrate that the combination of the two techniques effectively reduces the backtracks and accelerates the test generation.展开更多
文摘A TPG system, SABATPG, is given based on a generic structural model of large circuits. Three techniques of partial implication, aftereffect of identified undetectable faults and shared sensitization with new concepts of localization and aftereffect are employed in the system to improve FAN algorithm. Experiments for the 10 ISCAS benchmark circuits show that the computing time of SABATPG for test generation is 19.42% less than that of FAN algorithm.
基金Supported by Joint Research Fund for Overseas Chinese Young Scholars (No. 50128503) and National Natural Science Foundation of China (No. 50390060)
文摘This paper presents modeling tools based on Boolean satisfiability (SAT) to solve problems of test generation for combinational circuits. It exploits an added layer to maintain circuit-related information and value justification relations to a generic SAT algorithm. It dovetails binary decision graphs (BDD) and SAT techniques to improve the efficiency of automatic test pattern generation (ATPG). More specifically, it first exploits inexpensive reconvergent fanout analysis of circuit to gather information on the local signal correlation by using BDD learning, then uses the above learned information to restrict and focus the overall search space of SAT-based ATPG. Its learning technique is effective and lightweight. The experimental results demonstrate the effectiveness of the approach.
文摘Line justification is a basic factor in affecting the efficiency of algorithms for test generation.The existence of reconvergent fanouts in the circuit under test resalts in backtracks in the process of line justification.In order to reduce the number of backtracks and shorten the processing time between backtracks,we present a new algorithm called DLJ(dynamic line justification)in which two techniques are employed.1.A cost function called“FOCOST”is proposed as heuristic information to represent the cost of justifying a certain line.When the relations among the lines being justified are“and”,the line having the highest FOCOST should be chosen.When the relations are“or”,the line having the lowest FOCOST should be chosen.The computing of the FOCOST of lines is very simple.2. Disjoint justification cubes dynamically generated to perform backtracks make the backtrack number of the algorithm minimal.When the backtrace with cube C_1 does not yield a solution,the next cube to be chosen is C′_2=C_2-{C_1,C_2}.Experimental results demonstrate that the combination of the two techniques effectively reduces the backtracks and accelerates the test generation.
