Algorithms and Parallel Computing

15.4 DATA SCHEDULING

The timing function assigns a time value to each node in the dependence graph. The algorithm dependence graph becomes transformed into a directed acyclic graph (DAG), which will help us determine multithreaded or systolic array implementations. A simple but very useful timing function is an affine scheduling function of the form [86]

(15.3)

where the function t(p) associates a time value t to a point p in the dependence graph. The column vector s = [s₁, s₂] is the scheduling vector and s is an integer.

A valid scheduling function uniquely maps any point p to a corresponding time index value. Such affine scheduling function must satisfy several conditions in order to be a valid scheduling function as explained below.

Assigning time values to the nodes of the dependence graph transforms the dependence graph to a DAG as 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. We assume the input text T = t₀ t₁ … t_n−1 arrives in word serial format where the index of ...