IP Library › Granted Patent US 12,306,247
Granted Patent B2
US 12,306,247 · App. 17/226,950 · Granted May 20, 2025

System and method for optimizing fault coverage based on optimized test point insertion determinations for logical circuits

Inventors: Spencer Millican (Auburn, AL); Yang Sun (Auburn, AL); Soham Roy (Auburn, AL); Vishwani D. Agrawal (Auburn, AL)
Assignee: Auburn University
G01R31/31835G06F30/337G06N3/045G06N20/00G06F2117/02
View Patent ↗
Loading inventors, assignments & file history…
Monitor This Case
Get email alerts when status or documents change.
Order Certified Copies
Most orders are placed with the USPTO same day — all within 24 business hours.
Order via The Patent Place →
Pre-filled with this patent's details
Quick Facts
Patent No.
US 12,306,247
App. No.
17/226,950
Granted
May 20, 2025
Kind
B2
Abstract

The methods and systems are directed to automated computer analysis and machine learning. Specifically, the systems and methods for using machine learning to generate fault prediction models and applying the fault prediction models to logical circuits to optimize test point insertion determinations and optimize fault detection in the logical circuit. Disclosed are methods and systems that that generates training data from training circuits (and optionally generate training circuits), trains a learning segment (which may include an artificial neural network (ANN)) using the training data. The learning segment (once trained) generates fault prediction models to predict the quality of a TP inserted on a given circuit location and optimize TPI for a given circuit. The methods and systems described provide computational (CPU/processing) time advantages and precision over conventional methods.

Claims (54)

1. A method for optimizing fault coverage for logical circuits, comprising:

receiving a set of training circuit data, wherein the set of training circuit data includes at least one training circuit;

analyzing the training circuit data for each training circuit in the set training circuit data to generate a set of training data, wherein the generation of training data includes selecting at least one candidate test point for training circuit, performing fault simulation on each training circuit and associated at least one candidate test point for each candidate test point and associated training circuit, and generating structured training data for each training circuit and associated candidate test point, based on the training circuit data, candidate test point, and fault simulation associated with each training circuit and associated candidate test point combination;

training a learning segment on the set of training data to learn to predict a change in fault coverage based on the set of training data;

generating at least one fault coverage model based on the learning of the learning segment, wherein the at least one fault coverage model predicts the change in fault coverage for a circuit;

selecting a plurality of candidate test points for a new circuit;

applying the at least one fault coverage model to the selected plurality of candidate test points to determine change in fault coverage for the new circuit;

stimulating test point insertion of an optimized test point, wherein the optimized test point is the candidate test point that meets a set of test point insertion rules based on results of the application of the at least one fault coverage model to the plurality of candidate test points;

analyzing the new circuit with the optimized test point to determine if a set of fault coverage optimization rules are achieved;

repeating the selecting, applying, simulating test point insertion, and analyzing steps above until the set of fault coverage optimization rules are achieved;

displaying the new circuit with the optimized test point after the fault coverage optimizations rules are achieved.

2. The method of claim 1 , wherein each training circuit in the training circuit data includes a set of gates and a set of inputs and a set of outputs associated with each gate representing an associated training circuit from the at least one training circuits.

3. The method of claim 2 , wherein the generation of the set of training data further includes:

for each training circuit in the set of training circuit data, converting the associated training circuit into a consistent fan-in/fan-out structure such that each gate in the associated training circuit that has been converted has only two inputs and only two fan-outs, wherein gates in the set of gates representing the associated training circuit with more than two inputs associated with the gate are replaced with an equivalent set of gates, inputs, and outputs to achieve the consistent fan-in/fan-out structure.

4. The method of claim 3 , wherein the generation of the set of training data further includes extracting at least one sub-circuit from each associated training circuit that has been converted and identifying at least one candidate test point for the at least one sub-circuit, wherein the fault simulation and generation of structured training data is performed for each extracted sub-circuit.

5. The method of claim 1 , wherein the structured test data includes one training circuit from the at least one training circuit, one-candidate test point from the at least one candidate test point associated with the one training circuit, and an output of the fault simulation, wherein the output of the fault simulation is a change in fault coverage.

6. The method of claim 1 , wherein the learning segment includes at least one artificial neural network, wherein the artificial neural network receives the set of test data and automatedly trains itself to predict an output of the fault simulation performed on each of the test circuits and candidate test points, wherein the output of the fault simulation is a change in fault coverage.

7. The method of claim 1 , wherein the change in fault coverage is one of stuck-at fault or delay fault.

8. The method of claim 1 , wherein the at least one candidate test point for the training circuit is one of a control-1 test point, a control-0 test point, or an observe test point.

9. The method of claim 1 , wherein the new circuit data includes a set of gates and a set of inputs and a set of outputs associated with each gate representing the new circuit data.

10. The method of claim 9 , further comprising converting the new circuit data into a consistent fan-in/fan-out structure such that each gate in the converted new circuit data has only two inputs and only two fan-outs, wherein gates in the set of gates representing the new circuit data with more than two inputs associated with the gate are replaced with an equivalent set of gates, inputs, and outputs to achieve the consistent fan-in/fan-out structure.

11. The method of claim 10 , wherein the selection of the plurality of candidate test points for the new circuit data includes selecting at least one candidate test point for each input and for each output for each gate in the new circuit data.

12. The method of claim 1 , further comprising extracting a sub-circuit from the new circuit data for each of the selected plurality of candidate test points and applying the at least one fault coverage model to the extracted sub-circuits, wherein the extracted sub-circuit is centered around the candidate test point.

13. The method of claim 1 , wherein the set of test point insertion rules compare the change in fault coverage for each of the plurality of candidate test points and determine that the optimized test point for simulated test point insertion is the candidate test point with a greatest change in fault coverage.

14. The method of claim 1 , further comprising generating at least a portion of the received set of training circuit data, wherein the generation of training circuit data includes creating at least one directed acyclic graph (DAG), converting each DAG into a random binary circuit, wherein the random binary circuit represents a training circuit of the at least one training circuits of the set of training circuit data.

15. The method of claim 14 , wherein the conversation of each DAG into a random binary circuit includes replacing all vertices of the DAG that have no outputs with a circuit input, replacing all of a set of other vertices of the DAG with a randomly selected gate, and replacing a set of dead-end vertices of the DAG with a circuit output.

16. A system for optimizing fault coverage for logical circuits, comprising:

a processor;

a display with a user interface to display an optimized simulated new circuit; and

a non-transitory computer readable medium programmed with computer readable code that upon execution by the processor causes the processor to:

receive a set of training circuit data, wherein the set of training circuit data includes at least one training circuit;

analyze the training circuit data for each training circuit in the set training circuit data to generate a set of training data, wherein the generation of training data includes selecting at least one candidate test point for training circuit, performing fault simulation on each training circuit and associated at least one candidate test point for each candidate test point and associated training circuit, and generating structured training data for each training circuit and associated candidate test point, based on the training circuit data, candidate test point, and fault simulation associated with each training circuit and associated candidate test point combination;

train a learning segment on the set of training data to learn to predict a change in fault coverage based on the set of training data;

generate at least one fault coverage model based on the learning of the learning segment, wherein the at least one fault coverage model predicts the change in fault coverage for a circuit;

select a plurality of candidate test points for a new circuit;

apply the at least one fault coverage model to the selected plurality of candidate test points to determine change in fault coverage for the new circuit;

stimulate test point insertion of an optimized test point, wherein the optimized test point is the candidate test point that meets a set of test point insertion rules based on results of the application of the at least one fault coverage model to the plurality of candidate test points;

analyze the new circuit with the optimized test point to determine if a set of fault coverage optimization rules are achieved;

repeat the selecting, applying, simulating test point insertion, and analyzing steps above until the set of fault coverage optimization rules are achieved;

display the new circuit with the optimized test point after the fault coverage optimizations rules are achieved.

17. The system of claim 16 , wherein the non-transitory computer readable medium further causes the processor to create a logic circuit based on the new circuit with the optimized test point after the fault coverage optimizations rules are achieved.

18. The system of claim 16 , wherein the learning segment includes at least one artificial neural network, wherein the artificial neural network receives the set of test data and automatedly trains itself to predict an output of the fault simulation performed on each test circuits and each associated candidate test, wherein the output of the fault simulation is a change in fault coverage.

19. The system of claim 16 , wherein the non-transitory computer readable medium further causes the processor to generate at least a portion of the received set of training circuit data, wherein the generation of training circuit data includes creating at least one directed acyclic graph (DAG), converting each DAG into a random binary circuit, wherein the random binary circuit represents a training circuit of the at least one training circuits of the set of training circuit data, further wherein the conversation of each DAG into a random binary circuit includes replacing all vertices of the DAG that have no outputs with a circuit input, replacing all of a set of other vertices of the DAG with a randomly selected gate, and replacing a set of dead-end vertices of the DAG with a circuit output.

20. A non-transitory computer readable medium programmed with computer readable code that upon execution by a processor causes the processor to execute a method for optimizing fault coverage for circuits, comprising:

receiving a set of training circuit data, wherein the set of training circuit data includes at least one training circuit;

analyzing the training circuit data for each training circuit in the set training circuit data to generate a set of training data, wherein the generation of training data includes selecting at least one candidate test point for training circuit, performing fault simulation on each training circuit and associated at least one candidate test point for each candidate test point and associated training circuit, and generating structured training data for each training circuit and associated candidate test point, based on the training circuit data, candidate test point, and fault simulation associated with each training circuit and associated candidate test point combination;

training a learning segment on the set of training data to learn to predict a change in fault coverage based on the set of training data;

generating at least one fault coverage model based on the learning of the learning segment, wherein the at least one fault coverage model predicts the change in fault coverage for a circuit;

selecting a plurality of candidate test points for a new circuit;

applying the at least one fault coverage model to the selected plurality of candidate test points to determine change in fault coverage for the new circuit;

stimulating test point insertion of an optimized test point, wherein the optimized test point is the candidate test point that meets a set of test point insertion rules based on results of the application of the at least one fault coverage model to the plurality of candidate test points;

analyzing the new circuit with the optimized test point to determine if a set of fault coverage optimization rules are achieved;

repeating the selecting, applying, simulating test point insertion, and analyzing steps above until the set of fault coverage optimization rules are achieved;

displaying the new circuit with the optimized test point after the fault coverage optimizations rules are achieved.

Assignments (1)
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Jan 28, 2022
From: MILLICAN, SPENCER; SUN, YANG; ROY, SOHAM; AGRAWAL, VISHWANI D
To: AUBURN UNIVERSITY
Reel/Frame 058809/0595 →
Continuity (4)
Provisional Application 63123717 · Dec 10, 2020
Provisional Application 63111943 · Nov 10, 2020
Provisional Application 63007495 · Apr 9, 2020
Related Publication 20210318379A1 · Oct 14, 2021
References Cited (48)
US 11010516B2 · Sikka · 2021 [cited by examiner]
Geuzebroek et al. Test Point Insertion that facilitates ATPG in reducing test time and data volume IEEE 2002 (Year: 2002). [cited by examiner]
Chakradhar et al. Toward Massively Parallel Automatic Test Generation IEEE Transactions on Computer-Aided Design vol. 9 No. 9, Sep. 1990 (Year: 1990). [cited by examiner]
C. Acero et al., “Embedded Deterministic Test Points,” IEEE Transactions on Very Large Scale Integration VLSI System, vol. 25, No. 10, pp. 2949-2961, Oct. 2017. [cited by applicant]
Aminian and F. Aminian, “Neural-network based analog-circuit fault diagnosis using wavelet transform as preprocessor,” IEEE Trans. Circuits Syst. II Analog Digit. Signal Process., vol. 47, No. 2, pp. 151-156, 2000. [cited by applicant]
P. H. Bardell and W. H. McAnney, “Self-Testing of Multichip Logic Modules,” in Proc. International Test Conference (ITC), 1982, pp. 200-204. [cited by applicant]
F. Brglez, “On Testability Analysis of Combinational Networks,” in Proc. IEEE International Symposium on Circuits and Systems (ISCAS), May 1984, pp. 221-225. [cited by applicant]
F. Brglez and H. Fujiwara, “A Neutral Netlist of 10 Combinational Benchmark Circuits and a Targeted Translator in Fortran,” in IEEE International Symposium on Circuits and Systems, Jun. 1985, pp. 1929-1934. [cited by applicant]
A. Briers and Totton, K., “Random pattern testability by fast fault simulation,” in Proc. IEEE International Test Conference, 1986, pp. 274-281. [cited by applicant]
T. Chakradhar, M. L. Bushnell, and V. D. Agrawal, “Toward massively parallel automatic test generation,” IEEE Trans. Comput. Des. Integr. Circuits Syst., vol. 9, No. 9, pp. 981-994, Sep. 1990. [cited by applicant]
M. Chern et al., “Improving Scan Chain Diagnostic Accuracy Using Multi-Stage Artificial Neural Networks,” in Proc. 24th Asia and South Pacific Design Automation Conference, New York, NY, Jan. 2019, pp. 341-346. [cited by applicant]
F. Como, M. S. Reorda, and G. Squillero, “RT-level ITC'99 benchmarks and first ATPG results,” IEEE Des. Test Comput., vol. 17, No. 3, pp. 44-53, 2000. [cited by applicant]
R. David, “Signature Analysis for Multiple-Output Circuits”, IEEE Trans. Comput., vol. C-35, No. 9, pp. 830-837, Sep. 1986. [cited by applicant]
S. Davidson, “ITC'99 Benchmark Circuits—Preliminary Results,” in Proc. IEEE International Test Conference, Atlantic City, NJ, Jan. 1999, pp. 1125-1125. [cited by applicant]
M. J. Geuzebroek, J. T. Van Der Linden, and a. J. Van De Goor, “Test point insertion for compact test sets,” Proc. Int. Test Conf. 2000 (IEEE Cat. No. 00CH37159), pp. 292-301, 2000. [cited by applicant]
M. J. Geuzebroek, J. T. Van Der Linden, and a. J. Van De Goor, “Test point insertion that facilitates ATPG in reducing test time and data volume,” Proceedings. Int. Test Conf., 2002. [cited by applicant]
S. Ghosh, E. MacDonald, S. Basu, and N. A. Touba, “Low-power Weighted Pseudo-random BIST Using Special Scan Cells,” in Proc. 14th ACM Great Lakes Symposium on VLM (GLSVLSI), New York, NY, USA, 2004, pp. 86-91. [cited by applicant]
S. Ghosh, S. Bhunia, A. Raychowdhury, and K. Roy, “A Novel Delay Fault Testing Methodology Using Low-Overhead Built-In Delay Sensor,” IEEE Transaction Computer-Aided Design Integration Circuits System, vol. 25, No. 12, … [cited by applicant]
L. R. Gomez and H. Wunderlich, “A Neural-Network-Based Fault Classifier,” in Proc. 25th IEEE Asian Test Symposium (ATS), 2016, pp. 144-149. [cited by applicant]
J. P. Hayes and A. D. Friedman, “Test Point Placement to Simplify Fault Detection,” IEEE Trans. Comput., vol. C-23, No. 7, pp. 727-735, 1974. [cited by applicant]
F. P. Higgins and R. Srinivasan, “BSM2: next generation boundary-scan master,” in Proc. 18th IEEE VLSI Test Symposium (VTS), Montreal, Quebec, Canada, 2000, pp. 67-72. [cited by applicant]
S. Hellebrand, J. Rajski, S. Tarnick, S. Venkataraman, and B. Courtois, “Built-in Test for Circuits with Scan Based on Reseeding of Multiplepolynomial Linear Feedback Shift Registers,” IEEE Trans. Comput., vol. 44, No. … [cited by applicant]
B. Karlik, “Performance analysis of various activation functions in generalized MLP architectures of neural networks,” Int. J. Artif Intell. Expert Syst., \o\. I, No. 4, pp. 111-122, 2015. [cited by applicant]
G. N. Karystinos and D. A. Pados, “On overfitting, generalization, and randomly expanded training sets,” IEEE Transaction Neural Networks, vol. 11, No. 5, pp. 1050-1057, Sep. 2000. [cited by applicant]
D. P. Kingma and J. Ba, “Adam: A Method for Stochastic Optimization,” Dec. 2014, Accessed: Oct. 5, 2020. [Online]. Available: http://arxiv.org/abs/1412.6980. [cited by applicant]
I. Koren and Z. Koren, “Defect Tolerance in VLSI Circuits: Techniqi and Yield Analysis,” Proc. IEEE, vol. 86, No. 9, pp. 1819-1838, Sep. 1998. [cited by applicant]
B. Krishnamurthy, “A Dynamic Programming Approach to the Test Point Insertion Problem,” in Proc. 24th ACM/IEEE Design Automation Conference, New York, NY, USA, 1987, pp. 695-705. [cited by applicant]
Y. Ma et al., High Performance Graph Convolutional Networks with Applications in Testability Analysis, in Proc. 56th Annual Design Automation Conference (DAC), New York, NY, USA, 2019, pp. 18:1-18:6. [cited by applicant]
A. L. Maas, A. Y. Hannun, and A. Y. Ng, “Rectifier nonlinearities improve neural network acoustic models,” in Proc. icml, 2013, vol. 30, No. 1, p. 3. [cited by applicant]
J. Mahmod, S. Millican, U. Guin, and V. Agrawal, “Delay Fault Testing: Present and Future,” in Proc. IEEE VLSI Test Symposium (VTS), Monterey, CA, 2019. [cited by applicant]
A. Menon, K. Mehrotra, C. K. Mohan, and S. Ranka, “Characterization of a Class of Sigmoid Functions with Applications to Neural Networks,” NeuralNetw., vol. 9, No. 5, pp. 819-835, Jul. 1996. [cited by applicant]
P. K. Nag, A. Gattiker, Sichao Wei, R. D. Blanton, and W. Maly, “Modeling the Economics of Testing: a DFT Perspective,” IEEE Design & Test Computers, vol. 19, No. 1, pp. 29-41, fan. 2002. [cited by applicant]
P. Nigh and A. Gattiker, Test Method Evaluation Experiments and Data, in Proc. International Test Conference (ITC), 2000, pp. 454-463. [cited by applicant]
D. Nguyen and B. Widrow, “Improving the learning speed of 2-layer neural networks by choosing initial values of the adaptive weights,” 1990 IJCNN Int. Jt. Conf. Neural Networks, pp. 21-26 vol. 3, 1990. [cited by applicant]
I. Pomeranz and S. M. Reddy, “Design-for-testability for Path Delay Faults in Large Combinational Circuits Using Test Points,” IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst., vol. 17, No. 4, pp. 333-343,Apr. 1998. [cited by applicant]
I. Pomeranz, “Computation of Seeds for LFSR-Based n-Detection Test Generation,” ACM Transaction on Design Automation of Electronic Systems, vol. 22, No. 2, pp. 1-13, Jan. 2017. [cited by applicant]
J. Pradeep, E. Srinivasan, and S. Himavathi, “Diagonal based feature extraction for handwritten character recognition system using neural network,” ICECT 2011—2011 3rd Int. Conf. Electron. Comput. Technol., vol. 4, pp. … [cited by applicant]
S. Roy, B. Stiene, S. K. Millican and V. D. Agrawal, “Improved Random Pattern Delay Fault Coverage Using Inversion Test Points,” in Proc. IEEE 28th North Atlantic Test Workshop (NATW), Burlington, VT, May 2019, pp. 206-… [cited by applicant]
J. Savir, “Skewed-Load Transition Test: Part I, Calculus,” in Proc. International Test Conference, Baltimore, MD, Sep. 1992, pp. 705-713. [cited by applicant]
K. Seshan, “Reliability Issues: Reliability Imposed Limits to Scaling,” in Handbook of Thin Film Deposition (Fourth Edition). William Andrew Publishing, 2018, pp. 43-62. [cited by applicant]
Y. Sun and S. Millican, “Test Point Insertion Using Artificial Neural Networks,” in Proc. IEEE Computer Society Annual Symposium on VLSI (ISVLSI), Miami, FL, Jul. 2019, pp. 253-258. [cited by applicant]
J. Sziray, “Test Generation and Computational Complexity,” in IEEE 17th Pacific Rim International Symposium on Dependable Computing, Pasadena, CA, Dec. 2011, pp. 286-287. [cited by applicant]
N. Tamarapalli and J. Rajski, “Constructive Multi-phase Test Point Insertion for Scan-based BIST,” in Proc. IEEE International Test Conference, Washington, DC, Oct. 1996, pp. 649-658. [cited by applicant]
H. Tatsumi, Y. Murai, and S. Tokumasu, “Logic circuit diagnosis by using neural networks,” in Proc. IEEE International Symposium on Multiple-Valued Logic, 2001, pp. 345-350. [cited by applicant]
N. A. Touba and E. J. McCluskey, “Test Point Insertion Based on Path Tracing,” in Proc. VLSI Test Symposium, 1996, pp. 2-8. [cited by applicant]
H.-C. Tsai, K.-T. Cheng, C.-J. Lin, and S. Bhawmik, “A Hybrid Algorithm for Test Point Selection for Scan-based BIST,” in Proc. 34th Design Automation Conference (DAC), Anaheim, CA, Jun. 1997, pp. 478-483. [cited by applicant]
T. W. Williams, “Test Length in a Self-Testing Environment,” IEEE Des. Test Comput., vol. 2, No. 2, pp. 59-63, Apr. 1985. M. Nakao, S. Kobayashi, K. Hatayama, K. Iijima, and S. Terada, “Low Overhead Test Point Insertion… [cited by applicant]
D. Xiang, X. Wen, and L. Wang, “Low-Power Scan-Based Built-In Self-Test Based on Weighted Pseudorandom Test Pattern Generation and Reseeding,” IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 25, N… [cited by applicant]