Algorithms and Parallel Computing

17.9 DESIGN 3: USING d₃ = [1 −1]^t

A point p = [i j]^t in DAG will be mapped to a point in DAG given by

(17.39)

The resulting corresponding to the projection matrix P₃ will consist of 2m − 1 nodes or tasks. Similar to design 2, each task is only active for m time steps at most. Therefore, we could map task T_i and T_j to T_k if the indices satisfy the equation

(17.40)

Through this artifact, we are able to reduce the number of nodes and ensure that each node is active all the time. Before we proceed further, we need to observe more closely the diagonal lines transferring the output of T_i−1,j−1 to T_{i, j}. After mapping, we see that communication is accomplished between tasks according to the relations