17.8 DESIGN 2: USING d2 = [1 1]t
A point in the DAG p = [i j]t will be mapped by the projection matrix P2 = [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 P2 = [1 −1] onto the point
(17.36)
The DAG corresponding to the projection matrix P2 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 d2 = [1 1]t.
Although the 
consists of 2m − 1 nodes, most of them are not active all the time. For example, task T0 and T8 are active for one time step only. T1 and T7 are active for two time steps only. Figure 17.5 show the node activities at the different time steps. In general, we note that Ti and Tm+i are active at nonoverlapping time steps. Therefore, we could ...
Get Algorithms and Parallel Computing now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
