Author: Don Dailey
Date: 17:27:54 01/26/98
Go up one level in this thread
On January 26, 1998 at 07:05:23, Rickard Björklund wrote: >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 Hi Rickard, Splitting the window up is highly speculative and is not likely to pay off. I remember seeing an article years ago that also talked about this method and the conclusion was not encouraging. We have versions of cilk that run on distributed memory systems. If you use global hash tables you might want to use message passing. We usually run on SMP's with shared memory but we can run on virtually anything available. We once ran on 1,836 i860's with Cilk. All the scheduling details are handled by Cilk but you decide where work is spawned, synced or aborted. The mechanisms are simple and natural for chess. As I've mentioned before, Cilk was practically designed for chess. I have some psuedo code I posted a few days ago which shows clearly how we do it. Cilk basically is C with a few features added. We have a device called an "inlet" which can see return results without waiting for syncronization. This allows us to abort work when beta cutoffs happen. In short you should have no trouble programming with Cilk and it's available for several platforms. We have not yet done a Window's NT port but are looking into it. - Don
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.