標籤：

【HPC向】1. Conways Game of Life-OpenMP

04-24

(封面圖片：CC BY-SA 3.0 來自:Bandwagonman at English Wikipedia)

本節，我們用簡單的OpenMP shared memory 方法對Conways Game of Life進行並行化處理。OpenMP恐怕是最簡單的並行方法了，零並行基礎的人可以很快掌握，並且切實減少計算時間。當然，你如果是從事大規模並行，一定知道OpenMP的局限，不適合跨節點運行。

OpenMP這種shared memory 方法，在量化計算裡面非常適合，因為大量矩陣運算這樣數據頻繁交換更喜歡shared memory方式。另外intel 提供的mkl數學庫，就有OpenMP版本，幫你加速矩陣運算，快速傅里葉變換。

異構計算、圖形處理器的相關並行，架構也幾乎類似shared memory方法。例如OpenACC，CUDA, OpenCL這些。學會OpenMP可以觸類旁通。

在開始並行編程之前，我們介紹衡量並行程序好壞的一些指標：加速比（speedup ratio），並行效率（parallel efficiency）。

加速比 S , T_1 是單個計算核心計算耗時， T_N 是N個計算核心計算耗時。

S=frac{T_1}{T_N}

理想情況下， S=N

並行效率 E

E=frac{S}{N}

理想情況下， E=1 ,並行效率通常在在1以下，但有例外。

1. Fortran中的二維數組

在編寫並行代碼之前，應該了解一下Fortran的二維數組存儲問題，當然這是Fortran的常識性問題。Fortran與C存儲二維數組方式不同，Fortran是按照列去存儲，對於如下數組,

real(kind=8) :: A(3,4)

數組在堆棧中的存儲順序為，

A(1,1) A(2,1) A(3,1) A(1,2) A(2,2) A(3,2) A(1,3) A(2,3) A(3,3) A(1,4) A(2,4) A(3,4)

這個很重要，當數組很大時候，我們做數組循環，更希望指針沿著堆棧連續讀取，而不是來回跳躍。也就是，我們要這樣循環，

do j = 1,N do i = 1,N opt(A(i,j)) enddoenddo

對於多個線程處理，我們更希望線程在做讀取操作時候，也是連續沿著堆棧走，而不是跳躍。

2. OpenMP並行編寫

OpenMP 是一個API，有編譯器提供，有不多的語法，在此不想贅述。語法建議在如下網站上學習，

OpenMP?

computing.llnl.gov圖標

重要的是並行計算的邏輯問題，OpenMP 是shared memory 模型下的一個並行工具。這樣，重中之重是區分哪些變數是位於共享內存(SHARED)中，那些變數是每個進程所獨自佔有的（PRIVATE），一旦明白這個概念，並行模型就完成了（如果不考慮負載均衡）。

對於Conways Game of Life，共有變數無非是記錄生命狀態的那個矩陣。這裡值得注意的是，我用兩個矩陣stat，stat_new。stat是一個只讀的二維數組，stat_new是直進行寫操作的二維數組，這樣很安全。多個進程處理一份共享的數據時，千萬小心讀寫同步這樣情況，處理不當輕則數據混亂，重者出現死鎖。

核心二重循環代碼在上一節。這裡我們用四種方式對二重循環進行並行，分別測試。

! 記為 ji-OUT!!$OMP PARALLEL SHARED(stat,stat_new) PRIVATE(i,j,k,l,i2,j2,sur_live)!$OMP DOdo j = 1,N do i = 1,N ...... enddoenddo!$OMP END DO!$OMP END PARALLEL

! 記為 ij-OUT!!$OMP PARALLEL SHARED(stat,stat_new) PRIVATE(i,j,k,l,i2,j2,sur_live)!$OMP DOdo i = 1,N do j = 1,N ...... enddoenddo!$OMP END DO!$OMP END PARALLEL

! 記為 ji-INNER!do j = 1,N!$OMP PARALLEL SHARED(stat,stat_new) PRIVATE(i,j,k,l,i2,j2,sur_live)!$OMP DO do i = 1,N ...... enddo!$OMP END DO!$OMP END PARALLELenddo

! 記為 ij-INNER!do i = 1,N!$OMP PARALLEL SHARED(stat,stat_new) PRIVATE(i,j,k,l,i2,j2,sur_live)!$OMP DO do j = 1,N ...... enddo!$OMP END DO!$OMP END PARALLELenddo

區別在於，i j循環的順序，並行結構體的位置。這其實是四種截然不同的並行方式。在此之前，我們要把畫布改大，改成1024×1024的還算可以。這樣效果明顯一些，同時關掉 寫文件的那個函數，目前暫不涉及並行讀寫文件。

3. 並行測試

我們粗略對上述四種方法進行並行測試，得出以下曲線。

測試用intel fortran 2013編譯。

四種並行編寫方式，給出不同的wall time以及加速比。當然，我的並行測試沒有嚴格控制變數。OpenMP有編譯器提供，因此與編譯器優化有關。

在OpenMP內部，對循環的處理，我們可以僅僅當成黑箱子。因此實際工作中要多測試一些，不能憑藉「原理」去理所應當地書寫代碼。

量化計算，這樣的例子非常多，例如雙電子積分的四重循環，後自洽場計算的多層嵌套。還涉及海量數據積分矩陣的讀取。這部分Multithread 的編寫夠做幾篇文章了。

儘管OpenMP很簡單，但是這種並行方式可控性不高，大規模程序出現多線程bug，鎖，極難調試出來。你如果寫一個簡單程序，日常工作中OpenMP會很快減少計算時間。

下一部分，講MPI處理這個問題，用信息傳遞角度親自編寫不共享內存的並行方式。


推薦閱讀：

TAG:OpenMP | 並行編程 | 並行計算 |