2014全國并行應(yīng)用挑戰(zhàn)賽初賽技術(shù)報告模版

應(yīng)用程序簡介應(yīng)用程序運行環(huán)境應(yīng)用程序分析應(yīng)用程序運行和優(yōu)化過程應(yīng)用程序運行和優(yōu)化結(jié)果1.應(yīng)用程序簡介3D

Elastic

Wave

Modeling（簡稱3D-EW），三維彈性波模型。3D-EW方法是一種用波場延拓的方法來模擬彈性波在各

向同性的彈性介質(zhì)中

的方法。在這個程序中，縱波（P波）和橫波（S波）被分別模擬，這樣可以更好地得知縱波和橫波在彈性介質(zhì)中的傳遞。該方法可以通過高階有限差分方法來模擬彈性波的傳遞。3D-EW廣泛應(yīng)用于石油和天然氣勘探領(lǐng)域。這個應(yīng)用 在參加ASC14，2014世界大學(xué)生超級計算機競賽時，取得了滿分的好成績。如今 在之前的代碼上進一步優(yōu)化，取得了大約15%的提升。2.

應(yīng)用程序運行環(huán)境硬件環(huán)境：CPU:

2×In Xeon

E5-2670(8

Cores,

2.6GHz,

20MB

Cache,8.0GT)Mem:

64GB(8×8GB)

ECC

Registered

DDR3

1600MHz

Samsung

MemoryMIC：In Xeon

Phi

5110P

Knights

Corner環(huán)境：OS:

Red

Hat

Enterprise

Linux

Server

release

6.3

(Santiago)Kernel:2.6.32-279.e16.x86_64In compiler:13.1.1

(gcc

version

4.4.6

compatibility)并行接口：OpenMP輸入規(guī)模：case1:360*360*280的介質(zhì)區(qū)域，100單位時間，模擬20次波傳遞case2:360*360*280的介質(zhì)區(qū)域，500單位時間，模擬1次波傳遞注：波 的范圍隨著時間加大。在case1中，波只 了該區(qū)域1/30不到的空間，在case2中就已經(jīng)充滿了整個區(qū)域，所以雖然第二次算例只模擬一次波的

，運算量卻大大超過算例13.應(yīng)用程序分析這個程序的代碼并不長，只有幾百行。沒有自編函數(shù)和類，是典型的面向過程的程序。程序需要一個輸入文件和兩個輸出文件。輸入文件包含了許多參數(shù)，輸出文件包含兩個，一個是真正的輸出文件，輸出一組參數(shù)；另一個是log文件，記錄程序的輸入信息和運行時間。3.應(yīng)用程序分析程序的結(jié)構(gòu)如右邊的圖所示。程序主要是由一個ishot循環(huán)和一個lt循環(huán)構(gòu)成，其中ishot每次循環(huán)不需要迭代，lt循環(huán)前后需要迭代數(shù)據(jù)。在計算各點參數(shù)時，實際上也是一個kji的三層循環(huán)（kji對應(yīng)區(qū)域的長寬高）。每次ishot循環(huán)完成后都要輸出一組數(shù)據(jù)，為高度為169的點的一個參數(shù)。最終運行完以后會統(tǒng)計程序運行時間并輸出時間。驗證程序輸出是否正確需要用到另一個專門檢驗誤差的程序。在這個程序中，如果和原程序輸出的誤差在規(guī)定范圍內(nèi)，程序輸出就算正確。4.應(yīng)用程序運行和優(yōu)化過程程序的I/O很少，熱點集中在對各點的參數(shù)計算那一部分。主要的瓶頸則在CPU的計算部分1：因為源代碼是串行程序，用OpenMP與在單節(jié)點上達到并行效果，提高效率2：用OpenMP進行線程級并行以后，使用向量化進一步提高性能3：通過OpenMP并行+向量化后，程序在CPU上獲得了非常好的加速效果，之后

嘗試在CPU+MIC上進一步提升性能4：使用傳統(tǒng)編程方法優(yōu)化后，發(fā)現(xiàn)MIC上雖然已實現(xiàn)并行和向量化，但是性能遠遠低于理論值，通過閱讀大量文獻以及查看生成的匯編代碼，發(fā)現(xiàn)編譯器生成了大量的低效率的gather/scatter指令，運用底層的Cintrinsic指令改寫代碼，使得程序變得更有效率，單M性能達到最優(yōu)版本（OpenMP+SIMD）代碼在CPU上性能的兩倍。5：最后，根據(jù)程序的情況，修改了算法中不合理的地方，同時在向量化方面取得了 優(yōu)化，使得程序性能進一步提高。4.應(yīng)用程序運行和優(yōu)化過程優(yōu)化方法1：用openmp使得程序有線程級并行注：并非每一處的openmp優(yōu)化的pragma都一樣，此為示例返回4.應(yīng)用程序運行和優(yōu)化過程優(yōu)化方法2：使用simd使得程序做到向量化注：實際上向量化并不都是這么簡單，有些地方需要手動展開循環(huán)，有些地方要修改運算步驟返回4.應(yīng)用程序運行和優(yōu)化過程優(yōu)化方法3：將程序由cpu運行改寫為CPU+MIC運行，具體方法是把一部分cpu的計算轉(zhuǎn)移到MIC上去原代碼改進代碼{}…//計算{…//一部分計算}#pragmaoffload

(mic){…//另一部分計算}{…//host與MIC通信}注：這是CPU+MIC

思路，在之后的程序相比這時其實做了非常多的調(diào)整，但 并沒有改變起先， 在規(guī)劃CPU+MIC的運算時，想的方法是在ishot上進行拆分，前后的ishot沒有數(shù)據(jù)依賴，通過ishot進行并行，好處是數(shù)據(jù)傳輸少后來 發(fā)現(xiàn)，有些算例nshot只有1，比如case2。這種時候這個方法就不合適了。在后面的優(yōu)化方法中，拆分的方法為區(qū)域分解，在運算中把波的區(qū)域分成兩個部分，一部分放在CPU上運行，另一部分放在MIC上運行。兩個需要的數(shù)據(jù)傳輸了，但這個方法的泛用性更高。返回4.應(yīng)用程序運行和優(yōu)化過程原程序部分代碼：這個循環(huán)是在剛才流程圖中，這個部分里的一段可以看出，循環(huán)內(nèi) 數(shù)組的跨度很大，空間局部性比較差，這也是為什么，普通

在MIC上取得的優(yōu)化非常有限，一定要使用C

intrinsic修改代碼才能達到比較好的效果4.應(yīng)用程序運行和優(yōu)化過程優(yōu)化方法4：程序本身對MIC并不算很友好，所以要改寫成對MIC友好的代碼，具體方法是用Cintrinsic改寫代碼，可以使Cache存取效率得到大幅度提高并避免編譯器生成的低效率指令原代碼

C

intrinsic代碼返回4.應(yīng)用程序運行和優(yōu)化過程優(yōu)化方法5：最后

時發(fā)現(xiàn)算法還有一個可以改進的地方，把原本的數(shù)組值傳遞改為了地址傳遞，使得效率進一步提高原代碼 改進代碼for(….){…up2[…]=up1[…];up1[…]=up[…];…}Double

*tmp

=

up2;up2=up1;up1=up;up=tmpPS：這兩步是在ASC14之后，在這次比賽中采用的新的優(yōu)化4.應(yīng)用程序運行和優(yōu)化過程優(yōu)化方法6：向量化之前有不完善的地方：在一這個三層循環(huán) ，包括2個小循環(huán)與其他代碼。自 量化不是在三層循環(huán)的最內(nèi)層展開，而是在2個小循環(huán)處展開，結(jié)果剩下的一小部分代碼就沒有做到向量化

1：這兩個小循環(huán)都是常數(shù)循環(huán)。為此 手動展開了這兩個循環(huán)。2：即使如此向量化還是沒有完成，后來發(fā)現(xiàn)是因為之前未循環(huán)的代碼中有一部分的存在使得向量化無法成功。幸運的是，這一部分可以寫在循環(huán)外面，做了這些改進了，向量化效果進一步提升了。4.應(yīng)用程序運行和優(yōu)化過程優(yōu)化方法6：原代碼

改進代碼1：for

(…){for

(kk=1;kk<5;++kk){…//循環(huán)代碼A（向量化）}…//代碼B（未向量化）}for

(…){…//循環(huán)代碼A（kk替換為1）…//循環(huán)代碼A（kk替換為2）…//循環(huán)代碼A（kk替換為3）…//循環(huán)代碼A（kk替換為4）…//循環(huán)代碼A（kk替換為5）…//代碼B}4.應(yīng)用程序運行和優(yōu)化過程優(yōu)化方法6：原代碼

改進代碼2：….….最后在循環(huán)外面添加5.

應(yīng)用程序運行和優(yōu)化結(jié)果優(yōu)化匯總注：最開始的CPU+MIC的性能并不好，可以看到在case1里面提升很少，實際上，這里cpu承擔(dān)了70%的工作（20個shot中的14次shot）而MIC只做了30%的工作，但即使如此MIC的時間仍然遠遠超過單用CPU的時間（128秒可以看做MIC算30%數(shù)據(jù)的時間+傳輸時間）。按照未加入C

intrinsic的代碼，2塊CPU的工作效率是MIC的10倍以上。case2的中，shot只有1次，所以只能100%CPU處理或者100%MIC處理，所以這里沒有用最初的cpu+MIC測case2。優(yōu)化時間（case1）提升（case1）加速比（case1）時間（case2）提升（case2）加速比（case2）原始404.001.004544.001.00修改，用openmp并行40.708.939.93368.0011.3512.35手動做simd向量化36.7010.0111.01263.0016.2817.28cpu+mic128.002.163.16///mic上添加intrinsic，手動做數(shù)據(jù)對齊62.505.466.46195.0022.3023.30改進數(shù)組傳輸，減少計算量61.805.546.54179.0024.3925.39完善向量化60.005.736.73169.0025.8926.895.應(yīng)用程序優(yōu)化結(jié)果126.8911.013.156.466.546.7317.2812.35123.3024.399.92CPUCPU+MIC5.應(yīng)用程序優(yōu)化結(jié)果在本次應(yīng)用中，

發(fā)現(xiàn)，對3D-EW這種訪存數(shù)據(jù)跨度比較大的程序，傳統(tǒng)的優(yōu)化 在MIC上效果不是很大，甚至性能不如CPU。 最終只能通過底層的C

intrinsic編程指令集消除編譯器生成的低效率代碼，發(fā)揮MIC架構(gòu)核多、向量化寬度大的優(yōu)點，并最終發(fā)揮出MIC的性能優(yōu)勢，使其在計算能力獲得近2倍于最優(yōu)化版本CPU程序在8核CPU上的性能。從剛才的表上可以看出，在case1中，MIC只占30%的計算量，時間就已經(jīng)達到了128秒，而純CPU的最佳版本，運行完整個應(yīng)用只要36秒。由于這個CPU+MIC版本中I/O部分很少，如果簡單用128/0.3，時間會達到

400秒以上，幾乎與串行CPU版本沒有差異，而最佳CPU版本的速度在它。按照這個比例case2中，自己估計甚至不止這個10倍以上，而此時兩者用了完全相同的優(yōu)化純MIC版本至少也需要4500秒才可能跑完，據(jù)數(shù)。雖然在case1中，cpu+mic的最終版本的時間比單用cpu少，但這時因為傳輸 了太多的時間。case1的計算量遠遠小于case2，但其中每次傳輸?shù)牟糠謪s是一樣的。最終版本的cpu+mic程序中，在規(guī)模一樣的情況下，傳輸?shù)臄?shù)據(jù)與shot*lt成正比。如此看來，計算量遠遠超過case1的case2，傳輸量卻只是case1的1/4。這也就可以得知，為何在case2中，cpu+mic的性能會比純cpu好不少。優(yōu)化工作亮點之一是通過寫底層的Cintrinsic代碼，把3D-EW這個程序，從本身的MIC不友好，CPU的速度遠超過MIC，改進成一個對MIC比較友好的版本。在最完美的版本中，CPU與MIC上的負載比例為4:5，也就是說，1塊M

可以得到2.5塊cpu（8核）的速度。盡管如此，由于host和MIC間需要做大量的 ，性能提升的紅利被數(shù)據(jù)傳輸 了很多。之所以得到這種結(jié)果，是因為 對MIC編譯器做了深入的研究。我們發(fā)現(xiàn)，如果不手動使用C

intrinsic編寫代碼，編譯器就會調(diào)用很多低效率指令，從而造 能嚴重