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
    0 references
    0 references
    0 references
    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