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.04 seconds to execute
Last modified: Thu, 07 Jul 11 08:48:38 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.