基于眾核平臺(tái)的CLCG并行化設(shè)計(jì)與實(shí)現(xiàn)

楊 杰，宋博文，張保東，周曉輝

（1.西安郵電大學(xué) 國(guó)有資產(chǎn)管理處，陜西 西安 710121；2.西安郵電大學(xué) 計(jì)算機(jī)學(xué)院，陜西 西安 710121；3.高效能服務(wù)器和存儲(chǔ)技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室，山東 濟(jì)南 251621）

Monte Carlo模擬是一種利用隨機(jī)因子求解金融和數(shù)學(xué)等問(wèn)題的計(jì)算方法，而隨機(jī)數(shù)產(chǎn)生器生成隨機(jī)數(shù)序列是Monte Carlo模擬的基本問(wèn)題之一［1］。線性同余產(chǎn)生器（Linear Congruential Generator，LCG）是一種應(yīng)用較為廣泛的隨機(jī)數(shù)產(chǎn)生器，它具有算法簡(jiǎn)單、生成速率快等特點(diǎn)，但存在隨機(jī)數(shù)序列生成周期短的缺陷［2］。而組合式線性同余產(chǎn)生器（Combined Linear Congruential Generator，CLCG）通過(guò)兩個(gè)LCG的結(jié)合共同遞推產(chǎn)生隨機(jī)數(shù)［3］，可提高隨機(jī)數(shù)序列的周期以及隨機(jī)性，但需借助并行化處理［4］，以降低其計(jì)算量。

基于CPU平臺(tái)的隨機(jī)數(shù)產(chǎn)生器并行化設(shè)計(jì)存在功耗高、維護(hù)成本高等問(wèn)題［5］，而基于Intel集成眾核（Many Integrated Core，MIC）平臺(tái)［6］采用低能耗的協(xié)處理器方式，具有多核多線程、運(yùn)算速度快等特點(diǎn)，能實(shí)現(xiàn)在更低功耗、更高密度范圍內(nèi)進(jìn)行高度并行處理。本文基于Intel MIC平臺(tái)，對(duì)CLCG進(jìn)行并行化設(shè)計(jì)，并對(duì)基于CPU和基于Intel MIC兩個(gè)平臺(tái)下的CLCG性能進(jìn)行對(duì)比實(shí)驗(yàn)。

1 CLCG串行算法及其并行化設(shè)計(jì)

1.1 CLCG串行算法

線性同余隨機(jī)數(shù)產(chǎn)生器（Linear Congruential Generator，LCG）的遞推公式［2］為

其中a、c和m 分別為乘數(shù)、增量和模數(shù)，Xn為生成的隨機(jī)數(shù)。

CLCG是組合LCG，遞推公式［2］為

m1＝231－1，m2＝231－249，zn為中間變量時(shí)，產(chǎn)生［0，1）之間的均勻隨機(jī)數(shù)

其隨機(jī)數(shù)序列生成周期p是m1－1和m2－1的最小公倍數(shù)，約為256。

1.2 CLCG并行算法設(shè)計(jì)

將CLCG周期為p的原始隨機(jī)數(shù)序列平均劃分成N 段，最多可運(yùn)行N＝210個(gè)線程，各線程最多產(chǎn)生隨機(jī)數(shù)個(gè)數(shù)為L(zhǎng)＝p／N＝246個(gè)，每個(gè)線程的子序列都是原始序列從特定起點(diǎn)開(kāi)始遞推產(chǎn)生的連續(xù)子序列。CLCG的并行算法中每個(gè)線程獨(dú)自產(chǎn)生原始序列的其中一段，彼此之間并無(wú)相關(guān)性。假設(shè)實(shí)際產(chǎn)生的隨機(jī)數(shù)總?cè)蝿?wù)量為R＿Num，分配的線程數(shù)為T(mén)＿Num，則每個(gè)線程能夠產(chǎn)生R＿Num／T＿Num個(gè)隨機(jī)數(shù)。CLCG的并行算法設(shè)計(jì)如圖1所示。

圖1 CLCG并行化原理

其中線程i產(chǎn)生的隨機(jī)數(shù)序列為

CLCG并行化的關(guān)鍵問(wèn)題是確定線程i的初始狀態(tài)UiL，即通過(guò)初始值x0快速有效的計(jì)算出線程i對(duì)應(yīng)的隨機(jī)數(shù)值xiL，得出xiL需先計(jì)算隨機(jī)數(shù)值xL。

可以得到［2］

其中aLmodm通過(guò)分治算法在O（logL）的時(shí)間復(fù)雜度［7－8］內(nèi)計(jì)算出來(lái)，遞推公式為

根據(jù)上述推導(dǎo)可用偽代碼將CLCG并行化算法具體描述為

輸入：種子seed［2］，線程數(shù)T＿Num，任務(wù)量R＿Num輸出：R＿Num個(gè)隨機(jī)數(shù)U

并行算法設(shè)計(jì)的可行性主要考核加速比和可擴(kuò)展性?xún)身?xiàng)指標(biāo)，指標(biāo)特性分析如下。

CLCG串行算法的任務(wù)量與產(chǎn)生的隨機(jī)數(shù)總量R＿Num成正比，而CLCG的并行算法是將總?cè)蝿?wù)量平均分配給i個(gè)線程，充分并行的情況下，并行算法的加速比接近于線程數(shù)。而當(dāng)任務(wù)量較少時(shí)，分配線程、訪問(wèn)共享變量、內(nèi)存間轉(zhuǎn)換等通信開(kāi)銷(xiāo)會(huì)額外消耗時(shí)間，相應(yīng)的加速比會(huì)下降，而任務(wù)量逐漸增加后，通信開(kāi)銷(xiāo)所占比例越來(lái)越小，逐漸呈現(xiàn)出線性加速。

采用等加速標(biāo)準(zhǔn)［9］分析CLCG并行算法的可擴(kuò)展性。按照等加速定義，對(duì)于某個(gè)并行算法，若增大一定任務(wù)量后并行過(guò)程的平均速度不變，則稱(chēng)該算法是可擴(kuò)展的。其中平均速度不變指速度與線程數(shù)呈線性比例增長(zhǎng)，加速比為線性或近似線性。CLCG產(chǎn)生隨機(jī)數(shù)的任務(wù)量較大時(shí)，理論加速比接近線性加速，CLCG的并行算法擴(kuò)展性會(huì)更好。

1.3 基于MIC平臺(tái)的CLCG并行算法實(shí)現(xiàn)

Intel生產(chǎn)的MIC協(xié)處理器支持上百個(gè)線程，而且CLCG并行化屬于細(xì)粒度并行，適合移植到MIC平臺(tái)上［10－11］，因此基于Intel MIC的 CLCG 可實(shí)現(xiàn)并行化，實(shí)現(xiàn)過(guò)程分為3個(gè)步驟：（1）將CLCG串行版本利用OpenMP并行化，并利用隨機(jī)數(shù)檢測(cè)庫(kù)TestU01測(cè)試隨機(jī)數(shù)序列的準(zhǔn)確性；（2）測(cè)試CPU上并行版本的整體性能，如果擴(kuò)展性不好，對(duì)程序進(jìn)行優(yōu)化，使之發(fā)揮出眾核的優(yōu)勢(shì)；（3）移植到Intel MIC上進(jìn)行性能測(cè)試。

2 實(shí)驗(yàn)數(shù)據(jù)及性能分析

2.1 TestU01測(cè)試分析

選用均勻隨機(jī)數(shù)統(tǒng)計(jì)檢測(cè)庫(kù)TestU01［12］測(cè)試CLCG并行化后產(chǎn)生隨機(jī)數(shù)的質(zhì)量。分別對(duì)CLCG串行版本與4線程并行版本進(jìn)行隨機(jī)數(shù)質(zhì)量測(cè)試，最終并行版本通過(guò)了452項(xiàng)統(tǒng)計(jì)檢測(cè)，與串行版本相同，每項(xiàng)檢測(cè)的統(tǒng)計(jì)假定值P－value統(tǒng)計(jì)分布情況如圖2所示。圖2中CLCG串行版本檢測(cè)的統(tǒng)計(jì)假定值P－value在區(qū)間（0.08，0.92）之間比例為84.28%，CLCG并行版本檢測(cè)的統(tǒng)計(jì)假定值P－value在區(qū)間（0.08，0.92）之間比例為85.62%，檢測(cè)比例基本相同。同時(shí)對(duì)CLCG串行和并行版本檢測(cè)的P－value進(jìn)行雙樣本擬合優(yōu)度統(tǒng)計(jì)檢測(cè)，檢測(cè)結(jié)果是0.3261。兩種版本檢測(cè)的統(tǒng)計(jì)假定值P－value近似服從相同分布，說(shuō)明CLCG串行和并行程序產(chǎn)生的隨機(jī)數(shù)質(zhì)量近似。

圖2 CLCG串行與4線程并行程序TestU01測(cè)試P－value統(tǒng)計(jì)分布

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

測(cè)試所選用的CPU平臺(tái)為兩個(gè)8核處理器Intel Xeon E5－2680＠2.7GHz，分別對(duì)1、2、4、8、16個(gè)線程下產(chǎn)生1000000、10000000、100000000、1000000000和10000000000個(gè)隨機(jī)數(shù)的時(shí)間進(jìn)行了測(cè)試，測(cè)試結(jié)果如表1所示，計(jì)算相應(yīng)加速比如圖3所示。

表1 CLCG基于CPU的測(cè)試時(shí)間／s

由圖3可知，基于CPU的CLCG并行化加速比與線程數(shù)接近線性增長(zhǎng)，產(chǎn)生隨機(jī)數(shù)的數(shù)量較少時(shí)加速比并不明顯。線程數(shù)為16時(shí)，最優(yōu)加速比為14.17倍。當(dāng)線程數(shù)增加時(shí)，可通過(guò)增加任務(wù)量提高加速比，說(shuō)明CLCG并行算法具有一定擴(kuò)展性，其并行程序可以移植到Intel MIC平臺(tái)。

圖3 CLCG基于CPU的加速比趨勢(shì)

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

采用Intel MIC原生模式運(yùn)行并行程序：在Intel編譯選項(xiàng)中添加－mmic選項(xiàng)，編譯后上傳到MIC卡上執(zhí)行。實(shí)驗(yàn)所使用的MIC平臺(tái)為Intel Xeon Phi 3110P57cores＠1.10GHz，含有57個(gè)核心，每個(gè)物理核心有4個(gè)線程。分別對(duì)1、2、4、8、16、32、56、112、168和224個(gè)線程下產(chǎn)生1000000、10000000、100000000、1000000000及10000000000個(gè)隨機(jī)數(shù)的時(shí)間進(jìn)行了測(cè)試，測(cè)試結(jié)果如表2所示，計(jì)算相應(yīng)加速比如圖4所示。

表2 CLCG基于MIC的測(cè)試時(shí)間／s

圖4 CLCG基于MIC的加速比趨勢(shì)

由圖4可知，基于MIC的CLCG并行化加速比與線程數(shù)并沒(méi)有呈現(xiàn)出足夠的線性增長(zhǎng)，當(dāng)線程數(shù)為224時(shí)，最優(yōu)加速比為112.47倍，單個(gè)Intel MIC卡相比于CPU單線程，運(yùn)行最優(yōu)加速比提升了14.61倍。隨著線程數(shù)量的增加，線程的創(chuàng)建和銷(xiāo)毀工作占用系統(tǒng)資源的比重增加，線程間又訪問(wèn)共享變量，增加了系統(tǒng)負(fù)擔(dān)，降低并行效率，加速比不會(huì)隨著線程數(shù)線性增長(zhǎng)。同時(shí)隨著任務(wù)量變大，線程數(shù)的增加后，加速比逐漸呈線性狀態(tài)，驗(yàn)證了CLCG并行算法的可擴(kuò)展性。由圖4可知，線程數(shù)并非越多越好，比如產(chǎn)生100000000個(gè)隨機(jī)數(shù)時(shí)112個(gè)線程左右用時(shí)最少，因?yàn)榫€程數(shù)太多，開(kāi)銷(xiāo)也增大，影響了整體計(jì)算速度，因此需根據(jù)任務(wù)量設(shè)置合適的線程數(shù)。從分析結(jié)果可以得出，雖然Intel MIC單核的計(jì)算能力弱于同期的CPU，但是利用Intel MIC眾核并行的多核多線程特點(diǎn)，加速比依然可以得到提升。

3 結(jié)束語(yǔ)

基于Intel集成眾核平臺(tái)下的CLCG并行化設(shè)計(jì)，通過(guò)隨機(jī)數(shù)檢測(cè)庫(kù)TestU01的452項(xiàng)測(cè)試，驗(yàn)證了該設(shè)計(jì)的可行性。同時(shí)基于CPU平臺(tái)和Intel MIC平臺(tái)進(jìn)行時(shí)間測(cè)試和性能分析，測(cè)試結(jié)果表明基于Intel MIC平臺(tái)測(cè)試，線程數(shù)較多時(shí)并行效率并不是非常高，但相比較CPU單線程，MIC平臺(tái)的最優(yōu)加速比還是依然可以滿(mǎn)足設(shè)計(jì)要求，產(chǎn)生10000000000個(gè)隨機(jī)數(shù)的時(shí)間提升了14.61倍。與串行算法相比，CLCG基于Intel MIC并行化后，運(yùn)行速度得到改善，可為Monte Carlo模擬實(shí)現(xiàn)提供一種可行的優(yōu)化方案。

［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］吳再龍，眾核體系下算法優(yōu)化的若干技術(shù)研究［D］.青島：中國(guó)海洋大學(xué)，2014：10－13.

［6］王恩東，張清.MIC高性能計(jì)算編程指南［M］.北京：中國(guó)水利水電出版社，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］鄭東，趙慶蘭，張應(yīng)輝.密碼學(xué)綜述［J］.西安郵電大學(xué)學(xué)報(bào)，2013，18（6）：1－10.

［9］陳國(guó)良.并行算法的設(shè)計(jì)與分析［M］.北京：高等教育出版社，2002：268.

［10］楊志昱，張旭東.基于集成眾核的高性能計(jì)算軟件優(yōu)化［J］.電子技術(shù)與軟件工程，2014（21）：23.

［11］呂慧偉，程元，白露，等.眾核處理器和眾核集群的并行模擬［J］.計(jì)算機(jī)研究與發(fā)展，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.