CFD并行計(jì)算大揭秘！算法玩的不好，照樣香菇、藍(lán)瘦！

2017-02-24 by:CAE仿真在線來源:互聯(lián)網(wǎng)

相關(guān)背景

單核計(jì)算原來越不能滿足大規(guī)模CFD計(jì)算的需求。大量的學(xué)術(shù)機(jī)構(gòu)和工程院所通過并行的方法來進(jìn)行上億網(wǎng)格的計(jì)算模擬。理所當(dāng)然的,并行計(jì)算(Parallel computing)需要配備多核CPU的計(jì)算機(jī),也即并行計(jì)算機(jī)(Parallel computers)。

并行計(jì)算機(jī)和普通計(jì)算機(jī)相同,也是使用常規(guī)芯片,因此并行計(jì)算機(jī)比矢量計(jì)算機(jī)(Vector computers)要便宜的多。商用并行計(jì)算機(jī)通常具有上千個(gè)處理器,上T的內(nèi)存。因此計(jì)算能力是驚人的。

CFD工程師經(jīng)常會(huì)問,并行計(jì)算是僅僅調(diào)用多個(gè)CPU就可以實(shí)現(xiàn)加速計(jì)算了么?

Too simple, sometimes naive!

CFD并行計(jì)算大揭秘！算法玩的不好，照樣香菇、藍(lán)瘦！cfd流體分析圖片1

并行計(jì)算遠(yuǎn)非那樣簡(jiǎn)單

多CPU串行計(jì)算

基于單核計(jì)算設(shè)計(jì)的算法,可能在并行計(jì)算機(jī)上不能夠有效的運(yùn)行。我們用循環(huán)語句為例,如果使用自動(dòng)并行編譯器對(duì)代碼進(jìn)行編譯,并行只是在循環(huán)語句里面執(zhí)行。依據(jù)Amdahl法則,計(jì)算效率由最低效的部分決定。因此整個(gè)代碼中,不能并行計(jì)算的代碼要盡可能的小。

目前CFD中采用的并行算大體思路為把計(jì)算域分為子計(jì)算域,并且分別使用不同的CPU核心來對(duì)子計(jì)算域進(jìn)行計(jì)算。在這種并行分塊策略下,不同的CPU核心運(yùn)算相同的代碼,只不過他們處理的數(shù)據(jù)不同(分別處理自己的數(shù)據(jù)),在并行計(jì)算后再對(duì)數(shù)據(jù)進(jìn)行重組。

由于每個(gè)CPU核心需要處理自己的數(shù)據(jù),且某些數(shù)據(jù)需要和其他CPU核心中的數(shù)據(jù)中獲取,因此,CPU核心之間存在著數(shù)據(jù)交換。每個(gè)CPU處理的計(jì)算域的邊界也稱之為CPU邊界(Processor Boundary)。

顯性格式相對(duì)來說還是比較容易并行的,因?yàn)椴僮鞯臄?shù)據(jù)都是上一個(gè)時(shí)間步的已知數(shù)據(jù)。其離散后的矩陣為對(duì)角陣。數(shù)據(jù)交換只存在于在每個(gè)時(shí)間步計(jì)算完成后子計(jì)算域彼此的交界處。顯性格式并行計(jì)算最困難的部分就是橢圓形的壓力泊松方程。

隱性格式相對(duì)來講并行起來比較麻煩,矩陣的系數(shù)計(jì)算只是稍微麻煩一點(diǎn)(隱形格式離散后非對(duì)角陣),更頭疼的是求解這個(gè)非對(duì)角陣的迭代矩陣求解器不是很容易并行起來。比如:高斯消去法在計(jì)算的時(shí)候需要調(diào)用之前的迭代值,這導(dǎo)致其很難并行計(jì)算。

舉例,我們來看使用常規(guī)的矩陣求解方法(如采用ILU類型的矩陣求解器)在并行中的計(jì)算特點(diǎn):

CFD并行計(jì)算大揭秘！算法玩的不好，照樣香菇、藍(lán)瘦！cfd流體分析圖片2

在上圖中,黑格子為我們的2D網(wǎng)格單元,整個(gè)網(wǎng)格域被分為4個(gè)垂直的子區(qū)域并分別由4個(gè)不同的CPU求解。在每個(gè)網(wǎng)格單元上,存儲(chǔ)在著我們的矩陣系數(shù)。在常規(guī)的方式中,矩陣系數(shù)的計(jì)算需要相鄰網(wǎng)格單元的值。

假若某種矩陣求解器的矩陣系數(shù)構(gòu)造需要其西側(cè)和南側(cè)矩陣系數(shù)的值。那么CPU1上節(jié)點(diǎn)1、2上的矩陣系數(shù)可以順序求出,在這個(gè)時(shí)候,CPU2、3、4閑置,因?yàn)樗麄冃枰鱾?cè)和南側(cè)的矩陣系數(shù)值才能進(jìn)行計(jì)算。

在CPU1上節(jié)點(diǎn)1、2上的矩陣系數(shù)求出之后,CPU2開始求解節(jié)點(diǎn)3、4的矩陣系數(shù)。在這個(gè)時(shí)候,CPU1可以計(jì)算節(jié)點(diǎn)10、11的矩陣系數(shù)。

在CPU2求解之后,CPU3開始求解節(jié)點(diǎn)5、6的值。于此同時(shí),CPU1已經(jīng)完成節(jié)點(diǎn)10、11的矩陣系數(shù)計(jì)算,并可以開始進(jìn)行節(jié)點(diǎn)19、20的計(jì)算。

在CPU3計(jì)算節(jié)點(diǎn)5、6的值之后,CPU4開始計(jì)算節(jié)點(diǎn)7、8、9的值,同時(shí)CPU1、2、3也在分別進(jìn)行著計(jì)算...

可以看出,CPU1總是比CPU2快一步,CPU2總是比CPU3快一步,以此類推。圖中天藍(lán)色陰影部分即表示的為這種CPU負(fù)載的不均衡。

在上圖中,CPU1只是領(lǐng)先了CPU4四行,如果分配了400個(gè)核,那么這意味著CPU1領(lǐng)先了CPU400共400行數(shù)據(jù)!這導(dǎo)致大量的閑置時(shí)間(idle time)。

CFD并行計(jì)算大揭秘！算法玩的不好，照樣香菇、藍(lán)瘦！cfd流體分析圖片3
上圖中,CPU1已經(jīng)跑完了,還需要繼續(xù)等待CPU2、3、4、...15,并且CPU15才跑到一半!

CFD并行計(jì)算大揭秘！算法玩的不好，照樣香菇、藍(lán)瘦！cfd學(xué)習(xí)資料圖片4

要真正的并行計(jì)算,算法改進(jìn)迫不及待。

并行計(jì)算

目前,CFD計(jì)算中的并行算法均采用分解(decompose)的方式,附加矩陣求解器的重構(gòu)。分解的方式主要有兩種:空間分解和時(shí)間分解。

如前文所述,在空間分解中,計(jì)算域被分解為幾個(gè)小的計(jì)算域。空間分解的首要任務(wù)就是效率最大化:使得每個(gè)處理器獲得相同的工作量。

舉例:我們把計(jì)算域空間分解為9個(gè)子計(jì)算域,并編號(hào)為1-9。通常的并行做法為:同時(shí)把矩陣系數(shù)分解為9*9階塊矩陣。其中矩陣的對(duì)角塊對(duì)應(yīng)子計(jì)算域的矩陣系數(shù)。非對(duì)角塊中包含子計(jì)算域邊界處的交互關(guān)系。