Paper published in a book (Scientific congresses and symposiums)
Distributed Dynamic Load Balancing for Iterative-Stencil Applications
Dethier, Gérard; Marchot, Pierre; de Marneffe, Pierre-Arnoul
2009In Cracow Grid Workshop '08 Proceedings
Peer reviewed
 

Files


Full Text
dethier-cgw08.pdf
Author preprint (149.34 kB)
Download
Annexes
CGW08-Poster.pdf
Publisher postprint (423.27 kB)
Poster (won the "Best Poster Award")
Download

The preferable form of CGW presentation is a poster. The poster associated to this paper won a "Best Poster Award".


All documents in ORBi are protected by a user license.

Send to



Details



Keywords :
Dynamic Load Balancing; Distributed Systems
Abstract :
[en] In the context of jobs executed on heterogeneous clusters or Grids, load balancing is essential. Indeed, a slow machine must receive less work than a faster one otherwise the overall job termination will be delayed. This is particularly true for Iterative-Stencil Applications where tasks are run simultaneously and are interdependent. The problem of assigning coexisting tasks to machines is called mapping. With dynamic clusters (where the number of machines and their available power can change over time), dynamic mapping must be used. A new mapping must be calculated each time the cluster changes. The mapping calculation must therefore be fast. Also, a new mapping should be as close as possible to the previous mapping in order to minimize task migrations. Dynamic mapping methods exist but are based on iterative optimization algorithms. Many iterations are required to reach convergence. In the context of a distributed implementation, many communications are needed. We developed a new distributed dynamic mapping method which is not based on iterative optimization algorithms. Current results are encouraging. Load balancing execution time remains bounded for tested cluster sizes. Also, a decrease of ~20% of the global available computational power of a cluster leads to ~30% of migrated tasks during load rebalancing. A new mapping is therefore close to the previous one.
Disciplines :
Computer science
Author, co-author :
Dethier, Gérard ;  Université de Liège - ULiège > Département de chimie appliquée > Génie chimique - Opérations physiques unitaires
Marchot, Pierre ;  Université de Liège - ULiège > Département de chimie appliquée > Génie chimique - Systèmes polyphasiques
de Marneffe, Pierre-Arnoul ;  Université de Liège - ULiège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Informatique (ingénierie du logiciel et algorithmique)
Language :
English
Title :
Distributed Dynamic Load Balancing for Iterative-Stencil Applications
Publication date :
March 2009
Event name :
Eight Cracow Grid Workshop (CGW'08)
Event organizer :
Academic Computer Center CYFRONET AGH
Institute of Computer Science AGH
Institute of Nuclear Physics PAN
Event place :
Cracow, Poland
Event date :
13-15 October 2008
Audience :
International
Main work title :
Cracow Grid Workshop '08 Proceedings
ISBN/EAN :
978-83-61433-00-2
Pages :
303-310
Peer reviewed :
Peer reviewed
Funders :
FWB - Fédération Wallonie-Bruxelles [BE]
Available on ORBi :
since 05 April 2009

Statistics


Number of views
184 (14 by ULiège)
Number of downloads
217 (9 by ULiège)

Bibliography


Similar publications



Contact ORBi