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

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

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

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

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

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

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