[r-t] 147 TDMM

[Mark Davies]

RAS writes,

> 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 
search".

MBD