Algorithms and Parallel Computing

15.6 DESIGN 1: DESIGN SPACE EXPLORATION WHEN s = [1 1]^t

The feeding point of input sample t₀ is easily determined from Fig. 15.1 to be p = [0 0]^t. The time value associated with this point is t(p) = 0. Using Eq. 15.3, we get s = 0. Applying the scheduling function in Eq. 15.8 to e_P and e_T, we get

(15.13)

(15.14)

This choice for the timing function implies that both input variables P and Y will be pipelined. The pipeline direction for the input T flows in a southeast direction in Fig. 15.1. The pipeline for T is initialized from the top row in the figure defined by the line j = m − 1. Thus, the feeding point of t₀ is located at the point p = [−m m]^t. The time value associated with this point is given by

(15.15)

Thus, the scalar s should be s = −2m. The tasks at each stage of the SPA derived in this section will have a latency of 2m time steps compared to Design 1.a.

Figure 15.2 shows how the dependence graph 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 and Y are pipelined between tasks, while variable T is broadcast ...