Hybrid solver for integrated circuit diagnostics and testing

Patent metadata

Field	Value
Publication number	US-12038478-B2
Application number	US-202217855012-A
Country	US
Kind code	B2
Filing date	Jun 30, 2022
Priority date	Jun 30, 2022
Publication date	Jul 16, 2024
Grant date	Jul 16, 2024

Abstract

One embodiment provides a method and a system for computing diagnoses for a physical system. During operation, the system can obtain a design of the physical system, generate a design of a diagnostic system by augmenting the design of the physical system based on a number of fault-emulating subsystems, and convert the design of the diagnostic system into a polynomial formula comprising a plurality of variables. The plurality of variables can include inputs and outputs of the original physical system and a number of ancillary variables. The system can further embed the polynomial formula on a hardware-based solver configured to perform optimization using the polynomial formula as an objective function to obtain a diagnostic vector used for explaining faults in the physical system.

First claim

What is claimed is:

1. A computer-implemented method for computing diagnostics for a to-be-diagnosed circuit, the method comprising:
obtaining, by a computer, a design of the to-be-diagnosed circuit comprising a plurality of logic gates;
generating a design of a diagnostic system by augmenting the design of the to-be-diagnosed circuit based on a number of fault-emulating subcircuits, wherein augmenting the design of the to-be-diagnosed circuit comprises inserting a fault-emulating subcircuit at an output of each logic gate within the to-be-diagnosed circuit, wherein the fault-emulating subcircuit comprises first and second assumable inputs for respectively emulating stuck-at-0 and stuck-at-1 faults;
converting the design of the diagnostic circuit into a polynomial formula comprising a plurality of variables, wherein the plurality of variables comprise inputs and outputs of the circuit and a number of ancillary variables, wherein the inputs comprise the first and second assumable inputs of the fault-emulating subcircuits, and wherein the ancillary variables comprise outputs of logic gates within the diagnostic circuit; and
embedding the polynomial formula on a hardware-based solver configured to perform optimization using the polynomial formula as an objective function to obtain a diagnostic vector used for explaining faults in the to-be-diagnosed circuit.

2. The method of claim 1 , wherein converting the design of the diagnostic circuit into the polynomial formula comprises representing each logic gate using a corresponding polynomial.

3. The method of claim 1 , further comprising splitting the diagnostic circuit into a plurality of subcircuits by implementing a cube-and-conquer technique, thereby facilitating parallel processing.

4. The method of claim 1 , wherein converting the design of the diagnostic circuit comprises reducing an order of the polynomial formula to obtain a quadratic polynomial formula.

5. The method of claim 4 , wherein reducing the order of the polynomial formula comprises:
determining an occurrence frequency of a product of a k-tuple of variables selected from the plurality of variables, wherein k is an integer;
determining a ranking of the k-tuple of variables based on the occurrence frequency of the product; and
in response to determining that the ranking is higher than a predetermined ranking, introducing an additional ancillary variable to replace the product of the k-tuple of variables.

6. The method of claim 1 , further comprising mapping the polynomial formula to a formula embeddable on the hardware-based solver, wherein mapping the polynomial formula to the embeddable formula comprises solving a graph isomorphism problem.

7. The method of claim 1 , wherein the hardware-based solver comprises an Ising machine.

8. A non-transitory computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method for generating test vectors for a to-be-tested circuit, the method comprising:
obtaining a design of the to-be-tested circuit comprising a plurality of logic gates;
generating a design of a test circuit by augmenting the design of the to-be-tested circuit based on a number of fault-emulating subcircuits, wherein augmenting the design of the to-be-tested circuit comprises inserting a fault-emulating subcircuit at an output of each logic gate within the to-be-tested circuit, wherein the fault-emulating subcircuit comprises first and second assumable inputs for respectively emulating stuck-at-0 and stuck-at-1 faults;
converting the design of the test circuit into a polynomial formula comprising a plurality of variables, wherein the plurality of variables comprise inputs and outputs of the test circuit and a number of ancillary variables, wherein the inputs comprise the first and second assumable inputs of the fault-emulating subcircuits, and wherein the ancillary variables comprise outputs of logic gates within the test circuit; and
embedding the polynomial formula on a hardware-based solver configured to perform optimization using the polynomial formula as an objective function to obtain the test vectors used for testing potential faults in the to-be-tested circuit.

9. The non-transitory computer-readable storage medium of claim 8 , wherein converting the design of the test circuit into the polynomial formula comprises representing each logic gate using a corresponding polynomial.

10. The non-transitory computer-readable storage medium of claim 8 , wherein the method further comprises splitting the test circuit into a plurality of subcircuits by implementing a cube-and-conquer technique, thereby facilitating parallel processing.

11. The non-transitory computer-readable storage medium of claim 8 , wherein converting the design of the test circuit comprises reducing an order of the polynomial formula to obtain a quadratic polynomial formula.

12. The non-transitory computer-readable storage medium of claim 11 , wherein reducing the order of the polynomial formula comprises:
determining an occurrence frequency of a product of a k-tuple of variables selected from the plurality of variables, wherein k is an integer;
determining a ranking of the k-tuple of variables based on the occurrence frequency of the product; and
in response to determining that the ranking is higher than a predetermined ranking, introducing an additional ancillary variable to replace the product of the k-tuple of variables.

13. The non-transitory computer-readable storage medium of claim 8 , wherein the method further comprises mapping the polynomial formula to a formula embeddable on the hardware-based solver, and wherein mapping the polynomial formula to the embeddable formula comprises solving a graph isomorphism problem.

14. The non-transitory computer-readable storage medium of claim 8 , wherein the hardware-based solver comprises an Ising machine.

15. A computing system, comprising:
a processor; and
a memory coupled to the processor and storing instructions that when executed by the processor cause the processor to perform a method for computing diagnoses or generating test vectors for a digital circuit, the method comprising
receiving a design of the digital circuit comprising a plurality of logic gates;
generating a design of a fault-augmented diagnostic or test circuit by augmenting the design of the digital circuit based on a number of fault-emulating subcircuits, wherein augmenting the design of the digital circuit comprises inserting a fault-emulating subcircuit at an output of each logic gate within the digital circuit, wherein the fault-emulating subcircuit comprises first and second assumable inputs for respectively emulating stuck-at-0 and stuck-at-1 faults;
converting the design of the fault-augmented diagnostic or test circuit into a polynomial formula comprising a plurality of variables, wherein the plurality of variables comprise inputs and outputs of the fault-augmented diagnostic or test circuit and a number of ancillary variables, wherein the inputs comprise the first and second assumable inputs of the fault-emulating subcircuits, and wherein the ancillary variables comprise outputs of logic gates within the fault-augmented diagnostic or test circuit; and
embedding the polynomial formula on a hardware-based solver configured to perform optimization using the polynomial formula as an objective function to obtain a diagnostic vector used for explaining faults or the test vectors used for testing potential faults in the digital circuit.

16. The computing system of claim 15 , wherein converting the design of the diagnostic

Assignees

• Palo Alto Res Ct Inc
• Xerox Corp

Inventors

• Feldman Aleksandar B
• De Kleer Johan
• Campos Perez Alexandre
• Matei Ion

Classifications

• G01R31/318558

  Addressing or selecting of subparts of the device under test · CPC title

• G06F17/10

  Complex mathematical operations {(function generation by table look-up G06F1/03; evaluation of elementary functions by calculation G06F7/544)} · CPC title

• G01R31/31709

  Jitter measurements; Jitter generators (measuring jitter, noise figure or signal-to-noise ratio per se G01R29/26; analysis of tester signals G01R31/31901) · CPC title

• H04L1/205

  jitter monitoring · CPC title

• G01R31/3177

  Testing of logic operation, e.g. by logic analysers · CPC title