Behavioral transformations for hardware synthesis and code optimization based on Taylor expansion diagrams

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.

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.

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.

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.

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.