Programmatically generated reduced fault injections for functional safety circuits
Techniques are disclosed for eliminating redundancy in fault simulations to improve efficiency and to reduce the time and computing power required to generate a robust fault list, which results in adequate diagnostic coverage of a particular post-silicon electronic device for functional safety applications. The techniques described herein implement an automated methodology to identify identical sub-circuits in a design after the design is synthesized to gates, and utilize isomorphism to define a manner in which identical blocks may be reliably identified to ensure adequate coverage and accurate, consistent fault injection results. The netlist may advantageously implement a “flat” as opposed to a hierarchal design. Moreover, multiple levels of granularity may be identified for the various sub-circuits associated with the reference graphs used to identify isomorphic sub-graphs.
1 . A device, comprising:
a communication interface configured to receive a graph dataset corresponding to a graph representation of a netlist of a circuit design for which fault injection simulation is to be performed in accordance with an initial fault list, the graph representation including a set of sub-graphs associated with respective sub-circuits of the circuit design; and
processor circuitry configured to:
calculate, from the graph dataset, a set of reference sub-graphs that are candidates for being isomorphic with other sub-graphs in the netlist;
partition the netlist into a decomposed netlist by selecting a subset of the set of sub-graphs having a size that matches one or more of the reference sub-graphs;
identify, as one or more isomorphic sub-graphs, one or more sub-graphs within the decomposed netlist that are isomorphic with one or more of the reference sub-graphs;
identify a location of each of the isomorphic sub-graphs in the netlist; and
remove the identified location of all but one of the isomorphic sub-graphs in the netlist from the initial fault list to generate a reduced fault list.
2 . The device of claim 1 , wherein the processor circuitry is configured to:
calculate the set of reference sub-graphs by computing and storing, in a memory associated with the device, node eccentricities associated with a first sub-graph and a second sub-graph, from among the sub-graphs, in a first and a second array, respectively; and
identify the first sub-graph and the second sub-graph as candidates for being isomorphic and thus belonging to the set of reference sub-graphs when an eccentricity of the first array and an eccentricity of the second array match one another.
3 . The device of claim 2 , wherein the processor circuitry is configured to identify (i) the location of one or more sub-graphs in the decomposed netlist that are isomorphic to one of the set of reference sub-graphs by executing a pattern matching process that utilizes, as a pattern matching parameter, a predetermined number of nodes from a start element of the first array and the second array, respectively, and (ii) a location of recurring sub-circuits in the circuit design using matching strings computed as a result of the pattern matching process.
4 . The device of claim 1 , wherein the processor circuitry is configured to partition the netlist into the decomposed netlist by randomly selecting the subset of the set of sub-graphs having a size that matches one or more of the reference sub-graphs.
5 . The device of claim 1 , wherein the processor circuitry is configured to partition the netlist into the decomposed netlist such that a center of nodes of the subset of the set of sub-graphs are a same distance from a center of the graph representation.
6 . The device of claim 1 , wherein the netlist has a flat design in which only primitives are instanced.
7 . The device of claim 1 , wherein a portion of the sub-circuits that are associated with the reference sub-graphs have a different netlist granularity.
8 . A device, comprising:
a memory configured to store computer-readable instructions; and
processor circuitry configured to execute the computer-readable instructions stored in the memory to:
receive a graph dataset corresponding to a graph representation of a netlist of a circuit design for which fault injection simulation is to be performed in accordance with an initial fault list, the graph representation including a set of sub-graphs associated with respective sub-circuits of the circuit design;
calculate, from the graph dataset, a set of reference sub-graphs that are candidates for being isomorphic with other sub-graphs in the netlist;
partition the netlist into a decomposed netlist by selecting a subset of the set of sub-graphs having a size that matches one or more of the reference sub-graphs;
identify, as one or more isomorphic sub-graphs, one or more sub-graphs within the decomposed netlist that are isomorphic with one or more of the reference sub-graphs;
identify a location of each of the isomorphic sub-graphs in the netlist; and
remove the identified location of all but one of the isomorphic sub-graphs in the netlist from the initial fault list to generate a reduced fault list.
9 . The device of claim 8 , wherein the processor circuitry is configured to:
calculate the set of reference sub-graphs by computing and storing, in the memory, node eccentricities associated with a first sub-graph and a second sub-graph, from among the sub-graphs, in a first and a second array, respectively; and
identify the first sub-graph and the second sub-graph as candidates for being isomorphic and thus belonging to the set of reference sub-graphs when an eccentricity of the first array and an eccentricity of the second array match one another.
10 . The device of claim 9 , wherein the processor circuitry is configured to identify (i) the location of one or more sub-graphs in the decomposed netlist that are isomorphic to one of the set of reference sub-graphs by executing a pattern matching process that utilizes, as a pattern matching parameter, a predetermined number of nodes from a start element of the first array and the second array, respectively, and (ii) a location of recurring sub-circuits in the circuit design using matching strings computed as a result of the pattern matching process.
11 . The device of claim 8 , wherein the processor circuitry is configured to partition the netlist into the decomposed netlist by randomly selecting the subset of the set of sub-graphs having a size that matches one or more of the reference sub-graphs.
12 . The device of claim 8 , wherein the processor circuitry is configured to partition the netlist into the decomposed netlist such that a center of nodes of the subset of the set of sub-graphs are a same distance from a center of the graph representation.
13 . The device of claim 8 , wherein the netlist has a flat design in which only primitives are instanced.
14 . The device of claim 8 , wherein a portion of the sub-circuits that are associated with the reference sub-graphs have a different netlist granularity.
15 . A non-transitory computer readable medium having instructions stored thereon that, when executed by processor circuitry, cause the processor circuitry to:
receive a graph dataset corresponding to a graph representation of a netlist of a circuit design for which fault injection simulation is to be performed in accordance with an initial fault list, the graph representation including a set of sub-graphs associated with respective sub-circuits of the circuit design;
calculate, from the graph dataset, a set of reference sub-graphs that are candidates for being isomorphic with other sub-graphs in the netlist;
partition the netlist into a decomposed netlist by selecting a subset of the set of sub-graphs having a size that matches one or more of the reference sub-graphs;
identify, as one or more isomorphic sub-graphs, one or more sub-graphs within the decomposed netlist that are isomorphic with one or more of the reference sub-graphs;
identify a location of each of the isomorphic sub-graphs in the netlist; and
remove the identified location of all but one of the isomorphic sub-graphs in the netlist from the initial fault list to generate a reduced fault list.
16 . The non-transitory computer readable medium of claim 15 , further including instructions that, when executed by the processor circuitry, cause the processor circuitry to:
calculate the set of reference sub-graphs by computing node eccentricities associated with a first sub-graph and a second sub-graph, from among the sub-graphs, in a first array and a second array, respectively; and
identify the first sub-graph and the second sub-graph as candidates for being isomorphic and thus belonging to the set of reference sub-graphs when an eccentricity of the first array and an eccentricity of the second array match one another.
17 . The non-transitory computer readable medium of claim 16 , further including instructions that, when executed by the processor circuitry, cause the processor circuitry to identify (i) the location of one or more sub-graphs in the decomposed netlist that are isomorphic to one of the set of reference sub-graphs by executing a pattern matching process that utilizes, as a pattern matching parameter, a predetermined number of nodes from a start element of the first array and the second array, respectively, and (ii) a location of recurring sub-circuits in the circuit design using matching strings computed as a result of the pattern matching process.
18 . The non-transitory computer readable medium of claim 15 , further including instructions that, when executed by the processor circuitry, cause the processor circuitry to partition the netlist into the decomposed netlist by randomly selecting the subset of the set of sub-graphs having a size that matches one or more of the reference sub-graphs.
19 . The non-transitory computer readable medium of claim 15 , further including instructions that, when executed by the processor circuitry, cause the processor circuitry to partition the netlist into the decomposed netlist such that a center of nodes of the subset of the set of sub-graphs are a same distance from a center of the graph representation.
20 . The non-transitory computer readable medium of claim 15 , wherein the netlist has a flat design in which only primitives are instanced.
21 . The non-transitory computer readable medium of claim 15 , wherein a portion of the sub-circuits that are associated with the reference sub-graphs have a different netlist granularity.