Algorithms and Parallel Computing

17.5 DATA SCHEDULING

Pipelining or broadcasting the variables of an algorithm is determined by the choice of a timing function that assigns a time value to each node in the dependence graph. A simple but useful timing function is an affine scheduling function of the form

(17.12)

where the function t(p) associates a time value t to a point p in the dependence graph. The row vector s = [s₁ s₂] is the scheduling vector and s is an integer. Since all points in have nonnegative indices, the value of scalar s must be 0.

Assigning time values to the nodes of the dependence graph in transforms the dependence graph to a directed acyclic graph (DAG) as was discussed in Chapters 10 and 11. More specifically, the DAG can be thought of as a serial–parallel algorithm (SPA) where the parallel tasks could be implemented using a thread pool or parallel processors for software or hardware implementations, respectively. The different stages of the SPA are accomplished using barriers or clocks for software or hardware implementations, respectively.

Input data timing restricts the space of valid scheduling functions. Let us assume that input variable b(i) arrives at different adjacent time steps. Referring to Eq. 17.8, if b(m − i) arrives at iteration i corresponding to time t, then b(m − i − 1) arrives ...