Parallelizing the sampler (not the model)

[nhuurre]

The HMC sampler is inherently sequential, you need to know the previous gradient before you can decide where to evaluate the next gradient. Only a little bit of parallelism is possible, the most recent discussion is in

Within-chain parallelization idea (maybe crazy)

The recent discussion about setting expectations for reduce_sum got me thinking. Is there any chance that a more consistent speedup is available by computing the forward and backward parts of the HMC trajectory in parallel, so that whenever the tree expansion proceeds in the direction where the trajectory is so-far shorter, the work has already been done? On the negative side, this approach would throw out a non-trivial amount of integration in one direction or the other at every iteration. Ne…