Author: Robert Hyatt
Date: 11:41:07 08/25/05
Go up one level in this thread
On August 25, 2005 at 14:02:40, James Swafford wrote: >On August 24, 2005 at 23:22:50, Robert Hyatt wrote: > >>On August 24, 2005 at 22:23:11, James Swafford wrote: >> >>> >>>I'm sure most parallel searchers use algorithms that allow splitting >>>at arbitrary nodes in the tree. I'm curious how good (or bad!) >>>it would be to simply spawn threads at the root to search an entire >>>move. >>> >>>In other words, if I have 4 processors, then I would have 4 search >>>threads running, each searching a different root move. >> >>Here's an assignment. Take your favorite program, and set up a middlegame >>position. Let it start searching. When an iteration takes at least a minute, >>pay careful attention, and watch your time when it starts the next iteration. >>Watch carefully and notice when it pops up a score for the first move and goes >>on to the next move. Then watch carefully until that iteration ends. >> >>Here is the question. >> >>You have three times. >> >>time(iteration start) >>time(first score displayed) >>time(iteration ended) >> >>look at the difference between the first two, and compare that to the difference >>between the last two divided by #legal_moves-1... >> >>You will note that the first move takes _way_ more time than all the other moves >>combined. now guess what happens when you search the second-best move first? >>It takes as long as the first move. And then guess how long the first move >>takes? Same time it took before. >> >>Bottom line is that this only gives you a very tiny speedup. Maybe 1.5X if you >>are lucky. We used this in the very first parallel search we did. Because we >>had no time to develop something better for that ACM event. It was not good. >> >>Even worse, what about positions where you just have one or two legal moves? :) >> >> >>> >>> Yes, I know that's incredibly simplistic. I'm just curious as to >>>how the naive approach compares to something more complex. >> >>Poorly. _very_ poorly. :) >> >> >>> >>>Thanks, >>>-- >>>James > > >Would you briefly describe how you make the decision to split, >or direct me to a paper? > >I'm not that concerned with the mechanics of splitting (I suppose >you just fork() and use locks to protect global data structures)... >I'm more interested in the *where* at this point. > >-- >James The where is pretty easy. I can split at _any_ ply where both of the following conditions are true: 1. there is at least one idle processor; 2. I have completely searched at least one move at the current ply. This is known as the "young brothers wait" condition...
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.