Reference : Distributed Dynamic Load Balancing for Iterative-Stencil Applications
Scientific congresses and symposiums : Paper published in a book
Engineering, computing & technology : Computer science
Distributed Dynamic Load Balancing for Iterative-Stencil Applications
Dethier, Gérard mailto [Université de Liège - ULg > Département de chimie appliquée > Génie chimique - Opérations physiques unitaires >]
Marchot, Pierre mailto [Université de Liège - ULg > Département de chimie appliquée > Génie chimique - Systèmes polyphasiques >]
de Marneffe, Pierre-Arnoul mailto [Université de Liège - ULg > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Informatique (ingénierie du logiciel et algorithmique) >]
Cracow Grid Workshop '08 Proceedings
Eight Cracow Grid Workshop (CGW'08)
13-15 October 2008
Academic Computer Center CYFRONET AGH
Institute of Computer Science AGH
Institute of Nuclear Physics PAN
[en] Dynamic Load Balancing ; Distributed Systems
[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.
Communauté française de Belgique - CfB
The preferable form of CGW presentation is a poster. The poster associated to this paper won a "Best Poster Award".

File(s) associated to this reference

Fulltext file(s):

Open access
dethier-cgw08.pdfAuthor preprint145.84 kBView/Open

Additional material(s):

File Commentary Size Access
Open access
CGW08-Poster.pdfPoster (won the "Best Poster Award")413.35 kBView/Open

Bookmark and Share SFX Query

All documents in ORBi are protected by a user license.