Distributed Dynamic Load Balancing for Iterative-Stencil Applications

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.