
Dynamic Load Balancing and SchedulingLoad balancing for a parallel system is one of the most important problems which has to be solved in order to enable the efficient use of parallel computer systems. This problem can be compared to problems arising in natural work distribution processes like that of scheduling all activities (tasks) needed to construct a large building. Several objectives have to be taken into consideration:
The reasearch in this area focusses on the analysis of different load balancing strategies. We are interested in the behavior of randomized algorithms and investigate simple "ballsintobinsgames" as well as more complex settings. In this area we develop and evaluate load balancing algorithms. In order to ensure their practical applicability we evaluate them using simulations or implementations on parallel systems. We distinguish between synchronous and asynchronous algorithms. In the first case we assume alternating calculation and load balancing phases. In the second case the load balancing activities are performed at the same time as the calculation. The load balancing algorithms are integrated into real applications like distributed computer chess, finite element methods, and image generation. The resulting feedback leeds to a further improvement of our methods. If you are interested, please contact Thomas Decker or Petra Berenbrink.
updated by Thomas Decker Jan/28/1998 