Analysis of the List Scheduling Algorithm for Precedence Constrained Parallel Tasks |
| |
Authors: | Keqin Li |
| |
Institution: | (1) Department of Mathematics and Computer Science, State University of New York, New Paltz, New York 12561-2499, USA |
| |
Abstract: | Given P processors, and a set of precedence constrained parallel tasks with their processor requirements and execution times, the problem of scheduling precedence constrained parallel tasks on multiprocessors is to find a nonpreemptive schedule of the tasks on a multiprocessor with P processors, such that the schedule length is minimized. We show that for many heuristic choices of the initial priority list, the list scheduling algorithm has worst-case performance ratio P, which is unbounded as P gets large. However, it is also shown that when task sizes are bounded from above by a fraction of P, the list scheduling algorithm has finite worst-case performance ratio. In particular, we prove that if all tasks request for no more than qP processors, where 0 < q < 1, then the worst-case performance ratio of the list scheduling algorithm is no larger than which is independent of the initial priority list. When q is small, the above bound is very close to the well known Graham's bound 2 – 1/P in scheduling sequential tasks. |
| |
Keywords: | list scheduling parallel task precedence constraint task scheduling worst-case performance ratio |
本文献已被 SpringerLink 等数据库收录! |
|