[發明專利]一種基于子圖解耦的粗粒度可重構陣列調度方法

有效

• 申請號: 202110049464.1
• 申請日: 2021-01-14
• 公開（公告）號: CN112698954B
• 公開（公告）日: 2022-05-10
• 發明（設計）人: 景乃鋒;尹琛;王琴;蔣劍飛;賀光輝;毛志剛
• 申請（專利權）人: 上海交通大學
• 主分類號: G06F9/50
• 分類號: G06F9/50
• 代理公司: 上海旭誠知識產權代理有限公司 31220
• 代理人: 鄭立

本發明提供了一種基于子圖解耦的粗粒度可重構陣列調度方法，涉及計算機協處理器加速器領域，包括子圖解耦模塊、動態配置切換模塊、子圖調度器，其中，所述子圖解耦模塊是針對程序中的非一致性控制流，將數據流圖解耦成子圖依次執行；所述動態配置切換模塊是設計了一種多米諾骨牌式的配置切換機制，降低動態配置切換的開銷；所述子圖調度器是通過監測片上緩存中子緩存(bank)的空滿狀態，對子圖的執行順序進行動態調度。利用本發明提供的算法，可以提高陣列計算單元(PE)利用率，降低子圖切換的開銷。

技術領域

本發明屬于計算機協處理器加速器，涉及粗粒度可重構陣列的結構以及陣列計算單元利用率提升的方法。

背景技術

粗粒度可重構陣列CGRA由大量可配置的計算單元PE組成，每個PE以數據流驅動的模式執行操作。通過空間映射的方式，一旦輸入數據有效，大量PE便可以同時并行執行。這極大地提高了陣列的計算吞吐率。

然而隨著可重構陣列的應用范圍擴大，程序中存在的非完美循環，分支，循環依賴會將整個程序分割成不同的控制流區域。這些非一致性控制流區域無法同時流水執行，因此會顯著降低陣列中PE的利用率，進而降低陣列執行性能。以下將以非完美循環，分支和循環依賴為例，進行闡述。

圖2(a)中以通用矩陣乘這個應用為例，對非完美循環進行闡述。如圖2(a)左側代碼所示，內層循環體(實線框所示)每執行block_size次，外層循環體(虛線框所示)才執行一次；因此由于非完美循環中內外層循環觸發頻率不同，導致執行外層循環的PE(右圖斜線陰影所示)大部分時間處于空閑狀態，因此降低PE利用率。

圖2(b)中以稀疏向量乘這個應用為例，對分支進行闡述。如圖2(b)左側代碼所示，if分支和else分支會根據分支的判斷條件選擇性執行，不會同時執行。因此，如圖2(b)右圖所示，執行if分支的PE(斜線陰影所示)和執行else分支的PE(格子陰影所示)在任一時刻都必定有一方是處于空閑狀態。因此同樣會降低PE的利用率。

圖2(c)中以LU分解為例，對循環依賴進行闡述。如圖2(c)左側代碼所示，具有數據依賴的執行體(虛線框和實線框所示)無法同時并行執行。因此，如圖2(c)右圖所示，執行這兩塊區域的PE(斜線陰影和格子陰影)會交替處于空閑狀態，進而降低PE的利用率。

針對非完美循環，現有技術可以通過循環交換和循環展開，對內層循環體和外層循環體進行重新組織，但并沒有消除執行外層循環的PE利用率低的問題；針對分支，現有技術通過將不同分支上的指令合并映射到同一PE上以提高PE利用率，但這種方法不適用于路徑長度差異較大的非平衡分支；針對循環依賴，現有技術通過利用線程間通信挖掘細粒度的數據并行，但是會引入額外的硬件開銷。

此外，現有的數據流調度方法都只針對其中某一種非一致性控制流進行調度優化，無法同時支持上述三種情形。

因此，本領域的技術人員致力于開發一種可以同時克服以上三種情況的調度方法。

發明內容

有鑒于現有技術的上述缺陷，本發明所要解決的技術問題是如何提高陣列計算單元(PE)利用率，降低子圖切換的開銷。

為實現上述目的，本發明提供了一種基于子圖解耦的粗粒度可重構陣列調度方法，其特征在于，包括子圖解耦模塊、動態配置切換模塊、可重構陣列模塊，其中，所述子圖解耦模塊是針對程序中的非一致性控制流，將數據流圖解耦成子圖依次執行；所述動態配置切換模塊是設計了一種多米諾骨牌式的配置切換機制，降低動態配置切換的開銷；所述子圖調度器是通過監測片上緩存中子緩存(bank)的空滿狀態，對子圖的執行順序進行動態調度。

進一步地，所述調度方法包括以下步驟：

步驟S1：將數據流圖(DFG)中處于所述非一致性控制流的區域分割成若干個相互獨立的所述子圖；

步驟S2：同一時間內，每個所述子圖在陣列上獨立執行并進行充分的循環展開以提高陣列PE利用率；