Parallel machine scheduling with uncertain communication delays

Aziz Moukrim; Eric Sanlaville; Frédéric Guinand

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

  • Volume: 37, Issue: 1, page 1-16
  • ISSN: 0399-0559

Abstract

top
This paper is concerned with scheduling when the data are not fully known before the execution. In that case computing a complete schedule off-line with estimated data may lead to poor performances. Some flexibility must be added to the scheduling process. We propose to start from a partial schedule and to postpone the complete scheduling until execution, thus introducing what we call a stabilization scheme. This is applied to the m machine problem with communication delays: in our model an estimation of the delay is known at compile time; but disturbances due to network contention, link failures, ... may occur at execution time. Hence the processor assignment and a partial sequencing on each processor are determined off-line. Some theoretical results for tree-like precedence constraints and an experimental study show the interest of this approach compared with fully on-line scheduling.

How to cite

top

Moukrim, Aziz, Sanlaville, Eric, and Guinand, Frédéric. "Parallel machine scheduling with uncertain communication delays." RAIRO - Operations Research - Recherche Opérationnelle 37.1 (2003): 1-16. <http://eudml.org/doc/244855>.

@article{Moukrim2003,
abstract = {This paper is concerned with scheduling when the data are not fully known before the execution. In that case computing a complete schedule off-line with estimated data may lead to poor performances. Some flexibility must be added to the scheduling process. We propose to start from a partial schedule and to postpone the complete scheduling until execution, thus introducing what we call a stabilization scheme. This is applied to the m machine problem with communication delays: in our model an estimation of the delay is known at compile time; but disturbances due to network contention, link failures, ... may occur at execution time. Hence the processor assignment and a partial sequencing on each processor are determined off-line. Some theoretical results for tree-like precedence constraints and an experimental study show the interest of this approach compared with fully on-line scheduling.},
author = {Moukrim, Aziz, Sanlaville, Eric, Guinand, Frédéric},
journal = {RAIRO - Operations Research - Recherche Opérationnelle},
keywords = {parallel computing; scheduling with communication delays; disturbances on communication delays; list scheduling; flexibility; distrubances on communication delays},
language = {eng},
number = {1},
pages = {1-16},
publisher = {EDP-Sciences},
title = {Parallel machine scheduling with uncertain communication delays},
url = {http://eudml.org/doc/244855},
volume = {37},
year = {2003},
}

TY - JOUR
AU - Moukrim, Aziz
AU - Sanlaville, Eric
AU - Guinand, Frédéric
TI - Parallel machine scheduling with uncertain communication delays
JO - RAIRO - Operations Research - Recherche Opérationnelle
PY - 2003
PB - EDP-Sciences
VL - 37
IS - 1
SP - 1
EP - 16
AB - This paper is concerned with scheduling when the data are not fully known before the execution. In that case computing a complete schedule off-line with estimated data may lead to poor performances. Some flexibility must be added to the scheduling process. We propose to start from a partial schedule and to postpone the complete scheduling until execution, thus introducing what we call a stabilization scheme. This is applied to the m machine problem with communication delays: in our model an estimation of the delay is known at compile time; but disturbances due to network contention, link failures, ... may occur at execution time. Hence the processor assignment and a partial sequencing on each processor are determined off-line. Some theoretical results for tree-like precedence constraints and an experimental study show the interest of this approach compared with fully on-line scheduling.
LA - eng
KW - parallel computing; scheduling with communication delays; disturbances on communication delays; list scheduling; flexibility; distrubances on communication delays
UR - http://eudml.org/doc/244855
ER -

References

top
  1. [1] E. Bampis, F. Guinand and D. Trystram, Some Models for Scheduling Parallel Programs with Communication Delays. Discrete Appl. Math. 51 (1997) 5-24. Zbl0863.68015MR1424523
  2. [2] Ph. Chrétienne, A polynomial algorithm to optimally schedule tasks on a virtual distributed system under tree-like precedence constraints. EJOR 43 (1989) 225-230. Zbl0689.90045MR1033650
  3. [3] Ph. Chrétienne and C. Picouleau, Scheduling with communication delays: a survey, in Scheduling Theory and its Applications, edited by Ph. Chrétienne, E.G. Coffman, J.K. Lenstra and Z. Liu. John Wiley Ltd. (1995). MR1376609
  4. [4] E.G. Coffman Jr. and R.L. Graham, Optimal scheduling for two-processor systems. Acta Informatica 1 (1972) 200-213. Zbl0248.68023MR334913
  5. [5] G.L. Djordjevic and M.B. Tosic, A heuristic for scheduling task graphs with communication delays onto multiprocessors. Parallel Comput. 22 (1996) 1197-1214. Zbl0875.68083MR1426112
  6. [6] G. Galambos and G.J. Woeginger, An on-line scheduling heuristic with better worst case ratio than Graham list scheduling. SIAM J. Comput. 22 (1993) 349-355. Zbl0781.90051MR1207790
  7. [7] A. Gerasoulis and T. Yang, A Comparison of Clustering Heuristics for Scheduling DAGs on Multiprocessors. J. Parallel Distributed Comput. 16 (1992) 276-291. Zbl0797.68021MR1196593
  8. [8] A. Gerasoulis and T. Yang, Application 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. Rolim. Kluwer Academic Publishers, The Netherlands (1995). Zbl0856.68130
  9. [9] F. Guinand and D. Trystram, Optimal scheduling of UECT trees on two processors. RAIRO: Oper. Res. 34 (2000) 131-144. Zbl0961.90032MR1755979
  10. [10] C. Hanen and A. Munier, Performance of Coffman Graham schedule in the presence of unit communication delays. Discrete Appl. Math. 81 (1998) 93-108. Zbl0894.68012MR1492003
  11. [11] 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
  12. [12] A.W.J. Kolen, A.H.G. Rinnooy Kan, C.P.M. Van Hoesel and A.P.M. Wagelmans, Sensitivity analysis of list scheduling heuristics. Discrete Appl. Math. 55 (1994) 145-162. Zbl0824.90082MR1301856
  13. [13] P. Kouvelis and G. Yu, Robust Discrete Optimization and Its Applications. Kluwer Academic Publisher (1997). Zbl0873.90071MR1480918
  14. [14] J.K. Lenstra, M. Veldhorst and B. Veltman, The complexity of scheduling trees with communication delays. J. Algorithms 20 (1996) 157-173. Zbl0840.68013MR1368721
  15. [15] A. Moukrim and A. Quilliot, Scheduling with communication delays and data routing in Message Passing Architectures. Springer, Lecture Notes in Comput. Sci. 1388 (1998) 438-451. 
  16. [16] C.H. Papadimitriou and M. Yannakakis, Towards an Architecture-Independent Analysis of Parallel Algorithms. SIAM J. Comput. 19 (1990) 322-328. Zbl0692.68032MR1042731
  17. [17] V.J. Rayward–Smith, UET scheduling with interprocessor communication delays. Discrete Appl. Math. 18 (1986) 55-71. Zbl0634.90031
  18. [18] V. Sarkar, Partitioning and Scheduling Parallel Programs for Execution on Multiprocessors. The MIT Press (1989). Zbl0679.68056
  19. [19] G.C. Sih and E.A. Lee, A compile-time scheduling heuristic for interconnection-constrained heterogeneous processor architectures. IEEE Trans. Parallel Distributed Systems 4 (1993) 279-301. 
  20. [20] Y.N. Sotskov, A.P.M. Wagelmans and F. Werner, On the calculation of stability radius of an optimal or an approximate schedule. Ann. O.R. 83 (1998) 213-252. Zbl0911.90222MR1661683
  21. [21] S.D. Wu, E. Byeon and R.H. Storer, A graph-theoretic decomposition of the job shop scheduling problem to achieve scheduling robustness. Oper. Res. 47 (1999) 113-124. Zbl0979.90030MR1689986
  22. [22] T. Yang and A. Gerasoulis, List scheduling with and without communication delay. Parallel Comput. 19 (1993) 1321-1344. Zbl0797.68020

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.