Parallel processing of best-first branch and bound algorithms on distributed memory multiprocessors.

Abstract

The mapping of Branch and Bound (BB) algorithms on Distributed Memory Multiprocessors (DMMs) is considered. The performance of a parallel BB algorithm on this class of multiprocessors is degraded by three types of overhead. The first is computation overhead, which reflects the cost of exp and ing subproblems that are not exp and ed by the sequential algorithm. The second is imbalance overhead, which reflects the amount of idle time due to load imbalance. The third is communication overhead, which reflects the cost of interprocessor communication. There is a tradeoff between the first two types of overhead versus the third. The extent to which the three types of overhead and the tradeoff among them affect performance is demonstrated experimentally using three parallel algorithms implemented on a commercial hypercube multiprocessor. The algorithms represent different strategies for mapping the BB technique on hypercubes. The first two algorithms (CL and SHIFT) represent common strategies for mapping the sequential algorithm onto DMMs. The third algorithm, referred to as the DL algorithm, is proposed to demonstrate the effective use of the tradeoff among the overheads which is embodied in the strategy used by that algorithm. The performance of the three algorithms is measured for four application problems: the 8-puzzle problem, the 0-1 integer programming problem, the traveling salesman problem, and the general integer programming problem. The performance of the DL algorithm shows an overall performance that is generally better than the performance of the other two algorithms.