From: Christopher Booth Newsgroups: comp.parallel Subject: Re: superlinear question Date: 19 Oct 1998 17:25:32 GMT Organization: DERA Malvern Approved: bigrigg@cs.cmu.edu Message-Id: <70fsmc$jr6$1@encore.ece.cmu.edu> Originator: bigrigg@ece.cmu.edu Randy Crawford wrote: > Superlinear speedup == (perpetual motion machine || perverse serial > implementation). This is just not true! 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. 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... Chris -- Christopher Booth, DERA Malvern, St Andrews Rd, Malvern, WR14 3PS. UK Tel:+44 (0)1684 896400 mailto:cjmb@dera.gov.uk Fax:+44 (0)1684 894389 Don't play mind games with a telepath. The views expressed above are entirely mine and do not represent the views, policy or understanding of any other person or official body. -- Articles to bigrigg+parallel@cs.cmu.edu (Admin: bigrigg@cs.cmu.edu) Archive: http://www.hensa.ac.uk/parallel/internet/usenet/comp.parallel