有向圖并行計(jì)算中的多目標(biāo)剖分算法.pdf

1、在以離散網(wǎng)格為基礎(chǔ)的科學(xué)計(jì)算數(shù)值模擬中，在某些情形下，網(wǎng)格間的計(jì)算順序是單方向數(shù)據(jù)依賴的，這種依賴關(guān)系可以抽象為有向圖。于是，這類科學(xué)數(shù)值模擬的并行計(jì)算可以抽象成為有向圖的并行計(jì)算問題。如何剖分這些有向圖成多個(gè)子圖，將各子圖對(duì)應(yīng)的數(shù)值模擬任務(wù)映射到不同的處理機(jī)，是該類數(shù)值模擬有向圖并行計(jì)算的基礎(chǔ)。有向圖并行計(jì)算可分解為三個(gè)部分，有向圖剖分算法、結(jié)點(diǎn)的優(yōu)先級(jí)算法和基于有向圖剖分算法和結(jié)點(diǎn)優(yōu)先級(jí)算法的掃描并行算法。有向圖剖分算法中，我們需要

2、綜合考慮連通性、并行度、負(fù)載平衡、通信開銷四個(gè)目標(biāo)。本文在傳統(tǒng)有向圖剖分算法的基礎(chǔ)上，提出了一個(gè)權(quán)衡這四個(gè)目標(biāo)的有向圖多目標(biāo)剖分區(qū)域分解算法。應(yīng)用于二維非結(jié)構(gòu)網(wǎng)格上的柱對(duì)稱中子輸運(yùn)并行計(jì)算中，基于該剖分算法的通量掃描并行算法的并行效率比基于非結(jié)構(gòu)網(wǎng)格無向圖剖分區(qū)域分解的相應(yīng)并行算法的并行效率有明顯的提高。具體分為六章。 第一章簡單分析離散網(wǎng)格為基礎(chǔ)的科學(xué)數(shù)值模擬中有向圖剖分的應(yīng)用，指出了開展多目標(biāo)剖分區(qū)域分解算法研究的必要性，總

3、結(jié)了有向圖剖分算法的發(fā)展?fàn)顩r和以往有向圖剖分算法的不足。最后，簡述了本文的主要工作。 第二章介紹有向圖并行計(jì)算的基本概念、有向圖并行計(jì)算的評(píng)判準(zhǔn)則和基于區(qū)域分解的掃描并行算法。 第三章介紹有向圖的結(jié)點(diǎn)優(yōu)先級(jí)算法。 第四章介紹多目標(biāo)剖分區(qū)域分解算法，即如何根據(jù)圖中結(jié)點(diǎn)的單方向數(shù)據(jù)依賴關(guān)系，將圖剖分成P個(gè)子圖，分配給P臺(tái)不同的處理機(jī)，使得基于圖剖分的掃描并行算法獲得最高的并行效率。我們將相鄰結(jié)點(diǎn)引入多目標(biāo)剖分區(qū)域分解

4、算法之后，相應(yīng)地引入三個(gè)新概念，從而改進(jìn)多目標(biāo)剖分區(qū)域分解算法。 第五章利用掃描并行算法對(duì)IterativeKernigham-Lin(IKL)方法和改進(jìn)前后多目標(biāo)剖分區(qū)域分解算法給出的剖分進(jìn)行比較.并對(duì)結(jié)果進(jìn)行具體分析。實(shí)驗(yàn)結(jié)果表明我們的多目標(biāo)剖分區(qū)域分解算法達(dá)到了預(yù)期的目標(biāo)，并且某些性質(zhì)方面比IKL方法有更好的效果，而改進(jìn)后的算法比改進(jìn)前的多目標(biāo)剖分區(qū)域分解算法有更好的效果。 第六章為結(jié)束語，總結(jié)了全文工作，展望了將