Author: Charles Roberson
Date: 11:48:30 01/01/06
Go up one level in this thread
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. 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.
This page took 0.01 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.