Author: Uri Blass
Date: 14:04:21 01/01/06
Go up one level in this thread
On January 01, 2006 at 14:48:30, Charles Roberson wrote: > > I beleive what you are suggesting has been well researched. > If you split things up in a simple nonsharing divide and conquer > method as it seems you suggest, the threaded algorithm is likely > to take longer than the single thread algorithm. > > Why? Beacuase you are not sharing bounds information. I did not suggest not to share information for long time but only for limited time. I also do not think that it is simple to program it and my intuition tell me that it is more complicated than normal parallel search because you need to store information in some local hash and copy it to global hash later when you may do it one times for 40,000 nodes(or something like that). My idea is that different threads probe the global hash tables but do not store information in the global hash tables before they finish their small task. The small task may be something like search 10,000 nodes or finish what you do(what comes first). hash tables still can be used for pruning and only the information from the last 30,000 nodes or less than it of the other threads may not be available for pruning(when the threads finish their tasks they may share this information by copying them from local hash to the global hash). So, a thread > gets a portion of the search tree and does not find in that portion > a bound as good as one found in another portion. Also, nearly all of the > values in that portion of the tree maybe be so close in value that > virtually no prunning happens. > > This type of idea can easily be experimented with using a simple > branch and bound algorithm on a nonlinear multidimensional problem. > If branch and bound is used and you share the bound information, one > can achieve superlinear speedups. Without sharing, you can actually > get a slow down. > > You say you lack experience/understanding of multithreading. I suggest > starting with a mathematical optimization problem and then applying a > branch and bound algorithm to it. Then experiment with several methods > of multithreading the branch and bound algorithm. You should see results > in the range that I have described. I admit that I do not understand the last part. I do not know nothing about using multithreading not in chess programs and even in chess programs I know almost nothing about it but it is clear to me that the threads have tasks to do and that they use the global hash tables so dividing big tasks in a deterministic way to small tasks and later learn everything possible thing from the results of the small tasks to continue seem to me logical. There is some loss of information that may prevent more efficient pruning but my intuition tell me that information from the last nodes of other threads is usually not very important because if 10,000,000 nodes already were searched the probability that the next 30,000 nodes in threads a,b,c are going to give important information for pruning the 10,000 nodes in thread d is small because in most cases threads a,b,c are going to search clearly different branches than the branch that thread d searches. Uri
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.