Accession Number : ADA184246

Title :   A Tight Upper Bound for the Speed-Up of Parallel Best-First Branch-and-Bound Algorithms.

Descriptive Note : Technical rept.,

Corporate Author : MARYLAND UNIV COLLEGE PARK CENTER FOR AUTOMATION RESEARCH

Personal Author(s) : Huang,Shie-Rei ; Davis,Larry S

PDF Url : ADA184246

Report Date : May 1987

Pagination or Media Count : 26

Abstract : 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.

Descriptors :   *ALGORITHMS, *PARALLEL PROCESSING, *QUEUELING THEORY, PARALLEL ORIENTATION, SEQUENCES, DELAY, SYNCHRONIZATION(ELECTRONICS), TIGHTNESS, MODELS, POPULATION, DATA BASES, GLOBAL, SHARING, THEORY

Subject Categories : Numerical Mathematics

Distribution Statement : APPROVED FOR PUBLIC RELEASE