Geodesic
Scheduling Multilayer Divisible Computations
Berlińska, Joanna1 ; Drozdowski, Maciej2 
1 Faculty of Mathematics and Computer Science, Adam Mickiewicz University, Umultowska 87, 61-614 Poznań, Poland.
2 Institute of Computing Science, Poznań University of Technology, Piotrowo 2, 60-965 Poznań, Poland.
RAIRO - Operations Research - Recherche Opérationnelle, New challenges in scheduling theory, Tome 49 (2015) no. 2, pp. 339-368

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

We analyze scheduling multilayer divisible computations. Multilayer computations consist of a chain of parallel applications, such that one application produces input for the next one. A simple form of multilayer computations are MapReduce parallel applications. The operations of mapping and reducing are two divisible applications with precedence constraints. We propose a divisible load model and give an algorithm for scheduling multilayer divisible computations. The algorithm is tested in a series of computational experiments. We draw conclusions on schedule patterns and determinants of the performance.

Reçu le :
Accepté le :
DOI : 10.1051/ro/2014050
Classification : 90B35, 68M20, 68M14
Keywords: Scheduling, divisible loads, parallel processing, multilayer computations, MapReduce

Berlińska, Joanna 1 ; Drozdowski, Maciej 2

1 Faculty of Mathematics and Computer Science, Adam Mickiewicz University, Umultowska 87, 61-614 Poznań, Poland.
2 Institute of Computing Science, Poznań University of Technology, Piotrowo 2, 60-965 Poznań, Poland. 
@article{RO_2015__49_2_339_0,
     author = {Berli\'nska, Joanna and Drozdowski, Maciej},
     editor = {Blazewicz, Jacek and Pesch, Erwin and Philipps, Cynthia and Trystram, Denis and Zhang, Guochuan},
     title = {Scheduling {Multilayer} {Divisible} {Computations}},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {339--368},
     publisher = {EDP-Sciences},
     volume = {49},
     number = {2},
     year = {2015},
     doi = {10.1051/ro/2014050},
     zbl = {1310.90041},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1051/ro/2014050/}
}
TY  - JOUR
AU  - Berlińska, Joanna
AU  - Drozdowski, Maciej
ED  - Blazewicz, Jacek
ED  - Pesch, Erwin
ED  - Philipps, Cynthia
ED  - Trystram, Denis
ED  - Zhang, Guochuan
TI  - Scheduling Multilayer Divisible Computations
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2015
SP  - 339
EP  - 368
VL  - 49
IS  - 2
PB  - EDP-Sciences
UR  - http://geodesic.mathdoc.fr/articles/10.1051/ro/2014050/
DO  - 10.1051/ro/2014050
LA  - en
ID  - RO_2015__49_2_339_0
ER  - 
%0 Journal Article
%A Berlińska, Joanna
%A Drozdowski, Maciej
%E Blazewicz, Jacek
%E Pesch, Erwin
%E Philipps, Cynthia
%E Trystram, Denis
%E Zhang, Guochuan
%T Scheduling Multilayer Divisible Computations
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2015
%P 339-368
%V 49
%N 2
%I EDP-Sciences
%U http://geodesic.mathdoc.fr/articles/10.1051/ro/2014050/
%R 10.1051/ro/2014050
%G en
%F RO_2015__49_2_339_0
Berlińska, Joanna; Drozdowski, Maciej. Scheduling Multilayer Divisible Computations. RAIRO - Operations Research - Recherche Opérationnelle, New challenges in scheduling theory, Tome 49 (2015) no. 2, pp. 339-368. doi: 10.1051/ro/2014050

Cité par Sources :