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

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

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

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

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

1.1 CLCG串行算法

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

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

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

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

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

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

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

圖1 CLCG并行化原理

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

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

可以得到［2］

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

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

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

并行算法設(shè)計的可行性主要考核加速比和可擴展性兩項指標(biāo)，指標(biāo)特性分析如下。

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

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

1.3 基于MIC平臺的CLCG并行算法實現(xiàn)

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

2 實驗數(shù)據(jù)及性能分析

2.1 TestU01測試分析

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

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

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

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

表1 CLCG基于CPU的測試時間／s

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

圖3 CLCG基于CPU的加速比趨勢

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

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

表2 CLCG基于MIC的測試時間／s

圖4 CLCG基于MIC的加速比趨勢

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

3 結(jié)束語

基于Intel集成眾核平臺下的CLCG并行化設(shè)計，通過隨機數(shù)檢測庫TestU01的452項測試，驗證了該設(shè)計的可行性。同時基于CPU平臺和Intel MIC平臺進行時間測試和性能分析，測試結(jié)果表明基于Intel MIC平臺測試，線程數(shù)較多時并行效率并不是非常高，但相比較CPU單線程，MIC平臺的最優(yōu)加速比還是依然可以滿足設(shè)計要求，產(chǎn)生10000000000個隨機數(shù)的時間提升了14.61倍。與串行算法相比，CLCG基于Intel MIC并行化后，運行速度得到改善，可為Monte Carlo模擬實現(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］.青島：中國海洋大學(xué)，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］鄭東，趙慶蘭，張應(yīng)輝.密碼學(xué)綜述［J］.西安郵電大學(xué)學(xué)報，2013，18（6）：1－10.

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

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

［11］呂慧偉，程元，白露，等.眾核處理器和眾核集群的并行模擬［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.