并行編譯續(xù)和調(diào)試

并行算法實踐國家高性能計算中心（合肥）22023/4/4并行編譯簡介（續(xù)）國家高性能計算中心（合肥）32023/4/4語句重排語句重排（statementreordering)是基于語句依賴圖的程序變換，它改變語句的詞法順序但不改變語句間依賴關(guān)系。該變換常用于循環(huán)向量化。當(dāng)循環(huán)中語句間有循環(huán)依賴關(guān)系時，可通過此變換將與語句執(zhí)行順序相反的依賴關(guān)系改變?yōu)榕c語句執(zhí)行順序一致的依賴關(guān)系，從而使循環(huán)向量化。 考慮如下循環(huán)例1：

L: forI=2toNdo S1:A(I)=B(I)+C(I+1) S2:D(I)=A(I+1)+1 S3:C(I)=D(I) endfor國家高性能計算中心（合肥）42023/4/4上述循環(huán)中依賴關(guān)系為：

S2aS1S1aS3和S2fS3，其中依賴關(guān)系

S2aS1使得循環(huán)不能向量化。S1S2S3原語句依賴圖語句重排S2S1S3重排后的語句依賴圖國家高性能計算中心（合肥）52023/4/4語句重排后，原來的循環(huán)可以向量化,語句順序為：

S2：D(2:N)=A(3:N+1)+1 S1:A(2:N)=B(2:N)+C(3:N+1)S3:C(2:N)=D(2:N)國家高性能計算中心（合肥）62023/4/4循環(huán)置換循環(huán)置換(looppermutation)是改變循環(huán)位置的程序變換，屬于迭代級的變換，而循環(huán)交換即是此種變換的特例。該變換有如下特點(diǎn)： －置換外層無循環(huán)依賴的循環(huán)與內(nèi)層有依賴的循環(huán)，使得置換后內(nèi)層可向量化； －置換無依賴的循環(huán)到外層使得整個循環(huán)嵌套可以并行執(zhí)行，可增加每次迭代的并行粒度并減少障礙同步次數(shù)； －在有多層可向量化的循環(huán)時，置換范圍較大的循環(huán)到外層可以增加向量的長度。國家高性能計算中心（合肥）72023/4/4考慮如下循環(huán)例2：

L1:forI=1toMdo

L2:forJ=1toMdo S:B(I,J)=A(I,J-1) T:A(I,J)=B(I,J)*C(I,J) endfor endfor

循環(huán)中存在(0,1)的依賴關(guān)系TS，不能對內(nèi)層向量化?？梢岳醚h(huán)置換（交換）：

L2:forJ=1toMdo

L1:forI=1toMdo

此時，上述循環(huán)嵌套在內(nèi)層可以向量化！

國家高性能計算中心（合肥）82023/4/4再考慮以下循環(huán)例3：

forI=2toNdo forJ=2toNdoS: A(I,J)=(A(I-1,J)+A(I+1,J))/2 endfor endfor

此循環(huán)中依賴關(guān)系：方向向量為(1,0)的SfS和(1,0)的SaS；因此循環(huán)嵌套中外層不可并行，內(nèi)層可以并行(沒有依賴關(guān)系），但并行粒度僅為一條語句?？梢圆捎媒粨Q循環(huán)的方式：

forJ=2toNdo

forI=2toNdo此時外層循環(huán)可以并行，其粒度為一個（內(nèi)層）循環(huán)。國家高性能計算中心（合肥）92023/4/4循環(huán)置換的充要條件：

假定P是mXm的置換矩陣，由P定義的m層循環(huán)嵌套L的置換是合法的，當(dāng)且僅當(dāng)對于L的每一個方向向量，均有P>0成立。 這里mXm的置換矩陣P定義為： －每個元素非0即1

－每行有且僅有一個元素為1

－每列有且僅有一個元素為1

令(i)表示P中第i列中為1的元素所在的行號，則函數(shù)：i(i)是集合{1,2,…,m}上的一個置換，它完全確定矩陣P。P可以表示為：1,2,…,m(1),(2),…,(m)P＝

或

(1),(2),…,(m)國家高性能計算中心（合肥）102023/4/4考慮循環(huán)例2和例3： 對于例2，置換矩陣P=

[2,1],而原循環(huán)中的方向向量為=(0,1),P=(0,1)[2,1]=(1,0)>0。因此該循環(huán)交換是合法的。 對于例3，置換矩陣P=

[2,1],而原循環(huán)中的方向向量為=(1,0),P=(1,0)[2,1]=(0,1)>0。因此該循環(huán)交換是合法的。 這里P=[2,1]其矩陣形式為： 而P’=[3,2,1]的矩陣形式為：

0110001010100國家高性能計算中心（合肥）112023/4/4循環(huán)逆轉(zhuǎn)循環(huán)逆轉(zhuǎn)(loopreversal)－顛倒循環(huán)中迭代執(zhí)行的順序，改變了循環(huán)迭代方向的變換，也使得變換循環(huán)中方向向量發(fā)生逆轉(zhuǎn)。如果循環(huán)在逆轉(zhuǎn)變換后，它的方向向量均為正向量，則稱該變換前后的循環(huán)等價，該變換是合法的。

考慮如下循環(huán)例4：

forI=1to100do

forJ=1to5doS: A(I,J)=A(I-1,J+1)+1

endfor endfor國家高性能計算中心（合肥）122023/4/4循環(huán)例4的迭代依賴圖如下，可知它含有方向向量為 (1,-1)的依賴關(guān)系，其內(nèi)層循環(huán)可以并行化（但粒度為5次迭代），其外層不能并行化，也不能進(jìn)行循環(huán)交換。（為什么？）對循環(huán)J進(jìn)行并行，粒度為5次迭代國家高性能計算中心（合肥）132023/4/4但對例4中，循環(huán)J進(jìn)行逆轉(zhuǎn)，則方向向量變?yōu)?1,1)。 可以對循環(huán)嵌套進(jìn)行循環(huán)交換。此時內(nèi)層循環(huán)I可以并行化（粒度為100次迭代?。?，迭代依賴圖如右所示：

forJ=5downto1do forI=1to100doS: A(I,J)=A(I-1,J+1)+1 endfor

endfor國家高性能計算中心（合肥）142023/4/4圈收縮(cycleshrinking)－此變換技術(shù)一般用于依賴距離大于1的循環(huán)中，它將一個串行循環(huán)分成兩個緊嵌套循環(huán)，其中外層依然串行執(zhí)行，而內(nèi)層則是并行執(zhí)行（一般粒度較小）。 考慮循環(huán)例5：(K為正整數(shù))

forI=0toNdoS: A(I+K)=B(I)T: B(I+K)=A(I)+C(I) endfor圈收縮ST語句依賴圖國家高性能計算中心（合肥）152023/4/4循環(huán)例5既不能向量化，也不能并行化（why？） 考察（K=4時）迭代依賴圖： 可知，此循環(huán)可以按K個迭代一組串行執(zhí)行，而每一組內(nèi)可以并行執(zhí)行。循環(huán)例5可以改寫為：

forJ=0toNstepK

doallI=JtoJ+K-1S: A(I+K)=B(I)T: B(I+K)=A(I)+C(I) enddoall endfor國家高性能計算中心（合肥）162023/4/4并行程序的調(diào)試并行調(diào)試的困難并行調(diào)試的方法已有的調(diào)試工具國家高性能計算中心（合肥）172023/4/4并行調(diào)試的困難不確定性 －傳統(tǒng)的循環(huán)調(diào)試失效 －執(zhí)行路徑（結(jié)果）的不確定性 －執(zhí)行行為的不可再生 －導(dǎo)致不確定性的因素：

共享變量的競爭消息傳遞的競爭

MPI中的MPI_ANY_SOURCE和MPI_ANY_TAG PVM中表示任意消息來源和標(biāo)簽的通配符：-1

進(jìn)程動態(tài)調(diào)度不確定的系統(tǒng)調(diào)用探針效應(yīng) －調(diào)試行為對并行程序執(zhí)行的干擾國家高性能計算中心（合肥）182023/4/4死鎖－常見的并行程序錯誤 －共享變量中不恰當(dāng)?shù)淖x寫互斥 －消息傳遞中不恰當(dāng)采用阻塞（同步）收發(fā)通訊，如下面“環(huán)狀通訊”語句片段：

send(data,count,left-node,MSG_TAG)

recv(indata,count,right-node,MSG_TAG)

－消息收發(fā)的不匹配Pi：send(data,count,node-j,some_MSG_TAG)Pj：recv(indata,count,node-i,other_MSG_TAG)

國家高性能計算中心（合肥）192023/4/4并行調(diào)試的方法記錄－重放(record-replay)

在程序運(yùn)行中可以對相關(guān)的消息傳遞(或共享變量的讀寫）進(jìn)行記錄，以便在重放時利用這些信息來控制同步通信，保證循環(huán)調(diào)試的有效性。此方法應(yīng)注意所記錄的信息規(guī)模及所產(chǎn)生的探針效應(yīng)。斷點(diǎn)調(diào)試(breakpointdebugging) ①基于控制流的斷點(diǎn)，同串行調(diào)試的斷點(diǎn)類似。②基于事件的斷點(diǎn)，當(dāng)發(fā)生異?；蛴脩舳x的事件時斷點(diǎn)生效。③基于謂詞的斷點(diǎn)，當(dāng)某個條件表達(dá)式成立時斷點(diǎn)生效。此外，由于并行程序的多任務(wù)性，斷點(diǎn)還有所謂的全局?jǐn)帱c(diǎn)。

國家高性能計算中心（合肥）202023/4/4并行調(diào)試的方法漸增檢查點(diǎn)(incrementalcheckpoint)

針對運(yùn)行時間長的并行程序的執(zhí)行，以固定的周期或在某些特定場合下對程序運(yùn)行狀態(tài)的進(jìn)行全面記錄。周期的劃分可以是基于時間片的，也可以是基于數(shù)據(jù)片的，比如每計算完若干數(shù)據(jù)進(jìn)行一次記錄。程序員可以查看各次記錄，并結(jié)合重放技術(shù)縮小并定位錯誤范圍。事件分析與靜態(tài)分析國家高性能計算中心（合肥）212023/4/4已有的并行調(diào)試工具文本方式的并行調(diào)試器 －此類調(diào)試器使用較廣泛，如pdbx，且多數(shù)基于串行調(diào)試器gdb或dbx －提供傳統(tǒng)串行調(diào)試器的全部功能（命令行方式） －提供適當(dāng)?shù)牟⑿姓{(diào)試手段 －HPDF論壇(HighPerformanceDebuggerForum)

制定并行調(diào)試器的標(biāo)準(zhǔn)語法和命令圖形界面調(diào)試器 如DCDB（DawningClusterDeBugger）、Tatalview、xpdbx等。 －GUI方式的調(diào)試手段 －數(shù)據(jù)可視化 －通訊可視化國家高性能計算中心（合肥）222023/4/4并行調(diào)試器DCDB國家高性能計算中心（合肥）232023/4/4國家高性能計算中心（合肥）242023/4/4PVM程序的調(diào)試

PVM主程序中在spawn另一程序時如果使用了PvmTaskDebug作為flag參數(shù)項，則通過shell文件$PVM_ROOT/lib/debugger來啟動程序。在該shell文件中，用戶可以指定自己想用的調(diào)試器。MPI程序的調(diào)試

MPI程序的0號進(jìn)程的啟動： mpirun–gdb–npXXuserfile–p4nor