On Tue, 2008-08-12 at 18:18 +0200, Gian-Carlo Pascutto wrote:
> Don Dailey wrote:
>
> > We need to define terms so we don't end up arguing about something we
> > probably agree on.
> >
> > Here is my assertion (which I admit needs to be checked):
> >
> > Given perfect move ordering, but not a-priori knowledge of this, a
> > parallel program will search more nodes on average than a serial
> > program. And more processors will "waste" more work in this sense.
> > That's my definition of "wasted work."
> >
> > I'm sure there are also synchronization issues and other overheads, but
> > let's just deal with the tree size. I think you agree with this, but
> > I'm not sure.
>
> I disagree with it. The system you mentioned earlier (YBWC or Jamboree
> search) would work fine here in avoiding any unnecessary work. The fact
> that you don't know for sure in advance that the tree is perfectly
> ordered does not actually change anything, since you work from the
> assumption that it is anyway (that's even true in practise!).
>
> You simply always split after you have searched the first move. In a
> perfectly ordered tree, there will be no beta cuts and no alpha updates,
> so there will be no wasted work. But there will also be no perfect
> scaling because of critical tree issues.
I found what I was looking for. The article you need to look at is
called "The StarTech Massively Parallel Chess Program" by Bradley
Kuszmaul and there are formula's for predicting the performance of a
chess program given N processors.
Here is an important snippet, but proofs follow in the paper:
The critical path length C is the time it would take for the
program to run on an infinite-processor machine with no
scheduling overheads.
The paper goes on with an analysis of how much parallelism exists in
perfectly ordered trees, a stupid analysis if it's always 100% as you
believe.
Anyway, I'm only going into this because you challenged my statement
that parallel chess programs do extra work (which is clearly the case in
a practical sense and now we see is true theoretically as well.)
Now it's possible the paper is flawed - I don't believe everything I
read. If you can show that you probably could write your own paper
exposing the flaw.
- Don
>
> This system will work reasonably well on a real, non-perfectly ordered
> tree, and will not waste work in a perfectly ordered one.
>
> (All assuming no hashtables)
>
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
