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

PARALLEL DESIGN AND PERFORMANCE ANALYSIS OF MARKOV CHAIN MONTE CARLO ALGORITHM

作　　者：周玉科[1] 刘建文 王妍[3] 

机构地区：[1]中国科学院地理科学与资源研究所生态系统网络观测与模拟重点实验室,北京100101 [2]福州大学空间信息工程研究中心数据挖掘与信息共享教育部重点实验室,福建福州350116 [3]中国水利水电科学研究院流域水循环模拟与调控国家重点实验室,北京100434

出　　处：《计算机应用与软件》2017年第12期250-255,272,共7页Computer Applications and Software

基　　金：国家自然科学基金项目(41601478);国家重点研发计划项目(2016YFC0500103);中科院STS项目(KFJ-SW-STS-167);中科院地理资源所青年启动基金;资源与环境信息系统国家重点实际室开放基金项目(2016)

摘　　要：马尔科夫链蒙特卡洛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.

关 键 词：马尔可夫链蒙特卡洛算法 分治法则 多核计算 共享内存 加速性能 

分 类 号：TP3[自动化与计算机技术—计算机科学与技术]