University of Paderborn Computer Science Home AG-Monien Research   Load Balancing   Basics Synchronous Algorithms Asynchronous Algorithms Applications

Dynamic Load Balancing and Scheduling Load 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 whole work should be completed as fast as possible. As workers are very expensive, they should be kept busy. If there is only little work to do, the distribution of the tasks has to be planed very well. On the other hand, at other time periods the distribution can be done straight ahead because there is enough work to do. The work should be distributed fairly. About the same amount of work should be assigned to every worker. There are precedence contstraints between different tasks (we can start building the roof only after finishing the walls). Thus we also have to find a clever processing order of the different jobs. Our working team has been dealing with load balancing and scheduling problems since several years. The activities include a wide area of topics ranging from purely theoretical questions to real applications.   Basics 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 "balls-into-bins-games" as well as more complex settings.   Algorithms 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.   Synchronous algorithms   Asynchronous algorithms   Applications 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