A Tight Upper Bound for the Speed-Up of Parallel Best-First Branch-and-Bound Algorithms.
MARYLAND UNIV COLLEGE PARK CENTER FOR AUTOMATION RESEARCH
Pagination or Media Count:
Most previous studies of the speedup of parallel branch-and-bound algorithms are based on the amount of work done in the parallel case and in the sequential case. Any evaluation of a parallel algorithm should include both the execution time and the synchronization delay. In this paper, a finite population queueing model is used to capture the synchronization delay in parallel branch-and-bound algorithms and to quantitatively predict the behavior of their speedup. A program to solve the Traveling Salesman Problem was written on a BBN Butterfly multiprocessor to empirically demonstrate the credibility of this theoretical analysis. Finally, we note that similar analyses can be applied to evaluate parallel AI systems in which processes communicate through a shared global database.
- Numerical Mathematics