Parallel Machine Scheduling with Uncertain Communication Delays

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

RAIRO - Operations Research (2010)

  • 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 37.1 (2010): 1-16. <http://eudml.org/doc/105277>.

@article{Moukrim2010,
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},
keywords = {Parallel computing; scheduling with communication delays; disturbances on communication delays; list scheduling flexibility.; parallel computing; scheduling with communication delays; distrubances on communication delays; list scheduling; flexibility},
language = {eng},
month = {3},
number = {1},
pages = {1-16},
publisher = {EDP Sciences},
title = {Parallel Machine Scheduling with Uncertain Communication Delays},
url = {http://eudml.org/doc/105277},
volume = {37},
year = {2010},
}

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
DA - 2010/3//
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.; parallel computing; scheduling with communication delays; distrubances on communication delays; list scheduling; flexibility
UR - http://eudml.org/doc/105277
ER -

References

top
  1. E. Bampis, F. Guinand and D. Trystram, Some Models for Scheduling Parallel Programs with Communication Delays. Discrete Appl. Math.51 (1997) 5-24.  
  2. Ph. Chrétienne, A polynomial algorithm to optimally schedule tasks on a virtual distributed system under tree-like precedence constraints. EJOR43 (1989) 225-230.  
  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).  
  4. E.G. Coffman Jr. and R.L. Graham, Optimal scheduling for two-processor systems. Acta Informatica1 (1972) 200-213.  
  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.  
  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.  
  7. A. Gerasoulis and T. Yang, A Comparison of Clustering Heuristics for Scheduling DAGs on Multiprocessors. J. Parallel Distributed Comput.16 (1992) 276-291.  
  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).  
  9. F. Guinand and D. Trystram, Optimal scheduling of UECT trees on two processors. RAIRO: Oper. Res.34 (2000) 131-144.  
  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.  
  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.  
  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.  
  13. P. Kouvelis and G. Yu, Robust Discrete Optimization and Its Applications. Kluwer Academic Publisher (1997).  
  14. J.K. Lenstra, M. Veldhorst and B. Veltman, The complexity of scheduling trees with communication delays. J. Algorithms20 (1996) 157-173.  
  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. C.H. Papadimitriou and M. Yannakakis, Towards an Architecture-Independent Analysis of Parallel Algorithms. SIAM J. Comput.19 (1990) 322-328.  
  17. V.J. Rayward-Smith, UET scheduling with interprocessor communication delays. Discrete Appl. Math.18 (1986) 55-71.  
  18. V. Sarkar, Partitioning and Scheduling Parallel Programs for Execution on Multiprocessors. The MIT Press (1989).  
  19. G.C. Sih and E.A. Lee, A compile-time scheduling heuristic for interconnection-constrained heterogeneous processor architectures. IEEE Trans. Parallel Distributed Systems4 (1993) 279-301.  
  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.  
  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.  
  22. T. Yang and A. Gerasoulis, List scheduling with and without communication delay. Parallel Comput.19 (1993) 1321-1344.  

NotesEmbed ?

top

You must be logged in to post comments.