Vector restoration using accelerated validation and refinement

[0002] This application claims priority from co-pending U.S. Provisional Patent Application Ser. No. 60/086,758 filed on May 27, 1998.

[0003] IA. Field of the Invention

[0004] This invention relates to a method for restoring test vectors that are used to detect faults in large industrial design systems. Specifically, this invention relates to a method for restoring a minimal subsequence of vectors that detects a chosen set of faults. This invention is embodied in a method for two-step vector restoration and a method for accelerated two-step vector restoration that improve run-times of fault diagnosis for large designs.

[0005] IB. Background of the Invention

[0006] A vector is a set of inputs to a system. A test set is a set of vectors that identify faults in the system. Target fault list is a list of a subset of faults that are identified by a given test set. Given a test set, and a set of target fault list that is known to be detected by the test set, vector restoration techniques identify a minimal subsequence that detects all faults in the target fault list. See R. Guo, I. Pomeranz, and S. M. Reddy, “Procedures for static compaction of test sequences for synchronous sequential circuits based on vector restoration,” Technical Report8.3.1997, Electrical and Computer Engineering Department, University of Iowa, 1997.

[0007] Restoration techniques are useful in static test sequence compaction or fault diagnosis methods. Known static test sequence compaction methods are described in the following references: T. M. Niermann, R. K. Roy, J. H. Patel, and J. A. Abraham, “Test compaction for sequential circuits,” IEEE Trans. Computer-Aided Design, vol. 11, no. 2, pp. 260-267, February 1992; B. So, “Time-efficient automatic test pattern generation system,” Ph.D. Thesis, EE Dept., Univ. of Wisconsin at Madison, 1994; I. Pomeranz and S. M. Reddy, “On static compaction of test sequences for synchronous sequential circuits,” Proc. Design Automation Conf., pp. 215-220, June 1996; M. S. Hsiao, E. M. Rudnick, and J. H. Patel, “Fast algorithms for static compaction of sequential circuit test vectors,” Proc. IEEE VLSI Test Symp., pp. 188-195, April 1995; S. T. Chakradhar, and M. S. Hsiao, “Partitioning and Reordering Techniques for Static Test Sequence Compaction of Sequential Circuits,” Technical Report1997, Computers & Communications Research Lab, NEC USA Inc.

[0008] Compaction techniques based on vector restoration are described in I. Pomeranz, and S. M. Reddy, “Vector Restoration Based Static Compaction of Test Sequences for Synchronous Sequential circuits.” Proceedings Int. Conf. on Computer Design, pp. 360-365, 1997, University of Iowa, August 1997; and A. Raghunathan and S. T. Chakradhar, “Acceleration techniques for dynamic vector compaction,” Proc. Int. Conf. Computer-Aided Design, pp. 310-317, August 1995.

[0009] IB1. Review of vector restoration

[0010] A test set is an ordered sequence of vectors v₁, . . . , v_n. The test set detects faults f₁, . . . , f_zthat form the fault set F. If a fault f is detected at vector v_iof the test set, then the detection time D[f] of the fault is i. The information on the detection times can be obtained easily using a pre-processing phase that involves fault simulation. Fault dropping is a conventional way of performing such a fault simulation.

[0011] For example, the test set in FIG. 1 has 20 vectors v₁, . . . , v₂₀. This test set detects five faults f₁, . . . , f₅. Fault f₅is detected at vector v₂₀. Therefore, D[f₅]=20. Detection times for other faults are as shown in the FIG. 1. For any given fault f with D[f]=t, there exists a sequence of vectors v_i, . . . , v_t(1≦i≦t) that detects the fault assuming an unknown initial state. For example, f₄is detected at vector v₁₆and there exists a subsequence v₁, . . . , v₁₆that detects the fault. It is also possible that a shorter sequence of vectors v_i, . . . , v_t(1<i≦t) detects the fault.

[0012] A conventional method called linear vector restoration method determines the subsequence by first considering only vector v_t. If one or more target faults are not detected, then the subsequence v_t-1, v_tis proposed. If this sequence also does not detect all target faults, then additional vectors v_t-2, . . . , v₁(in that order) are considered until all target faults are detected. Such a procedure is clearly complex. More details about the complexity of this technique will be provided below.

[0013] The linear vector restoration technique is illustrated by subsequence restoration for faults f₄and f₅which constitute target faults in the example of FIG. 1. Since f₅is detected at v₂₀, the first subsequence considered by the linear vector restoration method is v₂₀. The fault f₅is not detected by this first subsequence. Therefore, the subsequence is updated to include vector v₁₉. The new subsequence is v₁₉,v₂₀. This subsequence also does not detect the fault f₅. Therefore, additional vectors are restored until the restored subsequence includes v₁₇. As shown in FIG. 1, this subsequence detects fault f₅. Therefore, vector restoration for fault f₅is complete.

[0014] The next step is to verify if f₄is also detected by the restored vector set. For this example, the sequence v₁₇, . . . , v₂₀also detects f₄, This completes the restoration process for the target faults f₄and f₅.

[0015] IB2. An application of vector restoration

[0016] Static compaction method using vector restoration is disclosed in detail in U.S. patent application Ser. No. 09/135,561, filed on May 27, 1998 by Bommu, et al., now U.S. Pat. No. 5,987,636 which is incorporated herein by reference.

[0017] Static compaction methods based on vector restoration share the framework described in FIG. 2. Given a test set, fault set, and detection time for every fault, these methods produce a shorter test set that detects at least as many faults as the original test set. The input data includes a set of test vectors, a list of faults to be detected, and the detection times for the faults, Block 2.01 in FIG. 2. First, a set of faults is chosen as the target faults in Block 2.02. These faults can have the same or different detection times.

[0018] If the latest detection time of any fault in the target list is t, then the restoration process Block 2.05 finds a subsequence v_i, . . . , v_t(1≦i≦t) that (1) detects all faults in the target fault list, and (2) if the subsequence is pre-pended to the restored subsequence for earlier target faults, then all earlier target faults are still detected. The next set of target faults is chosen from faults that remain undetected by restored vectors in Block 2.02. This process is continued in Blocks 2.03 and 2.04 until all target faults are detected.

[0019] The problem of compacting the test set of FIG. 1 can be used as an illustration of the vector restoration method. Vector restoration for faults f₄and f₅results in the restored sequence v₁₇, . . . , v₂₀. However, fault f₃is still undetected. Therefore, the next target fault chosen is f₃. The process continues with restoration for fault f₃. The detection time of f₃is 12. Therefore, restoration of f₃starts from the vector v₁₂instead of vector v₁₇. The first sequence proposed for f₃is v₁₂, v₁₇, . . . , v₂₀. This is because it is possible that a sequence starting from v₁₂and ending at any of the vectors in the already restored vectors v₁₇, . . . , v₂₀could detect f₃. Therefore, while restoring a vector sequence for f₃, the already restored vectors v₁₇, . . . , v₂₀are also simulated. Restoration process continues until all faults are detected. For this example, the compacted vector set is v₁, . . . , v₁₂, v₁₇, . . . , v₂₀.

[0020] The conventional linear vector restoration techniques have a major problem that limit their usage. They require prohibitively large run-times for systems in large industrial designs.

[0021] It is therefore an objective of this invention to provide improved vector restoration techniques that require significantly less run-times than conventional methods.

[0022] Specifically it is an object of this invention to provide a method for restoring a minimal subsequence of test vectors for testing a system having a set of faults detectable by the sequence of test vectors.

[0023] To achieve the above objects it is provided a method for restoring a sequence of test vectors for testing a system, said system having a set of faults detectable by the sequence of test vectors, a subset of said set of faults called target faults, said method having a validation phase and a restoration phase, wherein said validation phase identifies a first subsequence of test vectors that detects the target faults and a second subsequence that does not detect the target faults, wherein said restoration phase identifies the shortest subsequence in between the first subsequence and the second subsequence that detects the target faults.

[0024] Another aspect of this invention is a method for restoring a sequence of test vectors comprising: assigning faults to a fault list; identifying a detection time each for each of said faults; initializing a restoration sequence list to nil; assigning faults from the fault list having highest detection times to a target fault list; assigning base to be equal to minimum of said highest detection times and a time corresponding to a first vector in the restoration sequence list; performing a validation phase that identifies a low subsequence of test vectors that detects all faults in the target fault and a high subsequence that does not detect at least one fault in the target fault list; performing a refinement phase that identifies a shortest subsequence in between the low subsequence and the high subsequence wherein said shortest subsequence detects all faults in the target fault list; removing faults from the fault list that are also in the target fault list; updating the restoration sequence list to be the union of the restoration sequence list and the shortest subsequence identified in step g; and repeating until the fault list is empty.

[0025] An improvement includes a method wherein in the validation phase additional vectors are continually added to the restoration sequence and fault simulation is performed until all the faults in the target fault list are detected.

[0026] Further improvement includes a method for performing the validation phase.

[0027] Still further improvements include a method wherein the refinement phase is performed on the restoration sequence by doing a binary search to detect a shortest subsequence that detects all faults in the target fault list.

[0028] Still further improvements include a method for performing the refinement phase.

[0029] Another aspect of this invention is a method for restoring a sequence of test vectors in an accelerated manner, said method comprising: identifying test vectors, a fault list having faults that can be detected using said test vectors and detection times for said faults; selecting faults to be assigned to target fault list if said faults exist; performing overlapped validation such that if two faults in the target fault list have restored sequences that overlap then the two faults are merged to form one target fault; performing overlapped refinement if a segment that detects the one target fault exists; and repeating while target faults exist.

[0030] Further improvements include a method wherein while performing overlapped validation if restored sequence of two faults have common vectors, restoration process of the two vectors are overlapped.

[0031] Still further improvements include a method wherein while at least one fault in the target fault is undetected during overlapped validation step, new target faults that are identified not to be in the target fault list are added to the target fault list.

[0032] Still further improvements include a method wherein while performing overlapped refinement a segment is identified between a low sequence that identifies all faults in the target fault list and a high subsequence in which at least one fault in the target fault list is not identified.

[0033] Still further improvements include a method wherein while at least one fault in the target fault is undetected during overlapped refinement step if new faults not in the target list are identified then the new faults are added to the target fault list.

[0034] Still further improvements include method for performing overlapped validation, overlapped refinement, updating target fault lists and the values of HIGH and LOW.

[0035] The above objectives and advantages of the present invention will become more apparent by describing in detail preferred embodiments thereof with reference to the attached drawings in which:

[0036] FIG. 1 shows an example depicting a test set and a corresponding fault set.

[0037] FIG. 2 shows a block diagram illustrating a method for compaction using vector restoration.

[0038] FIG. 3 shows a graphical illustration of an embodiment of the two-phase vector restoration scheme.

[0039] FIG. 4 shows a pseudo-code implementation for an embodiment of the two-phase vector restoration algorithm.

[0040] FIG. 5 shows comparison of the conventional linear vector restoration and the two-phase restoration.

[0041] FIG. 6 shows a block diagram illustrating an accelerated two-phase vector restoration scheme.

[0042] FIG. 7 shows a pseudo-code implementation of an embodiment of an accelerated two-phase vector restoration algorithm.

[0043] FIG. 8 shows a block diagram illustrating the overlapped validation scheme.

[0044] FIG. 9 shows a pseudo-code implementation of an embodiment of the overlapped validation algorithm.

[0045] FIG. 10 shows a pseudo-code implementation of an embodiment of an algorithm that updates range information (LOW and HIGH arrays).

[0046] FIG. 11 shows a pseudo-code implementation of an embodiment of an algorithm that updates the target faults list.

[0047] FIG. 12 shows pseudo-code for an embodiment of an algorithm that checks the existence of segments.

[0048] FIG. 13 shows a block diagram illustrating a method for overlapped refinement.

[0049] FIG. 14 shows a pseudo-code implementation of an embodiment of the overlapped refinement algorithm.

[0050] FIG. 15 shows an example illustrating accelerated two-phase restoration.

[0051] FIG. 16 shows Table 1 with the results for ISCAS circuits.

[0052] FIG. 17 shows Table 2 that presents results for several industrial designs using the present invention.

[0053] This invention provides new techniques for vector restoration. A new, two-step restoration scheme that is shown to be practical for large designs, is disclosed. This method is significantly superior to the conventional linear vector restoration. The techniques described below can be used to improve run-times of applications like static compaction and fault diagnosis.

[0054] Experiments demonstrate that using the described restoration technique, a static test sequence compaction can process large industrial designs that could not be handled using conventional linear vector restoration techniques presented in I. Pomeranz, and S. M. Reddy, “Vector Restoration Based Static Compaction of Test Sequences for Synchronous Sequential circuits.” Proceedings Int. Conf. on Computer Design, pp. 360-365, 1997, University of Iowa, August 1997.

[0055] IVA. Two-phase vector restoration

[0056] The restoration process of the present invention consists of two phases: validation and refinement. In the validation phase, a sufficient subsequence of vectors is quickly identified. Such a subsequence is guaranteed to also contain a shorter subsequence of vectors that will detect all target faults. This subsequence is larger than necessary and is referred to as the validated segment.

[0057] The refinement phase trims the validated segment and finds the shortest subsequence that detects all target faults.

[0058] The restoration process according to the present invention recognizes that faults can be detected by non-overlapping subsequences. Restoring faults f₃and f₅, in the example of FIG. 1, illustrates such a case. The entire test set can be proposed as the subsequence required to detect faults f₃and f₅. However, subsequences that detect faults f₃and f₅do not share vectors. As has been shown above, subsequence v₁₇, . . . , v₂₀detects f₅and subsequence v₁, . . . , v₁₂detects f₃. These subsequences have no vectors in common. The restoration technique of the present invention produces two subsequences instead of a single subsequence. It is clear that these subsequences can be ordered in any way to detect faults f₃and f₅. Such independent subsequences are referred to as segments. The restoration technique of the present invention restores non-overlapping segments that can be ordered arbitrarily to detect all target faults.

[0059] A key concept behind the two-phase restoration process can be explained using FIG. 3, which illustrates an embodiment of the two-phase restoration scheme of the present invention. The current target fault is f. Its detection time is shown as D[f]. Labels low, opt, high, base and last assume values between 1 and n (original test set consists of vectors v₁, . . . , v_n). The sequence ResSeg (v_base, . . . , v_last) restored for earlier targets, and does not detect the current target fault f.

[0060] The restoration process for f begins at vector v_base. Validation phase identifies a subsequence v_low, . . . , v_lastthat detects the target fault. The restoration phase also establishes that subsequence v_high, . . . , v_lastdoes not detect the target fault. Importantly, the shortest subsequence that detects the target begins at some vector between v_lowand v_high.

[0061] The refinement phase identifies the subsequence v_opt, . . . , v_baseas the shortest subsequence that is added to the restored subsequence ResSeq. Here, low≦opt<high.

[0062] An embodiment of the two-phase restoration algorithm is described by the pseudo-code presented in FIG. 4. The restoration algorithm repeats validation and refinement phases until all faults in the input fault list F_uare detected by restored sequence ResSeq. During each iteration, only faults not detected by the currently restored sequence ResSeq are considered. Among the undetected faults, faults that have the highest detection times are selected as target faults. These faults are included in the target fault list F_T. Next two sections describe the validation and refinement phases.

[0063] IVAL. Validation

[0064] Given a target fault list F_T, the validation phase determines values of variables low and high that delimit the validated segment. This phase can either inherit a restored sequence ResSeq from previous restoration phases or can begin a new sequence. Variable base is initialized to be the minimum of detection time of a fault in F_Tand the index of the first vector in the already restored sequence ResSeg. The restoration algorithm extends ResSeq to detect faults in F_T.

[0065] The while loop (FIG. 4, Line 6) makes several calls to the fault simulator (FIG. 4, Line 8). If ResSeg has vectors, then fault simulator verifies whether F_Tis already detected by ResSeq. If one or more faults in F_Tare not detected, then additional vectors are added to ResSeq (FIG. 4, Lines 10 and 11). This process continues until sufficient vectors are added to detect F_T.

[0066] It can be shown that the validation step makes at most O(log k) calls to the fault simulator, when k vectors are added to ResSeq to detect F_T. In the worst case, validation phase simulates only 2^[log2k]+1vectors. This does not include simulation of vectors in ResSeq.

[0067] Operation of the validation phase can be illustrated by considering how a sequence for fault f₅in the example of FIG. 1 is restored. Since f₅is the first fault being restored, ResSeq has no vectors. Therefore, base and low are assigned the value D[f₅]=20. During the first iteration of the while loop (FIG. 4, Line 6), fault simulator determines that f₅is not detected by the sequence consisting of one vector v₂₀. Since f₅is not detected, variable low is updated to be 20−2⁰=19. In the next iteration, the fault simulator determines that f₅is not detected by the sequence v₁₉, v₂₀. Therefore, variable high is updated to 19. The variable low is also updated to 20−2¹=18.

[0068] If this process continues, f₅will be detected when low=20−2²=16. This is because the sequence v₁₆, . . . , v₂₀detects the fault from an unknown initial state. Addition of the vector v₁₆cannot alter detectability of the fault. At this point, high=18. This marks the end of the validation phase. Four iterations of the while loop were required. The validated segment consists of vectors v₁₆, . . . , v₂₀. This segment contains more vectors than necessary to detect f₅.

[0069] IVA2. Refinement

[0070] After the validation phase, all faults in the target fault set F_Tare marked as undetected (FIG. 4, Line 13). Refinement phase identifies the shortest subsequence in the validated segment that detects F_T.

[0071] The while loop (FIG. 4, Line 14) in the refinement phase also makes several calls to the fault simulator (FIG. 4, Line 17). A simple, binary search procedure is used to zoom in on the shortest subsequence that detects all faults in F_T. The refinement phase makes at most O(log(high−low)) calls to the fault simulator. If k is the length of the restored sequence, then O(log k) calls to the fault simulator are required in the worst case. Also, the refinement phase in the worst case may require simulation of 2k*log k vectors. This again does not include simulation of vectors in ResSeg.

[0072] Refinement phase for f₅(FIG. 1) involves a binary search between low=16 and high=18 for the shortest subsequence that detects f₅. The first sequence considered starts at vector v₁₇. This is because (low+high)/2=17. Sequence v₁₇, . . . , v₂₀detects f₅. Therefore, low is updated to 17. Since low=high+1, the while loop of Line 14 terminates and the refinement phase also terminates. The shortest subsequence found is v₁₇, . . . , v₂₀.

[0073] IVA3. Comparison with linear vector restoration

[0074] First, the complexity of the linear vector restoration (LVR) process will be analyzed. In the vector restoration for fault f₅, the first sequence considered is of length 1 (v₂₀), followed by a sequence of length 2 (v₁₉, v₂₀), and this process is continued until the sequence v₁₇, . . . , v₂₀. One vector is added at each iteration. Consequently, total number of vectors simulated during restoration is 1+2+3+4. Here, the length of the restored subsequence is 4 and four steps were involved in retrieving the sequence. Generalizing from the above calculation, if a subsequence of length k is restored, then:

[0075] number of vectors simulated during restoration=1+2+ . . . +k=k(k+1)/2.

[0076] number of iterations to restore the subsequence=k (this also represents the number of times the fault simulator is invoked).

[0077] FIG. 5 illustrates the different steps involved in LVR and two-phase restoration while restoring the vector for f₅in example of FIG. 1.

[0078] The final sequence restored both by LVR and 2φ are exactly the same. If k is the length of restored sequence, then a careful analysis of the algorithm in FIG. 4 shows the following:

[0079] validation phase needs simulation of 2^[Log2k]+1vectors.

[0080] refinement phase could in the worst case require simulation of 2k*log₂k vectors.

[0081] algorithm in FIG. 4 makes at most 2log₂k+1 calls to a fault simulator.

[0082] The significance of the above analysis is evident when typical numbers for k are considered. When the sequence ResSeq has 1000 vectors and the restoration process for a target requires addition of 100 vectors to ResSeq, the value of k is 100. Vectors from ResSeq are simulated for every call to the fault simulator. If the number of vectors that are simulated during restoration is v_LVRfor linear restoration and v_2φ for the two-phase technique, then,

[0083] v_LVR=1000*(# fault simulator calls)+100*(100+1)/2

[0084] =1000*100+5050=105,050

[0085] v_2φ=1000*(# fault simulator calls)+(256+2* 100*7)

[0086] =1000* (2*7+1)+(256+2*100*7)=16, 656

[0087] Clearly, two-phase restoration requires almost an order of magnitude fewer simulations as compared to linear restoration. Consequently, significant speed-up is achieved by using two-phase restoration.

[0088] IVB. Accelerated two-phase restoration

[0089] The two-phase restoration procedure described in FIG. 4 considers a new target only after restoring the shortest sequence for current target. Typically, restored sequences for successive targets overlap. Therefore, it may be unnecessary to find the shortest sequence for current target. In many cases, it is possible to identify the next target even before vector restoration for the current target is complete.

[0090] Accelerated two-phase restoration algorithm is another aspect of this invention. In this method, new targets are identified in either the validation phase or the refinement phase. When new targets are identified, the restoration process for the current target is overlapped with the restoration of the new target. As shown below, overlapping of vector restoration in the two-phase method further significantly accelerates the restoration process. The restored segments are identical in both two-phase and accelerated two-phase methods.

[0091] The accelerated restoration algorithm flow is illustrated in FIG. 6. Like the basic vector restoration algorithm, it inputs a set of test vectors, a list of faults to be detected, and the list of detection times for those faults in 6.01. Unlike the basic two-phase restoration algorithm described above, the accelerated version overlaps validation and refinement of multiple target faults. Specifically, the restoration portion of the accelerated version consists of three phases: overlapped validation 6.05, segment existence condition 6.06, and overlapped refinement phase 6.07.

[0092] A key concept behind the accelerated version is as follows. If a subsequence obtained after validation phase does not include a segment for target faults, then a refinement phase is unnecessary. The accelerated version overlaps validation for multiple faults until a subsequence is identified that includes a segment. The refinement phase 6.07 extracts a segment for target faults. Again, this phase overlaps refinement phases of several target faults.

[0093] The algorithm for the accelerated version is shown in FIG. 7. Similar to the basic two-phase algorithm, the accelerated version also repeats validation and refinement phases until all faults in the input fault list F_uare detected by the restored sequence ResSeq. The accelerated version also computes the target fault list F_Tat the beginning of each iteration. However, there are several fundamental differences between the basic and the accelerated version: (1) accelerated version modifies the target fault list in the validation or refinement phase, (2) accelerated version performs refinement only after the validated phase produces a sequence that includes a segment for target faults, and (3) every refinement phase of the while loop (FIG. 6, Line 8) in the accelerated version produces exactly one segment. This is unlike the basic version where several refinement phases may be required to produce a segment that detects target faults.

[0094] The accelerated version also stores more information about the range of vectors that detect or do not detect a fault. This information is easily available during fault simulation of a sequence and target faults. In the algorithm of FIG. 4, the validation phase determines values of variables low and high that satisfy two properties: (1) subsequence v_low, . . . , v_lastdetects all target faults F_T, but (2) subsequence v_high, . . . , v_lastdoes not detect at least one fault in F_T.

[0095] The accelerated version uses arrays LOW and HIGH to record the range information for each fault. For a fault f, assuming that LOW[f]=i and HIGH[f]=j, the values i and j always satisfy the following two properties: (1) sequence v_i, . . . , v_lastdetects the fault, but (2) sequence v_j, . . . , v_lastdoes not detect the fault. Range information for every fault is continuously updated during overlapped validation or refinement. The following two sections describe overlapped validation and refinement.

[0096] IVB1. Overlapped validation

[0097] In the validation phase of the two-phase restoration algorithm of FIG. 4, assume that f_xis the current target, an intermediate sequence v_low, . . . v_last(see FIG. 3) does not detect f_x, and that this sequence does not also detect another fault f_ythat has a detection time D[f_y]≧low. In such a case, restored sequences for faults f_xand f_yoverlap. In particular, both sequences will include vectors v_low, . . . , v_D[fy]. Therefore, validation for faults f_xand f_ycan be overlapped.

[0098] In the example of FIG. 1, during validation for f₃, the sequence v₄, . . . , v₁₂is considered as a possible candidate. Fault simulation reveals that both f₂and f₃are not detected. The detection time of f₂is 5. Therefore, any restored sequence that detects f₂will at least share vectors v₄and v₅with the restored sequence for fault f₃. Therefore, the restored sequence for f₃alone cannot form a segment. To accelerate segment restoration, both faults can be merged as one target F_T=(f₂, f₃). Validation phase can overlap restoration for faults f₂and f₃.

[0099] A key concept of the overlapped validation is as follows. If restored sequences of two faults have common vectors, then restoration process for the two faults can be overlapped. This provides a significant computational advantage. The overlapped validation process is shown in FIG. 8. The algorithm inputs a target fault list, partial segment of test vectors, and the detection times of the faults in 8.01. In 8.02 vectors are added to the partial segment. In 8.03 it is determined if the target is detected. If the target is detected, the algorithm exits after outputting the validated segment in 8.04, otherwise the target fault list is updated in 8.05, and the execution continues with 8.02.

[0100] If the dotted Block 8.05 that updates the target list in FIG. 8 is ignored, then the flow chart describes the validation phase of the basic algorithm. During overlapped validation, an additional task is performed when one or more faults in the target fault list F_Tare not detected. This task determines if new targets have been identified. If a new target is found, then the validation phase proceeds by including new targets in current target fault list.

[0101] The detailed algorithm for the overlapped validation phase is shown in FIG. 9. During each iteration of the while loop (FIG. 9, Line 3), a new sequence Seq is proposed (FIG. 9, Line 5). A new fault list F_sis also constructed (FIG. 9, Line 4). This set includes all undetected faults that have detection times corresponding to vectors in Seq. Fault simulation of sequence Seq is used to update the range information for faults in F_s. For example, consider a fault fεF_sthat is detected by fault simulation. Let the index of the first vector in Seq be index. If LOW[f]<index, then the value of LOW[f] is updated to be index. This is because fault simulation has established that fault f is detected by the sequence Seq. If fault simulation did not detect fault f, then the value of HIGH[f] can be updated. For example, if HIGH[f]>index, then the value of HIGH[f] is updated to be index. The algorithm for range information update is shown in FIG. 10.

[0102] If one or more faults in F_Tare not detected by the Seg, then new targets can be identified. This step did not exist in the basic algorithm. New targets are identified using the algorithm UPDATE_TARGETS that is shown in FIG. 11. Using the range information for faults in F_T, the index high is first identified in such a way that subsequence v_high, . . . , v_lastdoes not detect at least one fault in F_T. Undetected faults that are not part of the target fault list F_T(FIG. 11, Line 3) are considered in decreasing order of their detection times. Let fault f_p, be such an undetected fault.

[0103] Considering the vector v_D[fp], if high≦D[f_p]+1, restored sequence for F_Twill definitely include the vector v_D[fp]. Also, if HIGH[f_p]≦D[f_p], then the restored sequence for f_pwill also include the vector v_D[fp]. This is because it is known that the sequence v_HIGH[fp], . . . , v_lastcannot detect f_p. If vector v_D[fp] is common to restored sequences for faults in F_Tand the fault f_p, the restoration process for these faults can be overlapped by including f_pin F_T.

[0104] It is possible that F_Tincludes faults that can be detected by the sequence v_high, . . . , v_last. For example, consider a fault fεF_T. If LOW[f]≧max, then the sequence v_high, . . . , v_lastdefinitely detects f. Line 10 in FIG. 11 identifies such faults. These faults can be marked as detected and they do not have to be considered again during the restoration process. Therefore, they are deleted from the fault list F_uand target list F_T. If f_pis included as a new target, then the value of high (FIG. 11, Line 4) is recomputed. The update process stops at the first fault f_p, that is not a new target. This is because restored sequences for remaining undetected faults do not overlap with the segment for target faults F_T.

[0105] IVB2. Segment existence check

[0106] The sequence obtained after validation may or may not contain a segment. If no segment exists, then refinement phase is unnecessary. The algorithm in FIG. 12 determines if a sequence includes a segment. The sequence ResSeq does not detect faults in F_T. Range information of faults in F_Tis used to determine the value of variable low (FIG. 12, Line 2). The sequence Seq={v_low, . . . , v_base} U ResSeq detects all faults in F_T. This procedure assumes that fault simulation has already been performed for Seq.

[0107] SEGMENT_FOUND is an embodiment of an algorithm that determines if subsequence v_low, . . . v_baseincludes a segment that detects F_T. In this phase, it is not necessary to identify the exact segment for F_T. It suffices to establish existence of a subsequence in Seq that satisfies two properties: (1) subsequence detects F_T, and (2) no undetected fault in F_u-F_Thas a detection time that corresponds to any vector in the subsequence.

[0108] The first step is to compute F_c. This set includes all undetected faults with detection times corresponding to vectors in Seq. If F_chas no faults, then Seq includes a segment (FIG. 12, Line 6). Otherwise, vectors that belong to restored sequences for faults in F_chave to be excluded. Consider a fault fεF_c. Since HIGH[f]≦low, fault f is not detected by Seq. More importantly, restored sequence for fault f overlaps with Seq. The overlap can include vectors v_low, . . . , v_D[f]. Therefore, if a segment exists for F_T, then it must be contained in the subsequence v_D[f]+1, . . . , v_base. Line 8 in FIG. 12 determines the index low of the first vector that does not belong to restored sequences for any fault in F_c.

[0109] Based on faults in F_c, a shorter sequence Seq (FIG. 12, Line 9) is proposed. The new sequence Seq may not detect all faults in F_T. Fault simulation determines this. If such is the case (FIG. 12, Lines 16-17), Seq does not include a segment for F_T. If the Seq does detect all faults in F_T(FIG. 12, Line 14), then it is not clear whether or not a segment for F_Texists. However, now there is a shorter sequence to examine as compared to the original sequence at the beginning of the while loop (FIG. 12, Line 3). The process is repeated for the shorter sequence. This procedure will be illustrated below by using an example.

[0110] IVB3. Overlapped refinement

[0111] In the example of FIG. 1, after the validation phase of the basic algorithm (FIG. 4) for fault f₃, the target fault list F_T=(f₃, f₂), high=4 and low=1. Based on these initial values, the first sequence processed by the fault simulator is v₂, . . . , v₁₂. This sequence detects both faults in F_T. However, fault f₁is not detected. Its detection time D[f₁]=3 corresponds to vector v₃that is already included in the sequence v₂, . . . , v₁₂. Therefore, the restored sequence for f₁also includes vectors v₂and v₃and further refinement of v₂, . . . , v₁₂is unnecessary. Refinement phases of fault f₁and faults in F_Tshould be overlapped to find the segment.

[0112] A key concept of overlapped refinement is to find a segment. As in overlapped validation, new targets are identified if one or more faults in F_Tare not detected. If a new target is found, then the refinement phase proceeds by including the new target in F_T. Unlike the basic algorithm of FIG. 4, the overlapped refinement phase (1) always produces a segment, and (2) new faults may be added to F_Tduring the refinement phase.

[0113] An embodiment of the overlapped refinement process is shown in FIG. 13. The algorithm inputs a validated segment and a list of target faults together with their detection times. The validated segment that is input is pruned in 13.02. In 13.03, the algorithm determines if the target is detected. If the target is not detected, the fault list is updated in 13.06, and the execution resumes with pruning validated segment in 13.02. If the target is detected, condition 13.04 determines if further refinement is possible. If the answer is “yes”, the execution continues with pruning validated segment in 13.02, otherwise the execution is completed and the found segment is output.

[0114] Again, if the dotted box 13.06 is ignored, then the flow chart shows the refinement phase of the basic algorithm.

[0115] An embodiment of a detailed algorithm for the overlapped refinement phase is shown in FIG. 14. Initially, ResSeq does not detect faults in F_T. Range information of faults in F_Tis again used to find the first vector v_lowof the sequence that detects faults F_T(FIG. 14, Line 2). All faults in F_Tare detected by the subsequence v_low, . . . , v_base. Range information is also used to identify the index high such that at least one fault in F_Tis not detected. This sequence is v_high, . . . , v_baseA segment for F_Tbegins somewhere between low and high. Overlapped refinement identifies this segment. This segment detects all faults in F_Tbut it may also detect other faults. The additional faults detected in the segment eventually become new targets that are included in F_T.

[0116] During each iteration of the while loop (FIG. 14, Line 4), a new sequence Seq is proposed (FIG. 14, Line 6). A new fault list F_sis constructed that includes undetected faults with detection times corresponding to vectors in Seq. Fault simulation of sequence Seq is used to update the range information for faults in F_s.

[0117] If all faults in F_Tare detected (FIG. 14, Line 11-15), then the next sequence will be chosen using a procedure other than the standard binary search process. Then the set F_c(FIG. 14, Line 11) is computed. This set includes all faults with detection times corresponding to some vector in the sequence Seq but these faults are known not be detectable by sequence Seq. Again, vectors that belong to restored sequences for faults in F_chave to be excluded. Line 12 in FIG. 14 determines the index start of the first vector that does not belong to restored sequences for any fault in F_c. The next sequence that will be chosen on Line 6 is {v_start, . . . , v_base} U ResSeq. Clearly, this is a shorter sequence.

[0118] If at least one fault in F_Tis not detected, there is an opportunity for finding new targets. UPDATE TARGETS is an embodiment of a procedure that finds new targets. Since new targets may be included in F_T, the limits low and high (FIG. 14, Lines 18-19) are recomputed. More importantly, the next sequence will be chosen using the binary search process. A sequence larger than Seq will have to be considered in the next iteration.

[0119] Overlapped validation and refinement significantly improves performance in the restoration of a segment. As it will be shown below, these techniques accelerate the compaction process by a factor of 2 for one of the larger industrial designs.

[0120] Example in FIG. 15 will be used to illustrate the operation of the accelerated version of the algorithm. The test set consists of thirty vectors v₁, . . . , v₃₀and the fault list has eight faults F_u{f₁, . . . , f₈}. The example shows detection time and all subsequences that detect a fault assuming an unknown initial state. For example, fault f₃is detected after the application of vector v₁₉. Therefore, D[f₃]=19. Only subsequence v₁₆, . . . , v₁₉detects this fault starting from an unknown initial state. Every fault is detected by exactly one subsequence, except fault f₃, see FIG. 15. This fault is detected by two subsequences v₁, . . . , v₂₂, and v₂₂, . . . , v₂₈.

[0121] For this example, the accelerated version requires two refinement phases. Two segments are found: {v₃, . . . , v₁₄} and {v₁₇, . . . , v₃₀}. The procedure used to find the first segment will be illustrated below. The second segment is found in a similar way.

[0122] The first segment v₁₇, . . . , v₃₀is derived as follows. First the 2-φ* algorithm of FIG. 7 will be considered. Since this is the first iteration, there are no vectors in ResSeq. Lines 2-4 are initialization steps that are required before a new segment is derived. Variable base+30 since the highest detection time is for fault f₅and D[f₈]=30. The target fault list F_Thas only one fault f₈. The procedure RESET_LOW_HiGH initializes the arrays LOW and HIGH. For any fεF_u, LOW[f]=1 and HIGH[f]=31.

[0123] Algorithm OVERLAPPED_VALIDATION: Initially, F_T=f₈. The variable start=31 since HIGH[f₈]=31. The restoration process considers seven sequences in the following order:

[0124] 1. The first sequence considered for fault simulation is v₃₀. This is because, from line 4, low=30. The fault set F_s={f₈} because all other faults in F_Thave detection times less than 30. Fault simulation of vector v₃₀does not detect any fault in F_s. The range information is updated using procedure UPDATE_LOW_HIGH as follows: HIGH[f₈]=30. The procedure UPDATE_TARGETS does not produce any new targets. The first fault considered in this procedure is f_p=f₇(FIG. 11, Line 3). The variable high=HIGH[f₈]=30. Since D[f_p]=29, therefore, high>D[f_p] and fault f₇is not a new target.

[0125] 2. The next sequence considered for fault simulation is Seq={v₂₉, v₃₀}. This is because, from FIG. 9, Line 4, low=29. Set F_Tstill includes only one fault f₈. However, F_s={f₇, f₈} since detection times of both f₇and f₈are equal to or greater than 29. Fault simulation of Seq also does not detect any fault in F_T. Range information is updated as follows: HIGH[f₇]=HIGH [f₈]=29. The procedure UPDATE_TARGETS produces one new target, as follows. The first fault considered in this procedure is f_p=f₇. The variable high=HIGH[f₈]=29. Since D[f₇]=29, therefore, high≦D[f₇]+1. Also, HIGH[f₇]≦D[f₇]. Therefore, f₇is a new target and it is included in target fault list F_T. The set F_dethas no faults. The second fault considered is f_p=f₆. The variable high=MINIMUM(HIGH[f₇],HIGH[f₈])=29. Since D[f₆]=26, therefore, high>D[f₆]+1 and f₆is not a new target.

[0126] 3. The next sequence considered is Seq={v₂₈, . . . , v₃₀}. For this pass, F_T=F_s={f₇, f₈}. Again, fault simulation of Seq does not detect any fault in F_s. Range information is updated as follows: HIGH[f₇]=HIGH [f₈]=28. The procedure UPDATE_TARGETS does not result in a new target.

[0127] 4. The next sequence considered is Seq=[v₂₆, . . . , v₃₀]. The set F_T={f₇, f₈} and F_s={f₆, f₇, f₈}. The fault f₆is considered in F₈because D[f₆]=26≧26 and HIGH[f₆]=31>26. Fault simulation results in the detection of fault f₈. Range information is updated as follows: HIGH[f₆]=HIGH[f₇]=LOW[f₈]=26. The procedure UPDATE_TARGETS (1) produces one new target f₆, and (2) the fault f₈is marked detected, and eliminated from both F_Tand F_u. Fault f₆is a new target because restored sequence for f₆will overlap with the sequence v₂₆, . . . , v₃₀.

[0128] 5. The next sequence considered is Seq={v₂₂, . . . , v₃₀}. The sets F_T={f₆, f₇} and F_s={f₅, f₆, f₇}. Again, fault f₅is included in F_ssince its detection time is 22. Fault simulation of Seq results in detection of f₅. Range information is updated as follows: HIGH[f₆]=HIGH[f₇]=LOW[f₅]=22. The procedure UPDATE_TARGETS (1) produces no new targets, but (2) the fault f₅is marked detected, and eliminated from both F_Tand F_u.

[0129] 6. The next sequence considered is Seq={v₁₄, . . . , v₃₀}. The sets F_T={f₆, f₇} and F_s={f₁, f₂, f₃, f₄, f₆f₇}. Faults f₁, . . . , f₄are included in F_ssince their detection times are greater than or equal to 14. Fault simulation of Seq results in detection of all faults in F_sexcept f₁. Range information is updated as follows: LOW[f₂]=LOW[f₃]=LOW[f₄]=LOW[f₆]=LOW[f₇]=HIGH[f₁]=14. The procedure UPDATE_TARGETS produces no new targets. Since all faults in F_Tare detected, the overlapped validation phase terminates with the sequence v₁₄, . . . , v₃₀.

[0130] Algorithm SEGMENT_FOUND: Initially, F_T={f₆, f₇} and low=14. Therefore, the sequence v₁₄, . . . , v₃₀detects all faults in F_T. The set F_cis computed as follows. All faults in F_u={f₁, f₂, f₃, f₄, f₆, f₇} have detection times greater than or equal to 14. However, only one fault f₁has HIGH[f₁]≦14. Therefore, F_c={f₁}. The first sequence proposed for fault simulation is Seq={v₁₅, . . . v₃₀}. The set F_s={f₂, f₃, f₄, f₆, f₇}. Fault simulation reveals that all faults in F_sare detected. Range information is updated as follows: LOW[f₂]=LOW[f₃]=LOW[f₄]=LOW[f₆]=LOW[f₇]=15. Since all faults in F_Tare detected, a segment may be possible within the sequence Seq. All faults in F_Tare marked as undetected and the shorter sequence {v₁₅, . . . , v₃₀} is examined for a segment. The set F_cis again recomputed and it is found that F_chas no faults. Therefore, the sequence {v₁₅, . . . , v₃₀} has a segment.

[0131] Algorithm OVERLAPPED_REFINEMENT: This phase identifies the segment {v₁₇, . . . , v₃₀}. At the beginning of the refinement phase, F_T={f₆, f₇}. From Lines 1 and 2 of the refinement algorithm in FIG. 14, high=22 and low=15. Therefore, the first vector of the segment is somewhere between vectors v₁₅and v₂₂. The refinement process considers five sequences in the following order:

[0132] 1. The first sequence considered (FIG. 14, line 6) is Seq={v₁₈, . . . , v₃₀}. This is because opt=[(low+high)/2]=18 is determined as in the binary search process of the refinement phase of basic algorithm. The sets F_T={f₆, f₇}, and Fs={f₂, f₃, f₄, f₆, f₇}. Fault simulation of Seq reveals that faults f₄, f₆and f₇are detected. Range information is updated as follows: LOW[f₄]=LOW[f₆]=LOW[f₇]=HIGH[f₂]=HIGH[f₃]=18. Since all faults in F_Tare detected, the set F_cis computed to be F_c={f₂, f₃}. Since F_chas faults, therefore, the next sequence is not chosen using the standard binary search process. The variable start=1+19=20, and variable low=18.

[0133] 2. The next sequence considered is Seq={v₂₀, . . . , v₃₀}. This is because, from FIG. 14, Line 5, opt=start=20. At this time F_Tis unchanged, and F_s={f₄, f₆, f₇}. Fault simulation of Seq reveals that faults f₆and f₇are detected but f₄is not detected. Range information is updated as follows: LOW[f₆]=LOW[f₇]=HIGH[f₄]=20. Since all faults in F_Tare detected, the set F_cis computed to be F_c={f₄}. Since F_chas faults, therefore, the next sequence is not chosen using the standard binary search process. The variable start=1+21=22, and variable low=20.

[0134] 3. The next sequence considered (FIG. 14, Line 6) is Seq={v₂₂, . . . , v₃₀}. Again, F_T={f₆, f₇} remains unchanged. however, F_s={ }. This is because Seq has already been considered for fault simulation during the OVERLAPPED_VALIDATION phase. Therefore, no fault simulation is necessary. Faults f₆and f₇cannot be detected by Seq. Range information remains unchanged: HIGH[f₆]=HIGH[f₇]=22. Now, new targets are identified by using procedure UPDATE_TARGETS.

[0135] Algorithm UPDATE_TARGETS of FIG. 11 is executed next. Initially, F_T={f₆, f₇} and F_u={f₁, f₂, f₃, f₄, f₆, f₇}.

[0136] (a) The first fault considered (FIG. 11, Line 3) is f_p=f₄. Considering all faults in F_T, it is determined that high=22 (FIG. 11, Line 4). Since high≦D[f₄]+1 and HIGH[f₄]=20≦D[f₄], there is a new target f₄that is included in F_T. The set F_detis computed to be F_det={ } (Line 10) This is because LOW[f₆] and LOW[f₇] is equal to 20 and high=22.

[0137] (b) The second fault considered is f_p=f₃. Since D[f₃]=19 and high=20, fault f₃is a new target. Again, f₃is added to F_T. The target fault list is updated to F_T={f₃, f₄}. The set F_detis computed to be F_det={f₆, f₇}. This is because LOW[f₆]=LOW[f₇]=20≧high. These two faults are marked detected. They are deleted from F_Tand F_u. Now, F_T={f₃, f₄}.

[0138] (c) The third fault considered is f_p=f₂. Since D[f₂]=18 and high=18, fault f₂is a new target. Again, f₂is added to F_T. The target fault list is updated to F_T={f₂, f₃}. Set F_detis found to be F_det={f₄}. Fault f₄is marked as detected. This fault is deleted from F_Tand F_u. Now, F_T={f₂, f₃}.

[0139] (d) The last fault considered is f_p=f₁. Since D[f₁]=14 and high=18, fault f₁is not a new target. No more new targets are possible.

[0140] 4. Then the execution switches back to Line 18 of the OVERLAPPED_REFINEMENT algorithm (FIG. 14). At this point, F_T={f₂, f₃}. Since F_Thas changed, the limits are recomputed to be high=18 and low=15. Note that the next sequence will be chosen using the binary search process. The next sequence considered is Seg={v₁₆, . . . , v₃₀}. This is because from FIG. 14, Line 5, opt=16. The set F_sis the same as F_T. Fault simulation of Seq reveals that both faults f₂and f₃are detected. Range information is updated as follows: LOW[f₂]=LOW[f₃]=16. Since all faults in F_Tare detected, it is possible that the segment for F_Tmay be shorter than Seq. The next sequence will not be chosen using the binary search process. The variable start=1+16=17, and variable low=16.

[0141] 5. The last sequence considered is Seq={v₁₇, . . . , v₃₀}. This is because from Line 6 of FIG. 14, opt=17. Now, F_s=F_T={f₂, f₃}. Fault simulation of Seq reveals that f₂is detected but f₃is not. Range information is updated as follows: LOW[f₂]=HIGH[f₃]=17. There is an opportunity for finding a new target. Procedure UPDATE_TARGETs (1) does not find any new target, but (2) it determines that f₂is detected. This fault is deleted from F_Tand F_u. The values of high and low are recomputed to be 17 and 16, respectively. This violates the condition of the while loop (FIG. 14, Line 4) and the refinement process is terminated.

[0142] IVC. Experimental Results

[0143] The described vector restoration technique was implemented as part of a static test sequence compaction system. The implementation includes both basic and advanced techniques described above. To make a fair comparison, the linear vector restoration algorithm was also implemented. Standard approach performs simulation on a single fault during the vector restoration process. I. Pomeranz, and S. M. Reddy, “Vector Restoration Based Static Compaction of Test Sequences for Synchronous Sequential circuits.” Proceedings Int. Conf. on Computer Designpp. 360-365, 1997, University of Iowa, August 1997. This approach was augmented to consider multiple faults during vector restoration. In the present implementation, faults with the same detection time are considered simultaneously for restoration. Thus, the procedure takes advantage of the parallel fault simulator used in the implementation. Present implementation of the linear vector restoration algorithm will be referred to as LVR*.

[0144] Experimental results are reported for ISCAS benchmark circuits and several industrial designs. F. Brglez, D. Bryan, and K. Kozminski, “Combinational profiles of sequential benchmark circuits,” Int. Symposium on Circuits and Systems, pp. 1929-1934, May 1989. New techniques will be compared with the LVR* approach. Table 1 shown in FIG. 16 presents results for ISCAS circuits. Table 2 shown in FIG. 17 presents results for several industrial designs. All tables report number of vectors in the original and compact vector set. Compaction quality is reported as percentage reduction in the original vector test. The CPU seconds are reported for Sun UltraSPARC work station. CPU seconds reported are platform-specific. Therefore, to give an idea of the complexity of the algorithm, the time taken for fault simulation of all faults using original vector set is also reported. These times are reported under column Initial Sim. Time. Columns LVR*, 2-φ, and 2-φ* report CPU seconds required for compaction using linear vector restoration, two-phase restoration and accelerated two-phase restoration, respectively. Vector restoration based compaction approaches preserve the fault coverage of the original vector set. Therefore, fault coverage numbers are not reported.

[0145] The initial vector set used for ISCAS circuits were obtained using the test set generator HITEC described in T. M. Niermann and J. H. Patel, “HITEC: A test generation package for sequential circuits,” Proc. European Conf. Design Automation(EDAC), pp. 214-218, March 1991. The results for compaction on ISCAS circuits are given in Table 1. The compaction with proposed restoration techniques is significantly faster for larger ISCAS designs. For ISCAS designs, on the average, compaction using described technique is about twice the time taken for one fault simulation of original vector set.

[0146] The number of gates and number of flip flops in industrial designs considered in the experiments are given in Table 2. Industrial designs 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. Table 2 also shows results obtained by using the acceleration techniques described above. Results using the basic algorithm of FIG. 4 are reported in column 2-φ. Results obtained using the acceleration techniques discussed above are reported in column 2-φ*. In general, we find that the compaction time is about 2 to 10 times the initial fault simulation time. Compaction with accelerated two-phase restoration runs 2 to 5 times faster than linear vector restoration. For example for industrial design p29, compaction with accelerated two-phase restoration was completed in 12380 seconds. For the same circuit, compaction with improved linear vector restoration required 41616 seconds. Using the proposed restoration technique, the compaction system was able to complete on large designs containing about 200,000 gates and 5000 flip flops, while LVR* did not complete even after 2 CPU days. The overlapped validation and refinement algorithms have proven to be extremely useful for large designs. Results for these techniques are reported in column 2-φ*. The 2-φ* version is particularly effective for circuits with large segments. For example, in industrial design p306 there is a segment of 2666 vectors and the use of 2-φ* algorithm results in more than a factor of 2 improvement in CPU seconds.

[0147] The experimental results demonstrate the superiority of the new vector restoration technique. Described technique significantly improves the run times of vector restoration based static compaction algorithms.

[0148] IVD. Conclusion

[0149] The vector restoration technique described above is significantly superior to existing techniques. The new technique performs vector restoration by repeatedly iterating over two phases: validation and refinement. The described technique can restore subsequences that satisfy additional conditions such as: (1) target faults are detected assuming a known initial state before application of the subsequence, or (2) restored subsequence forms a segment. Subsequences that satisfy additional properties are useful in static test sequence compaction and fault diagnosis methods. Several acceleration techniques for vector restoration are also disclosed. Results from experiments on ISCAS designs and several large industrial designs confirm the practicality of presented approach.

[0150] Other modifications and variations to the invention will be apparent to those skilled in the art from the foregoing disclosure and teachings. Thus, while only certain embodiments of the invention have been specifically described herein, it will be apparent that numerous modifications may be made thereto without departing from the spirit and scope of the invention.