Affordable Access

Parallel branch and bound on an MIMD system

  • Computer Science


In this paper we give a classification of parallel branch and bound algorithms and develop a class of asynchronous branch and bound algorithms for execution on an MIMD system. We develop sufficient conditions to prevent the anomalies that can occur due to the parallelism, the asynchronicity or the nondeterminism, from degrading the performance of the algorithm. Such conditions were known already for the synchronous case. It turns out that these conditions are sufficient for asynchronous algorithms as well. We also investigate the consequences of nonhomogeneous processing elements in a parallel computer system. 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 efficiency are not capable of fully characterizing the actual execution of an asynchronous parallel algorithm. Finally we present some computational results obtained for the symmetric traveling salesman problem

There are no comments yet on this publication. Be the first to share your thoughts.


Seen <100 times

More articles like this

An MIMD parallel computer system

on Computer Physics Communication... Jan 01, 1982

Sorting on an MIMD-type parallel processing system

on Euromicro Newsletter Jan 01, 1978

Experiments in mimd parallelism

on Future Generation Computer Sys... Jan 01, 1990
More articles like this..