Figure 1. Test Environment
Massoud Shadfar, Armita Paymandoust, Zainalabedin Navabi
Electrical and Computer Engineering Department
Faculty of Engineering, Campus No. 2
University of Tehran
14399, Tehran IRAN
Tel: +98-21-800-8485; Fax: +98-21-646-1024
Email: navabi@ece.ut.ac.ir
VHDL gate level models for fault simulation by the Critical Path Tracing method have been developed. These models will be used by a VHDL test bench for pseudo random test generation. Modeling strategy and the test environment will be described in this paper.
In this paper we will use VHDL gate models in an integrated environment for pseudo random test generation. VHDL models for fault collapsing will generate a reduced fault list. A VHDL test bench will read faults from the reduced fault list and apply random tests patterns to VHDL models for fault simulation. When a random test is found to detect faults from the fault list, the test pattern and the faults detected by this pattern are recorded. At the end of the test process, test patterns and faults that remain undetected along with achieved fault coverage will be listed in a file.
Fault simulation is done by the Critical Path Tracing method. In this method a test is applied and circuit lines with values that influence a primary output value are identified. Stuck-at-value faults on such lines are detected by the input test pattern.
The following section consists of a description of a test environment for test application and fault detection. Section 3 of this paper presents fault list generation method and its corresponding file format. Section 4 details the fault simulation method by use of Critical Path Tracing VHDL models. In Section 5, method of random generation of test vectors will be described. Section 6 will show a VHDL test bench for test application and fault detection. Conclusions including past work and present direction will be given in Section 7.
Our proposed environment consists of a VHDL netlist which will be used in two separate test benches. As shown in Figure 1, the first test bench uses fault collapsing gate models for the generation of a reduced fault list. This test bench generates a list of distinguishable faults. This list will be used by a second VHDL test bench for test vector generation. This test bench uses Critical Path Tracing models for simulation of the circuit and fault detection.
Figure 1. Test Environment
TYPE.GATE ID [ SINGLE STUCK FAULT LIST ] ... AND2( 108 ) [ I1:none ;I2:sa_1 ;O1:sa_1 ] OR2 ( 109 ) [ I1:none ;I2:none ;O1:sa_0 ] NOR2( 111 ) [ I1:none ;I2:sa_0 ;O1:sa_1 ] NOT ( 112 ) [ O:sa_1, sa_0 ] ... |
Tests Applied: 011111000101011 011100100100010 111100010001000 100010101000000 . . . Resulting fault coverage: 88% Faults that remain undetected are: AND2( 76 ) [ I2:sa_1 ] OR2 ( 23 ) [ O1:sa_0 ] NOR2( 45 ) [ I1:sa_1 ] NAND2( 48 ) [ I2:sa_0 ; O1:sa_1 ] . . . |
Critical path tracing is used for finding faults detected by a specific test vector. For this purpose, the test is applied to the inputs of the fault free circuit. This vector determines all intermediate circuit logic values. If a line value is forced to its complementary value, and this value causes the output of the circuit to toggle, then we can conclude that a fault on the line with the new complementary value can be detected at the output. Such line is said to be a critical line of the circuit with the applied test. Finding critical lines becomes more involved in circuits with re-convergent fanouts. To provide necessary background for describing our critical path tracing, an example with and without fanout will be presented.
Figure 4. Example of CPT in a fanout-free circuit
Figure 5 shows a circuit with a re-convergent fanout, with two different test vectors. The argument used in conjunction with Figure 4 for finding critical path lines can be used to mark all the critical lines of Figure 5 except the fanout stem. The decision to mark the fanout stem critical depends on the effects of the stem on the gates influenced by this line. With the 111 input vector toggling the value on the fanout stem does not cause the output to change value. On the other hand, if the input vector is 110, changing the fanout stem value to 0 causes the output to change from 1 to 0. Therefore the fanout stem in Figure 5 with the 111 input test vector is not critical, but the test input of 110 makes the fanout stem a critical line.
Figure 5. CPT with re-convergent fanout
3.1 CPT METHOD
In the original critical path tracing method [1], primary input values are propagated to all circuit lines. The circuit is traced from output to input for identifying critical lines in a manner similar to what was described in the previous section. In the process of this tracing, when a fanout is encountered, a simulation phase will determine if the effect of changing the value of a fanout stem will be marked as critical. In order to reduce the size of the part of the circuit that is simulated, a partitioning of the circuit is done to simulate only up to the point whose effect on the output is known.
From the above discussion it is clear that critical path tracing by this method requires much forward simulation and backward propagation in an iterative fashion. In addition, partitioning of the circuit into isolated parts with inputs influenced by fanout stem and outputs influencing the primary output is a time consuming process.
Above all, the case mentioned before, in which a fanout stem can be critical even if none of its branches are critical, cannot be handled by the standard CPT method. This is because, the method requires a critical path through branches to reach to a fanout.
3.2. ONE PASS CRITICAL PATH TRACING
Considering the problems associated with the original critical path tracing algorithm, we have developed a new method that eliminates the need for any partitioning or partial simulation of the circuit. In one pass CPT, simulation is only necessary at the beginning when a test vector is applied. Decision to mark a stem as critical will be based on the information that is passed from gates that are driven by the fanout branches back to the fanout node. In general one pass CPT is centered around the facts that 1) A gate with critical output locally decides on its input lines being critical, and 2) Fanout stems require information from all their branches before they can declare a stem as being critical. Therefore gates, interconnecting lines and fanout nodes must cooperate in providing necessary information to gates and fanout nodes.
3.2.1 GATE BEHAVIOR
Based on the type and the output value of a gate, a gate makes certain decisions about its input lines. A gate may declare an input line as being critical or it may declare an input as being blocked from becoming critical by another one of its inputs. The expected behavior of a gate is to identify each of its inputs as being critical or being blocked. In a two input AND gate, shown in Figure 6, if only one of the inputs of the gate has a controlling value (Figure 6-a) that input line is critical and the other is blocked, from being critical. If both inputs of a two input gate have controlling values, Figure 6-b, then each input is considered as blocked by the other input. Therefore, both inputs will be referred to being as blocked. In this case if both inputs change simultaneously, the output value will toggle. As shown in Figure 6-c, if both inputs of a gate have non-controlling values then both inputs are critical, since changing each input will change the output value. The significance of a gate in one pass CPT is only due to its critical and blocked input lines.
Figure 7. Gate notations
a) One critical and one blocked input
b) Two blocked inputs c) Two critical inputs.
An interconnection of several gates for critical path tracing can be done by use of a graph using the notation presented in section 3.1. Such a graph will be refereed to as critical path graph (CPG). Figure 8 shows a simple AND-OR circuit and its corresponding CPG.
Figure 8. Critical path graph
Figure 9. Path kinds
In addition to gates determining the kind of their input lines, the other decision made in one pass critical path tracing is the decision to mark a fault stem as being critical to not critical. This decision is made by a fanout node and will be based on the types of paths (CP and BPn) associated with fanout branches. The following definition is needed for study of fanout behavior.
Figure 10. Rule a replaces two converging critical paths
Figure 12. Rule c replaces two converging Bps with a CP
An example illustrates application of the above rules to a fanout for finding faults detected by an input vector. Circuit shown in Figure 13-a has reconvergent fanouts with three edges at the divergence point and two convergence points. For input ABCDE=01000 all line values are first calculated. Based on these values and gate characteristics critical and blocked lines will be known, as shown in Figure 13.b. Whether stem B is critical or not will be decided by the application of Rules a, b, and c.
Initially a loop can be observed between the fanout node and gates a, b, and d. Applying Rule c to this loop reduces it to a straight line, and therefore converting the graph of Figure 13-b to that of Figure 14-a. This graph also contains a loop, for the reduction of which Rule a can be applied. The resulting graph is shown in Figure 14-b.
(a)
(b)
Figure 13. Applying Rules a,b, c, and d
(a)
(b)
Figure 14. Continuing example of Figure 13
The above rules and their application to logic circuits can be easily implemented in a concurrent programming environment. The above discussion facilitates the presentation of VHDL gate models for performing critical path tracing.
After the initial simulation, and after several delta times, all node values will be known. Based on its output values each gate produces CP or BP on its inputs. Primary outputs, being always on a critical path, initiate critical value determination of the output gates. Therefore gate models may observe a CP transaction on their outputs. Such a gate will decide CP or BP on its inputs. This information will eventually be collected and observed at a fanout node. In order to keep track of paths leading to a fanout, each gate collectively send its identification along with the kind information (Critical or Blocked) on its input line signals.
Faults detected are reported by the individual gates and PIs, and POs. Fault detected at a fanout stem will be reported by gates or PIs immediately connected to it. In the CPT implementation for pseudo random test generation, reporting is done by crossing out detected faults in a shared variable structure that lists all circuit faults that are to be detected. The VHDL implementation of critical path tracing consists of types, resolution function, gate models and utility programs. In this section each of these parts will be described. The report shared variable will be addrresed in a later section. Before this description, we will make definitions for relating rules of Section 3 to the VHDL coding.
3.3.1 INFORMATION FIELDS
Interconnecting lines between gates carry information in the forward and backward directions. In the forward direction only logic values are transmitted. In the backward direction information regarding critical, blocked, and the index n number of blocked paths (CP, BPn) are transmitted. The logical values will be referred to as logic, and the information needed for critical path algorithm will be referred to as path_info.
3.3.2 CRITICAL LEVELS
Path_info of a node whose forward logical value is not known (U) is none. The code value for this state is -3. At the beginning simulation all line path_info is none. After an input vector is applied to the primary inputs, logic values propagate to the outputs changing logic values to '0' or '1', while keeping path_info values to none. The process of determining path_info begins with outputs identifying themselves as critical (CP). CP is a value that is assigned to the path_info and has a code value of 0. Path_info propagate backwards from output towards the inputs of the circuit. On their way, all lines will receive different values of path_info. If an input of a gate is blocking critical path of another input, its path_info becomes BP1 which has a code value of 1. A BPn blocked by another input becomes BPn+1, increasing its code value by 1.
The level of a path_info is determined by its code value. Therefore, CP with level 0 has the lowest level and a BP5 with level 5 has the highest level. Two adjacent levels are those whose codes are consecutive numbers of 0, or above (i.,e., none is not included).
If a line is neither critical nor it is blocking a critical path, it is UNCP and has a code value of negative 2. A similar line, but one that also contains fanout stem information has a code of -1 and will be referred to as UNCP_I.
3.3.3 LINE TYPE
A line type for containing logical and path information is shown in Figure 15. This is a record named fsim with logic and path_info elements.
TYPE fsim IS RECORD logic : imp; path_info : bkt; END RECORD; |
The path_info element is an array of 4 rows and 20 columns of integers. Path information on each line is included in this array. In each row, the first integer specifies a code value of a path. Therefore a line that is part of a critical path has a 0 value in position (0,0) of the path_info array. The rest of the integers in a row of this array contain gate identifications for all gates that a critical path has gone through. The other three rows contain similar information which will be described in the following sections.
Figure 16. General CPT model structure
3.3.4 GATE MODELS
A gate model has inputs and outputs of type fsim and INOUT mode. A model is responsible for forward propagation of logic values, and backward (output to input) propagation of path information. A model is also responsible for reporting its inputs and outputs on which faults are being detected. Each gate has a unique identification number passed to it via a generic clause. A single process in the statement part of a gate architecture handles logical and path information generation. In the following discussion we will use a two input NAND gate for demonstrating the behavior of critical path tracing models. A general outline of a gate model is shown in Figure 16.
............ WAIT UNTIL i1.logic /= 'U' AND i2.logic /= 'U'; in1 := i1.logic; in2 := i2.logic; out1 := in1 NAND in2; o.logic <= out1; .............. |
The code for generation of logic value on the output of a gate is shown in Figure 17. After none 'U' values are observed on all gate inputs, a gate uses logic field of its inputs and assigns proper value to the logic field of its output. At this time the gate goes in the backward mode and will only be sensitive to events on the path_info field of its output. When fault values for specific test vector have been crossed out from the shared variable fault list, gates will again go into forward mode and again become sensitive to events on their inputs. The process of re-initialization which operates after a gate has marked off its detected faults is shown in Figure 18.
............ --- initialization i1 <= none_U; i2 <= none_U; o <= none_U; --- wait until all lines in circuit initialized. WAIT FOR 10 PS; tn := tn + 1; ........ |
A gate waits until an event on its output changes path_info field of the output to a value other than none. This happens when a code value greater than -1 is placed on the path_info of an output. The code value of a path_info greater than -1 is an indication that the output is either on a critical (CP), or it on a blocked path (BPn). In this case, based on input logic values, path information for the path_info fields of the inputs will be determined and assigned to the fields of the individual inputs. The code section responsible for this behavior is shown in Figure 19.
......... ELSIF temp_o(1,1) > -1 THEN IF in1 = '0' AND in2 = '1' THEN temp_i1 := added_node(temp_o,id); temp_i2 := increment_depth(temp_o,id); ELSIF in1 = '1' AND in2 = '0' THEN temp_i1 := increment_depth(temp_o,id); temp_i2 := added_node(temp_o,id); ELSIF in1 = '0' AND in2 = '0' THEN temp_i1 := increment_depth(temp_o,id); temp_i2 := temp_i1; ELSE .......... |
Figure 20. A path information example
IF temp_o(1,1) = -1 THEN IF in1 = '1' AND in2 = '0' THEN temp_i1 := uncp; temp_i2 := temp_o; ELSIF in1 = '0' AND in2 = '1' THEN temp_i1 := temp_o; temp_i2 := uncp; ELSIF in1 = '0' AND in2 = '0' THEN temp_i1 := uncp; temp_i2 := uncp; ELSE temp_i1 := temp_o; temp_i2 := temp_o; END IF; |
3.3.5 FANOUT RESOLUTION
Although, all interconnecting lines are resolved, resolution of value is only significant at the fanout nodes, and that is only important when processing path information in the backward direction. The resolution function for this purpose is called backtracing which will be discussed here.
Drivers of the backtracing resolution function are path_info that reach a fanout from various gates. The resolution function makes a copy of all its drivers in a temporary buffer and starts processing and making modifications to this buffer using rules a, b, c of Section 3.2. Initially the resolution function searches for a path record which has the highest code value of all the other drivers. The highest code value corresponds to a path with most number of blockages. This path being blocked the most, represents part of an innermost loop. The part of the resolution function searching for the deepest BPn is shown in Figure 23.
FUNCTION backtracing (paths : int_4by20_vector) RETURN int_4by20 IS VARIABLE temp1, temp2 : int_4by20_vector(paths'RANGE); VARIABLE depth, util1 : INTEGER := 0; . . . BEGIN . . . FOR i IN paths'RANGE LOOP --Finding deepest path IF depth < temp1(i)(1,1) THEN depth := temp1(i)(1,1); END IF; END LOOP; |
......................
IF depth > 0 THEN ------------- construct and reject
FOR i IN depth DOWNTO 1 LOOP
-- path with i depth will be constructed.
FOR j IN paths'RANGE LOOP
IF temp1(j)(1,1) = i THEN
FOR l IN j + 1 TO (paths'LENGTH - 1) LOOP
IF temp1(l)(1,1) = i THEN
replace_check (
temp1(j), temp1(l), constructed, connection);
IF connection THEN
temp1(j) := constructed;
temp1(l) := none;
END IF;
END IF;
END LOOP;
END IF;
END LOOP;
FOR j IN paths'RANGE LOOP
---- path with i-1 depth is rejected
IF temp1(j)(1,1) = i THEN -- by path with i depth.
FOR l IN paths'RANGE LOOP
IF temp1(l)(1,1) = (i - 1) THEN
remove_check (
temp1(j), temp1(l), constructed, connection);
IF connection THEN
temp1(l) := constructed;
END IF;
END IF;
END LOOP;
END IF;
END LOOP;
END LOOP;
END IF;
........
|
As shown in Figure 25 the test generation testbench consists of a test controller and the circuit netlist. As described in the CPT section, the primary outputs have a special role in the activation of the CPT gate models and are instantiated separate from the circuit netlist.
Test Controller
CKT
PO
Read Falt Collapsing Data and Load into Shared Variable linked list.
Use LFSR technique for pseudo random test generation.
Initiate circuit, apply PRPG data, mark off PI detected faults.
In addition to the fault information, the total numberr of faults is also obtained from fault collapsing file and read into a shared variable. This value will be used for calculation of fault coverage.
Another process statement in the test controller is responsible for the generation of pseudo random test vectors. This process uses a polynomial and a seed as input for the PRPG shift register. With each clock a new test is generated.
TYPE g_faults; TYPE g_faults_ptr IS ACCESS g_faults; TYPE g_faults IS RECORD g_type : STRING (1 TO 6); id : POSITIVE; in_1 : faults; -- inverters use in1 in_2 : faults; out_1 : faults; link : g_faults_ptr; --for linked list; END RECORD; . . . SHARED VARIABLE fault_table : g_faults_ptr := NULL; |
As the critical information move in the backward direction towards the test controller outpiuts, the CPT gate models cross out detected faults in the shared variable fault linked list (Figure 27). < p>When the test controller receives the information on its outputs from the CPT gate models, its lines starts behaving as primary inputs and crosses out faults that are detected on these lines.
Before repeating the process of initializing the CPT models and applying a new test vector, the test controller checks for a target fault coverage. If this is satisfied, the test process terminates. At this time the list of undetected faults is extracted from the fault linked list and reported to an output file. An example of this file is shown in Figure 2. Other information such as the number of accomplished fault coverage are also reported to this output file.
If the test process is not to terminate, the PRPG clock is activated for it to generate another random test data. Reaching a given fault coverage or exhausting all random test data are two reasons for the test process to terminate.
5. Conclusion
We have shown vhdl models for fault collapsing and the use of such models for psuedo random test generation. The emphasis here was on the CPT method and its implemntation. More work is being done on the psudo random test generation and will be reported in a later paper.
This work is part of an on-going research on VHDL modeling strategies for test related applications and environments utilizing such models. In this work gate models for tasks such as test generation, fault collapsing, and fault simulation are being developed.
REFERENCES: