Partitioning and Reordering Methods for Static Test Sequence Compaction of Sequential Circuits

1. Field of the Invention

This invention relates to methods for compacting test sets for sequential circuits. More specifically, to partitioning and reordering methods for fast static test sequence compaction of sequential circuits.

This application relates to U.S. application Ser. No. 09/001,543 filed on Dec. 31, 1997 entitled, "State Relaxation Based Subsequence Removal Method for Fast Static Compaction in Sequential Circuits," which is assigned to the Assignee of the present invention and which is incorporated herein by reference.

2. Background and Description of Related Art

Since the cost of testing sequential circuits is directly proportional to the number of test vectors in a test set, short test sequences are desirable. Reduction in test set size can be achieved using static or dynamic test set compaction algorithms. Dynamic techniques such as those described in Chakradhar, S., et al., "Bottleneck Removal Algorithm for Dynamic Compaction and Test Cycle Removal," Proc. European Design Automation Conf., pp. 98-104, September 1995), Chakradhar, S., et al., "Bottleneck Removal Algorithm for Dynamic Compaction in Sequential Circuits," IEEE Trans. on Computer-Aided Design, (Accepted for Publication) 1997 and Niermann, T. M., et al., "Method for Automatically Generating Test Vectors for Digital Integrated Circuits," U.S. Pat. No. 5,377,197, 1994, perform compaction concurrently with the test generation process. These techniques often require modification of the test generator.

Static compaction techniques, on the other hand, are employed after the test generation process. Obviously, static techniques are independent of the test generation algorithm and do not require modifications to the test generator. In addition, static compaction techniques can further reduce the size of test sets obtained after dynamic compaction.

Several static compaction approaches for sequential circuits have been proposed in the following papers: Niermann, T. M., et al. "Test Compaction for Sequential Circuits," IEEE Trans. Computer-Aided Design, vol. 11, no. 2, pp. 260-67, February 1992, So, B., "Time-efficient Automatic Test Pattern Generation System," Ph.D. Thesis, EE Dept. Univ. of Wisconsin-Madison, 1994, Pomeranz, I., et al., "On Static Compaction of Test Sequences for Synchronous Sequential Circuits," Proc. Design Automation Conf., pp. 215-20, June 1996 and Hsiao, M. S. et al., "Fast Algorithms for Static Compaction of Sequential Circuit Test Vectors," Proc. IEEE VLSI Test Symp., pp. 188-195, April 1995.

Some of these approaches (Niermann, Time Compaction, So) cannot reduce test sets produced by random or simulation-based test generators. Static compaction techniques based on vector insertion, omission, or selection have also been investigated (Pomeranz). These techniques require multiple fault simulation passes. If a vector is omitted or swapped, the fault simulator is invoked to make sure that the fault coverage is not affected. Vector restoration techniques, as described in Guo, R., et al., "Procedures for Static Compaction of Test Sequences for Synchronous Sequential Circuits Based on Vector Restoration," Technical Report Aug. 3, 1997, Electrical and Computer Engineering Department, University of Iowa, August 1997, aim to restore sufficient vectors necessary to detect all faults, starting with the harder faults. Fast static test set compaction based on removing recurrence subsequences that start and end on the same states has also been reported recently (Hsiao). However, these test sets are not as compact as those achieved by algorithms that use multiple fault simulation passes.

The present invention included methods of compacting a sequential circuit test vector set by partitioning faults into hard and easy faults, re-ordering vectors in a test set and a combination of partitioning and re-ordering.

FIG. 1 shows two typical fault coverage curves. The curve with a small dip, curve 2, is associated with test sets that are composed of random vectors followed by deterministic vectors that are generated by automatic test pattern generators (ATPG's). In either case, fault coverage increases rapidly for the first few test vectors and then eventually levels off. In this level region, a large number of vectors are required to detect very few additional faults. This observation is formalized by using two parameters x (x.sub.1 for curve 1, x.sub.2 for curve 2) and y. The first x % of the vectors detect y % of the faults. For example, it is possible that the first 10% of the vectors in the test set detect 90% of the faults. It should also be observed that faults detected during the quick rise of the fault coverage curve are also usually detected by vectors generated during the level region of the curve. Empirical observations lead to two questions:

1. Because the majority of the test set ((100-x) % of the vectors) is used to detect a few hard faults ((100-y) % of the detected faults), can the computational time be reduced by compacting the test set only with respect to the hard faults?

2. If the test set is re-ordered by placing vectors comprising the last w % of the test set to be at the beginning of the test set, how much of the y % easily detectable faults will still be detected by the re-ordered w % vectors?

The first question suggests that fault list partitioning be performed for static compaction. The test set is compacted by only considering the hard faults. This substantially reduces the cost of fault simulation because only a few faults have to considered during multiple fault simulation passes. Also, computationally expensive static compaction techniques that have been proposed in the past can now be re-examined. This is because the cost of fault simulation can be greatly reduced by using fault list partitioning.

With respect to the second question, re-ordering of test vectors for sequential circuits must be done carefully. This is because detection of a fault in a sequential circuit requires a specific sequence of vectors. Re-ordering is effective if vectors that detect hard faults also detect other faults.

The basic method of this invention is to partition the test vector set into two subsequences and then perform re-ordering compaction on one of the two subsequences.

The contribution of this invention is two fold. First, the computational cost for static test set compaction is substantially reduced by careful fault list and test set partitioning. Second, re-ordering of vectors is shown to be very effective in reducing the test set size. Significant compactions have been obtained very quickly for large ISCAS89 sequential benchmark circuits and several synthesized circuits.

FIG. 1 is a graph of typical fault coverage curves.

FIG. 2 is a diagram showing test set compaction using partitioning.

FIGS. 3(a) and (b) are diagrams showing selection of the partition at the middle and beginning of the test set.

FIG. 4 is a diagram showing a re-ordered test set.

FIG. 5 is a diagram showing a shorter re-ordered test set.

FIG. 6 shows a test set algorithm via partitioning and re-ordering.

FIG. 7 is a table showing compaction results for HITEC test sets.

FIG. 8 is a table showing compaction results for STRATEGATE test sets.

FIG. 9 is a table showing compaction results for production circuits.

The embodiments will be described below with reference to the figures and the following examples. The preferred embodiment, which is a combination of partitioning and re-ordering, will be described after the individual methods are described. Given a test set T, a subsequence of the test set is represented as T[v.sub.i, v.sub.i+1, . . . , v.sub.j ], where v.sub.i and v.sub.j are the i.sup.th and j.sup.th vectors in the test set T, respectively. Furthermore, the set of faults detected by a subsequence T[v.sub.i, . . . , v.sub.j ] is denoted as F.sub.det [v.sub.i, . . . , v.sub.j ].

Consider a test set T with n vectors v.sub.1, . . . , v.sub.n. Assume that this test set detects f faults. If a static compaction algorithm requires m fault simulations, then the worst case time required for multiple fault simulation passes is proportional to m.times.n.times.f single-vector logic simulations.

Test Set and Fault List Partitioning

The process of compaction using partitioning is illustrated in FIG. 2.

It begins by splitting the original test set T into two subsequences T[v.sub.i, . . . , v.sub.i ] and T[v.sub.i+1, . . . , v.sub.n ]. Let r be the ratio of total faults f and the set of faults detected by the subsequence T[v.sub.i+1, . . . , v.sub.n ]: ##EQU1##

If the test set is compacted with respect to only faults in F.sub.det [v.sub.i+1, . . . , v.sub.n ] (Step 1 of FIG. 2), then the computational cost can be reduced to m.times.n.times.(f/r). If r is large, then significant savings in computational time can be achieved. For example, if only 10% of the total faults are detected by the second subsequence, then the time required for multiple fault simulation passes can be reduced by an order of magnitude.

After compaction in Step 1, it is possible that the compacted test set T.sub.compact may not detect all target faults. This is because only a subset of faults were considered during compaction. A possible solution is to combine T.sub.compact and the first subsequence T[v.sub.1, . . . , v.sub.i ] (Step 2 of FIG. 2). One can always append T.sub.compact to the first sequence T[v.sub.1, . . . , v.sub.i ]. This ensures that all target faults f are detected. A second option is to append T[v.sub.1, . . . , v.sub.i ] at the end of the sequence T.sub.compact. This is a better combination because many of the faults detected in T[v.sub.1, . . . , v.sub.i ] may have already been detected by T.sub.compact. This can result in dropping of some or all of the vectors in subsequence T[v.sub.1, . . . , v.sub.i ].

Note that after fault list partitioning, static compaction of the test set T can be performed by any compaction algorithm. In fact, more expensive compaction algorithms may now be cost effective due to the lower cost of fault simulation.

It is better to split the test set at a position closer to the beginning of the test set. Suppose the test set is split in half. Then, compaction of test set T has to be performed by considering only faults detected by the second half of the test set. However, after the first phase of compaction, the first half of the test set still has to be appended, as shown in FIG. 3(a), resulting in a possibly less compact test set. On the other hand, if the test set had been partitioned at an earlier position, as shown in FIG. 3(b), then the portion of the original test set that has to be appended is much smaller. However, the cost of fault simulation during compaction can be higher because more faults may have to be simulated.

Static compaction is performed with respect to only a fraction of the faults. Therefore, the computational cost of compaction procedures would be less than a method that considers all faults. Also, one would expect less compact test sets because only a subset of faults are considered for compaction. However, experiments show that both computational cost and the quality of compaction are benefited by fault list partitioning.

Re-Ordering of Vectors

Another valid question that stems from the shape of the fault coverage curve illustrated in FIG. 1 is whether sequences that detect hard faults can also detect many other, easier faults. In other words, if the sequence of vectors that detect hard faults is copied to the beginning of the test set, can some vectors in the modified test set be omitted? Obviously, it is desirable to compact the modified test set so that it is smaller than the original test set.

Again, consider a test set T[v.sub.1, . . . , v.sub.n ] that detects f faults. If a new test sequence is created by copying the subsequence T[v.sub.k, . . . , v.sub.n ], 1.ltoreq.k.ltoreq.n, to be at the beginning of the original test set T (see FIG. 4), then the modified test sequence is Tnew[v.sub.k, . . . , v.sub.n, v.sub.1, . . . , v.sub.n ]. All target faults are still detectable because the original test set is a subset of the modified test sequence.

There are (n-k+1)+n vectors in the modified test set. Clearly, at least n-k+1 vectors can be omitted from the modified test set without affecting the fault coverage. This is because the first n-k+1 vectors of the modified test set can always be dropped and the compact test set is same as the original test set T.

However, it is possible that more than n-k+1 vectors can be dropped by omitting vectors at the end of the modified test set. For example, consider two faults f.sub.y and f.sub.z that are detected by the original test set T[v.sub.1, . . . , v.sub.n ]. Also, assume that faults f.sub.y and f.sub.z are detected after vectors v.sub.m and v.sub.n, respectively. Here, v.sub.n is the last vector in the test set and m<n. Suppose there exists a k, m<k<n, such that subsequence T[v.sub.k, . . . , v.sub.n ] detects only one fault f.sub.z. FIG. 5 illustrates this scenario. Re-ordering T[v.sub.k, . . . , v.sub.n ] vectors yields the modified test set T[f.sub.k, . . . , v.sub.n, v.sub.i, . . . , v.sub.n ]. Clearly, the subsequence T[v.sub.m +1, . . . , v.sub.n ] at the end of the modified test set is unnecessary, since this subsequence contributes to the detection of only fault f.sub.z and this fault is already detected by the first few vectors of the modified test set. Therefore the modified test set can be compacted to be T[v.sub.k, . . . , v.sub.n, v.sub.1, . . . , v.sub.m ]. The size of the compact test set is (n-k+1)+m. Since k>m, the new test set size can be less than the original test size n. For example, if k=m+3, then the compacted test set is two vectors smaller than the original test set.

Computing the exact k for the last detected fault f.sub.z may be computationally expensive. Instead, an arbitrary k can be selected and the subsequence T[v.sub.k, . . . , v.sub.n ] can be re-ordered to be at the beginning of the test set. Fault simulation of the modified test sequence will determine whether some vectors can be removed. This process can be repeated until every vector in the original test set has been re-ordered.

The size of the subsequence being re-ordered plays a significant role in determining the amount of compaction that is possible. For example, if large subsequences are re-ordered, then less compaction is achieved. When the subsequence size is small, then more compaction is achievable but at a higher computational cost for fault simulation. For instance, if the re-ordered subsequence consists of 5% of vectors in the test set, then it would take up to 20 passes to finish re-ordering of all vectors in the original test set. Also, this will require a maximum of 20 fault simulation passes. On the other hand, if the re-ordered subsequence consists of only 1% of the vectors then it would take up to 100 passes. Note that if a large number of vectors are omitted during the first few passes then the total number of passes required can be significantly less than the maximum.

Combined Test Set Compaction Method

The first step in the combined test set compaction method is to perform test set and fault-list partitioning. This involves splitting of the test set into two subsequences T[v.sub.1, . . . , v.sub.i ] and T[v.sub.i+1, . . . v.sub.n ]. Only faults detected by the second subsequence are considered for compaction. The specific value of i (1.ltoreq.i<n) has a significant impact on the execution time and quality of the resulting compacted test set. This value can be determined in several ways:

1. Choose a value for i such that the subsequence T[v.sub.i+1, . . . v.sub.n ] has a pre-determined number of vectors, or

2. Choose a value of i such that the subsequence T[v.sub.1, . . . v.sub.i ] detects a pre-determined number of faults, or

3. Choose a value for i based on both faults and pre-determined number of vectors.

For example, one can partition a test set by 1) including 90% of the test set as part of the second subsequence, or 2) by including sufficient vectors in the first subsequence so that 80% of the faults are detected and the remaining vectors are included in the second subsequence. In either case, faults detected by the first subsequence are not considered during compaction of the original test set.

There are advantages and disadvantages of each partitioning technique. If the test set is split based on a pre-determined number of vectors, then few faults may be detected by the first subsequence. This may require consideration of a large number of faults during compaction, and the savings in execution times may not be as great. On the other hand, if partitioning is performed by including sufficient number of vectors in the first subsequence so that a pre-determined percentage of faults are detected, then the first subsequence can have too many vectors. This can result in a less compact test set. One technique may be better than the other depending on the test set and the target fault list. Finding the optimal value of i may be as difficult as the compaction problem itself. In the present invention, the value of i is chosen based on a pre-determined percentage of faults that have to be detected by the first subsequence. The value of i can also be chosen using more elaborate methods.

After partitioning has been performed, re-ordering is performed. Re-ordering a subsequence of vectors in a test set results in a new test that is a concatenation of the subsequence and the original test set. The size of the subsequence to be re-ordered has a significant impact on the execution time and quality of the resulting compacted test set. For example, if a large number of vectors are re-ordered during each iteration, then the execution time will be small but resultant test sets may be less compact.

Selection of the number of vectors to reorder is also dependent on the test set and the target fault list. In general, coarse-grain (more vectors) re-ordering may be better for large test set sizes. This is because fine-grain re-ordering can require a large number of fault simulation passes, and the computing resources required can be prohibitive. However, fine-grain re-ordering can lead to good compaction. Therefore, a hybrid approach is developed. The test set is first quickly reduced using coarse-grain re-ordering. Then, fine-grain reordering is performed to further reduce the test set. Coarse-grain re-ordering is performed by considering a subsequence size of 5% of the test set. Then, fine-grain reordering is performed by considering the subsequence size to be 1% of the test set. This two-step reordering has proven to be effective for many circuits.

The pseudo-code for vector-reordering with partitioning is shown in FIG. 6. The method involves first picking a partitioning point. Next, coarse and fine-grain re-ordering is performed with respect to only (100-Y) % of the partitioned faults. When the re-ordering is complete, the first partition of the vectors is appended. Fault simulation is again applied to remove any non-contributing vectors from the first partition. If no partitioning is desired, the partitioning and the concatenation steps in the algorithm are skipped, and Y is set equal to 0%.

The static test set compaction algorithm was implemented in C by repetitively calling a commercial fault simulator via system calls. HITEC and STRATEGATE test sets generated for both ISCAS89 sequential benchmark circuits and several synthesized circuits were used to evaluate the effectiveness of the algorithms. HITEC is a state-of-the-art deterministic test generator. STRATEGATE is a simulation-based test generator based on genetic algorithms that generate test sets with very high fault coverages. All experiments were performed on a Sun UltraSPARC with 256 MB RAM. Note that due to repetitive system calls to the commercial fault simulator, there is extra overhead in reading in the circuit, fault list, and setting up of the data structures necessary for compaction.

Experimental Results

The compaction results are shown in the tables in FIGS. 7 and 8 for HITEC and STRATEGATE vectors, respectively. Both tables show the total numbers of faults, the number of vectors in the original test set, and the number of faults detected by the test set. For each test set, compact test sets are generated using two methods. One method compacts the test set by only considering re-ordering of vectors. Results for this experiment are shown in column No-partition. The number of vectors in the compact test set are shown in column Vec, the percentage reduction in test vectors as compared to the original test set is shown in column % R, the number of faults detected by the compact test set is shown in column Det and the CPU seconds required is shown in column Time. The second method uses both partitioning and re-ordering. Results for this experiment are shown in column Partition.

The partitioning technique splits the test set by considering sufficient vectors in the first subsequence so that 80% of faults are detected. Therefore, the second subsequence consists of only 20% of the faults, and compaction of the entire test set is done with respect to only these faults. After the first phase of compaction, the first subsequence is appended to the compact test set. Vector-reordering is based on a two-step process. First, subsequences that include 5% of the test set (coarse-grain re-ordering) are considered, followed by the second step that considers re-ordering of sequences that include 1% (fine-grain re-ordering) of the test set.

For most circuits, significant reductions in test set sizes were achieved for both vector re-ordering without partitioning and vector re-ordering with partitioning. Fault coverages for the compacted test sets are always greater than or equal to the original fault coverages. For example, in circuit s35932, the compacted HITEC test set detected more faults. Since STRATEGATE vectors already provide high fault coverages, additional faults were not detected after compaction.

On average, 41.1% and 35.1% reductions were obtained for HITEC vectors with and without partitioning, respectively, with a maximum test set reduction of 72.2% for circuit s35932. Similarly, averages of 48.9% and 46.4% reductions were achieved for STRATEGATE vectors with and without partitioning, with maximum test set reduction of 88.4% for s5378. The tables in FIGS. 7 and 8 show that execution times are significantly lower with partitioning. For smaller circuits, partitioning reduces the execution time by about 50%. For the larger circuits, the execution time is reduced by a factor of 4.32 (compaction of HITEC vectors for circuit am2910).

Ideally, by considering 20% faults during compaction, a 5-fold increase in speed can be expected. This is seen for larger circuits. Ideal measures are difficult to obtain due to fixed overheads from logic-simulation costs. For instance, if logic-simulation constitutes 40% of total simulation cost (this cost includes logic and fault simulation costs), then the best speed-up we can achieve is ##EQU2## Thus, greater fractions of the simulation cost are needed for logic simulation for smaller circuits due to the fewer numbers of faults. On average, partitioning accelerated the compaction process by 2.90 times for HITEC vectors and by 3.14 times for STRATEGATE vectors.

The size of compact test sets derived using partitioning is comparable to the size of compact test sets derived without using partitioning. For example, differences between compacted STRATEGATE test set sizes for partitioning and non-partitioning techniques are less significant. However, there are cases where marginally smaller compact test sets are achieved in the no partitioning case. This seems to happen when the number of vectors necessary to detect 80% of faults is large. However, compaction with partitioning appears to result in marginally better compact test sets when the number of vectors in the first subsequence of the split test set is small.

Examination of HITEC and STRATEGATE test sets reveals that a smaller percentage of STRATEGATE vectors are necessary to detect 80% of detected faults. Therefore, a larger percentage of HITEC vectors are required to detect 80% of the faults. For HITEC test sets, compaction without partitioning resulted in marginally better test sets than those with partitioning. One can always partition at a lower fault coverage (e.g., at 60% or 70%) to reduce the number of vectors in the first subsequence, but this can increase the execution times for compaction with partitioning. There are always exceptions. For instance, in the HITEC test set for s444, compaction with partitioning achieves a significantly more compact test set in much shorter execution time. This is because the first 80% of the detected faults are also detected by vectors in the second subsequence that detects hard faults (20% of remaining faults).

The static compaction method was also applied to a few large production circuits. These circuits have several non-Boolean primitives, such as tristate buffers, bidirectional buffers and buses. In addition, they have set/reset flip-flops and multiple clocks. Original test sets for these circuits were derived using a commercial test generator. Compaction results are shown in the table in FIG. 9. For these circuits, it was not possible to run experiments without partitioning because the run times were prohibitively long. Therefore, compaction with partitioning had to be used to cut down the execution times. Significant reductions in test set sizes have been achieved as compared to the original test set. Furthermore, fault coverages obtained by the compacted test sets were often higher.

In terms of reductions in test set sizes among the various static test set compaction techniques, vector-omission based compaction as described in Pomeranz generally outperforms other compaction approaches. However, such technique may not be applicable to large circuits or large test sets. Compaction based on recurrence subsequence removal is very fast, but it produces less compact test sets. In addition, sometimes a slight drop in fault coverage may result after compaction due to the optimistic assumptions made in the subsequence removal algorithm. Circuits for which only a few recurrence subsequences exist, such as circuits s1196, s1238, s1423, s5378, and am2910, recurrence subsequence removal becomes ineffective. Finally, both Vector-restoration as described in Guo and the present invention produce compact test sets at less expensive costs than the Pomeranz method. These static compaction approaches are not constrained by lack of recurrence subsequences and significant reductions in test set sizes were achieved for these circuits.

One significant feature of the present invention is that the test-set and fault-list partitioning strategy can be applied to any of the previously proposed vector-omission (Pomeranz) and vector-restoration (Guo) methods to further reduce execution times. This is an important feature that distinguishes this method from the previously proposed methods. Overall, this method is practical for large designs.

The present invention embodies a new static test set compaction framework using fault list and test set partitioning, and vector-reordering. Significant reductions in test set sizes have been obtained using the invention. Furthermore, partitioning techniques rapidly accelerate the compaction process. Although not attempted here, partitioning and re-ordering techniques can be easily used to accelerate other known static compaction algorithms. These techniques can significantly reduce the CPU seconds required for compaction without compromising on the quality of compaction. Compaction algorithms based on extensive fault simulations can particularly benefit from the partitioning technique. Experiments show that the proposed compaction technique is viable for large circuits or large test sets.

While the above is a description of the invention in its preferred embodiments, various modifications and equivalents may be employed. Therefore, the above description and illustration should not be taken as limiting the scope of the invention which is defined by the claims.