基于超多核心平台的Knuth39并行化实现及性能分析

doi:10.11772/j.issn.1001-9081.2015.01.0058

计算机应用 ›› 2015, Vol. 35 ›› Issue (1): 58-61.DOI: 10.11772/j.issn.1001-9081.2015.01.0058

基于超多核心平台的Knuth39并行化实现及性能分析

张保东¹, 周津羽², 刘逍^1,2, 华诚², 周晓辉^1,2

1. 西安邮电大学计算机学院, 西安710121;
2. 陕西省高性能计算研究中心并行计算实验室, 西安710121

收稿日期:2014-08-06 修回日期:2014-09-23 发布日期:2015-01-26 出版日期:2015-01-01
通讯作者: 周晓辉
作者简介:张保东(1990-),男,山西晋城人,硕士研究生,主要研究方向:高性能计算;周津羽(1976-),男,北京人,研究员,主要研究方向:高性能计算、大数据;刘逍(1988-),男,山东文登人,硕士研究生,主要研究方向:高性能计算、自然语言处理;华诚(1987-),男,安徽桐城人,工程师,主要研究方向:金融计算、高性能计算;周晓辉(1978-),男,山东济南人,教授,博士,主要研究方向:高性能计算、大数据.
基金资助:
陕西省自然科学基础研究计划项目(2013JM8028).

Implementation and performance analysis of Knuth39 parallelization based on many integrated core platform

ZHANG Baodong¹, ZHOU Jinyu², LIU Xiao^1,2, HUA Cheng², ZHOU Xiaohui^1,2

1. School of Computer Science and Technology, Xi'an University of Posts and Telecommunications, Xi'an Shaanxi 710121, China;
2. Parallel Computing Laboratory, Shaanxi Research Center for High Performance Computing, Xi'an Shaanxi 710121, China

Received:2014-08-06 Revised:2014-09-23 Online:2015-01-26 Published:2015-01-01

摘要/Abstract

摘要：

针对Knuth39随机数发生器运行速度慢的问题,提出了一种基于超多核心(MIC)平台的Knuth39并行化方法.首先,将Knuth39发生器的随机数序列以固定间隔划分成多个子序列;然后,每个线程从各子序列的起点开始生成随机数;最后,将各个线程生成的随机数序列组合成最终的序列.实验结果表明,并行化后Knuth39通过了TestU01的452项测试,与串行程序相同.同中央处理器(CPU)单线程相比,并行化后MIC平台下的最优加速比可达到15.69倍.所提方法有效地提高了Knuth39发生器的运行速度,并且保证了生成序列的随机性,更加适用于高性能计算领域.

关键词: 随机数发生器, Knuth39, 并行化, 超多核心, TestU01

Abstract:

To solve the low running speed problem of Knuth39 random number generator, a Knuth39 parallelization method based on Many Integrated Core (MIC) platform was proposed. Firstly, the random number sequence of Knuth39 generator was divided into subsequences by regular interval. Then, the random numbers were generated by every thread from the corresponding subsequence's starting point. Finally, the random number sequences generated by all threads were combined into the final sequence. The experimental results show that the parallelized Knuth39 generator successfully passed 452 tests of TestU01, the results are the same as those of Knuth39 generator without parallelization. Compared with single thread on Central Processing Unit (CPU), the optimal speed-up ratio on MIC platform is 15.69 times. The proposed method improves the running speed of Knuth39 generator effectively, ensures the randomness of the generated sequences, and it is more suitable for high performance computing.

Key words: random number generator, Knuth39, parallelization, Many Integrated Core (MIC), TestU01

中图分类号:

TP311.52

张保东, 周津羽, 刘逍, 华诚, 周晓辉. 基于超多核心平台的Knuth39并行化实现及性能分析[J]. 计算机应用, 2015, 35(1): 58-61.

ZHANG Baodong, ZHOU Jinyu, LIU Xiao, HUA Cheng, ZHOU Xiaohui. Implementation and performance analysis of Knuth39 parallelization based on many integrated core platform[J]. Journal of Computer Applications, 2015, 35(1): 58-61.

参考文献

[1] SALMON J K, MORAES M A, DROR R O, et al. Parallel random numbers: as easy as 1, 2, 3 [C]// SC'11: Proceedings of 2011 International Conference for High Performance Computing, Networking, Storage and Analysis. New York: ACM, 2011: Article No. 16.
[2] WANG M, GUO F, QU H, et al. Combined random number generators: a review [C]// ICCSN 2011: Proceedings of the 2011 IEEE 3rd International Conference on Communication Software and Networks. Piscataway: IEEE, 2011: 443-447.
[3] OYA K, KITADA T, TANAKA S. Study on random number generator in Monte Carlo code [J]. Atomic Energy Society, 2011, 10(4): 301-309.
[4] LEHMER D H. Mathematical methods in large-scale computing units [C]// Proceedings of the Second Symposium on Large-Scale Digital Calculating Machinery. Cambridge: Harvard University Press, 1951: 141-146.
[5] KNUTH D E. The art of computer programming, volume 2: seminumerical algorithms [M]. 3rd ed. Boston: Addison-Wesley, 1998: 108.
[6] MARTON K, SUCIU A, PETRICEAN D. A parallel unpredictable random number generator [C]// Proceedings of the 2011 10th Roedunet International Conference: Networking in Education and Research. Piscataway: IEEE, 2011: 1-5.
[7] GAO S, PETERSON G D. GASPRNG: GPU accelerated scalable parallel random number generator library [J]. Computer Physics Communications, 2013, 184(4): 1241-1249.
[8] BRADLEY T, du TOIT J, GILES M, et al. Parallelisation techniques for random number generators [M]// GPU Computing Gems Emerald Edition. San Francisco: Morgan Kaufmann, 2011: 231-246.
[9] BARASH L Y, SHCHUR L N. RNGSSELIB: program library for random number generation, SSE2 realization [J]. Computer Physics Communications, 2011, 182(7): 1518-1527.
[10] BARASH L Y, SHCHUR L N. PRAND: GPU accelerated parallel random number generation library: using most reliable algorithms and applying parallelism of modern GPUs and CPUs [J]. Computer Physics Communications, 2014, 185(4): 1343-1353.
[11] ZHU Y, LI B, SUN T, et al. Research on scalability of parallel computing system [J]. Computer Engineering and Applications, 2011, 47(21): 47-49.(祝永志,李丙峰,孙婷婷,等.并行计算系统可扩展性的研究[J].计算机工程与应用,2011,47(21):47-49.)
[12] KHEMKA J, GAJJAR M, VASWANI S, et al. Performance evaluation of medical imaging algorithms on Intel MIC platform [C]// Proceedings of the 2013 20th International Conference on High Performance Computing. Piscataway: IEEE, 2013: 396-404.
[13] SUCIU A, TOMA R A, MARTON K. Parallel implementation of the TestU01 statistical test suite [C]// Proceedings of the 2012 IEEE 8th International Conference on Intelligent Computer Communication and Processing. Piscataway: IEEE, 2012: 317-322.

[1]	王周恺, 张炯, 马维纲, 王怀军. 面向高速列车监测数据的并行解压缩算法[J]. 计算机应用, 2021, 41(9): 2586-2593.
[2]	蒋林, 施佳琪, 李远成. 可重构结构下合成视点失真变化算法并行设计与实现[J]. 计算机应用, 2021, 41(6): 1734-1740.
[3]	宋祥帅, 杨伏长, 谢江, 张武. Graphlet Degree Vector方法的优化与并行[J]. 《计算机应用》唯一官方网站, 2020, 40(2): 398-403.
[4]	郭良敏, 朱莹, 孙丽萍. 障碍空间中基于并行蚁群算法的k近邻查询[J]. 计算机应用, 2019, 39(3): 790-795.
[5]	李龙洋, 董一鸿, 施炜杰, 潘剑飞. SQM:基于Spark的大规模单图上的子图匹配算法[J]. 计算机应用, 2019, 39(1): 46-50.
[6]	孙佳敏, 朱嘉富, 杨伏长, 谢江. 大规模生物网络马尔可夫聚类的并行化算法[J]. 计算机应用, 2019, 39(1): 66-71.
[7]	杨伏长, 朱嘉富, 孙佳敏, 谢江. 生物复杂网络motif发现的并行算法[J]. 计算机应用, 2019, 39(1): 72-77.
[8]	崔晨, 郑林江, 韩凤萍, 何牧君. 基于内存的HBase二级索引设计[J]. 计算机应用, 2018, 38(6): 1584-1590.
[9]	张承畅, 张华誉, 罗建昌, 何丰. 基于云计算和改进K-means算法的海量用电数据分析方法[J]. 计算机应用, 2018, 38(1): 159-164.
[10]	刘有耀, 杨鹏程. 基于JavaCC的C代码自动并行化的设计与实现[J]. 计算机应用, 2016, 36(9): 2422-2426.
[11]	韩逢庆, 宋志坚, 余锐. 海量图片快速去重技术[J]. 计算机应用, 2016, 36(7): 1797-1800.
[12]	曾雪琳, 吴斌. 基于位置的社会化网络的并行化推荐算法[J]. 计算机应用, 2016, 36(2): 316-323.
[13]	林炀, 江育娥, 林劼. 基于分布式架构的时间序列局部相似检测算法[J]. 计算机应用, 2016, 36(12): 3285-3291.
[14]	于苹苹, 倪建成, 姚彬修, 李淋淋, 曹博. 基于Spark框架的高效KNN中文文本分类算法[J]. 计算机应用, 2016, 36(12): 3292-3297.
[15]	陈珍, 夏靖波, 杨娟, 韦泽鲲. 基于MapReduce的支持向量机态势评估算法[J]. 计算机应用, 2016, 36(1): 133-137.

基于超多核心平台的Knuth39并行化实现及性能分析

Implementation and performance analysis of Knuth39 parallelization based on many integrated core platform

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics