Computational experiments with an asynchronous parallel branch and bound algorithm
January 1989
Research Paper
| Related Files |
|---|
View PDF Version
(eur-few-cs-89-02.pdf, 0.1MB) |
In this paper we present an asynchronous branch and bound algorithm for execution on an MIMD system, state sufficient conditions to prevent the parallelism from degrading the performance of this algorithm, and investigate the consequences of having the algorithm executed by nonhomogeneous processing elements. We introduce the notions of perfect parallel time and achieved efficiency to empirically measure the effects of parallelism, because the traditional notions of speedup and processor utilization are not adequate for fully characterizing the actual execution of an asynchronous parallel branch and bound algorithm. Finally we present some computational results obtained for the symmetric traveling salesman problem.
Keywords
- branch and bound
- traveling salesman problem
- asynchronicity
- nondeterminism
- MIMD
- loosely coupled system
- parallel computer
Automatically Extracted Terms
- algorithm
- process
- subproblem
- problem
- slave
- branch
- execution
- boulder algorithm
- slave process
- processing
- master
- element
- processing elements
- pyramid
- number
- program
- master process
- instance
- machine
- anomaly
