Author: Robert Hyatt
Date: 13:46:32 12/23/99
Go up one level in this thread
On December 23, 1999 at 14:59:52, José de Jesús García Ruvalcaba wrote: >On December 23, 1999 at 14:53:16, Robert Hyatt wrote: > >>On December 23, 1999 at 14:43:33, José de Jesús García Ruvalcaba wrote: >> >>>On December 22, 1999 at 18:37:16, Robert Hyatt wrote: >>> >>>>On December 22, 1999 at 17:38:27, José de Jesús García Ruvalcaba wrote: >>>> >>>>>On December 21, 1999 at 17:44:06, Robert Hyatt wrote: >>>>> >>>>>[big snip] >>>>>> >>>>>>Also, chess is _far_ from "embarassingly parallel". It is one of the more >>>>>>difficult-to-program parallel algorithms, because alpha/beta is a strictly >>>>>>defined sequential algorithm. Doing it in parallel invites a lot of extra >>>>>>work that can't be avoided. >>>>>> >>>>>[big snip] >>>>> >>>>> I was just about to begin a new thread asking "is there a quick and dirty way >>>>>of parallelizing a chess search?". By your post I guess that the answer is "no". >>>>>José. >>>> >>>> >>>>There are "quick and dirty" ways to do it. But they don't produce what would be >>>>called stellar performance... >>>> >>>>unfortunately... :) >>> >>> Where can I find about those 'quick and dirty' ways? Poor performance was to be >>>expected, of course. >>>José. >> >> >>The simplest idea is "young brothers wait" which has been around in various >>forms since 1980. It is still non-trivial to handle the locking and potential >>race conditions... but it is not terribily difficult to get up and going. > >Did you use it in 1983 Cray Blitz? Cray Blitz went like this: 1983 (first parallel version, completed in 2 weeks when cray surprised us with a working dual cpu XMP) we split at the root only. Typical performance was maybe 1.5x faster in good cases, no faster in some. 1984 saw "PVS" come along (principle variation splitting, not to be confused with todays "PVS" serial search (principle variation search). This was harder, but all processors stayed together at the same node in the tree, so it wasn't too hard. Next (1985) came an enhanced version that eliminated a lot of idle waiting. And finally (1988) I finished DTS which was about as good as can be done, but _very_ complicated. It took me over one year of _full time_ work to debug the thing after I had finished the coding. And I still found a bug here and there every time we played. The current search in Crafty is not as good as DTS, but it is better than the other approaches I used. The main thing I do is that there is very little time where one processor is spent waiting on another for anything...
This page took 0.01 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.