基于BWDSP指令Cache的PLRU替換算法研究

洪興勇 ，洪 一 ，2

(1.合肥工業大學 計算機與信息學院，安徽 合肥 230009；2.中國電子科技集團第38研究所，安徽 合肥 230031)

自1978年以來，我國的集成電路用量和產量幾乎以平均每年20%的速度同步增長，集成電路生產中心也在向中國大陸轉移，使我國IC產業迅速發展。目前IC制造工藝水平已達到28 nm，為設計高性能DSP系統打下了牢固的基礎。DSP處理器速度與存儲器速度之間的差異是DSP體系結構設計的一個瓶頸問題，在DSP處理器的存儲層次中，Cache是離處理器內核最近的一層存儲器，而Cache技術是有效解決DSP處理器的存儲層問題的重要技術[1]。可以依據Cache的速度和命中率來配置Cache的參數，使Cache的性能達到最佳[2]。

1 BWDSP處理器總體結構

BWDSP處理器是中國電子集團第38研究所自主研制的一款32 bit靜態超標量處理器，采用8發射、11級流水線、SIMD架構。處理器指令總線寬度為512 bit，數據總線位寬為256 bit；指令存儲空間和數據存儲空間在物理上是分開的，指令存儲空間大小為2 MB，指令Cache空間為512 KB，數據存儲空間為8 MB；取指程序計數器每變化一次，從指令Cache中取出8條指令為一個256 bit指令包進入指令流水線。BWDSP處理器的執行部件包含在4 個執行宏中，分別為 macro x、macro y、macro z、macro t。指令譯碼單元解析從指令包中得到的并行指令，并決定指令在那些執行宏中運行，進而為指令分配對應執行宏中的執行資源，并且把指令翻譯為微操作，發射到4個執行宏。高性能DSP處理器總體結構如圖1所示。

在高性能DSP處理器上對指令進行重復訪問時，指令Cache的失效次數與指令空間大小的關系：首先計算第一次重復訪問時的失效次數。設程序指令大小為M，即M0=M/512個Cache行。當M≤512 KB時，程序被訪問后，指令Cache每一組內至多包含一個Cache行的有效指令數據，不會因為沖突失效而發生替換，所以再次執行程序時，不會使指令Cache發生失效；當M在512 KB～1 024 KB時，訪問完一遍之后，前 512個 Cache行的數據會填充每組內的一個Cache行，而超過512個Cache行的部分，每個Cache行的指令數據有1/4的概率替換掉有效數據，因此，被替換出去的Cache行數約為(M0-512)/4，即重復訪問的失效概率約為(M0-512)/4 M；對于M在 1 024 KB～1 536 KB、1 536 KB～2 048 KB、2 048 KB～∞的情況時，可用同樣的方法分析得到訪問一遍之后被替換出去的Cache行數目。

由上述可知，當執行程序指令空間小于512 KB(即M0＜512 KB)時，所有 Cache行都不會被替換掉；而當執行程序指令空間大于512 KB時，被替換出去Cache行數呈線性增長，并且不同區間內增長的斜率依次變大。因此，當執行程序指令空間大于指令Cache大小時，指令Cache行被替換出去的概率與指令Cache的替換算法有關。

指令 Cache參數包括：Cache容量大小、Cache塊大小、組相聯度和替換策略。在某種程度上，可通過優化Cache參數提高Cache的性能，但當Cache容量增加到某一程度時，Cache命中率將迅速降低[3]。指令Cache替換算法是影響指令Cache性能的主要因素，目前常見的指令Cache替換算法有Random、FIFO、LRU、LFU、MRU、SCK-4[4]，此外還有比較新穎的LNC算法。FIFIO和Random算法硬件實現簡單，但其性能不佳；而常用的LRU算法性能最佳，但是硬件實現過于復雜，同時該算法占用時間較多。因此，LRU替換算法不是指令Cache最佳的替換算法[5]。預取技術是利用空間局部性，若利用預取技術來克服LRU算法，其缺點將導致缺失不斷增加[6]。而采用PLRU算法對LRU算法進行改進，幾乎不會影響Cache的缺失率，并且簡化了硬件實現代價及復雜度[7]。

2 PLRU替換算法

LRU(Least Recently Used)替換算法是基于程序時間局部性原理(即現在使用指令代碼在不久時間里將再次訪問該條指令代碼)，每次替換最近最少被使用的Cache塊。LRU替換算法是組相聯Cache中最常用的替換算法之一(即比較Cache組內指令行中哪個指令行時間最長沒有被訪問過則被替換出去)，而且每次都要記錄每個指令塊的使用情況。Cache是N組相聯映射，需要log2N位來描述LRU替換算法中組內每塊的使用狀態[8]。嚴格意義上的LRU算法實現代價很大，因此考慮到硬件開銷，通常使用偽LRU替換算法，即PLRU(Pseudo-LRU)算法。PLRU算法與LRU算法相近，但簡化了數據預測的過程[9]。 PLRU 通過使用 MRU（Most Recently Used）位，使組中每個Cache塊都有自己的MRU位。4-way組相聯指令Cache的PLRU替換算法示意圖如圖2所示。

4-way組相聯Cache 由 Data Array、Tag Array、LRU Array三部分組成，其中，LRU Array的入口數目與Tag Array的入口數目一致，每個LRU Array入口包含一個8 bit的 LRU矢量“lru[0:7]。 “lru[0:1]表示 way0的狀態（b00表示way0是最近最少使用，b01表示way0是最近第2少使用，b10表示way0是最近第3少使用，b11表示way0是最近經常使用）；lru[2:3]表示way1的狀態；lru[4:5]表示way2的狀態；lru[6:7]表示way3的狀態。其lru[0:7]結構圖如圖3所示。

PLRU替換算法的步驟如下：

(1)上電復位時，將LRU Array所有入口值設置為8’b11100100，即 lru[0:7]=11100100。4路中最近經常使用情況為 way0＞way1＞way2＞way3。

(2)如果命中Cache，則按照下述算法更新8 bit的矢量(lru[0:7])值。

在BWDSP指令Cache采用4-way組相聯的Cache中，Cache命中可能在4路中的某一路命中，當某一路命中時則要更新lru[0:7]的值。有如下4種情況：

①若命中 Cache的 way0，則根據 lru[0:1]值為 b00、b01、b10、b11 4 種情況更新 lru[0:7]的值：

②若命中 Cache的 way1，則根據 lru[2:3]值為 b00、b01、b10、b11 4 種情況更新 lru[0:7]的值：

③若命中Cache的way2，則根據 lru[4:5]值為b00、b01、b10、b11 4 種情況更新 lru[0:7]的值：

④若命中 Cache的 way3，則根據 lru[6:7]值為 b00、b01、b10、b11 4 種情況更新 lru[0:7]的值：

(3)如果Cache缺失，則按照下述替換算法替換 Cache的數據塊，并更新對應的lru[0:7]的值。

3 仿真與實驗結果

BWDSP模擬器包含了編譯器、BWDSP指令集、匯編器，能夠編譯用高級語言(C語言)編寫的雷達信號處理的程序代碼和產生基于BWDSP體系結構的目標代碼。BWDSP模擬器的主頻為 1 MHz、11級流水線，其內核發射的寬度為8條指令，指令存儲器為 1 Mb，指令 Cache大小為256 Kb，4路組相聯映射，數據存儲器為2 Mb。用4個典型雷達信號處理程序xd_lib_test2_1_Cache.out、xd_lib_test2_1_part_cache.out、xd_lib_test2_1_Cache.out、dsp.out在BWDSP模擬器驗證平臺上對本文提出的PLRU替換算法進行仿真實驗，并與直接映射、FIFO、RLU、Random替換算法進行對比，從指令Cache的訪問次數、命中次數、缺失次數和命中率來統計指令Cache的性能，其仿真結果如表1所示。

表1 指令Cache的仿真結果

表1的仿真結果表明，本文提出的PLRU替換算法其命中率高于其他三種替換算法，且實現PLRU替換算法的硬件代價相對于LRU替換算法要低。通過驗證，高性能BWDSP處理器其整體性能都高于其他三種方法的1.12倍。

高性能DSP處理器是未來DSP發展趨勢，高速緩存器的多層次存儲器體系結構是提高數字信號處理器系統性能的重要方法。本文在32 bit BWDSP基礎上提出了基于PLRU替換算法的512 bit指令包的指令Cache研究，通過實驗仿真，指令Cache的PLRU替換算法在指令Cache的命中率比 FIFO、RLU、Random替換算法都要高出約5.0%。

[1]PEREZ W J H，SANCHEZ E，REORDA M S.Functional test generation for the PLRU replacement mechanism of embedded Cache memories[C].Test Workshop(LATW)，2011 12thLatin American，27-30 March 2011.

[2]TAWADA M，YANAGISAWA M，OHTSUKI T，et al.Exact and fast L1 Cache configuration simulation for embedded systems with FIFO/PLRU Cache replacement policies[C].VLSI Desgin，Automation and Test(VLSI-DAT)，International Symposium，2011：1-4.

[3]KLEEN A，STIENBERG E，ANSCHEL M，et al.An improved instruction Cache replacement algorithm[C].Signal Processing Systems Design and Implementation，2-4 Nov.2005：573-578.

[4]田小波，陳蜀宇.基于最小效用的流媒體緩存替換算法[J].計算機應用，2007，27(3)：733-736.

[5]KLEEN A，STIENBERG E，ANSCHEL M，et al.An improved instruction Cache replacement algorithm[C].Signal Processing Systems Design and Implementation，2-4 Nov.2005：573-578.

[6]ZUCKER D F，LEE R B，FLYNN M J.Hardware and software Cache prefetching techniques for MPEG benchmarks[J].IEEE Transactions on Circuitsand Systems for Video Technology，2000，10(5)：782-796.

[7]江喜平，高德遠.CISC中混合Cache的優化設計[J].計算機工程與應用，2006(10)：109-111.

[8]Zhang Xi，Li Chongmin，Wang Haixia.A Cache replacement policy using adaptive insertion and re-reference prediction[C].Computer Architecture and High Performance Computing.oct.2010：95-102.

[9]MOLMEN S，MOHSEN S，HOSSEIN R M.Performance evaluation of Cache memory organizations in embedded systems[C].Information Technology，2007：1045-1050.