提前运行牺牲选择以减少内含式高速缓存中不合需要的置换行为的方法和装置

摘要

公开了一种用于选择和更新高速缓存中的置换候选的方法和装置。在一个实施例中，高速缓存未命中可启动末级高速缓存中的当前置换候选的驱逐。高速缓存未命中也可启动未来置换候选的选择。在未来置换候选的选择后，对应的高速缓存线可在较低级高速缓存中被无效，但仍驻留在末级高速缓存中。未来置换候选可通过在后一高速缓存未命中前对末级高速缓存中的置换候选的随后的命中来更新。

说明书

领域

本发明公开一般涉及在高速缓存未命中时采用高速缓存线置换方法的微处理器，尤其涉及在内含式高速缓存中采用高速缓存线置换方法的微处理器。

背景

微处理器可利用多级高速缓存设计以减小存储器访问的等待时间。更接近处理器核心的高速缓存级(一级(L1)高速缓存)可具有对低等待时间的设计强调，而离处理器核心最远的高速缓存级(末级高速缓存(LLC))可具有对较大容量的设计强调。中间的高速缓存级如果存在的话则可用在低等待时间和大容量之间作出的折衷来为性能而设计。

当对高速缓存作出存储器访问(例如，读或写)时，确定所请求的存储器位置在高速缓存中是存在(高速缓存“命中”)还是不存在(高速缓存“未命中”)。如果发生未命中，则必须在高速缓存中为将从较高级高速缓存或从系统存储器加载的所请求的线留出空间。高速缓存一般具有用于确定哪一个现有的高速缓存线应被驱逐以为该新的高速缓存线留出空间的置换方法。该过程通常称为“牺牲”。置换方法可包括诸如最近最少使用(LRU)法、随机选择法和先进先出(FIFO)法之类的公知方法。这些和其它方法中的每一种都具有优点和缺点。

为了保持多处理器核心系统中的高速缓存相关性，通常执行对所请求的高速缓存线的监听。在多级高速缓存系统中，这一般意味着需要将监听消息向下传播，这从末级高速缓存开始并延向下到达L1高速缓存的所有路线继续。部分地为了减少由这些监听消息产生的等待时间，很多高速缓存被设计成内含的。内含式高速缓存维持了存在于较低级高速缓存中的任何高速缓存线同样存在于该内含式高速缓存中的这一特性。因此，在很多情况下仅需要对末级高速缓存执行监听：如果特定的高速缓存线不存在于末级高速缓存中，则按照内含特性，它也不会存在于任何较低级高速缓存中。然而，该内含特性可产生其自身的性能降低人为因素。

附图简述

在附图的各图中作为示例而不是限制示出了本发明，其中相同参考标号指的是相似的元件，附图中：

图1是根据一个实施例的包括末级高速缓存的多核处理器的示意图。

图2是根据一个实施例的高速缓存的示意图。

图3是根据一个实施例的高速缓存系统中的事件的时序图。

图4是根据本发明公开的一个实施例的用于选择置换候选的方法的流程图。

图5A和5B是根据本发明公开的两个实施例的包括具有高速缓存的处理器的系统的示意图。

详细描述

以下的描述描述了用于在多级高速缓存中的牺牲过程中所使用的改进的高速缓存线置换方法的技术。在以下的描述中，陈述了诸如逻辑实现、软件模块分配、总线和其它接口信号传输技术等众多具体细节以及操作细节以提供对本发明的更全面理解。然而，本领域的技术人员将意识到，可在没有这些具体细节的情况下实施本发明。在其它情况下，没有详细示出控制结构、门电平电路以及全部的软件指令序列，以免使本发明晦涩。本领域的普通技术人员利用所包括的描述将能够实现适当的功能而不需要过多的实验。在某些实施例中，本发明以存在于诸如由Intel^公司生产的那些Pentium^兼容处理器的多核实现中的高速缓存的形式公开。然而，可在存在于诸如Itanium^处理器族兼容处理器或X-Scale^族兼容处理器等其它类型的处理器中的高速缓存中实施本发明。

现在参考图1，根据一个实施例示出了包括末级高速缓存104的多核处理器102的示意图。在该实施例中所示的是利用两个处理器核一处理器核0112和处理器核1122-的情况。在其它实施例中，可采用单个处理器核或两个以上处理器核。通过其名称可知，末级高速缓存104一般表示这是离处理核112和122最远而最接近系统存储器140的高速缓存。然而，在某些实施例中，可有在多核处理器102和系统存储器140之间的较高高速缓存。

末级高速缓存104可被配置为单一高速缓存(数据和指令两者)或数据高速缓存。最低级高速缓存-一级(L1)数据高速缓存0110和L1数据高速缓存1120被示为在多核处理器的高速缓存分层结构中直接在末级高速缓存104之下。在其它实施例中，可有诸如二级(L2)高速缓存之类的被配置在L1数据高速缓存110、120和末级高速缓存104之间的另外的高速缓存。末级高速缓存104一般包括允许数据通过接口142在末级高速缓存104和系统存储器140之间传输的接口电路。在各实施例中，接口142可以是多点总线或点对点接口。

在某些实施例中，末级高速缓存104是内含的。内含式高速缓存是其中包含在较低级高速缓存中的任一高速缓存线也包含在该内含式高速缓存中的高速缓存。内含特性允许简化的监听以确保高速缓存相关性，因为仅需要对内含式高速缓存进行监听而不需要对任何其它较低级高速缓存进行监听，以确定特定的高速缓存线是否存在。

现在参考图2，根据一个实施例示出了高速缓存200的示意图。在某些实施例中，高速缓存200可以是图1的末级高速缓存104。在其它实施例中，高速缓存200可以是中间级高速缓存。高速缓存200被示为N路组关联高速缓存(N-way setassociative cache)。在N路组相关联高速缓存中，M组中的每一组具有用于保持高速缓存线的N个位置，称为一“路”。系统存储器中的任何特定高速缓存线可仅被加载到M组中特定的一组，但该特定的高速缓存线可被加载到该特定组的N路中的任一路。作为一种边界情况，全关联高速缓存可被认为是仅具有一组的N路组关联高速缓存。

图2示出具有M组的高速缓存200，这些组被标记为组0210到组M-1240。高速缓存200可包括高速缓存控制逻辑242，它可包括电路以与外部接口连接、响应于监听请求、在高速缓存线未命中时将请求转发给系统存储器、以及在高速缓存线命中时将高速缓存线转发给较低级高速缓存。各组中的一组，即组2218具有所示的进一步细节。所示的其它组中可具有类似的细节。连同组控制逻辑280一起示出了路0250到路N-1272。组控制逻辑可包括用于在一般作为对高速缓存的“未命中”的结果需要将新的高速缓存线添加到组2时标识置换方法的电路。该置换方法可标识哪一路包含将被新的高速缓存线覆盖的高速缓存线。该标识的高速缓存线可被称为“置换候选”。在各实施例中，置换方法可通过标识最近最少使用的高速缓存线(LRU)、通过随机地标识置换候选、或通过以组中的加载顺序(例如，先进先出(FIFO))标识置换候选来进行。所有这些置换方法可首先搜索无效的高速缓存线，并且仅在没有找到无效的高速缓存线时着手其特定的方法。在其它实施例中，可使用其它置换方法。

高速缓存为内含式的一个结果是在确定置换候选，并且允许该高速缓存线被驱逐(“牺牲”)时，则可将存在于较低级高速缓存中的所有等价高速缓存线无效。这保持了内含的特性，但成本高。出于这个原因，在较低级高速缓存中重复使用的特定高速缓存线不会经常从末级高速缓存中加载。当利用诸如LRU之类的置换方法时，这可导致该高速缓存线被选为置换候选。在当前的实施中，可将置换候选驱逐并且该高速缓存线在较低级高速缓存中被无效。在较低级高速缓存中正被积极使用的该特定高速缓存线由于需要从系统存储器中取回而将忍受等待时间惩罚。

因此，在一个实施例中，组控制逻辑可对该组的每一高速缓存未命采取若干动作。组控制逻辑可驱逐早期标识的当前置换候选的高速缓存线。组控制逻辑也可利用所采用的任何置换方法来标识未来的置换候选。在一个实施例中，组控制逻辑可使得向较低级高速缓存发出对于包含在未来置换候选中的高速缓存线的无效消息。总之，在一个实施例中，对于一组的特定高速缓存未命中导致三个动作：当前置换候选从末级高速缓存中的驱逐；未来置换候选的标识；以及未来置换候选的高速缓存线在较低级高速缓存中的无效。

在较低级高速缓存中经常使用的高速缓存线被无效为未来置换候选中的高速缓存线的情况下，可在无效发生后由相应的处理器核请求该高速缓存线。如果这在对同一高速缓存组的第二次未命中之前发生，则未来的置换候选在末级高速缓存中仍将可用。因此对于该高速缓存线将发生高速缓存命中，这对应于未来的置换候选。在这种情况下，组控制逻辑280可标识另一个未来置换候选、在较低级高速缓存中将新的未来置换候选的高速缓存线无效、并将第一未来置换候选的高速缓存线向下发送到较低级高速缓存。在对末级高速缓存的该组的第二次未命中时，组控制逻辑则可驱逐第二置换候选的高速缓存线。用第(i+1)个未来置换候选来置换第i个未来置换候选的过程可根据需要执行几次，直到对末级高速缓存的该组的第二次未命中的时候。

可以有将对于相应的高速缓存未命中的置换候选的驱逐定时的几种略微不同的方法。在一个实施例中，可在确定未命中发生时(或其后不久)进行驱逐。在其它实施例中，可延迟驱逐，直到高速缓存的填充缓冲器从较高级高速缓存或者从系统存储器接收到访问的高速缓存线的时候。

现在参考图3，根据一个实施例示出了高速缓存系统中的事件的时序图。图3的实施例示出所采用的LRU置换方法，但在其它实施例中可采用其它置换方法中的任一种。在时刻T0，发生对末级高速缓存的组X的未命中。因此，将在时刻T0具有LRU的路选为未来置换候选，且该路的高速缓存线在较低级高速缓存中被无效。

在时刻T1，发生对组X的另一个未命中，这导致从末级高速缓存中驱逐未来置换候选，即在时刻T0具有LRU的路。在同一时刻，选择一新的未来置换候选(在时刻T1具有LRU的路)，且对应于该新的未来置换候选的高速缓存线在较低级高速缓存中被无效。然而，对应于该新的未来置换候选的高速缓存线仍然驻留在末级高速缓存中。

在时刻T2，发生对未来置换候选(仍驻留在末级高速缓存中)的命中。然而仍选择了另一个新的未来置换候选择(在时刻T2具有LRU的路)，对应于该新的未来置换候选的高速缓存线在较低级高速缓存中被无效，且将在命中所请求的高速缓存线发送到较低级高速缓存。然后，在时刻T1具有LRU的较旧的未来置换候选在时刻T2在置换方法跟踪中被标记为的最近使用(MRU)。此外，对应于该新的置换候选的高速缓存线仍然驻留在末级高速缓存中。

在时刻T3，发生对未来置换候选(仍驻留在末级高速缓存中)的命中。然而仍选择了另一个新的未来置换候选(在时刻T3具有LRU的路)，对应于该新的未来置换候选的高速缓存线在较低级高速缓存线中被无效，且将命中中所请求的高速缓存线发送到较低级高速缓存。然后，在时刻T2具有LRU的较旧的未来置换候选在时刻T3在置换方法跟踪中被标记为最近使用(MRU)。此外，对应于该新的未来置换候选的高速缓存线仍然驻留在末级高速缓存中。

在时刻T4，发生对组X的另一个未命中。这导致未决的未来置换候选(在时刻T3具有LRU的路)被从末级高速缓存中驱逐。在同一时刻，选择一新的未来置换候选(在时刻T4具有LRU的路)，且对应于该新的未来置换候选的高速缓存线在较低级高速缓存中被无效。

在该示例中，在时刻T5对组X的下一个未命中前没有发生对未来置换候选的命中。这导致未决的未来置换候选(在时刻T4具有LRU的路)被从末级高速缓存中驱逐。在同一时刻，选择一新的未来置换候选(在时刻T5具有LRU的路)，且对应于该新的未来置换候选的高速缓存线在较低级高速缓存中被无效。

即使图3的示例仅示出在时刻T1和T4末级高速缓存未命中之间的对置换候选的两个命中，但对可由该实施例提供的命中的数量没有真正的限制。

现在参考图4，根据本发明公开的一个实施例示出了用于选择置换候选的方法的流程图。图4的实施例假设存在L1高速缓存和末级高速缓存。在其它实施例中，可存在末级高速缓存之下的其它级高速缓存。该过程在框410处开始。在提供了对末级高速缓存的第一次未命中后，在框412处通过置换方法来选择一置换候选，且将L1高速缓存中对应的高速缓存线无效。如果置换方法是LRU，则置换候选将是末级高速缓存的LRU的当前值。

框块414处进行存储器操作。可在框418处进行L1高速缓存查找，且在判定框420处确定是否发生对L1高速缓存的命中。如果是，则该过程经由“是”路径退出，且在框440处，更新置换方法对于L1高速缓存的状态并将用于所请求的高速缓存线的数据返回给处理器核。如果置换方法是LRU，则置换方法状态更新将是更新L1高速缓存的LRU的当前值。然后该过程回到框414。

如果在判定框420处确定未发生命中，则该过程经由“否”路径退出，并且在框422处进行末级高速缓存查找。然后在判定框428处，确定在末级高速缓存中是否发生命中。如果是，则该过程经由“是”路径退出，并在框436处更新对于末级高速缓存的置换方法状态。如果置换方法是LRU，则置换方法状态更新将是更新末级高速缓存的LRU的当前值。然后在判定框450处可确定对置换候选是否是命中。如果不是，则该过程经由“否”路径退出，且在框452处将用于所请求的高速缓存线的数据返回给L1高速缓存和处理器核。然而，如果对置换候选是命中，则该过程从判定框450经由“是”路径退出。在框456处选择一新的置换候选，且对应的高速缓存线在L1高速缓存中被无效。如果置换方法是LRU，则该置换候选将是末级高速缓存的第二最近最少使用的高速缓存线的当前值。然后在框452处将用于所请求的高速缓存线的数据返回给L1高速缓存和处理器核心。如果置换方法是LRU，则置换方法状态更新将是将末级高速缓存的第二最近最少使用的高速缓存线的当前值提升为LRU的当前值。然后在框414处开始再次重复该过程。

然而，如果在判定框428处确定在末级高速缓存中未发生命中，则该过程经由“否”路径退出判定框428。然后在框434处可采用几种动作。可支持出现在末级高速缓存填充缓冲器中的所请求的高速缓存线来驱逐置换候选的高速缓存线。可选择一新的置换候选，并且对应的高速缓存线在L1高速缓存中被无效。如果置换方法是LRU，则该置换候选将是末级高速缓存的第二最近最少使用的高速缓存线的当前值。可在框414开始再次重复该过程。

在图4所示的过程中，在框430中所讨论的末级高速缓存未命中的提供可从系统存储器启动对高速缓存线的请求。这在虚线框434中示出。置换的高速缓存线的驱逐可在该请求的启动时(或稍后)发生(在图4的实施例中)。在其它实施例中，可延迟置换候选的高速缓存线的驱逐，直到高速缓存线(对应于未命中)从存储器到达末级高速缓存的填充缓冲器。

现在参考图5A和5B，根据本发明公开的两个实施例示出了包括具有节流圈(throttle)和多个核的处理器的系统的示意图。图5A的系统一般示出其中处理器、存储器和输入/输出设备通过系统总线互相连接的系统，而图5B的系统一般示出其中处理器、存储器和输入/输出设备通过多个点对点接口来互相连接的系统。

图5A的系统可包括几个处理器，其中为了清楚起见仅示出了两个一处理器40、60。处理器40、60可包括末级高速缓存42、62。图5A的系统可具有经由总线接口44、64、12、8与系统总线6连接的几种功能。在一个实施例中，系统总线6可以是与由Intel^公司制造的Pentium^类微处理器一起使用的前端总线(FSB)。在其它实施例中，可采用其它总线。在某些实施例中，存储器控制器34和总线桥32可共同称为芯片组。在某些实施例中，芯片组的功能不同于如图5A的实施例中所示的那样可在物理芯片中分开。

存储器控制器34可允许处理器40、60从系统存储器10和基本输入/输出系统(BIOS)可擦除可编程只读存储器(EPROM)36中读或写。在某些实施例中，BIOSEPROM 36可采用闪存。存储器控制器34可包括总线接口8，以允许存储器读和写数据向系统总线6上的总线代理来回传送。存储器控制器34也可通过高性能图形接口39与高性能图形电路38连接。在某些实施例中，高性能图形接口39可以是高级图形端口AGP接口。存储器控制器34可通过高性能图形接口39将数据从系统存储器定向到高性能电路38。

图5B的系统也包括几个处理器，其中为了清楚起见仅示出了两个-处理器70、80。处理器70、80可各自包括与存储器2、4连接的逻辑存储器控制器集线器(MCH)72、82。处理器70、80也可包括末级高速缓存56、58。处理器70、80可利用点对点接口电路78、88经由点对点接口50交换数据。处理器70、80可利用点对点接口电路76、94、86、98经由各个点对点接口52、54来各自与芯片组90交换数据。芯片组90也可经由高性能图形接口92与高性能图形电路38交换数据。

在图5A的系统中，总线桥32可允许系统总线6和总线16之间的数据交换，系统总线在某些实施例中是工业标准体系结构(ISA)总线或外围部件互连(PCI)总线。在图5B的系统中，芯片组90可经由总线接口96与总线16交换数据。在任一系统中，总线16上可有各种输入/输出(I/O)设备14，在某些实施例中这些I/O设备包括低性能图形控制器、视频控制器和联网控制器。另一种总线桥18在某些实施例中可用于允许总线16和总线20之间的数据交换。总线20在某些实施例中可以是小型计算机系统接口(SCSI)总线、集成驱动电子设备(IDE)总线或通用串行总线(USB)总线。另外的I/O设备可与总线20连接。这可包括键盘和包括鼠标、音频I/O 24在内的光标控制设备22、包括调制解调器和网络接口在内的通信设备26以及数据存储设备28。软件代码可被存储在数据存储设备28上。在某些实施例中，数据存储设备28可以是固定的磁盘、软盘驱动器、光盘驱动器、磁光盘驱动器、磁带或包括闪存在内的非易失性存储器。

在上述说明中，参考其具体实施例描述了本发明。然而，显然可在不背离如所附权利要求书中所陈述的本发明的较宽的精神和范围的前提下对其进行各种修改和改变。因此，说明书和附图被认为是说明性的而不是限制性的意思。