Druckansicht der Internetadresse:

Fakultät für Mathematik, Physik und Informatik

Angewandte Informatik III - Robotik und eingebettete Systeme - Prof. Dr. Dominik HENRICH

Seite drucken


All fields:


The Liquid Model Load Balancing Method
Dominik Henrich

Abstract (english)
Load balancing is one of the central problems that have to be solved in parallel computation. Here, the problem of distributed, dynamic load balancing for massive parallelism is addressed. A new local method, which realizes a physical analogy to equilibrating liquids in multi-dimensional tori or hypercubes, is presented. It is especially suited for communication mechanisms with low set-up to transfer ratio occurring in tightly-coupled or SIMD systems. By successive shifting single load elements to the direct neighbors, the load is automatically transferred to lightly loaded processors. Compared to former methods, the proposed Liquid model has two main advantages. First, the task of load sharing is combined with the task of load balancing, where the former has priority. This property is valuable in many applications and important for highly dynamic load distribution. Second, the Liquid model has high efficiency. Asymptotically, it needs O(D . K . Ldiff ) load transfers to reach the balanced state in a D-dimensional torus with K processors per dimension and a maximum initial load difference of Ldiff . The Liquid model clearly outperforms an earlier load balancing approach, the nearest-neighbor-averaging. Besides a survey of related research, analytical results within a formal framework are derived. These results are validated by worst-case simulations in one-and two-dimensional tori with up to two thousand processors.

Publication data

Year: 1996
Publication date: 01. January 1996
Source: Journal of Parallel Algorithms and Applications, Special Issue on Algorithms for Enhanced Mesh Architectures
Project: LOADBAL
Referrer: https://www.ai3.uni-bayreuth.de/de/publikationen/resypub/index.php?mode=pub_show&pub_ref=henrich1996c


  TITLE             = "The Liquid Model Load Balancing Method",
  AUTHOR            = "Henrich, Dominik",
  YEAR              = "1996",
  JOURNAL           = "Journal of Parallel Algorithms and Applications, Special Issue on Algorithms for Enhanced Mesh Architectures",
  HOWPUBLISHED      = "\url{https://www.ai3.uni-bayreuth.de/de/publikationen/resypub/index.php?mode=pub_show&pub_ref=henrich1996c}",


Filename   Size   Language   Format
henrich1996c.The.Liquid.Model.Load.Balancing.Method.djvu   193.6K   english   DJVU download preprint
henrich1996c.The.Liquid.Model.Load.Balancing.Method.pdf   143.2K   english   PDF download preprint

Twitter Youtube-Kanal UBT-A Kontakt