Author: Robert Hyatt
Date: 17:56:56 12/23/99
Go up one level in this thread
On December 23, 1999 at 17:18:18, José de Jesús García Ruvalcaba wrote: >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? Dynamic Tree Splitting. Although that doesn't say an awful lot about the algorithm, which was the topic of my Ph.D. dissertation...
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.