數(shù)據(jù)流加速器上stencil計(jì)算的自動(dòng)優(yōu)化研究的中期報(bào)告

數(shù)據(jù)流加速器上stencil計(jì)算的自動(dòng)優(yōu)化研究的中期報(bào)告一、研究背景Stencil計(jì)算是一類常見的科學(xué)計(jì)算算法，主要用于求解偏微分方程問題和圖像處理等領(lǐng)域。由于其計(jì)算密集型和數(shù)據(jù)相關(guān)性強(qiáng)的特點(diǎn)，使得其運(yùn)行速度受到了多方關(guān)注。而數(shù)據(jù)流加速器作為新型的計(jì)算加速器，在風(fēng)能、天氣預(yù)報(bào)、地球物理學(xué)等領(lǐng)域中得到了廣泛應(yīng)用，并在科學(xué)計(jì)算領(lǐng)域中展現(xiàn)出了強(qiáng)大的計(jì)算能力。然而，在更高效的使用數(shù)據(jù)流加速器方面，一項(xiàng)關(guān)鍵的難題是如何自動(dòng)化優(yōu)化Stencil計(jì)算的執(zhí)行。在傳統(tǒng)的CPU體系結(jié)構(gòu)中，優(yōu)化的方法多樣，如代碼重排、使用高效數(shù)據(jù)結(jié)構(gòu)、并行化等。但是這些方法往往難以適應(yīng)數(shù)據(jù)流加速器的特殊結(jié)構(gòu)和計(jì)算模型。因此，如何利用數(shù)據(jù)流加速器的特點(diǎn)來優(yōu)化Stencil計(jì)算具有重要的理論和實(shí)際意義，對(duì)于數(shù)據(jù)流加速器的廣泛應(yīng)用具有十分重要的作用。二、研究現(xiàn)狀在數(shù)據(jù)流加速器上優(yōu)化Stencil計(jì)算的研究已經(jīng)開始貫穿整個(gè)計(jì)算機(jī)體系結(jié)構(gòu)的層次。在水平方向上，存在針對(duì)具體數(shù)據(jù)流加速器實(shí)現(xiàn)的特定優(yōu)化方法。例如，在IntelFPGA上，研究者非常關(guān)注內(nèi)存帶寬的利用，通過各種方法來改進(jìn)數(shù)據(jù)的傳輸效率，以提高數(shù)據(jù)流加速器上Stencil計(jì)算的性能。在縱向方向上，針對(duì)不同層次的硬件抽象（如體系結(jié)構(gòu)、指令級(jí)、并行算法等）為研究重點(diǎn)，與縱向相應(yīng)的是，其中具有代表性的研究工作如下：1.基于硬件抽象的優(yōu)化數(shù)據(jù)流加速器的特殊結(jié)構(gòu)和計(jì)算模型，使得對(duì)其計(jì)算過程進(jìn)行精細(xì)調(diào)優(yōu)具有重要意義。一些研究者針對(duì)不同的硬件抽象層次提出了針對(duì)性的優(yōu)化方法。例如，在運(yùn)算單元或內(nèi)存控制器級(jí)別上進(jìn)行的優(yōu)化可提高數(shù)據(jù)流加速器的存儲(chǔ)帶寬和運(yùn)算效率；而在指令層面或編譯器級(jí)別的優(yōu)化則通過改變數(shù)據(jù)訪問方式、順序等等，以獲得更高效的代碼。2.基于并行化的優(yōu)化Stencil計(jì)算本身具有并行性，因此并行化也是一種非常有前途的優(yōu)化手段，對(duì)數(shù)據(jù)流加速器的性能提升有著重要的作用。目前的研究主要分為兩類：一是基于傳統(tǒng)的并行算法思路，如利用OpenMP對(duì)數(shù)據(jù)流加速器進(jìn)行任務(wù)的劃分與調(diào)度等；二是基于流水線的高級(jí)硬件并行結(jié)構(gòu)，如一種基于GPU的數(shù)據(jù)流加速器的流水線結(jié)構(gòu)。三、研究目標(biāo)1.基于數(shù)據(jù)流加速器的整體特點(diǎn)，探索一種更加高效的自動(dòng)化優(yōu)化方法，以提高Stencil計(jì)算的執(zhí)行效率。2.建立一種數(shù)據(jù)流加速器上Stencil計(jì)算自動(dòng)優(yōu)化的框架，這個(gè)框架以數(shù)據(jù)依賴性為中心，包括算法設(shè)計(jì)、并行優(yōu)化和綜合分析等多個(gè)環(huán)節(jié)。3.系統(tǒng)地評(píng)價(jià)該自動(dòng)化優(yōu)化框架的可行性、實(shí)用性、正確性和有效性，為數(shù)據(jù)流加速器在Stencil計(jì)算處理的高效應(yīng)用提供技術(shù)支持。四、研究?jī)?nèi)容1.針對(duì)數(shù)據(jù)流加速器的計(jì)算模型，形式化研究Stencil計(jì)算過程中的數(shù)據(jù)依賴關(guān)系。2.針對(duì)形式化定義中的數(shù)據(jù)依賴關(guān)系，設(shè)計(jì)一種能夠發(fā)現(xiàn)數(shù)據(jù)依賴關(guān)系，并能夠自動(dòng)調(diào)整計(jì)算分配方案以更好地利用硬件資源的算法。3.通過模擬實(shí)驗(yàn)和基于目標(biāo)函數(shù)的分析，對(duì)自動(dòng)優(yōu)化方法進(jìn)行評(píng)估。在實(shí)驗(yàn)過程中，分別對(duì)比CPU、GPU和數(shù)據(jù)流加速器上Stencil計(jì)算的執(zhí)行效率和性能，驗(yàn)證算法的實(shí)際優(yōu)越性。五、總結(jié)本次中期報(bào)告總體介紹了數(shù)據(jù)流加速器上Stencil計(jì)算的自動(dòng)優(yōu)化研究。通過對(duì)該領(lǐng)域的現(xiàn)狀和研究目標(biāo)的分析，提出了一種基于數(shù)據(jù)依賴性的優(yōu)化方法，設(shè)計(jì)了自動(dòng)優(yōu)化框架，完成了算法設(shè)計(jì)，