Xu & Ihler @ AISTATS 2011 multicore Gibbs sampling in graphs

Multicore computing is on the rise, but algorithms such as Gibbs sampling are
fundamentally sequential and may require close consideration to be made
parallel. Existing techniques either exploit sparse problem structure or make
approximations to the algorithm; in this work, we explore an alternative to
these ideas. We develop a parallel Gibbs sampling algorithm for shared-memory
systems that does not require any independence structure among the variables yet
does not approximate the sampling distributions. Our method uses a look-ahead
sampler, which uses bounds to attempt to sample variables before the results of
other threads are made available. We demonstrate our algorithm on Gibbs sampling
in Boltzmann machines and latent Dirichlet allocation (LDA). We show in
experiments that our algorithm achieves near linear speed-up in the number of
cores, is faster than existing exact samplers, and is nearly as fast as
approximate samplers while maintaining the correct stationary distribution.