Load Balancing in Parallel and Distributed Systems
Load balancing is one of the key problems that must be addressed to efficiently use parallel and distributed computer systems. A parallel application can be visually described as a component-wise manufacturing process in industrial production. An application (=fabrication of an industrial product) is divided in several subtasks (=sub-products) and these subtasks are executed on different processors (=workers) of the parallel or distributed system. Subtasks can either be run independently from each other or, if required by the underlying application, interdependencies between them have to be obeyed. In the latter case, the processors must use communication in order to exchange intermediate results. Summarized, the load balancing problem aims at the following goals:
- The application's total execution time should be minimized.
- All processors of the system should operate during the whole computation and idle times should be avoided.
- The total load in the system should be distributed equally and 'fair' among the processors of the system.
- The communication overhead between the processors should be minimized.
For several years, the research group Monien has studied efficient load balancing algorithms. While we have analyzed the problem theoretically, we have also implemented the resulting algorithms and tested them in real world applications. We distinguish between synchronous and asynchronous load balancing methods. In the synchronous case, all processes involved in the computation stop from time to time in order to balance the newly generated load among them. In contrast, the load distribution is performed as a constant background process which is performed simultaneously with the computations in the asynchronous case.
To obtain good mappings of the tasks to the processors, several efficient methods have been developed. In our research group we have focused on analyzing local iterative load balancing algorithms. Thereby, we distinguish between diffusion and dimension exchange schemes. These two classes differ in the topology's communication abilities. Diffusion algorithms assume that a node of a network can send and receive messages to/from all of its neighbours simultaneously, whereas dimension exchange does only use pair wise communication with one neighbour after the other. We have determined the exact convergence rate, the flow quality as well as the behaviour of known diffusion algorithms. However, the analysis of the dimension exchange method is much more complicated and its convergence rate has only be determined for some simple topologies so far.
Other load balancing approaches that we consider are based on randomized strategies and exchange load between randomly chosen processors. Strategies of interests are Bidding and Workstealing. A somehow different approach is described by so called 'balls into bins' game. In this game, newly arriving jobs (balls) are evenly assigned to the processors (bins). Hereby the load of a constant number of randomly chosen bins is checked before the newly arriving ball is assigned to the processor with the smallest load.
The load balancing algorithms we have developed in our research group are integrated into real applications. Among them is a distributed computer chess program, a finite element method simulation tool and image generation software. The resulting feedback leads to further improvements of our methods. Over last years, we have also developed several software libraries that contain the most efficient load balancing strategies. Here we mention the 'Portable Parallel Branch-and-Bound Library (PPBBLib)' and the 'Virtual Data Space (VDS)' library. PPBBLib parallelizes sequential Branch-and-Bound algorithms by replacing the sequential heap by a (balanced) distributed implementation. VDS enables concurrent use of various load balancing paradigms and provides visual performance evaluation tools to facilitate the efficient application of the system.
In the future, load balancing algorithms for large, distributed and dynamic networks should be developed. Here, non-cooperative networks (such that the Internet) play a very important role. In order to develop efficient load balancing strategies for such topologies, the use of sophisticated linear algebraic and game theoretic methods is required.
Applications
Contact:
Dr. rer. nat. Robert ElsässerTel.: +49 (0) 52 51 60 66 90
elsa@upb.de
http://www.upb.de/cs/elsa/