3)缺点: 这种硬件堆栈既要求具有相联比较的功能,又要 求能全下移、部分下移和从中间取出一项的功能, 成本较高,因此只适用于组相联且组内块数较少的 LRU替换场合。 4)变形 上述这种堆栈,各块被访问的先后次序由该项在 堆栈中距离栈底是近还是远来反映。为了避免堆栈 中各行存放的内容经常同时进行下移,以便节省成 本,我们采用另一种变形,即将存放块号的寄存器 的几何位置与 Cache中的块号对应,而用寄存器存
3)缺点： 这种硬件堆栈既要求具有相联比较的功能，又要 求能全下移、部分下移和从中间取出一项的功能， 成本较高，因此只适用于组相联且组内块数较少的 LRU替换场合。 4)变形 上述这种堆栈，各块被访问的先后次序由该项在 堆栈中距离栈底是近还是远来反映。为了避免堆栈 中各行存放的内容经常同时进行下移，以便节省成 本，我们采用另一种变形，即将存放块号的寄存器 的几何位置与Cache中的块号对应，而用寄存器存
放值的大小来表示已被访问过的远近次序。以组相 联为例,每一组均使用如图444那样的一个寄存器 组,由2个寄存器组成,每个寄存器为s位宽,可以 存放表示从0到25-1的次序值。如果让越是最近访 问的,其次序值愈小,则只需通过相联比较求最大 值(不是相联比较相符),找到该最大值所在的寄 存器号,这就是对应 Cache中应该被替换掉的块的 块号
放值的大小来表示已被访问过的远近次序。以组相 联为例，每一组均使用如图4.44那样的一个寄存器 组，由2 s个寄存器组成，每个寄存器为s位宽，可以 存放表示从0到2 s－1的次序值。如果让越是最近访 问的，其次序值愈小，则只需通过相联比较求最大 值（不是相联比较相符），找到该最大值所在的寄 存器号，这就是对应Cache中应该被替换掉的块的 块号
第0块的访问次序 块0 第1块的访问次序 块1 第2块的访问次序 块2 25个 寄存器 第25-1块的访问次序 块251 S位 Cache存贮器 (其中一组) (其中一组) 图444组相联LRU法经寄存器实现 (每组一个,需要有相联比较功能
第0块的访问次序 第1块的访问次序 第2块的访问次序 第2 s -1块的访问次序 块0 块1 块2 块2 s -1 2 s个 寄存器 S位 （其中一组） Cache存贮器 （其中一组） 图 4.44 组相联LRU法经寄存器实现 （每组一个，需要有相联比较功能）
2比较对法 1)思路 比较法的基本思路是让各个块成对组合,用一个 触发器的状态来表示该比较对内两块访问的远近 序,再经门电路就可以找到LRU块。比如说有AB C三块,互相之间可以组合成 AB BA AC CA BO CB6对,其中AB和BA、AC和CA、BC和CB是重复 的,所以TAB为“1”,表示A比B更近被访问过; AB 为“0”,则表示B比A更近被访问过。TAC、TBC也 类 似定义。这样,当访问过的次序为ABC,即最近
2.比较对法 1)思路 比较法的基本思路是让各个块成对组合，用一个 触发器的状态来表示该比较对内两块访问的远近次 序，再经门电路就可以找到LRU块。比如说有A B C三块，互相之间可以组合成AB BA AC CA BC CB6对，其中AB和BA、AC和CA、BC和CB是重复 的，所以TAB为“1”，表示A比B更近被访问过； TAB 为“0”，则表示B比A更近被访问过。TAC 、TBC也 类 似定义。这样，当访问过的次序为A B C，即最近
访问过的为A,最久未被访问过的为C,则这三个触 发器状态分别为TB=1,TAC=1,TBC=1。如果访 问过的次序为BAC,C为最久未被访问过的块,则 此时必有TAB=0,TAC=1,TBC=1因此最久未被 访问过的块C作为被替换掉的块的话,用布尔代数 式必有: CLRU=TAB TAC TBC +TAB TAC TBC =TAC'TBO 同理可得: B LRU AB BC A LRU =1AB°1AC 因此,完全可以用门、触发器等硬件组合实现,如 图445所示:
访问过的为A，最久未被访问过的为C，则这三个触 发器状态分别为TAB＝1，TAC＝1，TBC＝1。如果访 问过的次序为B A C，C为最久未被访问过的块，则 此时必有TAB＝0，TAC＝1，TBC＝1。因此最久未被 访问过的块C作为被替换掉的块的话，用布尔代数 式必有： CLRU＝TAB• TAC•TBC +TAB• TAC•TBC ＝TAC•TBC 同理可得： BLRU＝TAB•TBC ； ALRU＝TAB• TAC 因此，完全可以用门、触发器等硬件组合实现，如 图4.45所示：