Method and apparatus for verifying structural correctness in retimed circuits
View Patent ↗A method for designing a system on a target device includes performing register retiming on an original design for the system to generate a retimed design. Register retiming is performed on the retimed design. The retimed design is determined to be structurally correct in response to determining that the performing register retiming on the retimed design results in the original design.
1. A method for designing a system on a target device, the method comprising:
performing register retiming on an original design for the system to generate a retimed design;
performing register retiming on the retimed design; and
determining that the retimed design is structurally correct in response to determining that the performing register retiming on the retimed design results in the original design.
2. The method of claim 1 , wherein the performing register retiming on the retimed design comprises identifying how registers in the original design are repositioned to form the retimed design.
3. The method of claim 1 , wherein the performing register retiming on the retimed design comprises identifying state variables that model registers on each edge of a retiming graph for the original design and for the retimed design.
4. The method of claim 3 , wherein the performing register retiming on the retimed design comprises identifying random variables that model retiming labels representing a number and a direction of register movement relative to a node on a retiming graph for the retimed design.
5. The method of claim 4 , wherein the performing register retiming on the retimed design comprises identifying a retiming constraint for each edge on the retiming graph for the retimed design, wherein the retiming constraint reflects a relationship between the state variables and the random variables.
6. The method of claim 5 , further comprising determining that the retimed design is structurally correct in response to finding solutions for the random variables.
7. The method of claim 4 , wherein the performing register retiming on the retimed design comprises setting bounding constraints that restrict values for the random variables.
8. The method of claim 1 further comprising identifying a largest absolute value for random variables representing the retiming labels.
9. The method of claim 1 , wherein the target device is an application specific integrated circuit.
10. The method of claim 1 , wherein the target device is a field programmable gate array.
11. A non-transitory computer readable medium including a sequence of instructions stored thereon for causing a computer to execute a method for designing a system on a target device, comprising:
performing register retiming on an original design for the system to generate a retimed design;
performing register retiming on the retimed design back to the original circuit; and
determining that the retimed design is structurally correct in response to determining that the performing register retiming on the retimed design results in the original design.
12. The non-transitory computer readable medium of claim 11 , wherein the performing register retiming on the retimed design comprises identifying how registers in the original design are repositioned to form the retimed design.
13. The non-transitory computer readable medium of claim 11 , wherein the performing register retiming on the retimed design comprises identifying state variables that model registers on each edge of a retiming graph for the original design and for the retimed design.
14. The non-transitory computer readable medium of claim 13 , wherein the performing register retiming on the retimed design comprises identifying random variables that model retiming labels representing a number and a direction of register movement relative to a node on a retiming graph for the retimed design.
15. The non-transitory computer readable medium of claim 14 , wherein the performing register retiming on the retimed design comprises identifying a retiming constraint for each edge on the retiming graph for the retimed design, wherein the retiming constraint reflects a relationship between the state variables and the random variables.
16. The non-transitory computer readable medium of claim 11 wherein the method further comprises identifying to a designer that the retimed design failed structural verification.
17. A system designer, comprising:
a register retiming unit that performs register retiming on an original design for a system to generate a retimed design; and
a verification unit that verifies whether the retimed design is structurally correct by performing register retiming on the retimed design and determining that the retimed design is structurally correct in response to determining that the performing register retiming on the retimed design results in the original design, wherein at least one of the register retiming unit and the verification unit is implemented by a processor.
18. The system designer of claim 17 , wherein the verification unit identifies unchanged flip-flops, and verifies an initial state equivalence of the unchanged flip-flops between the original design and the retimed design.
19. The system designer of claim 17 , wherein the verification unit identifies changed flip-flops and sequential compare points, and verifies an initial state equivalence of the changed flip-flops between the original design and the retimed design, using a sequential bounded logic simulation.