存算解耦合的粗粒度可重構(gòu)陣列訪存結(jié)構(gòu)設計

洪 途，景乃鋒

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

0 概述

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

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

1 存算解耦合與研究現(xiàn)狀

傳統(tǒng)的內(nèi)存層次結(jié)構(gòu)在地址訪問中難以避免緩存缺失問題帶來的內(nèi)存延時，且這一問題在訪存不具有局部性時更嚴重。因此，在緩存缺失時如何掩蓋內(nèi)存延時成為體系架構(gòu)研究中的一個關(guān)鍵問題。

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

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

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

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

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

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

2 基于存算解耦合的訪存結(jié)構(gòu)

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

圖2 LSE對架構(gòu)Fig.2 Architecture of LSE pair

LSE由控制塊和輕量級的存儲空間組成，存儲空間可以在不同的需求中根據(jù)配置對不同類型的訪存進行解耦合優(yōu)化?？刂茐K主要包含有限狀態(tài)機、線程計數(shù)器以及請求緩沖區(qū)。LSE對中主控制塊可以完成主從控制塊之間的數(shù)據(jù)與控制協(xié)同，分別如圖2中粗實線與粗虛線所示，在控制塊所控制的存儲空間可以接收主控制塊的數(shù)據(jù)輸入和控制輸入。LSE對布局在PE陣列的四周，通過互聯(lián)網(wǎng)絡為需要進行訪存的PE提供訪存接口。LSE的布局圖如圖3所示。

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

2.1 仿射訪問

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

圖4 仿射訪問優(yōu)化示意圖Fig.4 Schematic diagram of affine access optimization

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

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

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

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

2.2 寫請求

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

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

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

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

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

2.3 間接訪問

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

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

圖6 間接訪問優(yōu)化示意圖Fig.6 Schematic diagram of indirect access optimization

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

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

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

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

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

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

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

3 實驗與結(jié)果分析

3.1 實驗平臺

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

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

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

3.2 測試應用選擇

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

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

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

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

3.3 實驗結(jié)果分析

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

以不具有LSE的CGRA的性能作為性能基準，實驗結(jié)果如圖11所示?？梢钥闯?，在stencil和NW中，LSE能夠帶來平均2.72倍的性能優(yōu)化，在3個具有間接訪問的算法應用中，這一優(yōu)化為1.25倍，在采用亂序執(zhí)行對間訪問優(yōu)化時，亂序執(zhí)行能再帶來平均22%的性能優(yōu)化。Stencil和NW由于不具有間接訪問，因此不進行亂序執(zhí)行優(yōu)化。

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

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

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

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

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

4 結(jié)束語

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