[發(fā)明專利]一種針對(duì)粗粒度可重構(gòu)結(jié)構(gòu)的降低多類訪存沖突編譯方法

有效

• 申請(qǐng)?zhí)枺?/td>: 202011375400.2
• 申請(qǐng)日: 2020-11-30
• 公開（公告）號(hào): CN112306500B
• 公開（公告）日: 2022-06-07
• 發(fā)明（設(shè)計(jì)）人: 繩偉光;陳雨歌;蔣劍飛;景乃鋒;王琴;毛志剛
• 申請(qǐng)（專利權(quán)）人: 上海交通大學(xué)
• 主分類號(hào): G06F8/41
• 分類號(hào): G06F8/41
• 代理公司: 上海旭誠(chéng)知識(shí)產(chǎn)權(quán)代理有限公司 31220
• 代理人: 鄭立

一種針對(duì)粗粒度可重構(gòu)結(jié)構(gòu)的降低多類訪存沖突編譯方法，在編譯器后端面高度時(shí)，采用訪存壓力分?jǐn)偡椒ㄟM(jìn)行處理，調(diào)整不同子DFG的啟動(dòng)時(shí)間，調(diào)度結(jié)果將會(huì)通過數(shù)組起始地址偏置分配方法處理，對(duì)一時(shí)間內(nèi)所有的訪存操作訪問的不同數(shù)組起始地址進(jìn)行調(diào)整，還包括沖突感知映射方法的處理，根據(jù)沖突矩陣和當(dāng)前映射情況將不同操作映射至PE上，重排序和回溯算法確保了映射過程的正確性。本發(fā)明的有益效果為：有效降低多數(shù)組間的多存儲(chǔ)體沖突，大幅度降低主存利用DMA傳遞數(shù)據(jù)至片上存儲(chǔ)器的時(shí)間代價(jià)；避免訪存沖突，帶來CGRA上更高的應(yīng)用加速比；編譯器后端流程結(jié)構(gòu)簡(jiǎn)單，算法復(fù)雜度低，編譯速度快。

技術(shù)領(lǐng)域

本發(fā)明涉及粗粒度可重構(gòu)結(jié)構(gòu)編譯器領(lǐng)域，具體地，涉及降低粗粒度可重構(gòu)結(jié)構(gòu)中的多存儲(chǔ)體沖突和互聯(lián)沖突的數(shù)據(jù)分區(qū)和算子映射方法。

背景技術(shù)

隨著微電子工藝的發(fā)展，摩爾定律逐漸走向終結(jié)，微處理器的主頻難以取得進(jìn)一步的提升。粗粒度可重構(gòu)架構(gòu)(Coarse-Grained Reconfigurable architecture,CGRA)在后摩爾定律時(shí)代是相較傳統(tǒng)架構(gòu)能實(shí)現(xiàn)更高能效比的體系結(jié)構(gòu)。粗粒度可重構(gòu)架構(gòu)往往被應(yīng)用于加速計(jì)算密集型應(yīng)用程序中。在現(xiàn)代實(shí)際生活應(yīng)用程序中，應(yīng)用執(zhí)行時(shí)間主要消耗在少量循環(huán)內(nèi)核處。因此，針對(duì)將循環(huán)內(nèi)核映射到可重構(gòu)架構(gòu)上的優(yōu)化，對(duì)于提升可重構(gòu)架構(gòu)計(jì)算密集型應(yīng)用的性能具有重要意義。

典型的CGRA結(jié)構(gòu)是定義于ADRES[1]模型，如附圖1所示。具體由：片上存儲(chǔ)緩沖區(qū)(on-chip memory buffer,OMB)，全局寄存器緩沖區(qū)(global register buffer,GRB)，指令存儲(chǔ)器(context memory)和運(yùn)算單元陣列(processing element array,PEA)構(gòu)成。運(yùn)算單元陣列的每一個(gè)運(yùn)算單元(processing element,PE)結(jié)構(gòu)如附圖2所示，包含指令控制單元(context control unit)，功能單元(function unit)，輸出寄存器(output register)和本地寄存器緩沖區(qū)(local register buffer,LRB)?；谲浟魉夹g(shù)，編譯器將計(jì)算密集型應(yīng)用程序循環(huán)部分抽象為循環(huán)內(nèi)核形式，通常使用數(shù)據(jù)流圖(data flow gragh,DFG)表示。編譯器將DFG中不同運(yùn)算及訪存操作調(diào)度(schedule)并映射(mapping)到PEA中不同PE上。多個(gè)PE并行執(zhí)行數(shù)據(jù)訪存及運(yùn)算，以獲得更高的應(yīng)用加速比和算力。不同的調(diào)度及映射策略直接決定了CGRA完成計(jì)算密集型運(yùn)算的加速比和算力。高效地選取調(diào)度及映射策略以最小化循環(huán)內(nèi)核實(shí)際執(zhí)行時(shí)間，是實(shí)現(xiàn)粗粒度可重構(gòu)架構(gòu)編譯器首要目的之一。

軟件流水線策略帶來了對(duì)片上存儲(chǔ)器緩沖區(qū)并行提供數(shù)據(jù)的要求，當(dāng)同一時(shí)間內(nèi)訪存操作超過的并行提供數(shù)據(jù)的最大限制后，存在的訪存沖突會(huì)帶來流水線停滯。造成訪存沖突的原因有多種，包括多個(gè)訪存操作同時(shí)訪問多存儲(chǔ)體(Multi-bank)片上存儲(chǔ)器(Multi-Bank OMB)同一個(gè)存儲(chǔ)體(Bank)，以及多個(gè)訪存操作同時(shí)占用相同的互聯(lián)資源。通過對(duì)不同實(shí)際應(yīng)用領(lǐng)域常見的循環(huán)內(nèi)核分析統(tǒng)計(jì)，我們得到以下特征：第一，循環(huán)內(nèi)核中訪存操作占全部操作的47.9％。第二，發(fā)生在同一控制周期(Control Step,CS)的訪存操作之間的訪存沖突造成的時(shí)延占總運(yùn)行時(shí)間的68.4％。通過上述分析，可以在編譯器調(diào)度和映射策略的選取上綜合考慮訪存沖突因素以降低循環(huán)內(nèi)核運(yùn)行時(shí)間，規(guī)劃片上存儲(chǔ)器內(nèi)的數(shù)據(jù)放置以降低主存與片上存儲(chǔ)器數(shù)據(jù)傳輸時(shí)間，以提升應(yīng)用加速比和算力。

相關(guān)研究及分析

一、對(duì)減少訪存沖突的研究