# US 7,412,677 B1 · Detecting reducible registers

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 7,412,677 B1
- Document ID: US7412677B1
- Status: Granted
- Kind: B1
- Application number: 11/360,739
- Filed: 2006-02-22
- Granted: 2008-08-12
- Earliest claimed: 2006-02-22
- Assignees: Altera Corporation
- Inventors: Valavan Manohararajah; Gordon R. Chiu; Deshanand Singh; Stephen Brown
- Web page: https://patentgrep.com/patent/US7412677B1

## CPC

- G06F 30/327: Logic synthesis; Behaviour synthesis, e.g. mapping logic, HDL to netlist, high-level language to RTL or netlist
- G06F 30/3323: using formal methods, e.g. equivalence checking or property checking
- G06F 2119/12: Timing analysis or timing optimisation
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

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.

## Claims

### Claim 1

A method for optimizing a sequential circuit, the method comprising:
defining a set R1 having a first logic condition;
populating the set R1 with registers assumed to satisfy the first logic condition;
testing a plurality of registers in the set R1 for a violation of the first logic condition of the set R1;
removing, from the set R1, at least one register violating the first logic condition of the set R1; and
verifying whether the registers remaining in the set R1 satisfy the first logic condition.

### Claim 2 (depends on 1)

The method of claim 1, wherein the first logic condition is a stuck-at condition.

### Claim 3 (depends on 1)

The method of claim 1, further comprising:
defining a set R2 of registers having a second logic condition; and
placing the at least one register violating the first logic condition of the set R1 into the set R2.

### Claim 4 (depends on 3)

The method of claim 3, wherein the second logic condition is a duplicate condition.

### Claim 5 (depends on 3)

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 R1;
testing a plurality of registers in the set R2 for a violation of the second logic condition of the set R2; and
removing, from the set R2, at least one register violating the second logic condition of the set R2.

### Claim 6 (depends on 5)

The method of claim 5, further comprising:
removing the set R2 if the set R2 does not include any reducible registers.

### Claim 7 (depends on 5)

The method of claim 5, further comprising:
repeating testing a plurality of registers of the sets R1 and R2 for a predetermined number of iterations.

### Claim 8 (depends on 5)

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 R1 and R2 until a number of registers violating a logic condition of a set is less than a threshold value.

### Claim 9 (depends on 1)

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 R1;
determining a next state of the sequential circuit, wherein the next state includes second values for the plurality of registers of the set R1; and
comparing the next state to the current state to determine registers violating the first logic condition of set R1.

### Claim 10 (depends on 9)

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.

### Claim 11 (depends on 10)

The method of claim 10, wherein the simulating comprises randomly changing the input values and register values of registers not belonging to the set R1.

### Claim 12 (depends on 1)

The method of claim 1, wherein the verifying comprises using Boolean analysis.

### Claim 13 (depends on 12)

The method of claim 12, further comprising:
applying the first logic condition as a constraint on the Boolean analysis.

### Claim 14 (depends on 1)

The method of claim 1, further comprising:
removing a first register from the set R1 if the verifying determines that the first register does not satisfy the first logic condition.

### Claim 15 (depends on 14)

The method of claim 14, further comprising:
defining a set R2 of registers having a second logic condition; and
placing the first register that does not satisfy the first logic condition of the set R1 into the set R2.

### Claim 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 R1 having a first logic condition;
populating the set R1 with registers assumed to satisfy the first logic condition;
testing a plurality of registers in the set R1 for a violation of the first logic condition of the set R1;
removing, from the set R1, at least one register violating the first logic condition of the set R1; and
verifying whether the registers remaining in the set R1 satisfy the first logic condition.

### Claim 17 (depends on 16)

The information storage medium of claim 16, wherein the first logic condition is a stuck-at condition.

### Claim 18 (depends on 16)

The information storage medium of claim 16, further comprising:
defining a set R2 of registers having a second logic condition; and
placing the at least one register violating the first logic condition of the set R1 into the set R2.

### Claim 19 (depends on 18)

The information storage medium of claim 18, wherein the second logic condition is a duplicate condition.

### Claim 20 (depends on 18)

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 R1;
testing a plurality of registers in the set R2 for a violation of the second logic condition of the set R2; and
removing, from the set R2, at least one register violating the second logic condition of the set R2.

### Claim 21 (depends on 20)

The information storage medium of claim 20, further comprising:
removing the set R2 if the registers in the set R2 are not reducible.

### Claim 22 (depends on 20)

The information storage medium of claim 20, further comprising:
repeating testing a plurality of registers of the sets R1 and R2 for a predetermined number of iterations.

### Claim 23 (depends on 20)

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 R1 and R2 until a number of registers violating a logic condition of a set is less than a threshold value.

### Claim 24 (depends on 16)

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 R1;
determining a next state of the sequential circuit, wherein the next state includes second values for the plurality of registers of the set R1; and
comparing the next state to the current state to determine registers violating the first logic condition of set R1.

### Claim 25 (depends on 24)

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.

### Claim 26 (depends on 25)

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 R1.

### Claim 27 (depends on 16)

The information storage medium of claim 16, wherein the verifying comprises using Boolean analysis.

### Claim 28 (depends on 27)

The information storage medium of claim 27, further comprising:
applying the first logic condition as a constraint on the Boolean analysis.

### Claim 29 (depends on 16)

The information storage medium of claim 16, further comprising:
removing a first register from the set R1 if the verifying determines that the first register does not satisfy the first logic condition.

### Claim 30 (depends on 29)

The information storage medium of claim 29, further comprising:
defining a set R2 of registers having a second logic condition; and
placing the first register that does not satisfy the first logic condition of the set R1 into the set R2.