Tight upper bound for the speed-up of parallel best-first branch-and-bound algorithms. Technical report
Shi-Lun Huang, L.S. Davis · OSTI OAI (U.S. Department of Energy Office of Scientific and Technical Information) · 1987
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, it is noted that similar analyses can be applied to evaluate parallel AI systems in which processes communicate through a shared global database.