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

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

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

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