UET scheduling with unit interprocessor communication delays (Q1097163)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | UET scheduling with unit interprocessor communication delays |
scientific article |
Statements
UET scheduling with unit interprocessor communication delays (English)
0 references
1987
0 references
We consider the problem of scheduling a partially ordered set of unit execution time tasks (UET) on \(m>1\) processors where there is a communication delay of unit time between any pair of distinct processors. We show that the problem of finding an optimal schedule is NP-hard. A greedy schedule is one where no processor remains idle if there is some task available which it could process. We establish that the length of an arbitrary greedy schedule, \(\omega^ c_ g\) satisfies \[ \omega^ c_ g\leq (3-\frac{2}{m})\omega^ c_{opt}-(1-\frac{1}{m}) \] where \(\omega^ c_{opt}\) is the length of the optimal schedule. We define a generalized list schedule (a type of greedy schedule) and discuss anomalous behaviour of such schedules with respect to speed-up. The relevance of these results to the implementation of parallel languages is discussed.
0 references
UET scheduling
0 references
list scheduling
0 references
multiprocessor systems
0 references
NP-completeness
0 references
speed-up anomaly
0 references
scheduling a partially ordered set of unit execution time
0 references
communication delay
0 references
NP-hard
0 references
greedy schedule
0 references
parallel languages
0 references
0 references