用于处理器的高关联性高速缓存的第二次机会取代机制

摘要

本发明揭露一种高速缓存系统，其包含高速缓存(269、16A、17A、18A)和块取代控制器(266)。该高速缓存可以包含多个集合，每一个集合均包含多个块储存位置。该块取代控制器可以维护对应于该高速缓存中每一个集合的个别计数值。该个别计数值指向该给定集合内储存取代数据的合适块储存位置。该块取代控制器可针对该块储存位置中至少一些中之每一个维护相关联之最近存取位，该最近存取位指示是否该对应之块储存位置最近被存取。此外，该块取代控制器可以根据是否有特定之最近存取位指示该合适之块储存位置最近被存取，而储存该取代数据于被该个别计数值所指向之该合适之块储存位置内。

说明书

技术领域

本发明所揭示系关于微处理器缓存(cache)，更详言之，系关于缓存数据取代机制。

背景技术

由于计算机系统之主存储器设计系以密度为主要考虑而非速度，因此，微处理器设计者使他们的设计具有额外之缓存，以减少该微处理器对直接存取主存储器之需求。缓存系一种具有较主存储器更快之存取速度之小内存。缓存传统上系由快速之内存单元所构成，如：静态随机存取内存(SRAM)，相较于使用作主存储器之该内存(传统上系动态随机存取内存(DRAM)或同步动态随机存取内存(SDRAM))具有较快之存取时间和频宽。

先进之微处理器传统上包含芯片上(on-chip)高速缓存。于许多案例中，微处理器包含芯片上阶层式(hierarchical)缓存结构，阶层式缓存结构可能包含层次1(L1)、层次2(L2)和于某些案例中具有之层次3(L3)高速缓存。传统缓存阶层可以使用小且快速之L1缓存，该L1缓存可用以储存该最频繁使用之缓存线(cache line)。该L2缓存可以系较大且可能较慢之缓存，用以储存被频繁存取但不适合于L1之缓存线。该L3缓存可较该L2缓存更大且被用以储存被频繁存取但不适合于L2之缓存线。具有如上所述之缓存阶层可以藉由减少延迟(latency)来改善处理器效能，其中该延迟系关联于内存被处理器核心所存取。

于传统缓存设计中，任何给定之数据块(block of data)仅可被置放于一些小数目之实体位置的其中之一，称作集合(一般称作集合关联缓存(set associative cache))。每一个集合中之该最大块数系与该缓存的关联性(associativity)。一旦给定集合系被存满(full)，每一次新的数据必须被纳入该集合时，则已存在之项目必须被该新的数据所溢写(overwritten)或取代。某些形式之算法必须被用以决定于取代之过程中那一个已存在之项目将被溢写。取代演算中的一种形式系为该最近最少使用(least recently used，LRU)算法。于该LRU算法中，每一个集合中所有之项目之时间顺序均被追踪，并且如该名称所暗示，该最近最少使用之项目系被取代。这个算法于该关联性很小的情况下可以运作得很好。对于较高之关联性，持续追踪该LRU位置系变得复杂且该排序信息(ordering information)需要相当数量之储存空间。

发明内容

许多用于处理器高速缓存系统的高关联性高速缓存的第二次机会取代机制之实施例系被揭露。于一个实施例中，该高速缓存系统包含连接至块取代控制器之高速缓存。该高速缓存可包含多个集合，每一个集合均包含多个块储存位置。该块取代控制器可以用以维护对应于该高速缓存中每一个集合的个别计数值(separate count value)。对应于给定集合的该计数值指向该给定集合内储存取代数据的合适之块储存位置或块储存位置群组(group)。该块取代控制器可针对该块储存位置的至少一些中之每一个维护相关联之最近存取位，该最近存取位指示是否该对应之块储存位置最近被存取。此外，该块取代控制器可以根据是否对应于合适之块储存位置的特定最近存取位指示该合适之块储存位置最近被存取，而将该取代数据储存于该合适之块储存位置中被该个别计数值所指向之一者内。

于一个具体实现中，该块取代控制器可储存该取代数据于被该个别计数值所指向之合适之块储存位置内，以响应对应于该储存位置的该特定最近存取位，其中该特定最近存取位指出该储存位置最近未被存取。

于另一个具体实现中，该块取代控制器可禁止储存该取代信号于被该个别计数值所指向之合适之块储存位置内，以响应对应于该合适之储存位置的该特定最近存取位，其中该特定最近存取位指出该合适之块储存位置最近被存取。

附图说明

藉由参考附加图示使所属技术领域中具有通常知识者对本发明可有较佳的了解，且明了其许多特色与优点。

图1系包含多核心处理节点之计算机系统之一个实施例之块图；

图2系图标图1之高速缓存的实施例中较详细态样之块图；

图3系描述图2之该高速缓存的一个实施例中该操作之流程图；

图4系图标图1之高速缓存的另一个实施例中较详细态样之块图；

图5系描述图4之该高速缓存的一个实施例中该操作之流程图；

虽然本发明可容易作各种之修饰和替代形式，但是在此系由图式中之范例显示及详细说明本发明之特定实施例。然而，应暸解到此处特定实施例之图式及详细说明并不欲用来限制本发明为所揭示之特定形式，反之，本发明将涵盖所有落于如所附申请专利范围内所界定之本发明之精神和范围内之修饰、等效和替代内容。请注意该字句”may”系以宽松之意义被贯穿地使用于本发明(也就是，有可能的、可以的)，而不是强制之意义(也就是，必须)。

具体实施方式

现在转到图1，计算机系统10之一个实施例之块图系被图示于图1。于该图标之实施例中，该计算机系统10包含连接至内存14和周边装置13A-13B之处理节点12(processing node)。该节点12包含连接至节点控制器20之处理器核心15A-15B、多个HyperTransportTM(HT)接口电路24A-24C以及共享之层次3(shared L3)高速缓存60，其中，该节点控制器20系进一步连接至内存控制器22。该HT电路24C系连接至该周边装置13A，该周边装置13A又以菊环式组构(daisy-chainconfiguration)连接至该周边装置13B，于本实施例中系使用HT接口。该剩下之HT电路24A-24B可经由其它HT接口(未显示)而被连接至其它类似之处理节点(未显示)。该内存控制器22系连接至该内存14。于一个实施例中，节点12可系单一个集成电路芯片(integrated circuitchip)，该集成电路芯片包括显示于图1中之该电路系统(circuitry)。也就是说，节点12可为芯片多重处理器(chip multiprocessor，CMP)。任何层次之整合的(integrated)或离散的(discrete)组件均可被使用。此处提到处理节点12可包含许多其它为了简化而省略之电路。

于许多实施例中，节点控制器20也可包含许多种内连接(interconnection)电路(未显示)，其中该内连接电路系用于将处理器核心15A和15B彼此内连接、内连接至其它节点、以及内连接至内存。节点控制器20也可包含选择和控制许多节点特性之功能，如：该节点之该最大和最小操作频率，以及例如该节点之最大和最小电源供应电压。该节点控制器20一般可用以于该处理器核心15A-15B、该内存控制器22以及该HT电路24A-24C之间进行路由通讯(route communications)，视该通讯形式和该通讯之地址...等而定。于一个实施例中，该节点控制器20可以包含系统要求储列(system request queue，SRQ；未显示)，其中该节点控制器20系将接收之通讯(received communications)写入该系统要求储列。该节点控制器20可排程来自该SRQ之通讯以路由该通讯至该处理核心15A-15B、该HT电路24A-24C以及该内存控制器22之间之一个目标或数个目标。

一般而言，该处理器核心15A-15B可利用通往该节点控制器20之该接口与该计算机系统10之其它组件(例如：周边装置13A-13B、其它处理器核心(未显示)、该内存控制器22...等)通讯。该接口可被设计以任何想要之型态。于一些实施例中，缓存一致通讯可对于该接口而被定义。于一个实施例中，于该节点控制器20和该处理器核心15A-15B之间的该接口上之通讯系为封包之形式，类似用于该HT接口上者。于其它实施例中，任何想要之通讯方式均可被使用(例如，总线接口上之交换(transaction)，不同形式之封包...等)。于其它实施例中，该处理器核心15A-15B可共享通往该节点控制器20之接口(例如，共享之总线接口)。一般而言，来自于该处理器核心15A-15B之该通讯可包含要求(request)，诸如：读取操作(读取内存位置或该处理器核心外部之缓存器)、写入操作(写入内存位置或外部之缓存器)、响应探测(response toprobe)(对于缓存一致实施例)、中断确认(interrupt acknowledgement)以及系统管理讯息...等。

如以上所述，该内存14可包含任何适合之内存装置。例如，该内存14可包括该动态随机存取内存(DRAM)家族(诸如：RAMBUSDRAM(RDRAM)、同步DRAM(synchronous DRAM，SDRAM)和双倍数据传送率SDRAM(double data rate SDRAM))中一个或多个随机存取内存(RAM)。内存14可被称作为计算机可读取媒体(computer readablemedium)，其中该可读取媒体可储存程序指令(program instruction)。该内存控制器22可包括与该内存14介接之控制电路系统。此外，该内存控制器22可包含要求储列，该要求储列系用以排队(queuing)内存要求...等。

该HT电路24A-24C可包括多种缓冲器(buffer)及用以自HT连结(HT link)接收封包和在HT连结上传送封包之控制电路。该HT接口包括用以传送封包之单向连结(unidirectional link)。每一个HT电路24A-24C均可被连接至两个这样的连结(一个用于传送而一个用于接收)。给定之HT接口可以被操作于缓存一致型态(cache coherentfashion)(例如，介于处理节点之间)或被操作于非一致型态(non-coherentfashion)(例如，通往/来自周边装置16A-16B)。于该图标之实施例中，该HT电路24A-24B系并未被使用，而该HT电路24C系经由非一致性连结被连接至该周边装置16A-16B。

此处提到，虽然该目前之实施例使用该HT接口作为节点之间和节点与周边装置之间的通讯，但其它实施例可使用任何想要之接口或任何一种通讯接口。举例而言，其它以封包为基础之接口可被使用，总线接口可被使用，许多标准周边接口可被使用(例如，周边组件内连接(peripheral component interconnect，PCI)和PCI express...等)。

该周边装置13A-13B可为任何形式之周边装置。例如，该周边装置13A-13B可包含与另一个计算机系统通讯之装置，其中该装置系连接至该另一个计算机系统(例如，网络适配卡、整合于计算机系统主电路板上类似网络适配卡之电路系统，或调制解调器)。再者，该周边装置13A-13B可包含视讯加速器(video accelerator)、声卡(audio card)、硬式或软式磁盘驱动器或磁盘控制器、小型计算机系统接口(SmallComputer Systems Interface，SCSI)转接器、电话通讯卡(telephony card)、声效卡(sound card)以及多种数据撷取卡(data acquisition card)诸如：通用接口总线(GPIB)或场总线适配卡(field bus interface card)。此处提到该名称”周边装置”系意指包含输入/输出(I/O)装置。

一般而言，处理器核心15A-15B可包含被设计用以执行指令之电路系统，该指令系定义于给定之指令集合结构(instruction setarchitecture)中。也就是说，该处理器核心电路系统可用以取得(fetch)、译码(decode)、执行(execute)以及储存(store)该指令之结果，该指令系定义于该指令集合结构中。例如，于一个实施例中，处理器核心15A-15B可以该X86结构来实现。该处理器核心15A-15B可包括任何想要之组构，包含：超管路(superpipelined)、超纯量(superscalar)或两者之结合。其它组构可包含纯量(scalar)、管路(pipelined)、非管路(non-pipelined)...等。许多实施例可使用乱序预测执行(out of order speculative execution)或顺序执行(in order execution)。该处理器核心可包含用于一个或多个指令或其它功能之微编码(microcoding)，以与以上任何一种架构相结合。许多实施例可以实现许多其它设计特征，诸如：缓存、变换后备缓冲区(translation look-aside buffer，TLB)...等。因此，于该图示之实施例中，除了被两个处理器核心所共享之该L3缓存60之外，处理器核心15A包含L1缓存系统16A、L2缓存系统17A和TLB 18A。同样地，处理器核心15B包含L1缓存系统16B、L2缓存系统17B和变换后备缓冲区18B。该L1和L2缓存各自可代表任何于微处理器中发现之L1和L2缓存。另外，该处理节点12包含共享之L3缓存60，其中该L3缓存60系L3缓存次系统30(cache subsystem)之一部份。于该图示之实施例中，该L3缓存次系统30包含缓存控制器单元21(如所示，系节点控制器20之一部份)和该L3缓存60。缓存控制器21可用以控制被指向该L3缓存60之要求。

如以下将详加描述者，一个或多个该缓存和(或)TLB结构可实现取代机制，其中取代控制器可维护数据储存阵列中每一个块储存位置的最近被存取/被使用位(recently accessed/used bit)。另外，该取代控制器可维护计数值以依次地指向每一个块储存位置。当每一个合适之储存位置均被查看以决定是否储存取代数据，该最近被存取/被使用(RU)位可指示是否该对应之块储存位置最近被存取过。因此，该块取代控制器可根据是否该RU位指示该位置最近被存取过，而将该取代数据储存于该计数值所指向之该块储存位置。

亦应注意的是，虽然图1中所示之该计算机系统10包含一个处理节点12，但其它实施例可实现任意数目之处理节点。类似地，于许多实施例中，处理节点(如：节点12)可包含任意数目之处理器核心。许多该计算机系统10之实施例也可以于每一个节点12上包含不同数目之HT接口和不同数目之周边装置16(系连接至该节点)...等。

请参照图2，系显示图1中高速缓存系统实施例更详细之态样之块图。该高速缓存系统200(有时又被称作高速缓存)包含卷标控制262(tagcontrol)、块取代控制器266、最近最少使用(LRU)储存阵列264、卷标储存阵列263和数据储存阵列265。

该卷标储存阵列263可用以储存一些地址位(如：卷标)于多个位置中的每一个，该地址位系储存于该数据储存阵列265内之数据的缓存线之地址位。于一个实施例中，该标签控制262可以用以搜寻该卷标储存阵列263进而决定是否被要求之缓存线系出现在该数据储存阵列265。例如，标签控制262可决定是否有一个或多个关联于读取要求之地址位(address bit)系与储存于该卷标储存阵列263之内之任何地址卷标(address tag)匹配。如果该卷标控制262与被要求之地址匹配，则该卷标控制262可回复命中指示(hit indication)给该缓存控制器21，而如果在该卷标阵列263中没有发现匹配者则回复落空指示(missindication)。

于该图标实施例中，该数据储存阵列265包含多个块储存位置(如：269)。如图所示，数据储存阵列265具有编号由0至m-1之m列(row)，以及编号由0至n-1之n行(column)。于此实施例中，该数据储存阵列265实现了包含n路关联性(n ways of associativity)之集合关联高速缓存(set associative cache memory)。该路(way)系由该行所代表，而该集合由该列所代表。例如，如果该高速缓存系16路之集合关联缓存，则n将是16，而每一个集合将包含16个提供储存数据块之块储存位置。传统上，数据块可为缓存线。该集合的数目可视该高速缓存的尺寸而定。

该LRU储存阵列264包含多个储存位置。于图标之实施例中，该LRU储存阵列264包含相当于该数据储存阵列265中该列和行之列和行，其中该列系代表该集合。于该LRU储存阵列264中标记为”ru”之该储存位置中，该块取代控制器266可维护该数据储存阵列265中每一个块储存位置的最近被存取/被使用(RU)位。每一个RU位均指示是否该数据储存阵列中该对应之位置最近被存取。如同此处所使用，被存取/被使用系指操作，在该操作中，该数据储存阵列内之块储存位置系由于对该块储存位置中该数据的缓存要求而被读取或写入或是被存取。

除了RU位之外，该块取代控制器266可以于该LRU储存阵列264中每一个列之内维护计数值。例如，如图2所示，每一个列中该参考编号C0、C1、C2和C3代表四位计数值。该计数值代表指针(pointer)，指向数据储存阵列265中该对应之列内个别之块储存位置，其中该计数值可实现16路之集合关联缓存。因此，所示之该计数值系四位数值。如果该路数(the number of way)不同，则该计数值可具有不同之位数。于该图示实施例中，对应于给定集合的该计数值亦代表指标，指向该LRU储存阵列264中该相关联之RU位。

应注意的是在一个实施例中，当RU位系空的(clear)，则可指示块储存位置最近系未被存取。也就是说，当该RU位系位于逻辑0数值。同样地，当RU位系被设定的(set)，则可指示块储存位置最近系被存取。也就是说，当该RU位系位于逻辑1数值。然而，同样可预期该逻辑数值可被颠倒(reversed)以致于RU位可指示出块储存位置最近系未被存取，当RU位系被设定的或位于逻辑1数值；而RU位可指示出块储存位置最近系被存取，当RU位系空的或位于逻辑0数值。

如下所详述并同时参照图3之叙述，块取代控制器266可以用以储存取代数据于数据储存阵列265内，如果该计数值指向具有指示该块储存位置最近系未被存取之对应RU位之块储存位置。另外，如同此实施例中所使用之最近被存取(recently accessed)系指自从该计数值最后一次指向此块储存位置的”被存取/被使用”。

应注意的是，该取代机制可被使用于任何形式之缓存，该缓存系使用取代算法。例如，上述该高速缓存系统200可为L1缓存、L2缓存或L3缓存的代表。再者，也有其它型式之高速缓存于处理器的微结构(micro-architecture)内。例如，许多处理器使用习知之储存(如变换后备缓冲区(TLB))以储存虚拟或线性地址至实体地址转换。这些形式之储存也可以大部分相同于传统缓存的方式使用取代算法。如此，可预期上述该取代机制也可被使用于这些形式之缓存。

图3系描述图2中该高速缓存系统200之该实施例之该运作之流程图。共同参照图2和图3，于块300内，于一个实施例中，该块取代控制器266造成所有RU位指示最近未被存取。此情况可藉由例如：重置(reset)，来完成。为响应缓存存取请求(诸如对给定之块储存位置的读取要求)(例如：块305)，块取代控制器266设定对应于该被存取之块储存位置的该RU位(块310)。此操作可于每一次块储存位置被存取时发生。

当该数据储存阵列265系存满有效之数据，任何额外之数据填入都将有数据被取代。因此，为响应取代要求(块315)，块取代控制器266检查对应于该块储存位置的该RU位，其中该块储存位置系被该集合中之该计数值所指出，而该集合系被该要求之该地址所指示(块320)。如果该RU位系空的(于此例中)，指示出该位置最近系未被存取(块325)，该块取代控制器266取代该块储存位置中该数据，其中该块储存位置系被该集合中之该计数值所指出，而该集合系被该要求之该地址所指示(块330)，并且该块取代控制器266设定该对应之RU位(指示最近系被存取)。操作则如上述之块305来进行。

回头参照块325，如果该RU位系被设定的(is set)，指示该位置最近系被存取，则该块取代控制器266清空(clear)目前被该计数值所指向之该RU位(指示最近系未被存取)，并且增加该计数值以指向该集合中该下一个合适之块储存位置(块340)。该块取代控制器266可接着检查该下一个RU位，以查看是否该下一个RU位系空的或被设定的。如上所述，如果该RU位系被设定的，指示该下一个位置最近系被存取，则该块取代控制器266清空目前被该计数值所指向之该RU位(指示最近未被存取)，并增加该计数值以指向该集合中该下一个块储存位置。此操作将持续直到该块取代控制器发现RU位系空的，于此案例中操作将如以上块330中所述般被进行。因此，虽然不太可能，但所有该RU位可能于一个取代周期内被清空。

上述该等实施例对可以于该计数器依次的传递之间被存取之任何块提供被取代前的第二次机会。

请参照图4，所示为图标出高速缓存系统400之另一个实施例之更详细态样之块图。高速缓存系统400类似于图2之高速缓存200，但是具有一些操作上的差异。详而言之，视该实现之方式而定，不必要对于该数据储存阵列265中每一个块储存位置均维护RU位。如下所述，该总计之最近使用信息(包含该计数器和RU位两者)系维持在每个块储存位置一个位。

于图4所示之实施例中，该高速缓存系统400(有时系被称作高速缓存)包含卷标控制262、块取代控制器466、最近最少使用(LRU)储存阵列464、卷标储存阵列263以及数据储存阵列265。如图4所示，该数据储存阵列265包含多个块储存位置(如：269)，并且实现包括某路数关联性之集合关联缓存。因此，该LRU储存阵列464也包含多个储存位置。于一个实施例中，该块取代控制器466可针对该数据储存阵列265中每一个集合维护计数值。如此，该LRU储存阵列464也包含对应于该数据储存阵列265中该列和该行之列和行，其中该列代表该集合。于一个实施例中，该块取代控制器466可将每一个计数值储存于该LRU储存阵列464之列内。例如，如图4所示，每一个列中之该参考编号C0、C1、C2和C3系代表四位计数值。该计数值代表指向该数据储存阵列265内之个别块储存位置的指针。

然而，与图2所示之该实施例相比，图4中该块取代控制器466仅针对该数据储存阵列265中一部份该块储存位置维护最近被存取/被使用(RU)位。于该图示之实施例中，为了减少LRU阵列464内之LRU信息所需之储存，该计数值系储存于该等RU位间。因此，RU位之该数目可为n-log2n，其中n系关联性之路数(number of ways ofassociativity)。例如，于16路之缓存中，将有12个RU位和四位之计数值。于此案例中，最近已被该指针忽略之该RU位可被看作系逻辑0，所以这些位不需要储存。另外，根据RU位与该计数器之相对位置(position)而不是根据绝对之路数(absolute way number)来储存该RU位系有用的。例如，该块取代控制器466可储存LRU阵列464内之该计数值，以致于该第一RU位储存位置(在对应于任何的块储存位置的该计数值储存之后)系被该计数值所指向。因此，例如：如果该计数值系6，储存于行4之该RU位将对应于路数6之块储存位置，而不是如图2所示之实施例中该RU位所对应之路数4。

如以上与图4中所描述者，每次该计数值增加，则LRU储存阵列464中特定列内之该RU位系被向左移位(shifted left)一个位位置。因为该RU位中任何一个或全部均有可能于取代要求当时成为那一个被左移之位，所以似乎需要一个移位器(shifter)，该移位器具有和每一个列之该RU位数目一样多之路数。然而，该移位器所需要之尺寸可藉由数字因子”k”来减少，藉由在增加该计数器之前等待该最初k个RU位被设定并且仅以k之倍数增加。于此案例中，被用于任何给定之取代之该路(way)将不必要系该计数值所指向之该路，但可为自该计数值到计数值+k-1之该路中任何一个，该路之RU位指示最近未被存取/被使用。例如，于该图示实施例中，该计数值可以4之倍数(k＝4)增加。于此案例中，该计数值中该2个最低有效位(least significant bit)将总是逻辑0，所以该2个最低有效位不需要储存。此方式所节省之该储存空间可以被用以储存额外之RU位。因此，于此例中，每个集合中该16位LRU储存将被分配为两位计数值加上14个RU位。

于一个实施例中，每一个RU位均指示是否该数据储存阵列265中对应之块储存位置最近被存取。如同此处所使用，被存取/被使用系指操作，在该操作中，该数据储存阵列内之块储存位置系由于对该块储存位置中该数据的缓存要求而被读取或写入或是被存取。

应注意的是在一个实施例中，当RU位系空的，该RU位可指示块储存位置最近系未被存取。也就是说，当该RU位系位于逻辑0数值。同样地，当RU位系被设定的，该RU位可指示块储存位置最近系被存取。也就是说，当该RU位系位于逻辑1数值。然而，同样可预期该逻辑数值可被颠倒以致于RU位可指示出块储存位置最近系未被存取，当RU位系被设定的或位于逻辑1数值；而RU位可指示出块储存位置最近系被存取，当RU位系空的或位于逻辑0数值。

图5系描述图4中所示之该实施例之操作细节之流程图，如同该先前段落所修改者。共同参照图4和图5，于图5之块500中，该块取代控制器466造成所有RU位指示最近未被存取。此情况可藉由例如：重置，来完成。为响应缓存存取请求(诸如对给定之块储存位置的读取要求)，例如(块505)，块取代控制器466设定对应于该被存取之块储存位置的该RU位，如果于该要求时存在这样的位(块510)。此操作可于每一次块储存位置被存取时发生。

当该数据储存阵列265系存满有效之数据，任何额外之数据填入都将有数据被取代。因此，为响应取代要求(块515)，块取代控制器466检查对应于该块储存位置的该RU位以及对该集合的该下面三个RU位，其中该块储存位置系被该集合中之该计数值所指向，而该集合系被该要求之该地址所指示(块520)。如果此四个RU位中任何一个系空的，指示该位置系未被存取(块525)，则该块取代控制器466取代该块储存位置中该数据，其中该块储存位置对应于四个RU位中该第一个空的RU位(块530)，并且该块取代控制器466设定此位以指示最近系被存取。操作则如上述之块505来进行。

回头参照块525，如果该四个被检验之RU位全部均被设定，指示该等位置最近系被存取，则该块取代控制器466将所有对于该列之该RU位往左移位四个位位置，于右手端填0(zero-fill)(指示最近未被存取)，并且将计数值增加4以指向该接下来包含该集合中四个块储存位置的合适群组(块540)。该块取代控制器466可接着检查该接下来具有四个RU位之群组，以查看是否其中任何一个系空的。如上所述，如果该四个RU位全部系被设定的，指示该等位置最近系被存取，则该块取代控制器466将所有对于该列之该RU位往左移位四个位位置，并填0(指示最近未被存取)，并且将计数值增加4以指向该接下来包含该集合中四个块储存位置的合适群组。此操作将持续直到该块取代控制器发现RU位系空的，于此案例中操作将如以上块530中所述般被进行。因此，虽然不太可能，但所有该RU位可能于一个取代周期内被清空。

应注意的是，于另一实施例中，每当该第一组四个位(first four bit)被发现系被设定，则该块取代控制器466可用以移位/清空(shift/clear)该对于给定之列之四个RU位，而无须等待该下一个取代要求。于此案例中，当取代要求到达时，已经确认第一组四个群组中至少一个RU位系空的。

应注意的是，虽然于一些实施例中未显示，但有效之位/信息可被储存于该卷标阵列263或个别之储存阵列。如此，具有无效数据的块储存位置可以在具有有效之数据前一直被用以储存取代之数据(replacement data)。因此，当接收到缓存要求时，当正在决定储存取代数据至那一个位置时，该有效之信息可优先于该RU信息而被检查。

复应注意的是，虽然上述实施例中包含具有多重处理器核心之节点，可预期的是关联于缓存系统200和400之该功能可被用于任何形式之处理器，包含单一核心处理器。另外，虽然该实施例已经以硬件的关点被描述，但可预期的是该实施例可被实现于硬件、软件或软件之结合。于以软件实现之实施例中，该程序指令可被储存于例如图1之内存14内，并如所期望的被15A和15B所执行。然而，可预期的是该程序指令可被储存于任何形式之储存媒体中。

虽然该以上之实施例已被尽可能地详细描述，但以上所揭露的内容一旦理解后，许多的变化及修改对于该技术领域中熟习技术者将变得很明显。接下来的申请专利范围打算以涵盖所有这种变化与修改之方式来加以解读。

产业利用性

本发明一般可应用于微处理器。