Automatic test pattern generation-based circuit verification method and apparatus
12313680 ยท 2025-05-27
Assignee
Inventors
- Huiling Zhen (Hong Kong, CN)
- Miaohui Chen (Shenzhen, CN)
- Mingxuan Yuan (Hong Kong, CN)
- Naixing Wang (Shenzhen, CN)
- Wanqian Luo (Chengdu, CN)
- Yu HUANG (Shenzhen, CN)
Cpc classification
G06F30/33
PHYSICS
G06F30/3323
PHYSICS
G01R31/318342
PHYSICS
International classification
G01R31/3183
PHYSICS
G06F30/33
PHYSICS
Abstract
An automatic test pattern generation-based circuit verification method, comprises determining a to-be-detected first logic cone from a fan-out logic cone corresponding to the target line; determining, based on the first logic cone, a to-be-detected second logic cone from a fan-in logic cone corresponding to the target line; generating a first conjunctive normal form (CNF) based on the first logic cone and the second logic cone, and detecting the target line by using the first CNF to obtain a first detection result; and if the first logic cone is a partial region in the fan-out logic cone, and the first detection result meets a first specified condition corresponding to the first logic cone, determining a first verification result of the target line based on the first detection result.
Claims
1. A method comprising: selecting, a first logic cone from a fan-out logic cone corresponding to a target line in a circuit to be tested, wherein the fan-out logic cone comprises a first gate circuit that extends from the target line to an output end of the circuit; identifying, based on the first logic cone, a second logic cone in a fan-in logic cone corresponding to the target line, wherein the fan-in logic cone comprises a second gate circuit that extends from an input end of the circuit to the target line, and wherein the second logic cone comprises a third gate circuit that affects a first output value of the first logic cone; generating a first conjunctive normal form (CNF) based on the first logic cone and the second logic cone; detecting the target line using the first CNF to obtain a first detection result, wherein the first detection result indicates a fault type of the target line; and obtaining, when the first logic cone is a partial region in the fan-out logic cone and the first detection result meets a first specified condition corresponding to the first logic cone, a first verification result of the target line based on the first detection result.
2. The method according to claim 1, wherein the method further comprises further obtaining the first verification result based on the first detection result when the first logic cone is an entire region of the fan-out logic cone.
3. The method according to claim 1, wherein the method further comprises identifying, when the first logic cone is the partial region in the fan-out logic cone and the first detection result does not meet the first specified condition, a third logic cone from the fan-out logic cone, and wherein the third logic cone and the first logic cone are different.
4. The method according to claim 1, wherein selecting the first logic cone comprises selecting the first logic cone based on a preset initial depth value and a first step value, and wherein the initial depth value represents a distance between the target line and the first gate circuit.
5. The method according to claim 4, wherein the first specified condition is that the fault type in the first detection result is a difficult-to-detect fault.
6. The method according to claim 1, wherein selecting the first logic cone comprises selecting the first logic cone based on a preset quantity of output ends and a first step value.
7. The method according to claim 6, wherein the first detection result comprises: the fault type and a test pattern, wherein the test pattern is for performing circuit fault detection on the circuit; and the first specified condition is that the fault type in the first detection result is a detectable fault.
8. The method according to claim 1, wherein the method further comprises: selecting a third logic cone from the fan-out logic cone; selecting a fourth logic cone from the fan-in logic cone, wherein the third logic cone is different from the first logic cone, and wherein the fourth logic cone is in the fan-in logic cone and comprises a fourth gate circuit that affects a second output value of the third logic cone; generating a second CNF based on the third logic cone and the fourth logic cone, and detecting the target line using the second CNF to obtain a second detection result, wherein the second detection result indicates the fault type of the target line; when the first verification result is not obtained, the third logic cone is a partial region in the fan-out logic cone, and the second detection result meets a second specified condition corresponding to the third logic cone: obtaining a second verification result corresponding to the target line based on the second detection result; and stopping detecting the target line by using the first CNF; and stopping, when the first verification result is obtained, detecting the target line by using the second CNF.
9. The method according to claim 1, wherein the first CNF comprises at least one clause that is based on a fourth gate circuit in the first logic cone and a fifth gate circuit in the second logic cone.
10. The method according to claim 9, wherein the detecting the target line comprises: separately performing, when a quantity of clauses in the first CNF is greater than or equal to a specified threshold, a satisfiability (SAT) solution on the at least one clause; obtaining an SAT solution result of each of the at least one clause; and using an intersection of the SAT solution result of each of the at least one clause as the first detection result.
11. The method according to claim 9, wherein the first CNF comprises at least one target clause corresponding to at least one first target sub-circuit in the first logic cone and at least one target clause corresponding to at least one second target sub-circuit in the second logic cone, wherein the at least one first target sub-circuit is in a one-to-one correspondence with the at least one target clause, and wherein any of the at least one first target sub-circuit and the at least one second target sub-circuit comprises at least one fourth gate circuit.
12. The method according to claim 11, wherein before selecting the first logic cone, the method further comprises: identifying, when a quantity of gate circuits in the fan-in logic cone and the fan-out logic cone is greater than a first specified threshold, a first target sub-circuit in the fan-in logic cone based on the second gate circuit in the fan-in logic cone; and identifying a second target sub-circuit in the fan-out logic cone based on the first gate circuit in the fan-out logic cone.
13. The method according to claim 12, wherein the first target sub-circuit or the second target sub-circuit is a fan-out free region (FFR).
14. The method according to claim 12, wherein before selecting the first logic cone, the method further comprises simplifying, when a quantity of gate circuits in the fan-in logic cone and the fan-out logic cone is greater than a second specified threshold, two equivalent gate circuits in the fan-in logic cone and the fan-out logic cone into one fourth gate circuit for generating a CNF clause, wherein the second specified threshold is less than the first specified threshold, and wherein the two equivalent gate circuits are two fifth gate circuits with a same input and a same output.
15. An apparatus comprising: at least one memory configured to store instructions; and at least one processor coupled to at least one memory and configured to execute the instructions to cause the apparatus to: select a first logic cone from a fan-out logic cone corresponding to a target line in a circuit, wherein the fan-out logic cone comprises a first gate circuit that extends from the target line to an output end of the circuit; identify, based on the first logic cone, a second logic cone in a fan-in logic cone corresponding to the target line, wherein the fan-in logic cone comprises a second gate circuit that extends from an input end of the circuit to the target line, and wherein the second logic cone comprises a third gate circuit that affects a first output value of the first logic cone; generate a first conjunctive normal form (CNF) based on the first logic cone and the second logic cone; detect the target line using the first CNF to obtain a first detection result, wherein the first detection result indicates a fault type of the target line; and obtain, when the first logic cone is a partial region in the fan-out logic cone and the first detection result meets a first specified condition corresponding to the first logic cone, a first verification result of the target line based on the first detection result.
16. The apparatus according to claim 15, wherein the at least one processor is further configured to execute the instructions to cause the apparatus to select the first logic cone based on a preset initial depth value and a first step value, wherein the initial depth value represents a distance between the target line and the first gate circuit.
17. The apparatus according to claim 15, wherein the first CNF comprises at least one clause that is based on a fourth gate circuit in the first logic cone and a fifth gate circuit in the second logic cone.
18. The apparatus according to claim 15, wherein the at least one processor is further configured to execute the instructions to cause the apparatus to further obtain the first verification result based on the first detection result when the first logic cone is an entire region of the fan-out logic cone.
19. The apparatus according to claim 15, wherein the at least one processor is further configured to execute the instructions to cause the apparatus to identify, when the first logic cone is the partial region in the fan-out logic cone and the first detection result does not meet the first specified condition, a third logic cone from the fan-out logic cone, wherein the third logic cone and the first logic cone are different.
20. A computer program product comprising computer-executable instructions stored on a non-transitory computer readable medium that, when executed by at least one processor, cause an apparatus to: select a first logic cone from a fan-out logic cone corresponding to a target line in a circuit, wherein the fan-out logic cone comprises a first gate circuit that extends from the target line to an output end of the circuit; identify, based on the first logic cone, a second logic cone in a fan-in logic cone corresponding to the target line, wherein the fan-in logic cone comprises a second gate circuit that extends from an input end of the circuit to the target line, and wherein the second logic cone comprises a third gate circuit that affects a first output value of the first logic cone; generate a first conjunctive normal form (CNF) based on the first logic cone and the second logic cone; detect the target line using the first CNF to obtain a first detection result, wherein the first detection result indicates a fault type of the target line; and obtain, when the first logic cone is a partial region in the fan-out logic cone and the first detection result meets a first specified condition corresponding to the first logic cone, a first verification result of the target line based on the first detection result.
Description
BRIEF DESCRIPTION OF DRAWINGS
(1)
(2)
(3)
(4)
(5)
(6)
(7)
(8)
(9)
(10)
(11)
(12)
(13)
(14)
(15)
(16)
(17)
(18)
DESCRIPTION OF EMBODIMENTS
(19) To facilitate understanding of embodiments of this disclosure, the following describes terms related to embodiments of this disclosure. (1) Gate circuit: A unit circuit for implementing basic logic operations and composite logic operations is referred to as a gate circuit. Commonly used gate circuits have AND gate, OR gate, NOT gate, NAND gate, NOR gate, AND NOR gate, XOR gate and the like in terms of logic functions. (2) Line: A line is a connection line between any two connected gate circuits in a circuit. For example,
(20) A FFR is a region corresponding to a sub-circuit that does not include a fan-out node. For example, in the circuit shown in
(21) A fan-in logic cone is a region formed by a gate circuit that passes from an input end of a circuit to a target line; and a fan-out logic cone is a region formed by a gate circuit that passes from a target line to an output end of a circuit.
(22) Generally, when a circuit is verified, both a quantity of fan-out nodes and a depth of a logic cone affect detection difficulty of the circuit. A larger quantity of fan-out nodes and a larger depth of the logic cone indicate a longer time and a higher difficulty in circuit verification. (5) ATPG is a program development language and may be used to detect fault types of a plurality of lines included in a circuit under test. When the circuit verification is performed based on the ATPG, the fault type of each line can be determined. For example, the fault type of each line is determined to be a detectable fault or a difficult-to-detect fault. When the fault type of the line is determined to be the detectable fault, a semiconductor device test is performed by using test patterns automatically generated by the program. The test patterns are loaded to an input end of the device in sequence, and output signals are collected and compared with pre-calculated output patterns to determine a test result, to detect the circuit fault. (6) CNF is a normal form of propositional formulas, and is mainly used to solve logical judgment of propositional formulas. A conjunctive normal form of a proposition is not unique. The conjunctive normal form of the proposition can be obtained through a truth table or equivalent transformation. The propositional conjunctions that can be included in the CNF formula are AND, OR, and NOT. (7) A SAT problem is a problem of determining whether there is an explanation satisfying a given proposition. In other words, the satisfiability problem asks whether variables of a given propositional formula can be consistently replaced with a value TRUE or FALSE, and when the formula is evaluated to be TRUE, the formula is said to be satisfiable. If there is no assignment that can make the proposition formula TRUE, that is, for all possible variable assignments, the result of the proposition formula is FALSE, the formula is said to be unsatisfiable. (8) A netlist is a file used to describe a connection relationship between circuit components in a circuit design. Generally, the netlist is a text file that complies with a relatively simple markup syntax.
(23) A chip is an integrated circuit manufactured on a surface of a semiconductor wafer and adopts a method of miniaturizing a circuit. With development of chip circuit manufacturing processes, a larger integrated circuit can be integrated on a smaller component, and enhancement of chip manufacturing capabilities provides more possibilities for development of smart devices.
(24) After a chip circuit is designed, the chip circuit needs to be verified to check whether the chip circuit has a defect. The circuit includes a plurality of gate circuits, and some larger integrated chips may include tens of thousands of gate circuits. In a chip circuit verification process, a line between any two connected gate circuits in the circuit needs to be detected. A possible circuit fault of each line is classified into two types. One circuit fault type is a detectable fault, and the detectable fault is a circuit fault indicating that a fault can be determined based on an output value of the circuit under test within a specified time when an input value of the circuit under test is assumed. Another circuit fault type is a difficult-to-detect fault. The difficult-to-detect fault indicates that the same output value is obtained regardless of which input value is given to a circuit under test. In this case, whether a to-be-detected line is a redundant line needs to be determined.
(25) In conclusion, when the chip circuit is verified, not only verification accuracy, but also verification efficiency and a verification coverage rate need to be ensured. An ATPG-based detection method may be used when a circuit is verified. According to the ATPG-based detection method, a detectable fault and a difficult-to-detect fault in the circuit may be detected. In addition, when it is determined that the circuit fault type is a detectable fault, a test pattern may be generated, and the test pattern may be used to detect the circuit fault. The following describes two common ATPG-based testing methods.
(26) Manner 1: ATPG-Based Detection Method According to a D Algorithm.
(27) When ATPG-based detection is performed according to the D algorithm, a plurality of lines included in a circuit under test are respectively tested, and if any one of the lines is faulty, a set of initially allocated values is selected, and the initially allocated values are transmitted from an input end of the circuit to an output end of the circuit according to a logic rule of the circuit under test. When there is no further circuit branch to which the values can be transmitted and there is no collision, an implicit value of each connection line in the circuit under test can be inferred, and a location of the fault can be determined by comparing with the truth table of the circuit under test. If a conflict occurs during transmission, that is, assuming that a line is faulty but no fault occurs during transmission, a new line needs to be selected for testing.
(28) According to the foregoing method, when a circuit fault is found, the D algorithm may be stopped, indicating that the fault type corresponding to the currently detected line is a detectable fault, and during actual fault detection, allocation of the circuit under test for fault detection may be adjusted based on a detection result. For example, faults that are logically better detected are first detected. If an entire search space is used or a specified quantity of detection times or a detection time is exceeded, and a solution for circuit fault detection is still not obtained, the D algorithm is stopped and the fault type corresponding to the currently detected line is considered as a difficult-to-detect fault.
(29) It can be learned from the foregoing description that, when ATPG-based detection is performed according to the D algorithm, detection efficiency is affected by selection of the initially allocated values. If the initially allocated values are not properly selected, a detection time of the circuit under test may be severely affected. In addition, the ATPG-based detection according to the D algorithm usually needs to use the entire search space to determine the fault type as a difficult-to-detect fault, which is time-consuming and costly.
(30) Manner 2: ATPG-Based Detection Method According to an SAT Algorithm.
(31) When ATPG-based detection is performed according to the SAT algorithm, each line of the circuit under test needs to be detected. A CNF is generated for each line and solved. The CNF corresponding to each line is generated based on a circuit structure and a circuit propagation characteristic. For example, the target line is detected. A CNF corresponding to the target line is generated, and the CNF may be used to describe a proposition of assuming that the target line is faulty.
(32) After the CNF corresponding to the target line is generated, satisfiability (SAT) solution needs to be performed on the CNF. Specifically, performing SAT solution on the CNF corresponding to the target line may be understood as determining whether there is a set of variable values that can make the proposition of assuming that the target line is faulty true. A result of performing SAT solution on the CNF corresponding to the target line may include satisfiable and unsatisfiable. When the SAT solution result of the CNF corresponding to the target line is satisfiable, it indicates that there is a set of variable values that can make the proposition of assuming that the target line is faulty true, the fault type of the target line is a detectable fault, and in this case, the determined set of variable values may be used as the test pattern. When a circuit fault of the circuit under test is detected, the test pattern may be used as an input value of the circuit under test to obtain an output value of the circuit under test, and the circuit fault is detected by comparing an accurate output value with an actual output value of the circuit under test. When the SAT solution result of the CNF corresponding to the target line is unsatisfiable, it indicates that there is no set of variable values that can make the proposition of assuming that the target line is faulty true, that is, the proposition of assuming that the target line is faulty is not valid regardless of which input value is given. The fault type of the target line is a difficult-to-detect fault. In this case, whether the target line is a redundant line needs to be checked.
(33) During specific implementation, the performing SAT solution on the CNF corresponding to the target line may be inputting the CNF into an SAT solver for solution, where the SAT solver is a black-box solver. After the CNF corresponding to the target line is input to the SAT solver, the SAT solution result output by the SAT solver may be directly obtained. Specifically, the SAT solver may output the SAT solution result of the CNF corresponding to the target line as satisfiable, and output a test pattern. In this case, it may be determined that the fault type of the target line is a detectable fault. Alternatively, the SAT solver may output the SAT solution result of the CNF corresponding to the target line as unsatisfiable. In this case, it may be determined that the fault type of the target line is a difficult-to-detect fault.
(34)
(35) However, as complexity of the circuit structure of the circuit under test increases, the time for generating the CNF is longer when the ATPG-based detection is performed based on SAT. For example, for a circuit under test with tens of thousands of gate circuits, during serial calculation, a time for generating the CNF is far greater than a time for solving the. This increases a verification time of the chip circuit and reduces verification efficiency of the chip circuit.
(36) In conclusion, low efficiency exists in currently common ATPG-based detection methods.
(37) Based on the foregoing problem, an embodiment of this application provides an ATPG-based circuit verification method, to improve circuit verification efficiency.
(38)
(39) S701: The ATPG apparatus determines a to-be-detected first logic cone from a fan-out logic cone corresponding to the target line.
(40) Optionally,
(41) In an optional implementation, in this embodiment of this disclosure, when determining the first logic cone from the fan-out logic cone corresponding to the target line, the ATPG apparatus may determine a partial depth region from the fan-out logic cone as the first logic cone. For example, refer to (b) in
(42) It should be noted that in the ATPG-based circuit verification method provided in this embodiment of this disclosure, when detecting the target line, the ATPG apparatus may first use a partial region of the fan-out logic cone corresponding to the target line as the first logic cone. When a first detection result corresponding to the target line is not determined based on the first logic cone, the first logic cone may be re-divided, for example, a region of the first logic cone is increased, to implement an incremental division manner. It may be understood that, when the ATPG apparatus performs division on the first logic cone a plurality of times, a largest first logic cone that can be determined is an entire region of the fan-out logic cone. For example, as shown in (d) in
(43) S702: The ATPG apparatus determines, based on the first logic cone, a to-be-detected second logic cone from a fan-in logic cone corresponding to the target line.
(44) Refer to
(45) According to this embodiment of this disclosure, the ATPG apparatus may determine a fault type of the target line by detecting the gate circuit included in the first logic cone and the gate circuit included in the second logic cone.
(46) S703: The ATPG apparatus generates a first conjunctive normal form CNF based on the first logic cone and the second logic cone, and detects the target line by using the first CNF to obtain a first detection result, where the first detection result indicates the fault type of the target line.
(47) Optionally, that the ATPG apparatus detects the target line by using the first CNF may be that the ATPG apparatus performs SAT solution on the first CNF, determines an SAT solution result of the first CNF, and determines the first detection result based on the SAT solution result of the first CNF. It can be learned from the foregoing description of the SAT solution that the SAT solution result of the first CNF may be unsatisfiable and satisfiable. If the SAT solution result of the first CNF is unsatisfiable, it indicates that the proposition of assuming that the target line is faulty corresponding to the first CNF is not true regardless of an input value for the circuit under test. In this case, the first detection result determined based on the solution result of the first CNF is a difficult-to-detect fault. If the SAT solution result of the first CNF is satisfiable, it indicates that there is a set of pattern values. When the set of pattern values is used as an input value of the circuit under test, the proposition of assuming that the target line is faulty corresponding to the first CNF is true. In this case, the first detection result determined based on the solution result of the first CNF is a detectable fault, and the set of determined pattern values may be used as test patterns for fault detection on the circuit under test.
(48) Optionally, the first CNF includes at least one clause, and the at least one clause is generated based on a gate circuit in the first logic cone and a gate circuit in the second logic cone. Each clause may represent a constraint condition, and the first CNF including the at least one clause may describe the proposition of assuming that the target line is faulty. When the SAT solution result of the first CNF is satisfiable, it indicates that there is a set of patterns that can make the first CNF true, that is, there is a set of patterns that can make the proposition of assuming that the target line is faulty true. In this case, the first detection result is a detectable fault. In this case, when the target line is faulty, the fault can be found. When the SAT solution result of the first CNF is unsatisfiable, it indicates that there is no set of patterns that can make the first CNF true, that is, the proposition of assuming that the target line is faulty is not true. In this case, the first detection result is a difficult-to-detect fault. In this case, whether the target line is a redundant line needs to be checked.
(49) To further improve efficiency of detecting the target line, an embodiment of this disclosure further provides an SAT solution method. Specifically, before performing solution on the first CNF, it is determined whether a quantity of clauses included in the first CNF is less than a specified threshold. When the quantity of clauses included in the first CNF is less than a specified threshold, the first CNF is input to an SAT solver, and an SAT solution result output by the SAT solver is obtained.
(50) When the quantity of clauses included in the first CNF is greater than or equal to the specified threshold, a sequence decision method of looking ahead calculation may be used to solve the first CNF. The method is an optimization method for online prediction, and a final decision may be predicted in advance by using an intermediate result of optimization. For example,
(51) Optionally, when the first CNF is solved by using the sequence decision method of looking ahead, the ATPG apparatus may further extract the clauses in the first CNF in a sampling manner for solution. For example, when the first CNF includes N clauses, M clauses in the clauses may be randomly sampled for parallel solution, where M<N. In addition, the remaining NM clauses are simultaneously solved, and an intersection of a plurality of obtained SAT solution results is used as the SAT solution result of the first CNF. In actual calculation, K clauses can be simultaneously extracted to enhance the online prediction result, where K is an integer greater than 1.
(52) S704: If the first logic cone is a partial region in the fan-out logic cone, and the first detection result meets a first specified condition corresponding to the first logic cone, the ATPG apparatus determines a first verification result of the target line based on the first detection result.
(53) In an optional implementation, when the first logic cone is the partial region in the fan-out logic cone, and the first detection result meets the first specified condition corresponding to the first logic cone, the ATPG apparatus may determine the first verification result of the target line based on the first detection result. For example, the first detection result is used as the first verification result.
(54) It may be understood that, when the target line is detected, a CNF is directly generated based on the fan-out logic cone and the fan-in logic cone that correspond to the target line, and accuracy of an obtained detection result can be ensured when the target line is detected by using the CNF. However, it can be learned from the foregoing description that when the circuit structure is complex, it takes a long time to generate a CNF based on the fan-out logic cone and the fan-in logic cone and perform SAT solution on the CNF, resulting in low circuit verification efficiency. Therefore, in this embodiment of this disclosure, the first logic cone may be determined from the fan-out logic cone. When the first logic cone is the partial region in the fan-out logic cone, the first verification result cannot be directly generated based on the first detection result, and the first specified condition needs to be set. When the first detection result meets the first specified condition, the first verification result is generated based on the first detection result, to ensure accuracy of the first verification result.
(55) It should be noted that different first logic cones may be obtained in different division manners of the first logic cones, and the first logic cones in different division manners respectively correspond to different first specified conditions. The following separately describes the first logic cones obtained in different division manners and manners of determining the first verification result in embodiments of this disclosure. Manner 1: The ATPG apparatus determines, based on an initial depth value and a first step value, the first logic cone from the fan-out logic cone.
(56) It should be noted that the initial depth value is a distance between the target line and the gate circuit.
(57)
(58) In the division manner provided in Manner 1, the first specified condition corresponding to the first logic cone is that the fault type in the first detection result is a difficult-to-detect fault, or may also be understood as that an SAT solution result of the first CNF is unsatisfiable. To be specific, when the fault type in the first detection result is the difficult-to-detect fault, the ATPG apparatus may determine a first verification result of the target line based on the first detection result. For example, the ATPG apparatus may use the first detection result as the first verification result.
(59) It may be understood that performing SAT solution on the first CNF is to determine whether there is a set of pattern values that can make a result of the first CNF true, that is, make a proposition of assuming that the target line is faulty true. When the SAT solution result of the first CNF is unsatisfiable, it indicates that there is no set of pattern values that can make the result of the first CNF true. In this case, even if the depth of the first logic cone is increased, it cannot be determined that there is the set of pattern values that can make the result of the first CNF true. Therefore, the first detection result obtained by detecting the target line based on the first CNF corresponding to the current first logic cone may be considered as the first verification result of the target line. According to the method, accuracy of the detection result of the target line can be ensured, and CNFs do not need to be generated for an entire fan-in region and an entire fan-out region. This improves circuit verification efficiency.
(60) In addition, when the first detection result does not satisfy the first specified condition, that is, the SAT solution result of the first CNF is satisfiable, the ATPG apparatus may return to performing the step of determining the first logic cone and the second logic cone. In this case, the ATPG apparatus may determine the first logic cone from the fan-out logic cone based on the initial depth value and the first step value. For example, the first step value is added to the initial depth value to determine a depth value. The ATPG apparatus uses, as the first logic cone, a region corresponding to the depth value in the fan-out logic cone. For example, refer to
(61) Optionally, the ATPG apparatus may repeat the step of determining the first logic cone and the second logic cone, and detecting the target line based on the first CNF, until the fault type in the first detection result is a difficult-to-detect fault. Alternatively, when the first logic cone determined by the ATPG apparatus is an entire region of the fan-out logic cone, whether the first detection result meets the first specified condition does not need to be determined again, and the first verification result may be determined directly based on the first detection result.
(62) It should be noted that, when determining a first logic cone again, the ATPG apparatus may add a specified quantity of first step values to a depth value of the first logic cone that is determined last time, to determine the first logic cone in an incremental manner. Compared with a current manner of detecting a target line directly based on a fan-out region and a fan-in region, an amount of calculation is reduced and circuit verification efficiency is improved.
(63) The following further describes a method for detecting a target line based on Manner 1 by using an instance.
(64)
(65) In the division manner provided in Manner 2, the first specified condition corresponding to the first logic cone is that the fault type in the first detection result is a detectable fault, or may also be understood that an SAT solution result of the first CNF is SAT. To be specific, when the first detection result is the detectable fault, the ATPG apparatus may determine a first verification result of the target line based on the first detection result. For example, the ATPG apparatus may use the first detection result as the first verification result.
(66) It may be understood that performing SAT solution on the first CNF is to determine whether there is a set of pattern values that can make a result of the first CNF true. When the SAT solution result of the first CNF is satisfiable, it indicates that there is a set of pattern values that can make the result of the first CNF true. If the result of the first CNF is true, it indicates that the proposition of assuming that the target line is faulty is true. To be specific, in the current first logic cone, the proposition of assuming that the target line is faulty can be true. Even if a quantity of output ends included in the first logic cone is increased, a result that there is a set of patterns that can make the result of the first CNF true is not changed. Therefore, the first detection result obtained by detecting the target line based on the first CNF corresponding to the current first logic cone may be considered as the first verification result of the target line. According to the method, accuracy of the detection result of the target line can be ensured, and CNFs do not need to be generated for an entire fan-in region and an entire fan-out region. This improves circuit verification efficiency.
(67) In addition, when the first detection result does not satisfy the first specified condition, that is, the SAT solution result of the first CNF is unsatisfiable, the ATPG apparatus may return to performing the step of determining the first logic cone and the second logic cone. In this case, the ATPG apparatus may determine the first logic cone from the fan-out logic cone based on the preset quantity of output ends and the second step value. For example, a quantity value is determined by adding the second step value to the preset quantity of output ends. A region that is in the fan-out region and that includes the quantity of output ends is used as the first logic cone, to complete re-division of the first logic cone. For example, the re-divided first logic cone may be a logic cone b in
(68) It should be noted that the first logic cone obtained after the ATPG apparatus performs re-division may include the first logic cone determined last time. Alternatively, the first logic cone obtained after the re-division performed by the ATPG apparatus may not include the first logic cone determined last time. For example, the first logic cone obtained after the re-division may be a logic cone c in
(69) After determining a first logic cone and a second logic cone again, the ATPG apparatus may generate the first CNF again based on the first logic cone and the second logic cone, and repeat the step of detecting the target line based on the first CNF.
(70) Optionally, the ATPG apparatus may repeatedly determine the first logic cone and the second logic cone, and detect the target line based on the first CNF, until the fault type in the first detection result is a detectable fault. Alternatively, when the first logic cone determined by the ATPG apparatus is an entire region of the fan-out logic cone, or all determined first logic cones have traversed an entire region of the fan-out logic cone, whether the first detection result meets the first specified condition does not need to be determined again, and the first verification result may be determined directly based on the first detection result.
(71) It should be noted that, when determining a first logic cone again, the ATPG apparatus may add a specified quantity of second step values to a quantity of output ends of the first logic cone that is determined last time, to determine the first logic cone in an incremental manner. Compared with a current manner of detecting a target line directly based on a fan-out region and a fan-in region, an amount of calculation is reduced and circuit verification efficiency is improved.
(72) The following further describes a method for detecting a target line based on Manner 2 by using an instance.
(73) In an optional implementation of this application, the ATPG apparatus may detect the target line by using a dual-thread method. One thread may detect the target line according to the method provided in Manner 1, and the other thread may detect the target line according to the method provided in Manner 2. Specifically, the ATPG apparatus may start the first thread to determine the first logic cone and the second logic cone, and then generate the first CNF to detect the target line, to determine the first verification result. Simultaneously, the ATPG apparatus may further start the second thread to determine a third logic cone and a fourth logic cone, generate a second CNF based on the third logic cone and the fourth logic cone, and detect the target line based on the second CNF to determine a second verification result. For the method for determining the third logic cone and the fourth logic cone by the ATPG apparatus in the second thread and the method for detecting the target line based on the second CNF, refer to the implementation of Manner 1 or Manner 2. Details are not described again. It should be noted that, when the ATPG apparatus detects the target line by using the dual-thread method, manners of determining the first logic cone and the third logic cone are different. After the verification result is determined in one of the two threads, the other thread may stop working. For example, when first determining the first verification result in the first thread, the second thread stops working; or when the second verification result is first determined in the second thread, the first thread stops working.
(74) According to the foregoing method, the ATPG apparatus may determine, by using two threads, whether the fault type of the target line is a difficult-to-detect fault or a detectable fault, and may end detection of the target line after the verification result is determined in one thread. This further improves circuit verification efficiency.
(75) It can be learned from the foregoing description of the chip circuit that an integrated circuit in some chips is larger, for example, tens of thousands of gate circuits are integrated. For a chip with a larger circuit, when verification is performed on the chip circuit in this embodiment of this application, decomposition processing and/or simplification processing may alternatively be performed on the circuit. The following separately describes a circuit decomposition processing method and a circuit simplification processing method provided in embodiments of this application.
(76) 1. Circuit Decomposition Processing Method.
(77) Before determining the to-be-detected first logic cone from the fan-out logic cone, if determining that a quantity of gate circuits included in the fan-in logic cone and the fan-out logic cone is greater than a first specified threshold, the ATPG apparatus determines at least one target sub-circuit in the fan-in logic cone and at least one target sub-circuit in the fan-out logic cone, where the target sub-circuit may be an FFR.
(78) Optionally, that the ATPG apparatus determines that a quantity of gate circuits included in the fan-in logic cone and the fan-out logic cone is greater than a first specified threshold may be specifically that: The ATPG apparatus determines that a quantity of gate circuits in the fan-in logic cone and the fan-out logic cone meets at least one of the following conditions. Condition 1: A total quantity of gate circuits is greater than a first specified threshold; Condition 2: A quantity of fan-in gate circuits is greater than a first specified threshold; or Condition 3: A quantity of fan-out gate circuits is greater than a first specified threshold.
(79) The first specified threshold may be an empirical value.
(80) Optionally, after determining that the quantity of gate circuits included in the fan-in logic cone and the fan-out logic cone is greater than the first specified threshold, the ATPG apparatus may identify an FFR in the fan-in logic cone and the fan-out logic cone, and use each FFR as a target sub-circuit. After determining the first logic cone and the second logic cone, when generating the first CNF based on a gate circuit in the first logic cone and a gate circuit in the second logic cone, the ATPG apparatus may separately generate corresponding clauses for target sub-circuits included in the first logic cone and the second logic cone. Each target sub-circuit corresponds to a clause. It may be understood that a condition for a fault to propagate to any output end within an FFR is the same. Therefore, a fault propagated to a root node within an FFR may be represented by a clause. According to the method, the method for generating the first CNF can be simplified. This reduces a time required for generating the CNF, and improves circuit verification efficiency.
(81) 2. Circuit Simplification Processing Method.
(82) If determining that the quantity of gate circuits included in the fan-in logic cone and the fan-out logic cone is greater than a second specified threshold before determining the to-be-detected first logic cone from the fan-out logic cone, the ATPG apparatus simplifies two equivalent gate circuits in the fan-in logic cone and the fan-out logic cone into one gate circuit for generating a CNF clause, where the two equivalent gate circuits are two gate circuits with the same input and the same output.
(83) Optionally, the second specified threshold may be less than the first specified threshold. That is, during implementation, circuit decomposition processing and/or circuit simplification processing do not need to be performed on all circuits. The circuit simplification processing is performed when the quantity of gate circuits included in the fan-in logic cone and the fan-out logic cone is greater than the second specified threshold; and the circuit decomposition processing is performed when the quantity of gate circuits included in the fan-in logic cone and the fan-out logic cone is greater than the first specified threshold.
(84) Optionally, that the ATPG apparatus determines that a quantity of gate circuits included in the fan-in logic cone and the fan-out logic cone is greater than a second specified threshold may be specifically that the ATPG apparatus determines that a quantity of gate circuits in the fan-in logic cone and the fan-out logic cone meets at least one of the following conditions. Condition 1: A total quantity of gate circuits is greater than a second specified threshold; Condition 2: A quantity of fan-in gate circuits is greater than a second specified threshold; or Condition 3: A quantity of fan-out gate circuits is greater than a second specified threshold.
(85) The second specified threshold may be an empirical value.
(86) In an optional implementation, when the circuit corresponding to the fan-in logic cone and the fan-out logic cone is simplified, the circuit may be converted from a gate-level netlist form to a sum of product (SOP) form. A hash table corresponding to the fan-in logic cone and the fan-out logic cone is designed, and the circuit is preliminarily simplified by using a table lookup method. Specifically, if it is determined, according to the hash table, that outputs of two gate circuits with same inputs are also the same, it may be considered that the two gate circuits are equivalent. Further, a random pattern may be generated, and equivalence evaluation is performed on two gate circuits with the same input. For example, accurate calculation may be performed by using an SAT solver, to determine whether the two gate circuits are completely equivalent. After it is determined that the two gate circuits are equivalent, the two gate circuits may be simplified into one gate circuit for generating the CNF.
(87) Optionally, after the circuit is simplified until the quantity of gate circuits is less than or equal to the specified threshold, the simplification processing on the circuit may be stopped, or when there is no equivalent gate circuit in the circuit, the simplified processing on the circuit may be stopped.
(88) According to the method, equivalent gate circuits in the circuit corresponding to the fan-in logic cone and the fan-out logic cone may be simplified, to reduce a quantity of gate circuits that need to be considered when the first CNF is generated. This reduces difficulty in generating the first CNF and improves circuit verification efficiency.
(89) It should be noted that the circuit decomposition processing method may be executed by a circuit decomposition module in the ATPG apparatus, and the circuit simplification processing method may be executed by a circuit simplification module in the ATPG apparatus. The circuit decomposition module and the circuit simplification module may be plug-and-play modules.
(90) The following further describes an ATPG-based circuit verification method provided in an embodiment of this application by using a specific instance.
(91) The following further describes effects brought by the ATPG-based circuit verification method provided in embodiments of this application with reference to a result of testing performed on a hard case of a plurality of combined circuits by using the ATPG-based circuit verification method provided in embodiments of this application.
(92) First, several hard cases of the circuit under test in embodiments of this disclosure are described. Table 1 shows four circuits with different integration scales.
(93) TABLE-US-00001 TABLE 1 Name of a circuit under Maximum logic cone depth Quantity of gate test (max-depth) circuits b17 52 45339 b19 126 261358 b17-3 145 123360 b17-5 234 203664
(94) The circuit under test b17-5 has reached the logic cone depth of industrial large-scale circuits.
(95) The first set of test results are difficult-to-detect faults for the four circuits shown in Table 1 above (that is, redundant faults in actual industrial circuit detection and aborted faults that cannot be solved at a specified time. The faults are referred to as hard cases. From a perspective of optimization, the worst case of the hard cases requires full traversal of the search space. The faults are hard case faults for a heuristic detection method), as shown in Table 2.
(96) TABLE-US-00002 TABLE 2 Current SAT Name of a Detection time of the algorithm circuit method provided in Detection Increased under test this application (s) time (s) rate b17 2.43 4.08 40.44% b19 14.21 30.93 54.05% b17-3 181.02 388.15 53.36% b17-5 1481 5311.65 72.11%
(97) The second set of tests is test results obtained after the circuit under test b17-3 is detected according to the ATPG-based circuit verification method and the current ATPG-based circuit verification method provided in embodiments of this disclosure. The ATPG-based circuit verification method provided in this embodiment of this disclosure includes performing circuit simplification processing. The second set of test results is shown in Table 3.
(98) TABLE-US-00003 TABLE 3 ATPG-based circuit verification method provided in an embodiment of this Current ATPG-based circuit Name of a application verification method Increased circuit Test time Coverage Test time Coverage coverage under test (s) rate (s) rate rate b17-3 47.6 100% 19.3 0% 0.67% 30.2 90% 19.3 0% 0.59% 22.4 80% 19.3 0% 0.53% 16.8 70% 19.3 0% 0.47%
(99) The third set of tests is test results obtained after the circuit under test b17-5 is detected according to the ATPG-based circuit verification method and the current ATPG-based circuit verification method provided in embodiments of this disclosure. The ATPG-based circuit verification method provided in this embodiment of this disclosure includes performing circuit simplification processing. The third set of test results is shown in Table 4.
(100) TABLE-US-00004 TABLE 4 ATPG-based circuit verification method provided in an embodiment of this Current ATPG-based circuit Name of a application verification method Increased circuit Test time Coverage Test time Coverage coverage under test (s) rate (s) rate rate b17-5 298.5 100% 100.5 0% 1.297% 224.4 90% 100.5 0% 1.167% 115.6 80% 100.5 0% 1.037% 87.9 70% 100.5 0% 0.90%
drawn. 1. According to comparison of different scales, compared with an original ATPG-based detection method according to an SAT algorithm, the ATPG-based circuit verification method provided in this embodiment of this application has more prominent advantages with a larger circuit. 2. The coverage rate in the ATPG-based circuit verification method provided in this embodiment of this application may exceed the coverage rate in the current ATPG-based circuit verification method within a specific time limit. A specific analysis is as follows. (1) For the circuit under test b17-3 with a medium depth, according to the ATPG-based circuit verification method provided in this embodiment of this disclosure, more than 90% of faults that cannot be detected by using the current ATPG-based circuit verification method can be verified within twice a time of the current ATPG-based circuit verification method, increasing the coverage rate by 0.59%. In addition, according to the ATPG-based circuit verification method provided in this embodiment of this disclosure, 70% of faults that cannot be detected by using the current ATPG-based circuit verification method can be verified at a time shorter than that of the current ATPG-based circuit verification method, increasing the coverage rate by 0.47%. (2) For the circuit under test b17-5 with the maximum depth in the circuit under test, according to the ATPG-based circuit verification method provided in this embodiment of this disclosure, nearly 90% faults that cannot be detected by using the current ATPG-based circuit verification method can be verified within twice a time of the current ATPG-based circuit verification method, increasing the coverage rate by over 0.77%. In addition, according to the ATPG-based circuit verification method provided in this embodiment of this disclosure, about 70% of faults that cannot be detected by using the current ATPG-based circuit verification method can be verified within the same test time as the current ATPG-based circuit verification method, increasing the coverage rate by 0.9%.
(101) In addition, when the first CNF is solved by using the sequence decision method of looking ahead calculation provided in this embodiment of this disclosure, a test result of the large-scale circuit verification is shown in Table 5.
(102) TABLE-US-00005 TABLE 5 Test time for Test time for sampling a Test time sampling a plurality of for direct clause from clauses from Name of a circuit SAT the first CNF Increased the first CNF Increased under test solution (s) for SAT (s) rate for SAT (s) rate P2_SUB_414_U113 6.53 3.24 50.38% 3.56 (twice) 45.48% P2_SUB_414_U114 7.39 4.13 44.11% 4.02 (twice) 45.60% P2_SUB_355_U47 7.87 5.21 33.79% 4.23 (twice) 46.25% dated-5-19-u 4427 2532 42.81% 2218 (10 times) 49.90% Ndhf_xits_09_UNS 14400 8243 42.75% 7634 (10 times) 46.99%
(103) It can be learned from Table 5 that, when SAT solution is performed on the first CNF, an average increase of 42.77% is obtained in a clause sampled once, and an average increase of 46.84% is obtained in a clause sampled a plurality of times. The sequence decision method of looking ahead calculation provided in this embodiment of this disclosure significantly improves efficiency of SAT solution on the CNF.
(104) For a test result of the circuit simplification method provided in this embodiment of this disclosure in the circuit verification problem, refer to Table 6.
(105) TABLE-US-00006 TABLE 6 Test time Test time with no after Name of a circuit simplification simplification Increased under test processing (s) (s) rate P2_SUB_414_U113 0.21 0.147 30% P2_SUB_414_U114 0.40 0.29 27.5% P1_SUB_414_U64 5.97 4.29 28.14% P1_ADD_430_U83_2 1.96 1.44 26.53%
(106) It can be learned from Table 6 that after a simplification module is added, the performance of the ATPG-based method is improved by 28.04% on average.
(107) Finally, the ATPG-based circuit verification method provided in this embodiment of this disclosure is compared with the current ATPG-based circuit verification method. As shown in
(108) In conclusion, according to the ATPG-based circuit verification method provided in this embodiment of this disclosure, a symbol calculation feature of the SAT is fully utilized, and a detection procedure is divided into core modules such as circuit decomposition, circuit simplification, incremental calculation, and online prediction (Looking ahead). It effectively avoids a bottleneck of SAT calculation in ATPG, for example, a time for generating the CNF is too long or even longer than the solution time, and hidden structure information of the circuit is difficult to be included in the CNF. The ATPG-based circuit verification method provided in this embodiment of this disclosure may be directly used for detection of hard cases, to effectively increase the coverage rate.
(109) An embodiment of this application further provides an automatic test pattern generation apparatus 1600.
(110) The processor 1601 is configured to detect the target line by using the first CNF to obtain a first detection result, where the first detection result indicates a fault type of the target line; and if the first logic cone is a partial region in the fan-out logic cone, and the first detection result meets a first specified condition corresponding to the first logic cone, determine a first verification result of the target line based on the first detection result.
(111) In an implementation, the processor 1601 is further configured to if the first logic cone is an entire region of the fan-out logic cone, determine the first verification result based on the first detection result.
(112) In an implementation, the processor 1601 is further configured to if the first logic cone is the partial region in the fan-out logic cone, and the first detection result does not meet the first specified condition, determine a to-be-detected first logic cone again from the fan-out logic cone, where first logic cones determined different times are not all the same.
(113) In an implementation, the processor 1601 is specifically configured to determine, based on a preset initial depth value and a first step value, the first logic cone from the fan-out logic cone, where the initial depth value represents a distance between the target line and the gate circuit.
(114) In an implementation, the first specified condition is that the fault type in the first detection result is a difficult-to-detect fault.
(115) In an implementation, the processor 1601 is specifically configured to determine, based on a preset quantity of output ends and a second step value, the first logic cone from the fan-out logic cone.
(116) In an implementation, the first detection result includes the fault type and a test pattern, and the test pattern is used to perform circuit fault detection on the circuit under test; and the first specified condition is that the fault type in the first detection result is a detectable fault.
(117) In an implementation, the processor 1601 is further configured to determine a to-be-detected third logic cone from the fan-out logic cone; and determine a to-be-detected fourth logic cone from the fan-in logic cone, where the third logic cone is different from the first logic cone, and the fourth logic cone is a region that is in the fan-in logic cone and that is formed by a gate circuit that affects an output value of the third logic cone; and generate a second CNF based on the third logic cone and the fourth logic cone.
(118) The processor 1601 is further configured to detect the target line by using the second CNF to obtain a second detection result, where the second detection result indicates a fault type of the target line; when the first verification result is not determined, if the third logic cone is a partial region in the fan-out logic cone, and the second detection result meets a second specified condition corresponding to the third logic cone, determine a second verification result corresponding to the target line based on the second detection result, and stop detecting the target line by using the first CNF; and when the first verification result is determined, stop detecting the target line by using the second CNF.
(119) In an implementation, the first CNF includes at least one clause, and the at least one clause is generated based on a gate circuit in the first logic cone and a gate circuit in the second logic cone.
(120) In an implementation, the processor 1601 is specifically configured to if a quantity of clauses included in the first CNF is greater than or equal to a specified threshold, separately perform satisfiability SAT solution on the at least one clause, and determine an SAT solution result of each clause; and use an intersection of SAT solution results of the at least one clause as the first detection result.
(121) In an implementation, the first CNF includes at least one target clause corresponding to at least one target sub-circuit in the first logic cone and at least one target clause corresponding to at least one target sub-circuit in the second logic cone, where the target sub-circuit is in a one-to-one correspondence with the target clause, and any target sub-circuit includes at least one gate circuit.
(122) In an implementation, the processor 1601 is further configured to before the generation unit determines the to-be-detected first logic cone from the fan-out logic cone corresponding to the target line, if a quantity of gate circuits included in the fan-in logic cone and the fan-out logic cone is greater than a first specified threshold, determine a target sub-circuit in the fan-in logic cone based on the gate circuit in the fan-in logic cone, and determine a target sub-circuit in the fan-out logic cone based on the gate circuit in the fan-out logic cone.
(123) In an implementation, the target sub-circuit is a fan-out free region FFR.
(124) In an implementation, the processor 1601 is further configured to before the generation unit determines the to-be-detected first logic cone from the fan-out logic cone corresponding to the target line, if a quantity of gate circuits included in the fan-in logic cone and the fan-out logic cone is greater than a second specified threshold, simplify two equivalent gate circuits in the fan-in logic cone and the fan-out logic cone into one gate circuit for generating a CNF clause, where the second specified threshold is less than the first specified threshold, and the two equivalent gate circuits are two gate circuits with the same input and the same output.
(125) It may be understood that the memory 1602 in
(126) An embodiment of this disclosure further provides an automatic test pattern generation apparatus 1700.
(127) The generation unit 1701 is configured to perform the following procedures on a target line in a circuit under test, where the circuit under test includes a plurality of lines, any line is a connection line between two connected gate circuits, and the target line is any line in the plurality of lines; determine a to-be-detected first logic cone from a fan-out logic cone corresponding to a target line, where the fan-out logic cone is a region formed by a gate circuit that passes from the target line to an output end of the circuit under test; determine, based on the first logic cone, a to-be-detected second logic cone from a fan-in logic cone corresponding to the target line, where the fan-in logic cone is a region formed by a gate circuit that passes from an input end of the circuit under test to the target line, and the second logic cone is a region that is in the fan-in logic cone and that is formed by a gate circuit that affects an output value of the first logic cone; and generate a first conjunctive normal form CNF based on the first logic cone and the second logic cone.
(128) The detection unit 1702 is configured to detect the target line by using the first CNF to obtain a first detection result, where the first detection result indicates a fault type of the target line; and if the first logic cone is a partial region in the fan-out logic cone, and the first detection result meets a first specified condition corresponding to the first logic cone, determine a first verification result of the target line based on the first detection result.
(129) In an implementation, the detection unit 1702 is further configured to if the first logic cone is an entire region of the fan-out logic cone, determine the first verification result based on the first detection result.
(130) In an implementation, the generation unit 1701 is further configured to if the first logic cone is the partial region in the fan-out logic cone, and the first detection result does not meet the first specified condition, determine a to-be-detected first logic cone again from the fan-out logic cone, where first logic cones determined different times are not all the same.
(131) In an implementation, the generation unit 1701 is specifically configured to determine, based on a preset initial depth value and a first step value, the first logic cone from the fan-out logic cone, where the initial depth value represents a distance between the target line and the gate circuit.
(132) In an implementation, the first specified condition is that the fault type in the first detection result is a difficult-to-detect fault.
(133) In an implementation, the generation unit 1701 is specifically configured to determine, based on a preset quantity of output ends and a second step value, the first logic cone from the fan-out logic cone.
(134) In an implementation, the first detection result includes the fault type and a test pattern, and the test pattern is used to perform circuit fault detection on the circuit under test; and the first specified condition is that the fault type in the first detection result is a detectable fault.
(135) In an implementation, the generation unit 1701 is further configured to determine a to-be-detected third logic cone from the fan-out logic cone; and determine a to-be-detected fourth logic cone from the fan-in logic cone, where the third logic cone is different from the first logic cone, and the fourth logic cone is a region that is in the fan-in logic cone and that is formed by a gate circuit that affects an output value of the third logic cone; and generate a second CNF based on the third logic cone and the fourth logic cone.
(136) The detection unit 1702 is further configured to detect the target line by using the second CNF to obtain a second detection result, where the second detection result indicates a fault type of the target line; when the first verification result is not determined, if the third logic cone is a partial region in the fan-out logic cone, and the second detection result meets a second specified condition corresponding to the third logic cone, determine a second verification result corresponding to the target line based on the second detection result, and stop detecting the target line by using the first CNF; and when the first verification result is determined, stop detecting the target line by using the second CNF.
(137) In an implementation, the first CNF includes at least one clause, and the at least one clause is generated based on a gate circuit in the first logic cone and a gate circuit in the second logic cone.
(138) In an implementation, the detection unit 1702 is specifically configured to if a quantity of clauses included in the first CNF is greater than or equal to a specified threshold, separately perform satisfiability SAT solution on the at least one clause, and determine an SAT solution result of each clause; and use an intersection of SAT solution results of the at least one clause as the first detection result.
(139) In an implementation, the first CNF includes at least one target clause corresponding to at least one target sub-circuit in the first logic cone and at least one target clause corresponding to at least one target sub-circuit in the second logic cone, where the target sub-circuit is in a one-to-one correspondence with the target clause, and any target sub-circuit includes at least one gate circuit.
(140) In an implementation, the automatic test pattern generation apparatus further includes a circuit decomposition unit 1703. The circuit decomposition unit 1703 is configured to before the generation unit determines the to-be-detected first logic cone from the fan-out logic cone corresponding to the target line, if a quantity of gate circuits included in the fan-in logic cone and the fan-out logic cone is greater than a first specified threshold, determine a target sub-circuit in the fan-in logic cone based on the gate circuit in the fan-in logic cone, and determine a target sub-circuit in the fan-out logic cone based on the gate circuit in the fan-out logic cone.
(141) In an implementation, the target sub-circuit is a FFR.
(142) In an implementation, the automatic test pattern generation apparatus further includes a circuit simplification unit 1704. The circuit simplification unit 1704 is configured to before the generation unit determines the to-be-detected first logic cone from the fan-out logic cone corresponding to the target line, if a quantity of gate circuits included in the fan-in logic cone and the fan-out logic cone is greater than a second specified threshold, simplify two equivalent gate circuits in the fan-in logic cone and the fan-out logic cone into one gate circuit for generating a CNF clause, where the second specified threshold is less than the first specified threshold, and the two equivalent gate circuits are two gate circuits with the same input and the same output.
(143) It should be noted that, in embodiments of this disclosure, unit division is an example, and is merely logical function division. During actual implementation, another division manner may be used. Functional units in embodiments of this disclosure may be integrated into one processing unit, or each of the units may exist alone physically, or two or more units may be integrated into one unit. The integrated unit may be implemented in a form of hardware, or may be implemented in a form of a software functional unit.
(144) Based on the foregoing embodiments, an embodiment of this disclosure further provides a chip. The chip is connected to a memory, and the chip is configured to read and execute a software program stored in the memory, to implement the ATPG-based circuit verification method provided in the embodiment shown in
(145) Based on the foregoing embodiments, an embodiment of this disclosure provides a chip system. The chip system includes a processor, configured to support a computer apparatus in implementing the ATPG-based circuit verification method provided in the embodiment shown in
(146) Based on the foregoing embodiments, an embodiment of this disclosure further provides a computer program. When the computer program runs on a computer, the computer is enabled to perform the ATPG-based circuit verification method provided in the foregoing embodiments.
(147) Based on the foregoing embodiments, an embodiment of this disclosure further provides a computer-readable storage medium. The computer-readable storage medium stores a computer program. When the computer program is executed by a computer, the computer is enabled to perform the ATPG-based circuit verification method provided in the foregoing embodiments.
(148) A person skilled in the art should understand that embodiments of this disclosure may be provided as a method, a system, or a computer program product. Therefore, this application may use a form of a hardware-only embodiment, a software-only embodiment, or an embodiment with a combination of software and hardware. In addition, this disclosure may use a form of a computer program product that is implemented on one or more computer-usable storage media (including but not limited to a disk memory, a CD-ROM, an optical memory, and the like) that include computer-usable program code.
(149) This disclosure is described with reference to the flowcharts and/or block diagrams of the method, the device (system), and the computer program product according to this disclosure. It should be understood that computer program instructions may be used to implement each process and/or each block in the flowcharts and/or the block diagrams and a combination of a process and/or a block in the flowcharts and/or the block diagrams. The computer program instructions may be provided for a general-purpose computer, a dedicated computer, an embedded processor, or a processor of another programmable data processing device to generate a machine, so that the instructions executed by the computer or the processor of the another programmable data processing device generate an apparatus for implementing a specific function in one or more procedures in the flowcharts and/or in one or more blocks in the block diagrams.
(150) The computer program instructions may alternatively be stored in a computer-readable memory that can indicate a computer or another programmable data processing device to work in a specific manner, so that the instructions stored in the computer-readable memory generate an artifact that includes an instruction apparatus. The instruction apparatus implements a specific function in one or more procedures in the flowcharts and/or in one or more blocks in the block diagrams.
(151) The computer program instructions may alternatively be loaded onto a computer or another programmable data processing device, so that a series of operations and steps are performed on the computer or the another programmable device, so that computer-implemented processing is generated. Therefore, the instructions executed on the computer or the another programmable device provide steps for implementing a specific function in one or more procedures in the flowcharts and/or in one or more blocks in the block diagrams.
(152) It is clear that a person skilled in the art can make various modifications and variations to this disclosure without departing from the scope of this disclosure. This disclosure is intended to cover these modifications and variations of this disclosure provided that they fall within the scope of protection defined by the following claims and their equivalent technologies.