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

有效

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

1.一種訪存壓力分?jǐn)偡椒ǎ鳛镃GRA編譯器后端調(diào)度過程中的一個步驟，其特征在于，通過增加控制周期的數(shù)量，并調(diào)整DFG內(nèi)不同子圖之間的啟動時間，將循環(huán)內(nèi)核中每一個控制周期訪存操作數(shù)量降低，減少每一個控制周期內(nèi)發(fā)生訪存沖突的可能性，提升可重構(gòu)處理器應(yīng)用加速比；

編譯器后端對DFG中位于不同控制周期中的節(jié)點數(shù)量和訪存節(jié)點數(shù)量計數(shù)，通過貪婪算法調(diào)整不同子圖的啟動時間，在放置每一個子圖時，將節(jié)點數(shù)量和訪存節(jié)點數(shù)量平均地分配到不同的控制周期中；

在當(dāng)前策略得到的結(jié)果不滿足每個控制周期內(nèi)的節(jié)點數(shù)量限制的情況下，算法在分配啟動時間時同時考慮分?jǐn)偣?jié)點數(shù)量和訪存節(jié)點操作數(shù)量，在保證單控制周期內(nèi)節(jié)點數(shù)量約束下，分?jǐn)傇L存壓力。

2.一種數(shù)據(jù)放置方法，作為CGRA編譯器后端處理的一個步驟，其特征在于，固定存儲體數(shù)量，不進(jìn)行線性變換，僅通過調(diào)整數(shù)組起始地址來降低多存儲體沖突；

同一控制周期內(nèi)兩個對不同數(shù)組的訪存操作和不發(fā)生多存儲體沖突的條件為：

其中，循環(huán)內(nèi)核訪存的數(shù)組數(shù)量為K，數(shù)組名記為A₁,A₂,…,A_K，當(dāng)控制周期為r時，對第k個數(shù)組A_k中位置為A_k[a₀i₀+a₁i₁+…a_n-1i_n-1+a_n]元素的訪存被記作的向量形式，i₀,i₁,…,i_n-1為循環(huán)索引，a₀,a₁,…,a_n-1為線性變換系數(shù)；

對數(shù)組A_k的訪存操作所訪問的片上存儲器Bank編號如下所示，

數(shù)組A_k的所有元素將會被放置到片上存儲器首地址為O_k的位置，BankNum為片上存儲器存儲體數(shù)量；

已分配的數(shù)組占據(jù)了前Q的位置，則數(shù)組A_k在片上存儲器的起始地址O_k為：

3.如權(quán)利要求2的數(shù)據(jù)放置方法，其特征在于，其目標(biāo)為選取各數(shù)組在片上存儲器存儲的首地址O_k，降低在循環(huán)內(nèi)核執(zhí)行全過程中下式滿足的次數(shù)，其中，定義兩次訪問之間的曼哈頓距離為訪問索引之間的距離,即

在遍歷所有數(shù)組偏置組合情況下，算法復(fù)雜度達(dá)到Θ(BankNum^K)。

4.如權(quán)利要求3的數(shù)據(jù)放置方法，其特征在于，選取各數(shù)組在片上存儲器存儲的首地址O_k時基于貪婪算法，算法復(fù)雜度降低至Θ(BankNum×K)。