# US 2006/0156260 A1 · Behavioral transformations for hardware synthesis and code optimization based on Taylor expansion diagrams

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

- Number: US 2006/0156260 A1
- Document ID: US20060156260A1
- Status: Published application
- Kind: A1
- Application number: 11/292,493
- Filed: 2005-12-02
- Published: 2006-07-13
- Earliest claimed: 2004-12-03
- Assignees: University of Massachusetts
- Inventors: Maciej Ciesielski; Serkan Askar; Emmanuel Boutillon; Jeremie Guillot
- Web page: https://patentgrep.com/patent/US20060156260A1

## CPC

- G06F 30/30: Circuit design
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A systematic method and system for behavioral transformations for hardware synthesis and code optimization in software compilation based on Taylor Expansion Diagrams. The system can be integrated with any suitable architectural synthesis system. It can also be built into a compiler tool for general purpose processor or into a specific target compiler. For hardware synthesis, an arithmetic expression of the computation is extracted from the behavioral-level HDL design or directly from its matrix representation, and represented in canonical data structure, called Taylor Expansion Diagram. In architectural synthesis, factorization, common sub-expression extraction and decomposition of the resulting Taylor Expansion Diagram is performed, producing an optimized data flow graph, from which the structural HDL design is obtained using standard architectural synthesis. For software compilation and code optimization, common sub-expression extraction and factorization serve as pre-compilation optimization tasks performed according to the target architecture to generate a new code for the compiler.

## Claims

### Claim 1

A method of transforming a behavioral-level specification into a data flow structure, said method comprising the steps of:
representing the behavioral-level specification in a canonical data structure;
performing a series of formal transformations on the canonical data structure by means of the decomposition of the canonical structure; and
integrating the transformations with an architectural synthesis flow.

### Claim 2 (depends on 1)

The method according to claim 1, wherein the step of performing a series of formal transformations on the canonical data structure includes the steps of using common sub-expression extraction and/or factorization to reduce the size of the canonical data structure and to enable the subsequent decomposition, and decomposition of the canonical data structure to produce data flow graphs.

### Claim 3 (depends on 1)

The method according to claim 1, wherein Taylor Expansion Diagrams are used as the canonical data structure.

### Claim 4

A method of transforming a behavioral specification of a behavioral-level hardware description languages (HDL) design into a data flow structure, said method comprising the steps of:
parsing the original behavioral-level HDL design;
extracting a data flow graph to produce an intermediate format; and
using the intermediate format obtained to create a TED data structure for computation;
performing common sub-expression extraction and/or factorization of the global Taylor Expansion Diagram to produce a hierarchical Taylor Expansion Diagram;
performing decomposition of the global Taylor Expansion Diagram; and
deriving optimized data flow graphs from the decomposition.

### Claim 5 (depends on 4)

The method according to claim 4, wherein the TED construction includes the steps of
constructing the arithmetic expression by extracting it from the initial specifications.;
parsing the resulting arithmetic expression to produce a parsing tree;
carrying out variable ordering to minimize the size of the TED;
for the selected variable order, performing a bottom-up TED construction; and
performing normalization of the TED graph.

### Claim 6 (depends on 5)

The method according to claim 5, and including performing decomposition of the resulting TED to transform the functional representation into a data flow graph following the construction of the TED.

### Claim 7

A method for behavioral transformation of a behavioral-level design and/or an analytical representation of the design for hardware synthesis and code optimization, said method comprising the steps of:
extracting an arithmetic expression of the computation from the behavioral-level design or directly from the analytical representation;
representing the arithmetic expression in a canonical data structure;
performing common sub-expression extraction and/or factorization of the canonical data structure to produce a hierarchical canonical data structure;
performing decomposition of the hierarchical canonical data structure;
deriving optimized data flow graphs from the decomposition; and
obtaining a structural hardware description language design from the data flow graphs using standard architectural synthesis.

### Claim 8 (depends on 7)

The method according to claim 7, wherein the optimized data flow graphs comprise a family of equivalent data flow graphs.

### Claim 9 (depends on 7)

The method according to claim 7, wherein the step of representing the arithmetic expression in a canonical data structure includes constructing a global Taylor Expansion Diagram representing the arithmetic expression.

### Claim 10 (depends on 9)

The method according to claim 9, wherein the step of performing sub-expression extraction and/or factorization includes the steps of identifying common sub-expressions contained in the Taylor Expansion Diagram; extracting common sub-expressions by substituting a new variable for each sub-expression that is identified, and moving the new variable towards the top of the Taylor Expansion Diagram, producing the hierarchal Taylor Expansion Diagram.

### Claim 11 (depends on 10)

The method according to claim 10, wherein the step of performing sub-expression extraction and/or factorization further includes the steps of identifying at least one bottom variable in the Taylor Expansion Diagram and moving the bottom variable towards the top of the Taylor Expansion Diagram after the common sub-expressions have been extracted in producing the hierarchal Taylor Expansion Diagram.

### Claim 12 (depends on 7)

The method according to claim 7, wherein the step of performing decomposition includes creating a plurality of subgraphs producing the hierarchal Taylor Expansion Diagram.

### Claim 13 (depends on 12)

The method according to claim 12, wherein the step of performing decomposition includes using cut-based decomposition to produce the plurality of subgraphs.

### Claim 14 (depends on 13)

The method according to claim 13, wherein the step of performing decomposition of the hierarchical Taylor Expansion Diagram includes using an objective function, such as area, latency, power, and precision, for guiding the decomposition process.

### Claim 15 (depends on 7)

The method according to claim 7, wherein the analytical representation of the design is in form of a matrix or mathematical expression, such as a polynomial expression.

### Claim 16

A method of factoring and decomposing an arithmetic expression, said method comprising the steps of:
representing the arithmetic expression in a canonical data structure;
performing common sub-expression extraction and/or factorization of the canonical data structure to produce a hierarchical canonical data structure;
performing decomposition of the hierarchical canonical data structure by decomposing subgraphs of the hierarchical canonical data structure; and
deriving optimized data flow graphs from the decomposition.

### Claim 17 (depends on 16)

The method according to claim 16, wherein the optimized data flow graphs comprise a family of equivalent data flow graphs.

### Claim 18 (depends on 16)

The method according to claim 16, wherein the step of representing the arithmetic expression in a canonical data structure includes constructing a global Taylor Expansion Diagram representing the arithmetic expression.

### Claim 19 (depends on 18)

The method according to claim 18, wherein the step of performing sub-expression extraction and/or factorization includes the steps of identifying common sub-expressions contained in the Taylor Expansion Diagram, extracting the common sub-expressions by substituting a new variable for each sub-expression that is identified, and moving the new variable towards the top of the Taylor Expansion Diagram, producing a hierarchical Taylor Expansion Diagram.

### Claim 20 (depends on 19)

The method according to claim 19, wherein the step of performing sub-expression extraction and/or factorization further includes the steps of identifying at least one bottom variable in the Taylor Expansion Diagram, and moving the bottom variable towards the top of the Taylor Expansion Diagram after the common sub-expressions have been extracted in producing the hierarchical Taylor Expansion Diagram.

### Claim 21 (depends on 205)

The method according to claim 205, wherein the step of performing decomposition includes creating a plurality of subgraphs producing the hierarchal Taylor Expansion Diagram.

### Claim 22 (depends on 20)

The method according to claim 20, wherein the step of performing decomposition includes using cut-based decomposition to create the plurality of subgraphs.

### Claim 23 (depends on 22)

The method according to claim 22, wherein decomposition is applied to each subgraph independently.

### Claim 24 (depends on 16)

The method according to claim 16, wherein decomposing the hierarchical canonical data structure includes using an objective function, such as area, latency, power, and precision, for guiding the decomposition process.

### Claim 25 (depends on 24)

The method according to claim 24, wherein the step of decomposing the canonical data structure into a data flow graph includes the steps of:
identifying useful cuts and admissible cut sequences;
selecting the best cut sequence for the given objective, including identifying the cuts and computing the cost of the cuts;
performing a decomposition of the canonical data structure for the selected cut sequence, forming a decomposed portion;
reordering the resulting sub-expressions using variable ordering directly on the canonical data structure;
repeating the procedure for each decomposed part until all cuts have been made; and
creating a corresponding data flow graph, uniquely defined by the sequence of cuts applied.

### Claim 26

A method of factoring and decomposing an arithmetic expression, said method comprising the steps of:
constructing a global Taylor Expansion Diagram representing the arithmetic expression;
performing common sub-expression extraction and/or factorization of the global Taylor Expansion Diagram to produce a hierarchical Taylor Expansion Diagram;
performing decomposition of the global Taylor Expansion Diagram; and
deriving optimized data flow graphs from the decomposition.

### Claim 27 (depends on 26)

The method according to claim 26, wherein the optimized data flow graphs comprise a family of equivalent data flow graphs.

### Claim 28 (depends on 26)

The method according to claim 26, wherein the step of performing sub-expression extraction and/or factorization includes the steps of identifying common sub-expressions contained in the Taylor Expansion Diagram; extracting the common sub-expressions by substituting a new variable for each sub-expression that is identified, producing a hierarchical Taylor Expansion Diagram.

### Claim 29 (depends on 28)

The method according to claim 28, wherein the order of the variables of the hierarchical Taylor Expansion Diagram thus obtained is changed to exhibit new potential factorization.

### Claim 30 (depends on 28)

The method according to claim 28, wherein the new variables thus created are moved towards the top of the Taylor Expansion Diagram.

### Claim 31 (depends on 27)

The method according to claim 27, wherein the step of performing sub-expression extraction and/or factorization further includes the steps of identifying at least one bottom variable in the Taylor Expansion Diagram, and moving the bottom variable towards the top of the Taylor Expansion Diagram after the common sub-expressions have been extracted in producing a hierarchical Taylor Expansion Diagram.

### Claim 32 (depends on 26)

The method according to claim 26, wherein the step of performing decomposition includes creating a plurality of subgraphs producing the hierarchal Taylor Expansion Diagram.

### Claim 33 (depends on 32)

The method according to claim 32, wherein the step of performing decomposition includes using cut-based decomposition to produce the plurality of subgraphs.

### Claim 34 (depends on 26)

The method according to claim 26, wherein the step of decomposing the hierarchical canonical data structure includes using an objective function, such as area, latency, power, and precision, for guiding the decomposition process.

### Claim 35

A method of decomposing a canonical representation of an arithmetic expression into a plurality of data flow graphs using a cut-based decomposition, said method comprising the steps of:
identifying useful cuts and admissible cut sequences;
selecting an objective function, such as area, latency, power, and precision, for guiding the decomposition process;
selecting the best cut sequence for the selected objective function, including identifying the cuts and computing the cost of the cuts;
performing a decomposition of the canonical data structure for the selected cut sequence;
reordering the resulting sub-expressions using variable ordering directly on canonical data structure;
repeating the procedure for each decomposed part until all cuts have been made; and
creating a corresponding data flow graph.
