熊煥亮， 曾國(guó)蓀

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

?

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

熊煥亮1,2,3， 曾國(guó)蓀1,3

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.1 DAG任務(wù)粒度細(xì)化擴(kuò)展的前提假設(shè)

(1)假設(shè)擴(kuò)展前DAG并行任務(wù)已在原有并行機(jī)上成功運(yùn)行，滿足既定的功能和性能要求.

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

(1)

(2)

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

(3)

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

(4)

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

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

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

3.2 DAG任務(wù)粒度細(xì)化的擴(kuò)展過(guò)程

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

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

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

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

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

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

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

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

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

{

初始化任務(wù)隊(duì)列Queue,節(jié)點(diǎn)所在層號(hào)數(shù)組nodeLevel[],每層的計(jì)算節(jié)點(diǎn)數(shù)levelCount[]全為0;

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

將DAG圖中所有入度為0的任務(wù)節(jié)點(diǎn)入隊(duì);

while(Queue不為空){

GetQueuelength;//取當(dāng)前隊(duì)列的長(zhǎng)度

totalNodeNum+=Queuelength;//計(jì)算DAG并行任務(wù)總?cè)蝿?wù)數(shù).

for(int i=0;i

隊(duì)頭節(jié)點(diǎn)head出隊(duì);

nodeLevel[head.nodeNumber]=currentLevel;//標(biāo)記節(jié)點(diǎn)所在層號(hào).

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

}

currentLevel++;

}

for(int i=0;i

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

}

}

}

圖2 DAG并行任務(wù)的擴(kuò)展及其粒度細(xì)化

4 可變結(jié)構(gòu)并行計(jì)算DAG任務(wù)粒度細(xì)化擴(kuò)展方法的性能評(píng)估

4.1 DAG任務(wù)擴(kuò)展及粒度細(xì)化后并行計(jì)算性能分析

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

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

(2)DAG并行任務(wù)擴(kuò)展細(xì)化參數(shù)的假定

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

(5)

隨著體系結(jié)構(gòu)標(biāo)記速度由C1擴(kuò)展提高為C2，DAG并行任務(wù)中每個(gè)任務(wù)的并行計(jì)算負(fù)載相應(yīng)地?cái)U(kuò)展β=C2/C1倍，任務(wù)q1i擴(kuò)展后的計(jì)算負(fù)載由原串行部分和擴(kuò)展后的并行部分組成，即w2i=αiw1i+β(1-αi)w1i.

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

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

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

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

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

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

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

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

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

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

(6)

并行計(jì)算的速度效率近似為

(7)

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

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

(8)

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

4.2 可變結(jié)構(gòu)并行計(jì)算擴(kuò)展的仿真實(shí)驗(yàn)

4.2.1 仿真實(shí)驗(yàn)工具及實(shí)驗(yàn)設(shè)計(jì)

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

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

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

實(shí)驗(yàn)中，并行任務(wù)qi調(diào)度至計(jì)算節(jié)點(diǎn)pf(i)，表示為二元組(qi,pf(i))，DAG并行任務(wù)PTG1與體系結(jié)構(gòu)HSG1中計(jì)算節(jié)點(diǎn)的映射關(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擴(kuò)展為HSG2，并行任務(wù)PTG1擴(kuò)展細(xì)化為PTG2后，各并行子任務(wù)與計(jì)算節(jié)點(diǎn)的映射參照擴(kuò)展之前的匹配映射，例如，任務(wù)q11細(xì)化為(q21-1,q21-2,q21-0),其中q21-1和q21-0映射至計(jì)算節(jié)點(diǎn)p21-1(即原計(jì)算節(jié)點(diǎn)p11)，q21-2映射至新增計(jì)算節(jié)點(diǎn)p21-2，其它子任務(wù)與計(jì)算節(jié)點(diǎn)的映射類似.

4.2.2 仿真實(shí)驗(yàn)結(jié)果及分析

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

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

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

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

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

表3 可變結(jié)構(gòu)并行計(jì)算任務(wù)粒度細(xì)化擴(kuò)展實(shí)驗(yàn)結(jié)果

(k,β),k:任務(wù)粒度細(xì)化因子；β:計(jì)算負(fù)載擴(kuò)展因子

(k,β),k:任務(wù)粒度細(xì)化因子；β:計(jì)算負(fù)載擴(kuò)展因子

5 結(jié)束語(yǔ)

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

[1] 李曉梅, 莫?jiǎng)t堯, 胡慶豐,等. 可擴(kuò)展并行算法的設(shè)計(jì)和分析[M]. 長(zhǎng)沙:國(guó)防工業(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)可擴(kuò)展性：一種實(shí)用的可擴(kuò)展性度量[J]. 計(jì)算機(jī)學(xué)報(bào), 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)可擴(kuò)展性模型[J].計(jì)算機(jī)學(xué)報(bào), 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] 郝水俠, 曾國(guó)蓀, 譚一鳴. 計(jì)算任務(wù)與體系結(jié)構(gòu)匹配的異構(gòu)計(jì)算可擴(kuò)展性分析[J]. 電子學(xué)報(bào), 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)秀學(xué)科帶頭人計(jì)劃(10XD1404400);江西省自然科學(xué)基金(20161BAB212047,20151BAB207040);華為創(chuàng)新研究計(jì)劃(IRP-2013-12-03);高效能服務(wù)器和存儲(chǔ)技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室開(kāi)放基金(2014HSSA10);江西省教育廳科研項(xiàng)目(GJJ150426).

熊煥亮(1977—)，男，博士生，主要研究方向?yàn)椴⑿蟹植继幚?E-mail: 2012_xionghuanliang@#edu.cn

曾國(guó)蓀(1964—)，男，教授，博士生導(dǎo)師，工學(xué)博士，主要研究方向?yàn)椴⑿杏?jì)算、可信軟件和信息安全.

E-mail:gszeng@#edu.cn

TP338

A