熊 敏，王勇獻

(國防科學技術大學計算機學院，湖南 長沙 410073)

面向CPU+MIC混合異構平臺的地震波疊前時間偏移算法并行與優(yōu)化策略*

熊 敏，王勇獻

(國防科學技術大學計算機學院，湖南 長沙 410073)

地震波的疊前時間偏移算法是構造復雜巖層成像最有效的方法之一。地震勘探進入海量數據時代，且疊前偏移算法是數據處理中最費時的環(huán)節(jié)，對疊前偏移算法做并行計算優(yōu)化有著重要的研究意義。近年來，高性能并行計算開始進入異構、眾核時代，以Intel新一代至強融核MIC(Xeon Phi)為例，新型眾核處理器具有成本低、性能高等特點。從最經典的Kirchhoff疊前時間偏移 (PKTM) 算法出發(fā)，基于CPU+MIC異構平臺，采用offload編程模式實現對PKTM算法的并行移植與性能優(yōu)化，對于6 000萬規(guī)模(8 000×8 000)的應用問題，總的并行模擬時間從357.52 s減少到1.66 s，性能提升了214.37倍。

協同并行；Intel至強融核；異構并行；Kirchhoff疊前時間偏移；性能優(yōu)化

1 引言

對地底巖層構造進行成像是石油、天然氣勘探開發(fā)，以及地震勘探等領域的重要環(huán)節(jié)。地震波的疊前時間偏移算法是構造復雜巖層成像最有效的方法之一。Kirchhoff疊前時間偏移PKTM(Prestack Kirchhoff Time Migration)算法具有成像效率高、對速度模型要求低的優(yōu)點，能適應縱橫向速度變化較大的情況，同時還適用于大傾角的偏移成像，因此在構造復雜的地區(qū)，其優(yōu)勢更為突出。該算法自20世紀90年代起，逐漸成為地震勘探數據處理的常用成像手段[1]。圖1顯示的是PKTM算法的反演過程，圖1a是地下模型空間，圖1b數據空間，圖1c是反演獲得的模型空間，對于如漢字這樣復雜的形狀，PKTM算法仍然具有很高的還原度。隨著地震勘探進入海量數據時代，對計算資源的需求日益增加，疊前偏移算法是數據處理中最費時的環(huán)節(jié)，對疊前偏移算法進行并行計算優(yōu)化有著重要的研究意義。

Figure 1 PKTM migration process

近年來，高性能計算開始進入異構、眾核時代，異構眾核是大規(guī)模并行計算機的發(fā)展趨勢，新型眾核處理器具有成本低、性能高等特點。以Intel新一代至強融核MIC(Xeon Phi)為例，單個MIC設備擁有50個以上的處理器核，并采用寬向量(512位)設計，能夠提供1 TFlops雙精度浮點運算的性能，同時MIC還具有通用編程環(huán)境(Fortran、C 和 C++)、低功耗性能比、支持異構應用等優(yōu)勢[2]。Intel針對MIC推出一系列軟件工具鏈，以支持基于MIC的軟件開發(fā)，當前CPU+MIC異構平臺主要有四種編程模式：CPU原生模式、CPU為主MIC為輔模式(又稱offload模式)、CPU和MIC對等模式、MIC為主CPU為輔模式。最新TOP500[3]蟬聯第一的“天河二號”超級計算機即以MIC作為加速部件。針對不同領域應用問題的模型和計算特點，結合MIC的體系結構特點，研究在該處理器平臺上的性能優(yōu)化已經成為當前的研究熱點之一。

受益于硬件平臺的不斷更新與發(fā)展，地震波疊前時間偏移計算方法的性能在過去一段時間也持續(xù)獲得較大的提升。Bhardwaj D等人[4]利用MPI實現疊前偏移算法優(yōu)化，使偏移計算效率提高了近30%。王華忠等人[5]在集群系統中利用OpenMP多線程并行方法，優(yōu)化了三維Kirchhoff積分法偏移實現方案。張清等人[6]利用CUDA編程模型在GPU平臺上設計實現了靜態(tài)8點并行插值算法，性能是CPU動態(tài)插值算法內核的22.76倍。隨著MIC等新型眾核系統的出現，如何在CPU+MIC的異構平臺上，充分結合硬件體系結構特點與疊前時間偏移算法本身的特點，來做并行性能優(yōu)化，仍是一個值得探索的問題。本文從最經典的Kirchhoff疊前時間偏移 (PKTM) 算法出發(fā)，基于CPU+MIC異構平臺，采用offload編程模式實現對PKTM算法的并行移植與性能優(yōu)化。

2 地震波疊前時間偏移算法

在經典的Kirchhoff疊前時間偏移(PKTM)算法中，定義了兩個空間，一個是模型空間，簡記為x-s空間，是對地底巖層構造的刻畫，其離散下標記為(ix,is)；另一個為數據空間，簡記為y-t空間，是對儀器成像數據的刻畫，其離散下標記為(iy,it)。PKTM算法的實質是根據成像數據各像素的取值來反演、“復原”原始地底巖層構造的過程，具體來說，對于某個模型空間點(x,s)而言，按照成像原理與規(guī)律，若它會在數據空間內的點(y,t)處成像(該點未必唯一)，則需要滿足式(1)：

(x-y)2=v2(t2-s2)

(1)

其中v是與波傳播速度相關的一個常數。PKTM算法就是根據這一原理進行實現的，圖2為經典PKTM算法的核心實現流程[7]，其優(yōu)點是在復雜邊界條件下仍然能保持計算穩(wěn)定[8]。

Figure 2 Classical PKTM algorithm

圖2 經典Kirchhoff疊前時間偏移(PKTM)算法流程

算法的主體部分是用一個三重循環(huán)操作data和modl兩個數組，其時間復雜度為O(nx2×nt)，空間復雜度為O(nx×nt)。

3 移植和優(yōu)化方法

根據PKTM的實現過程與計算特點，本文將從四個層次對PKTM算法進行移植和優(yōu)化：算法層次的優(yōu)化、串行程序性能優(yōu)化、單一平臺上的多線程并行以及CPU+MIC異構平臺上的混合并行。

3.1 算法層次的優(yōu)化

本文首先分析原始算法的時間復雜性，并嘗試降低一個量階時間開銷的快速算法，基于新的快速算法探索進一步縮小迭代空間、提升加速效果的技術。

3.1.1 快速PKTM算法

由圖2中的經典PKTM算法流程可知，該算法的核心是計算數組下標，其中當給定模型空間下標(ix,is)以及數據空間的第一維下標iy時，計算數據空間的下標it是最費時的部分，要用到加減乘除及乘方、開方、取整等運算，即:

t2=(x-y)2/v2+s2,it=[t/dt]

(2)

其中[ ]表示取整運算符。注意到計算t時等號右邊第一項僅依賴于x與y的差值，因此若作變量替換ib=iy-ix，則可直接針對ib進行遍歷，避免對(ix,iy)的組合進行遍歷，從而達到降低遍歷空間開銷的目的。受此啟發(fā)，Claerbout J F和Black J L在經典算法基礎上進行改進，提出快速PKTM算法實現，流程如圖3所示[5]?？焖偎惴ㄊ购诵挠嬎悴糠旨性诙匮h(huán)的內部，時間復雜度從經典算法的(nx2×nt)降低到了O(nx×nt)。

Figure 3 Fast PKTM algorithm

圖3 快速Kirchhoff疊前時間偏移(PKTM)算法

3.1.2 提前確定迭代次數

在圖3的快速PKTM算法中，第6行有一個分支判斷，以確定是否產生了有效的it下標值，且僅當it有效時才執(zhí)行第7～9行的數據更新過程。由于第6行it有效性判定準則it

b2/v2+s2

(3)

注意到不等式左邊為平方和的形式，它是變量b和s的遞增函數，因此在第2～11行的循環(huán)迭代中，一旦某個ib值(不妨記為ibMax)導致第6行的it值越界無效，則后續(xù)更大ib值的迭代也同樣產生無效的it取值，因此可直接跳過這些后續(xù)的ib迭代，從而避免后續(xù)迭代中冗余的it計算。事實上，也可預先計算能產生有效it值的ib迭代范圍[0,ibMax)，達到同樣的目的。提前判斷出it的有效性也就是提前確定了迭代的次數，這種方法的好處是避免了無效it的計算，減少核心計算部分的計算次數。

為了有效量化這種技術帶來的收益，先將公式(3)寫成如下等價形式：

(4)

這表明在b-s平面(或者等價的整數坐標ib-is平面)上，能產生有效it值的范圍是一個橢圓在第一象限和第二象限所包圍區(qū)域的內部(圖4中I所示)。圖4中橫軸表示ib的取值，縱軸表示is的取值，橢圓內部為滿足公式(4)的范圍，以nx和-nx為頂點的大矩形框內部表示圖3第1～2行的全部迭代空間范圍，本方法將ib的取值縮小到橢圓的頂點ibMax和-ibMax，兩個矩形框之間的部分(圖4中II所示)即為本方法所節(jié)約的迭代范圍。以nx=8 000，nt=8 000，dt=0.004，dx=25，v=1 000為例，經過簡單計算可知迭代空間大小從1.28×108減少為2.048×107，避免了約84%的無效迭代。

Figure 4 Ellipse relationship between variables ib and is

3.1.3 利用對稱性減少迭代次數

觀察圖4，發(fā)現產生有效it的區(qū)域具有對稱性，即圖4中橢圓在第一象限和第二象限所包圍區(qū)域左右對稱，同時通過3.1.2節(jié)的方法優(yōu)化后所確定的迭代范圍也具有對稱性，即與橢圓相切的矩形區(qū)域同樣左右對稱?？紤]到公式(1)中計算t的過程用到的是b-s平面中點的坐標的平方值，而在對稱區(qū)域中，對稱點的坐標的平方值相同，因此可以利用此特性減少迭代次數以及核心計算的次數。圖5為本方法的優(yōu)化示意圖，優(yōu)化代碼將ib=0的情況進行特殊處理，剩下的兩個部分完全對稱，ib的迭代范圍縮小到(1,nx-1)，核心計算的次數也隨之減半。

優(yōu)化前 doib=-(nx-1),(nx-1) …if(it

優(yōu)化后 doib=0,0 …(單獨處理ib=0情形)enddodoib=1,nx-1 …(核心計算:計算it的值) if(it

Figure 5 Optimization method of symmetry to reduce loop cycles

圖5 利用對稱性減少迭代次數示意圖

3.2 串行程序的性能優(yōu)化

在算法層次進行優(yōu)化之后，本文對于串行程序進行了一系列優(yōu)化，包括優(yōu)化計算和優(yōu)化訪存兩個方面。

3.2.1 優(yōu)化計算

(1)常量計算提前。

圖3所示的快速Kirchhoff疊前時間偏移算法的流程中，第3～5行集中了平方、開方、除法和乘法等耗時的計算過程，是算法的核心計算部分。其中dx、dt、v、ds為常量，僅與常量相關與變量無關的計算只需要計算一次，就可以在每次迭代中使用，因此將這樣的常量計算提前到循環(huán)外部，可以有效減少計算的次數。對于公式(2)中對it的求解可以改寫成如下形式(ix-iy)：

(5)

改進前，除法運算和平方運算的運算次數約為4×nx×nt，而將常量計算提前后，除法運算的運算次數為1，平方運算的運算次數為2×nx×nt+2×nt+1。

(2)避免單雙精度混合運算。

兩種不同精度的數運算時，根據包容性，精度低的數需要先進行精度轉換才能保證計算結果的正確性。如單雙精度浮點數混合運算時，單精度浮點數將先轉換成雙精度數，然后再進行雙精度浮點計算。而精度越高，運算的開銷越大，因此如果僅使用單精度就能滿足的運算，應當避免與雙精度浮點數混合運算，從而減少高精度運算的額外開銷。

快速Kirchhoff疊前時間偏移算法中的所有計算過程，利用單精度浮點計算就足以保證精度。在具體代碼中，常常會用到一些浮點常量，如果沒有顯式標識為單精度浮點數，這些浮點常量將先被自動處理為雙精度浮點數，然后再與單精度的變量進行混合運算。為了避免單雙精度混合運算，應當在使用浮點常量時顯式地將其標識為單精度浮點數。

(3)SIMD向量化。

現代CPU處理器指令集普遍支持以單指令多數據(SIMD)方式執(zhí)行向量指令，充分利用好這些向量指令，可顯著提高應用程序性能。例如，在IntelXeon處理器上支持256位寬的向量寄存器及相對應的AVX或AVX2向量處理的指令，而在新一代MIC處理器上則支持512位寬的向量寄存器及相應向量處理指令，這意味著理想情況下，MIC上的一條指令可以并發(fā)處理16個單精度浮點數(每個單精度浮點數4字節(jié)、32位)的操作，較單指令單數據的標量處理加速16倍。

為了在應用程序中充分進行SIMD向量化，可以通過編譯器自動向量化、手工添加編譯指導語句、使用庫提供的向量數據類型編程、使用intrinsics編程以及內嵌向量化匯編指令等方式加以實現。為了在性能與程序移植性、可讀性等方面達到平衡，本文主要采用重構程序、使用編譯指導語句相結合以輔助編譯器自動向量化的方式。主要技術包括：①對內層對稱的ix迭代進行循環(huán)分裂，形成兩個循環(huán)結構，為了利用編譯器自動向量化，將其均修改為迭代變量逐次增加的形式；②在兩個最內層循環(huán)上加上#pragmasimd以告訴編譯器無需進行依賴性檢測，從而生成向量化指令。

3.2.2 優(yōu)化訪存

訪存是并行程序獲得良好并行效果的重要因素之一，并行程序的執(zhí)行過程中，由于循環(huán)變量有一定先后順序，可能出現訪問數據的順序與數據存放的順序不一致的情況，造成訪存局部性不好，發(fā)生訪問內存不連續(xù)的問題，訪存的不連續(xù)必將帶來額外的訪存開銷。解決這一問題可以根據循環(huán)的特點，對數據內存布局進行調整。

本文首先進行了循環(huán)交換優(yōu)化，但交換之后訪存的空間局部性不好，即相鄰兩次訪存的地址不連續(xù)，存在較大跨度。這是因為快速PKTM算法中的模型空間與數據空間均以二維數組的形式存儲，算法進行循環(huán)交換優(yōu)化之后，訪問二維數組的順序與數組在內存中存放的順序不一致，導致訪存不連續(xù)。為解決這個問題，可以通過調整數據內存布局，將二維數組在內存中的存放順序調整成算法循環(huán)過程中的訪存順序，以優(yōu)化訪存性能。數據內存布局調整前和調整后的訪存模式如圖6所示。

Figure 6 Memory access models before and after the exchange of loop variables

3.3 單一平臺上的多線程并行

不論是傳統CPU處理器還是新興MIC平臺均為多核或眾核體系結構，充分挖掘應用程序的并發(fā)性、提高多個處理器核心的利用率是提高應用程序性能的關鍵要素之一。在這種具有共享存儲特點的平臺上，主要通過OpenMP多線程模型實現并行，為此需要對應用程序進行深入分析和并行性發(fā)掘。

3.3.1 任務分解的多線程并行

為了實現方便，最初采用分割最外層ib循環(huán)的方式進行任務分解，每個任務分別處理一段互不重合的ib范圍，在整個模型空間及數據空間中進行遍歷，發(fā)現滿足有效性的點對(ix,is)和(ix±ib,it)，并完成相應的數據更新操作；多個任務并發(fā)處理，但由于不同任務中更新模型空間的位置有可能相同，為了避免線程級數據競爭，需要對模型空間點更新操作進行關鍵段保護(使用OpenMP的critical語句)或原子操作保護(使用OpenMP的atomic語句)。這種多線程并行在實現上只是針對循環(huán)書寫編譯指導語句，編程靈活、簡單，并行效率高。

上述OpenMP多線程實現會出現數據競爭，導致某些線程空閑等待，造成線程資源的浪費以及時間的消耗。避免數據競爭需要保證線程之間訪問的數據區(qū)域彼此不重合，需要對任務分解方案進行改進。

注意到PKTM算法的核心處理是對模型空間的nx×nt個離散網格點進行更新，由于各個離散網格點的更新過程相互獨立、互不影響，因此，本質上可并發(fā)處理。因此可以針對模型空間的數據分割進行任務分解，為了在并發(fā)性和并行粒度兩方面取得折衷，僅針對模型空間x-s平面中的s維進行一維分割，形成多個獨立的并行任務。采用這種新的任務分解后，每個任務僅遍歷模型空間的一個局部塊，彼此之間互不重疊，不會發(fā)生同時寫同一模型數據點的數據競爭；另一方面，盡管各任務間可能出現訪問同一數據空間點的情況，但由于是讀操作，不影響結果正確性，因此無需特殊處理。

在實現上，為了增大并行粒度，可簡單地將代碼中的ib循環(huán)與is循環(huán)進行交換，對最外層的is循環(huán)添加OpenMP編譯指導語句。由于采用第3.2.2節(jié)訪存優(yōu)化技術，這種循環(huán)交換后不會引發(fā)訪存性能問題。

3.3.2 多線程并行的運行配置與性能優(yōu)化

為了充分提升多線程并行程序的運行性能，還要考慮應用程序跟操作系統、硬件平臺間的協同問題，特別是任務調度及線程對處理器核的親和性問題。

由于通常線程數目受處理器資源所限，通常要遠小于并行任務的數量，采用何種策略將這些任務分配、調度到所有線程上，也會對性能造成直接影響，在下面的第3.4.2節(jié)專門詳細討論這個問題。

線程與處理器核綁定可以提高線程訪問CPU的Cache命中率，從而提高程序的并行性能。

3.4 CPU+MIC異構平臺上的混合并行

本文采用CPU為主MIC為輔模式，即offload模式進行CPU+MIC的混合并行。Offload模式適合串行計算程序中包含高并行計算部分，且并行部分并行度高的情況[9]。CPU+MIC混合并行的難點主要是任務分配和負載均衡的問題，混合并行的負載均衡涉及到不同計算能力的兩個平臺之間以及平臺內部各線程之間的負載均衡。下面將分別介紹這兩個層次的任務分配和負載均衡策略。

3.4.1CPU和MIC之間負載均衡

由于主頻與核數的不同，CPU與MIC之間的處理能力有差異，為了達到不同平臺之間的負載均衡，需要針對MIC和CPU的任務處理能力，對MIC和CPU的任務進行分配。本文用變量ratio表示上傳到MIC上進行處理的任務占總任務的比例，通過調整ratio的值，可以得到最優(yōu)的MIC與CPU任務數之比。當墻鐘時間最短時，認為MIC與CPU的任務比達到最優(yōu)，此時對應的ratio′( 1-ratio)的值即為最優(yōu)的MIC與CPU的任務比。

3.4.2 CPU或MIC內部多線程之間負載均衡

(1)采用動態(tài)任務調度策略。

任務調度策略包括動態(tài)任務調度和靜態(tài)任務調度。對于本應用，采用靜態(tài)任務調度策略會導致負載不均衡，采用動態(tài)任務調度策略則可以緩解負載不均勻的情況。

理論上，PKTM算法求得的數據空間下標it的值與負載量之間滿足以下關系：

(6)

其中，it為整數，且it∈[0,nt]。

公式(6)表明：對于確定的整數it，其負載量f(it)是可估算的，且負載量關于it遞減，負載量f(it)的函數圖像如圖7所示(nx=8 000，nt=8 000，dt=0.004，dx=25，v=1 000時)。不妨假設線程數為2，采用靜態(tài)任務調度策略時，任務將按照it遞增的順序交替分配給線程0和線程1，即所有it為偶數的計算任務交由線程0處理，所有it為奇數的計算任務交由線程1處理。假設分配給線程0和線程1的任務數相等，設為nTask，則線程0和線程1的負載量fp0和fp1可由公式(7)表示。

f(2)+…+f(2×nTask-2),

f(3)+…+f(2×nTask-1),

(7)

由于f(it)關于it遞減，因此有f(0)>f(1),f(2)>f(3),…,f(nTask-2)>f(nTask-1)，于是fp0>fp1，導致線程0和線程1之間的負載不均衡，且這種不均衡性會隨著任務數增加而更加明顯。

采用動態(tài)任務調度策略會根據線程的實際任務完成情況來分配新任務，負載不均衡的現象可以得到一定緩解。Vtune的實測結果也反映了這一點，詳見下一節(jié)內容。

Figure 7 Relationship between overload and variable it

(2)單個任務的粒度可調整。

為進一步解決負載不均衡問題，本文在采用動態(tài)任務調度的調度策略的同時，考慮利用chunksize變量調節(jié)任務的粒度。進行任務分配時的變量chunksize，其大小代表分配給線程的任務個數，chunksize的值越大，任務的粒度越大。本文將chunksize作為影響負載均衡問題的一個因素進行了一系列測試，通過調整chunksize值，測得一系列程序運行的墻鐘時間，其中，最短的墻鐘時間對應的chunksize值即為負載最均衡的chunksize值。

4 測試結果與分析

4.1 測試平臺與環(huán)境

為考察第3節(jié)各類優(yōu)化與效果，我們使用一個單結點的CPU+MIC異構計算機系統進行了測試。測試平臺的環(huán)境與參數如表1所示。

Table 1 Test platform and circumstance

4.2 典型優(yōu)化方法的效果

第3節(jié)提到的各種優(yōu)化方法相互之間有一定影響，所以單獨表示各個方法的性能比較困難。本文主要將之前提到的典型優(yōu)化方法融入到了3個主要版本中，測得問題規(guī)模為nt=8 000，nx=8 000時，幾個典型優(yōu)化方法的性能提升如圖8所示。

Figure 8 Performance improvement of classical optimization methods

圖8中，橫坐標為版本號，版本1(包括v1.0，v1.1和v1.2)均為基于經典PKTM算法的優(yōu)化版本，版本2(包括v2.0和v2.1)基于快速PKTM算法，版本3(包括v3.0和v3.1)為CPU+MIC協同異構平臺下的優(yōu)化版本。版本1主要進行的優(yōu)化包括編譯器優(yōu)化，Pthread改為OpenMP和提前確定迭代次數；版本2主要進行的優(yōu)化包括常量計算提前、循環(huán)交換、調整數組順序，利用對稱性減少迭代次數，線程動態(tài)任務分配；版本3主要是在版本2的基礎上進行MIC移植，改進了CPU與MIC之間的負載比例。

圖8的縱坐標代表獲得的性能提升，CPU的最優(yōu)性能在16線程的條件下獲得，性能提升的基準為經典PKTM并行算法的CPU性能；MIC的native模式最優(yōu)性能在180線程的條件下獲得，性能提升的基準為基于經典PKTM并行算法的MIC native模式性能；CPU+MIC的offload模式最優(yōu)性能在CPU端16線程、MIC端240線程×單MIC卡的條件下獲得，性能提升的基準為經典PKTM并行算法的CPU性能。具體性能提升如表2所示，最優(yōu)時間1.66 s與最原始的經典PKTM并行算法的357.52 s相比，性能提升了214.37倍。

Table 2 Performance improvement

4.3 問題規(guī)模取值對計算量的影響

問題規(guī)模對程序的計算量有一定影響，從而影響到優(yōu)化的性能。比如在快速PKTM算法中提前確定迭代次數的優(yōu)化方法，在固定規(guī)模nx=8 000，nt=8 000的條件下,it的計算量減少了約84%，對應不同規(guī)模的組合，減少的計算量也不同。

本文針對基于快速PKTM算法的提前確定迭代次數的優(yōu)化，測試了幾組不同規(guī)模對算法計算量以及性能提升的影響。測試結果如圖9所示。

Figure 9 Effect of scale combination on the amount of computation

圖9四幅圖的橫坐標代表ix的取值范圍，縱坐標是最大計算量比，表示對應一個具體ix，實際產生有效it時的計算量占優(yōu)化前計算it需要的計算量的比例。如圖9d中,ix=319時，最大計算量比為0.13，表示優(yōu)化前求it所進行的計算中，只有13%的計算產生了有效的it，而87%的計算量不滿足條件判斷。經過提前確定迭代次數的優(yōu)化，可以有效剔除無效計算，性能優(yōu)化的效果與問題規(guī)模的組合有關。如nx=2 000，nt=1 000時(如圖9d所示)，最大計算量比為0.13，在此組合下進行提前確定迭代次數的優(yōu)化至少能減少87%的計算量；而nx=1 000，nt=4 000時(如圖9c所示)，最大計算量比為0.9，優(yōu)化后能減少的計算量為10%，不如圖9d的效果好。

4.4 典型優(yōu)化方法效果展示

固定問題規(guī)模nx=8 000，nt=8 000之后，仍然有一些因素會對優(yōu)化性能造成一定影響，如3.4節(jié)提到的，將程序移植到MIC平臺上與CPU協同處理的過程中涉及到的負載平衡問題，任務調度策略會影響性能，同時線程任務粒度的大小對性能也有一定影響。

4.4.1 CPU或MIC內部多線程之間的負載均衡

之前介紹了CPU與MIC之間的處理能力有差異，因此需要針對MIC和CPU的任務處理能力，對MIC和CPU進行任務分配。圖10顯示了調整MIC與CPU任務分配比例對程序運行性能的影響。其中橫坐標為變量ratio(單位為0.1)，它表示分配到MIC端的任務數占總任務的比例，縱坐標代表按照ratio劃分任務后程序執(zhí)行的墻鐘時間。從圖10可以看出，當ratio約為0.5時，墻鐘時間最短，此時可以認為MIC與CPU之間的負載大致平衡，對應的MIC與CPU之間最優(yōu)任務數之比約為1∶1。

Figure 10 Allocation performance of load balance between MIC and CPU

4.4.2 動靜態(tài)任務調度策略

3.4.2節(jié)已從理論上分析了動態(tài)調度相較于靜態(tài)調度負載更為平衡，Vtune實測的結果也表明動態(tài)任務調度負載的優(yōu)勢。圖11是利用Vtune實測出的程序在不同任務調度策略下的運行情況。圖11a采用靜態(tài)任務調度策略，其中第五個線程是瓶頸，其結束時間最晚，且與其它線程的結束時間相差較大，程序實際運行時，其它運行結束的線程都在等待第五個線程結束，造成嚴重的資源浪費。圖11b采用動態(tài)任務調度策略，所有線程的結束時間相差很小，沒有線程空等的現象，資源利用率高，且與靜態(tài)任務調度策略相比，動態(tài)任務調度的墻鐘時間更短。

Figure 11 Load balance of static and dynamic scheduling

4.4.3 線程任務粒度大小

本文在考慮調度策略對性能造成影響的同時，也考慮了線程任務粒度(chunksize)對負載均衡造成的影響。進行任務分配時的變量chunksize，其大小代表分配給線程的任務個數，chunksize的值越大，任務的粒度越大。不同的任務粒度會影響程序的負載情況，經過實測得到chunksize與墻鐘時間的關系如圖12所示，其中橫坐標代表不同的chunksize的大小，縱坐標代表對應的程序運行墻鐘時間。由此可知，采取靜態(tài)任務調度，chunksize=6時墻鐘時間最短，負載相對平衡；采取動態(tài)任務調度策略，chunksize=5時墻鐘時間最短，負載相對平衡。

Figure 12 Effect of chunk size on load balance

5 測試結果與分析

本文針對Kirchhoff疊前時間偏移算法處理地震勘探數據的問題，基于CPU+MIC協同異構平臺，采用提前確定迭代次數、常量計算提前、循環(huán)交換、數據內存布局調整、利用對稱性減少迭代次數、線程動態(tài)任務分配、改進CPU+MIC負載比例等一系列方法對原始程序進行移植和優(yōu)化，對于6 000萬規(guī)模(8 000×8 000)的應用問題，總的并行模擬時間從357.52 s減少到1.66 s，性能提升了214.37倍。本文第4節(jié)的應用問題來源于中國計算機學會高性能計算專業(yè)委員會與Intel公司聯合舉辦的2013年全國教育科研并行應用程序優(yōu)化大賽決賽題目，作者所在團隊以本文優(yōu)化方法及效果獲得最高異構計算性能獎。

本文針對異構平臺計算能力的差異，進行了一系列的分析與測試，總結出影響異構平臺負載平衡的幾方面因素，并通過Vtune等進行了驗證，最終確定負載平衡的策略。本文進行的優(yōu)化和分析策略可以擴展到其它相似的異構程序移植中去。

后續(xù)工作主要可以從兩方面入手，一是可以進一步分析并行程序的可擴展性，二是針對更大的問題規(guī)模，可以考慮使用MPI多進程將程序擴展到多個結點上并行。

[1] Zhao Chang-hai, Wang Shi-hu, Luo Guo-an, et al. A highly extensible 3D prestack kirchhoff time migration parallel algorithm[C]∥National Annual Conference on High Performance Computing, 2013:49-60.(in Chinese)

[2] Jeffers J, Reinders J. Intel? Xeon Phitmcoprocessor high-performance programming[M]. NY:Elsevier, 2013.

[3] top500 supercomputer sites[EB/OL].[2014-10-16].http://www.top500.org.

[4] Bhardwaj D, Yerneni S. Efficient parallel I/O for seismic imaging in a distributed computing environment[C]∥Proc of

the 3rd Conference and Exposition on Petroleum Geophysics, 2000:105-108.

[5] Wang Hua-zhong, Liu Shao-yong, Kong Xiang-ning, et al. 3D Kirchoff PSDM for large-scale seismic data and its parallel implementation strategy[J]. Oil Geophysical Prospecting, 2012, 47(3):404-410.(in Chinese)

[6] Zhang Qing, Chi Xu-guang, Xie Hai-bo,et al. Parallel algorithm based on the travel time computing of pre-stack time migration using GPU[J]. Computing Systems & Applications, 2011,20(8):42-46.(in Chinese)

[7] Claerbout J F, Green I. Basic earth imagine[M]. California:Stanford University, 2008.

[8] Claerbout J F. Introduction to Kirchhoff migration programs[R]. California:Stanford Exploration Report, 1997:385-391.

[9] Wang En-dong, Zhang Qing, Shen Bo, et al. MIC High performance computing programming guide[M]. Beijing:China Water & Power Press, 2012.(in Chinese)

附中文參考文獻：

[1] 趙長海, 王獅虎, 羅國安，等. 一個高度可擴展的三維疊前Kirchhoff時間偏移并行算法[C]∥全國高性能計算學術年會, 2013:49-60.

[5] 王華忠, 劉少勇, 孔祥寧, 等. 大規(guī)模三維地震數據Kirchhoff疊前深度偏移及其并行實現[J]. 石油地球物理勘探, 2012, 47(3):404-410.

[6] 張清, 遲旭光, 謝海波，等. 基于GPU實現疊前時間偏移走時計算的并行算法[J]. 計算機系統應用, 2011, 20(8):42-46.

[9] 王恩東, 張清, 沈鉑，等. MIC高性能計算編程指南[M]. 北京:中國水利水電出版社, 2012.

XIONG Min,born in 1990,PhD candidate,CCF member(E200036553G)，her research interests include large scale engineering and science computation.

王勇獻(1975-),男,河南安陽人，博士，副研究員,CCF會員(E200021304M),研究方向為高性能計算。E-mail:yxwang@nudt.edu.cn

WANG Yong-xian,born in 1975,PhD,associate research fellow,CCF member(E200021304M),his research interest includes high performance computing.

Parallel optimization of the seismic wave PKTM algorithm on CPU+MIC heterogeneous platform

XIONG Min，WANG Yong-xian

(College of Computer,National University of Defense Technology,Changsha 410073,China)

An efficient technique which is now being implemented in photographing images of complicated rock stratum is the seismic wave PKTM algorithm. With the earthquake prediction coming into massive data generation, it is of essential importance to optimize this algorithm by parallel computation. In recent years, high performance parallel computation is characterized by heterogeneous and many cores systems.A typical example of this kind of processors, featured with low cost and high performance is Xeon Phi, being known as MIC. On the basis of the classic PKTM algorithm, we parallelize and optimize the PKTM algorithm in the offload programming model, based on CPU+MIC heterogeneous platform. For applications with the scale of 64 000 000(8 000×8 000),the total parallel simulation time is reduced from 357.52 seconds to 1.66 seconds, achieving 214.37x performance improvement.

collaborative parallel;Intel Xeon Phi;heterogeneous parallel;Kirchhoff Time Migration；performance optimization

1007-130X(2015)01-0014-09

2014-09-10;

2014-11-12基金項目：空氣動力學國家重點實驗室開放課題資助項目(SKLA201401)；國家自然科學基金資助項目(61379056, 11272352)

TP274

A

10.3969/j.issn.1007-130X.2015.01.003

熊敏(1990-),女，湖南長沙人，博士生，CCF會員(E200036553G)，研究方向為大規(guī)模工程與科學計算。E-mail:miyazawa21yy@aliyun.com

通信地址：410073 湖南省長沙市國防科學技術大學計算機學院學員五隊

Address:College of Computer,National University of Defense Technology,Changsha 410073,Hunan,P.R.China