From: Luc.Vereecken@chem.kuleuven.ac.be (Luc Vereecken)
Newsgroups: comp.parallel
Subject: Re: superlinear question
Date: 26 Oct 1998 20:14:51 GMT
Organization: KULeuvenNet
Approved: bigrigg@cs.cmu.edu
Message-Id: <712l7r$h7b$1@encore.ece.cmu.edu>
Originator: bigrigg@ece.cmu.edu


>Randy Crawford wrote:
>The standard serial branch and bound
>algorithm, when parallelized the obvious way, yields superlinear
>speed-up.  This is because it is virtually certain that exploring the
>best-guess branch first will sometimes be the wrong thing to do.  When
>it _is_ the wrong thing, the parallelized version will find the
>correct branch early enough to cut short pointless exploration of
>sub-optimal branches. 

This is more an issue of depth-first versus width-first (is this the
correct term in english ?). The parallel version is more a
width-first, therefore minimizing the number of less-optimal pathways
examined. The serial version is described here as a depth-first
system, with the inherent drawback that sometimes sub-optimal branches
are explored. Since the width-first requires (usually) more memory, it
is more easily implemented in parallel because (again usually) the
total amount of memory (and cache BTW) available is larger by about a
factor N.

>	Of course, if you insist on being perverse, you could
>implement a time-sliced serial branch-and-bound algorithm :-)  But
>even then the costs of context-switching on a single processor might
>mean that you could get superlinear speed-up...

There is no need of context-switching. You can program something like
that in one single program flow, eliminating superlinear speed-up. 

Luc

--
Articles to bigrigg+parallel@cs.cmu.edu (Admin: bigrigg@cs.cmu.edu)
Archive: http://www.hensa.ac.uk/parallel/internet/usenet/comp.parallel