唐 波，王勇獻(xiàn)

(國防科學(xué)技術(shù)大學(xué)計(jì)算機(jī)學(xué)院，湖南 長沙 410073)

1 引言

計(jì)算流體力學(xué)CFD(Computational Fluid Dynamics)是一門利用計(jì)算機(jī)對流體的復(fù)雜流動規(guī)律進(jìn)行數(shù)值模擬的學(xué)科。在CFD數(shù)值模擬中, 首先要把計(jì)算區(qū)域空間離散化為網(wǎng)格, 生成模擬計(jì)算過程中所需要的網(wǎng)格文件。網(wǎng)格主要分為結(jié)構(gòu)網(wǎng)格和非結(jié)構(gòu)網(wǎng)格, 本文主要關(guān)注結(jié)構(gòu)網(wǎng)格。隨著科學(xué)技術(shù)的發(fā)展, CFD數(shù)值模擬精度要求越來越高, 網(wǎng)格規(guī)模越來越大, 要滿足這種需求, 唯一的可行手段就是發(fā)展大規(guī)模并行計(jì)算。

當(dāng)采用結(jié)構(gòu)網(wǎng)格時, 計(jì)算區(qū)域被離散為多個大小不等的網(wǎng)格區(qū)塊, 在模擬計(jì)算過程中, 這些區(qū)塊被分配到不同進(jìn)程上進(jìn)行流體流動規(guī)律的數(shù)值模擬。如何使得數(shù)值模擬過程中各個進(jìn)程上任務(wù)負(fù)載平衡, 是提高并行CFD程序性能的關(guān)鍵技術(shù)之一。對于當(dāng)前并行CFD數(shù)值模擬應(yīng)用, 任務(wù)負(fù)載平衡問題已經(jīng)變得越來越復(fù)雜, 隨著并行計(jì)算規(guī)模的加大, 進(jìn)程間通信開銷的大小對并行性能的影響在加大; 網(wǎng)格塊數(shù)和進(jìn)程數(shù)的不匹配, 網(wǎng)格塊的計(jì)算量與進(jìn)程的計(jì)算能力不匹配, 使得傳統(tǒng)的分割或組合策略不能很好滿足負(fù)載平衡的需求; 隨著近年來異構(gòu)并行機(jī)的出現(xiàn), 不同類型處理器進(jìn)程上的計(jì)算能力不一樣, 不同類型處理器進(jìn)程間的通信能力不一樣, 使得傳統(tǒng)的負(fù)載平衡算法已不能滿足負(fù)載平衡要求。因此，有必要研究一種新的負(fù)載平衡算法來滿足當(dāng)前的并行CFD任務(wù)負(fù)載平衡需求。

目前, 國際上已有很多并行CFD任務(wù)負(fù)載平衡軟件, 如MB-split; 也有多種負(fù)載平衡算法, 如Streng M等[1]和Ytterstrom A[2]提出的三種經(jīng)典的負(fù)載平衡算法:遞歸對分法、貪婪負(fù)載平衡算法、增量貪婪負(fù)載平衡算法, Saule E提出的一種新的啟發(fā)式算法等[3]。國內(nèi)也有相應(yīng)的研究, 如張娟等人[4]提出的基于Block的遞歸二分對無向圖剖分算法, 鄭秋亞等人[5]提出的一種類似貪婪負(fù)載平衡算法的方法, 李桂波等人[6]提出的基于遺傳算法的任務(wù)負(fù)載平衡算法等。上述軟件和算法都只適應(yīng)特定的任務(wù)分配情形, 不能很好地滿足當(dāng)前并行CFD任務(wù)負(fù)載平衡的需求。

2 問題描述

2.1 計(jì)算量和通信開銷的度量

計(jì)算量與通信開銷是衡量大規(guī)模并行計(jì)算負(fù)載平衡的兩個重要因素, 它們都與具體的應(yīng)用問題緊密相關(guān)。在典型的多區(qū)結(jié)構(gòu)網(wǎng)格CFD應(yīng)用中, 根據(jù)所采用的求解器類型的不同, 計(jì)算量跟離散網(wǎng)格單元呈不同的關(guān)系。例如, 在經(jīng)典的顯式Runge-Kutta求解器及隱式LUSGS求解器中, 每個網(wǎng)格單元上執(zhí)行的計(jì)算量大體相等, 各網(wǎng)格塊的計(jì)算量與網(wǎng)格塊中網(wǎng)格單元數(shù)成正比。本文重點(diǎn)關(guān)注這兩類求解器, 因此計(jì)算量可以簡化為網(wǎng)格單元數(shù)。

Figure1 Parallel computer architecture圖1 圖1 并行計(jì)算機(jī)體系結(jié)構(gòu)

并行計(jì)算的通信開銷則依賴于高性能計(jì)算平臺的硬件體系結(jié)構(gòu)及并行計(jì)算組織方式。當(dāng)前的主流并行計(jì)算機(jī)的體系結(jié)構(gòu)如圖1所示, 一臺并行計(jì)算機(jī)內(nèi)有多個結(jié)節(jié), 各個結(jié)節(jié)的配置一樣, 每個結(jié)節(jié)內(nèi)可以包含多種類型的處理器, 每個處理器中可以創(chuàng)建多個進(jìn)程。其中, 不同處理器類型進(jìn)程的計(jì)算能力不一樣, 不同進(jìn)程之間的通信開銷隨著進(jìn)程所在處理器類型不一樣和是否在同一結(jié)節(jié)內(nèi)而不同。如P1與P1、P1與P2、P2與P2之間的通信開銷隨著它們是否在同一結(jié)節(jié)內(nèi)而不同。

因此,如何對進(jìn)程間的通信開銷進(jìn)行準(zhǔn)確建模與度量將變得異常重要。在以往CFD任務(wù)負(fù)載平衡的研究中, 通常用通信量代替通信開銷, 當(dāng)通信開銷與通信量二者不成正比時, 這種代替不能準(zhǔn)確地反映進(jìn)程間通信所占時間。經(jīng)過測試和總結(jié), 我們用式(1)的分段線性函數(shù)來刻畫進(jìn)程間的通信開銷與通信量的關(guān)系:

C(x)=ax+b,x∈[x1,x2]

(1)

其中，x代表通信量(單位:KB),C(x)為x通信量下的通信開銷(單位:ms),a、b是與機(jī)器硬件相關(guān)的參數(shù)。

2.2 負(fù)載平衡問題的數(shù)學(xué)描述

在并行CFD數(shù)值模擬計(jì)算中, 假定整個CFD流場區(qū)域由Nz個網(wǎng)格塊組成, 而高性能計(jì)算資源包含(圖1中)結(jié)節(jié)Nnode個, 每個結(jié)節(jié)內(nèi)創(chuàng)建a1個P1類型進(jìn)程, 創(chuàng)建a2個P2類型進(jìn)程, 整個計(jì)算的總進(jìn)程數(shù)為Np=Nnode×(a1+a2)。CFD任務(wù)負(fù)載平衡需要將Nz個網(wǎng)格塊分配到Np個進(jìn)程上, 使得其達(dá)到任務(wù)負(fù)載平衡。下面建立其數(shù)學(xué)描述。

CFD任務(wù)負(fù)載平衡問題的數(shù)學(xué)描述:定義進(jìn)程i上期望負(fù)載計(jì)算量為Wi, ave;每給定一種任務(wù)分配方式M,我們用Wi(M)表示進(jìn)程i上的實(shí)際計(jì)算量,Ci(M)表示進(jìn)程i與其余進(jìn)程間的通信總開銷。定義進(jìn)程i上的計(jì)算負(fù)載平衡因子gi(M)如式(2)所示,它刻畫了進(jìn)程i上實(shí)際計(jì)算負(fù)載與期望計(jì)算負(fù)載間的相對偏差量。定義任務(wù)分配方案M下的最大通信開銷f(M)如式(3)所示, 它表示通信負(fù)載最大的進(jìn)程上的通信開銷量：

(2)

(3)

本文的CFD任務(wù)負(fù)載平衡模型旨在尋找一個分配方案使得以下約束優(yōu)化問題成立：

(1)目標(biāo)函數(shù)：minf(M)；

(2)約束條件：gi(M)=0,i∈{0, 1, 2, …,Np-1}。

其中，M為不同的分配方案。

3 算法設(shè)計(jì)

在真實(shí)的并行CFD任務(wù)負(fù)載平衡應(yīng)用中, 我們通常會遇到進(jìn)程數(shù)遠(yuǎn)大于網(wǎng)格塊數(shù)或者網(wǎng)格塊計(jì)算量大于進(jìn)程所期望負(fù)載計(jì)算量的情況, 這時我們需要對網(wǎng)格塊進(jìn)行分割，以滿足負(fù)載平衡的需求; 也會遇到進(jìn)程數(shù)遠(yuǎn)小于網(wǎng)格塊數(shù)的情況, 這時我們需要對網(wǎng)格塊進(jìn)行組合映射，以達(dá)到各個進(jìn)程上的負(fù)載平衡。為了適應(yīng)各種應(yīng)用情形, 本文提出的負(fù)載平衡算法分為三步：首先，通過一定原則對原始網(wǎng)格塊進(jìn)行分割, 使其塊數(shù)大于進(jìn)程數(shù), 并使得體積最大網(wǎng)格塊的計(jì)算量不超過進(jìn)程所期望負(fù)載計(jì)算量; 然后，對第一步分割后的網(wǎng)格塊進(jìn)行組合分配, 這是一個NP完全問題, 本文采用遺傳算法來解決這一組合映射問題; 當(dāng)經(jīng)過前兩步處理仍存在計(jì)算負(fù)載不平衡的進(jìn)程時, 則啟動第三步處理, 對所有這些進(jìn)程上的計(jì)算量進(jìn)行增減微調(diào), 直至所有進(jìn)程都達(dá)到負(fù)載平衡需求。下面對這三步進(jìn)行詳細(xì)介紹。

3.1 網(wǎng)格塊循環(huán)分割算法及網(wǎng)格塊分割策略

對于給定的進(jìn)程數(shù)目及原始網(wǎng)格分布狀態(tài),可計(jì)算出每個進(jìn)程上計(jì)算的平均網(wǎng)格量,以此為基準(zhǔn),當(dāng)原始網(wǎng)格中存在體積超大的網(wǎng)格塊時,為了完成負(fù)載平衡,必須對這樣的網(wǎng)格塊進(jìn)行分割。這時可實(shí)施以下的網(wǎng)格塊循環(huán)分割算法, 使每個網(wǎng)格塊的體積大小不超過單個進(jìn)程的平均網(wǎng)格量,從而可使用第二步完成網(wǎng)格塊向進(jìn)程上的組合映射。網(wǎng)格塊循環(huán)分割算法的核心是維護(hù)一個網(wǎng)格塊列表和一個進(jìn)程列表,通過反復(fù)迭代,逐次完成網(wǎng)格塊的分割。

3.1.1 網(wǎng)格塊循環(huán)分割算法

輸入原始網(wǎng)格塊, 找出未標(biāo)記體積最大網(wǎng)格塊, 記該網(wǎng)格塊為Zunsign, 其計(jì)算量為Nmax; 計(jì)算進(jìn)程的集合, 找出未標(biāo)記計(jì)算能力最大的進(jìn)程, 如果所有進(jìn)程都已標(biāo)記則選出計(jì)算能力最小的進(jìn)程, 記該進(jìn)程為Pexpect, 其期望負(fù)載計(jì)算量記為Wexpect。算法如下：

1. while(存在Zunsign)

2. if(Nmax

3. 標(biāo)記Zunsign和Pexpect;

4. else{

5. 分割Zunsign, 標(biāo)記計(jì)算量為Wexpect的子網(wǎng)格塊和Pexpect;

6. 其余子網(wǎng)格塊添加到原始網(wǎng)格未標(biāo)記網(wǎng)格塊的序列中}

7. end if

8. end while

輸出適合向進(jìn)程上映射的網(wǎng)格塊集合, 其表現(xiàn)在以下兩個方面:網(wǎng)格塊數(shù)大于進(jìn)程數(shù); 網(wǎng)格塊的計(jì)算量不超過進(jìn)程所期望負(fù)載的計(jì)算量。

3.1.2 網(wǎng)格塊分割策略

CFD數(shù)值模擬中, 網(wǎng)格塊網(wǎng)格單元層數(shù)太少會對模擬計(jì)算的精度產(chǎn)生很大影響, 甚至導(dǎo)致計(jì)算結(jié)果不收斂。在并行CFD計(jì)算過程中, 對接邊界面積與通信量成正比。因此，在網(wǎng)格塊分割過程中要避免出現(xiàn)過“薄”的網(wǎng)格塊, 同時使得分割后子網(wǎng)格塊的表面積較小。為此我們提出了網(wǎng)格塊的多維分割方法來滿足這種需求。

本文多維分割方法分三種情況對網(wǎng)格塊進(jìn)行不同維數(shù)的分割:

(1)如果該網(wǎng)格塊的形狀接近正方體, 則對其進(jìn)行三維分割, 分割過程如圖2所示。圖2中標(biāo)記“r”的網(wǎng)格塊為分割所需的網(wǎng)格塊, 各子網(wǎng)格塊的大小不一樣, 為了方便畫圖, 此處子網(wǎng)格塊大小取為一樣。圖3和圖4作相同解釋。

Figure 2 Three-dimensional split example圖2 三維分割示例

(2)如果該網(wǎng)格塊的形狀為“扁平”狀, 則對其進(jìn)行二維分割, 分割過程如圖3所示。

Figure 3 Two-dimensional split example圖3 二維分割示例

(3)如果該網(wǎng)格塊的形狀為“長條”狀, 則對其進(jìn)行一維分割, 分割過程如圖4所示。

Figure 4 One-dimensional split example圖4 一維分割示例

上述多維分割算法, 本文稱為非智能多維分割算法。該算法在實(shí)際分割過程中, 容易產(chǎn)生過小的網(wǎng)格塊, 如所需子網(wǎng)格塊的大小和需分割父網(wǎng)格塊的大小相差不大, 這時對父網(wǎng)格塊進(jìn)行三維分割, 將會產(chǎn)生體積很小的子網(wǎng)格塊。因此, 本文在非智能多維分割算法的基礎(chǔ)上, 提出了智能多維分割算法, 其過程如下:

輸入:待分割的最大網(wǎng)格塊, 其計(jì)算量為Nmax; 當(dāng)前進(jìn)程期望負(fù)載的計(jì)算量, 記為Wexpect。

輸出:分割所需的子網(wǎng)格塊和剩余的子網(wǎng)格塊。

1. if(Wexpect≤1/8*Nmax)

2. if(是否適合三維分割)

3. 三維分割;

4. else if(是否適合二維分割)

5. 二維分割;

6. else 一維分割;

7. end if

8. else if(Wexpect>1/8*Nmax&&Wexpect≤1/4*Nmax)

9. if(是否適合二維分割)

10. 二維分割;

室間隔缺損是兒科常見先天性心臟病，約20%，其中缺損口徑小、分流量少等癥狀較輕者一般臨床癥狀并不典型，癥狀嚴(yán)重者會出現(xiàn)呼吸窘迫和左心衰竭等癥狀，由于左心室與右心室存在壓差，左向右分流時可導(dǎo)致肺血多引發(fā)充血性心力衰竭、肺動脈高壓等癥狀，給患兒的生命安全帶來了極大的威脅[1-2]。研究表明，在室間隔缺損并發(fā)癥出現(xiàn)之前予以針對性的措施進(jìn)行干預(yù)，是可以痊愈的，其中治療方式選擇至關(guān)重要[3-4]。本研究探討介入治療、外科手術(shù)在室間隔缺損患兒的應(yīng)用價(jià)值，現(xiàn)報(bào)道如下。

11. else 一維分割;

12. end if

13. else if(Wexpect>1/4*Nmax)

14. 一維分割;

15. end if

兩種多維分割算法, 在相同的條件下分割網(wǎng)格塊的效果將在實(shí)驗(yàn)部分給出。

3.2 網(wǎng)格塊向進(jìn)程上的分配算法

網(wǎng)格塊向進(jìn)程上的分配問題是一個NP完全問題, 隨著CFD數(shù)值模擬規(guī)模的擴(kuò)大, 問題解的搜索空間急劇增加, 普通的搜索算法已不能滿足CFD任務(wù)分配的需求, 本文采用遺傳算法來解決該問題。

3.2.1 遺傳算法的基本流程

Figure 5 Flow chart of genetic algorithm圖5 遺傳算法流程圖

由于CFD任務(wù)分配問題的特殊性, 在應(yīng)用遺傳算法解決該問題的過程中, 為了減小遺傳算法的搜索空間、提高遺傳算法的搜索能力、加快遺傳算法的收斂速度, 我們對遺傳算法的以下操作做了相應(yīng)改進(jìn), 以適應(yīng)CFD任務(wù)分配問題。

3.2.2 染色體編碼和種群初始化

在遺傳算法中, 一個染色體對應(yīng)問題的一個解。常規(guī)遺傳算法的染色體編碼一般采用二進(jìn)制編碼, 對于本文的任務(wù)分配問題是不適用的, 本文染色體x的編碼形式如式(4)所示:

(4)

本文用隨機(jī)算法按照式(4)的編碼方式生成遺傳算法的初始種群。隨機(jī)生成的編碼,可能產(chǎn)生部分進(jìn)程分配的網(wǎng)格塊為空的個體,稱為無效個體。對于這種情況,首先找出網(wǎng)格塊數(shù)為0的進(jìn)程,然后從網(wǎng)格塊數(shù)最多的進(jìn)程中隨機(jī)分出一個網(wǎng)格塊給此空進(jìn)程,如果存在多個空進(jìn)程,循環(huán)執(zhí)行上述操作,直至空進(jìn)程數(shù)為0。

3.2.3 選擇操作、交叉操作、變異操作

本文中選擇操作采用經(jīng)典的輪盤賭方法和最佳個體保存方法;變異操作采用傳統(tǒng)的單點(diǎn)變異操作,采用3.2.2節(jié)中提到的方法處理變異操作過程中產(chǎn)生的無效個體。

為了避免因傳統(tǒng)交叉操作產(chǎn)生的無效個體,本文引用并改進(jìn)了由Goldberg D E和Lingle R[7]于1985年提出的PMX操作,使其能夠滿足該問題的需求。例如,對于兩個父個體,隨機(jī)產(chǎn)生兩個位串交叉點(diǎn)“|”,位串交叉點(diǎn)之間的區(qū)域?yàn)榻徊鎱^(qū)域,如表1所示。首先交換父個體的兩個交叉區(qū)域,得到表1中的中間體;為了避免出現(xiàn)空進(jìn)程,進(jìn)行如下操作,中間體的交叉區(qū)域映射關(guān)系有:

2→1, 1→2, 4→3

根據(jù)映射關(guān)系,對M1中間體交叉區(qū)域外的部分進(jìn)行映射交換。如第一對映射關(guān)系2→1。找出M1中間體交叉區(qū)域外的第一個2所在位置,使其變換為1,然后依次根據(jù)映射關(guān)系進(jìn)行類似變換,最終得到M1的子個體如表1所示。同樣對M2中間體進(jìn)行映射交換,可得最終的子個體。

Table 1 Crossover operation表1 交叉操作

3.2.4 適應(yīng)度函數(shù)設(shè)計(jì)

我們采用帶懲罰函數(shù)[8]的適應(yīng)度函數(shù)設(shè)計(jì), 如式(5)所示:

(5)

其中，M為分配方案(個體)；F(M)為個體M下的適應(yīng)度值;f(M)刻畫了個體M下進(jìn)程間的最大通信開銷;g(M)=max(|gi(M)|), 刻畫了個體M下進(jìn)程上負(fù)載平衡因子絕對值的最大值;φ為懲罰函數(shù),r1為權(quán)重系數(shù),r2為懲罰系數(shù)。

對于不考慮通信開銷的情形, 可令r1為0。

懲罰函數(shù)有很多確定方法, 為了擴(kuò)大約束條件g(M)對適應(yīng)度的影響, 我們設(shè)定:

φ(g(M))=g2(M)

(6)

對于懲罰系數(shù)r2, 取個體M下的最大通信開銷f(M)的值, 此時適應(yīng)度函數(shù)為:

(7)

其中r1為可調(diào)節(jié)的參數(shù)。當(dāng)r1較大時, 為弱約束條件;當(dāng)r1較小時, 為強(qiáng)約束條件。

3.3 進(jìn)程上計(jì)算量二次優(yōu)化算法

經(jīng)過3.2節(jié)處理后, 原始網(wǎng)格塊在空間上分為了Np個區(qū)域, 每個區(qū)域?qū)?yīng)一個進(jìn)程。如圖6所示，實(shí)心黑圈代表網(wǎng)格塊, 連線代表網(wǎng)格塊之間的相鄰關(guān)系, 網(wǎng)格塊數(shù)目為11; 虛線劃分的區(qū)域與進(jìn)程對應(yīng), 進(jìn)程數(shù)為3。由于3.2節(jié)中的最終網(wǎng)格塊分配方案是由帶懲罰函數(shù)的適應(yīng)度函數(shù)選出的最優(yōu)個體, 不一定能很好地滿足2.2節(jié)中提出的約束條件, 也就是各進(jìn)程上的計(jì)算量不一定能達(dá)到負(fù)載平衡要求。對于沒有達(dá)到負(fù)載平衡的進(jìn)程我們需要對其計(jì)算量進(jìn)行二次優(yōu)化, 使其達(dá)到計(jì)算量的負(fù)載平衡。

Figure 6 Grids partition example圖6 網(wǎng)格區(qū)域劃分示例

該算法主要分為三個步驟:(1) 當(dāng)前分配方案, 若需要二次優(yōu)化, 選出需要二次優(yōu)化的進(jìn)程P; (2) 從進(jìn)程集合中找出合適的進(jìn)程Psuit, 使其與P共同完成二次優(yōu)化; (3) 從進(jìn)程P中分離出所需的網(wǎng)格塊Zsuit分配給Psuit。下面分別描述上面三個步驟的細(xì)節(jié):

第1步:在當(dāng)前的分配方案中, 若進(jìn)程最大的負(fù)載平衡因子大于所期望的值(此處取為0.05) , 則該進(jìn)程P需要二次優(yōu)化。

第2步:

(1)列出在空間上與P相鄰的進(jìn)程鏈表Plist,Plist中負(fù)載平衡因子最小的進(jìn)程為Plmin;

(2)if(Plmin的負(fù)載平衡因子< -0.05)

Plmin→Psuit;

(3)else 找出進(jìn)程集合中負(fù)載平衡因子最小的進(jìn)程Pmin,Pmin→Psuit;

(4)end if

第3步:

(1)定義對象為網(wǎng)格塊的鏈表Zlist;

(2)if(P與Psuit相鄰)

(3) 列出P中與Psuit有相鄰關(guān)系的網(wǎng)格塊, 添加給Zlist;

(4)else列出P中的網(wǎng)格塊, 添加給Zlist;

(5)end if

(6)計(jì)算Psuit所需的計(jì)算量Nrequire;

(7)if(Zlist中是否存在網(wǎng)格塊Zsuit的計(jì)算量N, 使得Nrequire*(1-0.05)

(8)Zsuit分配給Psuit, 從P中刪除Zsuit;

(9)else 使用分割策略分割Zlist中計(jì)算量最大的網(wǎng)格塊, 分割出所需的網(wǎng)格塊Zsuit;

(10)Zsuit分配給Psuit, 分割剩余的子網(wǎng)格塊分配給P, 從P中刪除被分割的網(wǎng)格塊;

(11)end if

4 數(shù)值實(shí)驗(yàn)結(jié)果

4.1 通信模型中參數(shù)的確定

本文的數(shù)值實(shí)驗(yàn)平臺為國家超級計(jì)算長沙中心的高性能計(jì)算系統(tǒng), 每個結(jié)節(jié)由兩個6核的Intel Xeon X5670的CPU組成, 主頻為2.93 GHz, 雙精度浮點(diǎn)峰值性能是70.32 GFlops。

在上述平臺上, 經(jīng)過簡單的實(shí)驗(yàn)測試與數(shù)據(jù)擬合, 結(jié)果表明，通信開銷與通信量之間均呈分段線性函數(shù)關(guān)系, 但結(jié)節(jié)內(nèi)與結(jié)節(jié)間兩種情形有區(qū)別, 結(jié)果如表2所示。

Table 2 Test results of communication overhead model表2 通信開銷模型測試結(jié)果

4.2 CFD算例負(fù)載平衡性能測試

4.2.1 同構(gòu)平臺的測試

在4.1節(jié)通信開銷模型測試的基礎(chǔ)上, 不同的CFD算例在不同的策略下進(jìn)行負(fù)載平衡性能測試。根據(jù)網(wǎng)格塊數(shù)與進(jìn)程數(shù)目的相對多少，將算例分為兩種情形, 下文分別稱為“情形A”和“情形B”。共測試了四種負(fù)載平衡策略, 分別用a、b、c、d表示(如圖7和8所示), 其中a為文獻(xiàn)[1]提到的貪婪負(fù)載平衡算法,b、c、d為本文算法。a采用一維分割策略,b采用智能多維分割策略,c采用非智能多維分割策略,d采用一維分割策略。我們將以文獻(xiàn)中的策略a作為性能比較的基準(zhǔn)。

情形A:網(wǎng)格塊數(shù)較少情形的測試結(jié)果(原始網(wǎng)格包含4個網(wǎng)格塊, 12億網(wǎng)格單元)。

Figure 7 Test results of load balancing in less zone number圖7 網(wǎng)格塊數(shù)較少情形的負(fù)載平衡測試結(jié)果

測試結(jié)果顯示, 在此種情況下, 本文算法b、c、d與傳統(tǒng)算法a在性能比較上具有很大的優(yōu)勢。隨著進(jìn)程數(shù)的增加, 算法a的最大負(fù)載平衡因子絕對值急劇增加, 顯現(xiàn)出了各進(jìn)程上計(jì)算任務(wù)的不平衡性, 這遠(yuǎn)離了負(fù)載平衡的約束條件, 因此本文算法優(yōu)于傳統(tǒng)算法。此處a方法64進(jìn)程后的情況不予測試。對于b與c和d之間的比較, 就進(jìn)程間最大通信開銷、對接邊界面數(shù)目、對接邊界面面積三方面而言,b具有明顯優(yōu)勢。實(shí)驗(yàn)結(jié)果表明了b算法能夠使得分割負(fù)載后網(wǎng)格塊之間的對接邊界面數(shù)較少, 對接邊界面面積最少, 從而在各進(jìn)程計(jì)算任務(wù)負(fù)載平衡的基礎(chǔ)上使得進(jìn)程間的最大通信開銷最小。綜上所述, 在網(wǎng)格塊數(shù)較少的情況下,b為綜合性能最好的方法。

情形B:網(wǎng)格塊數(shù)較多情形的測試結(jié)果(原始網(wǎng)格包含265個網(wǎng)格塊, 15 000 000網(wǎng)格單元)。

Figure 8 Test results of load balancing in more zone number圖8 網(wǎng)格塊數(shù)較多情形的負(fù)載平衡測試結(jié)果

測試結(jié)果顯示, 在此種情況下, 本文算法b、c、d與傳統(tǒng)算法a在性能比較上具有很大的優(yōu)勢。在進(jìn)程數(shù)較少的時候, 都能滿足最大負(fù)載平衡因子絕對值小于所期望的值(本文為0.05), 但在進(jìn)程間通信開銷方面本文算法具有明顯優(yōu)勢。隨著進(jìn)程數(shù)的增加, 算法a的最大負(fù)載平衡因子絕對值急劇增加, 顯現(xiàn)出了各進(jìn)程上計(jì)算任務(wù)的不平衡性, 這遠(yuǎn)離了負(fù)載平衡的約束條件, 綜合分析本文算法優(yōu)于傳統(tǒng)算法。當(dāng)進(jìn)程數(shù)小于網(wǎng)格塊數(shù)或相差不大時, 進(jìn)程間最大通信開銷、對接邊界面數(shù)目、對接邊界面面積三方面而言,b較c具有明顯優(yōu)勢，b與d相當(dāng)。隨著進(jìn)程數(shù)的繼續(xù)增加, 當(dāng)進(jìn)程數(shù)遠(yuǎn)遠(yuǎn)大于網(wǎng)格塊數(shù)時, 情形變換為A, 如圖7所示, 此時在進(jìn)程間最大通信開銷、對接邊界面數(shù)目、對接邊界面面積三方面的比較中,b具有明顯優(yōu)勢。實(shí)驗(yàn)結(jié)果表明，在網(wǎng)格塊數(shù)較多的情況下,b能使空間上具有相鄰關(guān)系的網(wǎng)格塊分配到同一進(jìn)程上, 從而減少各進(jìn)程間的通信開銷。在此種情況下，算法b能使分割后網(wǎng)格中的對接邊界面數(shù)較少, 對接邊界面面積最小, 從而在各進(jìn)程上計(jì)算任務(wù)負(fù)載平衡的基礎(chǔ)上使得進(jìn)程間的最大通信開銷最小。綜上所述, 在網(wǎng)格塊數(shù)較多的情況下, 算法b是綜合性能最好的方法。

4.2.2 異構(gòu)平臺的測試

如圖1所示并行計(jì)算機(jī), 假設(shè)一個結(jié)節(jié)包含第一類處理器兩個, 第二類處理器一個, 每個處理器中創(chuàng)建兩個進(jìn)程。假設(shè)第二類處理器的計(jì)算能力是第一類的兩倍, 本文異構(gòu)平臺下只作理論測試, 所以進(jìn)程間的通信開銷簡化為4.1節(jié)測試的通信開銷模型。測試結(jié)果如圖9所示,a′、b′、c′為本文算法，a′采用智能多維分割策略,b′采用非智能多維分割策略,c′采用一維分割策略(原始網(wǎng)格包含4個網(wǎng)格塊, 12億網(wǎng)格單元)。結(jié)果顯示, 本文算法a′、b′、c′同樣適合異構(gòu)平臺, 對于a′與b′和c′之間的比較, 就最大負(fù)載平衡因子絕對值來說, 三種方法都能滿足要求；就進(jìn)程間最大通信開銷、對接邊界面數(shù)目、對接邊界面面積三方面而言,a′具有明顯優(yōu)勢。綜上所述, 本文算法同樣適合異構(gòu)平臺, 采用智能多維分割方法的本文算法a′為綜合性能最好的方法。

Figure 9 Test results of load balancing on heterogeneous platform圖9 異構(gòu)平臺上的負(fù)載平衡測試結(jié)果

4.3 CFD實(shí)例負(fù)載平衡測試

在4.1節(jié)中提到的實(shí)驗(yàn)平臺下進(jìn)行CFD實(shí)例負(fù)載平衡測試, 其中網(wǎng)格包含八個等體積的網(wǎng)格塊, 800萬網(wǎng)格單元, 采用消息傳遞并行編程模型分別在20、40、60個CPU進(jìn)程上進(jìn)行并行模擬。表3列出了4.2.1節(jié)中四種方法的實(shí)際負(fù)載平衡性能(時間為CFD并行計(jì)算迭代20步所用的時間)。

對所列四種負(fù)載平衡指標(biāo)對CFD并行測試結(jié)果進(jìn)行分析, 結(jié)果表明:隨著進(jìn)程數(shù)的增加, 方法b在并行CFD任務(wù)負(fù)載平衡方面具有最優(yōu)的穩(wěn)定效果, 并且具有很好的可擴(kuò)展性(例如，進(jìn)程上的最大計(jì)算時間隨著進(jìn)程數(shù)的增加線性減少), 而且進(jìn)程間最大通信開銷也是四種方法中最小的。

綜合上述所有測試, 智能多維分割算法能夠使負(fù)載平衡后的最大負(fù)載平衡因子滿足要求, 使得進(jìn)程間的最大通信開銷最小, 對接邊界面數(shù)目較小, 對接邊界面面積最小。

Table 3 Test result of load balancing of CFD application example表3 CFD實(shí)例負(fù)載平衡測試結(jié)果

5 結(jié)束語

本文提出的大規(guī)模CFD多區(qū)結(jié)構(gòu)網(wǎng)格任務(wù)負(fù)載平衡算法, 集網(wǎng)格塊的分割、網(wǎng)格塊的組合、進(jìn)程上計(jì)算量的優(yōu)化于一體, 解決了傳統(tǒng)負(fù)載平衡方法適應(yīng)性不強(qiáng)的問題。該算法既適應(yīng)同構(gòu)計(jì)算平臺, 也適應(yīng)新型異構(gòu)平臺; 既適應(yīng)網(wǎng)格塊較少的情形, 也適應(yīng)網(wǎng)格塊較多的情形。該算法對通信開銷方面做了很好的度量。實(shí)驗(yàn)結(jié)果表明, 在適當(dāng)?shù)姆指畈呗韵卤疚乃惴軌蛉〉煤芎玫牟⑿蠧FD任務(wù)負(fù)載平衡性能, 減少并行CFD程序的運(yùn)行時間。隨著并行規(guī)模的擴(kuò)大, 本文所用遺傳算法的搜索空間會逐漸增加, 負(fù)載平衡處理時間會漸漸加大, 后續(xù)工作將研究如何對大規(guī)模負(fù)載平衡問題中的遺傳算法進(jìn)行加速。

[1] Streng M. Load balancing for computational fluid dynamics calculationsp[M]∥High Performance Computing in Fluid Dynamics Netherlands,Netherlands:Springer, 1996.

[2] Ytterstr?m A. A tool for partitioning structured multiblock meshes for parallel computational mechanics[J]. International Journal of High Performance Computing Applications, 1997, 11(4):336-343.

[3] Saule E, Bas E ?, Catalyürek I V. Load-balancing spatially located computations using rectangular partitions[J]. Journal of Parallel and Distributed Computing,2012,70(10):1201-1214.

[4] Zhang Juan,Lu Lin-sheng.Automatic partition algorithm based on multi-region and multi-code problem[J]. Computer Engineering, 2010, 36(9):73-76.(in Chinese)

[5] Zhang Qiu-ya, Liu San-yang, Zuo Da-hai. CFD parallel computing and load balancing research using multi-block structured grids[J]. Chinese Journal of Engineering Mathematics, 2010, 27(2):219-224.(in Chinese)

[6] Li Gui-bo, Yang Guo-wei. Study on parallel computation and load balance strategy based on multiblock structured grid[J]. Journal of Astronautics, 2011, 32(6):1224-1230.(in Chinese)

[7] Goldberg D E, Lingle R.Alleles, Loci, and the travelling salesman problem[C]∥Proc of International Conference on Genetic Algorithms and Their Applications, 1985:154-159.

[8] Chen Guo-liang, Wang Xu-fa, Zhuang Zhen-quan, et al. Genetic algorithm and its application[M]. Beijing:People’s Posts and Telecommunications Publishing House, 2001.(in Chinese)

附中文參考文獻(xiàn)：

[4] 張娟, 陸林生.基于多區(qū)域多代碼問題的自動分塊算法[J].計(jì)算機(jī)工程, 2010, 36(9):73-76.

[5] 鄭秋亞, 劉三陽, 左大海. 多塊結(jié)構(gòu)化網(wǎng)格CFD并行計(jì)算和負(fù)載平衡研究[J].工程數(shù)學(xué)學(xué)報(bào), 2010, 27(2):219-224.

[6] 李桂波, 楊國偉. 基于多塊結(jié)構(gòu)網(wǎng)格的并行計(jì)算及負(fù)載平衡研究[J]. 宇航學(xué)報(bào), 2011, 32(6):1224-1230.

[8] 陳國良, 王煦法, 莊鎮(zhèn)泉, 等. 遺傳算法及其應(yīng)用[M]. 北京:人民郵電出版社, 2001.