Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: MTD(f) (was Re: New(?) search idea.)

Author: Rickard Björklund

Date: 04:05:23 01/26/98

Go up one level in this thread


On January 24, 1998 at 17:12:48, Don Dailey wrote:

>The parallel algorithm is extremely simple, and completely recursive.
>So parallelism can happen anywhere.  The cilk language was designed
>around chess  and huge effort went into it to make it extremely
>efficient and powerful at the same time.   The scheduling algorithm
>is automatic and makes good decisions.  When a processor steals work
>from another processor it steals the oldest work that was posted so
>most of the "sharing" will get done near the root of the tree.
>
>A lot of our parallel searches look at LESS nodes than a serial
>search.  This can happen because if
>you are looking at a bunch of sibling moves in parallel one may
>just happen to give you a very fast cutoff (like a mate sequence)
>and return quickly where the serial program may not get to that
>move for a while.   In general of course any parallel program tends
>to do more work on the average.   There are things we do to try to
>avoid extra work, if we think a cutoff will happen we do not try
>to search siblings in parallel, but wait for the result of the search.
>I usually quote numbers like 20% more work than a serial job but in
>fact this is nonsense.  The work climbs very gradually with number
>of processors and drops with depth of search.   If we had 1 billion
>processors we would have to search for a long time to get the full
>benefit.
>Our program does not play speed chess well with a lot of slow processors
>etc.
>One intersting phenomemon we had with our 1800 processor Socrates
>program is that the iteration times looked linear!  It took a second
>per iteration until we were over 10 or something.  The branching
>factor was so low.  But this was because the deeper we went, the
>more parallelism we got.  Obviously, you cannot use 1836 processors
>to efficiently do a 1 ply search!   It's like getting 1000 people
>together to mow a small yard or garden!
>

This concerns my initial question. Can't these searches be done be
dividing the window among the processors. I know this has been done
for the usual alphabeta search and that it's not efficient when using
many processors. I think parallel window splitting is useful when
you do a shallow search. I'm thinking of using the window split for the
first plies in the iterative deepening and then resort to something YBW
like.

>
>Most of this stuff is a bookkeeping nightmare.  But with Cilk they
>are very high level commands and the language keeps up with all the
>detail.   You can still control a lot of the details if you want
>to and I have experiemented a lot with various scheduling algorithms
>but this simple one get's almost all the benefit.
>
>- Don
>

I'm a writing a parallel chess program myself (right now, I'm
encapsulating
all global variables in structs), but I'm the message-passing kind of
guy, so
I don't know much about Cilk. Does Cilk run on lously coupled system ?
Does it
require shared memory ? Is it portable ?

Is the scheduler written as a part of the chess program or is it a part
of Cilk ?

Rickard





This page took 0 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.