4.4	Optimization Strategy 1: Heuristic Search	51
22p (4 · 2−2n2 − 2−2n1 )L22	3
	Hi(z) + (2−2n3 − 4 · 2−2n2 )L22{H3(z)}
	=1
	i	(4.17)

3

22p (4 · 2−2n2 − 2−2n1 )L22 i=1 Hi(z) + 12 · 2−n2 L22{H1(z) + H3(z)}+

(2

−

2n3

16

2−

2n2

)L

2

z)

−

·

{

H3(

2

}

(4.18)

3 · 22(p−n2) L22

3

3

Hi(z) − L22

Hi(z)

(4.19)

=1

=2

i

i

12 · 22(p−n2) L22{H1(z) + H3(z)} − L22{H3(z)}

(4.20)

Example 4.6. As an example, consider the annotated computation graphs shown in Fig. 4.15(b). In the uppermost graph, the errors injected by quantizers Q1, Q2 and Q3 have variance 2−12 − 2−14, 2−10 − 2−12 and 2−8 − 2−10,

respectively. Applying L2 scaling results in a predicted error variance of 25 · (2−16 − 2−18) + 2−14 − 2−16 + 9 · (2−12 − 2−14) = 519 · 2−18. For the

system in the centre of Fig. 4.15(b), the errors injected by quantizers Q1, Q2 and Q3 have variance 2−10 − 2−14, 0, and 2−8 − 2−10, respectively. Applying L2 scaling results in a predicted error variance of 25 · (2−14 − 2−18) + 9 · (2−12 − 2−14) = 807 · 2−18, an increase on the previous error variance. Finally considering the lower-most system in Fig. 4.15(b), the errors injected by quantizers Q1, Q2 and Q3 have variance 2−10 − 2−14, 2−8 − 2−10 and 0, respectively. Applying L2 scaling results in a predicted error variance of 25 · (2−14 − 2−18) + 2−12 − 2−14 = 423 · 2−18, a reduction over the previous error variance. Thus if a user-specified constraint on the output noise power were set between 519 ·2−18 and 807 ·2−18, then the uppermost and lower-most structures would be feasible but the centre structure would be infeasible.

It has been shown that the noise model derived in Section 4.1.2 leads to a constraint space which, under well defined conditions, may be non-convex in the word-length optimization variables. It should be noted that this property is not simply an artifact of the noise model, but has been observed in practice using bit-true simulation. This non-convexity makes the constraint space a harder space to search for optimum solutions [Fle81].

4.4 Optimization Strategy 1: Heuristic Search

Since the word-length optimization problem is NP-hard [CW01], a heuristic approach has been developed to find feasible word-length vectors having small,

. . . nj|S|

. . . nj|S|

52 4 Word-Length Optimization

though not necessarily optimal, area consumption. The heuristic algorithm used is shown in Algorithm Word-LengthFalling. After performing an 1 scaling, the algorithm determines the minimum uniform word-length satisfying all error constraints. The design at this stage corresponds to a standard uniform word-length design with implicit power-of-two scaling, such as may be used for an optimized uniprocessor-based implementation. Each word-length is then scaled up by a factor k > 1, which represents a bound on the largest value that any word-length in the final design may reach. In the Synoptix implementation [CCL00a, CCL01b], k = 2 has been used. At this point the structure may be ill-conditioned, requiring reduction to a well-conditioned structure, as described in Section 4.1.1.

The resulting well-conditioned structure forms a starting point from which one signal word-length is reduced by one bit on each iteration. The signal word-length to reduce is decided in each iteration by reducing each wordlength in turn until it violates an output noise constraint. At this point there is likely to have been some pay-o in reduced area, and the signal whose word-length reduction provided the largest pay-o is chosen. Each signal’s word-length is explored using a binary search.

Although Algorithm Word-LengthFalling is a greedy algorithm, both the constraints and the objective function play a role in determining the direction of movement towards the solution. As a result, this algorithm is less dependent on local information than a pure steepest-descent search.

Algorithm 4.2

Algorithm Word-LengthFalling Input: A Computation Graph G(V, S)

Output: An optimized annotated computation graph G (V, S, A), with A = (n, p)

begin

Let the elements of S be denoted as S = {j1, j2, . . . j|S|} Determine p through 1 scaling

Determine u, the minimum uniform word-length satisfying (4.10) with n = u · 1

Set n ← ku · 1 do

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

Set bestmin ← currentcost

Determine w {2, . . . , nji }, if such a w exists, such

that (4.10) is satisfied for annotation ([nj1 . . . nji−1 w nji+1 but not satisfied for annotation ([nj1 . . . nji−1 (w − 1) nji+1

If such a w exists, set minval ← AG([nj1 . . . nji−1 w nji+1 If no such w exists, set minval ← AG([nj1 . . . nji−1 1 nji+1 if minval < bestmin do

. . . nj|S| ]T , p)

. . . nj|S| ]T , p) ]T , p)

]T , p)