Volume 37, Number 3, July-September 2003
|145 - 156
|15 December 2003
Scheduling Precedence Task Graphs with Disturbances
ID – IMAG, Antenne ENSIMAG, ZIRST, 51 avenue Jean Kuntzmann, 38330
Montbonnot Saint-Martin, France; Denis.Trystram@imag.fr.
In this paper we consider the problem of scheduling precedence task graphs in parallel processing where there can be disturbances in computation and communication times. Such a phenomenon often occurs in practice, due to our inability to exactly predict the time because of system intrusion like cache miss and packet transmission time in mediums like ethernet etc. We propose a method based on the addition of some extra edges to protect the initial scheduling from performing badly due to such changes and provide an upper bound on the performance guarantee for the scheduling algorithms. Moreover, this construction guarantees a result at least as good as the result obtained for the initial static scheduling. We also show that this construction is a minimal set in context of partially on-line scheduling.
Key words: Parallel processing / scheduling / stability / uncertainty communication delays.
© EDP Sciences, 2003
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.