多層超圖剖分算法及其在大規(guī)模CFD并行計(jì)算中的應(yīng)用研究.pdf

1、隨著高性能計(jì)算機(jī)的飛速發(fā)展和數(shù)值計(jì)算方法的日趨成熟，并行計(jì)算已成為求解大規(guī)?？茖W(xué)與工程問題的基本支撐技術(shù)。大規(guī)模并行計(jì)算的首要任務(wù)就是合理地分配計(jì)算資源，一方面希望平衡各處理器的計(jì)算負(fù)載，縮短處理器的空閑等待時(shí)間；另一方面希望減少處理器之間的通信開銷，縮短通信時(shí)間，提高并行性能。
　　超圖剖分策略以頂點(diǎn)表示計(jì)算負(fù)載，以超邊表示數(shù)據(jù)依賴關(guān)系，通過最小化處理器間的公共超邊來求解上述負(fù)載平衡問題，是一個(gè)極其有效的方法。其度量模型更加準(zhǔn)確

2、，剖分質(zhì)量更加優(yōu)秀，成為近年來備受研究者關(guān)注的熱點(diǎn)問題。然而，面對(duì)日益復(fù)雜的應(yīng)用問題，許多現(xiàn)有的超圖剖分算法已無法適應(yīng)日益變化的應(yīng)用需求。
　　本文的研究工作圍繞面向非結(jié)構(gòu)網(wǎng)格CFD計(jì)算的多層超圖剖分算法展開。針對(duì)多層算法的粗化、初始剖分、精化階段展開深入研究，提出了一系列滿足CFD計(jì)算實(shí)際需要的啟發(fā)式算法，并將設(shè)計(jì)的多層算法應(yīng)用于大規(guī)模CFD計(jì)算問題中，具有重要的理論研究意義和實(shí)際應(yīng)用價(jià)值。
　　本文的主要研究成果如下：<

3、br>　?。?）提出了基于頂點(diǎn)等級(jí)制度的加權(quán)內(nèi)積匹配粗化算法。
　　討論了現(xiàn)有粗化算法存在的問題，分析了粗化階段的重要性及對(duì)剖分性能的影響。提出以公共超邊為度量基礎(chǔ)的加權(quán)內(nèi)積匹配制度，來隱藏更多邊權(quán)；通過頂點(diǎn)權(quán)重確定訪問次序，通過頂點(diǎn)的鄰接度影響匹配優(yōu)先級(jí)，來產(chǎn)生更高的粗化率?；谏鲜鏊枷?，提出基于頂點(diǎn)等級(jí)制度的加權(quán)內(nèi)積匹配（HWIPM）粗化算法。數(shù)值實(shí)驗(yàn)表明，該算法在粗化率、邊權(quán)隱藏、運(yùn)行時(shí)間各方面均表現(xiàn)出較大的優(yōu)勢(shì)，并對(duì)最終的

4、剖分性能產(chǎn)生了積極影響。
　?。?）提出了基于鎖定收益的直接K路剖分遺傳精化算法。
　　分析了直接K路剖分較遞歸二路剖分的優(yōu)勢(shì)，并針對(duì)存在的問題，提出兩種優(yōu)化策略：一是提出基于二叉堆的頂點(diǎn)收益優(yōu)先級(jí)維護(hù)策略，將其應(yīng)用于K路邊界精化中，大大降低了算法的復(fù)雜性；二是提出鎖定收益的計(jì)算方法，將其應(yīng)用于頂點(diǎn)的移動(dòng)過程中，較大地減少了剖分截權(quán)。綜合上述策略，提出基于鎖定收益的K路（LKFM）精化算法，并結(jié)合遺傳算法的全局尋優(yōu)能力，形成

5、鄰域搜索采用LKFM算法，全局優(yōu)化采用遺傳算法的直接K路（MHGA）精化算法。數(shù)值實(shí)驗(yàn)表明，該算法在剖分截權(quán)、運(yùn)行時(shí)間各方面均表現(xiàn)出明顯的優(yōu)勢(shì)。
　?。?）提出了基于截權(quán)和最大子區(qū)外接度最小化的多目標(biāo)粒子群精化算法。
　　研究了最小化截權(quán)和最大子區(qū)外接度的重要性及兩者之間的對(duì)立統(tǒng)一關(guān)系，提出建立多目標(biāo)模型對(duì)該問題進(jìn)行優(yōu)化。針對(duì)這一問題，在最小化截權(quán)的基礎(chǔ)上，基于分層排序和線性加權(quán)相結(jié)合的方法，提出分階段多目標(biāo)MKFM精化算法

6、，并將其與粒子群算法結(jié)合，形成MHPSO精化算法。數(shù)值實(shí)驗(yàn)表明，該算法在保證剖分截權(quán)較優(yōu)、且不明顯增大運(yùn)行時(shí)間的前提下，在最小化最大子區(qū)外接度方面表現(xiàn)出明顯優(yōu)勢(shì)，該優(yōu)勢(shì)在CFD計(jì)算領(lǐng)域尤為突出。
　?。?）實(shí)現(xiàn)了多層超圖剖分研究成果在非結(jié)構(gòu)網(wǎng)格CFD并行計(jì)算中的應(yīng)用。
　　將所研究的多層超圖剖分算法應(yīng)用于非結(jié)構(gòu)網(wǎng)格CFD計(jì)算，形成以超圖剖分為分解策略，以MPI消息傳遞為通信手段的并行數(shù)值模擬。針對(duì)三個(gè)典型算例，在天河一號(hào)超級(jí)