ABSTRACT
This chapter presents basic (but important) results on task graph scheduling. We start with a motivating example before providing a quick overview of models and complexity results.
Consider the following algorithm to solve the linear system Ax = b, where A is an n × n nonsingular lower triangular matrix and b is a vector with n components:
for i = 1 to n do Task Ti,i: xi ← bi/ai,i for j = i+ 1 to N do
Task Ti,j : bj ← bj − aj,i × xi
For a given value of i, 1 6 i 6 n, each task Ti,∗ represents some computations executed during the i-th iteration of the external loop. The computation of xi is performed first (task Ti,i). Then, each component bj of vector b such that j > i is updated (task Ti,j).
