Figure 15.8 shows how the dependence of Fig. 15.1 is transformed to the DAG associated with s = [1 1]t. The equitemporal planes are shown by the gray lines and the execution order is indicated by the gray numbers. We note that the variables P, T, and Y are pipelined between tasks.

Figure 15.8 DAG for Design 2 when n = 10 and m = 4.


There are three simple projection vectors such that all of them satisfy Eq. 15.12 for the scheduling function. The three projection vectors are

(15.26) c15e026

(15.27) c15e027

(15.28) c15e028

Our multithreading design space now allows for three configurations for each projection vector for the chosen timing function.

15.7.1 Design 2.a: Using s = [1 −1]t and da = [1 0]t

The resulting c15ue009 is shown in Fig. 15.9 for the case when n = 10 and m = 4. Input T is pipelined between the tasks and task Ti is allocated pattern pi. The partial results for Y are pipelined such that the outputs are obtained from task T0.

Get Algorithms and Parallel Computing now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.