[r-t] 147 TDMM
richard at ex-parrot.com
Tue Oct 5 14:24:51 UTC 2010
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.
More information about the ringing-theory