大規(guī)模數(shù)值并行計算應用通常采用“分而治之”思想進行任務劃分。確保計算負載均衡和處理機間通信開銷最小,是獲得高效率的關鍵,因此如何合理有效地對任務剖分至關重要。圖剖分是借助圖論知識,將計算依賴關系抽象成圖,把任務劃分轉換成圖剖分問題。如何在并行平臺下高效地將圖剖分為多個子圖,確保計算和通信負載均衡,是并行圖剖分的主要研究內容。在設計圖剖分算法時,需要綜合考慮連通性、并行度、負載平衡、通信開銷等因素。 傳統(tǒng)圖剖分算法和軟件未考慮當前多核機群平臺中結點內和跨結點通信開銷之間的差異,而是將通信開銷單一化處理。隨著單結點內處理器核數(shù)不斷增加,結點內通信的比重日趨增加,結點內外這種通信開銷差異的影響日益顯著,對并行計算綜合性能影響愈來愈不容忽視。為此,本文針對多核集群平臺大規(guī)模并行計算,給出了一種新的圖剖分策略,在盡可能滿足計算負載平衡的前提下,使結點間通信開銷最小,對剖分策略進行了性能分析和數(shù)值實驗,結果顯示該策略可以進一步用來減少多核集群平臺上的通信開銷。 很多實際數(shù)值模擬問題(如動網(wǎng)格CFD計算、粒子模擬等)需要動態(tài)調整計算任務以滿足計算和通信負載均衡,圖(超圖)重剖分策略重在解決此類并行任務動態(tài)劃分問題。本文綜合分析了基于擴散的重剖分策略和重映射重剖分策略,對現(xiàn)有的重剖分模型進行了量化,以權衡重剖分過程中的通信和遷移開銷;在此基礎上對超圖的重剖分方法進行了改進,給出了一種適合超圖的重剖分策略,開展了算法分析設計,并將該重剖分策略在典型并行剖分軟件ParMetis中加以實現(xiàn),與ParMetis中的已有兩種剖分策略進行了對比分析和數(shù)值實驗。結果顯示該新重剖分策略的開銷要優(yōu)于ParMetis中的擴散方法和重映射方法,而執(zhí)行時間也比較接近。
【學位單位】：國防科學技術大學
【學位級別】：碩士
【學位年份】：2010
【中圖分類】：TP338.6
【部分圖文】：

指不在W 中而且與W 中頂點相鄰的所有adj (W ) {u V W : v W ( u , v ) E} 與頂點 6 相鄰，而且這兩個頂點的度都10}。當某個子圖中的頂點兩兩相鄰時，點 3、7 與 11 構成的子圖為完全子圖。頂點組成的有序集（u1,u2,…,um+1），其此時稱 m 為該路徑的長度。一條長 m u1,u2,),(u2,u3),…,(um,um+1)。如果存在一條以 v 連通。當 um+1=u1時，稱路徑(u1,u2,…不同，則稱之為簡單路徑，而所有的頂點回路中(u1,u2,…,um+1)中，如果所有邊都…，um互不相同，則稱之為基本回路。

國防科學技術大學研究生院工程碩士學位論文任務抽象為圖，在網(wǎng)格節(jié)點或是網(wǎng)格單元上進行模擬計算，也可以同時二者網(wǎng)格單元上模擬計算。如果計算主要是在網(wǎng)格節(jié)點上進行，可按如下方法把網(wǎng)格轉換成圖：網(wǎng)格的每個節(jié)點變成圖中的頂點，頂點之間的連線即為圖的邊，由此得到的圖稱為節(jié)點圖。如果計算主要在網(wǎng)格單元上進行，則每個網(wǎng)格單元對應圖中的一個頂點，如果有兩個單元共享同一個邊，則相應的頂點之間存在著邊，由此得到的圖稱為對偶圖。如圖 2.4(a)中，在計算中需要多次對每個三角網(wǎng)格進行計算，因此需要使用其相鄰三角網(wǎng)格的數(shù)據(jù)，所以可以把該問題用圖頂點權重來表示每個三角網(wǎng)格的計算量，而邊則用于表示相鄰兩個網(wǎng)格之間的數(shù)據(jù)通信。然后把抽象成的數(shù)據(jù)關系圖的頂點剖分成 k 個不相交的子集，也就是把網(wǎng)格節(jié)點或網(wǎng)格單元剖分成了 k 個具有相同頂點數(shù)的剖分域，并把這 k 個部分域分配到不同的處理機來執(zhí)行以提高并行執(zhí)行的效率。

國防科學技術大學研究生院工程碩士學位論文1 2 (V V))，在同一子集中，任何兩頂點間都沒有邊相連1V和2V。對分圖模型特別適合于初始任務和最終任務不同問模擬計算中的各階段任務的相互轉換、非方陣矩陣-向量相非方陣矩陣-向量相乘的對分圖[25]，矩陣的行列元素分別)的頂點集1V ,2V 表示，頂點集1V中的頂點的權重等于該頂點元素的個數(shù)，例如頂點4r 的權重為 1，其頂點的權重反映了量，任何擁有頂點ir 的處理機都會獲得 y Ax的部分解iy ，則可影響到向量 x 的求解。另外還可以通過設置列頂點為權最小化，對2V 中的頂點賦予權重可以用于另一個操作的相乘的結果作為迭代模型中的前瞻子等。

【參考文獻】

相關期刊論文 前1條

1 岳菲菲;王海軍;王新;黃東波;;高性能計算通信機制分析與研究[J];計算機工程與科學;2009年S1期

本文編號：2807391