15.7 DESIGN 2: DESIGN SPACE EXPLORATION WHEN s = [1 −1]t

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.

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)

(15.27)

(15.28)

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 d_{a} = [1 0]^{t}

The resulting is shown in Fig. 15.9 for the case when n = 10 and m = 4. Input T is pipelined between the tasks and task T_{i} is allocated pattern p_{i}. The partial results for Y are pipelined such that the outputs are obtained from task T_{0}.

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.