文獻標識碼: A
文章編號: 0258-7998(2013)01-0027-04
自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’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]←lru[6:7]-1;lru[4:5]←lru[4:5]-1; lru[2:3]
←lru[2:3]-1; lru[0:1]←b11;}
else if (lru[0:1]= =b01)
{ if (lru[2:3]==b00)lru[2:3]←lru[2:3];else lru[2:3]
←lru[2:3]-1;
if (lru[4:5]==b00)lru[4:5]←lru[4:5];else lru[4:5]
←lru[4:5]-1;
if (lru[6:7]==b00)lru[6:7]←lru[6:7];else lru[6:7]
←lru[6:7]-1;
lru[0:1] ←b11;}
else if (lru[1:0]= =b10)
{ if (lru[2:3]==b11) lru[2:3]←lru[2:3]-1;
else lru[2:3]←lru[2:3];
if (lru[4:5]==b11) lru[4:5]←lru[4:5]-1;else
lru[4:5]←lru[4:5];
if (lru[6:7]==b11) lru[6:7]←lru[6:7]-1; else
lru[6:7]←lru[6:7];
lru[0:1]=b11;}
else (lru[1:0]= =b11)
{lru[6:7]←lru[6:7],;lru[4:5]←lru[4:5],;lru[2:3]
←lru[2:3];lru[0:1]←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]←lru[6:7]-1;lru[4:5]←lru[4:5]-1; lru[2:3]
←b11; lru[0:1]←lru[0:1]-1,;}
else if(lru[2:3]= =b01)
{ if (lru[0:1]==b00) lru[0:1]←lru[0:1];
else lru[0:1]←lru[0:1]-1;
if (lru[4:5]==b00) lru[4:5]←lru[4:5];
else lru[4:5]←lru[4:5]-1 ,;
if (lru[6:7]==b00) lru[6:7]←lru[6:7];
else lru[6:7]←lru[6:7]-1 ;
lru[2:3] ←b11;}
else if(lru[2:3]= =b10)
{ if (lru[1:0]==b11)lru[0:1]←lru[0:1]-1;
else lru[0:1]←lru[0:1];
if (lru[4:5]==b11)lru[4:5]←lru[4:5]-1;
else lru[4:5]←lru[4:5];
if (lru[6:7]==b11)lru[6:7]←lru[6:7]-1;
else lru[6:7]←lru[6:7];
lru[2:3]=b11;}
else (lru[2:3]= =b11)
{lru[6:7]←lru[6:7],;lru[4:5]←lru[4:5],;lru[2:3]
←lru[2:3];lru[0:1]←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]←lru[6:7]-1;lru[4:5]←b11;lru[2:3]
←lru[2:3]-1;lru[0:1]←lru[0:1]-1;}
else if(lru[4:5]= =b01)
{ if (lru[0:1]= =b00)lru[0:1]←lru[0:1];
else lru[0:1]←lru[0:1]-1;
if (lru[2:3]= =b00)lru[2:3]←lru[2:3]; else lru[2:3]
←lru[2:3]-1;
if (lru[6:7]= =b00)lru[6:7]←lru[6:7]; else lru[6:7]
←lru[6:7]-1;
lru[4:5] ←b11}
else if(lru[4:5]= =b10)
{ if (lru[1:0]==b11)lru[0:1]←lru[0:1]-1,;
else lru[0:1]←lru[0:1];
if (lru[2:3]==b11)lru[2:3]←lru[2:3]-1,;
else lru[2:3]←lru[2:3];
if (lru[6:7]==b11)lru[6:7]←lru[6:7]-1;
else lru[6:7]←lru[6:7];
lru[4:5]=b11;}
else (lru[2:3]= =b11)
{lru[6:7]←lru[6:7]; lru[4:5]←lru[4:5];
lru[2:3]←lru[2:3]; lru[0:1]←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]←b11,;lru[4:5]←lru[4:5]-1;
lru[2:3]←lru[2:3]-1; lru[0:1]←lru[0:1]-1;}
else if(lru[6:7]= =b01)
{ if (lru[0:1]==b00)lru[0:1]←lru[0:1];
else lru[0:1]←lru[0:1]-1;
if (lru[2:3]==b00)lru[2:3]←lru[2:3];
else lru[2:3]←lru[2:3]-1 ,;
if (lru[4:5]==b00)lru[4:5]←lru[4:5],;
else lru[4:5]←lru[4:5]-1 ,;
lru[6:7] ←b11}
else if(lru[6:7]= =b10)
{ if (lru[1:0]==b11)lru[0:1]←lru[0:1]-1;
else lru[0:1]←lru[0:1];
if (lru[2:3]==b11)lru[2:3]←lru[2:3]-1;
else lru[2:3]←lru[2:3];
if (lru[4:5]==b11)lru[4:5]←lru[4:5]-1;
else lru[4:5]←lru[4:5];
lru[6:7]=b11;}
else (lru[6:7]= =b11)
{lru[6:7]←lru[6:7];lru[4:5]←lru[4:5];
lru[2:3]←lru[2:3]; lru[0:1]←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.