Hostname: page-component-cd9895bd7-q99xh Total loading time: 0 Render date: 2024-12-23T12:37:27.225Z Has data issue: false hasContentIssue false
  • English
  • Français

Scheduling Precedence Task Graphs with Disturbances

Published online by Cambridge University Press:  15 December 2003

Apurv Gupta ,
Gilles Parmentier  and
Denis Trystram
Apurv Gupta
Affiliation:
ID – IMAG, Antenne ENSIMAG, ZIRST, 51 avenue Jean Kuntzmann, 38330 Montbonnot Saint-Martin, France; [email protected].
Gilles Parmentier
Affiliation:
ID – IMAG, Antenne ENSIMAG, ZIRST, 51 avenue Jean Kuntzmann, 38330 Montbonnot Saint-Martin, France; [email protected].
Denis Trystram
Affiliation:
ID – IMAG, Antenne ENSIMAG, ZIRST, 51 avenue Jean Kuntzmann, 38330 Montbonnot Saint-Martin, France; [email protected].
Get access

Abstract

In this paper we consider the problem of scheduling precedence task graphs inparallel processing where there can be disturbances in computation andcommunication times. Such a phenomenon often occurs in practice, due to ourinability 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 theperformance guarantee for the scheduling algorithms. Moreover, this construction guarantees a result at least as goodas 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.

Keywords

Parallel processingschedulingstabilityuncertaintycommunication delays.
Type
Research Article
Information
RAIRO - Operations Research , Volume 37 , Issue 3 , July 2003 , pp. 145 - 156
Copyright
© EDP Sciences, 2003

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

J. Blazewicz, K. Ecker, E. Pesch, G. Schmidt and J. Weglarz, Scheduling in Computer and Manufacturing Systems. Springer-Verlag, 3rd edn. (1996).
Gerasoulis, A. and Yang, T., Dsc: Scheduling parallel tasks on an unbounded number of processors. IEEE Trans. Parallel Distrib. Syst. 5 (1994) 951-967.
A. Gerasoulis, J. Jiao and T. Yang, Applications of graph scheduling techniques in parallelizing irregular scientific computation, in Parallel Algorithms for Irregular Problems: State of the Art, edited by A. Ferreira and J.D.P. Rolim, Chapter 13. Kluwer Academic Publishers, Netherlands (1995) 245-267.
F. Guinand, A. Moukrim and E. Sanlaville, Scheduling With Communication Delays and On-Line Disturbances, in Proc. of the European Conference on Parallel Computing, EuroPar'99, Aug. 31-Sept. 3, Toulouse (France). Springer-Verlag, Lecture Notes in Comput. Sci. 1685 (1999).
Hwang, J.-J., Chow, Y.-C., Anger, F.D. and Lee, C.-Y., Scheduling precedence graphs in systems with interprocessor communication times. SIAM J. Comput. 18 (1989) 244-257. CrossRef
P. Kouvelis and G. Yu, Robust Discrete Optimization and its Applications. Kluwer Academic Publishers (1997).
Kieckhafer, R.M., Deogun, J.S. and Krings, A.W., The performance of inherently stable multiprocessor list scheduler. Real Time Syst. 15 (1998) 5-39.
Krings, A.W. and Dror, M., Real-time dispatching: Scheduling stability and precedence. Int. J. Found. Comput. Sci. 10 (1999) 313-327. CrossRef
Manacher, G.K., Production and stabilization of real-time task schedules. J. ACM 14 (1967) 439-465. CrossRef
Papadimitriou, C. and Yannakakis, M., Towards an architecture-independent analysis of parallel algorithms. SIAM J. Comput. 19 (1990) 322-328. CrossRef