[r-t] 147 TDMM
mark at snowtiger.net
Tue Oct 5 22:56:40 UTC 2010
> However in this
> case, the total time spent doing linkage searches was less
> than the total time spent doing plan generation. So there
> didn't seem any point in running multiple linkage processes.
Ah, missed that, yes good point.
> Parallelizing a tree search isn't as bad as you
> suggest -- you start by exploring the tree to depth N (a
> small number, probably 2 for the TDMM search I did), and
> store all branches in a list.
Yes, it's do-able. I think you should queue up branches and allocate
them to threads as they become free. In general you need a cleverer way
to spot the depth at which you fork, though. Too shallow and you can't
keep enough threads busy, or you end up with one thread finishing the
search way after the others. Too deep, and you start to worry about
overhead copying the false tables, etc. The effective depth is also
massively affected by the prefix if using a rotational search!
So a few things to think about, for a generic algorithm anyway. It's
nice to have an algorithm which is inherently parallel, like the "plan
More information about the ringing-theory