O'Reilly logo

Algorithms and Parallel Computing by Fayez Gebali

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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]tx1D49F_EuclidMathOne_10n_000100 is associated with the time value

(10.16) c10e016

(10.17) c10e017

where s = [s1 s2] is the scheduling vector and s is a scalar constant. Typically, the constant s = 0 since the domain x1D49F_EuclidMathOne_10n_000100 is typically in the first quadrant, the point at the origin p(0, 0) ∈ x1D49F_EuclidMathOne_10n_000100 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 ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required