Detecting reducible registers
View Patent ↗Reducible registers are determined to optimize a sequential circuit. A screening method tests one or more sets of registers where the registers of each set are assumed to satisfy a logic condition. The tests determine if the logic condition holds. If the logic condition of a set is found to be violated, the registers may be moved to another set having a different logic condition or removed completely. The registers remaining are potentially reducible. The reducibility of the registers is verified via Boolean analysis by verifying the logic conditions of a register set for each register. If a register does not pass verification, it then may be moved to a different set having a different logic condition or removed completely. The sets that pass verification are reducible.
1. A method for optimizing a sequential circuit, the method comprising:
defining a set R 1 having a first logic condition;
populating the set R 1 with registers assumed to satisfy the first logic condition;
testing a plurality of registers in the set R 1 for a violation of the first logic condition of the set R 1 ;
removing, from the set R 1 , at least one register violating the first logic condition of the set R 1 ; and
verifying whether the registers remaining in the set R 1 satisfy the first logic condition.
2. The method of claim 1 , wherein the first logic condition is a stuck-at condition.
3. The method of claim 1 , further comprising:
defining a set R 2 of registers having a second logic condition; and
placing the at least one register violating the first logic condition of the set R 1 into the set R 2 .
4. The method of claim 3 , wherein the second logic condition is a duplicate condition.
5. The method of claim 3 , further comprising:
repeating testing and removing for at least a portion of the plurality of registers that remain in the set R 1 ;
testing a plurality of registers in the set R 2 for a violation of the second logic condition of the set R 2 ; and
removing, from the set R 2 , at least one register violating the second logic condition of the set R 2 .
6. The method of claim 5 , further comprising:
removing the set R 2 if the set R 2 does not include any reducible registers.
7. The method of claim 5 , further comprising:
repeating testing a plurality of registers of the sets R 1 and R 2 for a predetermined number of iterations.
8. The method of claim 5 , further comprising:
repeating testing a plurality of registers and removing of at least one register violating a logic condition of the sets R 1 and R 2 until a number of registers violating a logic condition of a set is less than a threshold value.
9. The method of claim 1 , wherein the testing comprises:
determining a current state of the sequential circuit, wherein the state includes values for a plurality of registers of the set R 1 ;
determining a next state of the sequential circuit, wherein the next state includes second values for the plurality of registers of the set R 1 ; and
comparing the next state to the current state to determine registers violating the first logic condition of set R 1 .
10. The method of claim 9 , wherein the determining a next state comprises:
simulating the sequential circuit using register values of the current state and input values.
11. The method of claim 10 , wherein the simulating comprises randomly changing the input values and register values of registers not belonging to the set R 1 .
12. The method of claim 1 , wherein the verifying comprises using Boolean analysis.
13. The method of claim 12 , further comprising:
applying the first logic condition as a constraint on the Boolean analysis.
14. The method of claim 1 , further comprising:
removing a first register from the set R 1 if the verifying determines that the first register does not satisfy the first logic condition.
15. The method of claim 14 , further comprising:
defining a set R 2 of registers having a second logic condition; and
placing the first register that does not satisfy the first logic condition of the set R 1 into the set R 2 .
16. An information storage medium comprising a plurality of instructions adapted to direct an information processing device to perform an operation comprising:
defining a set R 1 having a first logic condition;
populating the set R 1 with registers assumed to satisfy the first logic condition;
testing a plurality of registers in the set R 1 for a violation of the first logic condition of the set R 1 ;
removing, from the set R 1 , at least one register violating the first logic condition of the set R 1 ; and
verifying whether the registers remaining in the set R 1 satisfy the first logic condition.
17. The information storage medium of claim 16 , wherein the first logic condition is a stuck-at condition.
18. The information storage medium of claim 16 , further comprising:
defining a set R 2 of registers having a second logic condition; and
placing the at least one register violating the first logic condition of the set R 1 into the set R 2 .
19. The information storage medium of claim 18 , wherein the second logic condition is a duplicate condition.
20. The information storage medium of claim 18 , further comprising:
repeating testing and removing for at least a portion of the plurality of registers that remain in the set R 1 ;
testing a plurality of registers in the set R 2 for a violation of the second logic condition of the set R 2 ; and
removing, from the set R 2 , at least one register violating the second logic condition of the set R 2 .
21. The information storage medium of claim 20 , further comprising:
removing the set R 2 if the registers in the set R 2 are not reducible.
22. The information storage medium of claim 20 , further comprising:
repeating testing a plurality of registers of the sets R 1 and R 2 for a predetermined number of iterations.
23. The information storage medium of claim 20 , further comprising:
repeating testing a plurality of registers and removing of at least one register violating a logic condition of the sets R 1 and R 2 until a number of registers violating a logic condition of a set is less than a threshold value.
24. The information storage medium of claim 16 , wherein the testing comprises:
determining a current state of the sequential circuit, wherein the state includes values for a plurality of registers of the set R 1 ;
determining a next state of the sequential circuit, wherein the next state includes second values for the plurality of registers of the set R 1 ; and
comparing the next state to the current state to determine registers violating the first logic condition of set R 1 .
25. The information storage medium of claim 24 , wherein the determining a next state comprises:
simulating the sequential circuit using register values of the current state and input values.
26. The information storage medium of claim 25 , wherein the simulating comprises randomly changing the input values and register values of registers not belonging to the set R 1 .
27. The information storage medium of claim 16 , wherein the verifying comprises using Boolean analysis.
28. The information storage medium of claim 27 , further comprising:
applying the first logic condition as a constraint on the Boolean analysis.
29. The information storage medium of claim 16 , further comprising:
removing a first register from the set R 1 if the verifying determines that the first register does not satisfy the first logic condition.
30. The information storage medium of claim 29 , further comprising:
defining a set R 2 of registers having a second logic condition; and
placing the first register that does not satisfy the first logic condition of the set R 1 into the set R 2 .