Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Crap statement refuted about parallel speedup (more)

Author: Robert Hyatt

Date: 12:31:09 09/19/01

Go up one level in this thread


On September 19, 2001 at 15:21:50, Robert Hyatt wrote:

>On September 19, 2001 at 10:21:44, Uri Blass wrote:
>
>>Not exactly.
>>
>>It is possible to get a speed improvement even in part of the 92% of the cases.
>>The fact that you only need the first move to get a cutoff does not prove that
>>the order of moves is optimal because it is possible that another move helps you
>>to get the cutoff faster.
>>
>>Uri
>
>
>That is certainly possible.  And it could be measured if someone wants to
>test it.  But irregardless, you _never_ want to search two moves at the same
>time if either will cause a cutoff, because _one_ is doing unnecessary work
>that is not contributing a thing to the speedup of the sequential algorithm.


I should have added more info.  here goes.

Suppose move 1 at one of these "fail high" nodes requires 100K nodes to search
it.  Suppose move 2 would only require 50K nodes.

If you search in parallel there, the first gets thru 50K  nodes before
being told to stop, because the second would have been searched after doing
50K nodes and failing high.  total nodes searched = 100K.  50K unnecessary.

If you search serially here and search the first node.  you will use the
second cpu somewhere deeper in that search, so that the 100K nodes are
searched in 1/2 the time in parallel.  You still fail high.  Total nodes
searched = 100K.  _exactly_ the same effort.  And in cases where the first
move fails high and the second does _not_ the cost goes way up.  As I do it
now, the cost doesn't change a bit.  The moral, which is well-known to parallel
alpha/beta searchers, is "never split in parallel at a node that is expected to
fail high."  That is why "Young Brothers Wait" works so well.  you have to
search the first move serially before searching the rest in parallel, to give
the first move a chance to fail high.  If the first doesn't fail high, you know
this node has a 92% probability of being a fail-low node that needs all branches
searched.

pretty good odds...



This page took 0.25 seconds to execute

Last modified: Thu, 15 Apr 21 08:11:13 -0700

Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.