Strid (2010) Efficient Parallelisation of Metropolis–Hastings Algorithms Using a Prefetching Approach

Summary

Strid (2010) introduces prefetching — a branch-prediction strategy that exploits parallel processors to evaluate the Metropolis-Hastings (MH) acceptance criterion at multiple future candidate states simultaneously, eliminating the serial bottleneck where each evaluation must await the previous acceptance decision. The paper derives the theoretical expected speedup $D(P)$ (expected draws per tour with $P$ processors), shows that the classical optimal acceptance rate of 0.234 is no longer optimal in parallel settings (the true optimum decreases monotonically toward zero as $P$ increases), and benchmarks five algorithm variants on a Smets-Wouters (2003) Dynamic Stochastic General Equilibrium (DSGE) model. The best variant, "most likely path," achieves a theoretical speedup of 4.99$\times$ with 7 processors and an actual cluster speedup of 5.15$\times$ with 8 processors.

Key Claims

Prefetching and the Metropolis Tree

At each iteration the MH chain must sequentially draw a candidate $\theta^*$, evaluate $\pi(\theta^*)$, and make an accept/reject decision before the next proposal can be formed. With $P$ parallel processors, prefetching speculatively evaluates the posterior at $P$ future states in parallel by building a binary Metropolis tree: at each node the chain either accepts (left branch) or rejects (right branch = current state), so $P$ nodes span all possible state trajectories. A tour of size $P$ selects a deterministic path through this tree; the expected draws per tour

$$D(P) = \sum_{p=1}^P \Pr(\text{node } p \text{ selected})$$

is the theoretical speedup over serial processing.

Five Algorithm Variants

Variant	Branch probabilities	$D(P=7)$ at $\alpha=0.25$	Notes
(1) Basic (Brockwell 2006)	All = 0.5	3.00	Lower bound; $D(P)=\log_2(P+1)$
(2) Static	Known $\alpha$; reject branches = $1-\alpha$, accept branches = $\alpha$	3.54	Best-case with constant acceptance rate
(3) Dynamic (uniform draws)	Empirical $\alpha_k = \Pr(u < X \mid u \in I_k)$ from pilot, over $K$ bins	3.81	Adapts to unknown $\alpha$ via histogram
(4) Dynamic (posterior approx.)	$\alpha \approx \min(\beta,\, p^*(\theta_\text{accept})/p^*(\theta_\text{current}))$	4.58	Uses Laplace approximation $p^* = \mathcal{N}(\theta_m, H_m^{-1})$
(5) Most likely path	Run chain $P$ steps ahead with $p^*$; non-branching tour	4.99	Best performer; inapplicable with discontinuous likelihoods

Optimal Acceptance Rate Shifts Downward with $P$

Serial MH optimum is $\alpha^\text{opt} \approx 0.234$ (Roberts-Rosenthal 2001). With prefetching the joint expected output is $E(\alpha, P) = E^1(\alpha) \times D(\alpha, P)$, where $E^1(\alpha)$ is serial efficiency and $D(\alpha,P)$ is the expected draws per tour. Because lower $\alpha$ increases the probability of long accepted-state runs (trees favoring the "left" branch), $D$ rises as $\alpha$ falls. The optimum is:

Processors $P$	$\alpha_\text{opt,P}$	Theoretical speedup
1 (serial)	0.234	1.0
3	~0.17	2.57
7	0.120	4.34
$\infty$	0	$\infty$

Independence Chain MH: Embarrassingly Parallel but Poor Mixing

The independence chain (ICMH) proposes each $\theta^*$ independently of the current state, so all proposals can be evaluated in parallel — $S(P) \approx P$ in theory. In practice for the 40-parameter Smets-Wouters model, the best ICMH achieves only 13% acceptance and an inefficiency factor ~8$\times$ worse than random-walk MH, making ICMH's parallelism advantage illusory.

Table 1: Theoretical Expected Draws per Tour (Smets-Wouters, $\alpha=0.25$)

Algorithm	P=3	P=7	P=15	P=31
Basic	2	3	4	5
Static	2.31	3.54	4.75	6.00
Dynamic (uniform)	2.38	3.81	5.04	6.24
Dynamic (post. approx)	2.57	4.58	6.45	8.04
Most likely path	2.66	4.99	7.31	8.42

Table 2: Actual Cluster Speedup (Lenngren High Performance Computing (HPC) Cluster, 8 processors)

Algorithm	$D$ (expected draws)	$S$ (actual speedup)	Serial time $\to$ Parallel time
Static P=8	3.77	3.46	80 min $\to$ 23 min
Most likely path P=8	5.39	5.15	~80 min $\to$ 15 min

Communication overhead accounts for the gap between $D$ and $S$.

DSGE Estimation Context

The one-block Random-Walk Metropolis-Hastings (RWMH) over all parameters simultaneously is standard for DSGE models because (i) the full conditional distributions are not available in closed form, (ii) blocking is difficult since drawing a subset of parameters would require solving a system of non-linear equations for each sub-block, and (iii) the Kalman filter marginalizes all latent states. Reparameterization to unbounded space improves the posterior Laplace approximation and thereby the accuracy of branch probability estimates for variants (4) and (5).

Two-Layer Parallelism

Strid (2010) also considers combining prefetching with a parallel particle filter (PPF) — the two layers can be used simultaneously. For the linearized DSGE model (Kalman filter), PPF alone already achieves the theoretical $S=P$; for nonlinear DSGE requiring a particle filter, the cross-over from PPF-alone to SP+PPF occurs at $P^*_\text{opt} = 22$ processors.

Limitations

• Practical speedup ceiling of approximately 10–15 processors; gains plateau due to the tree's logarithmic growth in $D(P)$.
• Degrades when multiple parameter blocks are updated in a single MH step.
• Most likely path is inapplicable when the likelihood is discontinuous (nonlinear DSGE with particle filter), because the Laplace approximation fails.
• Gibbs steps (acceptance rate $\alpha = 1$) are incompatible with prefetching: there is nothing to prefetch since every proposal is accepted.

Concepts Introduced or Extended

• Metropolis-Hastings Algorithm — prefetching, optimal acceptance rate under parallelism, five parallel variants
• State-Space Representation — DSGE/Kalman context for one-block MH estimation

Entities Mentioned

• Ingvar Strid

Quotes

"The most important finding is that the optimal acceptance rate for parallel computation is lower than the rule of thumb for serial computation."

"The independence chain MH is embarrassingly parallel but provides poor mixing in high-dimensional parameter spaces such as the Smets-Wouters model."

My Take

The prefetching idea is elegant and directly addresses the fundamental serial bottleneck of Markov Chain Monte Carlo (MCMC): the accept/reject decision cannot be made until the posterior evaluation completes. The theoretical framework (Metropolis tree, expected draws per tour) is clean and the key result — that $\alpha_\text{opt,P}$ decreases with $P$ — overturns received wisdom on tuning. The practical ceiling of ~5–8$\times$ speedup with 7–8 processors is modest by modern HPC standards, but the paper was written in 2010 when such speedups were meaningful. The most likely path variant, despite its name, is essentially running the chain forward using a Laplace approximation as a surrogate — conceptually close to modern surrogate-assisted MCMC. The limitations for nonlinear models (particle filter, no Laplace) are the binding constraint for modern DSGE work where nonlinear solution is increasingly standard.