Hardware simulation systems and methods for identifying state-holding loops and oscillating loops
A circuit hardware emulation module is configured to identify oscillating subgraphs of an emulated graph, or to identify state-holding subgraphs of an emulated graph. The emulation module identifies one or more loops within an emulated circuit; generates an acyclic emulation of at least a portion of the emulated circuit, wherein the acyclic emulation is characterized by one or more loop breakers; generates a loop detector emulation of a hardware-based loop detector circuit based at least in part on a quantity of loop breakers n characterizing the acyclic emulation, wherein the loop detector emulation comprises at least one of an oscillation detector or a state-holding detector; and executes the loop detector emulation for a plurality of input values for the emulated circuit to generate an output indicating at least one of an oscillation status or a state-holding status of the emulated circuit.
1. A hardware emulation system comprising at least one processor and at least one memory storing instructions that cause the system to:
receive a netlist of a circuit;
transform said netlist of the circuit to a directed graph:
identify one or more loops within the directed graph by identifying one or more strongly connected components (SCC) in the directed graph, wherein each of the one or more SCC comprises a plurality of vertices and a plurality of edges connecting the plurality of vertices;
replace n edges of the SCC with n loop breakers, wherein n is greater than 0;
apply constant values of 1s and 0s to the n loop breakers to generate 2 n netlists; and
perform a hardware emulation based on the 2 n netlists to detect one or more of an oscillation status and a state holding status using an oscillation detector and a state-holding detector.
2. The hardware emulation system of claim 1 , wherein the hardware emulation system detects oscillation in accordance with the following expression:
OSC
(
Y
)
=
~
∑
Sϵ
B
n
(
∏
k
=
1
n
δ
(
S
[
k
]
,
g
k
S
(
Y
)
)
)
.
wherein Y is a vector of Boolean variables, wherein “˜” represents a negation operation,
wherein B n represents a Boolean function having n variables, wherein δ is defined as:
wherein x is an element of Boolean set {0,1} and f is a Boolean function, wherein S is an element of B n , wherein g S (Y) represents the Boolean function from Y to B, and wherein k is an index varying from 1 to n, and wherein the S[k] represents the kth Boolean value of the n-tuple S belonging to B n .
3. The hardware emulation system of claim 1 , wherein the hardware emulation system detects state holding in accordance with the following expression:
STH
(
Y
)
=
∑
S
0
,
S
1
ϵ
B
n
S
0
<
S
1
(
∏
k
=
1
n
δ
(
S
0
[
k
]
,
g
k
S
0
(
Y
)
)
*
∏
k
=
1
n
δ
(
S
1
[
k
]
,
g
k
S
1
(
Y
)
)
)
.
wherein Y is a vector of Boolean variables, wherein “˜” represents a negation operation,
wherein B n represents a Boolean function having n variables, wherein δ is defined as:
wherein x is an element of Boolean set { 0 , 1 } and f is a Boolean function, wherein S 0 and S 1 are elements of B n , wherein S 0 is smaller than S 1 , wherein g S (Y) represents the Boolean function from Y to B, wherein k is an index varying from 1 to n, wherein S 0 [k] represent the kth Boolean value of the n-tuple S 0 belonging to B n , wherein S 1 [k] represent the kth Boolean value of the n-tuple S 1 belonging to B n , and wherein * represents a multiplication operation.
4. A method for circuit loop detection via circuit emulation, the method comprising:
receiving a netlist of a circuit;
transforming said netlist to a directed graph;
identify one or more loops within the directed graph by identifying one or more strongly connected components (SCC) in the directed graph, wherein each of the one or more SCC comprises a plurality of vertices and a plurality of edges connecting the plurality of vertices;
replacing n edges of the SCC with n loop breakers, wherein n is greater than 0;
applying constant values of 1s and 0s to the n loop breakers to generate 2 n netlists; and
performing a hardware emulation based on the 2 n netlists to detect one or more of an oscillation status and a state holding status using an oscillation detector and a state-holding detector.
5. The method of claim 4 , wherein the oscillation detection is performed in in accordance with the following expression:
OSC
(
Y
)
=
~
∑
Sϵ
B
n
(
∏
k
=
1
n
δ
(
S
[
k
]
,
g
k
S
(
Y
)
)
)
wherein Y is a vector of Boolean variables, wherein “˜” represents a negation operation,
wherein B n represents a Boolean function having n variables, wherein δ is defined as:
wherein x is an element of Boolean set {0,1} and f is a Boolean function, wherein S is an element of B n , wherein g S (Y) represents the Boolean function from Y to B, and wherein k is an index varying from 1 to n, and wherein the S[k] represents the kth Boolean value of the n-tuple S belonging to B n .
6. The method of claim 4 , wherein the state holding detection is performed in in accordance with the following expression:
STH
(
Y
)
=
∑
S
0
,
S
1
ϵ
B
n
S
0
<
S
1
(
∏
k
=
1
n
δ
(
S
0
[
k
]
,
g
k
S
0
(
Y
)
)
*
∏
k
=
1
n
δ
(
S
1
[
k
]
,
g
k
S
1
(
Y
)
)
)
wherein Y is a vector of Boolean variables, wherein “˜” represents a negation operation,
wherein B n represents a Boolean function having n variables, wherein δ is defined as:
Wherein x is an element of Boolean set {0,1} and f is a Boolean function, wherein S is an element of B n , wherein g S (Y) represents the Boolean function from Y to B, and wherein k is an index varying from 1 to n, and wherein the S[k] represents the kth Boolean value of the n-tuple S belonging to B n .
7. A non-transitory computer-readable storage medium comprising executable instructions configured to, when executed by a processor, cause the processor to:
receive a netlist of a circuit:
transform the netlist to a directed graph:
identify one or more loops within the directed graph by identifying one or more strongly connected components (SCC) in the directed graph, wherein each of the one or more SCC comprises a plurality of vertices and a plurality of edges connecting the plurality of vertices;
replace n edges of the SCC with n loop breakers, wherein n is greater than 0;
apply constant values of 1s and 0s to the n loop breakers to generate 2 n netlists; and
perform a hardware emulation based on the 2 n netlists to detect one or more of an oscillation status and a state holding status using an oscillation detector and a state-holding detector.
8. The non-transitory computer readable medium of claim 7 , wherein the oscillation is detected in accordance with the following expression:
OSC
(
Y
)
=
~
∑
Sϵ
B
n
(
∏
k
=
1
n
δ
(
S
[
k
]
,
g
k
S
(
Y
)
)
)
wherein Y is a vector of Boolean variables, wherein “˜” represents a negation operation, wherein B n represents a Boolean function having n variables, wherein δ is defined as:
wherein x is an element of Boolean set {0,1} and f is a Boolean function, wherein S is an element of B n , wherein g S (Y) represents the Boolean function from Y to B, and wherein k is an index varying from 1 to n, and wherein the S[k] represents the kth Boolean value of the n-tuple S belonging to B n .
9. The non-transitory computer readable medium of claim 7 , wherein the state holding is detected in accordance with the following expression:
STH
(
Y
)
=
∑
S
0
,
S
1
ϵ
B
n
S
0
<
S
1
(
∏
k
=
1
n
δ
(
S
0
[
k
]
,
g
k
S
0
(
Y
)
)
*
∏
k
=
1
n
δ
(
S
1
[
k
]
,
g
k
S
1
(
Y
)
)
)
wherein Y is a vector of Boolean variables, wherein “˜” represents a negation operation, wherein B n represents a Boolean function having n variables, wherein δ is defined as:
wherein x is an element of Boolean set { 0 , 1 } and f is a Boolean function, wherein S is an element of B n , wherein g S (Y) represents the Boolean function from Y to B, and wherein k is an index varying from 1 to n, and wherein the S[k] represents the kth Boolean value of the n-tuple S belonging to B n .