Linear scheduling is close to optimality
Alain Darte, Leonid Khachiyan, Yves Robert · 2003
This paper deals with the problem of finding optimal schedulings for uniform dependence algorithms. Given a convex domain, let T/sub f/ be the total time needed to execute all computations using the free (greedy) schedule and let T/sub l/ be the total time needed to execute all computations using the optimal linear schedule. The authors' main result is to bound T/sub l//T/sub f/ and T/sub l/-T/sub f/ for sufficiently 'fat' domains.>