  Computational intensity and sequential nature of estimation techniques for
Bayesian methods in statistics and machine learning, combined with their
increasing applications for big data analytics, necessitate both the
identification of potential opportunities to parallelize techniques such as
MCMC sampling, and the development of general strategies for mapping such
parallel algorithms to modern CPUs in order to elicit the performance up the
compute-based and/or memory-based hardware limits. Two opportunities for
Single-Instruction Multiple-Data (SIMD) parallelization of MCMC sampling for
probabilistic graphical models are presented. In exchangeable models with many
observations such as Bayesian Generalized Linear Models, child-node
contributions to the conditional posterior of each node can be calculated
concurrently. In undirected graphs with discrete nodes, concurrent sampling of
conditionally-independent nodes can be transformed into a SIMD form.
High-performance libraries with multi-threading and vectorization capabilities
can be readily applied to such SIMD opportunities to gain decent speedup, while
a series of high-level source-code and runtime modifications provide further
performance boost by reducing parallelization overhead and increasing data
locality for NUMA architectures. For big-data Bayesian GLM graphs, the
end-result is a routine for evaluating the conditional posterior and its
gradient vector that is 5 times faster than a naive implementation using
(built-in) multi-threaded Intel MKL BLAS, and reaches within the striking
distance of the memory-bandwidth-induced hardware limit. The proposed
optimization strategies improve the scaling of performance with number of cores
and width of vector units (applicable to many-core SIMD processors such as
Intel Xeon Phi and GPUs), resulting in cost-effectiveness, energy efficiency,
and higher speed on multi-core x86 processors.
