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

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

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

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

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