马尔科夫链蒙特卡洛算法并行化设计与性能分析

PARALLEL DESIGN AND PERFORMANCE ANALYSIS OF MARKOV CHAIN MONTE CARLO ALGORITHM

马尔科夫链蒙特卡洛MCMC(Markov Chain Monte Carlo)算法广泛应用于地球系统模型中参数不确定性分析和模拟。由于地球环境科学数据的高维度、大容量特性,迫切需求高性能的MCMC算法满足应用需求。采用数据分治法实现该算法的多核并行化。利用静态和动态分配策略将算法中的多个输入链分配到各CPU;独立计算并通过共享内存实现进程间通信;主进程回收各单元计算结果,合成最终的马尔可夫链输出矩阵。采用控制变量法分析不同样本和马尔可夫链数量下的算法加速情况。结果表明在计算规模较大、动态负载均衡的条件下易于获得较好的加速比,在4个CPU以内时效果显著,之后随着CPU增加加速效果出现波动或趋于稳定。研究表明并行化MCMC能够利用多核CPU硬件设施获得加速效果,更多核数的加速性能存在进一步优化的空间。

Markov chain Monte Carlo （MCMC） algorithm is widely used in the uncertain analysis and simulation of model parameters in the domain of earth system science. Due to the high dimension and high volume characteristic of earth environment data, it is urgent to develop a high performance version of MCMC algorithm. In this paper, we used the data ＇divide and conquer＇ strategy to convert the classic MCMC to a multi-core parallel method. Firstly, the input Markov chains were assigned to multiple CPU cores using static or dynamic load balance plan. Secondly, every standalone core computed the Markov chains assigned by the main process, and the communication between the cores was realized through the sharing memory in the computer. Finally, the main process collected the output Markov chains from every CPU core and aggregated to a Markov chains matrix. The speedup of this parallel MCMC method was tested by selecting different sample size and input Markov chains number. The results indicated that the parallel MCMC got better speedup performance when given more computing task to the CPU cores, as well as using a dynamic load balance plan when assigned the task to every CPU core. This study showed that parallel version of MCMC method could fully use the hardware of modern computer to obtain acceleration. In our future work, the speedup in the case of more than 4 CPU cores would be further optimized.