Author: Robert Hyatt
Date: 11:52:21 02/26/04
Go up one level in this thread
On February 26, 2004 at 12:06:10, Anthony Cozzie wrote: >On February 26, 2004 at 11:18:07, Charles Roberson wrote: > >> >> 30 years ago, I spent time working for tobacco farmers. I dislike smoking of >>any kind but it was the only job in town. There were several things that we did >>that easily applies to parallel algorithms. These methods were all in how to >>help out the slower people and getting the field primed faster. >> >> All rows were not of uniform length -- the fields had curved boundaries. >> So, here were some of the things we tried. >> 1) When the fastest person finishes, he helps the next person closest to >> finishing. Then, those two help the next person closest to finishing and >> so on .... >> >> Variation: When the #2 person is finished the two leaders help split >> their help across persons 3 and 4. Then the 4 split their >> help across persons 5,6,7,8. >> >> Once we had two or more helping the others "out". The >> fastest person helps the person farthest behind and so on. >> >> 2) When the first person finishes, he helps "out" the person the most >> behind. Then second person out helps the new person the most behind. >> If the person originaly farthest behind is not the second "out" due to >> the help. The two split efforts to help the most behind. >> >> >> Now, which was the most effective and which did the farmers like the most? >> #1 was the most effective and most liked by the farmer. >> >> Why? >> 1) it made it very clear who were the slackers. (an issue with comps??) >> 2) the slackers were often taught better techniques and thus sometimes. >> if they still didn't improve they weren't rehired. >> 3) it was better for morale -- the good received some amount of help but >> so did the bad. Also, the best performers did not do too much extra >> work. >> >> Now, how does this apply to comps. Are there slackers? Yes, what about >> distributed systems with different speed processors. >> >> The first algorithm reminds me of Young Brothers Wait -- the last nodes >> helped are the ones move ordering designates as least best. >> >> The second algorithm reminds me of Bob's paper on DTS or any other work >> stealing approach. > >I don't think DTS really suggested a split strategy (other than split at ALL >nodes if possible). Bob's paper is more, "how can we design a parallel >structure so that we can split anywhere in the tree". Once you have a working >DTS implementation, you can split however you want . . . > >anthony Correct. The "where do I split" code was changed many times _after_ the DTS paper was done. The issue however, was "how can I design a search so that I can split wherever and whenever I want, assuming I can find a good way to choose such a split point?" I am going to write up the current Crafty algorithm once I finish the hash collision study and paper, as it is time to explain what I am doing, as it is actually a reasonably effective parallel search, and produces reasonable performance, without the DTS requirement of throwing the recursive negamax search out the window and replacing it with an iterated search using lots of arrays for local data for each ply. The current idea is pretty simple, but of course the data structures get pretty deep when the tree can be recursively sub-divided many times along a single path. I'll be careful to explain exactly how the data structures work to make this effective.
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.