《電子技術應用》
您所在的位置:首頁 > 嵌入式技術 > 設計應用 > 基于BWDSP指令Cache的PLRU替換算法研究
基于BWDSP指令Cache的PLRU替換算法研究
來源:電子技術應用2013年第1期
洪興勇1,,洪 一1,2
1.合肥工業(yè)大學 計算機與信息學院,,安徽 合肥230009,; 2.中國電子科技集團第38研究所,,安徽 合肥230031
摘要: 通過BWDSP模擬器對目前常用的幾種替換算法和大小不同的指令Cache塊進行仿真實驗得出不同缺失率。實驗結果表明,,所提出的PLRU替換算法性能高于LRU,、LFU、FIFO替換算法,,并使BWDSP整體性能提高到為其他三種替換算法的1.12倍左右,。
中圖分類號: TP368
文獻標識碼: A
文章編號: 0258-7998(2013)01-0027-04
The PLRU replacement algorithm of instruction Cache based on BWDSP
Hong Xingyong1,Hong Yi1,,2
1.School of Computer and Information, Hefei University of Technology, Hefei 230009,,China; 2.No.38 Research Institute, China Electronics Technology Group Corporation, Hefei 230031,,China
Abstract: The paper does some experiments for the miss rates of different replacement algorithms and different Cache size on the simulator of BWDSP. The result of experiments shows that the PLRU algorithm is more efficient than LRU, LFU and FIFO algorithms,,and the total performance of BWDSP increases by nearly 12% times.
Key words : BWDSP,;instruction Cache;replacement algorithm,;PLRU

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

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


    在高性能DSP處理器上對指令進行重復訪問時,,指令Cache的失效次數(shù)與指令空間大小的關系:首先計算第一次重復訪問時的失效次數(shù),。設程序指令大小為M,即M0=M/512個Cache行,。當M≤512 KB時,,程序被訪問后,指令Cache每一組內至多包含一個Cache行的有效指令數(shù)據(jù),,不會因為沖突失效而發(fā)生替換,,所以再次執(zhí)行程序時,不會使指令Cache發(fā)生失效,;當M在512 KB~1 024 KB時,,訪問完一遍之后,前512個Cache行的數(shù)據(jù)會填充每組內的一個Cache行,,而超過512個Cache行的部分,,每個Cache行的指令數(shù)據(jù)有1/4的概率替換掉有效數(shù)據(jù),因此,,被替換出去的Cache行數(shù)約為(M0-512)/4,,即重復訪問的失效概率約為(M0-512)/4 M;對于M在1 024 KB~1 536 KB,、1 536 KB~2 048 KB,、2 048 KB~∞的情況時,可用同樣的方法分析得到訪問一遍之后被替換出去的Cache行數(shù)目,。
    由上述可知,,當執(zhí)行程序指令空間小于512 KB(即M0<512 KB)時,,所有Cache行都不會被替換掉,;而當執(zhí)行程序指令空間大于512 KB時,被替換出去Cache行數(shù)呈線性增長,,并且不同區(qū)間內增長的斜率依次變大,。因此,當執(zhí)行程序指令空間大于指令Cache大小時,,指令Cache行被替換出去的概率與指令Cache的替換算法有關,。
    指令Cache 參數(shù)包括:Cache容量大小、Cache塊大小,、組相聯(lián)度和替換策略,。在某種程度上,可通過優(yōu)化Cache參數(shù)提高Cache的性能,,但當Cache容量增加到某一程度時,,Cache命中率將迅速降低[3]。指令Cache替換算法是影響指令Cache性能的主要因素,,目前常見的指令Cache替換算法有Random,、FIFO,、LRU、LFU,、MRU,、SCK-4[4],此外還有比較新穎的LNC算法,。FIFIO和Random算法硬件實現(xiàn)簡單,,但其性能不佳;而常用的LRU算法性能最佳,,但是硬件實現(xiàn)過于復雜,,同時該算法占用時間較多。因此,,LRU替換算法不是指令Cache最佳的替換算法[5],。預取技術是利用空間局部性,若利用預取技術來克服LRU算法,,其缺點將導致缺失不斷增加[6],。而采用PLRU算法對LRU算法進行改進,幾乎不會影響Cache的缺失率,,并且簡化了硬件實現(xiàn)代價及復雜度[7],。
2 PLRU替換算法
    LRU(Least Recently Used)替換算法是基于程序時間局部性原理(即現(xiàn)在使用指令代碼在不久時間里將再次訪問該條指令代碼),每次替換最近最少被使用的Cache塊,。LRU替換算法是組相聯(lián)Cache中最常用的替換算法之一(即比較Cache組內指令行中哪個指令行時間最長沒有被訪問過則被替換出去),,而且每次都要記錄每個指令塊的使用情況。Cache是N組相聯(lián)映射,,需要log2N位來描述LRU替換算法中組內每塊的使用狀態(tài)[8],。嚴格意義上的LRU算法實現(xiàn)代價很大,因此考慮到硬件開銷,,通常使用偽LRU替換算法,,即PLRU(Pseudo-LRU)算法。PLRU算法與LRU算法相近,,但簡化了數(shù)據(jù)預測的過程[9],。PLRU通過使用MRU(Most Recently Used)位,使組中每個Cache塊都有自己的MRU位,。4-way組相聯(lián)指令Cache的PLRU替換算法示意圖如圖2所示,。
  

    PLRU替換算法的步驟如下:
    (1)上電復位時,將LRU Array所有入口值設置為8&rsquo;b11100100,,即lru[0:7]=11100100,。4路中最近經(jīng)常使用情況為way0>way1>way2>way3。
    (2)如果命中Cache,,則按照下述算法更新8 bit的矢量(lru[0:7])值,。
    在BWDSP指令Cache采用4-way組相聯(lián)的Cache中,,Cache命中可能在4路中的某一路命中,當某一路命中時則要更新lru[0:7]的值,。有如下4種情況:
    ①若命中Cache的way0,,則根據(jù)lru[0:1]值為b00、b01,、b10,、b11 4種情況更新lru[0:7]的值:
    if   (lru[0:1]= =b00)
      {lru[6:7]&larr;lru[6:7]-1;lru[4:5]&larr;lru[4:5]-1; lru[2:3]
&larr;lru[2:3]-1; lru[0:1]&larr;b11;}
    else if  (lru[0:1]= =b01)
        { if (lru[2:3]==b00)lru[2:3]&larr;lru[2:3];else lru[2:3]
&larr;lru[2:3]-1;
         if (lru[4:5]==b00)lru[4:5]&larr;lru[4:5];else lru[4:5]
&larr;lru[4:5]-1;
         if (lru[6:7]==b00)lru[6:7]&larr;lru[6:7];else lru[6:7]
&larr;lru[6:7]-1;
         lru[0:1] &larr;b11;}
    else if  (lru[1:0]= =b10)
            { if (lru[2:3]==b11) lru[2:3]&larr;lru[2:3]-1;
else lru[2:3]&larr;lru[2:3];
            if (lru[4:5]==b11) lru[4:5]&larr;lru[4:5]-1;else
lru[4:5]&larr;lru[4:5];
            if (lru[6:7]==b11) lru[6:7]&larr;lru[6:7]-1; else
lru[6:7]&larr;lru[6:7];
            lru[0:1]=b11;}
    else  (lru[1:0]= =b11)
            {lru[6:7]&larr;lru[6:7],;lru[4:5]&larr;lru[4:5],;lru[2:3]
&larr;lru[2:3];lru[0:1]&larr;lru[0:1],;}
    ②若命中Cache 的way1,,則根據(jù)lru[2:3]值為b00、b01,、b10,、b11 4種情況更新lru[0:7]的值:
    if  (lru[2:3]=b00)
      {lru[6:7]&larr;lru[6:7]-1;lru[4:5]&larr;lru[4:5]-1; lru[2:3]
&larr;b11; lru[0:1]&larr;lru[0:1]-1,;}
    else if(lru[2:3]= =b01)
          { if (lru[0:1]==b00) lru[0:1]&larr;lru[0:1];
else lru[0:1]&larr;lru[0:1]-1;
        if (lru[4:5]==b00) lru[4:5]&larr;lru[4:5];
else lru[4:5]&larr;lru[4:5]-1 ,;
        if (lru[6:7]==b00) lru[6:7]&larr;lru[6:7];
else lru[6:7]&larr;lru[6:7]-1 ;
        lru[2:3] &larr;b11;}
    else if(lru[2:3]= =b10)
            { if (lru[1:0]==b11)lru[0:1]&larr;lru[0:1]-1;
else lru[0:1]&larr;lru[0:1];
            if (lru[4:5]==b11)lru[4:5]&larr;lru[4:5]-1;
else lru[4:5]&larr;lru[4:5];
            if (lru[6:7]==b11)lru[6:7]&larr;lru[6:7]-1;
else lru[6:7]&larr;lru[6:7];
            lru[2:3]=b11;}
    else (lru[2:3]= =b11)
            {lru[6:7]&larr;lru[6:7],;lru[4:5]&larr;lru[4:5],;lru[2:3]
&larr;lru[2:3];lru[0:1]&larr;lru[0:1],;}
    ③若命中Cache 的way2,,則根據(jù)lru[4:5]值為b00、b01,、b10,、b11 4種情況更新lru[0:7]的值:
    if(lru[4:5]=b00)
       {lru[6:7]&larr;lru[6:7]-1;lru[4:5]&larr;b11;lru[2:3]
&larr;lru[2:3]-1;lru[0:1]&larr;lru[0:1]-1;}
    else if(lru[4:5]= =b01)
        { if (lru[0:1]= =b00)lru[0:1]&larr;lru[0:1];
else lru[0:1]&larr;lru[0:1]-1;
        if (lru[2:3]= =b00)lru[2:3]&larr;lru[2:3]; else lru[2:3]
&larr;lru[2:3]-1;
        if (lru[6:7]= =b00)lru[6:7]&larr;lru[6:7]; else lru[6:7]
&larr;lru[6:7]-1;
        lru[4:5] &larr;b11}
    else if(lru[4:5]= =b10)
            { if (lru[1:0]==b11)lru[0:1]&larr;lru[0:1]-1,;
else lru[0:1]&larr;lru[0:1];
            if (lru[2:3]==b11)lru[2:3]&larr;lru[2:3]-1,;
else lru[2:3]&larr;lru[2:3];
            if (lru[6:7]==b11)lru[6:7]&larr;lru[6:7]-1;
else lru[6:7]&larr;lru[6:7];
            lru[4:5]=b11;}
    else  (lru[2:3]= =b11)
            {lru[6:7]&larr;lru[6:7]; lru[4:5]&larr;lru[4:5];
lru[2:3]&larr;lru[2:3]; lru[0:1]&larr;lru[0:1];}
    ④若命中Cache 的way3,,則根據(jù)lru[6:7]值為b00,、b01、b10,、b11 4種情況更新lru[0:7]的值:
    if (lru[6:7]==b00) {lru[6:7]&larr;b11,;lru[4:5]&larr;lru[4:5]-1;
lru[2:3]&larr;lru[2:3]-1; lru[0:1]&larr;lru[0:1]-1;}
    else if(lru[6:7]= =b01)
        { if (lru[0:1]==b00)lru[0:1]&larr;lru[0:1];
else lru[0:1]&larr;lru[0:1]-1;
        if (lru[2:3]==b00)lru[2:3]&larr;lru[2:3];
else lru[2:3]&larr;lru[2:3]-1 ,;
        if (lru[4:5]==b00)lru[4:5]&larr;lru[4:5],;
else lru[4:5]&larr;lru[4:5]-1 ,;
        lru[6:7] &larr;b11}
    else if(lru[6:7]= =b10)
            { if (lru[1:0]==b11)lru[0:1]&larr;lru[0:1]-1;
else lru[0:1]&larr;lru[0:1];
            if (lru[2:3]==b11)lru[2:3]&larr;lru[2:3]-1;
else lru[2:3]&larr;lru[2:3];
            if (lru[4:5]==b11)lru[4:5]&larr;lru[4:5]-1;
else lru[4:5]&larr;lru[4:5];
            lru[6:7]=b11;}
    else (lru[6:7]= =b11)
            {lru[6:7]&larr;lru[6:7];lru[4:5]&larr;lru[4:5];
lru[2:3]&larr;lru[2:3]; lru[0:1]&larr;lru[0:1];}
    (3)如果Cache缺失,則按照下述替換算法替換Cache的數(shù)據(jù)塊,,并更新對應的lru[0:7]的值,。
    if(lru[0:1]==b00),
      {  替換way0中的數(shù)據(jù)塊;
         同時要更新對應lru[0:7]的值:lru[6:7]=lru[6:7]-1;
         lru[4:5]=lru[4:5]-1;lru[2:3]=lru[2:3]-1;lru[0:1]=11;}
    if(lru[2:3]==b00)
      {  替換way1中的數(shù)據(jù)塊;
         同時要更新對應lru[0:7]的值:lru[6:7]=lru[6:7]-1;
         lru[4:5]=lru[4:5]-1;lru[2:3]=b11;lru[0:1]=lru[0:1]-1;}
    If(lru[4:5]==b00)
      {  替換way2中的數(shù)據(jù)塊;
         同時要更新對應lru[0:7]的值:lru[6:7]=lru[6:7]-1,,
         lru[4:5]=b11,,lru[2:3]=lru[2:3]-1,lru[0:1]
         =lru[0:1]-1;}
    if (lru[6:7]==b00)
      {  替換way3中的數(shù)據(jù)塊;
         同時要更新對應lru[0:7]的值:lru[6:7]=b11;
         lru[4:5]= lru[4:5]-1;lru[2:3]= lru[2:3]-1;lru[0:1]=
         lru[0:1]-1;}
3 仿真與實驗結果
    BWDSP模擬器包含了編譯器,、BWDSP指令集,、匯編器,能夠編譯用高級語言(C語言)編寫的雷達信號處理的程序代碼和產(chǎn)生基于BWDSP體系結構的目標代碼,。BWDSP模擬器的主頻為1 MHz,、11級流水線,其內核發(fā)射的寬度為8條指令,,指令存儲器為1 Mb,,指令Cache大小為256 Kb,4路組相聯(lián)映射,,數(shù)據(jù)存儲器為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的訪問次數(shù),、命中次數(shù)、缺失次數(shù)和命中率來統(tǒng)計指令Cache的性能,,其仿真結果如表1所示,。

 

 

    表1的仿真結果表明,本文提出的PLRU替換算法其命中率高于其他三種替換算法,,且實現(xiàn)PLRU替換算法的硬件代價相對于LRU替換算法要低,。通過驗證,高性能BWDSP處理器其整體性能都高于其他三種方法的1.12倍,。
    高性能DSP處理器是未來DSP發(fā)展趨勢,,高速緩存器的多層次存儲器體系結構是提高數(shù)字信號處理器系統(tǒng)性能的重要方法。本文在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 12th Latin 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,F(xiàn)LYNN M J.Hardware and software Cache prefetching techniques for MPEG benchmarks[J].IEEE Transactions on Circuits  and Systems for Video Technology,,2000,,10(5):782-796.
[7] 江喜平,高德遠.CISC中混合Cache的優(yōu)化設計[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.

此內容為AET網(wǎng)站原創(chuàng),,未經(jīng)授權禁止轉載。