熊煥亮， 曾國蓀

(1.同濟大學 電子與信息工程學院，上海 200092; 2.江西農(nóng)業(yè)大學 軟件學院，江西 南昌 330045;3.國家高性能計算機工程技術(shù)中心同濟分中心，上海 200092)

?

可變結(jié)構(gòu)的并行計算中任務粒度細化可擴展方法

熊煥亮1,2,3， 曾國蓀1,3

(1.同濟大學 電子與信息工程學院，上海 200092; 2.江西農(nóng)業(yè)大學 軟件學院，江西 南昌 330045;3.國家高性能計算機工程技術(shù)中心同濟分中心，上海 200092)

首先評估并行任務及體系結(jié)構(gòu)中影響可擴展性的關(guān)鍵因素，并對并行任務及體系結(jié)構(gòu)進行圖建模.然后，提出一種DAG任務粒度細化的可擴展方法，本質(zhì)上是變換圖的結(jié)構(gòu)、調(diào)整圖節(jié)點權(quán)值和邊權(quán)值.進一步推導得出一些關(guān)于新擴展方法的有用結(jié)論.最后，應用網(wǎng)格模擬工具SimGrid開展實驗，結(jié)果表明所提出的擴展方法，能實現(xiàn)可變結(jié)構(gòu)并行計算的等速度效率擴展，對于并行計算擴展實踐有指導意義.

并行計算； 機器與算法； 可變結(jié)構(gòu)； 擴展方法

并行計算系統(tǒng)常通過擴展其規(guī)模來獲得更高的計算性能.可擴展性是評價并行計算系統(tǒng)能否擴展的一個極其重要性能指標[1].開展可擴展性研究首要問題是如何定義和度量并行計算可擴展性.關(guān)于并行計算可擴展性度量機制的研究中，比較有代表性的成果有：等效率(Iso-efficiency)[2]機制，等平均速度(Iso-speed)[3]機制，延遲度量(Latency metric)機制[4]等.國內(nèi)對并行計算可擴展性的研究也取得了一些重要研究成果：李等提出了一種等并行計算時間與通信開銷之比的可擴展性模型[5]，李等提出了一種近優(yōu)可擴展模型[6]，楊等提出了一種加速比增大的倍數(shù)與機器規(guī)模增大的倍數(shù)之比的可擴展性模型[7]，孫等將等平均速度度量機制擴展至異構(gòu)系統(tǒng)，提出了等平均速度效率度量機制(Iso-speed-e scalability metric)[8].楊學軍院士特別指出可擴展性度量在并行計算發(fā)展進程中的重要地位[9].

可擴展性研究的另外一個重要內(nèi)容是可擴展方法的研究.最初，可擴展方法的研究聚焦于機器的擴展，主要思路是通過增加諸如CPU、內(nèi)存、輸入/輸出接口等重要處理部件的數(shù)量，從而實現(xiàn)機器的擴展.對于體系結(jié)構(gòu)的可擴展研究，則主要關(guān)注節(jié)點間互連結(jié)構(gòu)的可擴展性，例如樹形的互連結(jié)構(gòu)可擴展性良好，而超立方體結(jié)構(gòu)卻難以擴展.并行算法的可擴展方法則主要在于可擴展性度量和試驗測量兩方面，此類擴展方法中較突出的有Speedup方法[10-11]、Iso-efficiency方法[2]、Iso-speed方法[3]、Latency方法[4]、以及同濟大學曾國蓀教授提出的等綜合性能面積方法[12].

目前，改善并行計算系統(tǒng)的可擴展性取得一些新成果，包括硬件可編程可重構(gòu)方法、程序編譯優(yōu)化和重寫技術(shù)等.硬件可編程重構(gòu)技術(shù)通過硬件可編程適應計算任務需求的變化，以期達到最佳性能.Tessier等[13]全面地綜述了可重構(gòu)體系結(jié)構(gòu)，指出可重構(gòu)體系結(jié)構(gòu)在計算并行任務時，對于不同的軟件實現(xiàn)，計算硬件均能獲得較好的性能和能效.程序編譯優(yōu)化等軟件可重構(gòu)技術(shù)則是通過優(yōu)化任務程序算法，變換程序算法結(jié)構(gòu)，以適應硬件體系結(jié)構(gòu)的變化升級，較之硬件可重構(gòu)技術(shù)，更為靈活和方便.曾國蓀等[14]給出了計算任務與體系結(jié)構(gòu)匹配的異構(gòu)計算等速度可擴展定義及可擴展性條件.熊煥亮等[15]針對一類結(jié)構(gòu)固定的并行計算，開展了等速度效率的可擴展性研究，針對并行任務的算法結(jié)構(gòu)和并行機的體系結(jié)構(gòu)同構(gòu)情形，提出了一種變圖權(quán)的等速度效率可擴展方法，而針對兩者結(jié)構(gòu)異構(gòu)情形，提出了一種關(guān)鍵路徑不變的等速度效率可擴展方法.

近年建設的并行計算系統(tǒng)在設計和建造時大多兼顧了后續(xù)可能的擴展升級.而對于擁有源碼等所有文檔資料的并行任務求解程序，不受算法結(jié)構(gòu)固定的約束，完全可根據(jù)硬件體系結(jié)構(gòu)的特性，優(yōu)化并行任務的粒度和算法結(jié)構(gòu).本文對此類可變結(jié)構(gòu)的并行計算，提煉其可擴展關(guān)聯(lián)變量，對并行任務和體系結(jié)構(gòu)進行圖建模，給出滿足實際擴展需求及可擴展性目標的擴展方法.

1 可變結(jié)構(gòu)并行計算的概念及擴展性度量

在實際應用中，諸如地球模擬，氣象預報等諸多領域，不斷對計算性能提出了更高的挑戰(zhàn)性需求.大量并行計算機系統(tǒng)迫切需要擴展升級，相應地，并行任務的求解算法也急需擴展優(yōu)化，以匹配擴展后的計算機系統(tǒng).此類并行計算機系統(tǒng)的軟硬件升級往往需要改變軟硬件的結(jié)構(gòu).

定義1 可變結(jié)構(gòu)的并行計算：指開展并行計算時，為提高并行計算系統(tǒng)的計算能力，允許并行機的體系結(jié)構(gòu)做合理的調(diào)整，或者為了求解更大規(guī)模的問題以及更高精度的問題解，并行任務的求解算法結(jié)構(gòu)可做合理的調(diào)整.

由定義1可知，對于可變結(jié)構(gòu)的并行計算，結(jié)構(gòu)可變意味著可在原體系結(jié)構(gòu)基礎上增加更多的計算節(jié)點，以及相應的通信鏈路，也可增加并行任務的計算負載，優(yōu)化任務的計算粒度，實現(xiàn)可變結(jié)構(gòu)并行計算的擴展.可擴展性是并行計算的重要性能指標之一，是指一個并行計算系統(tǒng)隨著其計算節(jié)點規(guī)模的擴展，其計算性能相應增強的能力，其度量如下定義.

定義2 可擴展性度量函數(shù)：是指并行計算擴展實踐中，用于計算及度量其可擴展性程度的關(guān)系表達式.記并行任務擴展前、后的計算負載分別為W1,W2，并行機體系結(jié)構(gòu)擴展前、后的標記速度分別為C1,C2,則可擴展性度量函數(shù)定義為Φ(C1,C2)=(W1/C1)/(W2/C2).

定義2給出了并行計算等速度效率可擴展性的度量函數(shù)，其中體系結(jié)構(gòu)的標記速度等于其每個計算節(jié)點分別運行基準測試程序所測得的計算速度之和，速度效率等于并行任務運行于體系結(jié)構(gòu)上的平均速度與體系結(jié)構(gòu)標記速度的比值.函數(shù)Φ(C1,C2)∈(0,1],在理想情況下，Φ(C1,C2)=1.一般情況下，Φ(C1,C2)<1.

2 可變結(jié)構(gòu)并行計算的圖模型

2.1 可變結(jié)構(gòu)體系結(jié)構(gòu)的圖描述

定義3 可變結(jié)構(gòu)的體系結(jié)構(gòu): 是指一類建設好的、開放的，并已成功運行的并行計算機系統(tǒng)，即指由若干計算節(jié)點及網(wǎng)絡設備，通過高速網(wǎng)絡連接而成的并行計算環(huán)境，且其計算節(jié)點可再次增加、網(wǎng)絡結(jié)構(gòu)可相應調(diào)整，可表示為一個帶權(quán)圖HSG=〈P,U,C,B〉,其中:

(1)圖頂點集合P={pi|i∈[1,m]}表示體系結(jié)構(gòu)中計算節(jié)點集,m=|P|表示計算節(jié)點數(shù).

(2)圖邊集U={uk|k∈[1,s]}表示體系結(jié)構(gòu)中計算節(jié)點的互連情況,邊數(shù)s=|U|表示其中通信鏈路數(shù).邊uk=(pi,pj),pi,pj∈P表示計算節(jié)點pi,pj由高速通信網(wǎng)絡連接在一起.

(3)權(quán)值集合C={ci|i∈[1,m]}表示各計算節(jié)點標記速度集,其中ci為計算節(jié)點pi的標記速度.

(4)權(quán)值集合B={bk|k∈[1,s]}表示互連計算節(jié)點間通信鏈路的帶寬集.?uk=(pi,pj)∈U,邊uk的權(quán)值bk表示計算節(jié)點pi和pj間通信鏈路的帶寬.

定義3中的結(jié)構(gòu)可變是指擴展時可增加新的計算節(jié)點及通信鏈路，由此引起計算節(jié)點之間互連結(jié)構(gòu)的變化，在體系結(jié)構(gòu)圖模型中表現(xiàn)為圖的拓撲結(jié)構(gòu)是可變的.

2.2 可變結(jié)構(gòu)并行任務的圖描述

定義4 可變結(jié)構(gòu)的并行任務: 是指一類開發(fā)好的，可重構(gòu)的，并已成功運行過的并行程序，即為適應擴展后的體系結(jié)構(gòu)，程序任務的求解流程和算法可重構(gòu)，如任務的求解粒度及任務依賴關(guān)系可重新調(diào)整，可表示為一個有向無環(huán)圖PTG=〈Q,L,E,Γ,A,Δ〉，其中：

(1)頂點集Q={qi|i∈[1,n]}表示并行任務集,圖階n=|Q|表示并行任務數(shù),且n可變.

(2)有向邊集L={lh|h∈[1,r]}表示關(guān)聯(lián)任務間的數(shù)據(jù)依賴集,L?Q×Q.?lh=〈qi,qj〉,lh表示任務qj對qi存在數(shù)據(jù)依賴.

(3)權(quán)值集E={εi|i∈[1,n]}表示并行任務計算精度集, 計算精度用相對誤差率表示, 如ε1=0.1表示計算結(jié)果精確到小數(shù)點后1位, 精度ε1提高10倍，則ε1變?yōu)?.1/10=0.01.

(4)權(quán)值集Γ={γi|i∈[1,n]}表示并行任務問題規(guī)模集，如在矩陣相乘算法中，問題規(guī)模為矩陣維數(shù).

(5)權(quán)值集A={αi|i∈[1,n]}表示并行任務的串行分量集.

(6)權(quán)值集Δ={δi|h∈[1,r]}表示關(guān)聯(lián)任務之間傳輸負載集.

通常，在改變?nèi)蝿粘绦虻挠嬎憔然騿栴}規(guī)模時，會引起任務程序計算負載的變化，不妨設并行任務qi的計算負載wi為其計算精度εi和問題規(guī)模γi的函數(shù)Ψi,即wi=Ψi(εi,γi).理論上任務之間的數(shù)據(jù)傳輸量與相關(guān)任務的計算負載密切相關(guān)，為便于擴展性分析，將數(shù)據(jù)傳輸量作為獨立的參數(shù).

3 可變結(jié)構(gòu)DAG任務粒度細化的擴展方法

3.1 DAG任務粒度細化擴展的前提假設

(1)假設擴展前DAG并行任務已在原有并行機上成功運行，滿足既定的功能和性能要求.

對于一DAG圖并行任務PTG1=〈Q1,L1,E1,Γ1,A1,Δ1〉，并行任務總數(shù)為n1,數(shù)據(jù)依賴關(guān)系數(shù)為r1.假設任務按照某種調(diào)度策略調(diào)度在體系結(jié)構(gòu)HSG1=〈P1,U1,C1,B1〉上成功地執(zhí)行，體系結(jié)構(gòu)中計算節(jié)點總數(shù)為m1，通信鏈路總數(shù)為s1，則PTG1的執(zhí)行時間T1和速度效率Ev1可通過如下分析計算得到.

(1)

(2)

在并行任務DAG圖中，從起始子任務至終止子任務存在多條執(zhí)行路徑，為便于描述每條路徑的執(zhí)行時間，分別定義任務節(jié)點隸屬路徑函數(shù)φj(i)，如式(1)所示，以及數(shù)據(jù)傳輸邊隸屬路徑函數(shù)φj(h)，如式(2)所示.φj(i)=1表示任務qi在第j條路徑Pathj上,φj(h)=1表示數(shù)據(jù)依賴lh在第j條路徑Pathj上且lh對應的兩個任務不在同一計算節(jié)點.記并行任務路徑總數(shù)為N1,則整個并行任務的執(zhí)行時間T1為

(3)

其中f和g為并行任務在并行機上執(zhí)行時采用的調(diào)度策略.并行任務的執(zhí)行時間T1取決于關(guān)鍵路徑的執(zhí)行時間，關(guān)鍵路徑執(zhí)行時間可參考文獻[15]中方法求解.在并行任務的執(zhí)行時間T1確定后，任務執(zhí)行的速度效率Ev1為

(4)

(2)并行機系統(tǒng)體系結(jié)構(gòu)已擴展完成

圖1 體系結(jié)構(gòu)的擴展

假設并行機的體系結(jié)構(gòu)從HSG1=〈P1,U1,C1,B1〉擴展為HSG2=〈P2,U2,C2,B2〉，系統(tǒng)的標記速度從C1擴展為C2，計算節(jié)點數(shù)從m1增加至m2，通信鏈路數(shù)從s1增加為s2，新增通信鏈路帶寬足夠大.然后在此基礎上，研究如何擴展重構(gòu)并行任務以匹配新的體系結(jié)構(gòu).

3.2 DAG任務粒度細化的擴展過程

由假設(2)可知，體系結(jié)構(gòu)擴展后，標記速度擴展了β=C2/C1倍.自然地，隨體系結(jié)構(gòu)性能的增強將DAG并行任務中每個任務的計算負載也擴展β倍，以實現(xiàn)待求解問題更高的求解精度.假設DAG任務的擴展過程中，串行計算部分保持不變，僅并行計算部分增加.

記擴展前DAG并行任務PTG1的任務序列為Q1=(q11,q12,…,q1n1)，對應的計算負載序列為W1=(w11,w12,…,w1n1)，每個任務的串行分量序列為A=(α1,α2,…,αn1)，則任務q1i擴展后的計算負載w2i=αiw1i+β(1-αi)w1i，其中β(1-αi)w1i為可并行計算負載.

在任務的可并行計算負載擴展后，需要將任務執(zhí)行的粒度細化，以盡可能均衡任務的計算負載，使加速計算任務的執(zhí)行成為可能.DAG并行任務粒度細化的啟發(fā)式方法如下：

(6) 根據(jù)PTG1的DAG圖，采用算法1確定每個任務節(jié)點所在層的并發(fā)度.

(9) 若PTG1中所有任務節(jié)點均處理完畢，則DAG任務細化結(jié)束，否則轉(zhuǎn)(7).

假設經(jīng)過分析，DAG并行任務中每個任務均實施擴展細化，則其擴展后的DAG并行任務如圖2b所示，每個任務均擴展細化為3個子任務，即2個可并行計算的子任務，1個規(guī)約任務，任務之間的依賴為粒度細化而產(chǎn)生的額外通信，例如任務q11,擴展為(q21-1,q21-2,q21-0)3個子任務，其中q21-1,q21-2為可并行計算的子任務，q21-0為規(guī)約子任務.

算法1. ComputeDOPForLevel//計算DAG并行任務中每個任務所在層及該層并發(fā)度.

輸入：初始的并行任務DAG圖(以鄰接表存儲)

輸出：DAG并行任務中每個任務所在層nodeLevel[]及每層的節(jié)點數(shù)levelCount[]

{

初始化任務隊列Queue,節(jié)點所在層號數(shù)組nodeLevel[],每層的計算節(jié)點數(shù)levelCount[]全為0;

初始化變量currentLevel=0,totalNodeNum=0;

將DAG圖中所有入度為0的任務節(jié)點入隊;

while(Queue不為空){

GetQueuelength;//取當前隊列的長度

totalNodeNum+=Queuelength;//計算DAG并行任務總?cè)蝿諗?shù).

for(int i=0;i

隊頭節(jié)點head出隊;

nodeLevel[head.nodeNumber]=currentLevel;//標記節(jié)點所在層號.

head指向的全部節(jié)點入隊;//head節(jié)點的所有鄰接節(jié)點入隊.

}

currentLevel++;

}

for(int i=0;i

levelCount[nodeLevel[i]]++;//計算每層的節(jié)點數(shù).

}

}

}

圖2 DAG并行任務的擴展及其粒度細化

4 可變結(jié)構(gòu)并行計算DAG任務粒度細化擴展方法的性能評估

4.1 DAG任務擴展及粒度細化后并行計算性能分析

4.1.1 可變結(jié)構(gòu)并行計算擴展參數(shù)的詳細假定

(1)并行機體系結(jié)構(gòu)擴展參數(shù)的假定

(2)DAG并行任務擴展細化參數(shù)的假定

根據(jù)假設(1)，擴展前DAG并行任務已成功調(diào)度至所匹配的計算節(jié)點.不妨假設任務DAG圖的N1條執(zhí)行路徑中，第j條路徑為關(guān)鍵路徑，則由式(3)可得DAG并行任務的執(zhí)行時間T1為

(5)

隨著體系結(jié)構(gòu)標記速度由C1擴展提高為C2，DAG并行任務中每個任務的并行計算負載相應地擴展β=C2/C1倍，任務q1i擴展后的計算負載由原串行部分和擴展后的并行部分組成，即w2i=αiw1i+β(1-αi)w1i.

為便于分析，假設DAG并行任務中所有任務均細化為k+1個子任務，k=m2/m1.任務q1i在擴展并實施粒度細化后，生成k個子并行任務(q2i-1,q2i-2,…,q2i-k)，每個子任務的計算負載為擴展前任務q1i負載w1i的η倍,η=α+β(1-α)/k，即w2i-1=w2i-2=…=w2i-k=ηw1i,以及1個規(guī)約子任務q2i-0.

對于數(shù)據(jù)依賴關(guān)系l1h=〈q1i,q1j〉，不妨設DAG并行任務擴展后，傳輸給每個后繼子任務的通信負載為擴展前通信負載δ1h的η倍,即為ηδ1h.

(3)擴展及粒度細化后的DAG并行任務與新體系結(jié)構(gòu)的匹配映射

擴展前，任務q1i映射至匹配的計算節(jié)點p1f(i)，不妨設q1i擴展及粒度細化生成的子任務q2i-1及q2i-0映射至計算節(jié)點p1f(i))，生成的其它子任務(q2i-2,…,q2i-k)映射至新增計算節(jié)點(p2f(i)-2,…,p2f(i)-k)，如圖3所示.

a 關(guān)鍵路徑任務粒度細化 b 擴展后的體系結(jié)構(gòu)

擴展前，任務之間的數(shù)據(jù)通信l1h映射至鏈路u1g(h), 擴展后，依賴數(shù)據(jù)在傳輸給新增計算節(jié)點時，需經(jīng)原通信鏈路u1g(h)傳輸至原計算節(jié)點，再經(jīng)新增通信鏈路傳輸至新增計算節(jié)點，如圖3所示.

4.1.2 可變結(jié)構(gòu)并行計算DAG并行任務關(guān)鍵路徑的擴展分析

根據(jù)假定(3)，子任務q2i-1與q2i-0在計算節(jié)點p1f(i)上執(zhí)行，由于與p1f(i)直連的新增計算節(jié)點標記速度不低于p1f(i)的標記速度，故q2i-1與q2i-0在p1f(i)上的計算時間不小于其它子并行任務在新增節(jié)點上的計算時間，而q2i-0的計算時間可理解為子并行任務(q2i-1,…,q2i-k)之間的數(shù)據(jù)規(guī)約等產(chǎn)生的時間開銷Toi,Toi=max(δi-1/b,δi-2/b,…,δi-k/b)，因此任務q1i擴展及粒度細化后，在匹配的計算節(jié)點上的執(zhí)行時間為ηw1j/c1f(i)+Toi,其中η=α+β(1-α)/k.數(shù)據(jù)通信l1h的傳輸負載擴展η倍后，數(shù)據(jù)傳輸時間可近似為ηδ1h/b1g(h)+ηδ1h/b.

命題1 可變結(jié)構(gòu)并行計算中，DAG并行任務PTG1=〈Q1,L1,E1,Γ1,A1,Δ1〉在匹配的體系結(jié)構(gòu)HSG1

根據(jù)命題1，可變結(jié)構(gòu)并行計算中，體系結(jié)構(gòu)HSG1擴展為HSG2，DAG并行任務PTG1擴展為PTG2后，PTG2的執(zhí)行時間為T2,即

(6)

并行計算的速度效率近似為

(7)

命題2 可變結(jié)構(gòu)并行計算中，DAG并行任務PTG1=〈Q1,L1,E1,Γ1,A1,Δ1〉在匹配的體系結(jié)構(gòu)HSG1〈P1,U1,C1,B1〉上執(zhí)行的關(guān)鍵路徑為j,如果HSG1按照假設(1)已擴展為HSG2，PTG1中每個任務的串行分量均為α，并按照假設(2)實施粒度細化擴展為PTG2，且PTG2和HSG2已按照假設(3)匹配映射好，則PTG2在HSG2上執(zhí)行的速度效率Ev2小于等于Ev1.

由命題2可知，可變結(jié)構(gòu)的并行計算實施任務粒度細化擴展時，速度效率保持近似相等.根據(jù)定義2，等速度效率可擴展性函數(shù)Φ=(W1/C1)/(W2/C2)=(C2/C1)/(W2/W1)=β/(kα+β(1-α)+χ)=1/(αk/β+(1-α)+χ/β)，其中χ為規(guī)約子任務計算負載比重.若忽略規(guī)約子任務計算負載，即χ=0，且α一定時，顯然有

(8)

當k<β時，即總計算負載的增長較系統(tǒng)標記速度的增長更慢，故有Φ>1，反之，當k≥β時，總計算負載的增長較體系結(jié)構(gòu)標記速度的增長更快，故有Φ≤1.

4.2 可變結(jié)構(gòu)并行計算擴展的仿真實驗

4.2.1 仿真實驗工具及實驗設計

為驗證所提出可擴展方法的有效性，在實驗室的Dell PC集群上，利用SimGrid3.10開展擴展模擬實驗.集群平臺包括32個計算節(jié)點，由千兆以太網(wǎng)互連組成，每個節(jié)點的CPU為Intel(R) XeonTM3.0 GHz，緩存4 GB，內(nèi)存32 GB.操作系統(tǒng)為Redhat Linux9.0，并行計算軟件環(huán)境為MPICH2.

表1 可變結(jié)構(gòu)的體系結(jié)構(gòu)擴展前后的性能參數(shù)(帶下劃線項為關(guān)鍵路徑對應的數(shù)據(jù)項)

可變結(jié)構(gòu)的并行計算仿真實驗中，擴展前的并行任務PTG1如圖2a所示，體系結(jié)構(gòu)HSG1如圖1a所示,HSG1及PTG1的具體參數(shù)取值如表1和表2所示，且實驗中任務的計算負載與問題規(guī)模及計算精度的函數(shù)關(guān)系假設為wi=105γi+106/εi.表2中參數(shù)α=1%為任務PTG1的串行分量，任務PTG1的計算規(guī)模和計算精度提升，任務計算負載相應地擴展β=C2/C1=3倍，k=m2/m1=2為任務PTG1的粒度細化因子,任務PTG1粒度細化后，通信負載的擴展倍數(shù)η=α+β(1-α)/k=1.495.

實驗中，并行任務qi調(diào)度至計算節(jié)點pf(i)，表示為二元組(qi,pf(i))，DAG并行任務PTG1與體系結(jié)構(gòu)HSG1中計算節(jié)點的映射關(guān)系具體為：(q11,p11),(q12,p11),(q13,p13),(q14,p11),(q15,p12),(q16,p14),(q17,p13),(q18,p12),(q19,p15),(q110,p15).在體系結(jié)構(gòu)HSG1擴展為HSG2，并行任務PTG1擴展細化為PTG2后，各并行子任務與計算節(jié)點的映射參照擴展之前的匹配映射，例如，任務q11細化為(q21-1,q21-2,q21-0),其中q21-1和q21-0映射至計算節(jié)點p21-1(即原計算節(jié)點p11)，q21-2映射至新增計算節(jié)點p21-2，其它子任務與計算節(jié)點的映射類似.

4.2.2 仿真實驗結(jié)果及分析

對于可變結(jié)構(gòu)的并行計算，在體系結(jié)構(gòu)已擴展升級好之后，并行任務采用任務粒度細化的擴展方法進行模擬擴展，在SimGrid3.1上運行模擬程序Simulator，實驗結(jié)果如表3所示.

表3中擴展后的速度效率0.361近似于擴展前的速度效率0.373，表明實驗中任務粒度細化擴展方法基本上實現(xiàn)了等速度效率擴展，擴展后的速度效率略低于擴展前的速度效率，主要是由于細化后的子任務之間規(guī)約開銷，從而影響了實際運行速度.另外，實驗中k=2,β=3.0, 根據(jù)公式(8)，有Φ>1，但實際上規(guī)約子任務計算負載總是客觀存在，實驗中取χ=0.14，χW1=390GI，從而有Φ=0.959.

為揭示不同的(k,β)對計算密集型、通信密集型及計算通信平衡型三類并行任務速度效率及可擴展性的影響，我們以表1中所描述的體系結(jié)構(gòu)，表2所描述的并行任務算法結(jié)構(gòu)為基準，以高通信負載比重模擬通信密集型任務，變換k和β，實施多次模擬擴展實驗.擴展實驗的速度效率變化曲線如圖4所示，可擴展性變化曲線如圖5所示.圖4中速度效率的變化曲線表明，在任務的結(jié)構(gòu)和計算負載，擴展參數(shù)(k,β)均相同時，通信密集型任務因通信延遲開銷較大，速度效率較計算密集型任務的速度效率明顯偏低，而計算通信平衡型任務的速度效率則介于兩者之間.

根據(jù)式(8)，當上述兩類任務的串行比α,以及參數(shù)k,β相同時，其可擴展性理應相同，但圖5中擴展性曲線表明，任務類型為通信密集型的并行計算，其可擴展性較計算密集型更小，計算通信平衡型任務的可擴展性介于兩者之間，這是由于通信密集型任務計算中通信負載比重較大，任務粒度細化生成的規(guī)約任務的計算負載明顯增加，致使其可擴展性降低.另外，圖5中計算密集型任務與通信密集型任務相比較，其可擴展性基本保持不變，這是因為計算密集型任務粒度細化擴展方法中，產(chǎn)生的額外通信、規(guī)約等開銷極少，可擴展性主要取決于參數(shù)k和β.

表2 可變結(jié)構(gòu)的并行任務擴展前后的性能參數(shù)(帶下劃線項為關(guān)鍵路徑包含的數(shù)據(jù)項)

表3 可變結(jié)構(gòu)并行計算任務粒度細化擴展實驗結(jié)果

(k,β),k:任務粒度細化因子；β:計算負載擴展因子

(k,β),k:任務粒度細化因子；β:計算負載擴展因子

5 結(jié)束語

對于一些成熟的、已成功運行的并行計算應用系統(tǒng)，為獲得更高的計算性能，通常會擴展計算節(jié)點規(guī)模，增大任務計算負載，優(yōu)化任務算法結(jié)構(gòu).針對此類可變結(jié)構(gòu)并行計算的可擴展問題，本文分析影響其可擴展性的并行任務因素及體系結(jié)構(gòu)因素，對并行任務及體系結(jié)構(gòu)進行圖建模.特別針對體系結(jié)構(gòu)業(yè)已擴展升級好，如何增大并行任務的計算負載，優(yōu)化任務算法結(jié)構(gòu)的擴展問題，提出了DAG任務粒度細化的可擴展方法，實質(zhì)上為變換圖結(jié)構(gòu)的可擴展方法.通過分析擴展前后的速度效率性能，證明了DAG任務粒度細化的擴展方法可基本實現(xiàn)可變結(jié)構(gòu)并行計算的等速度效率擴展.最后，為驗證所提出可擴展方法的有效性，編寫了基于網(wǎng)格計算模擬工具SimGrid3.10的C語言程序Simulator，模擬任務在體系結(jié)構(gòu)上的運行，從而實現(xiàn)模擬擴展實驗，結(jié)果表明所提出的擴展方法實現(xiàn)了可變結(jié)構(gòu)并行計算的等速度效率擴展.

[1] 李曉梅, 莫則堯, 胡慶豐,等. 可擴展并行算法的設計和分析[M]. 長沙:國防工業(yè)出版社,2000.

LI Xiaomei, MAO Zeyao, HU Qingfeng,etal. Design & analysis of scalable parallel algorithms[M]. Changsha: National Defense Industry Press, 2000.

[2] Grama A, Gupta A, Kumar V. Iso-efficiency: measuring the scalability of parallel algorithms and architectures[J]. IEEE Parallel & Distributed Technology, 1993, 1(3): 12.

[3] Sun X H, Rover D T. Scalability of parallel algorithm machine combinations[J]. IEEE Transactions on Parallel Distributed Systems, 1994, 5(6):599.

[4] Zhang X D, Yan Y, He K. Latency metric: an experimental method for measuring and evaluating parallel program and architecture scalability[J]. Journal of Parallel and Distributed Computing, 1994, 22(3): 392.

[5] Wu X F, Li W. Performance models for scalable cluster computing[J]. Journal of Systems Architecture, 1997, 44(3):189.

[6] 陳軍. 李曉梅. 近優(yōu)可擴展性：一種實用的可擴展性度量[J]. 計算機學報, 2001, 24(2):179.

CHEN Jun, LI Xiaomei. Near-optimal scalability: a practical scalability metric[J]. Chinese Journal of Computers, 2001, 24(2):179.

[7] 王與力, 楊曉東. 一種更有效的并行系統(tǒng)可擴展性模型[J].計算機學報, 2001, 24(1): 84.

WANG Yuli, YANG Xiaodong. A more effective scalability model for parallel system[J]. Chinese Journal of Computers, 2001, 24(1): 84.

[8] Chen Y, Sun X H, Wu M. Algorithm-system scalability of heterogeneous computing[J]. Journal of Parallel and Distributed Computing, 2008, 68(11): 1403.

[9] Yang X J, Wang Z Y, Xue J L. The reliability wall for exascale supercomputing[J]. IEEE Transactions on Computers, 2012, 61(6):767.

[10] Sun X H, Ni L M. Scalable problems and memory-bounded speedup[J]. Journal of Parallel and Distributed Computing, 1993, 19(1): 27.

[11] Yang X J, Du J, Wang Z Y. An effective speedup metric for measuring productivity in large-scale parallel computer systems[J]. Journal of Supercomputing, 2011, 56(2):164.

[12] Xiong H L, Zeng G S, Zeng Y. A novel scalability metric about iso-area of performance for parallel computing[J]. Journal of Supercomputing, 2014, 68(2):652.

[13] Tessier R, Pocek K, DeHon A. Reconfigurable computing architectures[J]. Proceedings of the IEEE, 2015, 103(3):332.

[14] 郝水俠, 曾國蓀, 譚一鳴. 計算任務與體系結(jié)構(gòu)匹配的異構(gòu)計算可擴展性分析[J]. 電子學報, 2010, 38(11): 2585.

HAO Shuixia, ZENG Guosun, TAN Yiming. Scalability analysis of heterogeneous computing based on computation task and architecture to match[J].ActaElectronicaSinica, 2010, 38(11): 2585.

[15] Xiong H L, Zeng G S, Ding C L,etal. Extensions by graph weight for parallel computing under the constraint of fixed structure[J]. IETE Journal of Research, 2015:doi:10.1080/03772063.2015.1093967, 2015.

Extension by Refining Task Granularity for Parallel Computation with Variable Structures

XIONG Huanliang1,2,3, ZENG Guosun1,3

(1. College of Electronics and Information Engineering, Tongji University, Shanghai 201804, China; 2. Software College， Jiangxi Agricultural University, Nanchang 330045， China; 3. Tongji Branch National Engineering & Technology Center of High Performance Computer, Shanghai 201804, China)

Aiming at such extension problem in parallel computation, this paper evaluates the key factors from parallel tasks and architecture which affect the scalability, and then models parallel tasks as well as architecture by the weighted graph. Especially, we propose the extension method of refining task granularity to realize an extension in parallel computation. The extension method transforms the graph’s structure and adjusts the weights of its nodes and edges in essence. Additionally, by further derivation, some significant conclusions about the new extension methods are drawn. Finally, the simulative experiments are conducted on the platform SimGrid to verify the effectiveness of the proposed extension methods. The results show that the new methods can realize iso-speed-e extension in parallel computation with variable structures, which is helpful for its practical extension.

parallel computation; machine and algorithm; variable structures; extension method

2015-10-08

上海市優(yōu)秀學科帶頭人計劃(10XD1404400);江西省自然科學基金(20161BAB212047,20151BAB207040);華為創(chuàng)新研究計劃(IRP-2013-12-03);高效能服務器和存儲技術(shù)國家重點實驗室開放基金(2014HSSA10);江西省教育廳科研項目(GJJ150426).

熊煥亮(1977—)，男，博士生，主要研究方向為并行分布處理.E-mail: 2012_xionghuanliang@#edu.cn

曾國蓀(1964—)，男，教授，博士生導師，工學博士，主要研究方向為并行計算、可信軟件和信息安全.

E-mail:gszeng@#edu.cn

TP338

A