高速Cache中一种树状结构的改进型LRU算法的替换策略

摘要

本发明公开了高速Cache中一种树状结构的改进型LRU算法的替换策略，该发明基于程序局部性原理，采用树状结构的改进型LRU算法的替换策略来提高替换效率以及命中率。在本发明中，当高速缓存需要更新时，解码电路将对有效位进行判断，当有效位全为1时，将依据树状结构的改进型LRU算法对替换状态存储器的值进行译码，决定出被替换的line，当有效位不全为1时，则会根据优先译码电路得到需要替换的line，从而完成整个的替换过程。该替换方法可在完成数据读写操作的同时进一步提高高速Cache的数据替换命中速度，提高高速Cache的性能。

说明书

技术领域

本发明涉及嵌入式微处理器设计技术领域，具体涉及高速Cache中一种树状结构的改进型LRU算法的替换策略，进一步涉及如何提高嵌入式微处理器内核快速地从高速Cache中读写数据的方法。

背景技术

嵌入式微处理器的设计难题之一在于嵌入式微处理器的高速工作频率与片外存储器的低速读写速度相差很大，这在很大程度上限制了嵌入式微处理器的性能和效率。在现代微处理器中，在嵌入式微处理器内核与片外储器间设计一级或多级高速缓存Cache组成多层次存储体系已经成为了缩小存储器与嵌入式微处理器速度差距的有效解决方法。但是高速缓存在工作时，容易发生缺失，当在高速缓存缺失发生时，会从主存中读出一个line存储到高速缓存里。这时，如果高速缓存中已经没有空闲的line，那么就需要从中选择一个line作为替换对象替换掉，采用不同的替换算法替换的效率大大不同，不同的算法所占用的资源也不一样。当前主流的替换算法为LRU(Least Recently Used)算法，即最近最久未使用算法。LRU算法是一种统计的方法，根据各个way的使用情况，统计出近期最少被使用的那个line然后用作替换。这种方法能够比较好地反映程序的局部性原理，且有很好的命中率，但是从硬件实现上来说比其他的常规算法实现更困难，并且会消耗更多的资源。这样导致替换速度变慢，增加系统的功耗。

因此亟待提出一种基于程序局部性原理，采用树状结构思想的改进型LRU算法的替换策略来提高替换效率以及命中率。

发明内容

本发明的目的是为了解决现有技术中的上述缺陷，提供高速Cache中一种树状结构的改进型LRU算法的替换策略。

本发明的目的可以通过采取如下技术方案达到：

高速Cache中一种树状结构的改进型LRU算法的替换策略，所述的替换策略包括下列步骤：

S1、完成四路组相连映射方式Set以及line的划分；

S2、对所划分的每一个Set设置一个寄存器栈，其容量为高速Cache的Set数n，寄存器栈由栈顶到栈底依次记录最近被访问的Set_a和最久没有被访问的Set_b；

S3、当某一个Set被访问时，那么位于该Set号之上的栈内元素依次向下移动一行，而被访问的Set号则压入栈顶，通过上述操作实现栈内元素的重排，得到近期不常使用的Set号；

S4、在近期不常使用的Set号中采用一种基于树状结构的方法找出具体某一路中的line需要进行替换；

S5、从主存中读出一个line的数据存储到高速Cache中，完成数据替换。

进一步地，所述的步骤S4具体如下：

S401、在Set中设计一个三位的寄存器，记做status[2:0]，更新方式为:status[2:0]＝00×时替换Way0，status[2:0]＝01×时替换Way1，status[2:0]＝1×0时替换Way2，status[2:0]＝1×1时替换Way3，其中，“×”表示保持原值；

S402、当发生访问缺失时，首先判断寄存器status[2:0]中status[2]位的数值，当status[2]＝0时，则判断status[1]的数值，若status[1]＝0时，则替换Way0中的Line，若status[1]＝1时，则替换Way1中的Line；

当status[2]＝1时，则判断status[0]的数值，若status[0]＝0时，则替换Way2中的Line，若status[0]＝1时，则替换Way3中的Line。

进一步地，所述的步骤S1具体如下：

S101、将高速缓存按照Cache的空间大小要求进行4等分，得到4路，即4个way，分别为way1、way2、way3和way4；

S102、将主存按照每一路的大小进行等分得到Page 0～Page n；

S103、将高速缓存中的每一个way和主存中的每一个Page重新进行等分得到每一个line，分别为line0～line n；

S104、所有的路way中相同的line分为一个Set，完成Set的设置后即完成四路组相连映射方式Set以及line的划分。

本发明相对于现有技术具有如下的优点及效果：

1)本发明基于程序局部性原理，采用树状结构的改进型LRU算法的替换策略来提高替换效率以及命中率。在本发明中，当高速缓存需要更新时，解码电路将对有效位进行判断，当有效位全为1时，将依据树状结构的改进型LRU算法对替换状态存储器的值进行译码，决定出被替换的line，当有效位不全为1时，则会根据优先译码电路得到需要替换的line，从而完成整个的替换过程。

2)本发明完成高速缓存中页面的替换，并在解码电路中采用并行判断电路来完成解码，可显著提高高速缓存的替换速度。

附图说明

图1是本发明中四路组相连中Set以及line的划分；

图2是本发明中寄存器栈法得到近期不常使用的Set号；

图3是本发明中树状结构的LRU算法替换策略流程图；

图4是本发明中状态模块的结构图；

图5是本发明中解码电路的工作流程；

图6是本发明中部分line处于空闲时的替换电路；

图7是本发明中基于树状结构的LRU算法的并行比较电路；

图8是本发明中编码电路结构。

具体实施方式

为使本发明实施例的目的、技术方案和优点更加清楚，下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。

实施例

为了克服高速Cache中LRU替换算法的缺点与不足，本实施例提供一种高效快速以及高命中率的替换方法，该替换方法可在完成数据读写操作的同时进一步提高高速Cache的数据替换命中速度，提高高速Cache的性能。

一种树状结构的改进型LRU算法的替换策略，具体包括如下步骤：

S1、完成四路组相连映射方式Set以及line的划分。

该步骤S1中四路组相连映射方式Set以及line的划分的步骤如下：

S101、将高速缓存按照设计(Cache的空间大小)要求进行4等分，得到4路(4-way)，分别为way1、way2、way3和way4；

S102、将主存按照每一路(way)的大小进行等分得到Page 0～Page n；

S103、将高速缓存中的每一个way和主存中的每一个Page重新进行等分得到每一个line(line 0～line n)；

S104、所有的路(way)中相同的line分为一个Set(组，如way 0与way1中的line 0即组成了Set_0，一共有Set_0～Set_n)。完成Set的设置后即完成四路组相连映射方式Set以及line的划分，划分完成后如图1所示。

S2、对所划分的每一个Set设置一个寄存器栈，其容量为高速Cache的Set数n，寄存器栈由栈顶到栈底依次记录最近被访问的Set_a和最久没有被访问的Set_b。

S3、当某一个Set被访问时，那么位于该Set号之上的栈内元素依次向下移动一行，而被访问的Set号则压入栈顶，这样实现了栈内元素的重排，得到近期不常使用的Set号。

S4、在近期不常使用的Set号中采用一种基于树状结构的方法找出是哪一路中的line需要进行替换。

该步骤S4具体如下：

S401、在Set中设计一个三位的寄存器，记做status[2:0]，更新方式为:status[2:0]＝00×时替换Way0；status[2:0]＝01×时替换Way1；status[2:0]＝1×0时替换Way2；status[2:0]＝1×1时替换Way3。(“×”表示保持原值)，真值表如表1所示，以实现对于近期访问的情况进一步的记录；

表1树状结构的LRU算法更新方法

S402、当发生访问缺失时，首先判断寄存器status[2:0]中status[2]位的数值。当status[2]＝0时，则判断status[1]的数值。若status[1]＝0时，则替换Way0中的Line；若status[1]＝1时，则替换Way1中的Line。当status[2]＝1时，则判断status[0]的数值。若status[0]＝0时，则替换Way2中的Line，若status[0]＝1时则替换Way3中的Line。

S5、从主存中读出一个line的数据存储到高速Cache中，完成数据替换。

在实际电路设计中，高速缓存的每一个line的替换状态(replace statues)是由一个SRAM或者一组寄存器构成的，结构如图4所示。在状态模块电路中，由编码电路路和解码电路组成。

1、解码电路

解码电路的主要功能是根据有效位来判断是否每一个line中都已经被全部填满了数据，并且对替换状态进行译码。当高速缓存需要更新时，解码电路从以下两种情况判断出用于替换的line：

(1)有效位不全为1。这说明该Set中还有空闲的line。此时解码电路将有效位不为1的那个line，用于数据替换，图5中的左半部分是当部分line处于空闲时的流程图，其具体流程为：

T1、首先判断有效位valid[0]，如果valid[0]为0则替换way0；否则进入T2；

T2、判断有效位valid[1]，如果valid[1]为0则替换way1；否则进入T3；

T3、判断有效位valid[2]，如果valid[2]为0则替换way2；否则替换way3；

此处在硬件上是属于一种优先译码电路，真值表如下：

表2部分line处于空闲状态时的替换电路真值表

故根据真值表得到最小项，而设计出最优化的门级电路，如图6所示，门级电路逻辑表达式为：

rep[0]＝～valid[0]；

rep[1]＝valid[0]&(～valid[1])；

rep[2]＝valid[0]&valid[1]&(～valid[2])；

rep[3]＝valid[0]&valid[1]&valid[2]；

(2)所有的有效位均为1。这种情况下，所有的line都已经被使用。解码电路将依据图3中的树状结构的思想，将替换状态存储器的值进行译码，决定出被替换的line。

当所有line都已经被使用时，解码电路会判断替换状态存储器的每一位。但如果对每一位进行逐一判断必然会增加路径的延时，如果采用并行的判断方式可以加快判断的速度，从而降低路径的延时，所以本发明在电路设计上采用如图7所示的并行判断电路来完成解码电路的设计。

2、编码电路

编码电路将各个way的命中和替换情况进行编码，并改写替换状态存储器中的内容。当高速缓存访问某个way时(不管是命中后读写还是缺失后替换)，编码电路根据树状结构的LRU算法，将最近访问高速缓存的信息进行编码，并记录在寄存器中，图8是编码电路的结构。

上述实施例为本发明较佳的实施方式，但本发明的实施方式并不受上述实施例的限制，其他的任何未背离本发明的精神实质与原理下所作的改变、修饰、替代、组合、简化，均应为等效的置换方式，都包含在本发明的保护范围之内。