存算解耦合的粗粒度可重構陣列訪存結構設計

洪 途，景乃鋒

（上海交通大學電子信息與電氣工程學院，上海 200240）

0 概述

粗粒度可重構陣列（Coarse-Grained Reconfigurable Array，CGRA）［1-3］包含可配置的處理單元（Processing Unit，PE）并具有互聯結構，在不同應用下能夠形成高效的數據流驅動計算。該體系結構配置數據流驅動代替傳統的集中式程序計數器（Program Counter，PC）和寄存器堆，兼具通用計算的靈活性和專用計算的高效性。在計算能力方面，當程序映射到CGRA上時，可以對PE進行軟件流水化以及并行展開實現高計算吞吐量；在功耗方面，數據流計算通過數據可用性以及配置對PE進行驅動，能夠有效減少指令和調度的能耗開銷［4］。

盡管CGRA提供了一個實現高能效計算的新方向，但在實際應用中仍然存在訪存性能不足以支持大量PE計算的問題。雖然CGRA可以通過互聯網絡形成高效的數據流直傳而無需通過大量的內存讀寫來實現數據傳遞，但由于多核計算的高計算吞吐量，訪存性能較差仍然是CGRA存在的一個嚴重問題［5-6］。本文設計一種基于存算解耦合（Decoupled Access Execute，DAE）的片上存儲讀寫單元，以優化內存訪問的性能并提高硬件利用率。

1 存算解耦合與研究現狀

傳統的內存層次結構在地址訪問中難以避免緩存缺失問題帶來的內存延時，且這一問題在訪存不具有局部性時更嚴重。因此，在緩存缺失時如何掩蓋內存延時成為體系架構研究中的一個關鍵問題。

在基于程序計數器和寄存器堆的中央處理器（Central Processing Unit，CPU）和圖形處理器（Graphics Processing Unit，GPU）體系結構中，可以通過上下文切換來掩蓋內存延時。而CGRA因其分布式軟件流水的架構特征，缺乏足夠的寄存器以及中心協同控制來實現大范圍的線程切換。因此，針對現有的CGRA架構，需要尋找其他內存延時掩蓋的方法。

存算解耦合［7］將核心計算與訪存請求分離，通過這兩部分在迭代執行進度上的解耦合實現延時的覆蓋，其執行原理如圖1所示。在傳統的耦合模式中，由于編譯后的匯編代碼必須在加法運算執行完并寫回后才能開始下一次迭代的內存訪問，使得整個應用需要承擔所有的訪存延時。而在解耦合模式中，訪存的觸發不再依賴于執行的結束，而是將訪存和計算的運行時間重疊來實現內存延時掩蓋。

圖1 存算解耦合示意圖Fig.1 Schematic diagram of decoupled access execute

基于DAE的訪存延時掩蓋技術關鍵在于：1）去除訪問與執行之間非數據相關的依賴性，使訪存能夠提前執行；2）需要一個存儲空間用于存放提前預取得到的訪問數據；3）訪存與執行之間需要同步機制，在訪存數據就緒時激發執行部分的運行。

目前關于DAE的研究較多。在CPU領域，文獻［8］通過ARM big.LITTLE（大小核）實現了DAE，其利用小核進行地址計算與內存訪問，利用大核執行核心計算。但由于大小核之間只能利用緩存一致性進行交互，因此導致性能受損。ASIC中的doublebuffer設計也通過訪存和執行的迭代解耦對內存延時進行掩蓋。在CGRA架構中，文獻［9-10］都使用了DAE的方式進行訪存和計算的解耦合。Plasticine［9］將陣列分化為地址計算單元、片上存儲單元和核心計算單元，分別用于數據預取、片上內存管理以及核心計算。FPCA［10］通過專用的地址生成模塊對內存進行訪問，內部包含簡單的循環迭代控制和地址計算電路。

上述研究都使用了分化的地址單元和計算單元，通過先入先出（First Input First Output，FIFO）機制連接地址計算和核心計算來傳遞數據［11］，但顯然這些設計的硬件利用率對應用的計算訪存比很敏感（如Plasticine在所有應用中的平均利用率僅為39.27%），并且完全分離的執行和訪存對程序員和編譯器也提出了更高的要求，需要對兩個部分分別進行編程和編譯。此外，對于間接訪問，由于訪存得到的數據仍要作為地址進行計算，因此無法進行延遲優化。

2 基于存算解耦合的訪存結構

由于現有CGRA架構中仍然存在硬件利用率低、編程抽象以及性能受限的問題，因此本文提出基于DAE的訪存結構Load/Store Elemen（tLSE）。圖2中以兩個LSE結合成LSE對的形式給出了架構框圖，實線與虛線分別表示數據通路和控制通路。

圖2 LSE對架構Fig.2 Architecture of LSE pair

LSE由控制塊和輕量級的存儲空間組成，存儲空間可以在不同的需求中根據配置對不同類型的訪存進行解耦合優化。控制塊主要包含有限狀態機、線程計數器以及請求緩沖區。LSE對中主控制塊可以完成主從控制塊之間的數據與控制協同，分別如圖2中粗實線與粗虛線所示，在控制塊所控制的存儲空間可以接收主控制塊的數據輸入和控制輸入。LSE對布局在PE陣列的四周，通過互聯網絡為需要進行訪存的PE提供訪存接口。LSE的布局圖如圖3所示。

圖3 LSE布局圖Fig.3 Layout of LSE

2.1 仿射訪問

通過循環迭代變量經過仿射變換得到地址進行的訪問即仿射訪問，其地址與迭代變量函數的最高次為1。這種訪問類型（包括連續訪問）空間局部性較好且具有無循環依賴的特征。通過單獨的LSE即可對其進行如圖4所示的映射優化，對PE陣列進行仿射變換計算得到地址并通過互連網絡輸入到LSE中，將LSE配置為FIFO模式，通過圖2中的線程計數器為請求打上標記并發送到內存層次結構。線程計數器的計數大小與存儲容量相等，每個計數標簽對應存儲中的一個條目，當數據返回時根據標簽填充進對應的存儲條目中。在FIFO模式下，LSE的輸出由輸出指針進行指定，輸出指針總是指向先進入LSE的請求對應的存儲條目。這種措施可在內存層次結構發生亂序時保證程序的正確性。

圖4 仿射訪問優化示意圖Fig.4 Schematic diagram of affine access optimization

在圖4中，LSE起到了將執行部分（核心計算）和地址計算部分（仿射變換）在循環迭代進度上隔離的效果。執行部分在執行第1次和第2次迭代時，LSE中容納了第3次～第18次迭代的請求，這些請求正在內存層次結構中進行內存訪問并承受內存延時。地址計算部分非阻塞地執行第19次和第20次迭代。當存儲空間足以覆蓋內存延時時，執行部分將感受不到內存延時，因為訪存請求是提前于核心計算被發出的。

LSE對的設計加強了CGRA對不同訪存延時的適應能力，在內存訪問較多、存儲帶寬緊張的情況下，LSE對可以通過主控制塊對從控制塊控制的存儲空間加以利用，從而實現串聯的效果。兩倍的存儲空間可以用來容納更多次的迭代，通過進一步隔開執行和訪存之間的迭代進度來適應更高的訪問延時。LSE對在訪存延時低時獨立工作，在訪存延時高時串聯協同工作。

相比于其他DAE對仿射訪問的優化，LSE通過數據可用性對執行部分進行驅動，即當LSE中頭指針所指向的數據可用時才會使LSE輸出數據并激活執行部分進行計算。這種細粒度的驅動方式一方面簡化了訪存和執行之間的同步，另一方面也大幅減少了所需的存儲空間面積，可計算的數據將被立刻輸出并釋放存儲空間用于下一個訪存請求等待內存延時。

在軟件抽象方面，LSE簡化了程序員和編譯器的工作，只需要在高級語言編譯后的數據流圖（Data Flow Diagram，DFG）基礎上將訪存替換成LSE即可完成DFG到CGRA配置的映射。這一點在分化的DAE策略中難以實現，因為訪存和執行的完全分離，需要分別對其進行編程并完成同步。

2.2 寫請求

作為PE陣列與內存層次結構的接口，LSE除了讀請求以外還需要具備完成寫請求的能力，從而在不同讀寫比例的應用中都保持較高利用率。

如圖5所示，LSE對通過對齊的協作方式完成寫請求，兩個LSE分別暫存寫請求的數據和地址。其中，從控LSE保存寫地址，主控LSE保存寫數據，主從控制塊分別為輸入的數據打上迭代標簽。

圖5 LSE寫請求示意圖Fig.5 Schematic diagram of LSE write request

數據流圖中的地址和數據來自兩條并行的數據通路，因此，數據和地址很可能不會同時到達。在圖5中，主控制塊通過虛線箭頭所示的控制通路對LSE對中的兩塊存儲空間進行協同控制，此時LSE不再工作于FIFO模式下，而是根據條件進行選擇輸出。當同一迭代標簽的數據和地址都湊齊時觸發寫請求的產生，LSE對將地址和請求共同發送到內存層次結構形成一個完整的寫請求。LSE的存儲空間也為地址和數據通路提供了解耦合的關系，當一條通路延遲較長時，通過存儲空間為短路徑保留更多的請求，從而防止短路徑的堵塞。

現有CGRA的訪存結構往往不兼具寫請求的能力，因為寫請求的地址和數據分別產生自地址單元和計算單元，而分化的地址單元和數據單元之間缺少協同。因此，CGRA通常需要專用的寫結構用于寫操作，這加劇了CGRA架構的硬件利用率問題。

2.3 間接訪問

間接訪問是現有CGRA存儲結構中存在的問題，因為現有CGRA結構中訪存得到的數據會作為地址繼續進行內存訪問，需要將地址計算再次分化為第1次訪問和第2次訪問來分別進行預取，這對數據通路和編程的靈活性提出了很高的要求，而分化的地址計算和核心計算不具備這一靈活性。另一方面，應用中存在很多間接訪問（如在SPEC 2017應用集合中間接訪問占據了所有應用總訪存的15%［12］），這些間接訪問仍然屬于流式訪問的范疇，即不具有循環間依賴特性，因此，其仍然具備優化的潛力。

間接訪問的地址具有靜態不可預測和地址隨機分布的特性。前者導致難以執行很有效的預取，后者導致失去很好的空間局部性，兩者對性能影響都很大。圖6展示了利用LSE對優化中間接訪問的過程。

圖6 間接訪問優化示意圖Fig.6 Schematic diagram of indirect access optimization

如圖6所示，本文通過LSE對之間的對齊和更大范圍內的協同行為對間接訪問進行優化。b［i］以及d［i］的訪問屬于仿射訪問，LSE控制存儲空間以FIFO方式隱藏第1次訪問的內存延時。對數組a和數組c的訪問屬于間接訪問，需要使用b［i］和d［i］作為地址進行訪問。在正常映射的基礎上，LSE對通過對齊的方式對a和c數組進行亂序訪問。亂序訪問時不再對訪存數據執行先入先出順序，而是像寫請求一樣，當LSE對中某一次迭代的兩個數據都湊齊時，觸發這一次迭代兩個數據的共同輸出。

為保證程序的正確性，需要使加法運算的其他操作數i和e［i］保持與亂序的LSE對同樣的順序。這一過程通過全局的標簽FIFO實現，LSE對完成一次對齊后將數據輸出到PE陣列并將對應的標簽寫入標簽FIFO中對執行順序進行記錄。操作數i和e［i］對應的LSE此時需要根據各自在標簽FIFO中的指針從標簽FIFO中讀取迭代標簽并根據標簽輸出自身對應條目的數據。此時i變量雖然不需要進行內存訪問，但仍需要經過LSE實現順序跟隨的行為。在此過程中，a［b［i］］和c［d［i］］稱為對齊的操作數，a［b［i］］、c［d［i］］、e［i］和i稱為相交的操作數（它們需要執行互為操作數的計算）。

在行為上，對第1次訪問進行仿射訪問的優化方式掩蓋第1次訪問的訪存延時，從而保證b［i］和d［i］的吞吐量不受延遲影響。對于第2次的間接訪問，除同樣使用存儲空間進行解耦合外，還需要通過亂序執行做進一步優化。其他相交的操作數則進行順序跟隨來保證程序的正確性。兩次迭代隔離實現兩級預取，間接訪問的延時將不會影響陣列的計算吞吐量。

對間接訪問進行亂序優化的原因是間接訪問的空間局部性較弱，很可能其先發的請求緩存缺失而后發的請求緩存命中。在使用亂序執行時，先對齊的迭代可以先進行后續的執行而不必維持原有順序，這不僅減少了后續PE的流水線停頓，同時也能盡早釋放存儲空間。

相比于FIFO模式，亂序執行引入了如圖7所示的線程級并行方式，其中虛線框內的第4次迭代先集齊了操作數，可以先輸出進行計算而不用等待之前迭代的執行。這一優化只使用在間接訪問中，因為仿射訪問的地址變換往往是單調的，內存缺失不具有隨機性。這種亂序和跟隨的行為實現了一種簡化的記分板，由于間接訪問具有更高的平均延時，因此以間接訪問的匹配順序作為循環迭代的執行順序，而其他操作數進行順序跟隨。此模式可優化作為瓶頸的間接訪問的性能，從而提高應用的整體性能。

圖7 亂序執行的線程級并行示意圖Fig.7 Schematic diagram of thread level parallelism of out-of-order execution

LSE將訪存操作與輕量級存儲空間進行耦合，針對所有訪存請求的延遲進行迭代隔離，同時還通過串聯、對齊、跟隨的協同操作具備更強的控制靈活性，可以實現對各種訪存類型（包括寫請求）的優化。相比于現有的CGRA的訪存結構，LSE對訪存本身進行定制而不是對地址計算和核心計算進行分化，從而避免了對地址計算和核心計算的分步編程和同步。同時統一的存儲接口有利于提高計算單元利用率，避免對應用的地址計算和核心計算比例的敏感性。

3 實驗與結果分析

3.1 實驗平臺

本文在文獻［13］的目標CGRA架構下通過替換LSE結構對訪存結構進行優化。實驗平臺是基于C++編寫的系統級模擬器。該模擬器包含周期精確的PE陣列以及周期近似的內存層次單元，同時包含32 KB的緩存以及地址合并單元［14（］coalescor）。本文在動態隨機存儲器（Dynamic Random Access Memory，DRAM）仿真模型中使用周期精確的DRAMsim2［15］，以保證內存延時和帶寬的準確性，同時在DRAM設備上將DDR3_micron_16M_8B_x8_sg15作為存儲性能模擬的參數來源。以3×3卷積應用為例的實驗流程如圖8所示。

圖8 卷積映射流程Fig.8 Procedure of convolution mapping

一段C代碼程序通過編譯形成DFG［16］，在DFG中將訪存操作替換為用LSE實現。生成帶有LSE的DFG后，再根據圖8所示的連接關系、算子以及訪存類型將DFG轉化為模擬器和硬件可識別的配置包，模擬器通過配置包對其包含的PE、互連結構和LSE進行配置，從而實現應用需求的計算功能。

3.2 測試應用選擇

實驗中從應用集MachSuite［17］選擇以下5個典型應用進行測試：Stencil是標準的無依賴流式處理應用，可以測試DAE對連續訪問的優化；稀疏矩陣乘（SPMV）、分子動力學（MD）和廣度優先搜索（BFS）包含間接訪問，且含有不同數量的相交間接訪問；序列匹配（NW）具有一定的循環間依賴性并含有較多的條件分支判斷。上述應用的計算、訪存、分支指令占比如圖9所示。可以看出，由于Stencil和MD屬于計算密集型應用，因此訪存指令占比較小，而SPMV、BFS以及NW分支和訪存指令占比較大。

圖9 各類指令占比Fig.9 Proportion of various instructions

在訪存局部性上，本文所選擇的應用也具有不同的特征，根據文獻［18］計算各個應用的時間、空間局部性得分，如圖10所示。可以看出，5個應用具有不同的時空局部性，其中具有間接訪問的MD、BFS以及SPMV的局部性得分最低。

圖10 時空局部性對比Fig.10 Comparison of temporal and spatial locality

3.3 實驗結果分析

實驗設置了不具有LSE、LSE維序優化和亂序優化的3個CGRA性能對照組，以及由gem5［19］根據文獻［20］仿真的ARM A15的性能結果。

以不具有LSE的CGRA的性能作為性能基準，實驗結果如圖11所示。可以看出，在stencil和NW中，LSE能夠帶來平均2.72倍的性能優化，在3個具有間接訪問的算法應用中，這一優化為1.25倍，在采用亂序執行對間訪問優化時，亂序執行能再帶來平均22%的性能優化。Stencil和NW由于不具有間接訪問，因此不進行亂序執行優化。

圖11 綜合性能對比Fig.11 Comparison of comprehensive performance

除了綜合的應用性能之外，分別探索仿射訪問與亂序執行的性能隨LSE的深度改變的變化，實驗結果如圖12所示。

圖12 LSE存儲空間大小對仿射訪問與間接訪問的影響Fig.12 Influence of LSE storage size on affine access and indirect access

以存儲空間大小為4作為基準，測試LSE存儲空間對性能的優化效果，如圖12（a）所示，LSE到達拐點后能夠達到4倍以上的性能優化。在圖12（b）中以4深度的維序執行為性能基準，可以看出，在間接訪問中，亂序執行相比維序執行能夠達到平均21%的性能提升，并且能夠以更少的存儲空間開銷實現更好的訪存效果。

從硬件開銷角度考慮，相比于在PE內實現多線程的文獻［21］方案，只在LSE中進行線程級并行而不是在每個PE中進行，減少了PE內部的上下文存儲面積；而從功耗角度考慮，相比于從DRAM預取到緩存，再從緩存讀到PE陣列的傳統內存延時掩蓋策略，LSE具有更精準（不會被緩存顛簸影響）和數據搬移次數更少的特點，在功耗上具有優勢。

4 結束語

針對粗粒度可重構陣列的訪存問題以及現有解決方案的不足，本文提出了基于訪存執行解耦合的CGRA訪存結構LSE，其將控制邏輯集成在輕量級的存儲空間中，通過單個LSE、LSE對間以及全局協同可以進行串聯、對齊、跟隨等操作，從而適應不同的訪存場景。LSE在硬件利用率、編程抽象以及間接訪問方面較傳統結構性能均有所提高，實驗結果也證明了其在整體應用及間接訪問中的性能優化效果。下一步將實現寄存器傳輸級（Register Transfer Level，RTL）代碼，得到更精確的硬件實驗數據以及更接近實際流片后的結果。此外，還將研究基于C語言的編程模型和編譯自動化方法，使基于訪存結構LSE的解耦合CGRA對程序員更友好，適用范圍更廣。