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

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

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

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

【參考文獻(xiàn)】

相關(guān)期刊論文 前1條

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

本文編號(hào)：2807391