Author: James Swafford
Date: 11:02:40 08/25/05
Go up one level in this thread
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
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.