文獻(xiàn)標(biāo)識(shí)碼： A
文章編號(hào)： 0258-7998(2013)01-0027-04
自1978年以來(lái)，我國(guó)的集成電路用量和產(chǎn)量幾乎以平均每年20%的速度同步增長(zhǎng)，集成電路生產(chǎn)中心也在向中國(guó)大陸轉(zhuǎn)移，使我國(guó)IC產(chǎn)業(yè)迅速發(fā)展。目前IC制造工藝水平已達(dá)到28 nm，為設(shè)計(jì)高性能DSP系統(tǒng)打下了牢固的基礎(chǔ)。DSP處理器速度與存儲(chǔ)器速度之間的差異是DSP體系結(jié)構(gòu)設(shè)計(jì)的一個(gè)瓶頸問(wèn)題，在DSP處理器的存儲(chǔ)層次中，Cache是離處理器內(nèi)核最近的一層存儲(chǔ)器，而Cache技術(shù)是有效解決DSP處理器的存儲(chǔ)層問(wèn)題的重要技術(shù)[1]?？梢砸罁?jù)Cache的速度和命中率來(lái)配置Cache的參數(shù)，使Cache的性能達(dá)到最佳[2]。
1 BWDSP處理器總體結(jié)構(gòu)
BWDSP處理器是中國(guó)電子集團(tuán)第38研究所自主研制的一款32 bit靜態(tài)超標(biāo)量處理器，采用8發(fā)射、11級(jí)流水線、SIMD架構(gòu)。處理器指令總線寬度為512 bit，數(shù)據(jù)總線位寬為256 bit；指令存儲(chǔ)空間和數(shù)據(jù)存儲(chǔ)空間在物理上是分開(kāi)的，指令存儲(chǔ)空間大小為2 MB，指令Cache空間為512 KB，數(shù)據(jù)存儲(chǔ)空間為8 MB；取指程序計(jì)數(shù)器每變化一次，從指令Cache中取出8條指令為一個(gè)256 bit指令包進(jìn)入指令流水線。BWDSP處理器的執(zhí)行部件包含在4個(gè)執(zhí)行宏中，分別為macro x、macro y、macro z、macro t。指令譯碼單元解析從指令包中得到的并行指令，并決定指令在那些執(zhí)行宏中運(yùn)行，進(jìn)而為指令分配對(duì)應(yīng)執(zhí)行宏中的執(zhí)行資源，并且把指令翻譯為微操作，發(fā)射到4個(gè)執(zhí)行宏。高性能DSP處理器總體結(jié)構(gòu)如圖1所示。
在高性能DSP處理器上對(duì)指令進(jìn)行重復(fù)訪問(wèn)時(shí)，指令Cache的失效次數(shù)與指令空間大小的關(guān)系：首先計(jì)算第一次重復(fù)訪問(wèn)時(shí)的失效次數(shù)。設(shè)程序指令大小為M，即M0=M/512個(gè)Cache行。當(dāng)M≤512 KB時(shí)，程序被訪問(wèn)后，指令Cache每一組內(nèi)至多包含一個(gè)Cache行的有效指令數(shù)據(jù)，不會(huì)因?yàn)闆_突失效而發(fā)生替換，所以再次執(zhí)行程序時(shí)，不會(huì)使指令Cache發(fā)生失效；當(dāng)M在512 KB～1 024 KB時(shí)，訪問(wèn)完一遍之后，前512個(gè)Cache行的數(shù)據(jù)會(huì)填充每組內(nèi)的一個(gè)Cache行，而超過(guò)512個(gè)Cache行的部分，每個(gè)Cache行的指令數(shù)據(jù)有1/4的概率替換掉有效數(shù)據(jù)，因此，被替換出去的Cache行數(shù)約為(M0-512)/4，即重復(fù)訪問(wèn)的失效概率約為(M0-512)/4 M；對(duì)于M在1 024 KB～1 536 KB、1 536 KB～2 048 KB、2 048 KB～∞的情況時(shí)，可用同樣的方法分析得到訪問(wèn)一遍之后被替換出去的Cache行數(shù)目。
由上述可知，當(dāng)執(zhí)行程序指令空間小于512 KB(即M0<512 KB)時(shí)，所有Cache行都不會(huì)被替換掉；而當(dāng)執(zhí)行程序指令空間大于512 KB時(shí)，被替換出去Cache行數(shù)呈線性增長(zhǎng)，并且不同區(qū)間內(nèi)增長(zhǎng)的斜率依次變大。因此，當(dāng)執(zhí)行程序指令空間大于指令Cache大小時(shí)，指令Cache行被替換出去的概率與指令Cache的替換算法有關(guān)。
指令Cache 參數(shù)包括：Cache容量大小、Cache塊大小、組相聯(lián)度和替換策略。在某種程度上，可通過(guò)優(yōu)化Cache參數(shù)提高Cache的性能，但當(dāng)Cache容量增加到某一程度時(shí)，Cache命中率將迅速降低[3]。指令Cache替換算法是影響指令Cache性能的主要因素，目前常見(jiàn)的指令Cache替換算法有Random、FIFO、LRU、LFU、MRU、SCK-4[4]，此外還有比較新穎的LNC算法。FIFIO和Random算法硬件實(shí)現(xiàn)簡(jiǎn)單，但其性能不佳；而常用的LRU算法性能最佳，但是硬件實(shí)現(xiàn)過(guò)于復(fù)雜，同時(shí)該算法占用時(shí)間較多。因此，LRU替換算法不是指令Cache最佳的替換算法[5]。預(yù)取技術(shù)是利用空間局部性，若利用預(yù)取技術(shù)來(lái)克服LRU算法，其缺點(diǎn)將導(dǎo)致缺失不斷增加[6]。而采用PLRU算法對(duì)LRU算法進(jìn)行改進(jìn)，幾乎不會(huì)影響Cache的缺失率，并且簡(jiǎn)化了硬件實(shí)現(xiàn)代價(jià)及復(fù)雜度[7]。
2 PLRU替換算法
LRU(Least Recently Used)替換算法是基于程序時(shí)間局部性原理(即現(xiàn)在使用指令代碼在不久時(shí)間里將再次訪問(wèn)該條指令代碼)，每次替換最近最少被使用的Cache塊。LRU替換算法是組相聯(lián)Cache中最常用的替換算法之一(即比較Cache組內(nèi)指令行中哪個(gè)指令行時(shí)間最長(zhǎng)沒(méi)有被訪問(wèn)過(guò)則被替換出去)，而且每次都要記錄每個(gè)指令塊的使用情況。Cache是N組相聯(lián)映射，需要log2N位來(lái)描述LRU替換算法中組內(nèi)每塊的使用狀態(tài)[8]。嚴(yán)格意義上的LRU算法實(shí)現(xiàn)代價(jià)很大，因此考慮到硬件開(kāi)銷，通常使用偽LRU替換算法，即PLRU(Pseudo-LRU)算法。PLRU算法與LRU算法相近，但簡(jiǎn)化了數(shù)據(jù)預(yù)測(cè)的過(guò)程[9]。PLRU通過(guò)使用MRU（Most Recently Used）位，使組中每個(gè)Cache塊都有自己的MRU位。4-way組相聯(lián)指令Cache的PLRU替換算法示意圖如圖2所示。
PLRU替換算法的步驟如下：
(1)上電復(fù)位時(shí)，將LRU Array所有入口值設(shè)置為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路中的某一路命中，當(dāng)某一路命中時(shí)則要更新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ù)塊，并更新對(duì)應(yīng)的lru[0:7]的值。
if(lru[0:1]==b00)，
{ 替換way0中的數(shù)據(jù)塊;
同時(shí)要更新對(duì)應(yīng)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ù)塊;
同時(shí)要更新對(duì)應(yīng)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ù)塊;
同時(shí)要更新對(duì)應(yīng)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ù)塊;
同時(shí)要更新對(duì)應(yīng)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 仿真與實(shí)驗(yàn)結(jié)果
BWDSP模擬器包含了編譯器、BWDSP指令集、匯編器，能夠編譯用高級(jí)語(yǔ)言(C語(yǔ)言)編寫的雷達(dá)信號(hào)處理的程序代碼和產(chǎn)生基于BWDSP體系結(jié)構(gòu)的目標(biāo)代碼。BWDSP模擬器的主頻為1 MHz、11級(jí)流水線，其內(nèi)核發(fā)射的寬度為8條指令，指令存儲(chǔ)器為1 Mb，指令Cache大小為256 Kb，4路組相聯(lián)映射，數(shù)據(jù)存儲(chǔ)器為2 Mb。用4個(gè)典型雷達(dá)信號(hào)處理程序xd_lib_test2_1_Cache.out、xd_lib_test2_1_part_cache.out、xd_lib_test2_1_Cache.out、dsp.out在BWDSP模擬器驗(yàn)證平臺(tái)上對(duì)本文提出的PLRU替換算法進(jìn)行仿真實(shí)驗(yàn)，并與直接映射、FIFO、RLU、Random替換算法進(jìn)行對(duì)比，從指令Cache的訪問(wèn)次數(shù)、命中次數(shù)、缺失次數(shù)和命中率來(lái)統(tǒng)計(jì)指令Cache的性能，其仿真結(jié)果如表1所示。
表1的仿真結(jié)果表明，本文提出的PLRU替換算法其命中率高于其他三種替換算法，且實(shí)現(xiàn)PLRU替換算法的硬件代價(jià)相對(duì)于LRU替換算法要低。通過(guò)驗(yàn)證，高性能BWDSP處理器其整體性能都高于其他三種方法的1.12倍。
高性能DSP處理器是未來(lái)DSP發(fā)展趨勢(shì)，高速緩存器的多層次存儲(chǔ)器體系結(jié)構(gòu)是提高數(shù)字信號(hào)處理器系統(tǒng)性能的重要方法。本文在32 bit BWDSP基礎(chǔ)上提出了基于PLRU替換算法的512 bit指令包的指令Cache研究，通過(guò)實(shí)驗(yàn)仿真，指令Cache的PLRU替換算法在指令Cache的命中率比FIFO、RLU、Random替換算法都要高出約5.0%。
參考文獻(xiàn)
[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]．計(jì)算機(jī)應(yīng)用，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] 江喜平，高德遠(yuǎn).CISC中混合Cache的優(yōu)化設(shè)計(jì)[J].計(jì)算機(jī)工程與應(yīng)用，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．