Most parallel and distributed platforms available today show a large unbalance between slow communications and fast local computations which makes the scheduling of tasks much harder to handle efficiently. The so called scheduling with large communication delays problem has been proved to be NP-hard even in some restricted cases. Its status regarding approximation is still unknown. In this work, we propose to study this challenging problem for graphs with a specific structure of 2-dimensional grids. More precisely, we provide lower and upper bounds for both sub-problems of unbounded number of processors and two processors. We show in both cases that the proposed scheduling algorithms are close to lower bounds.
Accepté le :
DOI : 10.1051/ro/2014048
Mots-clés : Parallel processing, scheduling, large communication delays
@article{RO_2015__49_2_369_0,
author = {Daoudi, E.M. and Trystram, D. and Wagner, F.},
editor = {Blazewicz, Jacek and Pesch, Erwin and Philipps, Cynthia and Trystram, Denis and Zhang, Guochuan},
title = {Scheduling 2-dimensional grids with large communication delays},
journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
pages = {369--381},
publisher = {EDP-Sciences},
volume = {49},
number = {2},
year = {2015},
doi = {10.1051/ro/2014048},
zbl = {1310.90044},
language = {en},
url = {http://www.numdam.org/articles/10.1051/ro/2014048/}
}
TY - JOUR AU - Daoudi, E.M. AU - Trystram, D. AU - Wagner, F. ED - Blazewicz, Jacek ED - Pesch, Erwin ED - Philipps, Cynthia ED - Trystram, Denis ED - Zhang, Guochuan TI - Scheduling 2-dimensional grids with large communication delays JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2015 SP - 369 EP - 381 VL - 49 IS - 2 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/ro/2014048/ DO - 10.1051/ro/2014048 LA - en ID - RO_2015__49_2_369_0 ER -
%0 Journal Article %A Daoudi, E.M. %A Trystram, D. %A Wagner, F. %E Blazewicz, Jacek %E Pesch, Erwin %E Philipps, Cynthia %E Trystram, Denis %E Zhang, Guochuan %T Scheduling 2-dimensional grids with large communication delays %J RAIRO - Operations Research - Recherche Opérationnelle %D 2015 %P 369-381 %V 49 %N 2 %I EDP-Sciences %U http://www.numdam.org/articles/10.1051/ro/2014048/ %R 10.1051/ro/2014048 %G en %F RO_2015__49_2_369_0
Daoudi, E.M.; Trystram, D.; Wagner, F. Scheduling 2-dimensional grids with large communication delays. RAIRO - Operations Research - Recherche Opérationnelle, New challenges in scheduling theory, Tome 49 (2015) no. 2, pp. 369-381. doi : 10.1051/ro/2014048. http://www.numdam.org/articles/10.1051/ro/2014048/
, , and , Scheduling trees with large communication delays on two identical processors. J. Scheduling 8 (2005) 179–190. | DOI | Zbl
R.J. Anderson, P. Beame and W. Ruzzo, Low overhead parallel schedules for task graphs, in Proc. of SPAA (1990).
, and , A low overhead schedule for a 3D-grid graph. Parallel Proces. Lett. 2 (1992). | DOI
E. Bampis, A. Giannakos and J-C. König, On the complexity of scheduling with large communication delays. EJOR 94 (1996). | Zbl
, and , Some models for scheduling parallel programs with communication delays. Discrete Appl. Math. 72 (1997). | DOI | Zbl
J. Blazewicz, K. Ecker, E. Pesh, G. Schimdt and J. Weglarz, Handbook on Scheduling – from theory to applications. Springer (2007). | Zbl
E.G. Coffman and P.J. Denning, Operating system theory. Prentice Hall (1972).
P. Chrétienne and C. Picouleau, Scheduling with communication delays: A survey, in Scheduling Theory and its Applications. Wiley (1995).
M. Cosnard and D. Trystram, Algorithmes et architectures parallèles. Inter Editions (1993).
M. Drozdowski, Scheduling for Parallel Processing. Springer (2009). | Zbl
R. Giroudeau, JC. Konig, F. Moulai and J. Palaysi, Complexity and approximation for the precedence constrained scheduling problem with large communication delays, in Proc. EuroPar, LNCS, Springer (2005). | Zbl
, , and , Scheduling precedence graphs in systems with interprocessor communication times. SIAM J. Comput. 18 (1989) 244–257. | DOI | Zbl
A. Jakoby and R. Reischuk, The complexity of scheduling problems with communication delays for trees, in Proc. Scandinavian workshop on Algorithmic Theory (1992).
V. Kumar, A. Grama, A. Gupta and G. Karypis, Introduction to parallel computing: design and analysis of algorithms. The Benjamin/Cummings Publishing company (1994). | Zbl
, and , The complexity of scheduling trees with communication delays. J. Algorithms 20 (1996). | DOI | Zbl
R. Lepere and C. Rapine, An asymptotic O()-approximation algorithm for the scheduling problem with duplication on large communication delay graphs, in Proc. STACS (2002). | Zbl
R. Lepère and D. Trystram, A new clustering algorithm for large communication delays, in Proc. of IPDPS (2002).
A. Munier, Approximation algorithms for scheduling trees with general communication delays. Parallel Computing (1999). | Zbl
and , Towards an Architecture-Independent Analysis of Parallel Algorithms. SIAM J. Comput. 19 (1990) 322–328. | DOI | Zbl
J. Pecero, D. Trystram and A. Zomaya, A new genetic algorithm for scheduling for large communication delays, in Proc. EuroPar, LNCS, Springer (2009).
, UET scheduling with unit interprocessor communication delays. Discrete Appl. Math. 18 (1987) 55–71. | DOI | Zbl
and , Scheduling task graphs optimally with A*. J. Supercomputing 51 (2010) 310–332. | DOI
and , List scheduling with and without communication delays. Parallel Computing 19 (1993) 1321–1344. | DOI | Zbl
D. Trystram, Scheduling parallel applications using malleable tasks on clusters, in Proc. of IPDPS (2001).
Cité par Sources :
