基于并行計(jì)算的Laplace變換

滿迪　陳華　周濤

摘要：Laplace變換是一種解決常系數(shù)偏微分方程初邊值問題的常用方法，在此，利用離散化方法和蒙特卡羅算法求解Laplace變換，運(yùn)用多線程技術(shù)，結(jié)合高性能并行計(jì)算中WinAPI，OpenMP的并行模式獲得最優(yōu)計(jì)算方法。通過數(shù)值結(jié)果可以看出，蒙特卡羅OpenMP方法速度最慢，效率最低，基于離散算的WinAPI方法計(jì)算速度最快，并行效率最高，最終獲得結(jié)論的并行計(jì)算模式應(yīng)用到其他初值問題。

關(guān)鍵詞： Laplace變換；OpenMP；WinAPI；蒙特卡羅算法

中圖分類號(hào)：TP393 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2016）23-0223-03

1 概述

拉普拉斯變換是工程數(shù)學(xué)常用的一種積分變換，在工程技術(shù)和理論研究等諸多方面有較廣泛的應(yīng)用，特別是對(duì)于求解常系數(shù)線性偏微分方程的初邊值問題。本文基于離散化的思想和蒙特卡羅算法對(duì)某一常見函數(shù)進(jìn)行Laplace變換，利用兩種并行模式改造并精選出最優(yōu)的并行計(jì)算處理方法。

蒙特卡羅方法是一種隨機(jī)模擬方法，它以統(tǒng)計(jì)理論方法和概率為基礎(chǔ)，是使用隨機(jī)數(shù)或偽隨機(jī)數(shù)來解決實(shí)際計(jì)算問題的方法。OpenMP是一種面向共享內(nèi)存及分布式共享內(nèi)存的多處理器多線程并行編程語言，是能用于顯示指導(dǎo)多線程、共享內(nèi)存并行的應(yīng)用程序編程接口，并利用封裝好的函數(shù)來進(jìn)行并行計(jì)算；WinAPI并行模式是通過編寫線程函數(shù)，利用Windows系統(tǒng)中的API接口進(jìn)行多線程調(diào)度來實(shí)現(xiàn)并行。通過對(duì)數(shù)值實(shí)驗(yàn)的串并行算法的計(jì)算速度，加速效果進(jìn)行比較，得出并行優(yōu)化后的計(jì)算方法。并進(jìn)一步考慮將計(jì)算中高效的并行方法應(yīng)用到其他數(shù)值問題。

2 拉普拉斯變換描述

3.1 API實(shí)現(xiàn)

首先在進(jìn)程內(nèi)創(chuàng)建線程，它是CPU調(diào)度和分配的基本單位。利用WINAPI定義線程函數(shù)，在線程函數(shù)內(nèi)分配該線程所要進(jìn)行的任務(wù)，然后將線程函數(shù)導(dǎo)入到創(chuàng)建好的線程中運(yùn)行，計(jì)算機(jī)通過API接口，針對(duì)創(chuàng)建的線程數(shù)目，調(diào)度相同數(shù)目的CPU進(jìn)行計(jì)算，最后將各線程的計(jì)算結(jié)果合并得到最終結(jié)果。

程序中使用多線程時(shí)，很多情況下是一些線程進(jìn)行某些處理操作，而其他線程必須對(duì)其處理結(jié)果進(jìn)行了解，若不采取適當(dāng)措施，其他線程會(huì)在線程處理任務(wù)結(jié)束前就去訪問處理結(jié)果，因此產(chǎn)生了數(shù)據(jù)競爭。為避免數(shù)據(jù)競爭，我們使用臨界區(qū)進(jìn)行數(shù)據(jù)同步，臨界區(qū)獨(dú)占對(duì)某些共享資源的訪問，它只允許一個(gè)線程對(duì)共享資源進(jìn)行訪問。若有多個(gè)線程想同時(shí)訪問臨界區(qū)，那么在一個(gè)線程進(jìn)入臨界區(qū)后其他線程將被掛起。在本問題的實(shí)現(xiàn)過程中，將求和運(yùn)算拖入臨界區(qū)，來避免頻繁介入臨界區(qū)。

3.2 OpenMP實(shí)現(xiàn)

利用parallel for循環(huán)并行化

采用工作分配的執(zhí)行方式，利用parallel for循環(huán)語句將總的工作量按照一定的方式分配到各個(gè)線程，最后將所有線程的結(jié)果匯總。Parellel for 是對(duì)一個(gè)完整的for循環(huán)進(jìn)行分割，它根據(jù)線程數(shù)大小按工作量平均分配，每個(gè)線程的工作量為總的工作量/線程數(shù)。為了避免產(chǎn)生數(shù)據(jù)競爭，采用的方法是對(duì)競爭變量私有化，添加私有量private（n），再對(duì)執(zhí)行完的程序利用reducation語句進(jìn)行歸約操作，用來更好的收集任務(wù)結(jié)果。

4 蒙特卡羅算法求解

4.1 蒙特卡羅算法

4.3 基于OpenMp并行算法實(shí)現(xiàn)

我們?cè)诖谐绦虻幕A(chǔ)上通過OpenMP進(jìn)行并行處理。求解該問題需要計(jì)算N個(gè)值，然后對(duì)N個(gè)值進(jìn)行求和。在計(jì)算N個(gè)值得過程中數(shù)據(jù)之間沒有依賴關(guān)系，所以我們采用四個(gè)線程將任務(wù)進(jìn)行分配。在計(jì)算每個(gè)值之前我們都需要隨機(jī)產(chǎn)生一個(gè)介于積分區(qū)間的隨機(jī)數(shù)，為了減少共享內(nèi)存帶來的時(shí)間消耗，我們將這個(gè)隨機(jī)數(shù)設(shè)定為每個(gè)線程的私有變量private（x）。然后利用規(guī)約reduction（+：s）將N個(gè)值進(jìn)行求和運(yùn)算，得到最終結(jié)果。

5 分析與結(jié)論

上述結(jié)果可以看出利用離散化方法所花費(fèi)的時(shí)間整體比較少，在串行的基礎(chǔ)上對(duì)它進(jìn)行并行實(shí)現(xiàn)，使得效率進(jìn)一步提高。OpenMP的加速比達(dá)到2.5396，API的加速比達(dá)到3.113。利用蒙特卡洛算法計(jì)算過程中所用時(shí)間比較長。主要因?yàn)槊商乜逅惴ㄖ饕槍?duì)的是多重積分的計(jì)算，而該問題是一重積分的運(yùn)算所以效率較低。但蒙特卡洛算法的串行和并行算法相比較可以看出并行算法效率較高，加速比達(dá)到2.498。綜合上述結(jié)果可以看出基于離散方法的API并行效率最高。

6 結(jié)語

對(duì)于Laplace變化，可以看出基于離散算法的API的并行效率最高，蒙特卡洛OpenMP效率最低。OpenMP編程模型比較適合迭代的并行計(jì)算。類似的我們還可以通過并行手段解決其他的并行計(jì)算問題。

參考文獻(xiàn)：

[1] 朱建偉，劉榮.多線程并行快速求解e值得六種方法[J].現(xiàn)代計(jì)算機(jī)，2013（6）.

[2] 薛小超，王克，朱朋海.基于多核并行的非線性方程蒙特卡洛計(jì)算方法[J].電腦知識(shí)與技術(shù)，2014（7）.

[3] 劉輝玲，葉峰.計(jì)算多重積分的均勻隨機(jī)數(shù)蒙特卡羅法的實(shí)現(xiàn)[J]電腦知識(shí)與技術(shù)，2008（12）.

[4] 張繼偉.基于MPI的并行拉普拉斯變換算法及其應(yīng)用研究[D].湖北大學(xué)，2011.