An efficient branch and bound algorithm for fine-grained hypercube multiprocessors is presented. The method uses a global storage allocation scheme where all processors collectively store all back-up paths such that each processor needs to store only a constant amount of information. At each iteration of the algorithm, all nodes of the current back-up tree may decide whether they need to create new children, be pruned, or remain unchanged. An algorithm that, on the basis of these decisions, updates the current back-up tree and distributes global information in O(log m) steps, where m is the current number of nodes, is described. This method also provides a dynamic allocation mechanism that obtains optimal load balancing. Another important property of the method is that, even if very drastic changes in the current back-up tree occur, the performance of the load balancing mechanism remains constant. The method is currently being implemented on the Connection Machine.

Additional Metadata
Conference IEEE International Workshop on Tools for Artificial Intelligence: Architectures, Languages and Algorithms
Citation
Dehne, F, Ferreira, Afonso G., & Rau-Chaplin, Andrew. (1989). Parallel branch and bound on fine-grained hypercube multiprocessors. Presented at the IEEE International Workshop on Tools for Artificial Intelligence: Architectures, Languages and Algorithms.