可擴展數(shù)據(jù)驅動并行算法研究及應用.pdf

1、在高性能科學計算中，計算區(qū)域通常被離散成網(wǎng)格，微分方程在網(wǎng)格上由計算方法離散。從相鄰網(wǎng)格間數(shù)據(jù)依賴關系的角度，計算方法可以分為兩種類型:無向數(shù)據(jù)依賴和有向數(shù)據(jù)依賴。對于前者，網(wǎng)格單元的計算可以通過引用相鄰網(wǎng)格單元的已知量而獨立進行;對于后者，網(wǎng)格單元的計算依賴于某些相鄰網(wǎng)格單元的最新計算結果，也就是說，只有所有這些相鄰網(wǎng)格單元計算完畢，才能開始該網(wǎng)格單元的計算。
　　對無向數(shù)據(jù)依賴的計算方法，計算區(qū)域可以分解為多個子區(qū)域并分配到不

2、同處理器中，高效并行算法可以按粗粒度的BSP模型進行設計。但是，對有向數(shù)據(jù)依賴的計算方法，這種并行算法設計模式無法適應，需要考慮細粒度的并行計算模型和相應的并行算法。細粒度的并行計算對并行機的通信延遲提出了很高的要求，但是，隨著現(xiàn)代高性能計算機的快速發(fā)展，處理器間的通信延遲可以降低到幾個微秒，這使得細粒度的高效有向數(shù)據(jù)依賴并行算法的設計成為可能。
　　本文以求解粒子輸運方程的離散縱標(SN)計算方法及其它若干有向數(shù)據(jù)依賴關系計算方

3、法為背景，圍繞刻畫有向數(shù)據(jù)依賴關系的并行計算模型、基于模型的通用并行算法、并行算法的性能優(yōu)化、并行算法的實際應用等方面進行了系統(tǒng)深入的研究，取得如下主要研究成果:
　?。ㄒ唬┩ㄟ^分析典型科學計算應用計算方法的有向數(shù)據(jù)依賴關系，基于有向圖，歸納總結并提出了一種刻畫有向數(shù)據(jù)依賴關系的數(shù)據(jù)驅動并行計算模型，將計算方法的并行計算問題等價地轉化為模型的并行計算問題。
　?。ǘ┽槍?shù)據(jù)驅動并行計算模型，提出了統(tǒng)一形式的數(shù)據(jù)驅動并行算法

4、，以及相應的性能評價方法。該算法由三部分組成:有向圖剖分、結點優(yōu)先級策略和并行流水線算法。
　　（三）針對二維輻射輸運問題，實現(xiàn)具體的數(shù)據(jù)驅動并行算法，通過對程序LARED-R-1的并行化，在上百個處理器上，取得了可擴展的并行性能。
　?。ㄋ模┽槍?shù)據(jù)驅動并行算法，提出一種具有普適性的新的結點優(yōu)先級策略，可用于充分挖掘并行度。理論證明和實際應用表明，該策略在數(shù)百個處理器上效果明顯。
　?。ㄎ澹┽槍Σ⑿凶赃m應結構網(wǎng)格應用