Hybrid solver for integrated circuit diagnostics and testing

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 or test circuit into the polynomial formula comprises representing each logic gate using a corresponding polynomial.

17. The computing system of claim 15 , wherein converting the design of the diagnostic or test circuit into the polynomial formula comprises reducing an order of the polynomial formula to obtain a quadratic polynomial formula.

18. The computing system of claim 17 , 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.

19. The computing system of claim 15 , 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.

20. The computing system of claim 15 , wherein the hardware-based solver comprises an Ising machine.