多線程并行快速求解Pi的方法

于朋

摘 要 本文首先分別應用不同的求Pi方法分析講解了WinAPI、OpenMP、MPI三大并行算法中常遇到的一些問題，根據問題提出了相應的解決方案。另外實現了對BBP算法的初步并行化，大大縮減了該算法的運行時間。文章最后利用三種方法求解了蒙特卡洛算法求Pi，并對比分析了三種算法的優缺點。

【關鍵詞】WinAPI OpenMP MPI

1 問題背景與提出

隨著技術的發展，單片機越來越難滿足人們對于大量數據處理的需求，因此，人們越來越依賴于利用并行計算技術來解決程序規模龐大，運算時間長及數據量大的課題。本文即對當下比較常用的幾種并行技術WinAPI、OpenMP、MPI三種并行模式進行討論課研究，并以計算π值為例，將并行模式與串行模式進行對比，研究并行計算的機理、優缺點及一些常見問題。

2 模型建立

2.1 蒙特卡羅思想，蒲風投針實驗

（1）取白紙一張，在上面畫許多間距為d的等距平行線；

（2）取一根長為l（l

（3）直線與針相交概率p的近似值可用m/n得到，進而可得到圓周率的近似值為2nl/md。

2.2 級數方法

2.3 并行BBP算法

當今世界在進行計算機性能測試時往往選擇在一定時間內計算Pi值得位數，而最常用的算法之一就是BBP算法。該算法不需要多精度浮點算術運算的支持，在支持IEEE浮點運算的通用計算機上即可進行計算而且該算法只需要非常少的內存。BBP算法也是目前算法中非常適用于并行計算的算法。

公式為：

3 算法描述與實現

3.1 API實現

Windows實現多線程并行計算時會產生數據競爭，數據競爭（Data racing）導致計算結果不準確。產生錯誤的原因在于兩個線程在同時訪問同一內存區域時，且一個線程在進行寫操作。為此采用同步技術，利用臨界區解決此問題。由于本次試驗中，數據計算量較小，所以基本不會產生數據競爭的錯誤，但是一旦運行計算量較大或者在共享量上運算時間較長的程序時，就會產生數據競爭，在本例中，我們以cout輸出程序為引子，觀察使用臨界區和不使用臨界區的區別：

代碼如下：

}

pi= count*4.0 / numSteps；

//EnterCriticalSection（&cs）；

cout << piSum<< " " << threadID << endl；

piSum+= pi；

// LeaveCriticalSection（&cs）；

我們將輸出程序置于piSum值之前，由于cout運行時，在屏幕上顯示需要消耗較大時間，所以就會有機會產生數據重疊或者兩者讀到了一樣的piSum值。（如圖1所示）。

所以，當我們使用臨界區后結果為：（如圖2所示）。

另外，臨界區的設定也直接影響計算速度，所以盡量縮小臨界區有利于提高運行速度。

線程取值過大的影響：

3.2 OpenMP實現級數方法

OpenMP是一種面向共享內存以及分布共享內存的多處理器多線程并行編程語言，是一種能夠被應用于顯式指導多線程、共享內存并行的應用程序編程接口（如圖3所示）。OpenMP具有良好可移植性，支持多種編程語言。parallel for 循環并行化利用編譯指導語句parallel for 并行原理是采用工作分配的執行方式，將循環所需要的工作量按一定方式分配到各個線程，所有線程執行工作總和是原串行完成的工作量。parallel for 根據CUP的大?。ň€程數多少）按工作量平均分配，對于線程數為8個，這里蒙特卡洛方法工作量取numSteps=10，000，000步，則每個線程要計算（1/8）*numSteps步的工作量。要特別注意的是在這里必須避免數據競爭（Data racing），采用的方法是對競爭變量私有化，使用private（t，fun，...）。

核心代碼：

double Pi（double x）

{

omp_set_num_threads（numThreads）；

int sign = 1；

#pragma omp parallel for reduction（+：c[omp_get_thread_num（）]）

for （int i = 2； i < N； i++）

{

c[omp_get_thread_num（）] += 4 * x；

sign = sign * （-1）；

x = sign /double （2 * i - 1）；

}

這個算法中，我們發現運行后，串行時間和并行時間是基本一致的：

這個問題在于x，sign的值為共享量，當不同的線程在調用時存在等待的時間，所以如果將這些值私有化，則可以解決這些問題。由于使用private時，各個私有變量必須在for中有定義，即在進入并行區時，for循環中的所有私有變量是需要重新定義的，因此我們必須使得x，sign等變量在定義時全部使用已知量來定義

#pragma omp parallel for private（x，y）reduction（+：pi）

for （int i = 1； i < N； i += 2）

{

y = 1 / double（2 * i - 1）；

pi = pi + 4 * y；

x = -1 / double（2 * （1 + i） - 1）；

pi = pi + 4 * x；

}

因此程序完美的解決了并行問題。（如表1所示）。

3.3 BBP算法的實現

MPI是專門為集群和多節點并行計算語言，運行效率高，實現方式多樣，可以進行主從式、并列式以及流水線式等方式的實現。在利用計算機多核CPU，模擬多個節點的實現方式。改造成主從式程序，利用0號節點作為主節點收發數據，也參與計算，而其他節點只進行計算，為負載均衡選擇詳盡的計算量運行到不同的節點上。

根據BBP算法（如圖4所示）我們將整個運算分成4個部分，分別用一個線程進行運算，其運算總時間約等于線程中運行時間最長的那個（計算結果如表2所示）。

3.4 API、OpenMP、MPI對比實驗

我們以蒙塔卡羅算法為例，分別采用API、OpenMP、MPI三種并行方式對值進行計算，來對比其運算效率和運算精度（計算結果如表3所示）。

4 結論

（1）MPI模擬多節點計算的速度是最快的，而且計算結果也是最接近穿行結果的，所以MPI適合計算大規模的較為精確的求解問題。

（2）WinAPI實現用臨界區的效果最差，而且WinAPI的計算速度很大程度也和臨界區的設定有關，盡量縮小臨界區有利于提高并行速度。

（3）WinAPI實現用線程號為每個線程分配不同的任務，分配過程需要人為干預，對于函數復雜的程序來說，實現繁瑣，不利于使用。

（4）數值計算時要根據實際情況選擇和改造算法。比如在計算值就比e更適合并行。而且每種并行方法都有它的特使要求，比如在使用parallel for private時，由于變量進入for循環后屬于重新定義，所以不能出現自己為自己賦值的情況，需要按照程序一步步展開來寫，相對繁瑣。

參考文獻

[1]多核系列教材編寫組.多核程序設計[M].北京：清華大學出版社，2007.

[2]朱建偉，劉榮.多線程并行快速求解e值的六種方法[J].現代計算機，2013.

[3]張翔圓.周率Pi的BBP多核并行算法實現[J].普洱學院學報，2013.

作者單位

中國石油大學（華東）理學院 山東省青島市 266500