基于众核平台的CLCG并行化设计与实现

杨 杰，宋博文，张保东，周晓辉

（1.西安邮电大学 国有资产管理处，陕西 西安 710121；2.西安邮电大学 计算机学院，陕西 西安 710121；3.高效能服务器和存储技术国家重点实验室，山东 济南 251621）

Monte Carlo模拟是一种利用随机因子求解金融和数学等问题的计算方法，而随机数产生器生成随机数序列是Monte Carlo模拟的基本问题之一［1］。线性同余产生器（Linear Congruential Generator，LCG）是一种应用较为广泛的随机数产生器，它具有算法简单、生成速率快等特点，但存在随机数序列生成周期短的缺陷［2］。而组合式线性同余产生器（Combined Linear Congruential Generator，CLCG）通过两个LCG的结合共同递推产生随机数［3］，可提高随机数序列的周期以及随机性，但需借助并行化处理［4］，以降低其计算量。

基于CPU平台的随机数产生器并行化设计存在功耗高、维护成本高等问题［5］，而基于Intel集成众核（Many Integrated Core，MIC）平台［6］采用低能耗的协处理器方式，具有多核多线程、运算速度快等特点，能实现在更低功耗、更高密度范围内进行高度并行处理。本文基于Intel MIC平台，对CLCG进行并行化设计，并对基于CPU和基于Intel MIC两个平台下的CLCG性能进行对比实验。

1 CLCG串行算法及其并行化设计

1.1 CLCG串行算法

线性同余随机数产生器（Linear Congruential Generator，LCG）的递推公式［2］为

其中a、c和m 分别为乘数、增量和模数，Xn为生成的随机数。

CLCG是组合LCG，递推公式［2］为

m1＝231－1，m2＝231－249，zn为中间变量时，产生［0，1）之间的均匀随机数

其随机数序列生成周期p是m1－1和m2－1的最小公倍数，约为256。

1.2 CLCG并行算法设计

将CLCG周期为p的原始随机数序列平均划分成N 段，最多可运行N＝210个线程，各线程最多产生随机数个数为L＝p／N＝246个，每个线程的子序列都是原始序列从特定起点开始递推产生的连续子序列。CLCG的并行算法中每个线程独自产生原始序列的其中一段，彼此之间并无相关性。假设实际产生的随机数总任务量为R＿Num，分配的线程数为T＿Num，则每个线程能够产生R＿Num／T＿Num个随机数。CLCG的并行算法设计如图1所示。

图1 CLCG并行化原理

其中线程i产生的随机数序列为

CLCG并行化的关键问题是确定线程i的初始状态UiL，即通过初始值x0快速有效的计算出线程i对应的随机数值xiL，得出xiL需先计算随机数值xL。

可以得到［2］

其中aLmodm通过分治算法在O（logL）的时间复杂度［7－8］内计算出来，递推公式为

根据上述推导可用伪代码将CLCG并行化算法具体描述为

输入：种子seed［2］，线程数T＿Num，任务量R＿Num输出：R＿Num个随机数U

并行算法设计的可行性主要考核加速比和可扩展性两项指标，指标特性分析如下。

CLCG串行算法的任务量与产生的随机数总量R＿Num成正比，而CLCG的并行算法是将总任务量平均分配给i个线程，充分并行的情况下，并行算法的加速比接近于线程数。而当任务量较少时，分配线程、访问共享变量、内存间转换等通信开销会额外消耗时间，相应的加速比会下降，而任务量逐渐增加后，通信开销所占比例越来越小，逐渐呈现出线性加速。

采用等加速标准［9］分析CLCG并行算法的可扩展性。按照等加速定义，对于某个并行算法，若增大一定任务量后并行过程的平均速度不变，则称该算法是可扩展的。其中平均速度不变指速度与线程数呈线性比例增长，加速比为线性或近似线性。CLCG产生随机数的任务量较大时，理论加速比接近线性加速，CLCG的并行算法扩展性会更好。

1.3 基于MIC平台的CLCG并行算法实现

Intel生产的MIC协处理器支持上百个线程，而且CLCG并行化属于细粒度并行，适合移植到MIC平台上［10－11］，因此基于Intel MIC的 CLCG 可实现并行化，实现过程分为3个步骤：（1）将CLCG串行版本利用OpenMP并行化，并利用随机数检测库TestU01测试随机数序列的准确性；（2）测试CPU上并行版本的整体性能，如果扩展性不好，对程序进行优化，使之发挥出众核的优势；（3）移植到Intel MIC上进行性能测试。

2 实验数据及性能分析

2.1 TestU01测试分析

选用均匀随机数统计检测库TestU01［12］测试CLCG并行化后产生随机数的质量。分别对CLCG串行版本与4线程并行版本进行随机数质量测试，最终并行版本通过了452项统计检测，与串行版本相同，每项检测的统计假定值P－value统计分布情况如图2所示。图2中CLCG串行版本检测的统计假定值P－value在区间（0.08，0.92）之间比例为84.28%，CLCG并行版本检测的统计假定值P－value在区间（0.08，0.92）之间比例为85.62%，检测比例基本相同。同时对CLCG串行和并行版本检测的P－value进行双样本拟合优度统计检测，检测结果是0.3261。两种版本检测的统计假定值P－value近似服从相同分布，说明CLCG串行和并行程序产生的随机数质量近似。

图2 CLCG串行与4线程并行程序TestU01测试P－value统计分布

2.2 基于CPU的CLCG并行化性能分析

测试所选用的CPU平台为两个8核处理器Intel Xeon E5－2680＠2.7GHz，分别对1、2、4、8、16个线程下产生1000000、10000000、100000000、1000000000和10000000000个随机数的时间进行了测试，测试结果如表1所示，计算相应加速比如图3所示。

表1 CLCG基于CPU的测试时间／s

由图3可知，基于CPU的CLCG并行化加速比与线程数接近线性增长，产生随机数的数量较少时加速比并不明显。线程数为16时，最优加速比为14.17倍。当线程数增加时，可通过增加任务量提高加速比，说明CLCG并行算法具有一定扩展性，其并行程序可以移植到Intel MIC平台。

图3 CLCG基于CPU的加速比趋势

2.3 基于MIC的CLCG并行化性能分析

采用Intel MIC原生模式运行并行程序：在Intel编译选项中添加－mmic选项，编译后上传到MIC卡上执行。实验所使用的MIC平台为Intel Xeon Phi 3110P57cores＠1.10GHz，含有57个核心，每个物理核心有4个线程。分别对1、2、4、8、16、32、56、112、168和224个线程下产生1000000、10000000、100000000、1000000000及10000000000个随机数的时间进行了测试，测试结果如表2所示，计算相应加速比如图4所示。

表2 CLCG基于MIC的测试时间／s

图4 CLCG基于MIC的加速比趋势

由图4可知，基于MIC的CLCG并行化加速比与线程数并没有呈现出足够的线性增长，当线程数为224时，最优加速比为112.47倍，单个Intel MIC卡相比于CPU单线程，运行最优加速比提升了14.61倍。随着线程数量的增加，线程的创建和销毁工作占用系统资源的比重增加，线程间又访问共享变量，增加了系统负担，降低并行效率，加速比不会随着线程数线性增长。同时随着任务量变大，线程数的增加后，加速比逐渐呈线性状态，验证了CLCG并行算法的可扩展性。由图4可知，线程数并非越多越好，比如产生100000000个随机数时112个线程左右用时最少，因为线程数太多，开销也增大，影响了整体计算速度，因此需根据任务量设置合适的线程数。从分析结果可以得出，虽然Intel MIC单核的计算能力弱于同期的CPU，但是利用Intel MIC众核并行的多核多线程特点，加速比依然可以得到提升。

3 结束语

基于Intel集成众核平台下的CLCG并行化设计，通过随机数检测库TestU01的452项测试，验证了该设计的可行性。同时基于CPU平台和Intel MIC平台进行时间测试和性能分析，测试结果表明基于Intel MIC平台测试，线程数较多时并行效率并不是非常高，但相比较CPU单线程，MIC平台的最优加速比还是依然可以满足设计要求，产生10000000000个随机数的时间提升了14.61倍。与串行算法相比，CLCG基于Intel MIC并行化后，运行速度得到改善，可为Monte Carlo模拟实现提供一种可行的优化方案。

［1］L’ECUYER P.Random numbers for simulation［J］.ACM Transactions on Modeling and Computer Simulation，1990，33（10）：85－97.

［2］Knuth D E.The Art of Computer Programming，Volume 2 （3rd Ed.）：Seminumerical Algorithms［M］.Boston：Addison－Wesley Longman Publishing，1998：108.

［3］Gao S，Peterson G D.GASPRNG：GPU accelerated scalable parallel random number generator library［J］.Computer Physics Communications，2013，184（4）：1241－1249.

［4］Bradley T，Toit J，Giles M，et al.Parallelization techniques for random number generators［J］.GPU Computing Gems，2015，1（5）：152－163.

［5］吴再龙，众核体系下算法优化的若干技术研究［D］.青岛：中国海洋大学，2014：10－13.

［6］王恩东，张清.MIC高性能计算编程指南［M］.北京：中国水利水电出版社，2012：103.

［7］L’ECUYER P，Simard R，Jack C，et al.An object－oriented random number package with many long streams and substreams［J］.Operations Research，2002（2）：1073－1075.

［8］郑东，赵庆兰，张应辉.密码学综述［J］.西安邮电大学学报，2013，18（6）：1－10.

［9］陈国良.并行算法的设计与分析［M］.北京：高等教育出版社，2002：268.

［10］杨志昱，张旭东.基于集成众核的高性能计算软件优化［J］.电子技术与软件工程，2014（21）：23.

［11］吕慧伟，程元，白露，等.众核处理器和众核集群的并行模拟［J］.计算机研究与发展，2013（5）：1111.

［12］Ismay C.Testing independence of parallel pseudorandom number streams incorporating the data’s multivariate nature［J］.Dissertations ＆ Theses－Gradworks，2013（8）：583.