Geodesic
Scheduling 2-dimensional grids with large communication delays
Daoudi, E.M.1  ; Trystram, D.2, 3 ; Wagner, F.2
1 University Mohammed I, Faculty of Sciences, LaRI laboratory, Oujda, Morocco.
2 Grenoble Institute of Technology, France.
3 Institut Universitaire de France 
RAIRO - Operations Research - Recherche Opérationnelle, New challenges in scheduling theory, Tome 49 (2015) no. 2, pp. 369-381

Voir la notice de l'article provenant de la source Numdam

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.

Reçu le :
Accepté le :
DOI : 10.1051/ro/2014048
Classification : 90B35
Keywords: Parallel processing, scheduling, large communication delays

Daoudi, E.M. 1 ; Trystram, D. 2, 3 ; Wagner, F. 2

1 University Mohammed I, Faculty of Sciences, LaRI laboratory, Oujda, Morocco.
2 Grenoble Institute of Technology, France.
3 Institut Universitaire de France  
@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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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

Cité par Sources :