LINEAR SCHEDULING IS NEARLY OPTIMAL
- 1 December 1991
- journal article
- Published by World Scientific Pub Co Pte Ltd in Parallel Processing Letters
- Vol. 1 (2) , 73-81
- https://doi.org/10.1142/s0129626491000021
Abstract
This paper deals with the problem of finding optimal schedulings for uniform dependence algorithms. Given a convex domain, let Tf be the total time needed to execute all computations using the free (greedy) schedule and let Tl be the total time needed to execute all computations using the optimal linear schedule. Our main result is to bound Tl/Tf and Tl − Tf for sufficiently "fat" domains.Keywords
This publication has 0 references indexed in Scilit: