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

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

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

3、法為背景，圍繞刻畫有向數(shù)據(jù)依賴關(guān)系的并行計算模型、基于模型的通用并行算法、并行算法的性能優(yōu)化、并行算法的實際應(yīng)用等方面進行了系統(tǒng)深入的研究，取得如下主要研究成果:
　　（一）通過分析典型科學(xué)計算應(yīng)用計算方法的有向數(shù)據(jù)依賴關(guān)系，基于有向圖，歸納總結(jié)并提出了一種刻畫有向數(shù)據(jù)依賴關(guān)系的數(shù)據(jù)驅(qū)動并行計算模型，將計算方法的并行計算問題等價地轉(zhuǎn)化為模型的并行計算問題。
　　（二）針對數(shù)據(jù)驅(qū)動并行計算模型，提出了統(tǒng)一形式的數(shù)據(jù)驅(qū)動并行算法

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