VLSI CAD Lab

The design, initially specified in C or behavioral HDL, is translated into a hybrid network composed of islands of functional blocks, represented using canonical, graph-based data structure called Taylor Expansion Diagram (TED), and structural operators. TEDs are constructed from polynomial expressions describing functionality of the arithmetic components of the design. They are then transformed into a structural data flow graph (DFG) representation through a series of functional decomposition steps, including TED linearization, factorization, common subexpression elimination (CSE), and TED decomposition. An important feature of TED decomposition is that it minimizes the number of arithmetic operations, and in particular multiplications, hence contributing to area minimization. The DFG obtained as a result of TED decomposition is then combined with the remaining structural operators, and the entire network (global DFG) is further restructured to minimize the design latency, subject to the imposed resource constraints.

The overall TDS system flow [1] is shown in the figure below. The left part of the figure shows traditional high-level synthesis flow (using high-level synthesis tool GAUT), which extracts a control data flow (CDFG) from the initial specification. The flow on the right is the TDS system, which transforms the initial CDFG into an optimized DFG, which is then passed back to GAUT for high-level synthesis.

 

 

TED decomposition is based on identifying common subexpressions and replacing them by new variables (e.g., S1 = c+d, S2 = a+b, see figure below). Then, a cut-based decomposition is performed by identifying split edges, which decompose the graph disjunctively and introduce ADD operations; and cut nodes (dominators), which decompose the graph conjunctively and introduce MULT operations. The result is a Normal Factored Form (NFF), which is unique for a TED with fixed variable order. Different variable orderings will result in different factored forms and hence different DFGs.In the example below, for the variable order a,b,c,d the NFF is 0 = (a+b)(c+d)+d

Once a TED is decomposed into a Normal Factored Form (NFF), a structural representation (DFG) is generated for that form by replacing additions by ADD operations and multiplications by MULT operations. Unlike NFF, a DFG is not unique, and a number of restructuring algorithms can be applied to minimize the expected latency, considering design constraints imposed on hardware resources.

 

In addition to minimizing the number of multiplications during TED decomposition, the system replaces constant multiplications by shift operations, as illustrated in the figure below, for function F=7a+6b. First, constants coefficients are represented in canonical sign digit (CSD) form, and constant 2 is replaced by variable L (left shift). The modified TED is then decomposed by factoring out L, resulting in the DFG shown in the right part of the figure.

 

The diagram below, part(a) shows an initial DFG network for a simple design that involves arithmetic operators that can be written as functional expressions and represented as TEDs, and a structural element (gtmux, shown in gray), considered as a black box. In the diagram below, part(b) shows the restructured DFG, with the number of multipliers + adders reduced from 17+9 to 3+4, and the latency reduced from 9 to 4. This DFG is then used as input to high-level synthesis to produce designs with smaller hardware area or smaller latency than from the original DFG derived directly from the initial design specification.