1、Energy Efficient Hardware Synthesis of Polynomial Expressions 18th International Conference on VLSI Design,Anup Hosangadi Ryan Kastner ECE Department, UCSB,Farzan Fallah Advanced CAD Research Fujitsu Labs of America,Outline,Introduction Related Work Problem formulation Algorithms for optimizing poly
2、nomials Experimental results Conclusions,Introduction,Embedded system applications need to compute polynomial expressions Continuous functions can be approximated by Taylor Series Adaptive (polynomial) filters Polynomial interpolation/extrapolationin Computer Graphics Encrpytion,Introduction,Commonl
3、y occuring computations implemented in hardware More flexibility than processor architecture NPAs (Hardware accelarators) in PICO project Custom Instructions (Tensilica) Upto 100 times improvement over processor implementation (Kastner et.al TODAES02) Develop techniques for reducing power consumptio
4、n,Related Work (Behavioral transforms),Power consumption depends on many factors Reducing number of operations Hardware: (Nguyen and Chatterjee TVLSI00) Software: (I.Hong et.al TODAES99)Voltage reduction after speedup transformations Retiming, Pipelining, Algebraic restructuring(Chandrakasan et. al
5、TCAD95),Related Work,Scheduling and resource allocation Shutting down unused resources (Monteiro et. al. DAC 96) Allocation of registers, functional units and interconnects (A.Raghunathan et. al ICCD94) Multiple Vdd scheduling Assigning supply voltage to each operation in CDFG (M.Chang and M.Pedram
6、TVLSI97),Related Work,Switching power is proportional to number of operationsMultiplications are expensive in Embedded systems Average 40 times more power than addition at 5V (V.Krishna et. al, VLSI Design 1999) Careful optimization of expressions is therefore necessary to save power,Reducing operat
7、ions in polynomial expressions,No good tool for polynomials Designers rely on hand optimized librariesConventional compiler techniques: CSE and Value numbering not suited for polynomials.Horner form: most popular representation anxn + a1xn-1 + .an-1x + a0 = (anx + an-1)x + an-2)x + a1)x + a0 Not goo
8、d for multivariate polynomials Only a single polynomial expression at a time,Comparison with Horner form,Quartic-spline polynomial (3-D graphics) P = zu4 + 4avu3 + 6bu2v2 + 4uv3w + qv4 Horner form (from MapleTM) P = zu4 + (4au3 + (6bu2 + (4uw + qv)v)v)v(17 multiplications) Proposed algebraic method:
9、d1 = v2 ; d2 = d1*vP = u3(uz + ad2) + d1( qd1 + u(wd2 + 6bu) ) (11 multiplications),Related Work (Polynomial Expressions,Expression Factorization (M.A. Breuer JACM69) Allows only one kind of operator at a timeUsing Symbolic Algebra (M.A.Peymandoust, De Micheli) Mapping polynomial datapaths to librar
10、ies (DAC01) Low power embedded software (DATE02) Results depend heavily on set of library elementseg. (a2 b2) = (a+b)(a-b) iff (a+b) or (a-b) is a library element Manipulates only a single expression at a time,F1 = A + B + C + D; F2 = A + P + D;,= Extract (A + D),Motivating Example,Consider set of e
11、xpressionsUsing CSE,16 multiplications and 4 additions/subtractions,12 multiplications and 4 additions/subtractions,Motivational Example,Using Horner transformUsing our algebraic technique,12 multiplications and 4 additions/subtractions,7 multiplications and 3 additions/subtractions,Introduction to
12、algebraic technique for redundancy elimination,Algebraic techniques in multi-level logic synthesis (MLLS) Decomposition, factoring reduce number of literalsDistill and Condense use Rectangle Covering methodsPolynomial Expressions (Our Technique) Factoring, Single term common subexpressions reduces n
13、umber of multiplications Multiple term common subexpressions reduces number of additions and possibly multiplicationsKey Differences (Generalization to handle higher orders) Kernelling techniques Finding single cube intersections,Introduction to our technique (Outline),Find a subset of all possible
14、subexpressions (kernel generation)Transformation of Polynomial Expressions Problem formulationExtract multiple term common subexpressions and factorsExtract single term common factors,Introduction to our technique,Terminology Literal: A variable or a constant eg. a,b,2,3.14 Cube: Product of literals
15、 e.g. +3a2b, -2a3b2c SOP: Sum of cubes e.g. +3a2b 2a3b2c Cube-free expression: No literal or cube can divide all the cubes of the expression Kernel: A cube free sub-expression of an expression, e.g. 3 2abc Co-Kernel: A cube that is used to divide an expression to get a kernel, e.g. a2b,Introduction
16、to our Technique,Matrix Representation of Polynomial ExpressionsF = x3y xy2z is represented byEach row represents a product term Each column represents a variable/constant Each element (i,j) represents power of variable j in term i,Generation of Kernels (example),P1 = x3y + x2y2z L = x,y,zDivide by
17、x: Ft = P1/x = x2y + xy2z,Generation of Kernels (example),Ft = P1/x = x2y + xy2zC = Biggest Cube dividing all cubes of Ft,1 1 0,/ C =,C =,= xy,Generation of Kernels (example),Obtain Kernel:F1 = Ft/C = (x2y + xy2z)/(xy) = ( x + yz) Obtain Co-Kernel D1 = x*(xy) = x2y No kernels within F1. Go back to P
18、1 P1 = x3y + x2y2z Divide now by next variable yFt = x3 + x2yz C = x2 But (x y) CStop Here, to avoid repeating same kernel Ft/C = (x + yz) No more kernels extracted Record kernel F1 = P1 with co-kernel 1,Concept of kernels and co-kernels,Theorem: Two expressions f and g can have a multiple term comm
19、on subexpression iff there are 2 kernels Kf and Kg having a multiple term intersectionDetection of multiple term common subexpressions by intersection of sets of kernelsEach co-kernel : kernel pair represents a possible factorizatione.g. x3y + x2y2z = x2y(x + yz)Set of kernels a subset of all possib
20、le subexpressions,All Kernels and Co Kernels,Which kernels to choose?,Kernel Cube Matrix (KCM),One row for each Kernel generated One column for each distinct kernel cube Each non-zero element represents a term,x3y,Finding Kernel Intersections (Distill Algorithm),Each kernel intersection or factor ap
21、pears as a rectangle Rectangle: Set of rows and columns such that all elements are 1 Value of a rectangle = Weighted sum of the energy savings of the different operations Goal: Maximum valued rectangular covering of KCM Greedy heuristic: covering by prime rectangles,Modeling value function of a rect
22、angle,Formula for weighted sum of energy savings on selection of a rectangleR = # of rows ; C = # of columnsM(Ri) = # of multiplications in row (co-kernel) i.M(Ci) = # of multiplications in column (kernel-cube) im = ratio of average energy consumption of multiplication to addition in the target libr
23、ary,Value =,Distill Algorithm,Distill Algorithm,Remove covered terms,4xy x2y = xyd2 d2 = 4 x Saves 2 multiplications Value = 80,Distill Algorithm,Distill algorithm exits after no more kernel intersections can be found,P1 = x2yd1 d1 = x + yz P2 = 4d1 xyz d2 = 4 - x P3 = xyd2,Can further optimize by f
24、inding single cube intersections,Finding single cube intersections (Condense algorithm),Form Cube Literal Matrix (CLM) One row for each cube One column for each literal Eg. 2 cubes F1 = a4b3c; and F2 = a2b4c2,Finding single cube intersections (Condense algorithm),Each (single term) common subexpress
25、ion appears as a rectangle. Rectangle: Set of rows and columns where all elements are non-zeroValue of a rectangle is number of multiplications saved by selecting it C = cube corresponding to the rectangleValue = Rows*( (Ci ) -1) Maximum valued rectangular covering will give minimum number of multip
26、licationsUse greedy iterative covering by prime rectangles,Cube Literal Matrix (Condense Algorithm),Save 2 multiplications by extracting xy,CLM for our example after Distill algorithm,C = xy,Condense Algorithm,Extracting xy,No more favorable cube intersections found,Final Implementation,Total 7 mult
27、iplications, 3 additions/subtractions Savings of 5 multiplications, 1 addition/subtraction compared to CSE Impossible to obtain such results using conventional techniques,Experimental setup,Polynomials used in Computer graphics and Signal Processing 1.0 technology library, characterized for power co
28、nsumption Synthesized using Synopsys Design CompilerTM Min Hardware constraints (1 adder + 1 multiplier) Med Hardware constraints (Max 4 multipliers),Experimental setup,Estimated power using Synopsys Power CompilerTM for random inputs, using RTL Simulator (VCSTM) Compared energy consumption with CSE
29、 and Horner form Compared energy after voltage scaling,Results (Comparing operations),Results (Min Hardware constraints),Results (Med Hardware constraints),Conclusions,Technique to reduce number of operations in polynomial expressions Large savings in energy consumption observed over CSE and Horner
30、methods Need to consider scheduling and resource allocation to obtain further improvements,Conclusions,Thank you! Questions ?,Extra slides,Finding Kernel Intersections (Distill Algorithm),Worst case scenario for Distill algorithmNumber of prime rectangles exponential in number of rows/columns Heuristic methods to find best prime rectangle In practice polynomial expressions are not so large,
