基于多核并行的非線性方程蒙特卡洛計算方法

薛小超　王克　朱朋海

摘要：隨著社會生產(chǎn)生活的發(fā)展，對計算機的依賴越來越大，要解決龐大計算量的實際問題就需要高性能的計算機以及高速的計算方法。在應(yīng)用蒙特卡洛方法求解非線性方程組時，利用多線程技術(shù)，串行改并行，使用WinAPI、OpenMP、MPI三種并行模式得出三種最優(yōu)的并行計算方法。根據(jù)數(shù)值試驗分析了各種計算模式的優(yōu)缺點，發(fā)現(xiàn)MPI并行模式計算速度最快，最終得以結(jié)論并行計算模式可以推廣到各種數(shù)值計算問題。

關(guān)鍵詞：并行計算；多線程；WinAPI；OpenMP；MPI

中圖分類號：TP301.6 文獻標識碼：A 文章編號：1009-3044（2014）21-5115-05

針對下面提出的山高問題，本質(zhì)上就是求解非線性方程組，而對于非線性方程組數(shù)值解法發(fā)展迅速，如迭代法、Newton法、同倫算法、人工智能算法[1]等。這些算法優(yōu)點突出，對于同倫算法、人工智能算法有很高的精度，計算速度非常快，看上去是完美的，但美中不足的是這些算法都為串行算法，缺少多核CPU并行手段，經(jīng)過并行之后的算法求解非線性方程組能夠極大地縮短計算時間，提高效率。為此專門利用三種最常用的并行模式，精心改造并挑選出三種最優(yōu)的并行計算方法。

第一種并行模式：使用WinAPI[2]創(chuàng)建新線程即線程函數(shù)，然后通過API接口進行多線程調(diào)度完成并行；第二種并行模式：使用OpenMP[2]并行語言，通過設(shè)置參數(shù)與線程數(shù)，利用庫函數(shù)循環(huán)并行化，實現(xiàn)算法并行計算；第三種并行模式：MPI[2] 并行是一種基于消息傳遞的并行語言，各進程具有獨立的堆棧和代碼段，多個程序獨立進行，從而利用多節(jié)點或者多CPU模擬多節(jié)點實現(xiàn)并行計算，這也是MPI并行最快的原因。就這樣我們可以串行該并行，得到優(yōu)化算法，不僅解決非線性方程問題還拓展到其它數(shù)值問題。

1 問題提出

山高的估計：假如你站在山頂且身上帶著一只具有跑表功能的計算器，你也許會出于好奇心想用扔下一塊石頭聽回聲的方法來估計山的高度，假定你能準確地測定時間，你又怎樣來推算山崖的高度呢，請你分析這一問題[3]。

2 問題分析

除地球吸引力外，對石塊下落影響最大的當屬空氣的阻力。根據(jù)流體力學(xué)知識，此時可設(shè)空氣阻力正比于石塊下落的速度，阻力系數(shù)為常數(shù)，因而，由牛頓第二定律可得[3]：

3 串行算法求解

串行算法是最基本的實現(xiàn)方法。其實現(xiàn)的核心是fun的絕對值與fun0的比較，每產(chǎn)生一個fun就與fun0比較，絕對值小的賦值給fun0，直到完成循環(huán)。具體的算法實現(xiàn)：

4 并行算法求解

4.1 WinAPI并行實現(xiàn)

首先利用WinAPI生成線程函數(shù)，編寫線程函數(shù)完成單一工作量，主函數(shù)中調(diào)用該線程函數(shù)，根據(jù)線程數(shù)目調(diào)用相應(yīng)的CPU進行計算，保證CPU運行正常，負載量均衡。最后將計算結(jié)果合并、比較得到需要的結(jié)果。

在Windows實現(xiàn)多線程并行計算時會產(chǎn)生數(shù)據(jù)競爭（Data racing），數(shù)據(jù)競爭導(dǎo)致計算出現(xiàn)錯誤，計算結(jié)果有時相差很大。錯誤的原因歸結(jié)為多線程同時訪問同一區(qū)域，讀寫操作沖突。為此采用同步技術(shù)，利用臨界區(qū)與線程號分配任務(wù)解決此問題。

對于此問題，臨界區(qū)作用于非線性方程組求解。臨界區(qū)是一種針對多線程對同一區(qū)域訪問混亂而設(shè)置的保護機制。它的作用在于當并行時，多線程訪問次序因臨界區(qū)而有序，互相不干擾，計算結(jié)果也就不會影響，是一個很好的屏障。

5 分析與討論

開發(fā)驗證工具：計算機Intel Core i7 八核處理器，開發(fā)工具Microsoft Visual Studio 2010，Microsoft Windows 版本[6.2.9200] 2012 Microsoft Corporation。

結(jié)果分析與比較：對串行和并行的方法進行數(shù)值實驗，為了分析的方便，數(shù)值實驗的計算步數(shù)為20，000，000。數(shù)值實驗結(jié)果如下呈現(xiàn)：

四線程并行計算：

在表中，計算時間取平均值所得，以串行計算時間除以每種并行方式計算所用時間作為加速比，加速比理論值為4[4]（八線程加速比為8） 。由于實際調(diào)用線程及數(shù)據(jù)規(guī)約都會有時間損耗，導(dǎo)致加速比小于理想值。

由上面數(shù)據(jù)可知，WinAPI與OpenMP結(jié)果差不多，這與實際相符合，OpenMP是對WinAPI多線程的封裝，兩者在實現(xiàn)理論上一致。OpenMP算法簡單，使用方便，但總體來說并不穩(wěn)定。

MPI是基于通信的并行實現(xiàn)，它以獨特的實現(xiàn)方式在目前并行計算的發(fā)展趨勢下體現(xiàn)出強大的生命力。當然在進行主從式、并列式以及流水線式等方式的實現(xiàn)時，對于大數(shù)據(jù)傳輸要考慮數(shù)據(jù)傳輸時間，合理調(diào)整程序。 另外通過試驗比較，可以看出MPI計算速度最快，所用時間最少，因而加速比最接近理論值，增多節(jié)點數(shù)目相信計算效果會更好，所以MPI并行模式最適合求解大規(guī)模問題。

6 結(jié)束語

通過求解非線性方程組，可以看出蒙特卡洛方法在處理數(shù)值計算問題中發(fā)揮著重要的作用，將蒙特卡洛方法并行化可以極大地節(jié)省時間，提高效率，并且并行方法中的MPI方法并行處理時體現(xiàn)了很大的優(yōu)勢。類似的我們還可以通過并行手段解決其它的數(shù)值計算問題。

參考文獻：

[1] 夏林林，戶晗蕾，吳開騰，等.非線性方程組數(shù)值方法的研究進展[J].內(nèi)江師范學(xué)院學(xué)報，2013（10）：12-17.

[2] 多核系列教材編寫組.多核程序設(shè)計[M].北京：清華大學(xué)出版社，2007.

[3] 建模-百度文庫[EB/OL].（2012-11-14）. http：//wenku.baidu.com/view/3ba882323968011ca300919f.html.

[4] 朱建偉，劉榮.多線程并行快速求解e值的六種方法[J].現(xiàn)代計算機，2013（17）：15-20.

[5] 劉榮，朱建偉，李富合，等.基于四種并行計算模式的自然對數(shù)底并行計算方法[J].電腦知識與技術(shù)，2013（14）：3415-3419.