title: Multithreading Forwards/Backwards for a CRF
body: <p>I am attempting to multithread the forwards-backwards algorithm to find marginal probabilities. This will be used as a submodule for training a CRF. The below is pseudocode for the forwards segment of CRF training on a single example (sourced from <a href="https://firebb.github.io/parahmm/" rel="nofollow noreferrer">here</a>).</p>
  <pre><code>for i in 0 .. T-1:
      for j in 1 ... N:
          for k in 1 ... N:
              p = alpha[(i-1)][k] + trans[k][j] + obvs[j][i]
              alpha[i][j] = logadd(alpha[i][j], p)
  </code></pre>
  <p>My plan for using N threads (reasonable for my use case with N being at most 10) to compute columns of the alpha matrix independently, and syncing with a barrier upon completion of computing each row actually runs SLOWER than the original sequential code.</p>
  <p>I believe that the overhead of synchronization mechanisms is the root of this problem, as I am using threads from a pool and reusable barriers for all operations. Is there a better design that I should consider, or does the small size of N not justify parallelizing on computing columns of alpha?</p>