Algorithms and Parallel Computing

10.5 THE SCHEDULING FUNCTION FOR THE 1-D FIR FILTER

This section discusses how to execute the tasks in the dependence graph in stages of execution. At each stage, a group of the tasks gets executed followed by tasks in the next stage and so on. We use an affine scheduling function such that any point p = [i j]^t ∈ is associated with the time value

(10.16)

(10.17)

where s = [s₁ s₂] is the scheduling vector and s is a scalar constant. Typically, the constant s = 0 since the domain is typically in the first quadrant, the point at the origin p(0, 0) ∈ and s usually has positive components.

The main purpose of the scheduling function is to divide the tasks in the dependence graph into stages that are executed sequentially. Several tasks will be executed in parallel at each stage. Effectively, the scheduling function will convert the dependence graph into a DAG, and more specifically, it will convert it into a serial–parallel algorithm (SPA) as Theorems 11.2 and 11.3 will prove in Chapter ...