Halton序列并行加速与优化
|
摘要
Halton序列内部算法相关性复杂,生成大数量级的Halton序列耗时巨大,不利于实时性研究。针对该状况,提出在"天河二号"超算平台下的Halton序列并行加速方案,利用OpenMP实现多线程并行,在此基础上优化Halton序列生成过程,减少空间存储度以及并行通讯开销,提高生成速率。实验结果表明,通过"天河二号"超算平台上多线程并行加速,加速倍数可达22.2842倍。
The internal algorithms of the Halton sequence is highly correlated,and it is time consuming to generate large-order Halton sequences,which is not conductive to real-time research.In view of this situation,Halton sequential parallel acceleration scheme under Tianhe II supercomputer platform was proposed.OpenMP was used to implement multi-threaded parallelism.On this basis,the Halton sequence generation process was optimized to reduce the spatial storage and parallel communication overhead while increasing the rate of generation.Experimental results show that the speedup can reach 22.2842 times through parallel execution of multiple threads on Tianhe II supercomputer platform.
The internal algorithms of the Halton sequence is highly correlated,and it is time consuming to generate large-order Halton sequences,which is not conductive to real-time research.In view of this situation,Halton sequential parallel acceleration scheme under Tianhe II supercomputer platform was proposed.OpenMP was used to implement multi-threaded parallelism.On this basis,the Halton sequence generation process was optimized to reduce the spatial storage and parallel communication overhead while increasing the rate of generation.Experimental results show that the speedup can reach 22.2842 times through parallel execution of multiple threads on Tianhe II supercomputer platform.
引文
[1]SHI Nannan,ZHU Lichao.Comparison of different Halton sampling methods in mixed Logit model[J].Journal of Wuhan University of Technology(Transportation Science and Engineering),2016,40(5):913-918(in Chinese).[史楠楠,诸立超.不同Halton抽样方法在混合Logit模型中的比较[J].武汉理工大学学报(交通科学与工程版),2016,40(5):913-918.]
[2]XIONG Lijun,WU Yu,QIAN Kechang,et al.Functional extreme value search method based on Halden’s low-bias sequence[J].Guangxi Sciences,2013,20(1):9-11(in Chinese).[熊李军,武昱,钱克昌,等.基于低偏差序列Halton的函数极值搜索方法[J].广西科学,2013,20(1):9-11.]
[3]WANG Juan,LI Rui,WANG Chunzhi.Biprobit model estimation and application of panel data based on Halton sequences[J].Mathematics in Practice and Theory,2015,45(24):87-95(in Chinese).[王娟,李锐,王春枝.基于Halton序列的面板数据Biprobit模型估计及应用[J].数学的实践与认识,2015,45(24):87-95.]
[4]LIN Xiaochun.“Tianhe II”won the global super-computing six consecutive champions[J].Modern Enterprise,2015(11):40(in Chinese).[林小春.“天河二号”获全球超算六连冠[J].现代企业,2015(11):40.]
[5]ZHU Yehua.“Tianhe II”helps to explore dark matter[J].Science&Technology Review,2016,34(5):38-39(in Chinese).[祝叶华.“天河二号”助力探寻暗物质[J].科技导报,2016,34(5):38-39.]
[6]FANG Xiang,LI Ningqiu,FU Xiaozhe,et al.Construction of aquatic pathogen information analysis platform based on“Tianhe 2”and its application in analysis of aquatic pathogens[J].Heritage,2015,37(7):702-710(in Chinese).[方翔,李宁求,付小哲,等.基于“天河二号”的水产病原生物信息分析平台构建及其在水产病原分析中的应用[J].遗传,2015,37(7):702-710.]
[7]Paul Glasserman.Monte carlo methods in financial engineering[M].FAN Shaohua,SUN Wujun,transl.1st ed.Beijing:Higher Education Press,2013:278-282(in Chinese).[Paul Glasserman.金融工程中的蒙特卡罗方法[M].范韶华,孙武军,译.1版.北京:高等教育出版社,2013:278-282.]
[8]Weerasinghe G,Chi H,Cao Y.Particle swarm optimization simulation via optimal halton sequences[J].Procedia Computer Science,2016,80:772-781.
[9]Brandolini L,Colzani L,Gigante G,et al.Low-discrepancy sequences for piecewise smooth functions on the two-dimensional torus[J].Journal of Complexity,2016,33:1-13.
[10]Wang Menghan,Yue Zongmin,Meng Lie.Optimization of process parameters for cracking prevention of UHSS in hot stamping based on hammersley sequence sampling and back propagation neural network-genetic algorithm mixed methods[J].Journal of Harbin Institute of Technology,2016,23(2):31-39.
[11]He ZA,Ma C.Improved artificial bee colony algorithm with randomized Halton sequence[C]//IEEE International Conference on Computer and Communications.IEEE,2017:1270-1273.
[12]Gurov T,Karaivanova A,Alexandrov V.Energy study of monte carlo and quasi-Monte Carlo algorithms for solving integral equations[J].Procedia Computer Science,2016,80:1897-1905.
[13]Drmota M,Hofer R,Larcher G.On the discrepancy of Halton-Kronecker sequences[M]//Number Theory-Diophantine Problems,Uniform Distribution and Applications.Springer International Publishing,2017.
[2]XIONG Lijun,WU Yu,QIAN Kechang,et al.Functional extreme value search method based on Halden’s low-bias sequence[J].Guangxi Sciences,2013,20(1):9-11(in Chinese).[熊李军,武昱,钱克昌,等.基于低偏差序列Halton的函数极值搜索方法[J].广西科学,2013,20(1):9-11.]
[3]WANG Juan,LI Rui,WANG Chunzhi.Biprobit model estimation and application of panel data based on Halton sequences[J].Mathematics in Practice and Theory,2015,45(24):87-95(in Chinese).[王娟,李锐,王春枝.基于Halton序列的面板数据Biprobit模型估计及应用[J].数学的实践与认识,2015,45(24):87-95.]
[4]LIN Xiaochun.“Tianhe II”won the global super-computing six consecutive champions[J].Modern Enterprise,2015(11):40(in Chinese).[林小春.“天河二号”获全球超算六连冠[J].现代企业,2015(11):40.]
[5]ZHU Yehua.“Tianhe II”helps to explore dark matter[J].Science&Technology Review,2016,34(5):38-39(in Chinese).[祝叶华.“天河二号”助力探寻暗物质[J].科技导报,2016,34(5):38-39.]
[6]FANG Xiang,LI Ningqiu,FU Xiaozhe,et al.Construction of aquatic pathogen information analysis platform based on“Tianhe 2”and its application in analysis of aquatic pathogens[J].Heritage,2015,37(7):702-710(in Chinese).[方翔,李宁求,付小哲,等.基于“天河二号”的水产病原生物信息分析平台构建及其在水产病原分析中的应用[J].遗传,2015,37(7):702-710.]
[7]Paul Glasserman.Monte carlo methods in financial engineering[M].FAN Shaohua,SUN Wujun,transl.1st ed.Beijing:Higher Education Press,2013:278-282(in Chinese).[Paul Glasserman.金融工程中的蒙特卡罗方法[M].范韶华,孙武军,译.1版.北京:高等教育出版社,2013:278-282.]
[8]Weerasinghe G,Chi H,Cao Y.Particle swarm optimization simulation via optimal halton sequences[J].Procedia Computer Science,2016,80:772-781.
[9]Brandolini L,Colzani L,Gigante G,et al.Low-discrepancy sequences for piecewise smooth functions on the two-dimensional torus[J].Journal of Complexity,2016,33:1-13.
[10]Wang Menghan,Yue Zongmin,Meng Lie.Optimization of process parameters for cracking prevention of UHSS in hot stamping based on hammersley sequence sampling and back propagation neural network-genetic algorithm mixed methods[J].Journal of Harbin Institute of Technology,2016,23(2):31-39.
[11]He ZA,Ma C.Improved artificial bee colony algorithm with randomized Halton sequence[C]//IEEE International Conference on Computer and Communications.IEEE,2017:1270-1273.
[12]Gurov T,Karaivanova A,Alexandrov V.Energy study of monte carlo and quasi-Monte Carlo algorithms for solving integral equations[J].Procedia Computer Science,2016,80:1897-1905.
[13]Drmota M,Hofer R,Larcher G.On the discrepancy of Halton-Kronecker sequences[M]//Number Theory-Diophantine Problems,Uniform Distribution and Applications.Springer International Publishing,2017.