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

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
May 01, 1987
Accession Number
ADA184246

Entities

People

  • Larry S. Davis
  • Shie-rei Huang

Organizations

  • University of Maryland

Tags

Communities of Interest

  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Algorithms
  • Automation
  • Classification
  • Contracts
  • Databases
  • Decomposition
  • Engineers
  • Equations
  • Iterations
  • Lepidoptera
  • Maryland
  • Multiprocessors
  • Saturation
  • Security
  • Test And Evaluation
  • Trees (Data Structures)
  • Universities

Fields of Study

  • Computer science

Readers

  • Operations Research
  • Parallel and Distributed Computing.

Technology Areas

  • AI & ML
  • AI & ML - Bayesian Inference
  • AI & ML - Machine Learning Algorithms