# US 2015/0178418 A1 · Model-based retiming with functional equivalence constraints

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

- Number: US 2015/0178418 A1
- Document ID: US20150178418A1
- Status: Published application
- Kind: A1
- Application number: 14/640,239
- Filed: 2015-03-06
- Published: 2015-06-25
- Earliest claimed: 2012-12-04
- Assignees: The MathWorks, Inc.
- Applicants: The MathWorks, Inc.
- Inventors: Yongfeng Gu; Girish Venkataramani
- Web page: https://patentgrep.com/patent/US20150178418A1

## CPC

- G06F 30/327: Logic synthesis; Behaviour synthesis, e.g. mapping logic, HDL to netlist, high-level language to RTL or netlist
- G06F 30/33: Design verification, e.g. functional simulation or model checking
- G06F 30/3323: using formal methods, e.g. equivalence checking or property checking
- G06F 30/398: Design verification or optimisation, e.g. using design rule check [DRC], layout versus schematics [LVS] or finite element methods [FEM] (optical proximity correction [OPC] design processes G03F1/36)
- G06F 2119/16: Equivalence checking
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A system and method tests for functional equivalence prior to automatically retiming a high-level specification. An Intermediate Representation (IR) includes one or more graphs or trees based on the high-level specification. A functional equivalence (FE) analyzer determines whether one or more components in the graph meet certain value and state conditions and thus is a candidate for retiming. A scheduler can use components that fail FE as a retiming boundary.

## Claims

### Claim 1

A method comprising:
building, on a computer, at least one intermediate representation (IR) including a specification for one or more components and a plurality of interconnections between the one or more components;
storing the at least one IR in a memory;
analyzing, on the computer, a first component of the at least one IR, the analyzing comprising
receiving a first input value;
determining a first condition of whether the first component produces an output value that is the same as the first input value; and
determining a second condition of whether the first component does not change internal state with the first input value;
when the first and second conditions are determined to exist, then
rearranging, on the computer, at least one of the plurality of interconnections or at least one of the one or more of the components in the at least one IR.

### Claim 2 (depends on 1)

The method of claim 1 wherein the rearranging further comprises:
retiming an execution order of the first component in the at least one IR.

### Claim 3 (depends on 2)

The method of claim 2 wherein the retiming comprises:
scheduling an execution order of the one or more components in the at least one IR, wherein each of the one or more components is scheduled to execute in a given stage of a pipeline where stage of the pipeline are defined by two or more registers in the at least one IR.

### Claim 4 (depends on 1)

The method of claim 1 additionally comprising:
analyzing, on the computer, a second component of the at least one IR, the second component being connected to the first component, the analyzing for
determining a third condition of whether the second component produces a second output value that is the same as a second input value; and
determining a fourth condition of whether the second component does not change internal state with the second input value; and
when the third and fourth conditions exist, then
rearranging, on the computer, the first and second component, or at least one connection between the first and second component or other components in the at least one IR.

### Claim 5 (depends on 1)

The method of claim 1 additionally comprising:
analyzing, on the computer, a second component of the at least one IR, the second component being connected to the first component, the analyzing for
determining a third condition of whether the second component produces a second output value that is the same as a second input value; and
determining a fourth condition of whether the second component does not change internal state with the second input value; and
when the third and fourth conditions do not exist, then
using the connection between the first and second component as a boundary for partitioning the at least one IR into a first partitioned portion that includes the first component that passes a retiming test and a second partitioned portion that includes the second component that fails a retiming test.

### Claim 6 (depends on 5)

The method of claim 5 additionally comprising:
analyzing, on the computer, a third component located in the first partitioned portion, the third component connected to the first component, and the analyzing comprising:
determining a fifth condition of whether the third component produces third output value that is the same as a third input value; and
determining a sixth condition of whether the third component does not change internal state with the third input value; and
when the fifth and sixth conditions exist,
rearranging, on the computer, the third component, or at least one connection between the third component and other components located in the first partitioned portion.

### Claim 7 (depends on 1)

The method of claim 1 additionally comprising:
generating Hardware Description Language (HDL) code or C code based on the at least one IR.

### Claim 8 (depends on 1)

The method of claim 1 further comprising:
receiving the at least one IR from a code generator.

### Claim 9 (depends on 1)

The method of claim 1 wherein the analyzing further comprises:
computing semantics of the first of the one or more components by executing a time based block model of the first of the one or more components, or by using a compiler technique.

### Claim 10

A method comprising:
building, on a computer, at least one intermediate representation (IR) including a specification for two or more components and a plurality of interconnections between the two or more components;
storing the at least one IR in a memory;
analyzing, on the computer, a first component and a second component of the at least one IR, the first and second components connected to one another, and the analyzing comprising
determining a first condition of whether the first component passes a to functional equivalence retiming test;
determining a second condition of whether the second component fails a functional equivalence retiming test;
when the first and second conditions are determined to exist, then
using the connection between the first and second component as a boundary for partitioning the at least one IR into a first partitioned portion that includes the first component that passes the functional equivalence retiming test and a second partitioned portion that includes the second component that fails the functional equivalence retiming test.

### Claim 11 (depends on 10)

The method of claim 10 additionally comprising:
rearranging, on the computer, at least one or more of the components in the first partitioned portion of the at least one IR.

### Claim 12 (depends on 10)

The method of claim 10 additionally comprising:
rearranging, on the computer, at least one or more of the components in the second partitioned portion of the at least one IR,

### Claim 13 (depends on 10)

The method of claim 10 wherein the functional equivalence retiming test for a selected one of the first component or the second component further comprises:
given an input value;
determining a first condition of whether the selected component produces an output value that is the same as the given input value; and
determining a second condition of whether the selected component does not change internal state with the given input value;

### Claim 14 (depends on 10)

The method of claim 10 wherein the functional equivalence retiming test for a selected one of the first or the second component further comprises:
determining whether the selected component
(a) has a predetermined initial state; or
(b) produces an expected output value given an input value, or
(c) produces no state change for a selected input value; and
if at least two of (a), (b) and (c) are determined to be true, then determining the selected component passes the functional equivalence test.

### Claim 15 (depends on 10)

The method of claim 10 wherein the functional equivalence retiming test for a selected one of the first component or the second component further comprises:
determining whether the selected component:
has a zero initial state value; and
produces a zero output value from a zero input value.

### Claim 16 (depends on 10)

The method of claim 10 additionally comprising:
retiming an execution order of the components within the first partitioned portion of the IR.

### Claim 17 (depends on 10)

The method of claim 10 additionally comprising:
retiming an execution order of the first partitioned portion independently from retiming an execution order of the second partitioned partition.

### Claim 18 (depends on 10)

The method of claim 10 additionally comprising:
receiving, on the computer, the IR from a code generator.

### Claim 19 (depends on 10)

The method of claim 10 further comprising, on the computer, using the IR to generate Hardware Description Language (HDL) code or C code.

### Claim 20 (depends on 10)

The method of claim 10 further comprising, on the computer,
determining semantics of the first and second component by executing a model of the component, or by using compiler techniques for constant propagation or conditional constant propagation.

### Claim 21

An apparatus comprising:
an intermediate representation (IR) receiver, for receiving an IR that comprises a functional model that includes a representation of at least two components and a plurality of interconnections between the components;
a memory, for storing the IR;
a processor, for executing program code for a functional equivalence analyzer, the program code for accessing the memory to read the IR and to determine if a first component in the functional model, given a first input value;
(a) produces a first output value that is the same as the first input value; and
(b) does not change internal state with the first input value; and
when (a) and (b) are determined to be true, then the program code further rearranging at least one of the plurality of interconnections or at least one of more of the components in the at least one IR.

### Claim 22 (depends on 21)

The apparatus of claim 21 wherein the program code further comprises:
an optimizer, for further retiming an execution order of the first component in the at least one IR.

### Claim 23 (depends on 22)

The apparatus of claim 22 wherein the optimizer is further for:
scheduling an execution order of the one or more components in the at least one IR, wherein each of the one or more components is scheduled to execute in a given stage of a pipeline where stage of the pipeline are defined by two or more registers in the at least one IR.

### Claim 24 (depends on 21)

The apparatus of claim 21 wherein the program code is further for:
analyzing a second component of the at least one IR, the second component being connected to the first component, the analyzing to determine whether the second component:
(c) produces a second output value that is the same as a second input value; and
(d) does not change internal state with the second input value; and
when (c) and (d) are true, then the program code further rearranging the first and second component, or at least one connection between the first and second component or connections with other components in the at least one IR.

### Claim 25 (depends on 21)

The apparatus of claim 21 wherein the program code is further for:
analyzing a second component of the at least one IR, the second component being connected to the first component, to determine if the second component:
(c) produces a second output value that is the same as a second input value; and
(d) does not change internal state with the second input value; and
when (c) and (d) are not both true, then the program code further using the connection between the first and second component as a boundary for partitioning the at least one IR into a first partitioned portion that includes the first component that passes a retiming test and a second partitioned portion that includes the second component that fails a retiming test.

### Claim 26 (depends on 25)

The apparatus of claim 25 wherein the program code is further for:
analyzing a third component located in the first partitioned portion, the third component connected to the first component, to determine if the third component:
(e) produces a third output value that is the same as a third input value; and
(f) does not change internal state with the third input value; and
when (e) and (f) are true, the program code then further rearranging the third component, or at least one connection between the third component and other components located in the first partitioned portion.

### Claim 27 (depends on 21)

The apparatus of claim 21 wherein the IR is further used by the processor for
generating Hardware Description Language (HDL) code or C code based on the at least one IR.

### Claim 28 (depends on 21)

The apparatus of claim 21 wherein the IR receiver further receives the at least one IR from a code generator.

### Claim 29 (depends on 21)

The apparatus of claim 21 wherein the program code is further for
computing semantics of the first of the one or more components by executing a time based block model of the first of the one or more components, or by using a compiler technique.

### Claim 30

An apparatus comprising:
an intermediate representation (IR) receiver, for receiving an IR that comprises a functional model that includes a representation of at least two components and a plurality of interconnections between the components;
a memory, for storing the IR;
a processor, for executing program code for a functional equivalence analyzer, the program code for accessing the memory to read the IR and to determine:
a first condition of whether a first component passes a functional equivalence retiming test;
a second condition of whether a second component fails a functional equivalence retiming test;
when the first and second conditions are determined to exist, using the connection between the first and second component as a boundary for partitioning the at least one IR into a first partitioned portion that includes the first component that passes the functional equivalence retiming test and a second partitioned portion that includes the second component that fails the functional equivalence retiming test.

### Claim 31 (depends on 30)

The apparatus of claim 30 wherein the program code is further for rearranging at least one or more of the components in the first partitioned portion of the at least one IR.

### Claim 32 (depends on 30)

The apparatus of claim 30 wherein the program code is further for rearranging at least one or more of the components in the second partitioned portion of the at least one IR.

### Claim 33 (depends on 30)

The apparatus of claim 30 wherein the functional equivalence retiming test for either the first component or the second component further comprises:
given an input value;
determining a first condition of whether the selected component produces an output value that is the same as the given input value; and
determining a second condition of whether the selected component does not change internal state with the given input value;

### Claim 34 (depends on 30)

The apparatus of claim 30 wherein the functional equivalence retiming test for either the first or the second component determines whether the component:
(a) has a predetermined initial state; or
(b) produces an expected output value given an input value, or
(c) produces no state change for a selected input value; and
if at least two of (a), (b) and (c) are determined to be true, then determines the selected component passes the functional equivalence test.

### Claim 35 (depends on 30)

The apparatus of claim 30 wherein the functional equivalence retiming test for a selected one of the first component or the second component further determines whether the selected component:
has a zero initial state value; and
produces a zero output value from a zero input value.

### Claim 36 (depends on 30)

The apparatus of claim 30 wherein the program code is further for retiming an execution order of the components within the first partitioned portion of the IR.

### Claim 37 (depends on 30)

The apparatus of claim 30 wherein the program code is further for retiming an execution order of the first partitioned portion independently from retiming an execution order of the second partitioned partition

### Claim 38 (depends on 30)

The apparatus of claim 30 wherein the program code is further for receiving the IR from a code generator.

### Claim 39 (depends on 30)

The apparatus of claim 30 wherein the program code is further for using the IR to generate Hardware Description Language (HDL) code or C code.

### Claim 40 (depends on 30)

The apparatus of claim 30 wherein the program code is further for determining semantics of the first and second component by executing a model of the component, or by using compiler techniques for constant propagation or conditional constant propagation.

### Claim 41

A non-transitory computer readable medium comprising instructions executable by a computer, the medium comprising:
instructions to build one or more intermediate representations (IRs) of a functional specification, at least one IR including a plurality components and a plurality of interconnections between the components;
instructions to store the at least one IR in a memory;
instructions to analyze the at least one IR to determine if at least one component therein:
(a) produces a first output value that is the same as a first input value; and
(b) does not change internal state with the first input value; and
instructions to rearrange at least one connection or the at least one component in the IR when (a) and (b) are true.

### Claim 42

A non-transitory computer readable medium comprising instructions executable by a computer, the medium comprising:
instructions to build one or more intermediate representations (IRs) of a functional specification, at least one IR including a plurality components and a plurality of interconnections between the components;
instructions to store the at least one IR in a memory;
instructions to analyze the at least one IR to determine if conditions for at least one component therein include:
(a) a first condition of whether a first component passes a functional equivalence retiming test;
(b) a second condition of whether a second component fails a functional equivalence retiming test; and
instructions to rearrange at least one connection or the at least one component in the IR, if conditions (a) and (b) are determined to exist for the component.
