5.5 Combined Optimization

101

5.5 Combined Optimization

The method presented in Section 5.4 can be used to form an estimate EG(n, p, R) of the error variances incurred through the implementation of computation graph G with word-lengths n, binary point locations p, and input correlation matrix R[τ ] = E{x[t]x[t − τ ]T }, where x is the vector of system primary inputs. This estimate may then be compared to the user-specified bounds E on error variance at each output.

Since both the scaling and the word-length of each signal can have an impact on system error and area, the problem of finding a suitable annotation for the computation graph must now be treated as the combined optimization problem formulated below c.f. the Word-length Optimization Problem from Chapter 4.

Problem 5.10 (Combined Word-length and Scaling Optimization).

Given a computation graph G(V, S) and correlation matrix R, the combined word-length and scaling optimization problem may be defined as to select (n, p) such that AG(n, p) is minimized subject to (5.14).

n N|S|	(5.14)
p Z|S|
EG(n, p, R) ≤ E

To solve this optimization problem, it is necessary to modify Algorithm Word-LengthFalling from Section 4.4 to incorporate the optimization of binary point locations. This is performed by Algorithm CombOptAlg, where 1 represents a vector of ones of appropriate size, and k is the scaling factor as described in Section 4.4. Bj is a lower bound on the binary point location of signal j. Typically Bj is set to be a fixed, but reasonably large, number of bits beneath the binary point location implied by 1 scaling. Although Bj is rarely reached in practical designs with realistic error constraints, these bounds are required to theoretically ensure termination of Algorithm CombOptAlg. Reaching pj = Bj is considered equivalent to pj −∞. The interpretation of this value is that it is unnecessary to calculate signal j in order to satisfy the error constraints, and so the entire cone of logic creating signal j may be optimized away.

Unlike the error estimation used in Algorithm Word-LengthFalling, the error estimation subroutine used in Algorithm CombOptAlg contains some computationally expensive calculations, namely the post-adder saturation error and pdf estimation, which involves numerical integration and series approximations [AS70]. However the calls to adder saturation error estimation routines in the above algorithm exhibit a high degree of temporal locality. It is highly probable that a given pj will not change from one iteration to the next, and therefore the same error estimations are often required. Rather than re-calculate these each time, new error estimates for a given adder are only

102 5 Saturation Arithmetic

calculated when the c parameter of either input saturated Gaussian distribution is changed, or the c¯ post-adder saturation nonlinearity cut-o is changed (see Sections 5.4.2 and 5.4.3).

5.5 Combined Optimization

103

Algorithm 5.3

Algorithm CombinedOptHeur Input: A Computation Graph G(V, S)

input correlation matrix R

Output: An Optimized Annotated Computation Graph G (V, S, A), (A = (n, p))

begin

Calculate the variance of each signal and the correlation coe cient between inputs to adders, to be used in all calls to the error estimation subroutine

Set p ← 1 scaling vector (as described in Section 3.1.1)

Determine u, the minimum uniform word-length satisfying EG(u · 1, p, R) ≤ E Set n ← ku · 1

do

Condition the graph G (V, S, A) Set currentcost ← AG(n, p) foreach signal j S do

Set bestmin ← currentcost

Determine w {2, ..., nj }, if such a w exists, such that

EG([n1 . . . nj−1 w nj+1 . . . n|S|]T , p, R) ≤ E and EG([n1 . . . nj−1 (w − 1) nj+1 . . . n|S|]T , p, R) E

If such a w exists, set minval ← AG([n1 . . . nj−1 w nj+1 . . . n|S|]T , p) If no such w exists, set minval ← AG([n1 . . . nj−1 1 nj+1 . . . n|S|]T , p)

if minval < bestmin do

Set bestsig ← j, bestmin ← minval, vartype ←word-length end if

Determine x {Bj + 1, ..., pj − 1, pj }, if such an x exists, such that

EG(n, [p1 . . . pj−1 x pj+1 . . . p|S|]T , R) ≤ E and EG(n, [p1 . . . pj−1 (x − 1) pj+1 . . . p|S|]T , R) E

If such an x exists, set minval ← AG(n, [p1 . . . pj−1 x pj+1 . . . p|S|]T ) If no such x exists, set minval ← AG(n, [p1 . . . pj−1 Bj pj+1 . . . p|S|]T )

if minval < bestmin do

Set bestsig ← j, bestmin ← minval, vartype ←scaling end if

end foreach

if bestmin < currentcost

if vartype = word-length

nbestsig ← nbestsig − 1 else

pbestsig ← pbestsig − 1 while bestmin < currentcost

end