用智能最近最少使用方案在高速缓存中进行功率性能调整

具体实施方式

处理器通常包括用于存储频繁使用的数据值的内部高速缓存。内部高速缓存通过减少为检索数据值和指令而对外部存储器的访问来提高处理器的性能。然而，随着包括在处理器中的内部高速缓冲存储器的数目增加，处理器消耗的功率也增加。

高速缓存通常比主存储器更小且更快，且存储来自最频繁使用的主存储器位置的数据的副本。高速缓存的地址空间被分成高速缓存行，高速缓存行的大小通常大于主存储器存取的大小。

高速缓存行大小是能在主存储器和高速缓存之间传输的最小存储器单元。高速缓存行通常存储多个字以利用引用的局部性，即，如果一个位置被读取，那么其后的位置可能此后不久就会被读取。主存储器和高速缓存中的每个位置具有关联的索引或地址。高速缓存中的每个位置具有关联的标志，用于存储也存储在高速缓存中的主存储器中的高速缓存行的索引。

当从主存储器的地址中读/向主存储器的地址写时，首先通过将主存储器地址的一部分与存储在高速缓存中的所有标志相比较来检查高速缓存，以确定该地址是否存储在高速缓存中。如果存在匹配，则高速缓存命中。如果不匹配，则高速缓存未命中。通常，高速缓存未命中时，在高速缓存中为未命中的地址分配新的条目，然后将从主存储器读取的数据的标志和副本存储在高速缓存中。

在N路组相联高速缓存中，地址空间被分成高速缓存行大小的高速缓存位置的块。高速缓存位置(高速缓存行)集合成组，每组具有N个高速缓存位置或N路。在找到给定地址的相应组之后，在该组内找到高速缓存行大小的高速缓存位置。高速缓存内有N个可缓存主存储器中的任何特定位置的位置。读取相联高速缓存中与每个条目一起存储的标志，以确定为特定主存储器地址要选择高速缓存的哪个条目。通常，N路组相联高速缓存并行读取存储在高速缓存中的所有N个标志和N个数据并选择与匹配标志关联的数据。

当所有高速缓存位置已满时，需要刷新(回收)该组内的其中一个元素以便为新元素腾出空间。有许多替换策略用于选择要刷新的元素。一种公知的替换策略基于伪最近最少使用(LRU)算法替换N路相联高速缓存中的元素。在给定一组元素且一系列对元素的访问事件的情况下，伪LRU算法遍历二进制搜索树以寻找伪LRU元素，即最近最有可能没被访问过的元素。二进制搜索树的每个节点具有指示搜索应当进行的方向(右或左)的关联的一位标志。根据标志的值遍历二进制树以查找伪LRU元素，同时在遍历期间通过将伪LRU元素的标志设置为所取的方向的反方向来更新每个标志。

替换策略还选择在高速缓存中将主存储器位置的副本存储在哪里。选择存储主存储器位置的副本的高速缓冲存储器位置可使用存储器位置的索引的一些位。例如，可以使用主存储器位置的索引的最低有效位作为高速缓冲存储器的索引。用存储器位置的索引的一部分来选择高速缓存条目减少了标志中存储的主存储器地址位的数量。

本发明的实施例提供一种减少N路组相联顺序高速缓存中功率消耗的方法。可以通过选择可用路或存储体(bank)的子集并在所选择的子集中选择LRU高速缓存条目，以使用顺序高速缓存的确定性特性来减少功率消耗。在顺序高速缓存中，高速缓存内的数据是顺序存储的，并按预定方式来访问。例如，指令高速缓存是顺序高速缓存，其中指令按程序定义的静态次序被存储。顺序高速缓存的另一个例子是跟踪高速缓存，其中指令在被解码之后或在退出时按执行的次序被存储。

图1是根据本发明原理的系统100的框图，系统100包括可配置为可伸缩N路组相联高速缓存的指令高速缓存102。处理器104包括用于与主存储器(外部存储器)108通信的总线接口单元106和用于存储通过总线接口单元106从主存储器108提取的指令的指令高速缓存102。处理器还包括耦合到指令高速缓存102的执行单元110，它执行从指令高速缓存102提取的指令。主存储器108可为Rambus动态随机存取存储器(RDRAM)、双倍数据速率动态随机存取存储器(DDR RAM)、同步动态随机存取存储器(SDRAM)或任何相似类型的存储器。

通过将频繁使用的数据值存储在指令高速缓存102中，因减少了为检索指令而对外部存储器110的访问，从而提高处理器104的性能。本发明的实施例将针对8路组相联指令高速缓存来描述。然而，本发明不限于8路组相联指令高速缓存。可以结合使用伪最近最少使用(LRU)算法的任何N路组相联顺序高速缓存来使用本发明。

可以将存储器分成可单独寻址的块，通称为存储体。基于地址，可以交替执行对存储体的访问，以便一次仅一个存储体是直接可访问的。因此，可以通过将组中的高速缓存位置或路分布在多个单独的存储体上(组的一个高速缓存位置存储在每个存储体中)，以减少高速缓存内的功率消耗。

图2是说明细分成8个存储体的图1所示的指令高速缓存102的框图。指令高速缓存102是以非节能模式为8路组相联高速缓存配置的。

虽然图2中未示出，但是指令高速缓存102的每个存储体可以包括附加的电路，包括解码器电路、读出电路和其它控制电路。解码器电路可用于将地址信息解码，以确定给定存储体的选定组，而读出电路可用于读出选定组的数据。控制电路可用于能在存储体内执行写和读操作。

8个存储体202_0，...，202_7中的每个存储体能够存储对应于N个组中的每个组的一路。例如，对应于组0至组n-1的0路存储在存储体0中，对应于组0至组n-1的路7存储在存储体7中。由于标志比较需要时间，所以存储在每个存储体中的路信息是时间关键的。因此，可以对所有“路”并行地执行标志比较，即对8个存储体的每一个存储体并行地执行标志比较以确定存储高速缓存条目的存储体。

因为有8个单独的路(存储体)，所以这8个存储体中的每个存储体存储特定组的一个元素。为了选择存储特定组的LRU元素的存储体，伪LRU算法保存7位LRU矢量(LRU[0]-LRU[6])。从LRU[0]开始检查每个LRU位的状态以确定要选择8个存储体中的哪一个存储体。

表1

如表1所示，LRU[0]的状态确定是从存储体0-3的集合中选择存储体还是从存储体4-7的集合中选择存储体。如果LRU[0]为“0”，则从存储体0-3的集合中选择存储体，如果LRU[0]为“1”，则从存储体4-7的集合中选择存储体。即使LRU[0]的状态选择存储体的两个集合的其中一个集合，仍必须对所有的存储体通电，因为基于伪LRU算法，在选择要覆写(回收)的元素之后，另一个集合的存储体将被选择，以便用于选择下一个要覆写的元素。

图3是图2所示的存储体其中之一202_0的实施例的框图。存储体202_0包括标志阵列300、数据阵列302和状态阵列304。数据阵列302存储高速缓存行中存储的数据。标志阵列300存储与高速缓存行对应的地址的标志部分。状态阵列304存储关于高速缓存中的条目是否有效的指示。数据阵列302和标志阵列300相对比较大，因此每个存储体的功率的很大部分被这些阵列消耗。

通常，物理存储器地址包括标志、组索引和偏移值。组索引用于选择组，而偏移值用于选择组内的位或字。将标志位与存储在标志阵列中对应于条目的标志位相比较来确定该物理存储器地址的数据是否存储在高速缓存中，即，是否存在高速缓存命中。

图4是说明根据本发明原理配置为4路组相联高速缓存的可伸缩8路组相联的实施例的框图。调整处于活动的路的数量以达成功率与性能的折衷。路的调整不涉及对高速缓存结构的任何物理改动，而且允许对多个市场领域使用相同的芯片，例如，使用相同的芯片作为用于高性能服务器的8路组相联高速缓存和用于移动系统的4路组相联高速缓存。

可以由修改的伪最近最少使用(LRU)算法通过在分配期间限制路选择来执行调整路的数目。在所示实施例中，虽然有8路，但是任何时间高速缓存的仅一半的路(存储体)是处于活动的，而其它4个存储体中的数据阵列、标志阵列和状态阵列可以断电。在可忽略性能上的损失的前提下，这样减少约一半的功率消耗。

在示出的8路相联高速缓存实施例中，通过可编程模式，高端工作站可使用所有的8路，而移动和超低功率领域可以仅使用存储体(路)的子集，例如，4路、2路、或1路。在一个实施例中，可编程的模式是启用/禁用位。

通过在分配期间将选择限制于N路的子集，以调整路的数量来达成功率与性能的折衷。高速缓存中的路的仅可选择子集是活动的，而其它组可以断电以减少功率消耗。

在一个实施例中，32K指令高速缓存具有64组的8路，其中每一路具有64字节的高速缓存行。8路的每一路都实施为存储体而每个存储体都具有标志阵列、数据阵列和状态阵列，如结合图3所示论述的。高速缓存行的64字节数据被存储在数据阵列中。32位的线性指令指针(LIP)组成标志部分并被存储在标志阵列中，6位的LIP用于选择64个组的其中一个组。由于每条高速缓存行都为64字节，所以当选择组时可忽略LIP的6个最低有效位(LIP[5]-LIP[0])。

本发明的实施例应用于任何顺序高速缓存，即按顺序方式访问的高速缓存，例如指令高速缓存或追踪高速缓存。指令高速缓存是存储要执行的指令的快速本地存储器。通常，指令高速缓存存储指令流。当代码的顺序代码段被执行时，处理器要执行的指令流呈现出高度空间局部性。空间局部性的概念是，如果数据附近的数据刚被引用过，则引用该数据的可能性更高。

当在代码中发生循环时，该流也呈现出高度空间和时间局部性。时间局部性是指在一时间点被引用的数据可能在不久的将来某个时间再次被引用的概率可能性。

不使用LRU矢量的最低有效位来选择N路的子集，而是使用由线性指令指针的一部分标识的地址范围。在示出的实施例中，使用LIP[12]在8路组相联指令高速缓存中选择4路的一组。由于存储器中指令存储的特性，通常顺序地访问指令高速缓存，因此下一个要访问的指令将在路的相同子集中是可能的。因此，可以将路的另一组断电以节省功率消耗，而对基于LIP[12]的状态选择的路的第一子集通电。对于特定的地址，始终仅访问8路组相联高速缓存中的4路，而可以将其它的4路断电。

如图4中的实施例所示，不使用LRU[0]位，而使用LIP[12]基于由LIP[12]的状态标识的地址范围来选择路的子集。当LIP[12]为“1”，即LIP[12:10]为“1XX”时，启用路4-7(存储体4-7 202_3、...、202_6)。当LIP[12]为“0”，即LIP[12:10]为“0XX”时，启用路0-3(存储体0-3202_0、...、202_2)。在任何时间，LIP要么为“0”要么为“1”，因此在任何给定的时间两个“4路”子集中仅一个子集被选择。对于特定的寻址方案，可以始终访问4路。

与使用LRU[0]来选择多路中的一路并通过在遍历时将其设为相反状态来更新的伪LRU算法对比，该路的组是基于线性指令指针中的地址位的其中之一来选择的。

使用线性指令指针来选择N路的子集避免了对高速缓存结构的物理改变。相反，通过使用线性指令指针，在分配期间基于地址范围来限制选择。电力节省适用于路中的数据阵列、标志阵列和状态阵列。对于当前未处于活动状态的路，可以在N路的子集的每一路中将数据阵列、标志阵列和状态阵列断电。

返回到图3，可以通过单独的控制信号来控制对存储体202_0中的标志阵列300、数据阵列302和状态阵列304的每个阵列通电。在一个实施例中，利用LIP[12]来限定打开和关闭标志阵列300和状态阵列304的控制信号，这样当在8路组相联高速缓存中基于LIP[12]的状态启用4路模式时，对4个未选择的路中的标志阵列300和状态阵列304的供电处于关闭。

利用每路(存储体)中的标志阵列300输出的路启用信号限定打开和关闭数据阵列的控制信号，因此也关闭未选择的路的数据阵列，从而导致额外的电力节省。

图5是用于将可伸缩8路存储体指定配置为4路组相联高速缓存的路选择器500的实施例。在所示的实施例中，路选择器包括2∶1多路复用器502。多路复用器502基于4路启用的状态来选择旧的LRU[0]或LIP[12]作为新的LRU[0]转发以供伪LRU算法使用。这样允许在高速缓存被配置成8路相联高速缓存的情况下将旧的LRU[0]作为新的LRU[0]转发，而在高速缓存被配置成4路组相联高速缓存的情况下将LIP[12]作为新LRU[0]转发。

图6说明8路智能伪LRU的实施例。如图所示，使用LIP[12]的状态来确定是启用包括路0、路1、路2和路3的路的子集还是启用包括路4、路5、路6和路7的路的子集。在LIP[12]的状态选择了路的一个子集后，使用LRU[6]-LRU[1]以从所选定的子集中选择路。

图7说明可伸缩8路智能伪LRU的实施例。在所示的实施例中，可通过使用线性指令指针(LIP)的附加位来扩展可断电的N路的子集。在可伸缩方法中，可以使用可用的8路中的4路以将8路组相联高速缓存修改成4路组相联高速缓存，使用可用的8路中的2路以将8路组相联高速缓存修改成2路组相联高速缓存，使用可用的8路中的1路以将8路组相联高速缓存修改成1路直接映射的高速缓存。

例如，当选择“2路模式”时，高速缓存变成4个“2路”高速缓存(或者实质上是256个组和2路)，最后当选择“直接映射”模式时，高速缓存变成8个“1路”高速缓存。如先前所论述的，可以基于选择的操作模式在高速缓存中将特定路的数据和标志阵列断电。

例如，在“2路模式”，对于数据、标志和状态阵列，可以将这些路中的6路断电，由此节省很多的电力。表2示出使用LIP[12]、[11]、[10]的真值表以用于说明对应于不同模式所使用的路。

表2

在所示的实施例中，使用线性指令指针值中的高阶地址位，即LIP[12-10]来选择所使用的路，因为使用这些地址位不影响高速缓存的顺序次序。

在“4路模式”中仅使用4路数据、标志和状态，可以将其余的路断电。在一个实施例中高速缓存可以是芯片上高速缓存，即与处理器在相同的芯片上。

在该实施例中，将结合图5描述的路选择器500修改成根据所选的模式是2路还是直接映射来选择是否将LIP[11:10]转发到伪LRU算法。例如，当选择2路模式时，使用LIP[12]来选择要存储在路0-3或路4-7中的地址的范围，并且根据LIP[12]的状态，使用LIP[11]在路0-1、路2-3、路4-5和路6-7之间进行选择。

在另一个实施例中，可以使用控制寄存器中的可编程(消除特征(de-feature))模式位来使一组路能打开/关闭。消除特征位允许在如台式机、可移动系统和服务器这样的不同类型系统中使用相同的处理器。例如，可以在用于移动系统的处理器中启用对一组路打开或关闭供电的能力，在移动系统中节省电力比性能更为重要。

通过将高速缓存从8路组相联高速缓存减少成两个4路组相联高速缓存，性能损失是可忽略的。由于路的数目减少而导致的高速缓存未命中，性能的损失增大。然后，可在功率和性能之间达成折衷。

在另一个实施例中，可以通过使模式永久性地被设置的熔丝位来实现可编程模式、例如图5示出的4路模式，从而使8路组相联高速缓存永久性地作为4路组相联高速缓存来工作以提供功率更低的处理器。

本领域的技术人员显见，本发明实施例中所包含的方法可以在包括计算机可用介质的计算机程序产品中实施。例如，这种计算机可用介质可由其上存储有计算机可读程序代码的只读存储器装置组成，如只读光盘(CD ROM)或常规的ROM装置或计算机软盘。

虽然本发明的实施例是参照其实施例来具体地描述和示出的，但是本领域技术人员将理解，在不背离由所附的权利要求涵盖的本发明范围的前提下可作形式和细节上的多种更改。