Scheduling precedence task graphs with disturbances

Apurv Gupta; Gilles Parmentier; Denis Trystram

RAIRO - Operations Research - Recherche Opérationnelle (2003)

  • Volume: 37, Issue: 3, page 145-156
  • ISSN: 0399-0559

Abstract

top
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.

How to cite

top

Gupta, Apurv, Parmentier, Gilles, and Trystram, Denis. "Scheduling precedence task graphs with disturbances." RAIRO - Operations Research - Recherche Opérationnelle 37.3 (2003): 145-156. <http://eudml.org/doc/244624>.

@article{Gupta2003,
abstract = {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.},
author = {Gupta, Apurv, Parmentier, Gilles, Trystram, Denis},
journal = {RAIRO - Operations Research - Recherche Opérationnelle},
keywords = {parallel processing; scheduling; stability; uncertainty; communication delays; communication times},
language = {eng},
number = {3},
pages = {145-156},
publisher = {EDP-Sciences},
title = {Scheduling precedence task graphs with disturbances},
url = {http://eudml.org/doc/244624},
volume = {37},
year = {2003},
}

TY - JOUR
AU - Gupta, Apurv
AU - Parmentier, Gilles
AU - Trystram, Denis
TI - Scheduling precedence task graphs with disturbances
JO - RAIRO - Operations Research - Recherche Opérationnelle
PY - 2003
PB - EDP-Sciences
VL - 37
IS - 3
SP - 145
EP - 156
AB - 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.
LA - eng
KW - parallel processing; scheduling; stability; uncertainty; communication delays; communication times
UR - http://eudml.org/doc/244624
ER -

References

top
  1. [1] J. Blazewicz, K. Ecker, E. Pesch, G. Schmidt and J. Weglarz, Scheduling in Computer and Manufacturing Systems. Springer-Verlag, 3rd edn. (1996). Zbl0767.90033
  2. [2] A. Gerasoulis and T. Yang, Dsc: Scheduling parallel tasks on an unbounded number of processors. IEEE Trans. Parallel Distrib. Syst. 5 (1994) 951-967. 
  3. [3] 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. Zbl0856.68130
  4. [4] 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). 
  5. [5] J.-J. Hwang, Y.-C. Chow, F.D. Anger and C.-Y. Lee, Scheduling precedence graphs in systems with interprocessor communication times. SIAM J. Comput. 18 (1989) 244-257. Zbl0677.68026MR986664
  6. [6] P. Kouvelis and G. Yu, Robust Discrete Optimization and its Applications. Kluwer Academic Publishers (1997). Zbl0873.90071MR1480918
  7. [7] R.M. Kieckhafer, J.S. Deogun and A.W. Krings, The performance of inherently stable multiprocessor list scheduler. Real Time Syst. 15 (1998) 5-39. 
  8. [8] A.W. Krings and M. Dror, Real-time dispatching: Scheduling stability and precedence. Int. J. Found. Comput. Sci. 10 (1999) 313-327. Zbl1319.68038MR1726988
  9. [9] G.K. Manacher, Production and stabilization of real-time task schedules. J. ACM 14 (1967) 439-465. 
  10. [10] C. Papadimitriou and M. Yannakakis, Towards an architecture-independent analysis of parallel algorithms. SIAM J. Comput. 19 (1990) 322-328. Zbl0692.68032MR1042731

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.