Peripheral partitioning and tree decomposition for partial scan

Details Peripheral partitioning and tree decomposition for partial scan Peripheral partitioning and tree decomposition for partial scan

2000-02-04

2003-01-07

Chung, Phung M. (Department: 2133)

Error detection/correction and fault detection/recovery

Pulse or data error handling

Digital logic testing

C714S724000

Reexamination Certificate

active

06505316

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The invention relates to scan techniques for sequential circuits. In particular, this invention relates to new partial scan techniques using peripheral partitioning and tree decomposition. The invention is embodied in a system to perform partial scan using peripheral partitioning and tree decomposition, in a method for partial scan using peripheral partitioning, in a method for partial scan using tree decomposition, and in a computer program product for enabling a computer to operate according to the method.
2. Related Work
Complexity of testing sequential circuits is well known in the prior art. Two fundamentally different approaches have been pursued in the prior art to reduce the complexity of testing sequential circuits: (1) a synthesis approach, where practitioners synthesize circuits that are easy to test, and/or (2) a design for testability approach, where post-synthesis modification techniques are employed to facilitate easy testing of the circuit.
The synthesis approach requires prohibitive computational resources. Also, when a hierarchical design methodology is used, integrating testability requirements involving different blocks or modules is difficult.
Design for testability techniques such as scan have been used widely for achieving high test coverage for sequential circuits. In scan techniques, memory elements (including flip-flops) in a circuit are chained into a shift register. A full scan involves the chaining of all the shift registers in the circuit to be tested. Scan provides for direct controllability and observability of all memory elements during the test mode. However, area and performance penalties of full scan design are unacceptable for many sequential circuit designs.
Partial scan techniques involve selecting only a subset of memory elements. This reduces area and performance penalties involved in a full scan.
Several approaches for selecting memory elements for partial scan have been suggested in the prior art. Testability analysis based approach is one of the approaches that is known in the prior art. See E. Trischler, “Incomplete Scan Path with an Automatic Test Generation Methodology,” in
Proceedings of the international Test Conference,
pp. 153-162, 1980; M. Abramovici, J. J. Kulikowski, and R. K. Roy, “The Best Flip-Flops to Scan,” in
Proceedings of the International Test Conference,
pp. 166-173, 1991; K. S. Kim and C. R. Kime, “Partial Scan by Use of Empirical Testability,” in
Proceedings of the International Conference on Computer-Aided Design,
pp. 314-317, November 1990; P. S. Parikh and M. Abramovici, “A Cost Based Approach to Partial Scan,” in
Proceedings of the
30
th ACM/IEEE Design Automation Conference,
pp. 255-259, June 1993 and D. Xiang and J. H. Patel, “A Global Algorithm for the Partial Scan Design Problem using Circuit State Information,” in
Proceedings of the International Test Conference,
pp. 548-557, October 1996.
Another method suggested in the prior art is a test generation based approach. See V. D. Agrawal, K. T. Cheng, D. D. Johnson, and T. Lin, “Designing Circuits with Partial Scan,”
IEEE Design and Test of Computers,
vol. 5, pp. 8-15, Apr. 1988; H.-K. T. Ma, S. Devadas, A. R. Newton, and A. Sangiovanni-Vincentelli, “An Incomplete Scan Design Approach to Test Generation for Sequential Machines,” in
Proceedings of the International Test Conference,
pp. 730-734, 1988; V. Chickermane and J. H. Patel, “A Fault Oriented Partial Scan Design Approach,” in
Proceedings of the International Conference on Computer
-
Aided Design,
pp. 400-403, November 1991; I. Park, D. S. Ha, and G. Sim, “A New Method for Partial Scan Design based on Propagation and Justification Requirements of Faults,” in
Proceedings of the International Test Conference,
pp. 413-422, October 1995; and V. Boppana and W. K. Fuchs, “Partial Scan Design based on State Transition Modeling,” in
Proceedings of the International Test Conference,
pp. 538-547, October 1996.
Functional or state machine analysis based approaches have also been used in the prior art. See V. Boppana and W. K. Fuchs, “Partial Scan Design based on State Transition Modeling,” in
Proceedings of the International Test Conference,
pp. 538-547, October 1996; C.-C. Lin, M. T.-C. Lee, M.Marek-Sadowska, and K.-C. Chen, “Cost Free Scan: A Low Overhead Scan Path Design Methodology,” in
Proc. of the International Conference on Computer
-
Aided Design,
November 1995; C. C. Lin, M.Marek-Sadowska, K. T. Cheng, and M. T. C. Lee, “Test Point Insertion: Scan Paths through Combinational Logic,” in
Proceedings of the
32
nd ACM/IEEE Design Automation Conference,
pp. 268-273, June 1995; D. Chang, M. T. C. Lee, M.Marek-Sadowska, T. Aikyo, and K. T. Cheng, “A Test Synthesis Approach to Reducing BALLAST DFT Overhead,” in
Proceedings of the
34
th ACM/IEEE Design Automation Conference,
pp. 466-471, June 1997.
Several practitioners have used a structural analysis based approach. See R. Gupta, R. Gupta, and M. A. Breuer, “The BALLAST Methodology for Structured Partial Scan Design,”
IEEE Transactions on Computers,
vol. C-39, pp. 538-544, Apr. 1990; K. T. Cheng and V. D. Agrawal, “A Partial Scan Method for Sequential Circuits with Feedback,”
IEEE Transactions on Computers,
vol. 39, pp. 544-548, April 1990; D. Lee and S. Reddy, “On Determining Scan Flip-Flops in Partial-Scan Designs,” in
Proceedings of the International Conference on Computer
-
Aided Design,
pp. 322-325, November 1990; A. Kunzmann and H. J. Wunderlich, “An Analytical Approach to the Partial Scan Problem,”
Journal of Electronic Testing: Theory and Applications,
vol. 1, pp. 163-174, 1990; S. Bhawmik, C. J. Lin, K. T. Cheng, and V. D. Agrawal, “Pascant: A Partial Scan and Test Generation System,” in
Custom Integrated Circuits Conference,
pp. 17.3.1-17.3.4, 1991; S. E. Tai and D. Bhattacharya, “A Three Stage Partial Scan Design Method using the Sequential Circuit Flow Graph,” in
Proceedings of the
7
th International Conference on VLSI Design,
pp. 101-106, January 1994; S. T. Chakradhar, A. Balakrishnan, and V. D. Agrawal, “An Exact Algorithm for Selecting Partial Scan Flip-Flops,” in
Proc. of the
31
st ACM/IEEE Design Automation Conf.,
pp. 81-86, June 1994; A. Balakrishnan and S. T. Chakradhar, “Sequential Circuits with Combinational Test Generation Complexity,” in 9
th International Conference on VLSI Design,
January 1996; and T. Ono, “Selecting Partial Scan Flip-flops for Circuit Partitioning,” in
Proceedings of the International Conference on Computer
-
Aided Design,
pp. 646-650, November 1994.
The testability analysis based methods use cost metrics during scan selection. The ability of testability based approaches to tightly correlate with sequential test generation effort required for large designs is not clearly established. Further, one often has to rely on the test generator to refine the measures and/or to gain confidence on the scan selection based on these testability measures. Some of the more sophisticated testability measures require large computational resources.
Test generation based approaches select scan memory elements based on identification of hard-to-detect faults. This approach is tightly coupled with the test generation tool and does not offer the designer any flexibility to determine scan flip-flops a priori. Further, scan selection strongly depends on the order of faults chosen by the test generation.
Often, one may have to perform multiple test generation runs to obtain good scan selection. This approach further constraints the already computationally intensive test generation process. Recent work by V. Boppana and W. K. Fuchs incorporates state machine analysis within the test generation based approach to select partial scan flip-flops. The applicability of such approaches to large designs have not been established.
Another recent functional approach showed that functional or cost-free scan paths can be established for any scan selection. See C.-C. Lin et al., “Cost Free Scan: A Low Overhead Scan Path Design Methodology,” in
Proc. of

Affiliated with

Also associated with

Rating

Peripheral partitioning and tree decomposition for partial scan does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Peripheral partitioning and tree decomposition for partial scan, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Peripheral partitioning and tree decomposition for partial scan will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3037929