摘要
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.
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.
