·上一文章：基于RFID的电力温度监控系统的软件分析与设计
·下一文章：基于CC2530的脉搏感知节点设计
2 PLRU替换算法
LRU (Least Recently Used)替换算法是基于程序时间局部性原理（即现在使用指令代码在不久时间里将再次访问该条指令代码），每次替换最近最少被使用的Cache块。LRU替换算法是组相联Cache中最常用的替换算法之一（即比较Cache组内指令行中哪个指令行时间最长没有被访问过则被替换出去），而且每次都要记录每个指令块的使用情况。Cache是N组相联映射，需要log2N位来描述LRU替换算法中组内每块的使用状态。严格意义上的LRU算法实现代价很大，因此考虑到硬件开销，通常使用伪LRU替换算法，即PLRU (Pseudo -LRU）算法。PLRU算法与LRU算法相近，但简化了数据预测的过程。 PLRU通过使用MRU (Most Recently Used）位，使组中每个Cache块都有自己的MRU位。4-way组相联指令Cache的PLRU替换算法示意图如图2所示。
4 -way组相联Cache由Data Array、 Tag Array, LRUArray三部分组成，其中，LRU Array的入口数目与TagArray的人口数目一致，每个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、表示way l的状态；lru[4:5]表示way2的状态；lru[6:7]表示way3的状态。其lru[0:7]结构图如图3所示。
PLRU替换算法的步骤如下：
(1)上电复位时，将LRU Array所有入口值设置为8'b11100100，即lru [ 0: 7 ] =11100100 。 4路中最近经常使用情况为way0 > way 1 > way2 > way3 。
(2)如果命中Cache，则按照下述算法更新8 bit的矢量（lru[0:7]）值。
在BWDSP指令Cache采用4-way组相联的Cache中，Cache命中可能在4路中的某一路命中，当某一路命中时则要更新lru[0:7]的值。有如下4种情况：
①命中Cache的way0，则根据Iru [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] ←bI11；｝
else if (lru[0：1]==b01)
{ if (lru [ 2：3]==b00)lru[2：3] ←ru[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]←b 11；｝
else if (lru[1:0]= =b10)
｛if (lru[2：3]==b11)Iru [ 2：3] ← lru[2：3]-1；
else lru [ 2：3] ←lru[2：3]；
if (lru[4：5]==b11)Iru [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]；｝
②若命中Cach。的way 1，则根据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]←b 11；｝
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]；｝
