17.8 DESIGN 2: USING d₂ = [1 1]^t

A point in the DAG p = [i j]^t will be mapped by the projection matrix P₂ = [1 −1] onto the point

(17.35)

To ensure that the index of the points in is nonnegative, we will add a fixed value m − 1 to all the points. Thus, a point in the dependence graph p = [i j]^t will be mapped by the projection matrix P₂ = [1 −1] onto the point

(17.36)

The DAG corresponding to the projection matrix P₂ is shown in Fig. 17.4. The DAG consists of 2m − 1 nodes.

Figure 17.4 Task processing workload details at each SPA stage for the left-to-right shift-and-add field multiplication algorithm for m = 5 and d₂ = [1 1]^t.

Although the consists of 2m − 1 nodes, most of them are not active all the time. For example, task T₀ and T₈ are active for one time step only. T₁ and T₇ are active for two time steps only. Figure 17.5 show the node activities at the different time steps. In general, we note that T_i and T_m+i are active at nonoverlapping time steps. Therefore, we could map tasks T_i and T_j to T_k if the indices satisfy the equation

(17.37)

Figure 17.5 Task activity for the left-to-right shift-and-add field multiplication algorithm for m = 5 and d₂ = [1 1]^t.

Through this artifact, we are able to reduce the number of nodes and ensure that each task is active all the time. The reduced is shown in Fig. 17.6. Notice that signal b(m − 1 − i) is broadcast to all tasks. Notice also that the output of c(i, j) is obtained at the end of the ith time step and is obtained from T_k, where k is given by

(17.38)

Figure 17.6 Task processing workload details at each SPA stage for the left-to-right shift-and-add field multiplication algorithm for m = 5 and d₂ = [1 1]^t.

At the end of time step i, all outputs c(i, 0), c(i, 1), … c(i, m − 1) are obtained from tasks T₀, T₁, … T_m−1, respectively.