POWER-AWARE DYNAMIC ENCODING

Abstract

Dynamic power-aware encoding method and apparatus is presented based on a various embodiments described herein. The experimental results confirmed that a desirable reduction in the toggling rate in the decompressed test stimulus is achievable by reasonable overhead (ATPG time, hardware overhead and pattern inflation) typically without degradation of a compression ratio. The performed experimental evaluation confirms that the described embodiments can support aggressive scan compression, efficient dynamic pattern compaction and a reduction of toggling rate in the decompressed test stimulus.

Claims

1. An apparatus, comprising: an EDA tool adapted to transform a circuit design to include design-for-test circuitry, the design-for-test circuitry including: selection circuitry selectively coupling a plurality of test stimulus sources to a decompressor circuit for generation of a decompressed test stimulus for detecting fault in a circuit under test in the circuit design, the plurality of test stimulus sources including: a static test stimulus source; and a dynamic test stimulus source, wherein the selection circuitry selectively enables the dynamic test stimulus source.

2. The apparatus of claim 1, wherein the dynamic test stimulus source is selectively enabled for a subset of care bits based on a grouping mechanism.

3. The apparatus of claim 1, wherein the dynamic test stimulus source includes a circular register such that at least one bit of said circular register is coupled to each scan chain in the circuit under test.

4. The apparatus of claim 1, wherein the dynamic test stimulus source includes two circular registers such that each scan chain in the CUT is coupled to each of said two circular registers.

5. The apparatus of claim 1, wherein the decompressed test stimulus is generated based on a superposition of the static test stimulus source and the dynamic test stimulus source.

6. The apparatus of claim 1, wherein the design-for-test circuitry further comprises: a programmable controller generating control signals to control the selection circuitry.

7. An apparatus, comprising: an EDA tool controlling automatic test pattern generation with design-for-test circuitry of a circuit design, the design-for-test circuitry including: selection circuitry selectively coupling a plurality of test stimulus sources to the decompressor circuitry for generation of a decompressed test stimulus for detecting fault in a circuit under test in the circuit design, the plurality of test stimulus sources including: a static test stimulus source; and a dynamic test stimulus source, wherein the selection circuitry selectively enables the dynamic test stimulus source.

8. The apparatus of claim 7, wherein the dynamic test stimulus source is selectively enabled for a subset of care bits based on a grouping mechanism.

9. The apparatus of claim 7, wherein the dynamic test stimulus source includes a circular register such that at least one bit of said circular register is coupled to each scan chain in the circuit under test.

10. The apparatus of claim 7, wherein the dynamic test stimulus source includes two circular registers such that each scan chain in the CUT is coupled to each of said two circular registers.

11. The apparatus of claim 7, wherein the decompressed test stimulus is generated based on a superposition of the static test stimulus source and the dynamic test stimulus source.

12. The apparatus of claim 7, wherein the static test stimulus source generates same test data bits for two or more consecutive shift cycles.

13. The apparatus of claim 7, wherein the design-for-test circuitry further comprises: a programmable controller generating control signals to control the selection circuitry.

14. The apparatus of claim 13, wherein the automatic test pattern generation further generates the control variables for the programmable controller.

15. An apparatus, comprising: an EDA tool adapted to transform a circuit design to include design-for-test circuitry, the design-for-test circuitry including: decompressor circuitry for generation of a decompressed test stimulus for detecting faults in a circuit under test in the circuit design, the decompressor circuitry generates care bits based on a system of linear equations such that the system of linear equations includes: a first disjoint set of static variables; and a second disjoint set of dynamic variables, wherein equations of the system of linear equations include at least one variable from the second disjoint set of dynamic variables and the variables of said second disjoint set of dynamic variables are selectively enabled for a subset of the care bits.

16. The apparatus of claim 15, wherein the variables of said second disjoint set of dynamic variables are selectively enabled for the subset of care bits based on a grouping mechanism.

17. The apparatus of claim 15, wherein the variables of said second disjoint set of dynamic variables are loaded into a dynamic test stimulus source.

18. The apparatus of claim 15, wherein the dynamic test stimulus source includes a circular register such that at least one bit of said circular register is coupled to each scan chain in the circuit under test.

19. The apparatus of claim 15, wherein the dynamic test stimulus source includes two circular registers such that each scan chain in the CUT is coupled to each of said two circular registers.

20. An apparatus, comprising: an EDA tool controlling automatic test pattern generation with design-for-test circuitry of a circuit design, the design-for-test circuitry including: decompressor circuitry for generation of a decompressed test stimulus for detecting faults in a circuit under test in the circuit design, the decompressor circuitry generates care bits based on characteristic equations such that the characteristic equations include: at least one variable of a first disjoint set of static variables; and at least one variable of a second disjoint set of dynamic variables, wherein said at least one variables of said second disjoint set of dynamic variables are selectively enabled for a subset of the care bits.

21. The apparatus of claim 20, wherein the variables of said second disjoint set of dynamic variables are selectively enabled for the subset of care bits based on a grouping mechanism.

22. The apparatus of claim 20, wherein the variables of said second disjoint set of dynamic variables are loaded into a dynamic test stimulus source.

23. The apparatus of claim 22, wherein the dynamic test stimulus source includes a circular register such that at least one bit of said circular register is coupled to each scan chain in the circuit under test.

24. The apparatus of claim 22, wherein the dynamic test stimulus source includes two circular registers such that each scan chain in the CUT is coupled to each of said two circular registers.

25. An apparatus, comprising: an EDA tool for processing data based on design-for-test circuitry of a circuit design, the design-for-test circuitry including: decompressor circuitry for generation of a decompressed test stimulus based on characteristic equations such that the characteristic equations include: at least one variable of a first disjoint set of static variables; and at least one variable of a second disjoint set of dynamic variables, wherein said at least one variable of the second disjoint set of dynamic variables of the characteristic equations is selectively enabled.

26. The apparatus of claim 25, wherein the decompressed test stimulus includes care bits for detecting faults in a circuit under test in the circuit design, wherein the at least one variable of said second disjoint set of dynamic variables, is selectively enabled for a subset of the care bits based on a grouping mechanism.

27. The apparatus of claim 25, wherein the at least one variable of said second disjoint set of dynamic variables is loaded into a dynamic test stimulus source.

28. The apparatus of claim 27, wherein the dynamic test stimulus source includes a circular register such that at least one bit of said circular register is coupled to each scan chain in the circuit under test.

29. The apparatus of claim 27, wherein the dynamic test stimulus source includes two circular registers such that each scan chain in the circuit under test is coupled to each of said two circular registers.

30. The apparatus of claim 26, wherein processing data includes at least one of the following: reading a specification of the design-for-test circuitry, identification of the design-for-test circuitry, performing a design rule check, performing ATPG, performing simulation, performing fault simulation, and performing fault diagnosis.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0043] FIG. 1 is a block diagram of an IC with on-chip data compression capability.

[0044] FIGS. 2(a)-2(c) show decompressor schemes.

[0045] FIGS. 3(a)-3(b) show decompressor schemes with a reduced toggling rate.

[0046] FIGS. 4(a)-4(c) show selector circuitry to selectively modify the original test stimulus.

[0047] FIG. 4(d) shows a shadow register to selectively modify original test stimulus.

[0048] FIG. 5 shows a block diagram of the power-aware decompressor.

[0049] FIG. 6 illustrates the construction of a decompressor.

[0050] FIG. 7 illustrates the construction of a power-aware decompressor.

[0051] FIG. 8 shows a linear compressor with reduced time complexity for linear encoding.

[0052] FIG. 9 shows an example encoding with scan cells that depend on one static valuable and one dynamic valuable.

[0053] FIG. 10 shows and example of identifying encoding conflicts in a 2-partite system of linear equations.

[0054] FIG. 11 example of preventing encoding conflicts in a 2-partite system of linear equations.

[0055] FIG. 12 shows an example initial encoding of augmented decompressor.

[0056] FIG. 13 shows an example interface of an augmented decompressor with a tester.

[0057] FIG. 14 shows 4 scan chains with triplets and scan chains generated during ATPG.

[0058] FIG. 15 shows the system of the linear equations with a row for each care bit and a column for each variable.

[0059] FIG. 16 shows a system of linear equations for calculating a statics seed and another system of linear equations for calculating a dynamic seed.

[0060] FIG. 17 shows a resulting static stimulus and a resulting dynamic stimulus and a generated decompressed test stimulus.

[0061] FIG. 18 is a table of experimental results for static and dynamic encoding.

[0062] FIG. 19 is another table of compression results for static versus dynamic encoding.

[0063] FIG. 20 is a simplified block diagram of a computer system configured to run an EDA tool.

[0064] FIG. 21 illustrates EDA tools and process flow for integrated circuit design and manufacturing.

DETAILED DESCRIPTION

[0065] The following examples are specific non-limiting examples illustrating various advantageous features of the presented technology. Only a subset of features demonstrated in a single example may be in an embodiment of the presented technology. An embodiment of the presented technology may include features from multiple examples. The number and length of scan chains, the number and length of segments, number and type of seeds and variables, existence of toggling, toggling rate, and configurations are changeable with different embodiments.

[0066] In FIG. 5, a block diagram of the proposed power-aware decompressor scheme shows the following blocks: 1) dynamic test stimulus source; 2) static test stimulus source and 3) a programmable controller including a plurality of selectors such that each selector can selectively enable dynamic test stimulus for a group of scan cells called hereafter power-groups. Both test stimulus sources can be inserted in a circuit design by a DFT software tool such as Synopsys DFT Compiler. Two disjoint sets of test data called static variables and dynamic variables are stored into the static and dynamic test stimulus sources, respectively, and control variables are stored into the programmable controller. The content of these variables is calculated by an ATPG module such as Synopsys TetraMAX and stored into one or more test patterns based on a specific format. The control variables and the programmable controller divide scan cells into power-groups based on the following three criteria: [0067] a) per shift (e.g., shift cycles are associated with rows in a 2D scan cell array); b) per scan chains (e.g., scan chains are associated with columns in a 2D scan cell array) and c) combined as an intersection of selected chains and selected consecutive shift cycles (e.g., let a set of adjacent rows in a 2D array form a group of consecutive shift cycles and a set of columns in a 2D array form a group of scan chains; then all scan cells that belong in an intersection of said group of shift cycles and said group of scan chains forms a power-aware group of scan cells). Toggling in the static test stimulus is expected to be very low, which reduces power consumption and reduces temperature that would otherwise increase along with power consumption.

[0068] Typically, the static test stimulus may change per pattern, two or more consecutive shift cycles, or two or more patterns. In this way, the static test stimulus source generates test stimulus that stays constant for two or more consecutive shift cycles, or all shift cycles of one or more test patterns. Therefore, significant toggling in decompressed test stimulus is expected only in the selected shift cycles and the selected scan chains. In a particular case, if a power-group of scan cells is enabled then bits of the decompressed test stimulus which are loaded into the selected scan cells are calculated as a superposition of corresponding bits of the dynamic and static test stimulus while bits of the decompressed stimulus which are loaded into the remaining (non-selected) scan cells are determined by corresponding bits of the static test stimulus. In this way, the toggling rate in this non-selected scan cells will be minimized, which reduces power consumption and reduces temperature that would otherwise increase along with power consumption. More formally, different values are shifted into a scan chain in two consecutive shift cycles, resulting in switching activities at inputs of the associated combinational circuit. These switching activities produce 0 to 1 and 1 to 0 transitions that may propagate in the associated combinational circuit.

[0069] Recently, the augmented product codes have been successfully used for constructing space and time compactors as well as sequential linear decompressors, for example, in U.S. Pat. No. 7,949,921; U.S. Pat. No. 8,914,695; U.S. Pat. No. 9,134,378; and US patent application 20140095101, for Synopsys, all incorporated by reference herein. The following procedure describes a construction of a power-aware linear decompressor scheme.

[0070] Procedure 1: Let N.sup.3 scan chains be viewed as an NNN array and a unique triplet (x,y,z) be assigned to a chain in row x, column y and block z where N2. Augmented decompressor (ADC), ADC(N,4), consists of four registers R.sub.0, R.sub.1, . . . , R.sub.3 of length N and a linear expander which is constructed based on the following steps: (i) assign a unique triplet (x,y,z) to each scan chain where x,y,z{0, 1, 2, . . . , N1}; (ii) assign an index {0, 1, 2, . . . , N1} to flip-flops in each register; (iii) assign a unique formula {y, (x+z) mod N, x, (x+y+z) mod N} to each register R.sub.k where k=(0, 1, . . . , 3); and (iv) couple each scan chain (x,y,z) to one flip-flop in each register such that the value of the corresponding formula determines the index of the flip-flop in each register; and (v) couple all flip-flops such that register R.sub.2 and R.sub.3 forms circular registers.

[0071] Procedure 1 guarantees that any three scan cells are linearly independent if a circular register of the ADC(N,4) receives N-bit dynamic seed per N shift cycles. In this way, the static test stimulus is generated by registers R.sub.0 and R.sub.1 which typically receives one static seed per pattern. The dynamic test stimulus is generated by circular registers R.sub.2 and R.sub.3 which typically receive one dynamic seed per T shift cycles where TN and parameter T is called a scope of dynamic seeds.

[0072] FIG. 6 illustrates a construction of the ADC(3,4) based on Procedure 1. First, each register R.sub.0, R.sub.1, . . . , R.sub.3 is uniquely associated with a formula. Let triplets (0,1,0) and (1,1,2) be assigned to two scan chains under consideration. A linear expander is constructed by coupling each scan chain to one flip-flop in each register such that the value of the corresponding formula determines the index of the flip-flop. Next step is to configure register R.sub.2 and R.sub.3 as circular registers. In this way, the static test stimulus is generated by registers R.sub.0 and R.sub.1, which receive data and periodically shift data or do not shift data in order to minimize the toggling rate in the decompressed test stimulus. The dynamic test stimulus is generated by circular registers R.sub.2 and R.sub.3, which shift data and periodically receive data.

[0073] FIG. 7 shows a power-aware ADC(3,4) which is constructed based on Procedure 1. The static test stimulus source includes registers R.sub.0 and R.sub.1 and the dynamic test stimulus source includes registers R.sub.2 and R.sub.3. First, a unique triplet (x,y,z) is assigned to each scan chain in the CUT and a unique formula f(x,y,z) is assigned to each register. The linear expander is constructed by coupling each scan chain to one flip-flop in each register such that the value of the assigned formula determines the index of the flip-flop. Next, a programmable controller specified a selection mechanism based on grouping scan cells among the plurality of scan chains and consecutive shift cycles. Last, the programmable controller is coupled in such a way that the dynamic test stimulus is selectively enabled for one or more power-groups. As a result, each scan cell is associated with a set of variables which are loaded into registers R.sub.0, R.sub.1, R.sub.2 and R.sub.3. The said set of variables including two static variables from registers R.sub.0 and R.sub.1 and two dynamic variables from register R.sub.2 and R.sub.3 such that the dynamic variables can be selectively enabled. The toggling rate is reduced by enabling a subset of power-groups.

[0074] Dynamic Linear Encoding

[0075] The dynamic encoding cannot be directly associated with either linear or non-linear decompressors. For example, a major obstacle for incorporating the conventional linear encoding into the branch-and-bound search is its time complexity which can be further magnified by ATPG backtracking. FIG. 8 shows a linear decompressor that has the potential to significantly reduce the time complexity of the linear encoding. The proposed linear decompressor receives one static seed per pattern and one dynamic seed per shift cycle. In other words, the scope of static variables is one pattern and the scope of dynamic variables is one shift cycle. For simplicity, let the characteristic equation of each scan cell include one dynamic variable. As a result, the dynamic variables divide scan cells into groups. The linear encoding may use dynamic seeds for encoding the first care bits for each group of scan cells and the static seeds for encoding all remaining care bits. The potential speedup of the linear encoding will be of the order of O(r.sup.3) where r is the ratio between the number of dynamic and static variables. The drawback is that the limited scope of the dynamic variables reduces the encoding efficiency of the described decompressor. The encoding efficiency of the described compressor can be increased by increasing the scope of dynamic variables and if the characteristic equation of each scan cell includes two or more dynamic variables instead of one dynamic variable.

[0076] Encoding procedure: Let SLEs include two distinctive sets of variables called herein static and dynamic. A SLEs is k-partite if the dynamic variables are divided into k disjoint sets of variables such that each equation of the SLEs includes at most one dynamic variable of each disjoint set. Dynamic variables of a k-partite SLEs divide scan cells into groups such that all scan cells of a group depend on the same k dynamic variables. Let the first care bit of a linearly independent group be dynamic and all other care bits be static. The proposed encoding procedure divides a partite SLEs into a SLEs based on dynamic variables and a SLEs based on static variables such that i) for each dynamic care bit, the SLEs of the dynamic variables includes one dynamic equation and ii) for each static care bit, the SLEs of the static variables includes one augmented equation which is calculated as a superposition of characteristic equations of the static care bit and a set of relevant dynamic care bits. For independent groups, the set of relevant dynamic care bits includes the first care bit for the corresponding independent group. For a dependent group, the set of relevant dynamic care bits includes the first care bit of all independent groups which are associated with a dependent group.

EXAMPLE 1

[0077] FIG. 9 shows an example wherein the scan cells depend on one static variable and one dynamic variable. The conventional linear encoding generates SLEs having 12 variables. The resultant SLEs is 1-partite because each characteristic equation includes one dynamic variable. As a result, each dynamic variable can be uniquely associated with a group of scan cells. Also, all groups of scan cells are linear independent because they are uniquely associated with dynamic variable. Let c.sub.0, c.sub.1 and c.sub.2 be an ordered set of care bits which are generated during the branch-and-bound search. Care bits c.sub.0 and c.sub.1 are dynamic because they are the first care bit in group v.sub.4 and group v.sub.5, respectively. Next, c.sub.2 is the second care bit of group v.sub.4 therefore the SLEs must include an augmented equation for this care bit. In the particular case, a set of relevant dynamic care bits includes c.sub.0, i.e., the first care bit of the corresponding group v.sub.4. The characteristic equations of c.sub.0 and c.sub.2 are v.sub.0v.sub.4=c.sub.0 and v.sub.1v.sub.4=c.sub.1, respectively. Since both care bits c.sub.0 and c.sub.2 depend on v.sub.4 , the resultant augmented equation includes static variables only. In this way, the 1-partite SLEs is partitioned into SLEs based on the static variables and 1-partite SLEs based on the dynamic variables.

EXAMPLE 2

[0078] FIG. 10 shows an example for an identification of encoding conflicts for 2-partite LSEs. Let c.sub.0, c.sub.1, . . . , c.sub.5 be an ordered set of care bits during ATPG. All encoding conflicts in the resultant SLEs based on the dynamic variables can be identified using a graph such that i) each node is associated with a variable and ii) each vertex is associated with an equation and is labeled with the value of this linear equation. A linear dependency exists if the corresponding graph has a loop. An encoding conflict exists if the loop has an odd number of 1's. Let the SLEs based on the dynamic variables include the following dynamic equations: v.sub.0v.sub.1=c.sub.0, v.sub.1v.sub.2=c.sub.1, v.sub.2v.sub.3=c.sub.2, v.sub.3v.sub.4=c.sub.3, v.sub.4v.sub.5=c.sub.4 and v.sub.0v.sub.5=c.sub.5. FIG. 10 shows the SLEs and the corresponding graph. The presented graph has one loop and an encoding conflict exists if c.sub.0c.sub.1c.sub.2c.sub.3c.sub.4c.sub.5=1. Therefore, care bit c.sub.5 is a static because it belongs to a dependent group and c.sub.0, c.sub.1, c.sub.2, c.sub.3 and c.sub.4 are relevant dynamic care bits of static care bit c.sub.5.

EXAMPLE 3

[0079] FIG. 11 shows an example for a prevention of encoding conflicts for 2-partite LSEs. All dependencies in the SLEs based on the dynamic variable are derived based on a matrix which includes a row for each dynamic variable of the first disjoint set, a column for each dynamic variable of the second disjoint set and elements of the matrix contain the value of the corresponding linear equation. Four elements at the intersection of a pair of rows and a pair of columns form a quadruplet. An encoding conflict exists if any quadruplet includes an odd number of 1's. Let us reuse the equations which are defined by Example 2 wherein {v.sub.1, v.sub.3, v.sub.5} is the first set of dynamic variables and {v.sub.0, v.sub.2, v.sub.4} is the second set of dynamic variables. The resultant matrix has three rows and three columns such that each row and column is uniquely associated with one variable of each disjoint set, respectively. All encoding conflicts can be prevented if the last (fourth) element of each quadruplet is set to a value 0 or 1 such that all the quadruplets always contain an even number of 1's. As a result, values of scan cells in dependent groups g.sub.0k, g.sub.1k, . . . can be determined based on the previous care bits c.sub.0, c.sub.1, . . . , c.sub.k. In other words, let all static variables be assigned to a particular value 0 or 1 then the values of all scan cells in a dependent group can be determined based on the relevant dynamic care bits. Therefore, the next care bit is always encodable. In this way, the encoding conflict for the next care bit can be prevented. For example, c.sub.0, c.sub.1, c.sub.2, c.sub.3 and c.sub.4 are relevant care bits of dependent group g.sub.41. To prevent encoding conflict, all scan cells in the dependent group are set according to the relevant care bits. For example, a scan cell in dependent group g.sub.41 is determined based on the following equation: f(v)=c.sub.0c.sub.1c.sub.2c.sub.3c.sub.4 where f(v) is a characteristic equation of this scan cell. As a result, all linearly dependent scan cells based on the dynamic variables contain an even number of 1s. This embodiment demonstrates that the identification and prevention of encoding conflicts in the 2-partite SLEs is a computationally efficient operation.

[0080] A decompressed test stimulus generated by the ADC(N,4,T) can be viewed as a superposition of a static test sequence based on 2N-bit static seed in registers R.sub.0, and R.sub.1 and a dynamic test sequence based on 2N-bit dynamic seeds in circular registers R.sub.2 and R.sub.3 where N is the length of registers and T is a scope of dynamic seeds. Each scan chain is coupled to one bit of registers R.sub.2 and R.sub.3 therefore the value loaded in each scan cell depends on two dynamic variables. The resultant SLEs is 2-partite. Next, the encoding is decomposed into two independent steps: an initial encoding and a final encoding. The goals of the initial encoding are to identify the encoding conflicts as early as possible during branch-and-bound search and to calculate the static seeds based on the static variables. The goal of the final encoding is to calculate dynamic seeds based on dynamic variables when ATPG is completed. Let each scan cell be uniquely associated with a characteristic equation such that each characteristic equation includes two static variables and two dynamic variables. Let a dynamic equation of a care bit be calculated by substituting all static variables with their values in the corresponding characteristic equation. Therefore each dynamic seed divides the scan cells into N.sup.2 groups such that: (i) scan cells in a group depend on the same two dynamic variables; (ii) four groups of a quadruple are linearly dependent; and (iii) each quadruplet includes one dependent group and all other groups are independent.

[0081] The initial encoding is based on static variables and includes two phases: unconstrained and constrained. During the unconstrained encoding, each care bit is considered independent and does not imply values of other scan cells. The unconstrained encoding continues until the first encoding conflict or all static variables are assigned to either value 0 or 1. During the constrained encoding, each care bit implies the values of all scan cells in the corresponding group and all dependent groups. As a result, all necessary scan cell assignments are easily identified. This feature is advantageous and improves the efficiency of dynamic pattern compaction. The unconstrained initial encoding is based on the following rules: 1) the first care bit of an independent group is called a dynamic care bit and all other care bits are called static; 2) a relevant bit of an independent group is the first care bit (or the corresponding dynamic care bit); 3) relevant care bits of a dependent group are the first care bits of the corresponding independent groups; and 4) each static care bit and the relevant dynamic care bits are represented in the SLEs by one augmented equation which is calculated as a superposition of their characteristic equations. In this way, the size of the resultant SLEs is greatly reduced because a small subset of care bits (only static care bits) need to be included into the SLEs based on a small subset of variables (static variables). Dependent groups can be calculated using a graph or quadruplets in accordance with previous embodiments.

[0082] The final encoding is based on dynamic variables and includes the following steps: 1) determine a dynamic equation of each dynamic care bit by substituting all static variables with the values assigned during the initial encoding; 2) for T consecutive shift cycles, encode all dynamic care bits with available 2N dynamic variables where T is the scope of dynamic seeds and N is the length of circular registers.

EXAMPLE 4

[0083] FIG. 12 illustrates an initial encoding of the ADC(N,4,T) for N=3 and TN in accordance with some embodiments described herein. For simplicity, let scan chains of a CUT have length of T where T is the scope of dynamic seeds. First, scan cells are divided into 9 groups such that each group is associated with two dynamic variables. Let a set of care bits {c.sub.0, c.sub.1, . . . , c.sub.4} belong to five different groups {g.sub.0, g.sub.1, . . . , g.sub.4} such that the index determines an order of these care bits during ATPG. The left-hand side in FIG. 12 shows the dynamic equations of groups g.sub.0, g.sub.1, g.sub.4 that are valid for all scan cells in the corresponding group. Note that the dynamic equations of groups g.sub.0, g.sub.1, . . . , g.sub.4 are linearly independent. As a result, each one of these care bits can be uniquely associated with one dynamic variable (a pivot element) of circular registers R.sub.2 and R.sub.3. Next, four groups located at the intersection of a pair of rows and a pair of columns are linearly dependent and form a quadruplet. An encoding conflict exists if and only if a set of linearly dependent groups contains an odd number of 1's. To avoid encoding conflicts, the dynamic equation of the last group of a quadruplet is calculated as a superposition of the dynamic equations of the previous three groups. To illustrate this, the dependent groups of group g.sub.4 are labeled as g.sub.4j for j=(0,1, . . . ,4). Let the characteristic equations of care bit c.sub.i be f.sub.i(v)=c.sub.i for i=(0, 1, . . . , 7). Also, let care bit c.sub.5 be the second care bit in group go and care bits c.sub.6 and c.sub.7 be the first and second care bits in dependent group g.sub.44, respectively. Care bits c.sub.5, c.sub.6 and c.sub.7 are static and they need to be included in the SLEs. An augmented equation of care bit c.sub.5 is f.sub.0(v)f.sub.5(v)=c.sub.0c.sub.5. The augmented equation of care bit c.sub.6 is f.sub.0(v)f.sub.2(v)f.sub.4(v)f.sub.6(v)=c.sub.0c.sub.2c.sub.4c.sub.6. More formally, c.sub.6 is the first care bit of dependent group g.sub.44 of quadruplet g.sub.0, g.sub.2, g.sub.4, and g.sub.44. Therefore, to avoid encoding conflict, the augmented equation of c.sub.6 is calculated as a superposition of the characteristic equations of c.sub.6 and the first care bit of groups g.sub.0, g.sub.2 and g.sub.4, respectively. Similarly, the augmented equation of care bit c.sub.7 is f.sub.0(v)f.sub.2(v)f.sub.4(v)f.sub.7(v)=c.sub.0c.sub.2c.sub.4c.sub.7. Note that all augmented equations include only static variables because dynamic equations of each static care bit and its relevant dynamic care bit(s) are linearly dependent. Next, the dynamic equations of dynamic care bits are calculated by a substitution of all static variables in their characteristic equations f.sub.0(v)=c.sub.0, f.sub.1(v)=c.sub.1, . . . , f.sub.4(v)=c.sub.4. During the final encoding, all dynamic care bits within the scope of a dynamic seed form a SLEs which includes one equation for each dynamic care bit. The resultant SLEs includes 2N dynamic variables and up to 2N1 equations per dynamic seed.

Power-Aware Dynamic Encoding

[0084] Let ADC(N,4,T) be constructed based on Procedure 1 and include registers R.sub.0, R.sub.1, R.sub.2 and R.sub.3 where N is the length of registers and T is scope of dynamic seeds. The ADC(N,4,T) comprises a static test stimulus source including registers R.sub.0 and R.sub.1 and a dynamic test stimulus source including registers R.sub.2 and R.sub.3. Toggling in the decompressed test stimulus of the ADC(N,4,T) is minimized if dynamic variables are enabled for fewer scan cells. The proposed power-aware dynamic encoding is based on dividing scan cells in power-aware groups such that the dynamic variables are selectively enabled for a subset of power-aware groups. In contrast to the dynamic encoding, the power-aware dynamic encoding first tries to encode each care bit based on the static variables. If this step produces an encoding conflict for a care bit then the power-aware dynamic encoding enables the corresponding power-aware group. As a result, the linear equations of all care bits in this power-group include both two static variables and two dynamic variables. In other words, the linear equations of scan cells in enabled power-aware groups includes both static and dynamic variables and the linear equations of scan cells in disabled power-aware groups includes static variables only. The resultant 2-partite SLEs is processed based on the principles described in the previous embodiments. More formally, dynamic variables divide care bits in selected power-aware groups into groups of scan cells. The SLEs is updated such that (i) each care bit in the unselected power-aware groups is included in the SLE based on a static equation which is calculated by removing dynamic variables in the corresponding characteristic equation; (ii) all care bits in the selected power-aware groups need to be encoded based on their characteristic equations. Accordingly, the first care bits in an independent group of scan cells are considered dynamic and excluded from the SLEs while all remaining care bits in the selected power-aware groups are considered static and need to be included into the SLEs using their augmented equations as described in Example 4. In this way, the original SLEs is partitioned into SLEs based on static variables and SLEs based on dynamic variables. The unconstrained encoding continues until the number of the enabled power-aware groups is smaller than a specified limit and all static variables are assigned to a specific value. Encoding conflicts in the SLEs based on dynamic variables can be easily identified using a graph in accordance with the previous embodiments. During constrained encoding, all necessary scan cell assignments can be easily derived by SLEs based on dynamic variables using quadruplets for each successfully generated test cube. The static test stimulus is enabled for all scan cells while the dynamic test stimulus is enabled for a subset of power-aware groups. As a result, toggling in decompressed test stimulus may appear only in enabled power-aware groups.

EXAMPLE 5

[0085] FIG.14 shows four scan chains, the corresponding triplets (x,y,z) of each scan chain which are coupled to the power-aware ADC(3,4) and an ordered set of care bits c.sub.0, c.sub.1, . . . ,c.sub.4 as they are generated during ATPG. Let each of the scan chains under consideration belong to different power-aware group. The goal of the power-aware dynamic encoding is to enable as few power-aware groups as possible. The original SLEs is shown in FIG. 15 and includes a row for each care bit and column for each variable. Note that each row of the SLEs corresponds to a care bit and is specified by a characteristic equation of the corresponding scan cell (including both static and dynamic variables) as well as the value assigned to this scan cell during ATPG. Next, each care bit is initially included in SLEs based on static variables. In this way, all power-aware groups are initially disabled. An encoding conflict exists for care bits c.sub.3 and to resolve this conflict the corresponding power-aware group is enabled. The enabled power-aware group includes care bits c.sub.1 and c.sub.3. Since care bits c.sub.1 and c.sub.3 are the first care bits in the corresponding groups of scan cells they are treated as dynamic care bits. The corresponding rows of care bits c.sub.1 and c.sub.3 are removed from the SLEs based on static variables and included into the SLEs based on dynamic variables. FIG.16 shows the resultant SLEs for calculating static seed and the resultant SLEs for calculating dynamic seed where v.sub.0, v.sub.1, . . . , v.sub.5 are static variables and v.sub.6, v.sub.7, . . . , v.sub.11 are dynamic variables, respectively. The size of each SLEs is 2N where N is the length of each register of the power-aware ADC(N,4). One of the possible solutions is v.sub.0=1, v.sub.7=1, v.sub.8=1 and all other variables are equal to 0. FIG. 17 shows the resultant static test stimulus and dynamic test stimulus for this assignment of static and dynamic variables as well as the corresponding decompressed test stimulus which is calculated based on a superposition (XOR operation) of individual test bits. Toggling in the decompressed test stimulus is greatly reduced compare to the original dynamic encoding based on the original ADC scheme.

[0086] A person skilled of the art may improve the encoding flexibility, the encoding efficiency or other desirable properties of the decompressor scheme by changing the scope or purpose of variables from a tester. For example, one or more dynamic variables may be used or reused as static variables or control variables within one or more test patterns. An example of such an approach is described in the next paragraph.

[0087] Experimental Evaluation

[0088] Dynamic encoding was evaluated based on ADC(N,5,T). The ADC(N,5,T) consists of five shift registers of length N. Shift registers R.sub.0, R.sub.1, R.sub.3 and R.sub.4 are configured as circular registers. Circular registers R.sub.0 and R.sub.1 receive 2N-bit static seed per pattern and circular registers R.sub.3 and R.sub.4 receive 2N-bit dynamic seed per T shift cycles through 2N-bit shadow register where TN. Each seed contains one redundant bit that is shifted into shift register R.sub.2 and all the redundant bits are treated as static variables by the encoding algorithm. FIG. 13 shows an interface of the ADC to a tester. The embodiment shows that one or more dynamic variables may be used or reused as either static variables or control variables in order to improve the encoding flexibility or other characteristic of the decompressor scheme. Since the limited scope of the dynamic variables reduces the encoding efficiency of the ADC. The key question examined here is whether dynamic encoding can compensate for the higher encoding efficiency of static encoding.

[0089] In the performed experiment, the dynamic and static encoding are evaluated based on ten industrial cores presented in Table 1. First, the highest compression ratio for each core is determined such that a test coverage loss w.r.t. a legacy scan mode is within 0.01 percent. The number of the static and dynamic variables, the encoding efficiency, TATR, the number of patterns and test coverage difference w.r.t. the legacy scan mode of the ADC for each core is given in columns 5, 6, . . . and 10, respectively. A perfect linear decompressor is simulated by ADC(15,5,1) which receives 2N-bit dynamic seed per shift cycle. In this way, the probability of an encoding conflict of the perfect decompressor for the first k care bits is extremely low where k is the number of variables for the ADC(15,5,15). After the first k care bits for the perfect linear decompressor, each care bit is considered encodable with probability 0.5. As a result, the encoding efficiency of the perfect decompressor is very likely be equal to or larger than 1. TATR for the static and dynamic encoding is determined for different compression ratios (1, 2, 3 and 4 more variables w.r.t. the highest compression ratio). For the static encoding, an encoding conflict exists if a test cube cannot be encoded. Typically, this is an exit condition for fault merging that occurs during dynamic compaction. Table 2 summarizes for all cores the number variables, the encoding efficiency, TATR for the dynamic encoding, as well as TATR and test coverage differences in percent w.r.t. legacy scan mode for dynamic encoding and the static encoding with 1, 10 and 100 encoding conflicts, respectively. Based on these results, the dynamic encoding outperforms the static encoding for all compression ratios. For compression ratio 1, 2, 3 and 4, the dynamic encoding achieves 34, 17, 8 and 5 percent higher TATR than the static encoding, respectively. Also, the dynamic encoding consistently achieves higher test coverage than the static encoding. For more than two decades, the key objective for synthesis of linear decompressors is to maximize the encoding efficiency. This experiment demonstrates that the dynamic encoding is a key feature for optimizing the performance of the linear decompressors. In this sense, this document defines a new paradigm for synthesis of linear decompressors.

[0090] Dynamic power-aware encoding is evaluated based on the ADC(15,4,15) constructed based on Procedure 1. The experimental results confirmed that, for example, seventy percent reduction in the toggling rate in the decompressed test stimulus is achievable by reasonable overhead (ATPG time, hardware overhead and pattern inflation) typically without degradation of compression ratio. The performed experimental evaluation confirms that the described embodiments can support aggressive scan compression, efficient dynamic pattern compaction and a reduction of toggling rate in the decompressed test stimulus.

[0091] FIG. 20 is a simplified block diagram of a computer system configured to run an EDA tool to implement any of the methods and processes herein.

[0092] Computer system 110 typically includes a processor subsystem 114 which communicates with a number of peripheral devices via bus subsystem 112. These peripheral devices may include a storage subsystem 124, comprising a memory subsystem 126 and a file storage subsystem 128, user interface input devices 122, user interface output devices 120, and a network interface subsystem 116. The storage subsystem 128 includes non-transitory memory storing computer programs, and resources to configure the data processing systems as an EDA tool for test pattern generation, encoding, simulation, fault simulation and diagnosis for decompressed test stimuli with low toggling rate as described herein. The tool can comprise a data processor and storage configured to provide computer program instructions of the tool. Alternatively, the tool can comprise software modules on a computer readable medium in a nonvolatile manner.

[0093] The input and output devices allow user interaction with computer system 110. Network interface subsystem 116 provides an interface to outside networks, including an interface to communication network 118, and is coupled via communication network 118 to corresponding interface devices in other computer systems. Communication network 118 may comprise many interconnected computer systems and communication links. These communication links may be wireline links, optical links, wireless links, or any other mechanisms for communication of information, but typically it is an IP-based communication network. While in one embodiment, communication network 118 is the Internet, in other embodiments, communication network 118 may be any suitable computer network.

[0094] The physical hardware component of network interfaces are sometimes referred to as network interface cards (NICs), although they need not be in the form of cards: for instance they could be in the form of integrated circuits (ICs) and connectors fitted directly onto a motherboard, or in the form of macrocells fabricated on a single integrated circuit chip with other components of the computer system.

[0095] User interface input devices 122 may include a keyboard, pointing devices such as a mouse, trackball, touchpad, or graphics tablet, a scanner, a touch screen incorporated into the display, audio input devices such as voice recognition systems, microphones, and other types of input devices. In general, use of the term input device is intended to include all possible types of devices and ways to input information into computer system 110 or onto computer network 118.

[0096] User interface output devices 120 may include a display subsystem, a printer, a fax machine, or non visual displays such as audio output devices. The display subsystem may include a cathode ray tube (CRT), a flat panel device such as a liquid crystal display (LCD), a projection device, or some other mechanism for creating a visible image. The display subsystem may also provide non visual display such as via audio output devices. In general, use of the term output device is intended to include all possible types of devices and ways to output information from computer system 110 to the user or to another machine or computer system.

[0097] Storage subsystem 124 stores the basic programming and data constructs that provide the functionality of certain embodiments. For example, the various modules implementing the functionality of certain embodiments may be stored in storage subsystem 124. These software modules are generally executed by processor subsystem 114.

[0098] Memory subsystem 126 typically includes a number of memories including a main random access memory (RAM) 130 for storage of instructions and data during program execution and a read only memory (ROM) 132 in which fixed instructions are stored. File storage subsystem 128 provides persistent storage for program and data files, and may include a hard disk drive, a floppy disk drive along with associated removable media, a CD ROM drive, an optical drive, or removable media cartridges. The databases and modules implementing the functionality of certain embodiments of the invention may have been provided on a computer readable medium such as one or more CD-ROMs, and may be stored by file storage subsystem 128. The host memory 126 contains, among other things, computer instructions which, when executed by the processor subsystem 114, cause the computer system to operate or perform functions as described herein. As used herein, processes and software that are said to run in or on the host or the computer, execute on the processor subsystem 114 in response to computer instructions and data in the host memory subsystem 126 including any other local or remote storage for such instructions and data.

[0099] Bus subsystem 112 provides a mechanism for letting the various components and subsystems of computer system 110 communicate with each other as intended. Although bus subsystem 112 is shown schematically as a single bus, alternative embodiments of the bus subsystem may use multiple busses.

[0100] Computer system 110 itself can be of varying types including a personal computer, a portable computer, a workstation, a computer terminal, a network computer, a television, a mainframe, a server farm, or any other data processing system or user device. Due to the ever changing nature of computers and networks, the description of computer system 110 is intended only as a specific example for purposes of illustrating the preferred embodiments of the present invention. Many other configurations of computer system 110 are possible having more or less components than the computer system.

[0101] In addition, while the present invention has been described in the context of a fully functioning data processing system, those of ordinary skill in the art will appreciate that the processes herein are capable of being distributed in the form of a computer readable medium of instructions and data and that the invention applies equally regardless of the particular type of signal bearing media actually used to carry out the distribution. As used herein, a computer readable medium is one on which information can be stored and read by a computer system. Examples include a floppy disk, a hard disk drive, a RAM, a CD, a DVD, flash memory, a USB drive, and so on. The computer readable medium may store information in coded formats that are decoded for actual use in a particular data processing system. A single computer readable medium, as the term is used herein, may also include more than one physical item, such as a plurality of CD ROMs or a plurality of segments of RAM, or a combination of several different kinds of media. As used herein, the term does not include mere time varying signals in which the information is encoded in the way the signal varies over time.

[0102] FIG. 21 illustrates EDA tools and process flow for integrated circuit design and manufacturing.

[0103] Aspects of the invention can be used to support an integrated circuit design flow. At a high level, the process starts with the product idea (step 200) and is realized in an EDA (Electronic Design Automation) software design process (step 210). When the design is finalized, it can be taped-out (step 227). At some point after tape out, the fabrication process (step 250) and packaging and assembly processes (step 260) occur resulting, ultimately, in finished integrated circuit chips (result 270).

[0104] The EDA software design process (step 210) is itself composed of a number of steps 212-230, shown in linear fashion for simplicity. In an actual integrated circuit design process, the particular design might have to go back through steps until certain tests are passed. Similarly, in any actual design process, these steps may occur in different orders and combinations. This description is therefore provided by way of context and general explanation rather than as a specific, or recommended, design flow for a particular integrated circuit.

[0105] A brief description of the component steps of the EDA software design process (step 210) will now be provided.

[0106] System design (step 212): The designers describe the functionality that they want to implement, they can perform what-if planning to refine functionality, check costs, etc. Hardware-software architecture partitioning can occur at this stage. Example EDA software products from Synopsys, Inc. that can be used at this step include Model Architect, Saber, System Studio, and DesignWare products.

[0107] Logic design and functional verification (step 214): At this stage, the VHDL or Verilog code for modules in the system is written and the design is checked for functional accuracy. More specifically, the design is checked to ensure that it produces correct outputs in response to particular input stimuli. Example EDA software products from Synopsys, Inc. that can be used at this step include VCS, VERA, DesignWare, Magellan, Formality, ESP and LEDA products.

[0108] Synthesis and design for test (step 216): Here, the VHDL/Verilog is translated to a netlist. The netlist can be optimized for the target technology. Additionally, the design and implementation of tests to permit checking of the finished chip occurs. Example EDA software products from Synopsys, Inc. that can be used at this step include Design Compiler, Physical Compiler, DFT Compiler, Power Compiler, FPGA Compiler, TetraMA1, and DesignWare products.

[0109] Netlist verification (step 218): At this step, the netlist is checked for compliance with timing constraints and for correspondence with the VHDL/Verilog source code. Example EDA software products from Synopsys, Inc. that can be used at this step include Formality, PrimeTime, and VCS products.

[0110] Design planning (step 220): Here, an overall floor plan for the chip is constructed and analyzed for timing and top-level routing. Example EDA software products from Synopsys, Inc. that can be used at this step include Astro and Custom Designer products.

[0111] Physical implementation (step 222): The placement (positioning of circuit elements) and routing (connection of the same) occurs at this step, as can selection of library cells to perform specified logic functions. Example EDA software products from Synopsys, Inc. that can be used at this step include the Astro, IC Compiler, and Custom Designer products.

[0112] Analysis and extraction (step 224): At this step, the circuit function is verified at a transistor level, this in turn permits what-if refinement. Example EDA software products from Synopsys, Inc. that can be used at this step include AstroRail, PrimeRail, PrimeTime, and Star-RC1T products.

[0113] Physical verification (step 226): At this step various checking functions are performed to ensure correctness for: manufacturing, electrical issues, lithographic issues, and circuitry. Example EDA software products from Synopsys, Inc. that can be used at this step include the Hercules product.

[0114] Tape-out (step 227): This step provides the tape out data to be used (after lithographic enhancements are applied if appropriate) for production of masks for lithographic use to produce finished chips. Example EDA software products from Synopsys, Inc. that can be used at this step include the IC Compiler and Custom Designer families of products.

[0115] Resolution enhancement (step 228): This step involves geometric manipulations of the layout to improve manufacturability of the design. Example EDA software products from Synopsys, Inc. that can be used at this step include Proteus, ProteusAF, and PSMGen products.

[0116] Mask data preparation (step 230): This step provides mask-making-ready tape-out data for production of masks for lithographic use to produce finished chips. Example EDA software products from Synopsys, Inc. that can be used at this step include the CATS(R) family of products.

[0117] Parallel flow. The integrated circuit manufacturing flow includes a parallel flow, as follows:

[0118] (1) Develop individual process steps for manufacturing the integrated circuit. This can be modeled with EDA tools such as the Synopsys tools Sentaurus Process, Sentaurus Topography, and Sentaurus Lithography. The input information here is the process conditions like temperature, reactor ambient, implant energy, etc. The output information is the change in geometry or doping profiles or stress distribution.

[0119] (2) Integrate the individual process steps into the complete process flow. This can be modeled with EDA tools such as the Synopsys tool Sentaurus Process. The input information here is the collection of the process steps in the appropriate sequence. The output is the geometry, the doping profiles, and the stress distribution for the transistors and the space in between the transistors.

[0120] (3) Analyze performance of the transistor manufactured with this process flow. This can be done with EDA tools such as the Synopsys tool Sentaurus Device. The input information here is the output of step (3) and the biases applied to transistor terminals. The output information is the currents and capacitances for each bias combination. For silicon based processes or structures, much of the information about the materials needed for simulation of electrical behavior using these tools is well known. For other materials, it may be necessary to generate or provide material parameters like atomic structure, energy, and the like in order to support device and process scale simulations. An EDA tool for generating parameters like this is described herein.

[0121] (4) If necessary, modify the process steps and the process flow to achieve the desired transistor performance. This can be done iteratively by using tools such as the Synopsys tools mentioned above.

[0122] Once the process flow is ready, it can be used for manufacturing multiple circuit designs coming from different fabless companies. The EDA flow 212-230 will be used by such fabless companies. The parallel flow described here is used at a foundry to develop a process flow that can be used to manufacture designs coming from their fabless customers. A combination of the process flow and the masks 230 are used to manufacture any particular circuit. If the integrated circuit is manufactured at an IDM (integrated device manufacturer) company instead of the combination of a fables company and a foundry, then both parallel flows described above are done at the same IDM company.