[r-t] 147 TDMM

[Richard Smith]

Mark Davies wrote:

> That raises an important question - did you make use of 
> multi-threading in any stage of your search?

Not multi-threading per se.  That's mostly due to laziness. 
The first stage (generating plans) is basically a tree 
search.  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.  Then each thread takes a 
branch and uses it as a prefix for the main tree search. 
I've done proof-of-concept searches like this, and it seems 
to work well.  (Yes, you often get one branch taking a lot 
longer than the others, but if you choose the initial branch 
depth appropriately, you rarely get one branch taking a lot 
longer than all the others put together.)

The reason I've not used this in any real searches is that 
there are quite a few bits of code that I haven't yet got 
around to making thread-safe.

> It strikes me the whole algorithm is inherently 
> parallizable - as soon as the first pass has produced the 
> first plan, you can start a linkage search on it; spawn a 
> thread for each plan you create, in fact.

Actually, I used a separate process for the second (linkage) 
stage.  Each linkage process would act on one or more plan 
file.  That would allow me to parallelize further by having 
multiple machines doing the linkage search.  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.

RAS