Can ClonalFrameML be parallelized in any way?

[tseemann]

If I understand correctly, CFML is single threaded?
Is it possible to parallelize / SMP it?
It's currently a bottleneck in all our analyses.
I might be able to invest time in this if you think OpenMP (threads) could help.
@andersgs

[xavierdidelot]

Hi Torsten,
Yes ClonalFrameML does not currently use any form of parallel computing. Implementing this would definitely cut down the running time, but I think it's not trivial. Most of the time is spent in the Baum-Welch algorithm which determines the key parameters such as recombination rate and branch lengths. The function implementing this starts on line 2162 of the main.cpp file and I suspect this is the bottleneck in your analyses, although it would be good to check with profiling. It seems that in the Hidden Markov Chain literature some solutions have been proposed to parallelise the Baum-Welch algorithm, and this might be a good starting point.

[tseemann]

I recompiled and linked using -pg, ran it on 5 x 100,000 and ran gprof on the gmon.out file.

  % time
 79.04      5.43     5.43      175     0.03     0.04  mydouble_forward_backward_expectations_ClonalFrame_branch(int, int, myutils::Matrix<Nucleotide> const&, std::vector<double, std::alloc>
 13.83      6.38     0.95 35000000     0.00     0.00  mydouble::operator+(mydouble const&) const

mydouble is your class, kept in log-space, to avoid overflows, so I guess adding in log space is a PITA.

[tseemann]

https://firebb.github.io/parahmm/

We achieved a total speed up of 75.63X and 56.99X over the best singled threaded baseline for Forward algorithm and Baum-Welch Training Algorithm using 16 threads on the GHC machine with AVX instructions.

[xavierdidelot]

Thanks for your comments and sorry for the delayed answer due to the Summer holiday. Your profiling confirms that it is indeed the HMM algorithm that takes most of the time as expected. parahmm may be exactly what's needed, and I hope to look into it further when I get a chance, although I don't know when that will be. Let's leave this issue open as a reminder (-:

[dustinlong]

Similar bottleneck in a pipeline we are developing and wanted to express additional interest in multithreading. Torsten, has the parahmm solution continued to work well for you? Many thanks.

[bede]

Just a +1 for a parallelised HMM

[edsonmachado]

Just one more...
Best!

[shaul-pollak]

+1!
Also, (importantly!) thanks for this amazing tool

[jianshu93]

hello All,

Just one more!

Parallelize it would be very useful.

Jianshu

[sbenvari]

one more