18.4 DATA SCHEDULING

Data scheduling assigns a time index value to any point in the dependence graph of Fig. 18.1. We use an affine scheduling function to specify the scheduling of the algorithm tasks. The affine scheduling functions are of the form [86]

(18.8)

where s = [s₁ s₂] is the scheduling vector and s is an integer.

Assigning time values to the nodes of the dependence graph 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.

Our choice for the scheduling vector is determined by any data input/output (I/O) requirements. Since the divisor polynomial is typically of low order, we can store its coefficients in memory and only treat A as an input polynomial supplied by the system generating the data to be compressed. From the figure, it appears that coefficient a_i of A is supplied to the dependence graph at the rightmost edge at point

(18.9)

From Eqs. 18.8 and 18.9, the time index value associated with such point is given by

(18.10)

Since the time of arrival difference between a_i−1 and a_i is 1, we can write

(18.11)

Thus, we must have s₁ = 1 in our scheduling function.

We can explore the possible values of s₂ by observing that the q input, shown by horizontal lines, is obtained at the left and is used by all the points on the horizontal line. Therefore, time associated with point (i, j) must be larger than or equal to the time value associated with point (i, j + 1). We can write this as

(18.12)

The above equation yields the inequality

(18.13)

We have another restriction on the value of s₂. The source of data for points on any diagonal lines is the a coefficients that are supplied at the right. Therefore, time associated with point (i, j) must be smaller than or equal to the time value associated with point (i + 1, j + 1). We can write this as

(18.14)

The above equation yields the inequality

(18.15)

From the above two inequalities, we deduce that the range for s₂ is

(18.16)

There are three possible choices for our scheduling function:

(18.17)

(18.18)

(18.19)