Algorithms and Parallel Computing

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 ...