陣列處理器分布式Cache的局部優先訪問結構設計*

劉有耀，張 園，山 蕊

(西安郵電大學電子工程學院，陜西 西安 710121)

1 引言

可重構陣列處理器具有設計復雜度低，編程靈活，高主頻、高吞吐率等特性,是未來處理器發展的必然趨勢[1 - 3]。隨著半導體工業和集成電路產業的發展，可重構陣列處理器的集成度顯著增加，支持應用的范圍越來越廣。以人工智能、超高清視頻編解碼、虛擬現實VR(Virtual Reality)、增強現實AR(Augmented Reality)等為代表的新興應用發展迅速，可重構結構在實現新興應用方面表現出較大的優勢。然而，新型應用具有計算數據龐大、訪存頻率較高等特點[4]，對可重構陣列處理器存儲結構的并行訪問特性提出了新的要求。如何在可重構陣列處理器上構建靈活、高效的存儲體系是處理器性能提升的一個關鍵問題[5]。

許多學者針對存儲結構進行了深入的研究，目前普遍采用的解決方法是在處理器中采用Cache緩解處理器處理速度與主存存儲速度失配引起的“存儲墻”問題[6,7]。文獻[8]采用片上大容量共享Cache來進行訪存，這種大容量的Cache結構不但使得整個系統的面積增加且訪存的并行性不高。文獻[9]采用多級Cache來進行訪問，多級Cache因為一致性帶來了較高的能耗，對于實時性數據處理較差，難以滿足新興應用對存儲并行性訪問的需求。為了增加數據的并行訪問，文獻[10]提出一種分布式Cache結構，在處理器PE(Processing Element)簇內根據多處理器特性采用片上分布式Cache結構來提高Cache容量，提高命中率，節省了能耗，提高了實時性。文獻[11]提出的分布式Cache緩存結構，在大規模存儲系統中提高了緩存吞吐量，節省了能耗。文獻[12]提出了一個具有分布式框架和異構緩存方法的通用Cache系統，該系統應用于車輛互聯網等大數據應用的實時高速數據傳輸。隨著新興應用對存儲訪問帶寬、延遲性能需求的進一步提高，分布式Cache成為可重構處理器緩解“存儲墻”問題一種行之有效的解決方案[13,14]。

可重構陣列處理器分布式存儲結構中，常用的實現陣列間數據訪問方法是在陣列處理器簇內PEG(Processing Element Group)設計簇內高效互連訪問結構，滿足簇內高效率、低延遲的訪問需求，這種簇內訪問結構是提升分布式存儲訪問性能的關鍵因素。文獻[15]提出的簇內訪問結構命名為行列交叉訪問結構LR2SS(Line Row two-Stage Switch),該結構針對數據密集型訪問存在較大的訪問延遲且計算并行性較差。文獻[16]提出的簇內全訪問FS(Full-Switch)雖然訪問延遲有所降低，但對于局部性訪問明顯的數據計算不能很好地處理。本文在可重構陣列處理器上基于分布式Cache結構，提出了一種簇內局部優先訪問互連結構LPAS(Local Priority Access Switch)。該結構特點如下所示：

(1)基于可重構陣列處理器全局重用少、局部性訪問明顯的特征，將可重構陣列處理器的存儲訪問進行區域劃分，分為本地區域LA(Local Area)和遠程區域RA(Remote Area)，其中遠程區域的劃分以本地區域為依托，根據訪問距離長短又分為3個等級。以第1行PE為例，第1行Cache為本地區域，第2行Cache為遠程區域1 RA1(Remote Area 1)，第3行Cache為遠程區域2 RA2(Remote Area 2)，第4行Cache為遠程區域3 RA3(Remote Area 3)。

(2)當PE訪問簇內Cache時，LA優先級最高，RA優先級低于LA。RA 3個等級中：RA1優先級最高，RA2次之，RA3最低。

(3)該結構支持低流量無沖突訪問模式下16個Cache的并行訪問，寫訪問操作1個周期完成，讀訪問操作2個周期完成并發送讀寫反饋信息告知PE，提高了可重構處理器的訪問并行性。

2 分布式Cache結構

一種具有局部訪問優先、全局共享的“物理分布、邏輯統一”的通用的分布式Cache結構如圖1所示，上層是1個由4×4個PE組成的陣列處理器簇，下層是由4×4個512×16 bit大小的高速緩存器(Cache)、輪詢仲裁器(arb)以及網絡適配器(NI)組成的存儲結構。簇內訪問結構在陣列處理器和Cache之間形成一個高速數據交互通路，該結構采用統一編址方式，使每個處理器可以通過地址的[7:4]并行性訪問這些分布式Cache，實現簇內數據的高效訪問，提高可重構陣列處理器的訪問并行性。

從PE角度看，該分布式Cache結構中每個PE可以直接訪問片上所有區域Cache，是片上共享Cache結構；物理實現上，采用4×4個獨立的Cache塊，通過簇內存儲結構實現LA區域優先訪問，RA區域次之的優先策略，同時利用多個Cache塊的并行存儲技術，實現簇內4×4個PE的并行訪問。當PE訪問Cache時，簇內訪問結構接受來自PE的請求，根據地址判斷是對LA區域Cache進行訪問還是RA區域Cache進行訪問，當PE訪問LA區域Cache時，優先級最高，當PE訪問RA區域Cache時，需通過簇內訪問結構仲裁出正確的響應順序完成對RA區域Cache的操作。一旦命中簇內Cache，立即將數據返回給請求PE，若不命中，則需要通過輪詢仲裁器仲裁出一路信號通過虛通道路由器VCR0901與外存進行通信。

Figure 1 Intra-cluster distributed Cache architecture圖1 簇內分布式Cache結構

本文設計的簇內訪問結構LPAS用于處理全局重用少、局部性明顯的視頻圖像多媒體數據時，通過在簇內配置數據訪問指令ST把PE最先訪問或經常訪問的數據放在LA的Cache中或較近距離RA的Cache中，把PE最后訪問的數據或不常訪問的數據放在離PE較遠位置RA的Cache中，這樣對于經常訪問的數據可以節省訪問較遠路徑所耗費的時間，同時，減少資源的消耗，提高訪存速度,提升并行訪問帶寬。同時，該設計硬件開銷小，并行訪問性高，可大大提高可重構陣列處理器的訪存帶寬；在應對大數據時代人工智能、計算機視覺等新興應用所要求的高實時性、高并行性以及靈活性時表現出了較好的優勢。

3 簇內訪問結構(LPAS)

3.1 LPAS硬件結構

局部優先訪問電路結構分為3部分，分別為仲裁選擇模塊Arb_select、仲裁模塊Cache_arbiter和總線模塊Bus，如圖2所示。

Figure 2 Intra-cluster local priority switch architecture圖2 簇內局部優先訪問結構

3.1.1 仲裁選擇模塊Arb_select

仲裁選擇模塊主要完成2個功能：(1)用來接收PE發出的讀寫請求，根據地址判斷請求的目的Cache位置，選擇目的Cache所在的仲裁模塊；(2)根據Bus模塊的反饋信號判斷當前請求是否完成，同時將反饋信息送回給請求的PE。若反饋信號為低，代表當前操作未處理，下1拍PE不能發送新的數據請求，此時將訪存信息暫存在電路中，等待正確的響應順序；若反饋信號為高，代表當前訪問完成，下1拍PE可以重新發送1組數據請求。

3.1.2 仲裁模塊Cache_arbiter

仲裁模塊設計了4種仲裁機制。第N行Cache仲裁機制為Cache_arbiterN(N=0,1,2,3)。每種仲裁機制工作過程如下：根據仲裁選擇模塊傳來的16位使能請求進行沖突仲裁(16位使能請求分別代表PE00～PE33的訪問請求)，有沖突訪問時，根據LA優先，RA次之的訪問順序仲裁出1路信號與Cache進行交互。無沖突訪問時，根據目的Cache的地址直接進行數據交互。

以第1行Cache仲裁Cache_arbiter0為例，仲裁過程如下：當第1行Cache00收到同區域PE阻塞通信時(PE00，PE01，PE02,PE03)，Cache_arbiter0經過輪詢仲裁機制隨機仲裁出1路信號與Cache00交互。當有不同區域PE(PE00,PE10,PE20,PE30)同時訪問Cache00時，Cache00經過Cache_arbiter0仲裁先對LA的PE00響應，然后處理較近距離的PE10,接著是PE20,最后是最遠距離的PE30。

3.1.3 總線模塊Bus

總線模塊主要將16個PE的請求信號和Cache_arbiter仲裁出的1路信號一起作為反饋信息送回到Arb_select模塊，Arb_select模塊根據反饋信息來判斷讀寫訪問操作要不要繼續保持。

3.2 LPAS的訪問機制

可重構陣列處理器分布式Cache的簇內局部優先訪問結構旨在完成簇內 PE和分布式Cache的連接，實現簇內PE和Cache的數據訪問，提高可重構陣列處理器簇內數據的訪問并行性。

Write access

1 input:data_wr_en,data_waddr,data_wdata

2 ifwr_ack=0

3 then Store request singal

4 Judgedata_waddr[7∶4]

5 Select cache_arbiterN

6 ifdata_num>0

7 then Do arbitration

8 output:wr_req_pe_num

9wr_cache_en

10wr_cache_data

11wr_cache_addr

12 ifwr_ack=1

13 then Release storage signal

14 next 1

該結構寫操作如下所示：

(1)當PE發出寫請求時，Arb_select模塊先判斷寫反饋信息wr_ack，若wr_ack為低，Arb_select將訪存信息寄存到電路中，等待正確的順序進行響應。

(2)Arb_select通過寫地址信息data_waddr[7∶4]判斷目的Cache位置，選擇目的Cache對應的仲裁Cache_arbiterN(N=0,1,2,3)。

(3)Cache_arbiterN通過16位讀熱碼data_num(16位讀熱碼分別代表PE00～PE33訪問請求,1代表有訪問請求)進行訪問仲裁，依據其局部優先的訪問特性仲裁出1路信號與目的Cache進行交互。

(4)Cache_arbiterN根據請求的PE號經Bus模塊發送寫反饋信息給請求的PE。

(5)PE收到寫反饋信息后，Arb_select在下1拍將寄存的信息釋放，至此1個完整的寫操作完成。可重構陣列處理器中16個PE可同時對16個Cache進行以上寫操作。PE的讀操作與寫操作類似，這里只給出了寫操作。

4 綜合分析與算法實現

4.1 綜合分析

采用Verilog HDL硬件描述語言，在Questasim10.1d工具下進行功能仿真驗證，選用Xilinx公司的ZYNQ系列芯片 XC7Z045 FFG900-2 FPGA進行綜合，其中LPAS結構與文獻[15]中LR2SS結構、文獻[16] 中FS結構芯片綜合資源使用情況對比如表1所示。

Table 1 FPGA chip resource usage table表1 FPGA資源使用表

分析測試結果表明，綜合后的LPAS結構在無沖突情況下，支持16個PE的同時讀/寫操作，寫操作1個周期完成，讀操作2個周期完成,最高頻率可達221 MHz,訪問峰值帶寬為7.6 GB/s。在無沖突情況下訪問峰值帶寬比LR2SS增加了0.95 GB/s,與FS在無沖突情況下的最高工作頻率和訪問峰值帶寬相近，但比FS占用的硬件資源少。

4.2 圖像處理算法的并行化映射

為驗證簇內局部優先訪問結構LPAS的可行性，將其應用于可重構視頻陣列處理器，搭建驗證平臺，選取灰度共生矩陣GLCM(Gray-Level Co-occurrence Matrix)進行紋理圖像特征提取的算法在此平臺上的映射分析。

灰度共生矩陣反映圖像灰度關于方向、相鄰間隔、變化幅度的綜合信息。一般在0°,45°,90°和135° 4個方向，從圖像灰度為i的像素(x,y)出發，統計距離為δ、灰度為j的像素(x+Δx,y+Δy)同時出現的概率P(i,j,δ,θ)。本文所設計的LPAS局部優先訪問結構對存入同行Cache的數據訪問延遲最低，因此選取水平方向θ=0°,δ=3統計P(i,j,3,0°) 生成GLCM。

P(i,j,3,0°)=

{[(x,y),(x+Δx,y+Δy)]|f(x,y)=i,

f(x+Δx,y+Δy)=j;

x=0,1,…,Nx-1;

y=0,1,…,Ny-1;|Δx|=3,|Δy|=0}

(1)

其中,i,j=0,1,…,L-1；|Δx|和|Δy|分別表示像素(x,y)與像素(x+Δx,y+Δy)的水平距離和垂直距離的絕對值；x,y是圖像中的像素坐標；Nx，Ny分別是圖像的行列數。1幅圖像的灰度級數一般為0～255，共256級。級數太多會導致計算的GLCM較大，求灰度共生矩陣之前，先將圖像灰度級壓縮為4級。用計算得到的4×4灰度共生矩陣提取紋理特征二階矩(能量)，二階矩反映圖像灰度分布均勻程度和紋理粗細度，是GLCM各元素的平方和，f大時，紋理粗，能量大，反之f越小，紋理越細，能量越少，如式(2)所示：

(2)

Figure 3 Image texture extraction map assignment圖3 圖像紋理提取映射分配

整個映射過程在1個簇內實現，如圖3所示。陣列處理器僅有PE33可以與外部交互，將最終得到的二階矩在PE33下用STM指令存到外存。具體映射過程如下：第1步：選取64×64的彩色圖像在Matlab中轉換為灰度圖像，并用LDM和ST指令將像素值讀入到16個PE的Cache中，每個Cache下存放64×4個像素值。第2步：簇內16個PE用LD指令并行從16個Cache中讀取像素值。第3步：16個PE開始并行遍歷像素值,并生成16個GLCM,編號為GLCM0～GLCM15，同時將生成的4×4的GLCM用ST指令存入每個Cache的最后16位地址中，低4位地址存放第1行，中間8位地址依次存放第2行，第3行，最后4位地址存放第4行。處理完成后，用ST指令將相應PE處理完成的握手信號存入PE33的Cache中。第4步：PE33用LD指令查看每個PE處理完成的握手信號，收到握手信號后，PE33將其他15個PE生成的灰度共生矩陣GLCM0～GLCM15用ADD指令和ST指令生成全局共生矩陣GLCM。第5步：PE33將生成的灰度共生矩陣用式(2)進行二階矩計算，將二階矩用STM指令存入外部存儲中。

最終在算法正確處理的情況下執行時間為0.24 ms。生成灰度共生矩陣GLCM0～GLCM15的過程中，16個PE并行訪問本地Cache數據，此時沖突概率為0，存儲訪問帶寬可以達到峰值7.6 GB/s。生成全局灰度共生矩陣GLCM和二階矩的計算時只有PE33訪問執行，沖突概率依舊為0，此時訪問帶寬為450 MB/s。最終該簇內局部優先訪問結構LPAS可以為該算法提供的數據訪存帶寬為478.125 MB/s。

5 仿真性能統計與比較

5.1 仿真性能統計

為驗證簇內局部優先訪問結構LPAS的正確性和局部低時延特性，分別選取了有沖突和無沖突情況的讀寫訪問在Questasim上進行仿真，對4×4分布式Cache中每1行Cache的RA區域和LA區域進行延遲統計。圖4是無沖突訪問的讀寫統計，行1表示第1行Cache的LA區域和RA區域的平均讀寫訪問延遲，行2表示第2行Cache的LA區域和RA區域的平均讀寫訪問延遲，行3表示第3行Cache的LA區域和RA區域的平均讀寫訪問延遲，行4表示第4行Cache的LA區域和RA區域的平均讀寫訪問延遲。由于讀操作和寫操作相似，圖5只統計了沖突概率分別為25%，50%，75%和100%時簇內第1行Cache的LA區域和RA1區域、RA2區域和RA3區域的局部平均寫訪問延遲。

Figure 4 Access without conflict圖4 無沖突訪問

Figure 5 Access with conflict圖5 沖突訪問

從圖4和圖5可以看出，無沖突訪問情況下：每1行Cache不管是LA還是RA平均寫訪問延遲均為1個周期，平均讀訪問延遲為2個周期。沖突訪問情況下：(1)同樣的沖突概率，每1行Cache的LA的平均寫訪問延遲最低，RA1次之，RA3的平均寫訪問延遲最大。(2)隨著沖突概率的增加，LA的平均寫訪問延遲保持在2.5個周期，RA的平均寫訪問延遲呈上升趨勢，其中RA3的平均寫訪問延遲上升最快。從以上分析結果可以看出，該互連結構具有明顯的局部訪問優勢。

5.2 仿真性能比較

為了進一步分析比較LPAS的低時延特性，針對這種簇內LPAS互連設計，進行了多種測試用例仿真，并與 LR2SS和FS進行仿真性能對比。首先對8種簡單的無沖突訪問進行性能仿真統計。(1)同行的PEs訪問同行的Caches，比如PE00訪問Cache10,PE01訪問Cache11,PE02訪問Cache12,PE03訪問Cache13;(2)同列的PEs訪問同行的Caches;(3)同行的PEs訪問同列的Caches;(4)同列的PEs訪問同列的Caches;(5)局部的2×2 PEs陣列交叉訪問；(6)一個局部 2×2 PEs陣列訪問另一個局部2×2 PEs陣列中的Caches；(7)局部 2×2 PEs陣列分別訪問4個局部 2×2 PEs陣列中的Caches；(8)局部 2×2 Caches陣列訪問本地2×2 PEs陣列中的Caches。3種結構的讀寫訪問延遲如圖6所示。

Figure 6 Read and write delay in simple cases圖6 簡單讀寫訪問延遲統計

簡單無沖突測試情況下，FS和LPAS具有相同的讀寫訪問延遲，其中平均寫訪問延遲為1個周期，平均讀訪問延遲為2個周期。LR2SS的平均寫訪問延遲為1.4個周期，平均讀訪問延遲為2.31個周期。由此可得出,在無沖突或低沖突率情況下,FS和LPAS的平均訪問延遲最小，LR2SS的平均訪問延遲最大。

為了更加深入地分析3種簇內結構延遲情況，選取了4類復雜情況測試用例，對寫訪問情況進行測試比對，每種情況至少模擬15種測試case，情況I是不同行的PEs訪問不同行的Caches,也稱為行循環訪問。測試結果表明3種結構的行循環平均寫訪問延遲相同，都為1個周期，這里省略了比對圖。情況II是不同列的PEs訪問不同列的Caches，也稱為列循環訪問，仿真統計結果見圖7。情況III是基于一定的沖突概率不同行的PEs訪問不同行的Caches，稱為不同行訪問不同行，仿真統計結果見圖8。情況IV是基于一定的沖突概率不同列的PEs訪問不同列的Caches，稱為不同列訪問不同列，仿真統計結果見圖9。

Figure 7 Line loop access delay圖7 列循環訪問延遲

Figure 8 Different lines delay with different lines access圖8 不同行訪問不同行

Figure 9 Different rows delay with different rows access圖9 不同列訪問不同列

以上4種復雜情況測試中，無沖突情況下： LR2SS、FS和LPAS結構的行循環平均寫訪問延遲相同，均為1個周期；FS和LPAS的列循環平均寫訪問延遲均為1個周期，LR2SS的平均列循環寫訪問延遲最大，為2.3個周期；加入沖突后：不同行訪問不同行的訪問情況下，FS和LPAS的平均寫訪問延遲均為1.42個周期，LR2SS的平均寫訪問延遲最大，為2.8個周期；不同行訪問不同列的訪問情況下，LPAS的平均寫訪問延遲最低為1.41個周期，FS的平均寫訪問延遲為1.43個周期，LR2SS的平均寫訪問延遲最大，為2.61個周期。從以上各種模擬情況可得到：多數情況下FS和LPAS的平均寫訪問延遲基本相同，也是3種結構中平均寫訪問延遲最低的，在有沖突的不同列訪問不同列的訪問中，LPAS平均寫訪問優于FS結構。

6 結束語

針對可重構視頻陣列處理器數據的訪存問題，本文基于分布式Cache結構設計了一種簇內局部優先訪問結構，該結構實現了簇內4×4個PE對4×4個Cache的并行訪問，在沒有沖突時對簇內Cache直接訪問，有沖突時按照本地區域優先，遠程次之的響應順序完成訪問。通過Xilinx公司的ZYNQ系列芯片 XC7Z045 FFG900-2 FPGA開發板進行驗證，在無沖突情況下，該互連結構支持簇內16個PE的同時讀/寫訪問，最高頻率可達221 MHz，訪存峰值帶寬為7.6 GB/s。相比于文獻[15]的LR2SS結構，有更低的訪問延遲，相比于文獻[16]的FS結構，在局部數據訪問時有較好的響應特性，該LPAS結構相比于前2種結構占用的硬件資源最少，且在大多數情況下有較低的訪問延遲。最后選取64×64的圖像提取紋理特征的算法在此結構上映射實現，完成該算法耗費時間為0.24 ms，算法映射過程中的訪問峰值帶寬為7.6 GB/s,且LPAS結構可為該算法提供 478.125 MB/s的訪存帶寬。