復(fù)雜形狀飛行器CFD并行計(jì)算的靜態(tài)負(fù)載平衡問題的研究_圖文

1、復(fù)雜形狀飛行器CFD并行計(jì)算的靜態(tài)負(fù)載平衡問題的研究木 劉鑫。陸林生江南計(jì)算技術(shù)研究所.無錫214083摘要:本文主要討論復(fù)雜形狀飛行器CFD并行計(jì)算的靜態(tài)負(fù)載平衡問題.首先,本文從圖論的于以邊緣通信為特征的一般數(shù)值計(jì)算問題。本文論述了二維問題正方形劃分總通信量最小、并行效率最高,三維問題立方體劃分總通信量最小、并行效率最高的結(jié)論?；谝陨辖Y(jié)論和實(shí)際課題特點(diǎn),本文提出一種一維優(yōu)先的規(guī)則分塊算法和基于自動(dòng)重分塊的不規(guī)則分塊算法相結(jié)合的方法,實(shí)驗(yàn)結(jié)果證明,該方法實(shí)現(xiàn)簡單,能夠處理不同規(guī)模復(fù)雜外形的CFD實(shí)際課題,且能達(dá)到較優(yōu)的負(fù)載平衡和較高的通信效率,明顯提高并行程序的整體效率.關(guān)鍵詞:CFD;并

2、行計(jì)算;靜態(tài)負(fù)載平衡;規(guī)則劃分;自動(dòng)重分計(jì)算流體力學(xué)(CFD是一門利用計(jì)算機(jī)對流體的復(fù)雜流動(dòng)進(jìn)行數(shù)值模擬的學(xué)科。流體的運(yùn)動(dòng)規(guī) 律可由歐拉方程、NS(Navier-Stokes方程等數(shù)學(xué)方程組來描述,CFD則采用數(shù)值計(jì)算方法求解這些 方程,研究流體運(yùn)動(dòng)特性,得出流體的時(shí)空流動(dòng)規(guī)律。在CFD中,首先要把計(jì)算區(qū)域離散化為網(wǎng)格。 流場的狀態(tài)由網(wǎng)格的各種流動(dòng)特征量來表述,如速度、密度、壓力、溫度等。CFD程序主要是對特 征量進(jìn)行大量迭代,由于計(jì)算量非常大,需要在高性能并行計(jì)算機(jī)或集群并行計(jì)算機(jī)系統(tǒng)上進(jìn)行大 規(guī)模并行計(jì)算。復(fù)雜形狀飛行器的一個(gè)重要特征是計(jì)算區(qū)域由多個(gè)大小不等的物理塊組成,這給負(fù)載平衡帶 來

3、很大的挑戰(zhàn)。如何進(jìn)行任務(wù)劃分與處理器分配是獲得較高的并行效率的關(guān)鍵.當(dāng)前大部分的CFD 并行計(jì)算課題的任務(wù)劃分采用人工劃分方式,或者只能實(shí)現(xiàn)計(jì)算區(qū)域較簡單情形的自動(dòng)任務(wù)劃分, 這些方法己不能滿足復(fù)雜形狀飛行器CFD的大規(guī)模并行計(jì)算的需要。本文結(jié)合實(shí)際應(yīng)用課題。從理 論探討和工程應(yīng)用出發(fā)在解決復(fù)雜形狀飛行器CFD并行計(jì)算的靜態(tài)負(fù)載平衡問題上做了一些嘗試。木本課題得到國家863高科技發(fā)展計(jì)劃(編號(hào):2003AA723050,國家自然科學(xué)基金資助項(xiàng)目(編號(hào):10072077 資助劉鑫,博I:生,主要研究領(lǐng)域?yàn)椴⑿兴惴ㄅc并行識(shí)別;陸林生,教授,博:I:生導(dǎo)師.主要研究領(lǐng)域?yàn)椴⑿兴惴ㄅc并行識(shí)別.61本文

4、先從圖論的角度討論了靜態(tài)負(fù)載平衡問題。給出靜態(tài)負(fù)載平衡問題的二二個(gè)優(yōu)化目標(biāo)。即 點(diǎn)集等分。最短通路和通信量最小。對于分布存儲(chǔ)的并行計(jì)算機(jī),當(dāng)處理器同構(gòu)時(shí).負(fù)載,f,衡問題 等價(jià)于一個(gè)線圖的分割問題.其對應(yīng)的約束條件,一是要求各處理器上的任務(wù)盡可能柏等,二是處 理器之間的最大通信量為極小。同時(shí),對于以邊緣通信為特征的一般數(shù)值計(jì)算問題。本文論述了二:維問題正方形劃分總通信量最小、并行效率最高,三維問題立方體劃分總通信量最小、并行效率最 高的結(jié)論.并給出實(shí)際分塊過程中應(yīng)遵循的準(zhǔn)則:使盡可能多的處理器處理規(guī)模較大的數(shù)據(jù)子集。 基于以上結(jié)論和本應(yīng)用課題的特點(diǎn)。本文提出兩種負(fù)載平衡算法:一維優(yōu)先的規(guī)則分塊

5、算法和基于 自動(dòng)重分塊的不規(guī)則分塊算法,分別處理中小規(guī)模和大規(guī)模并行的問題。實(shí)際使用時(shí),采用兩種算 法相結(jié)合的方法,當(dāng)處理器數(shù)少于或接近物理塊數(shù)時(shí).使用基于自動(dòng)重分塊的不規(guī)則分塊算法,該 算法更靈活,在處理器很少的情況下也可以獲得較好的負(fù)載平衡,彌補(bǔ)額外帶來的通信開銷;當(dāng)處 理器數(shù)大于物理塊數(shù)時(shí),采用一維分解優(yōu)先的規(guī)則分塊算法,這種算法在大規(guī)模并行時(shí)優(yōu)勢更明顯。 實(shí)驗(yàn)結(jié)果證明,兩種負(fù)載平衡算法相結(jié)合的方法實(shí)現(xiàn)簡單,能夠處理不同規(guī)模復(fù)雜外形的CFD實(shí)際 課題,且能達(dá)到較優(yōu)的負(fù)載平衡和較高的通信效率,明顯提高并行程序的整體效率。2靜態(tài)負(fù)載平衡問題的圖論表示用平面圖上的一個(gè)點(diǎn)集U=“l(fā),“2,甜口表

6、示p個(gè)處理器,用這些點(diǎn)的可能連線 F=Z,厶,六u×u表示節(jié)點(diǎn)間的通信線路。如果是同構(gòu)網(wǎng)絡(luò),則可以略去節(jié)點(diǎn)的權(quán)重 也不必考慮邊的方向性。則處理器的相互關(guān)系可以用無向圖H=川,F表示。一個(gè)并行應(yīng)用程序 我們使用賦權(quán)圖G=(V,E,p,仃來描述, 其中節(jié)點(diǎn)V=,I,2,。, 邊 E=巳,P2,P,V×V.節(jié)點(diǎn)權(quán)重戶:V專R,邊的權(quán)重盯:E專R。對于本文的cFD 問題,節(jié)點(diǎn)代表各處理器上的數(shù)據(jù)子集,邊代表數(shù)據(jù)通信.該圖的拓?fù)淇捎蓤D的鄰接矩陣A表示:彳=(%。,其中。1f,/刀,=l表示節(jié)點(diǎn)M、有通信,%=O表示節(jié)點(diǎn)U、一無 通信。G的端容量矩陣T為一實(shí)對稱矩陣.用來表示節(jié)點(diǎn)之間的

7、通信量:T=(ff,。,。其中 lf,療.當(dāng)f=,時(shí)。令f,=0,即忽略節(jié)點(diǎn)與自身的通信開銷。G的頂點(diǎn)容量代表節(jié)點(diǎn)的 數(shù)據(jù)處理的計(jì)算量,用實(shí)列向量C表示,則C=cI,乞,巳7=p(H,p(v2,戶(%. f l G中,節(jié)點(diǎn)分配于H中的f節(jié)點(diǎn)呵 Io G中,節(jié)點(diǎn)不分配于H中的,節(jié)點(diǎn)另有列向量X=(jcl,x2,童。7表示每個(gè)處理器的運(yùn)算開銷,則有X=BC.為了使并行系統(tǒng)達(dá)到較好的負(fù)載平衡狀態(tài),首先必須控制單個(gè)處理器承受的最大負(fù)載load(萬=max 芝:戶(V,=巴登(x, (1 -暑U I ssPpJ EV.石(”,l62設(shè)G巾的某個(gè)邊為e=VI,V2E,咖=甜IU,咖2夕=“2U。設(shè)w。為“

8、I到“。的 路徑,則圖G中某一邊在H中需要的最長通信鏈路10ng(萬-。器EM (2 此外。通信線路.兀上最大通信流量為加=盯(eo?(1.”2eE,E-.為了達(dá)到較好的負(fù)載平衡,應(yīng)控制晟大通信量.所以負(fù)載平衡的第三個(gè)指標(biāo)為:n。w(萬2,o譬。F加2廠囂譬?？?薈eE盯(e (3 _,。Ew。以上(1、(2、(3式給出了負(fù)載平衡問題的三個(gè)優(yōu)化目標(biāo)。即點(diǎn)集的等分,圖的最短通路問題, 網(wǎng)絡(luò)流問題。由于當(dāng)前MPP的通信速度很快。圖H可以看成是完全連接的,此時(shí)1w。I暑l。這樣, 圖G向圖H的映射問題可以退化成圖G的分割問題。設(shè)有p個(gè)處理器節(jié)點(diǎn),則負(fù)載平衡問題轉(zhuǎn) 化成求圖G的p個(gè)子集,且滿足cut(

9、石=:盯(e (4 瓢囂齲為極小。上式的意義是要求對圖G進(jìn)行切割時(shí)。被切斷的邊上的通信總量為最小。綜上所述,當(dāng) 處理器同構(gòu)時(shí),負(fù)載平衡問題等價(jià)于一個(gè)圖的分割問題,其對應(yīng)的約束條件。一是要求各處理器上 的任務(wù)盡可能相等,二是處理器之間的最大通信量為極小.3預(yù)備知識(shí)圖的分割可以采用幾何方法,簡單的幾何方法是將圖的節(jié)點(diǎn)在某一軸投影,再沿軸向進(jìn)行劃 分,這個(gè)軸可以是坐標(biāo)軸或者是圖的最小慣性軸。因?yàn)楸疚乃肅FD例題使用結(jié)構(gòu)化網(wǎng)格,所以我 們采用沿各個(gè)計(jì)算坐標(biāo)軸向進(jìn)行劃分的方法。下面我們分別就不同分塊算法的通信優(yōu)化問題和并行 效率問題進(jìn)行討論。3.1不同分塊算法的通信優(yōu)化問題通信優(yōu)化問題較為復(fù)雜,這里我

10、們假設(shè)只有二排邊緣通信的簡單情況。先考慮二維問題任葸 劃分的情況,每塊大小為t,只,f=1,2,p,二維區(qū)域大小為×,則總的通信量 。=2(羔(z,+J,一2,問題歸結(jié)為求(+兒一2在一y。=2/p條件下的最 f=I ,_l小值。又藝(x,+”一2羔2i萬一2=2(厄一1,當(dāng)且僅當(dāng)=兒時(shí),等號(hào)成 ;I f=I:芷,即j:維向I題任意劃分時(shí),正方形劃分總通信量晟小。63同樣地,三維問題的任意劃分情況歸結(jié)為求(x,y。+少,乙+x.z,一32在 ,=I工.J,z,=3/p條件下的最小值。一 2(毛J,。+y,z。+工,zf一322藝3(工,J,z,了一3J2=32(p一I當(dāng)且僅當(dāng)=y,=

11、z,時(shí),等號(hào)成立,即三維問題任意劃分時(shí),立方體劃分總通信量最小。3.2不同分塊算法的并行效率問題以八點(diǎn)平滑為例:曰(f,_,七=(彳(,一l,_,一I,七一I+彳(,/一I,七一1+彳(f一1,.,七一1+彳(,/,七一1+彳(fl,/一l,七+彳(f,/一l,七+彳(,一l,/,七+彳(f,一|f,七/8其中工七=l'2,.'。設(shè)一維分解的加速比為口l二維分解的加速比為口2.三維分解的加速比為口,.處理器個(gè)數(shù) 為p t每點(diǎn)的通信時(shí)間為f二維分解時(shí)每個(gè)處理器的數(shù)據(jù)子集為,.c,三維分解時(shí)每個(gè)處 理器的數(shù)據(jù)子集為,.cJl,假設(shè)>>1,則N 3%2礦石而33口,=了一

12、:_二_:一 /p+f2(彤十洲+腳 3/肘+f幸22(p一+2p州2當(dāng)且僅當(dāng),.=c=/萬時(shí)等號(hào)成立。33%2礦石鬲麗百;再而礦石看麗甲。/p+f2(陽+cJl,+砌 3/口+r62D一273當(dāng)且僅當(dāng)廠=f=廳=J7、r/Vp時(shí)等號(hào)成立。易得當(dāng)p>33時(shí),max(口3>口I:當(dāng)p>o時(shí)。max(口3>ma(口2;當(dāng)p>(2+12時(shí),max他2>口I綜上所述-當(dāng)且僅當(dāng),%取得最大值3/(3/p+r62p一273; 若p>5,則max(口3>max(口2>口I。3.3實(shí)際分塊過程中應(yīng)遵循的準(zhǔn)則設(shè)有Jp個(gè)處理器并行處理由個(gè)數(shù)據(jù)構(gòu)成的數(shù)據(jù)集S,分

13、配給每個(gè)處理器的數(shù)據(jù)子集S;包 含%個(gè)數(shù)據(jù)(f=1,2,pt且有當(dāng),/, /=1,2,ps,n s,=o U S=s I(吩一動(dòng)/司<占其中萬=/p是平均分配給各處理器的數(shù)據(jù)數(shù),占是給定的誤差。設(shè)有冊(mp個(gè)處理器中包 含的數(shù)據(jù)個(gè)數(shù)相等.且最大,則m越大.并行效率越高。證明:設(shè)有聊個(gè)處理器中包含的數(shù)據(jù)個(gè)數(shù)為門帳萬,先證明歷越大,l(刀吣一萬/矧越小。 不失一般性,令f=1,2,肌個(gè)處理器各包含"。,個(gè)數(shù)據(jù).則有塵生堅(jiān)二!:生堅(jiān)一1:堡堅(jiān):旦 +1. =:一.1. ,l。+乙惕 f=朋+I所以,當(dāng)朋越大,l(,l刪一萬/叫越小. 再證并行效率盯: 顯然所.門嘣+羔偉<(肌+

14、1.玎哪+蘭%t,+l ,=朋+2顯然。當(dāng)I(療一一萬/萬l越小,效率J7越高。綜上所述,實(shí)際分塊過程中應(yīng)遵循使盡可能多的處理器處理規(guī)模較大的數(shù)據(jù)子集的準(zhǔn)則,避 免出現(xiàn)某一個(gè)處理器的負(fù)載過大的情況。4靜態(tài)負(fù)載平衡算法實(shí)現(xiàn)及實(shí)驗(yàn)結(jié)果4.1一維分解優(yōu)先的規(guī)則分塊算法lUD啤一,D口%w/,D口l<占。如果有處理器不能滿足要求.則將給定的處理器總數(shù)遞減,再重新 分塊(這里取F0.1。一維分解優(yōu)先的規(guī)則分塊算法具體步驟如下:I把物理塊按從小到大的順序排列,先處理較小的物理塊,如果它們的數(shù)據(jù)子集之和小于等于 平均負(fù)載,則把它們組合在一個(gè)處理器中:II其余物理塊從負(fù)載平衡的角度出發(fā),按網(wǎng)格數(shù)比例分配

15、處理器數(shù),每個(gè)物理塊分配的處理 器數(shù)如果不是整數(shù),需要取整,處理器數(shù)小的向上取整,處理器數(shù)多的向下取整:為保持總數(shù)不變,修改最大塊的處理器數(shù):IV試探一維分解.如果劃分后該方向網(wǎng)格點(diǎn)數(shù)>規(guī)定的最小網(wǎng)格點(diǎn)數(shù),則一維分解; V如果該物理塊分配奇數(shù)個(gè)處理器且一維分解不成功.將處理器數(shù)調(diào)整為偶數(shù):VI試探:二維分解,如果劃分后該方向網(wǎng)格點(diǎn)數(shù)>=規(guī)定的最大網(wǎng)格點(diǎn)數(shù),則:二維分解; VII一維、二:維分解不成功的,則三維分解。65果遇到不能整除的情況，則根據(jù)該物理塊網(wǎng)格數(shù)大小將分配的處理器數(shù)進(jìn)行遞增或遞減，然厲再重 新進(jìn)行二維分解或三維分解。因?yàn)檫@樣的整除問題的存在，分塊后的處理器總數(shù)肯可能小

16、丁給定的 處理器數(shù)。 基于自動(dòng)重分的不規(guī)則分塊算法 當(dāng)處理器數(shù)小于物理塊數(shù)時(shí)我們發(fā)現(xiàn)一維分解優(yōu)先的規(guī)則分塊算法效果不理想，如果物理 塊大小相差很大而處理器數(shù)很少。規(guī)則分塊算法就不能滿足負(fù)載平衡的要求了。下面本文提出一種 新的基于自動(dòng)重分的不規(guī)則分塊算法，這種分塊算法適用面很廣，可以用在同構(gòu)機(jī)群上和異構(gòu)機(jī)群 上。該算法的基本原理是將超出平均負(fù)載的最大塊進(jìn)行重新分割以滿足負(fù)載平衡的要求，因而更為 靈活，在處理器數(shù)少于物理塊數(shù)時(shí)也可以達(dá)到較優(yōu)的負(fù)載平衡。這種不規(guī)則分塊算法在通信效率上 可能略遜于上一種方法，但是當(dāng)處理器數(shù)少的時(shí)候通信開銷相對于計(jì)算量來說比較小，較優(yōu)的負(fù)載 平衡可以彌補(bǔ)帶來的額外通信開

17、銷，所以這種算法是可行的。基于自動(dòng)重分的不規(guī)則分塊算法的具 體步驟如下： 初始化： 計(jì)算平均處理時(shí)間： ，礦 乙。 ，曲 嗽 粕一弱 其中：為每塊的網(wǎng)格數(shù)：為每個(gè)網(wǎng)格的運(yùn)算量（用浮點(diǎn)操作數(shù)表示）；只眥為每個(gè)處理 器每秒的浮點(diǎn)操作數(shù)。 假設(shè)所有處理器都分配一個(gè)非常小的小塊計(jì)算得到初始的雕： ；宰形 胖 主循環(huán)： ，（尸，） 眥 其中，（，）表示分配給該處理器的所有小塊的集合。 如果有小塊未分配，則將最大的未分配的小塊分配給最先完成計(jì)算的處理器； 如果（，腓乙（唧），則沿最長邊按比例分裂此塊以滿足雕乙，將剩下的部分 小塊劃分為未分配小塊，將該小塊劃分給該處理器。 在實(shí)際的處理過程中。我們采用兩種分

18、塊算法相結(jié)合的方式。如果給定的處理器數(shù)少于或接 近物理塊數(shù)，則采用基于自動(dòng)重分的不規(guī)則分塊算法，如果給定的處理器數(shù)大于物理塊數(shù)則采用 一維分解優(yōu)先的規(guī)則分塊算法。另外，在基于自動(dòng)重分的不規(guī)則分塊算法的具體實(shí)現(xiàn)中，也應(yīng)考慮 到上面提到的兩個(gè)問題：（）每個(gè)處理器包含的各方向的網(wǎng)格點(diǎn)數(shù)要有門檻值，但沿最長邊方向按 比例分裂小塊時(shí)?？赡茈y以滿足各方向的網(wǎng)格點(diǎn)數(shù)至少要大于的條件所以這種情況下將小塊沿 最長邊方向和次長邊方向按比例進(jìn)行二維分裂將剩下的三個(gè)部分小塊劃分為未分配小塊，將分裂 后的小塊劃分給該處理器。（）劃分給每個(gè)處理器的負(fù)載與平均負(fù)載之差要有限制。如果有一個(gè)處 理器彳能滿足要求。則修改哪的值調(diào)

19、用主循環(huán)重新分塊直至滿足負(fù)載，衡要求。 實(shí)驗(yàn)結(jié)果 本例題主要模擬某超燃沖壓發(fā)動(dòng)機(jī)的流場情況，控制方程是考慮化學(xué)非衡反應(yīng)的非定常二三 維方程： 望望塑絲墜塑墮 二一一一一二 缸 敘 包 砂 砂 式中：，辦，聲，盧，）是守恒變量；、是無粘通量向量； 、，、，是粘通量向量：是化學(xué)反應(yīng)源項(xiàng)。 計(jì)算方法采用隱式有限體積法，具有二排邊緣通信和二元遞歸計(jì)算特點(diǎn)。本題的計(jì)算規(guī)模比 較大計(jì)算區(qū)域劃分為個(gè)區(qū)，對應(yīng)塊不同類型的網(wǎng)格。網(wǎng)格具體情況見表、分 別表示三個(gè)方向的最大網(wǎng)格點(diǎn)數(shù)。 表 物理塊號(hào) 計(jì)算區(qū)域的具體情況 物理塊號(hào) 一 引 引 鉀 “ 定義衡量負(fù)載平衡的標(biāo)準(zhǔn)矽型鏟，其中是處理器數(shù)，。為每個(gè)處理器分得的 網(wǎng)格數(shù)，（）。采用上面提出的算法進(jìn)行負(fù)載分配，結(jié)果見表。 表不同處理器數(shù)的負(fù)載平衡情況 們 西（） 應(yīng)用本文提出的靜態(tài)負(fù)載平衡算法對發(fā)動(dòng)機(jī)流場情況的大規(guī)模并行計(jì)算結(jié)果