在MRU分配期间采用软I－MRU成员保护的方法和高速缓存系统

摘要

本发明涉及一种在MRU分配期间采用软I－MRU(最近最常使用)成员保护的方法和高速缓存系统，其中所选择的I－MRU成员(高速缓存行)只在有限数量的逐出循环内受保护，除非该成员在该期间被更新/利用。对指令的更新或访问重新启动确定高速缓存行何时不再作为I－MRU受保护的倒计时。因此，只有经常使用的指令行受保护，并且旧的I－MRU行因老化而到达高速缓存外。旧的I－MRU成员被逐出，使得同余类的所有成员可以用于数据。通过计数器或基于线性反馈移位寄存器(LFSR)而“赶出”I－MRU高速缓存行来完成I－MRU老化。调整LFSR使得I－MRU行在预设数量的逐出内受保护。

说明书

技术领域

本发明一般地涉及一种改进的数据处理系统，并且特别地涉及一种改进的高速缓存机制。更特别地，本发明涉及一种用于在高速缓存内完成I-MRU成员保护的改进的方法和设备。

背景技术

使用一级或多级高速缓存来衔接处理器和主存储器之间的性能差距是数据处理系统中已完善建立的特征。当处理器发出存储器访问请求时，首先将该请求发送到高速缓存以确定所请求的数据或指令是否存在于高速缓存存储器中。当在高速缓存中找到期望的信息时，“命中”就发生了。当对高速缓存的请求或访问没有产生期望的信息时，“未命中”就发生了。作为对未命中的响应，高速缓存“行”中的一行被新的一行替代。选择一行来进行替代的方法称为替代策略。

高速缓存通常采用集合关联方案，通过该方案将高速缓存分成不同类的行，其中每类包含较小的固定数量的行。行的类通常称为“同余类”。同余类中的行(其表明地址能够驻留的位置数)通常称为集合关联高速缓存中的集合。

一般使用的一种类型的替代策略是最近最少使用(LRU)策略。LRU策略建立在同余类中最近最少使用的高速缓存行是最不值得保留的前提上。因此，当需要逐出一个高速缓存行以为一个新行腾出空位时，LRU策略选择一个高速缓存行作为牺牲，该高速缓存行是同余类中最近最少访问的集合(或成员)。

在LRU策略内，典型地，针对LRU状态(在高速缓存中针对每个同余类维持该LRU状态)执行两种类型的操作。

最近最常使用的更新(MRU更新)操作典型地由于高速缓存命中而发生。MRU更新调节LRU状态使得“命中”成员排在该同余类中所有其他成员的前面，将在该成员位置上的高速缓存行设定为该同余类中最有价值的成员。

最近最少使用的牺牲选择(LRU牺牲选择)操作典型地在高速缓存未命中需要分配成员以保持从存储层级结构的其他地方到达的高速缓存行时发生。该操作确定哪一个高速缓存行是同余类中最不值得保留的，逐出该高速缓存行，并且将最近到达的高速缓存行放置在该成员的位置上。

若干因素使多级高速缓存层级结构中LRU替代策略的行为变得复杂，特别是当这些层级结构包含在第n-1级由多个结构共享的第n级高速缓存时更是如此。例如，处理器可以包含第一级指令高速缓存和第一级数据高速缓存。这些高速缓存可以由包括指令和数据的第二级高速缓存来支持。设计这种结构使得对在第一级高速缓存中未命中的高速缓存行的处理器请求很可能在第二级高速缓存中找到。

正如前面所描述的，在第一级高速缓存中的LRU替代策略将处理器最经常使用的那些高速缓存行更新为“最近最常使用”。对于处理器来说更不重要(或更没有价值)的高速缓存行，由于它们不那么经常被使用，所以它们被标记为最近最常使用的可能性更小。这样，更频繁使用的行往往保留在第一级高速缓存中，而较不常使用的行往往被从第一级高速缓存中逐出。

第二级高速缓存中的LRU策略将在第一级高速缓存未命中发生时从第二级高速缓存请求的那些高速缓存行更新为最近最常使用。这些行往往是被从第一级高速缓存中逐出的那些行，并且对于处理器来说比往往在第一级高速缓存中命中的高速缓存行更没有价值。这样，最经常出现在第一级高速缓存没有找到而又被处理器反复需要的情况的高速缓存行是最可能在第二级高速缓存中保留的高速缓存行，这是这些高速缓存行更可能被MRU更新有益地影响的事实。

大量应用具有小的指令覆盖区和更大的数据需求，导致“不平衡”的高速缓存行为，其中处理器最常利用的指令经常被从L2高速缓存中逐出。这样，对处理器最有价值的高速缓存行从第二级高速缓存中的MRU更新受益的可能性更小，并且因此，比对处理器更没有价值的高速缓存行更有可能被从第二级高速缓存逐出。

已经提供了前面的方法用于保护在第一级高速缓存处所需要的特定指令不被从第二级(L2)高速缓存逐出。使用这些方法，L2高速缓存LRU算法包含一个指针以针对L2高速缓存中每个同余类保护指令最近最常使用(I-MRU)行。这个保留的‘路径’适用于防止技术代码(带有小的指令(“I”)覆盖区，但是带有大的数据覆盖区)“破坏”I覆盖区。这种传统的方法将基本上保护高速缓存的一个完整‘路径’。例如8路集合关联高速缓存的1/8将保留给指令。另外，与典型的伪lru算法相结合的剩余数据路径的不对称产生了一些工作负载的次优行为。

因此，本发明认识到，具有一种用于减轻由于对旧指令行的继续保护而表现出的次优性能的改进的方法、设备和计算机系统是有利的，这些旧指令行当前通过I-MRU策略而受保护以不被从第二级包含性的高速缓存逐出。

发明内容

所公开的是一种用于限制旧的指令最近最常使用(I-MRU)行在LRU牺牲选择处理中在MRU成员分配期间在高速缓存的同余类内受保护的时间长度的方法和设备。MRU更新逻辑被扩充为具有用以确定自从初始选择I-MRU成员/行用于I-MRU保护以来所经过的逐出循环的数量的逻辑。逐出循环的最大数量是预设的，在该最大数量的逐出循环之后，曾经受到I-MRU保护的行被认为是“旧”的并不再值得保护。

利用计数器/定时器跟踪在由MRU更新逻辑初始选择I-MRU成员用于保护之后所经过的循环的数量。在一个实施例中，同余类包括8个成员，LRU状态阵列包括三个附加的保护比特，其表示同余类中要受保护以不被逐出高速缓存的特定成员(0-7)的值。在每次后续经过MRU更新逻辑期间通过将由保护比特标识的特定成员标记为I-MRU来保护该成员不被选择为下一个LRU牺牲成员。高速缓存线的这一I-MRU保护一直继续到下面若干情况中的一种发生，包括：(1)MRU更新逻辑选择一个不同的成员用于I-MRU保护；(2)该I-MRU成员变为无效；或者(3)预设数量的逐出循环完成而没有访问/利用该行/成员。当第三种情况发生时，MRU更新逻辑取消对旧的I-MRU行的选择，使该行符合条件，可被选择用于LRU逐出。

根据一个实施例，针对每个同余类，修改MRU更新逻辑以通过基于软件的计数器/定时器来跟踪所经过的逐出循环的数量。定时器功能与MRU分配逻辑相关联，其中被分配以I-MRU状态的成员只在预设数量的逐出循环内受保护。一旦经过该数量的逐出循环而没有选择新的成员作为I-MRU，旧的I-MRU行就不再受保护并且可被选择用于LRU逐出。然后旧的I-MRU行可以在后续LRU逐出循环中被从高速缓存逐出，并且然后可以利用该行来存储数据。在发生后续访问的情况下，计数器/定时器实施例考虑到重新设置I-MRU成员的寿命。

在另一个实施例中，将线性反馈移位寄存器(LFSR)添加到MRU更新逻辑以表示计数器/定时器功能。调整LFSR使得I-MRU行在预设的随机数量的逐出内受保护。LFSR使对保护比特的编码过载，使得保护比特不再表示同余类的特定成员。LFSR实施例使得不需要大量定时器。

附图说明

被认为是本发明特点所在的新颖特征在所附权利要求书中提出。但是，参考应结合附图阅读的对示例性实施例的以下详细描述，可以最好地理解本发明本身以及其优选使用模式、进一步的目的和优势，其中：

图1是可以在其中实现本发明的一个实施例的数据处理系统的框图；

图2是可以在其中实现本发明的另一个数据处理系统的示图；

图3A-图3C表示根据本发明的实施例的示例性MRU更新功能的电路图，该MRU更新功能已经被扩充为具有受时间限制的成员I-MRU保护能力；

图4是根据本发明的示例性实施例的包括带成员保护比特的扩展LRU阵列的高速缓存体系结构，该阵列已经被流水线式地输入到MRU更新逻辑以在预设数量的逐出循环内保护选定的成员；以及

图5A和图5B是示出了根据本发明的示例性实施例的MRU更新逻辑的逻辑组件的两个实施例的框图，这两个实施例分别配置为具有计数器和LFSR以支持针对有效的受保护成员的受时间限制的I-MRU分配。

具体实施方式

现在参考附图并且特别地参考图1，示出了可以在其中实现本发明的一个示例性实施例的数据处理系统的框图。数据处理系统100是传统的多处理器计算机系统的示例。数据处理系统100具有若干处理单元，其中处理单元102和处理单元104被示出。这些处理单元连接到各种外围设备，包括输入/输出(I/O)设备106、存储器108以及固件110，其主要目的是只要第一次启动计算机就从外围设备中的一个找出并加载操作系统。I/O设备106可以包括例如显示监控器、键盘和永久存储设备。

处理单元102和104通过不同的装置与外围设备通信，这些装置包括例如通用互联或总线112。数据处理系统100可以具有很多没有示出的附加组件，诸如用于连接到诸如调制解调器或打印机之类的设备的串行和并行端口。本领域的普通技术人员将进一步理解，还有另外的可以与图1的框图中示出的组件联合使用的组件。例如，显示适配器可以用于控制视频显示监控器，以及存储控制器可以用于访问存储器108。同样，数据处理系统100可以具有多于两个的处理单元。

在对称多处理器(SMP)计算机中，所有的处理单元一般都相同。换句话说，这些处理器都使用指令和协议的公共集或子集来运行，并且一般具有相同的结构。典型的体系结构在图1中示出。在这些示例中，处理单元102包括包含处理器核心116的集成芯片114，并且处理单元104包括包含处理器核心120、指令高速缓存126和数据高速缓存128的集成电路118。处理器核心116和120包括寄存器和执行单元。这些组件用于执行程序指令以运行数据处理系统100。

正如所示出的，在图1中，处理单元102和处理单元104也在各自的集成电路114和118内包括高速缓存，诸如指令高速缓存122、数据高速缓存124、指令高速缓存126和数据高速缓存128。这些高速缓存是使用高速存储设备实现的。高速缓存一般用于临时存储可以由处理器反复访问的值，以便通过避免从存储器108加载这些值时的较长延迟来加速处理。当在单个集成芯片上与处理器核心一起集成封装时，这些高速缓存称为是在“板上”的。在这些示例中，位于集成电路114和集成电路118内的高速缓存是第1级(L1)高速缓存。每个高速缓存与一个高速缓存控制器(没有示出)关联，该高速缓存控制器管理高速缓存存储器与处理器核心和/或更低级的存储器之间的数据传输。

处理单元可以包括附加的高速缓存。例如，处理单元102包括高速缓存130并且处理单元104包括高速缓存132，它们称为第2级(L2)高速缓存。L2高速缓存130和L2高速缓存132充当存储器108与板上L1高速缓存，即指令高速缓存122、数据高速缓存124、指令高速缓存126和数据高速缓存128之间的媒介。这些L2高速缓存比板上高速缓存存储更大量的信息(例如指令和数据)，但是具有更长的访问延迟。例如，高速缓存130和高速缓存132可以集成到芯片中并具有256或512千字节的存储容量，但是处理单元102中的指令高速缓存122和数据高速缓存124以及处理单元104中的指令高速缓存126和数据高速缓存128可能只具有64千字节的总容量。

正如所示出的，高速缓存130和132都连接到总线112。所有从存储器108到处理器核心116的信息加载都通过高速缓存130，而所有到处理器核心120的信息加载都通过高速缓存132。尽管图1只示出了两级高速缓存层级结构，但是在有多级串联高速缓存的地方可以提供多级高速缓存层级结构。例如可以提供L3、L4和L5高速缓存。

在下面的对本发明的示例性实施例的详细描述中，足够详细地描述了实践本发明的特定示例性实施例以使本领域的普通技术人员能够实践本发明，并且应当理解，可以利用其他实施例并且在不偏离本发明的精神或范围的情况下可以进行逻辑的、体系结构的、程序的、机械的、电的及其他的改变。因此，下面的详细描述不应被理解为具有限制性意义，并且本发明的范围只在所附权利要求中限定。

同样，在附图的描述中，给类似的单元提供与前面的附图中类似的名称和参考数字。当后面的附图在不同的上下文中或以不同的功能来利用该单元时，提供给该单元一个代表图号的不同起始数字(例如对于图1来说是1xx，对于图2来说是2xx)。提供分配给单元的特定数字只是为了帮助描述，并不意味着暗示对本发明的任何限制(结构上的或功能上的)。

现在参考图2，根据本发明的一个示例性实施例示出了另一个数据处理系统的示图。也可以在数据处理系统200内实现本发明的处理和设备。这个特定的示例示出了共享的L2高速缓存，而图1中的数据处理系统100示出了非共享的高速缓存。

在这个示例中，数据处理系统200包括两个处理器，即处理器202和处理器204。高速缓存存储器206和高速缓存存储器208分别是位于处理器202和处理器204内的高速缓存存储器。在这个示例中，高速缓存存储器210是一个被这两个处理器共享的第2级高速缓存存储器。通过总线212提供对这个高速缓存存储器的访问。高速缓存控制214包括用于作为对来自处理器202和204的请求的响应而处理存储器210内的高速缓存行的逻辑。高速缓存控制214通过总线216连接到其他组件。例如，固件218、I/O设备220和存储器222连接到总线216.

数据处理系统100和数据处理系统200包括用于处理高速缓存行特别是存储最近获取的指令的高速缓存行的机制。正如下面更详细描述的，本发明提供了一种用于增强指令高速缓存行作为I-MRU保护成员的选择和后续释放的方法、设备和计算机系统。

高速缓存行的替代策略，特别是LRU替代策略在前面通过引用的方式包含于此的以下共同转让、共同未决的申请中被详细描述：序列号11/054,390(律师存档号AUS920040919US1)和序列号11/054,067(律师存档号AUS920041052US1)。此处只描述该描述中影响进行MRU处理的部分。本发明的特征与由这些相关申请所描述的LRU逐出方法/机制和高速缓存拓扑中的I-MRU成员保护功能有关。于是，本发明对MRU成员保护功能提供了进一步的修改/增强，如下面更详细描述的那样。

如上所述，某些操作偶尔期望受保护以在LRU牺牲选择期间不被选择作为牺牲，诸如当不平衡的高速缓存行为发生时(数据高速缓存行的高速流动与指令高速缓存行的低速流动)。这样，本发明提供了用于在LRU牺牲选择期间实现对特定的MRU指令高速缓存行(同余类的成员)的最佳的时间受控的保护的方法和设备。在特定的示例性实施例中，同余类包括8个成员，并且利用三个附加的保护比特来指向同余类内要受保护以不被从高速缓存逐出的特定成员(0-7)。

正如相关申请中所描述的，通过将成员保护比特设置成常量模式(与已更新的成员关联)而不改变向量中的其他比特来完成MRU更新操作。该子集包括n-1比特(其中n是高速缓存的关联度)，这些比特限定了已更新成员与同余类中每个其他成员之间的顺序。

应当注意，利用三个比特作为成员保护比特的特定实现方式是针对8比特的同余类示例而做出的。所需要的比特的实际数量是N，其中N是整数，使得2^N大于或等于同余类中成员的数量。

在处理针对高速缓存请求的操作期间，将保护比特与在LRU牺牲选择和MRU去往I状态期间提供的其他信息同时地以流水线式输入到MRU更新逻辑。MRU更新逻辑被扩充为具有用以对保护比特的值进行解码以产生对应的MRU向量的逻辑，将该MRU向量与MRU更新逻辑内的任意其他MRU向量进行逻辑或(OR)运算以创建单个MRU输入向量。MRU更新逻辑也包括用于在受保护成员被确定为无效时取代对该成员的默认的“进行MRU”(make MRU)处理的逻辑。另外，根据本发明，MRU更新逻辑被扩充为具有用以防止旧I-MRU继续受保护的逻辑。

这个附加逻辑提供的核心功能是提供一种用于确定自从初始选择I-MRU行用于MRU保护所经过的逐出循环的数量的机制。利用计数器/定时器(或线性反馈移位寄存器(LFSR))来跟踪在由I-MRU成员初始选择MRU更新逻辑用于保护之后所经过的循环的数量。通过在每次后续经过MRU更新逻辑期间将由保护比特标识的特定成员标记为I-MRU来保护该成员不被选择为下一个LRU牺牲。逐出循环的最大数量是预设的，在该最大数量的逐出循环之后，曾经受到I-MRU保护的选定行被认为是“旧”的并不再值得保护。这个预设的循环数量是一种设计特征，其可以由系统工程师调整。

通过这个附加逻辑，对高速缓存行的I-MRU保护继续到若干情况中的一种发生，包括：(1)MRU更新逻辑选择一个不同的成员用于I-MRU保护；(2)该I-MRU成员变为无效；或者(3)预设数量的逐出循环完成而没有访问/利用该行/成员。当第三种情况发生时，MRU更新逻辑取消对旧的I-MRU行的选择，使该行符合条件，可被选择用于LRU逐出。

根据一个实施例，针对每个同余类，修改MRU更新逻辑以通过基于软件的计数器/定时器来跟踪所经过的逐出循环的数量。定时器功能与MRU分配逻辑相关联，其中被分配以I-MRU状态的成员只在预设数量的逐出循环内受保护。一旦经过该数量的逐出循环而没有选择新的成员作为I-MRU，旧的I-MRU行就不再受保护并且可被选择用于LRU逐出。然后旧的I-MRU行可以在后续LRU逐出循环中被从高速缓存逐出，并且然后可以利用该行来存储数据。在发生后续访问的情况下，计数器/定时器实施例考虑到重新设置I-MRU成员的寿命。

在另一个实施例中，将线性反馈移位寄存器(LFSR)添加到MRU更新逻辑以提供计数器/定时器功能。调整LFSR使得I-MRU行在预设的随机数量的逐出内受保护。LFSR使对保护比特的编码过载，使得保护比特不再表示同余类的特定成员。LFSR实施例使得不需要大量定时器。

在示例性的实施例中，同余类包括8个成员，LRU状态阵列包括三个附加的保护比特，其表示同余类中要受保护以不被逐出高速缓存的特定成员(0-7)的值。在每次后续经过MRU更新逻辑期间通过将由保护比特标识的特定成员标记为I-MRU来保护该成员不被选择为下一个LRU牺牲成员，直到(a)选择一个不同的成员用于保护；或(b)该成员变为无效；或(c)该成员作为受保护成员超时，如这里所描述的那样。如下面所描述的，将已扩充的MRU更新逻辑(512)扩展为包括支持与保护比特关联的受时间限制的I-MRU成员保护功能所需要的若干逻辑组件。

保护比特用作一个指针，其标识了要受保护的成员/高速缓存行的特定位置(也就是说，在8成员的同余类中，成员0-7中的一个映射到高速缓存行A-H)。由这个指针标识的特定成员成为I-MRU并且因此在LRU牺牲选择期间在预先指定数量的逐出循环内受保护以不被选择作为牺牲，除非该成员是无效的或被作为I-MRU的另一个成员替代。这样，仅当在该行被处理器访问/利用之前该行变为无效或该行的保护状态超时，该受保护成员才会被牺牲。

为了本发明的目的，最近指令获取(I获取)操作触发对在其中存储指令的成员的保护。然后，MRU更新逻辑的操作保护同余类中最近获取的指令(这里称为指令最近最常使用，I-MRU)直到时间计数到期。但是，当检测到具有期望属性的新操作(也就是指令获取)时，该指针变为指向存储新I-MRU的成员。

图4示出了高速缓存体系结构的扩展框图表示，其中将成员保护比特从LRU状态阵列流水线式地输入到MRU更新逻辑。正如所示出的，保护比特通过一系列的锁存器而被锁存，同时执行带有I状态偏置和D状态去往MRU的LRU牺牲选择(参看相关申请)。D状态去往MRU独立于对成员保护比特的流水线操作和处理而发生，并且在前面通过引用的方式包含于此的律师存档号为AUS920041052US1的未决相关专利申请中描述了该过程。

图4的描述着重于对成员保护比特的流水线操作及关联的功能。完成实际确定和最终选择保护成员用于MRU保护所需要的附加逻辑在图5A和图5B的逻辑图中提供。

高速缓存同余类索引(或地址)保存在锁存器401中。从那里该地址被同时路由到目录阵列402、LRU状态阵列403以及为了进行随机读取高速缓存的操作而路由到数据阵列404。

已访问的同余类的13个状态比特被从LRU状态阵列403中读取并存放到锁存器405中。牺牲选择逻辑406选择牺牲成员，并且所选择的牺牲成员位置被存放在锁存器409中。然后，牺牲选择逻辑406通过流水线锁存器410和411将部分或全部LRU状态信息传递到MRU更新逻辑412。如上所述，“命中成员”信息被存放在锁存器415中，并且被流水线式地转发到锁存器416，从这里该信息被路由到MRU更新逻辑412。更进一步地，反MRU逻辑产生反MRU向量，该向量也从锁存器422被路由到MRU更新逻辑412。

在上述过程的同时，成员保护比特被放置到第一锁存器430中并通过流水线锁存器435和440传递到MRU更新逻辑412。流水线锁存器435和440的使用使成员保护比特能够基本上与LRU状态信息、命中成员向量(来自锁存器416)和反MRU向量(来自锁存器422)同时到达已扩充的MRU更新逻辑412。

同样，由于成员保护比特正在通过高速缓存电路，因此将该操作的属性锁存在操作属性锁存器407处并且通过锁存器418和428将这些属性流水线式地输入到MRU更新逻辑412。在用于确定何时选择新成员(也就是不同的指令)用于保护的选择过程中利用这些属性。在一个实施例中，这些属性表明操作是否为指令获取(I获取)操作，并且对保护比特进行更新以使它们指向主管所获取的指令的成员。

下面提出的描述只有在它们影响对与本发明相关的成员保护比特的处理的地方才参考其他示例性的输入。对于本发明来说，最重要的是与受保护成员相关的信息(来自锁存器440)。

根据本发明，已扩充的MRU更新逻辑412利用年表向量的性质，该性质使得可以对年表向量同时执行多个更新操作。利用这个性质，MRU更新功能能够同时执行多个“进行MRU更新”和多个“反MRU”更新。当利用年表同时执行多个更新时，顺序向“1”编码(设置主导)(set-dominant)或“0”编码(重置主导)(reset-dominant)偏置。

图3A-图3C示出了“进行MRU/LRU”逻辑526内的电路的内部视图。特别地，图3B示出了新的一组电路输入，即“进行根MRU”，其确定根比特在“进行MRU”过程期间是否被翻转(toggle)。现在描述与产生这些输入关联的一般功能和本发明的其他特征。正如随着下面对图5A和图5B的描述而变得清楚的，只有当由命中或牺牲成员选择产生的“进行MRU”功能被触发时才触发“进行根MRU”输入。

现在转到图5A，示出了已扩充的MRU更新逻辑512的框图表示，其包括提供本发明的时间限制I-MRU保护特征所需要的附加逻辑组件。在图A中，已扩充的MRU更新逻辑512接收以下内容作为输入：(1)LRU状态向量508(表示当前LRU状态的13比特宽的输入向量)，(2)反MRU向量506(馈送给与/非门554的8比特宽的向量，该与/非门554将“进行MRU”输入馈送给“进行MRU/LRU”逻辑526)，(3)命中成员向量504(馈送给MUX 516的也是8比特的向量，下面将描述该MUX 516的功能)，以及(4)成员保护比特502(标识预先选择的要保护的成员的LRU状态比特13-15)。根据本发明，MRU更新逻辑512也接收与成员保护比特502关联的并且如下面所描述地来利用的附加计数器比特501。

除了上述输入，还示出了MRU向量550(表示删除状态成员的8比特向量)。但是，与MRU向量550关联的功能在律师存档号为AUS920041052US1的未决专利申请中描述。

已扩充的MRU更新逻辑512包括“进行MRU/LRU”逻辑526，其接收四组输入。这些输入是：(1)13比特的LRU状态向量508；(2)8比特的“进行LRU”向量558；(3)8比特的“进行MRU”向量557；以及(4)8比特的“进行根MRU”向量556。直接从阶段锁存器411接收的13比特的LRU状态向量在前面已经描述过了。每个其他输入都来自选择过程/流水线操作，包括一个或多个逻辑组件和多个到MRU更新逻辑512的上述输入的置换。例如，除了成员保护比特和D状态向量，三组输入一起进行或运算以提供单个“进行MRU”输入向量。

成员保护比特502被路由到解码模块522，该解码模块522将3比特的输入转换成8比特的向量(成员保护向量503)，每个比特表示同余类中的一个成员，其中与受保护成员对应的比特设置为逻辑1，而所有其他的比特设置为逻辑0。然后这个成员保护向量503通过“零计数”门521被路由到与/非门552。与/非门552也从锁存器422接收反MRU向量506作为输入。与/非门552反转反MRU向量，并且两个输入的组合使得可以在成员不是无效时对该成员进行MRU更新。

根据本发明的实施例，提供了附加的逻辑，其建立了用于以下操作的机制：(a)跟踪其中特定成员受保护的逐出循环的数量，和(b)触发从特定成员移除保护状态。图5A示出了第一实施例，其提供了计数器更新/重新设置路径。提供计数器值501作为LRU状态增加。例如，计数器可以包括附加的LRU状态比特16-18，表示最大计数器值8(二进制000)。将计数器值501馈送到三条路径，其中将第一条路径示出为命中路径，将第二条并行路径示出为未命中路径(带计数器减小逻辑)，以及将第三条路径示出为到期的计数器路径。当在未命中路径上传播时，计数器值减小1，与自从I-MRU成员最后一次由于命中该成员而受保护以来经过另一个逐出循环对应。命中和未命中路径是计数器更新MUX 515的输入。计数器更新MUX 515从命中确定逻辑514接收选择输入，并且该选择输入使得计数器更新MUX 515：(a)在命中发生时选择命中路径输入，以及(b)在命中未发生时选择未命中路径输入(计数器-1)。

然后，将所选择的输入传递到新的计数器确定MUX 523，其负责选择何时将当前的计数器值传递到下一个循环或产生一个具有最大计数器值的新计数器。这样，如所示出的，MUX 523从MUX 515接收计数器值的第一输入和最大计数器值的第二输入(Max_Cnt)。然后，基于命中成员是否为指令(也就是当前指令或新指令)来确定在MUX 523的输入选择。如果命中成员不是指令，则在下一个逐出循环内将来自MUX 515的减小的计数器值作为新计数器值531来传递。但是，如果命中成员是指令，则建立新的计数器，新计数器值531为最大计数器值(例如111)。

到期的计数器路径包括“计数器＝0”确定逻辑513，其估计当前计数器的值是否等于0。当该值等于零时，发送信号到MRU启动(或零计数)门521。MRU启动门521允许传递来自解码模块522的输出，该输出是同余类的8比特向量，其中一个单独的比特被标记为“进行I-MRU”。当门521从逻辑513接收信号时，门521将所有8比特翻转为0，使得没有成员被标记为“进行I-MRU”。也就是说，门521从先前标记为“进行I-MRU”的比特移除“进行I-MRU”状态。通过这种方式，使得没有成员能够在计数器到期后仍然受到I-MRU保护。

在一个实施例中，门521是与门(或成串的与门)并且接收8比特的向量作为单独的向量行。与门也从逻辑513接收信号作为第二输入。当计数器值501为非零时，逻辑513将1值作为信号发送到与门。然后，I-MRU成员(计数器行设置为1)在它的向量行与来自逻辑513的信号进行与运算时从与门接收1输出，而所有其他向量行产生零输出。但是，当计数器值501为0时，从逻辑513传递0信号，并且当与0输入信号进行与运算时I-MRU成员的向量行变为零。

现在参考图5B，示出了根据本发明的第二实施例，其中利用LFSR来提供时间限制特征用于“进行MRU”功能。通过该第二实施例，LRU状态比特13-15的000成员被偏置为从来不受保护。这样，LRU状态比特的000编码产生了“进行MRU”向量‘00000000’。使用“0行偏置”配置505来完成对000比特的偏置，通过这样做，LRU状态比特解码的“0”向量行被接地，而剩余的已解码的向量行(1-7)被作为向量行输入503提供给与/非门552。如进一步所示出的，将状态比特选择MUX 563添加到用于LRU状态比特502的输入路径。然后，MUX 563接收第二输入‘000’。对MUX 563处的输入的选择依赖于两个因素：(a)是否LFSR＝“true“(也就是说输入值为1)以及(b)是否存在命中(514)。当LFSR＝“true”并且不存在命中时，MUX 563的选择输入选择000作为LRU状态以通过MRU选择逻辑(512)传播。否则，选择输入选择LRU状态比特502。示出了一个向与/非门565提供单个输入的示例LFSR563，其也接收命中/未命中逻辑514的输出作为第二输入。如所示出的，假定输入B表明“不是命中”，也就是未命中。同样，假定LFSR默认为真值。这样，当两个条件都为真值时两个输入都提供逻辑1。

然后，将从MUX 563选择的输入传递到解码逻辑522，其在“0行偏置”配置505中将LRU状态输入解码成各自的八个向量行(比特0-7)。如所示出的，比特0的向量行被接地，使得比特0可以从来不被选择为I-MRU成员。配置505内的每个其他向量行(1-7)都被表示并被传递给与/非门552。

利用LFSR来翻转成员保护比特502的比特并使这些比特过载，以便将所选择的成员作为I-MRU成员而移除。这样，基于LFSR状态而将8比特成员保护向量503的所有比特翻转为0。当成员保护向量503经过与/非门552时没有值为1的比特，则没有成员被标识为I-MRU成员。因此，移除了先前应用于旧I-MRU的保护。

调整LFSR使得I-MRU行在预设的随机数量的逐出内受保护。在这个实施例中，利用单个LFSR为所有同余类提供时间限制MRU保护特征。特别地，图5A示出的实施例需要大量定时器/计数器，每个同余类需要一个。其他的逻辑装置可以代替LFSR或与LFSR一起利用以达到类似的取消对旧I-MRU的选择以使其不受保护。例如，一个实施例可以通过向LRU状态比特添加比特行来利用两个计数器值以及LFSR。

反MRU向量用于找到无效的高速缓存行并使它成为LRU。使高速缓存行成为LRU与用以使保护成员成为MRU的任何尝试相冲突，并且解决该冲突有利于使反转的反MRU输入取代先前受保护的成员的“默认”“进行MRU”状态。

与/非门552的0输出禁用/关闭了针对该成员的“进行MRU”功能，因此使得该成员符合条件，可通过牺牲选择成为无效成员。但是，1输出使得该成员成为MRU，表明该成员是有效的并受到保护以不受到牺牲选择。

与/非门552的输出表示或逻辑518的一个输入，该或逻辑518接收两个附加输入，即MRU向量550和来自MUX 516的输出505。MRU向量550或“删除”MRU向量在律师存档号为AUS920041052US1的相关未决专利申请中描述。对三个输入一起进行或运算以提供输入到“进行MRU/LRU”逻辑526的单个“进行MRU”向量557。

MUX 516接收命中成员向量504和选择牺牲成员向量511(来自推断牺牲成员逻辑510)作为它的输入。MUX 516也从命中确定逻辑514接收(单比特)选择输入。命中确定逻辑514表明命中何时在高速缓存内发生，其也表明命中成员向量504应当被选择为MUX 516处的输出。但是，当在高速缓存中该请求未命中并且选择了牺牲成员时，选择信号将牺牲成员向量511作为MUX 516处的输出转发。否则，当没有操作或操作中止时，输出0向量。

将MUX 516的输出路由到编码逻辑520。编码逻辑520得到8比特向量并产生与该向量对应的3比特指针(也就是，指向由在MUX 516处选择的向量标识的成员的位置)，并且提供该指针作为两个输入中的一个以保护选择MUX 524。保护选择MUX 524接收成员保护比特作为它的第二输入。选择输入528选择两个3比特输入中的一个作为MUX524的输出。选择输入528是从选择锁存器428接收的并且表明操作是否表现出了使得成员保护扩展到接收新指令的成员的特定属性。选择输入528对受保护的比特进行更新以指向分配给命中/牺牲成员的成员。

当操作的属性表明新操作是指令时(也就是，操作表现出了用于选择要受保护的成员的预定属性)，选择输入528触发选择来自编码逻辑520的输入作为来自保护选择MUX 524的输出。这个输出表示新的LRU状态比特13-15 530，并且指向要受保护的成员。否则，选择成员保护比特502(经历在成员保护向量503处可能进行的取消选择)，并且LRU状态比特13-15 530保持相同。

命中/未命中MUX 516也提供在产生“进行MRU/LRU”逻辑526的三个输入时所利用的三个输出行。第一输出是“进行根MRU”556，其是当对根比特(LRU状态比特0)进行更新时触发的8比特向量。如所示出的，“进行根MRU”556只有当在MUX 516处选择命中成员或牺牲选择向量时才接收输入向量。当两种情况都不发生时，“进行根MRU”556接收空输入并且根比特没有被更新/翻转。

来自命中/未命中MUX 516的第二输出是到或逻辑518的，在上面已经描述过该或逻辑518。通过这个输入，命中成员和/或所选择的牺牲成员成为MRU(LRU比特1-12)，其触发输入556。最后，提供第三个输出作为到第二与/非门552的输入。到与/非门552的第二输入是反MRU向量506，其选择处于I状态的成员作为要“进行LRU”的成员。与/非门554提供用作“进行MRU/LRU”逻辑526的第三个输入的“进行LRU”输出向量。因此，作为反MRU成员的成员只有在该成员也不是命中成员或所选择的牺牲成员时才成为LRU。如果反MRU成员是所选择的牺牲成员的当前命中成员，那么就取代该成员的“进行LRU”功能/操作，因为成员不能同时既是LRU又是MRU。这种取代由于所选择的牺牲成员被新的有效条目替代而发生，该新的有效条目变成MRU成员并因此不应当被标记为用于为LRU牺牲选择。

因此，来自已扩充的MRU更新逻辑512的输出包括新的LRU状态向量的所有组件。它们是LRU状态比特0、1-12 532，其表明在下一个牺牲选择过程期间哪一个成员要被选择为LRU牺牲成员，以及LRU状态比特13-15 530，其指向/表明同余类中要保护的成员(如果有的话)。在图5A中，也提供了新计数器531的第三个输出。然后，将这些输出比特路由到并存储在LRU状态阵列403中，替代LRU状态阵列403内先前的LRU状态。

本发明提供了一种“软”指令最近最常使用(I-MRU)保护方案，其中所选择的MRU成员只在有限数量的逐出循环内受保护，除非该指令高速缓存行在该期间被更新/利用。对指令的更新或访问重新启动确定高速缓存行何时不再作为I-MRU受保护的倒计时。因此，只有经常使用的指令行受保护，并且旧的I-MRU行因老化而到达高速缓存外。旧的I-MRU成员被逐出，使得同余类的所有成员可以用于数据。在一个实施例中，通过基于线性反馈移位寄存器(LFSR)而“赶出”I-MRU高速缓存行来完成I-MRU老化。调整LFSR使得I-MRU行在预设数量的逐出内受保护。因此，本发明大大减轻了由于对旧指令行的继续保护而表现出的次优性能，传统上这些旧指令行是通过I-MRU策略而受保护以不被从第二级包含性的高速缓存逐出的。

作为最后的内容，重要的是注意到，尽管已经并将继续在安装有管理软件的全功能计算机系统的上下文中描述本发明的示例性实施例，但是本领域的普通技术人员应当理解，本发明的示例性实施例的软件方面能够作为程序产品以各种形式分布，并且本发明的示例性实施例可以等同地应用，而不管用于实际执行该分布的信号承载介质的特定类型如何。信号承载介质的示例包括诸如软盘、硬盘驱动器、CD ROM之类的可记录类型的介质和诸如数字和模拟通信链路之类的传输类型的介质。

已经为了说明和描述的目的而提出了对本发明的描述，但是该描述并非旨在穷举或将本发明限制为所公开形式的形式。很多修改和变更对本领域的普通技术人员来说将是很明显的。选择和描述实施例是为了最好地说明本发明的原理、实际应用并使本领域的普通技术人员能够针对具有适合于所考虑的特定用途的各种修改的各种实施例来理解本发明。