Parallel branch and bound on fine-grained hypercube multiprocessors |
| |
Authors: | Frank Dehne Afonso G. Ferreira Andrew Rau-Chaplin |
| |
Affiliation: | † Center for Parallel and Distributed Computing, School of Computer Science, Carleton University, Ottawa, Canada K1S 5BS ‡ Laboratoire de l'Informatique du Parallelisme - IMAG, Ecole Normale Superieure de Lyon, 69364, Lyon cedex 07, France |
| |
Abstract: | In this paper, we study parallel branch and bound on fine grained hypercube multiprocessors. Each processor in a fine grained system has only a very small amount of memory available. Therefore, current parallel branch and bound methods for coarse grained systems ( 1000 nodes) cannot be applied, since all these methods assume that every processor stores the path from the node it is currently processing back to the node where the process was created (the back-up path). Furthermore, the much larger number of processors available in a fine grained system makes it imperative that global information (e.g. the current best solution) is continuously available at every processor; otherwise the amount of unnecessary search would become intolerable. We describe an efficient branch-and-bound algorithm for fine grained hypercube multiprocessors. Our method uses a global 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 current nodes may decide whether they need to create new children, be pruned, or remain unchanged. We describe an algorithm that, based on these decisions, updates the current back-up paths and distributes global information in O(log m) steps, where m is the current number of nodes. This method also includes dynamic allocation of search processes to processors and provides optimal load balancing. Even if very drastic changes in the set of current nodes occur, our load balancing mechanism does not suffer any slow down. |
| |
Keywords: | Parallel algorithms Branch and bound Hypercube multiprocessor Fine grained parallel systems Load balancing Process allocation |
本文献已被 ScienceDirect 等数据库收录! |
|