Author: José de Jesús García Ruvalcaba
Date: 14:18:18 12/23/99
Go up one level in this thread
On December 23, 1999 at 16:46:32, Robert Hyatt wrote: >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... What does 'DTS' stand for?
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.