Performance Evaluation of Load Distribution Strategies in Parallel Branch and Bound Computations

Load distribution is essential for efficient use of available processors in a parallel branch-and-bound computation because the computation generates and consumes non-uniform subproblems at runtime. This paper presents six decentralized load distribution strategies. They are incorporated in a runtime support system, and evaluated in the solution of set partitioning problems on two parallel computer systems. It is observed that local averaging strategies outperform the randomized allocation and the Acwn algorithm significantly in large scale systems. They lead to an almost linear speedup in a PowerPC-based system with up to 32 nodes and to a speedup of 146.8 in a Transputer-based system with 256 nodes. It is also observed that the randomized allocation and the Acwn algorithm can be improved by 10% to 15% when the bound information of subproblems is accounted for in the decision-making for load balancing. 1 Introduction Branch-and-bound is a well-known technique for solving combinatori..