基于时间组记录确定高速缓存组替换顺序的方法和系统

摘要

本发明涉及一种基于时间组记录确定高速缓存组替换顺序的方法和系统。提供了一种用于高速缓存的缓存管理的技术。在请求将数据元素存储在高速缓存中的指令的先前执行期间，处理电路确定未命中计数和命中位置字段。针对数据元素存储所述未命中计数和所述命中位置字段，所述数据元素与请求存储所述数据元素的指令对应。所述处理电路基于所述未命中计数和/或所述命中位置字段以分层顺序放置所述数据元素。所述命中位置字段包括所述高速缓存中与所述数据元素相关的分层位置。

说明书

技术领域

本发明涉及数据处理，更具体地说，涉及基于时间记录信息的组关联 高速缓存中的数据元素的高速缓存组（cache set）替换顺序。

背景技术

高速缓存是一种组件，它透明地保存数据元素（或简称数据）以便可 以更快地服务于对任何保存的数据的未来请求。存储在高速缓存中的数据 元素对应于计算机系统中的预定义存储位置。此类数据元素可能是最近计 算的值，或者是还存储在其它位置的同一存储单元的重复副本。如果被请 求的数据包含在高速缓存中，则这是高速缓存命中，并且可简单地通过读 取高速缓存来服务于此请求，这相对较快，因为高速缓存通常靠近其请求 者构建。否则，如果数据未包含在高速缓存中，则这是高速缓存未命中， 并且必须从不一定靠近请求者的其它存储介质取回数据，因此相对较慢。 通常，可以从高速缓存获得服务的请求数越多，整体系统性能就变得越快。

发明内容

根据各示例性实施例，提供了一种用于基于时间组记录信息确定组关 联高速缓存中的数据元素的高速缓存组替换顺序的计算机系统、方法和计 算机程序产品。确定请求在高速缓存中存储数据元素的指令的未命中计数 和命中位置字段。基于所述指令的先前执行而生成所述未命中计数和所述 命中位置字段。在高速缓存未命中期间，基于所述未命中计数和所述命中 位置字段中的至少一个，使用分层定位方案将被请求的数据元素放置（安 装）在高速缓存组位置中。在高速缓存命中期间，根据（相同的）未命中 计数和命中位置字段修改所述数据元素的组替换顺序。所述命中位置字段 定义高速缓存同余类中与所述数据元素相关的分层位置。

通过本发明的技术实现其它特性和优点。在此详细描述本发明的其它 实施例和方面，并且这些实施例和方面被视为要求保护的发明的一部分。 为了更好地理解具有所述优点和特性的本发明，将参考说明书和附图。

附图说明

在说明书结尾处的权利要求中具体指出并明确要求保护了被视为本发 明的主题。从下面结合附图的详细说明，本发明的上述和其它特性和优点 将显而易见，这些附图是：

图1示出了根据本发明的一个实施例的系统的方块图；

图2示出了根据本发明的一个实施例的存储在高速缓存目录中用于每 个同余类的缓存的数据元素的分层位置的方块图；

图3示出了根据本发明的一个实施例的按照同余类的分层位置缓存在 高速缓存中的数据元素的方块图；

图4示出了根据本发明的一个实施例的更新命中位置字段和未命中计 数器的流程图；

图5示出了根据本发明的一个实施例的继续更新命中位置字段和未命 中计数器的流程图；

图6示出了根据本发明的一个实施例的由电路对高速缓存进行缓存管 理的方法；

图7示出了具有可根据本发明的实施例使用的能力的计算机的一个实 例；

图8示出了根据本发明的一个实施例的在计算机可读/可用介质上的 计算机程序产品的一个实例。

具体实施方式

微处理器可以包含一级（L1）数据高速缓存（D高速缓存）。L1数 据高速缓存用于保存系统存储器位置子集的数据元素，以便可以处理最靠 近处理器核心的执行加载和存储的指令。在高速缓存未命中时，将对应于 被请求存储位置的数据元素安装到高速缓存中。高速缓存中的每个表项表 示对应于存储器一部分的高速缓存行。用于高速缓存的一个此类典型安装 算法基于最近最少使用（LRU）。作为一个实例，数据高速缓存可以包含 1024个行，它们被称为同余类，并且数据高速缓存可以是4路组关联高速 缓存，它具有总共4k个表项。对于每个同余类，可以跟踪最近使用的组 到最近最少使用的组的排序，作为一组用于替换的分层位置。针对4组之 一中的给定同余类将新表项安装到数据高速缓存中时，选择LRU表项以 便替换。

同时多线程（SMT）处理器允许多个线程在单个处理器核心上并行运 行。尽管LRU方案仍然可以用于D高速缓存，但SMT能力引入新的资源 共享问题，它们可以导致次优性能。例如，一个线程可以流过大量数据空 间，这将破坏高速缓存级别（例如L1高速缓存），而另一个线程可以很 好地使用高速缓存，因为它主要访问少量数据。流过程通过其连续高速缓 存抖动（cache thrashing）禁止另一个线程。换言之，为了实现最优性能， 与其它也使用高速缓存的线程相比，每个线程不应该占用多于它可以有效 使用的高速缓存。

可以进行有关从未遇到高速缓存未命中的数据访问指令及其对应指令 地址的关联。此类实例是寄存器溢出和填充。给定指令（例如，store）使 用通用寄存器内容更新或安装高速缓存，后续指令（例如，load）访问存 储在高速缓存中的内容。与store接近的load从未未命中高速缓存。还可 以进行有关始终未命中的指令的高速缓存访问的关联。换言之，始终命中 或未命中可以与指令地址关联以用于未来预测行为。然而，具有命中和未 命中组合的数据高速缓存访问的任何指令不能很容易地仅与其有关预测未 来行为的指令地址关联。

根据一个示例性实施例，通过标记始终命中或未命中数据高速缓存的 指令，可以进行这些安装（在未命中时）到D高速缓存中以及从D高速缓 存中访问（加载/存储）的操作，以便不被设置为D高速缓存目录中的MRU （最近最常使用）位置（状态）和/或靠近MRU位置（状态）。通过这种 方式，例如，处理器可以防止线程完全破坏另一个线程在D高速缓存中的 数据的缓存。破坏高速缓存的线程具有始终未命中高速缓存的访问。此类 未命中不应被安装为MRU位置，否则数据必须尽力离开高速缓存，最后 到达LRU位置以便随后被逐出。根据一个示例性实施例，如果此类数据 初始被安装为LRU并且保持LRU（如果安装），则LRU位置中的此数 据实质上在它产生的高速缓存污染量方面被限制。如果给定load（或store） 访问例如始终命中高速缓存，则当在更靠近LRU位置的位置中标记命中 组还将导致高速缓存命中时，可能不必将命中组标记为MRU。通过标记 过于靠近MRU位置的数据元素，一旦不再需要所述数据（即，数据元素）， 则所述数据驻留在数据高速缓存中的时间长于所需的时间。通过根据示例 性实施例确定的那样在更靠近LRU的位置中维护始终命中的数据元素， 这允许在高速缓存中保留另一个数据元素，此数据元素在被重新访问之前 需要在高速缓存中保存更长时间。对于将表项标记为MRU时，先前MRU 表项将被移动到第二（第2）MRU位置，便是这种情况。第二MRU表项 与LRU位置的距离现在小了一个位置，并且LRU位置是将新表项安装到 高速缓存的给定同余类中时被逐出的表项。示例性实施例被配置为在数据 高速缓存中安装和/或更新表项时确定应将表项放置在哪个位置中（例如， 从MRU位置到LRU位置以及/或者根本未安装）。此技术可以扩展为用 于微处理器中的指令高速缓存和/或其它缓存结构。

现在转到图1，总体示出了根据一个实施例的系统100的方块图。系 统100包括处理器105。处理器105具有一个或多个处理器核心，并且处 理器核心可以被称为电路10。处理器105可以包括一级（L1）高速缓存 15。尽管示出L1高速缓存，但可以根据需要在L1高速缓存和L2高速缓 存中实现示例性实施例。L1高速缓存15包括L1数据高速缓存20（D高 速缓存）和L1指令高速缓存22（I高速缓存）。数据高速缓存20是处理 器上（硬件）存储器，用于将数据缓存（即，保存）在处理器105上。可 以将从存储器110取回的数据缓存在数据高速缓存20中，而将从存储器 110取回的程序代码115的指令缓存在指令高速缓存22（例如，处理器上 （硬件）存储器）中。

L1高速缓存15可以是具有X个同余类的N-路组关联高速缓存，如本 领域的技术人员理解的那样。D高速缓存20包括D高速缓存目录24，其 可以包含同余类的每个表项（数据元素）的LRU替换顺序（相应的分层 位置）。按照同余类，单个同余类中的数据元素的替换排序可以从MRU 位置、第二MRU位置、第三MRU位置到LRU位置，如图2中所示。 MRU位置是D高速缓存20中的数据元素（表项）的最高位置，第二MRU 位置第二高，第三MRU位置第三高，LRU位置是数据元素的最低位置（假 设4-路组关联高速缓存）。数据元素（表项）是表示L1高速缓存15的D 高速缓存20中缓存的数据。

图2示出了根据一个实施例的存储在D高速缓存目录24中用于D高 速缓存20中的每个同余类的缓存数据元素的每个组的替换排序（例如，4 个分层位置）的一个实例。在图2中，出于解释目的，具有同余类1到同 余类X（相当于同余类0到X-1，如本领域的技术人员理解的），并且在 每个同余类中示出4个组。例如，假设根据图3中所示的同余类1的分层 位置，数据元素A、B、C和D是在每组D高速缓存20中缓存的表项。 通常，如果将新的数据元素E安装到D高速缓存20的同余类1中，则此 入站数据元素E将成为MRU位置，并且数据元素D将被逐出D高速缓存 中的LRU位置。随后，每个数据元素将在分层排序中向下移动一个位置， 以便从MRU位置到LRU位置的新分层排序分别是E、A、B和C。

然而，电路10的（硬件）电路12被设计为根据位于I高速缓存22中 的跟踪表26将任意数据元素（例如入站数据元素E）安装在分层位置中。 电路12被配置为根据需要此特定数据元素的关联指令（例如，fetch指令） 的过去历史来确定分层位置以安装（和/或不安装）入站数据元素，以便在 处理器核心的处理器电路10再次执行（即，看到）来自程序代码115的此 特定指令时，电路12根据跟踪表26中的已存储位置安装对应的数据元素。 在I高速缓存22的跟踪表26中维护（标记）对应的指令地址连同处理其 对应的数据元素的说明，如在此进一步讨论的那样。

电路12可以是专用集成电路（ASIC）、现场可编程门阵列（FPGA） 等。此外，在一种实施方式中，电路12的逻辑可以被实现为示出为软件应 用14的软件代码。对电路12的功能、逻辑和特性的任何引用都适用于软 件应用14，如本领域的技术人员理解的。跟踪表26可以备选地和/或附加 地作为跟踪表26a存储在存储器110中，并且对跟踪表26的功能、逻辑和 特性的任何引用都适用于跟踪表26a，如本领域的技术人员理解的。

如由电路12所控制的，跟踪表26被配置为跟踪作为与执行数据访问 的指令的关联存储在D高速缓存20中的数据元素，并且当电路10随后处 理此指令时，根据先前针对此特定指令存储的未命中计数器27和命中位置 字段29而将其对应的数据元素放置在D高速缓存目录24中的分层位置中。 电路12使用跟踪表26跟踪访问D高速缓存20中的数据元素的每个指令 （例如，来自程序代码115和/或任何其它程序）的指令地址。

例如，假设数据元素E具有关联的指令地址E（或简称指令E）。第 一次在D高速缓存20中缓存数据元素E（并且在I高速缓存22中缓存指 令E）时，电路12被配置为在跟踪表26中跟踪指令E和数据元素E。在 此第一轮中，数据元素E排序在D高速缓存目录24的MRU位置中（与 正常情况一样）。对应于指令E的数据访问的未命中计数器27从零（0） 开始，并且例如在三（3）处饱和/结束，其中在此实例中3是阈值未命中 计数。任何高于3的高速缓存未命中都将超过该阈值，如在此讨论的那样。 对于指令E的数据访问的每次对D高速缓存20的高速缓存未命中，未命 中计数器27都将递增一（1），直至未命中计数器达到3。此时，未命中 计数器27不再进一步递增1。当存在对D高速缓存20的高速缓存命中时， 电路12将未命中计数器27递减1，直至达到0，并且不会递减到0以下。 如果在存储指令E访问的数据之后将其它入站数据元素存储在D高速缓存 20的同一同余类中，则LRU位置中的数据元素将被逐出D高速缓存20， 并且剩余的数据元素将在分层位置中向下移动一个位置。

通常，对于每次对D高速缓存20（中的数据元素E）的高速缓存命中， 数据元素E都将被移动到MRU位置中（如果数据元素E先前在分层结构 中向下移动），但数据元素E的移动不能高于MRU位置。

在电路10初始处理指令E的第一情况中，假设未命中计数器27达到 其最大值，例如阈值3。当电路12确定未命中计数器27达到其最大值3 时，未命中计数器27不会递增到其最大值3以上，而是在3处饱和。响应 于指令E访问的数据的高速缓存未命中（达到最大值3），电路12被配置 为识别到指令E使其对应的数据元素（始终）在LRU位置中安装和维护 以便指令E的后续处理（基于指令E的未命中计数器27达到3）。指令E 的后续处理指随后处理指令E，其中指令E访问要再次缓存在D高速缓存 20中的数据元素E。在LRU位置中维护数据元素E意味着电路12被配置 为（在指令E的跟踪表26中）确定和维护如下标记：指令E访问的数据 元素E随后要被放置在LRU位置中（当随后处理指令E时）并且不会向 上移动到D高速缓存目录24的MRU位置，即使当针对数据元素E发生 高速缓存命中时也是如此。不同于典型的高速缓存管理，电路12将指令E 的数据元素E锁定以免向上移动到任何分层位置（即使针对高速缓存命中 也是如此），直至数据元素E最后由入站数据元素逐出D高速缓存20。 可选地，在此类情况下，当未命中计数器27饱和（超过其阈值）时，电路 12可以被配置为针对指令E根本不在D高速缓存20中安装数据元素E。 要指出的是，如在此讨论的那样，高速缓存管理基于针对先前处理的每个 指令（例如在各种情况中讨论的指令E）存储在跟踪表26中的未命中计数 器27和命中位置字段29。

在指令E访问数据元素E的第二情况中，未命中计数器27未达到其 最大值（例如，未设置未命中计数器27），并且数据元素E最终会被逐出 D高速缓存20。电路12被配置为在命中位置字段29（对应于指令E）中 标明/标记（例如，设置适当的位）最靠近LRU位置的分层位置（包括LRU 位置本身），在该分层位置，数据元素E在被逐出之前具有高速缓存命中。 下面将提供四个实例情况。

在第一情况中，当在MRU位置中针对D高速缓存20中的数据元素E 出现最低高速缓存命中分层位置时，电路12将在指令E的命中位置字段 29中存储/标记MRU位置。当电路12随后再次处理指令E时，电路12 将检查指令E的命中位置字段29。如果命中位置字段29中的标记是MRU 位置，则在指令E的后续处理中，电路12在高速缓存未命中时将新表项 （相同或不同的数据元素E）安装到LRU位置中，因为数据元素E（仅） 需要D高速缓存20中的一个组。假设在D高速缓存20中针对数据元素E 发生高速缓存命中。通常，针对没有此公开的特性的高速缓存命中，数据 元素E将成为MRU位置。然而，在具有此公开的特性的情况下，针对高 速缓存命中，使得数据元素E如根据命中位置字段29允许的那样靠近 MRU位置，并且在上述情况中，针对高速缓存命中，使得数据元素E成 为LRU位置。根据指令E的命中分层位置字段29，此表项的移动将从不 高于（原始）安装分层位置。这将通过使必须等待的时间长于数据元素E 被逐出L1高速缓存所需的时间而防止污染L1高速缓存15。

在第二情况中，当在4路组关联高速缓存的第2MRU位置中针对D 高速缓存20中的数据元素E出现最低高速缓存命中分层位置时，电路12 将在指令E的命中位置字段29中存储/标记第2MRU位置。当电路12随 后再次处理指令E时，电路12将检查指令E的命中位置字段29。如果命 中位置字段29中的标记是第2MRU位置，则电路12在高速缓存未命中 时将新表项（相同或不同的数据元素E）安装到第3MRU（也称为第2 LRU）位置中，因为此表项（仅）需要两个组。假设在D高速缓存20中 针对数据元素E发生高速缓存命中。通常，针对高速缓存命中，数据元素 E将成为MRU位置。然而，针对高速缓存命中，使得数据元素E如根据 命中位置字段29允许的那样靠近MRU位置，并且在上述情况中，针对高 速缓存命中，（通过电路12）使得数据元素E成为第3MRU位置。

在第三情况中，当在第3MRU位置中针对D高速缓存20中的数据元 素E出现最低高速缓存命中分层位置（在MRU和第2MRU位置中可能 具有先前的高速缓存命中）时，电路12将在指令E的命中位置字段29中 存储/标记第3MRU位置。当电路12随后再次处理指令E时，电路12将 检查指令E的命中位置字段29。如果命中位置字段29中的标记是第3 MRU位置，则电路12在高速缓存未命中时将新表项（相同或不同的数据 元素E）安装到第2MRU位置中，因为此表项需要三个组。假设在D高 速缓存20中针对数据元素E发生高速缓存命中。通常，针对高速缓存命 中，数据元素E将成为MRU位置。然而，针对高速缓存命中，使得数据 元素E如根据命中位置字段29允许的那样靠近MRU位置，并且在上述 情况中，针对高速缓存命中，使得数据元素E成为第2MRU位置。

在第四情况中，当在LRU位置中针对D高速缓存20中的数据元素E 出现最低高速缓存命中分层位置（在其它访问中，可能在较高位置中存在 其它高速缓存命中）时，电路12将在指令E的命中位置字段29中存储/ 标记LRU位置。当电路12随后再次处理指令E时，电路12将检查指令 E的命中位置字段29。如果命中位置字段29中的标记是LRU位置，则电 路12将此表项安装到MRU位置中，因为新表项（相同或不同的数据元素 E）使用D高速缓存中的所有4个组。假设在D高速缓存20中针对数据 元素E发生高速缓存命中。对于高速缓存命中，使得数据元素E如根据命 中位置字段29允许的那样靠近MRU位置，并且在上述情况中，针对高速 缓存命中，使得数据元素E成为MRU位置。

对于命中位置字段29，一旦所述数据元素到达在该处出现最低高速缓 存命中分层位置的标记位置（当初始处理所述指令时确定），电路12将从 被标记位置（本身）一直回到MRU位置进行计数。计数的数量（X）是 此特定数据元素需要多少个组（分层位置）。为了查找安装分层位置，（电 路12）使用此数量（X）从LRU位置（本身作为1组）直到MRU位置进 行计数，并且计数停止（数量X）的分层位置是所述数据元素的安装位置。 命中分层位置字段29中的标记位置和安装分层位置之间存在反向关系。

为了进一步解释未命中计数器27操作和命中位置字段29操作之间的 差异，电路12被配置为运行D高速缓存20以便未命中计数器27优先于 命中位置字段29。当初始处理指令E时，假设未命中计数27达到（指令 E的）阈值，并且假设在命中位置字段29中标记数据元素E的最低高速 缓存命中位置（例如，MRU位置、第2MRU位置、第3MRU位置或LRU 位置）。在指令E的后续处理中，电路12被配置为（通过检查跟踪表26 以获得对应于指令E的标记/位）确定未命中计数器27达到阈值并且设置 了命中位置字段29。电路12被配置为确定未命中计数器27操作超越命中 位置字段29操作，以便应用对应于未命中计数器27的操作（即，在LRU 位置中安装和维护，直至将指令E访问的任何数据元素逐出D高速缓存 20，或者不在D高速缓存20中安装），而不是对应于命中位置字段29的 操作。

尽管在图1中示出了单个未命中计数器27和命中位置字段29，但未 命中计数器27和命中位置字段29表示多个未命中计数器27和命中位置字 段29，它们均对应于例如程序代码115和/或其它可执行程序代码的单独 指令（数据访问指令的指令地址）。尽管跟踪表26被示为在I高速缓存 22中，但可以在其它任何位置（按照处理器）维护跟踪表26，如本领域的 技术人员理解的那样。此外，可以以各种方式维护和构造跟踪表26，如本 领域的技术人员理解的那样，其中包括将指令地址作为预定义散列的函数， 将跟踪表作为组关联查找表进行维护等。

此外，要指出的是，电路12处理的每个指令被标记/存储以便在跟踪 表26中具有它自己的相应未命中计数器27和命中位置字段29。在此方面， 电路12随后可以检查跟踪表26以便了解针对I高速缓存22中的每个相应 指令的指令命中或未命中，并且当存在指令命中时，根据未命中计数器27 （如果满足阈值）和命中位置字段29（如果没有高速缓存命中，则其可以 为空）处理此指令的相应数据元素。先前处理的每个指令被绑定到它自己 的未命中计数器27和命中位置字段29以便应用于此指令的后续处理场合。

在一种实施方式中，未命中计数器27可以是两位（或者更多位，如果 需要），而命中位置字段29可以是两位。可以设置未命中计数器27的位 以便对相应指令遇到的D高速缓存未命中进行计数。电路12被配置为针 对每个指令识别何时达到未命中计数阈值。当针对所述指令尚未达到未命 中计数器27的未命中计数阈值时，与未命中计数器27相关的电路12在所 述指令的后续处理中将不会采取任何对应操作。当未命中计数达到未命中 计数阈值时，电路12将识别此情况并采取适当的未命中计数器27操作（例 如，在LRU位置中维护数据元素和/或不安装所述数据元素），如在此讨 论的那样。此外，可以设置命中位置字段29的位以便表示D高速缓存目 录24中的每个分层顺序（从MRU位置到LRU位置），并且根据相应指 令的命中位置字段存储特定分层顺序。根据此处的讨论，将理解可以使用 各种技术表示未命中计数器27和命中位置字段29的特性和功能，如本领 域的技术人员理解的那样。

使用参考指令E及其数据元素E的各种实例情况是为了进行解释，而 不是限制。根据本公开，电路12被配置为如在此讨论的那样同时或几乎同 时处理多个指令及其相应的数据元素。

处理器105可以是同时多线程（SMT）处理器，它允许多个线程在单 个处理器核心（例如，电路10）上并行运行。当（电路12）跟踪给定指令 访问遇到的最靠近LRU位置的分层位置时，可以将此指令作为维护单个 分层顺序的所有线程跟踪，或者可以根据每个线程执行跟踪。当使用更多 区域时，根据线程跟踪的优势在于知晓给定线程需要多少个组，因此最大 程度地减少了解其它线程的干扰。例如，参考图3，假设线程1具有数据 元素A和B，线程2具有数据元素C和D。不是将所述组作为一个整体进 行查看，而是可以将电路12配置为仅根据线程查看与位置相关的分层排 序，然后应用未命中计数器27和命中位置字段29，如在此讨论的那样。 例如，在每个线程的基础上，电路12被配置为针对线程2将数据元素C 视为MRU位置并将数据元素D视为第2MRU位置，然后类似地针对线 程2指令应用未命中计数器27和命中位置字段29。同样，电路12被配置 为考虑MRU位置中的数据元素A和第二MRU中的数据元素B，然后类 似地针对线程1指令应用未命中计数器27和命中位置字段29，如在此讨 论的那样。

例如，在应用SMT并且不修改算法时，线程1可以在此通道上始终 命中为（特定同余类的分层结构中的所有位置的）MRU和第2MRU位置。 在基于线程2执行的内容的未来代码通道上，线程1的数据可能不会作为 给定同余类中基于线程2执行/访问的内容的两个最近访问的表项之一提 供（作为第3MRU安装，因为它初始仅使用前两个位置）。

第一次安装（跟踪表26中没有信息）时，将表项安装到D高速缓存 20中并成为MRU，如上面描述的那样。以不同方式跟踪最差位置（最靠 近LRU位置）的计算。如果这是给定同余类中来自此线程的唯一表项（例 如，所有其它表项都来自另一个线程），则此表项可以被视为MRU和LRU 两者（线程中仅有一个表项，因此分配一个位置，从而MRU=LRU）。此 表项然后将被表示为命中（给定线程的）LRU位置，以便在未来安装时， 将它安装到（整个同余类的）MRU位置中。如果此线程具有两个表项（将 这两个表项称为A和B），并且在表项“A”和“B”之中“A”始终是 MRU，则“A”是MRU，“B”的最差访问位置是LRU位置（相当于此 线程的排序）。因此，“A”距离（此线程的排序的）LRU为一个位置。 因此，在跟踪表26中将（此线程的）表项“A”作为“第3MRU”跟踪 （其距整体同余类的LRU为一个位置），以便在未来安装时将“A”安装 到第2MRU位置中。从另一个线程而言，这将提供安全性，因为另一个 线程可能朝向LRU将此线程的表项“A”推动两个位置，并且“A”将在 D高速缓存中保持为分层结构的LRU位置。

现在转到图4，其中示出了根据一个示例性实施例的用于更新命中位 置字段29和未命中计数器27的流程图400。此外，流程图400示出了针 对应用命中位置字段29时D高速缓存20如何运行。

假设处理器105的电路10处理请求数据元素E的指令E以请求数据 元素E。在方块405，处理器105的电路12判定在D高速缓存20中针对 数据元素E是否存在D高速缓存命中。如果否，针对数据元素E没有D 高速缓存命中，则所述流程离开此页继续到图5中的方块505。如果是， 针对数据元素E存在D高速缓存命中，则在方块410，电路12判定在I 高速缓存22的跟踪表26中是否存在产生（发出）D高速缓存请求的指令 命中。如果否，I高速缓存22的跟踪表26中没有指令命中（即，此特定 指令（例如，指令E）没有标记的未命中计数器27和/或命中位置字段29）， 则在方块415，电路12被配置为在D高速缓存命中时根据分层位置（例如， MRU位置到LRU位置）设置命中位置字段29，并且将未命中计数器27 设置为0。跟踪表26中没有指令命中意味着此特定指令（例如，指令E） 先前未被处理以便具有未命中计数器27和命中位置字段29，或者已从跟 踪表26中删除此特定指令（例如，指令E）。

如果是，针对此特定指令（例如，指令E）在跟踪表26中存在指令命 中，则在方块420，电路12被配置为将D高速缓存表项（数据元素E）布 置/放置为尽可能靠近MRU位置而不超过命中位置字段29的功能。例如， 如果针对指令E将命中位置字段29设置为第2MRU位置，则电路12被 配置为将对应的数据元素E（由指令E的指令地址取回）布置/放置到D 高速缓存20的D高速缓存目录24中的第3MRU位置（如上面讨论的那 样）。

在方块425，电路12被配置为检查对应数据元素（例如，数据元素E） 在作为MRU位置安装时是否被设置为比针对相应指令（例如，指令E） 在跟踪表26中记录的位置更靠近LRU位置。如果是，则在方块430，电 路12被配置为在未命中计数器27中递减所述指令的未命中计数，并且将 命中位置字段29更新到当前分层位置。例如，如果初始作为MRU位置安 装并且随后被参考/标记为与第2MRU位置一样低，则在未来安装由指令 E访问的数据元素E时，数据元素E将作为第3MRU（也称为第2LRU） 位置安装。如果否，则在方块435，电路12被配置为在未命中计数器27 中递减所述指令的未命中计数，并且允许针对所述指令（例如，指令E） 按原样保持命中位置字段29。

现在转到图5，其中示出了根据一个实施例的继续图4中的流程图400 的流程图500。在方块505，如果存在D高速缓存未命中（即，在方块405 没有D高速缓存命中），则电路12被配置为判定在I高速缓存22的跟踪 表26中针对产生（发出）D高速缓存请求的指令E是否具有指令命中。 如果否，针对发出D高速缓存请求的指令E没有指令命中，则在方块510， 电路12被配置为通过针对此指令E将命中位置设置为MRU位置并且将 未命中计数器27的未命中计数设置为1，来将此特定指令（例如，指令E） 安装到跟踪表26中。

如果是，针对指令E在跟踪表26中存在指令命中，则在方块515，电 路12被配置为检查针对指令E是否应该发生ε处理（epsilon handling）。 如果对方块515的回答为否，针对所述指令没有ε处理，则在方块520， 电路12被配置为在未命中计数器27中递增所述指令的未命中计数，并且 根据命中位置字段29中的命中位置将对应的数据元素（例如，数据元素E） 安装在D高速缓存20中。

为了考虑过程变化性，针对ε处理具有ε因子。ε定义小的时间百分 比，其中电路12忽略存储在跟踪表26中的安装空间描述符（未命中计数 器27和命中位置字段29）并且将给定表项安装到MRU位置中。通过允 许将此类表项安装到MRU位置中，如果程序代码115（具有指令E）的 行为随时间改变并且由于安装距离MRU位置太远而错过潜在命中，则这 将允许处理器105的电路12更正/调整新的代码行为。因此，当对方块515 的回答为是时，针对此指令启动ε处理（例如，基于处理所述指令达预定 次数和/或在经过预定时段后），则在方块525，电路12被配置为将对应 的数据元素（例如，数据元素E）安装到D高速缓存20的MRU位置中， 将命中位置字段29设置为MRU位置，并且在未命中计数器27中递增所 述指令的未命中计数（同时忽略针对未命中计数器27和命中位置字段29 设置的先前数据/操作）。

图6示出了根据一个实施例的用于由电路12对D高速缓存20进行高 速缓存管理的方法600。要指出的是，尽管出于解释目的将电路12标识为 执行某些功能（例如，通过电线与硬件组件连接以便执行，如在此讨论的 那样），但电路12是电路10（形成处理器核心的硬件）的一部分。有关 电路12的任何讨论都适用于电路10，它们均形成处理器105（处理电路）。

在方块605，电路12被配置为在请求将数据元素（例如，数据元素E） 存储在高速缓存（例如，D高速缓存20）中的指令（例如，指令E）的先 前处理期间确定未命中计数器27中的未命中计数和命中位置字段29。针 对请求所述数据元素的指令存储未命中计数器27的未命中计数和命中位 置字段29。未命中计数器27和/或命中位置字段29可以同时设置，也可 以不同时设置。先前处理指较早时间，其中电路12处理所述指令以便在所 述指令的跟踪表26中存储/更新未命中计数器27数据和/或命中位置字段 29数据。

电路12被配置为在所述指令的后续处理期间基于（未命中计数器27 的）未命中计数和命中位置字段29中的至少一个以（D高速缓存目录24 的）分层顺序放置/安装所述数据元素。在方块610，命中位置字段29包 括与位于高速缓存（例如，D高速缓存20）中的同余类内的数据元素（例 如，数据元素E）相关的分层位置。

在方块615，响应于未设置未命中计数，电路12被配置为根据命中位 置字段29中存储的分层位置以所述分层顺序安装/放置所述数据元素。电 路12根据存储在命中位置字段29中的所述分层位置的反向关系以所述分 层顺序放置所述数据元素，并且响应于高速缓存命中，电路12防止所述数 据元素以所述分层顺序的移动高于所述分层位置的反向关系。

此外，响应于未命中计数器27的未命中计数和命中位置字段29之间 的冲突，电路12被配置为根据未命中计数处理所述指令（例如，设置位以 指示达到未命中计数器27的阈值）。根据未命中计数处理所述指令包括将 所述数据元素放置在所述高速缓存中的最近最少使用（LRU）位置中（当 定义为操作模式时）和/或不在所述高速缓存中安装所述数据元素（当定义 为操作模式时）。

命中位置字段29中的分层位置指示在所述指令的先前执行期间，与最 近最少使用（LRU）位置最接近并且其中针对所述数据元素发生高速缓存 命中的位置。电路12通过确定针对D高速缓存20中的数据元素发生高速 缓存命中的所述分层顺序中的最低位置，在请求将所述数据元素存储在高 速缓存中的指令的先前处理期间，确定未命中计数器27的未命中计数和命 中位置字段29；因此，电路12将所确定的发生所述高速缓存命中的最低 分层位置作为所述分层位置存储在命中位置字段29中（例如，设置对应的 位）。

针对指令地址执行指令取回以获得指令（例如，指令E）。此指令可 以触发对D高速缓存20的数据访问（针对数据元素E）。

图7示出了可以包括在示例性实施例中的具有各种能力的计算机700 的一个实例。在此讨论的各种方法、程序、模块、流程图、工具、应用、 电路、元件和技术也可以结合和/或使用计算机700的能力。此外，可以使 用计算机700的能力实现在此讨论的示例性实施例的功能。可以使用计算 机700的一个或多个能力实现此处在图1-6和8中讨论的任何元件、连接 到这些元件和/或支持这些元件（如本领域的技术人员理解的那样）。

通常，在硬件架构方面，计算机700可以包括一个或多个处理器710、 计算机可读存储器720，以及一个或多个输入和/或输出（I/O）设备770， 它们通过本地接口（未示出）在通信上耦合。所述本地接口例如可以是（但 不限于）一条或多条总线或其它有线或无线连接，如本领域公知的那样。 所述本地接口可以具有其它元件，例如控制器、缓冲器（高速缓存）、驱 动器、中继器和接收器以实现通信。此外，所述本地接口可以包括地址、 控制和/或数据连接以便在上述组件之间实现适当的通信。

处理器710是用于执行可以存储在存储器720中的软件的硬件设备。 处理器710可以是几乎任何定制或商用处理器、中央处理单元（CPU）、 数字信号处理器（DSP），或者是与计算机700关联的多个处理器之间的 辅助处理器，并且处理器710可以是基于半导体的微处理器（以微芯片形 式）或宏处理器。

计算机可读存储器720可以包括易失性存储元件（例如，随机存取存 储器（RAM），例如动态随机存取存储器（DRAM）、静态随机存取存储 器（SRAM）等）和非易失性存储元件（例如，ROM、可擦写可编程只读 存储器（EPROM）、电可擦写可编程只读存储器（EEPROM）、可编程 只读存储器（PROM）、磁带、光盘只读存储器（CD-ROM）、磁盘、软 盘、盒带、卡带等）的任何一个或其组合。此外，存储器720可以包括电、 磁、光和/或其它类型的存储介质。要指出的是，存储器720可以具有分布 式架构，其中各种组件可以彼此远离，但可以由处理器710访问。

计算机可读存储器720中的软件可以包括一个或多个单独程序，每个 程序包括用于实现逻辑功能的可执行指令的有序列表。存储器720中的软 件包括适合的操作系统（O/S）750、编译器740、源代码730，以及示例 性实施例的一个或多个应用760。如示出的那样，应用760包括多个功能 组件，用于实现示例性实施例的特性、过程、方法、功能和操作。计算机 700的应用760可以表示多个应用、代理、软件组件、模块、接口、控制 器等，如在此讨论的那样，但应用760并非意味着限制。

操作系统750可以控制其它计算机程序的执行，并且提供调度、输入- 输出控制、文件和数据管理、存储器管理以及通信控制和相关服务。

应用（多个）760可以采用面向服务的架构，其可以是彼此通信的服 务的集合。此外，所述面向服务的架构允许两个或更多服务协调和/或执行 活动（例如，代表彼此）。服务之间的每个交互可以是自包含且松散耦合 的，以便每个交互独立于任何其它交互。

此外，应用760可以是源程序、可执行程序（目标代码）、脚本，或 者是包括一组要执行的指令的任何其它实体。如果为源程序，则所述程序 通常通过编译器（例如编译器740）、汇编器、解释器等被转换，这些组 件可以包括在存储器720中，也可以不包括在存储器720中，以便结合 O/S750正确运行。此外，应用760可以被编写为（a）面向对象的编程语 言，其具有数据类和方法，或者（b）过程编程语言，其具有例程、子例 程和/或函数。

I/O设备770可以包括输入设备（或外围设备），例如但不限于鼠标、 键盘、扫描仪、麦克风、照相机等。此外，I/O设备770还可以包括输出 设备（或外围设备），例如但不限于打印机、显示器等。最后，I/O设备 770可以进一步包括传送输入和输出的设备，例如但不限于NIC或调制器 /解调器（用于访问远程设备、其它文件、设备、系统或网络）、射频（RF） 或其它收发器、电话接口、桥接器、路由器等。I/O设备770还包括用于 通过各种网络（例如因特网或内联网）通信的组件。I/O设备770可以使 用蓝牙连接和电缆连接到处理器710和/或与处理器710通信（例如，通过 通用串行总线（USB）端口、串行端口、并行端口、FireWire、HDMI（高 清晰度多媒体接口）等）。

当计算机700操作时，处理器710被配置为执行存储在存储器720中 的软件，以便将数据传送到存储器720并从存储器720中传送数据，并且 通常根据所述软件控制计算机700的操作。应用760和O/S750由处理器 710全部或部分读取，可能在处理器710中被缓冲，然后被执行。

当应用760以软件实现时，应指出，应用760可以存储在几乎任何计 算机可读存储介质中，以便由任何计算机相关系统或方法使用或与任何计 算机相关系统或方法结合。在本文档的上下文中，计算机可读存储介质可 以是能够包含或存储由计算机相关系统或方法使用或与计算机相关系统或 方法结合的电、磁、光或其它物理设备或装置。

应用760可以包含在任何计算机可读介质720中，以便由指令执行系 统、装置、服务器或设备（例如基于计算机的系统、处理器包含系统，或 者其它能够从指令执行系统、装置或设备取回指令并执行指令的系统）使 用或与指令执行系统、装置、服务器或设备结合。在本文档的上下文中， “计算机可读存储介质”可以是任何能够存储、读取、写入、传送或传输 由指令执行系统、装置或设备使用或与指令执行系统、装置或设备结合的 程序的装置。所述计算机可读介质例如可以是（但不限于）电、磁、光或 半导体系统、装置或设备。

计算机可读介质720的更具体的实例（非穷举的列表）将包括以下项： 具有一条或多条线的电连接（电）、便携式计算机软盘（磁或光）、随机 存取存储器（RAM）（电）、只读存储器（ROM）（电）、可擦写可编 程只读存储器（EPROM、EEPROM或闪存）（电）、光纤（光）和便携 式光盘只读存储器（CDROM、CD R/W）（光）。

在示例性实施例中，如果应用760以硬件实现，则应用760可以使用 以下技术的任何一种或组合实现，每种技术都是本领域公知的：具有用于 针对数字信号实现逻辑功能的逻辑门的分离逻辑电路（多个）、具有适当 的组合逻辑门的专用集成电路（ASIC）、可编程门阵列（多个）（PGA）、 现场可编程门阵列（FPGA）等。

将理解，计算机700包括可以包含在此处讨论的各种设备、服务器和 系统中的软件和硬件组件的非限制性实例，并且将理解，在示例性实施例 中，所讨论的各种设备和系统中可以包括其它软件和硬件组件。

如上面描述的那样，各实施例可以以计算机实现的过程以及用于实现 这些过程的装置的形式体现。一个实施例可以包括计算机程序产品800， 如图8中所示，在具有计算机程序代码逻辑804的计算机可读/可用介质 802中包含指令，所述指令在有形介质中体现为制品。计算机可读/可用介 质802的示例性制品可以包括软盘、CD-ROM、硬盘驱动器、通用串行总 线（USB）闪存驱动器或任何其它计算机可读存储介质，其中当计算机程 序代码逻辑804被加载到计算机并由计算机执行时，所述计算机变成用于 实现本发明的装置。各实施例包括计算机程序代码逻辑804，例如无论存 储在存储介质中，加载到计算机和/或由计算机执行，还是通过某种传输介 质传输（例如通过电线或电缆、通过光纤或通过电磁辐射），其中当计算 机程序代码逻辑804被加载到计算机并由计算机执行时，所述计算机变成 用于实现本发明的装置。当在通用微处理器上实现时，计算机程序代码逻 辑804段配置所述微处理器以产生特定逻辑电路。

如本领域的技术人员将理解的，本发明的各方面可以体现为系统、方 法或计算机程序产品。因此，本发明的各方面可以采取完全硬件实施例、 完全软件实施例（包括固件、驻留软件、微代码等）或组合了软件和硬件 方面的实施例的形式，本文一般称为“电路”、“模块”或“系统”。此 外，本发明的各方面可以采取体现在任何有形的表达介质（在介质中包含 计算机可用程序代码）中的计算机程序产品的形式。

可以使用一个或多个计算机可读介质的任意组合。所述计算机可读介 质可以是计算机可读信号介质或计算机可读存储介质。计算机可读存储介 质例如可以是（但不限于）电、磁、光、电磁、红外线或半导体系统、装 置或设备或上述任意适合的组合。所述计算机可读存储介质的更具体的实 例（非穷举列表）将包括以下项：具有一条或多条线的电连接、便携式计 算机软盘、硬盘、随机存取存储器（RAM）、只读存储器（ROM）、可 擦写可编程只读存储器（EPROM或闪存）、光纤、便携式光盘只读存储 器（CD-ROM）、光存储设备、磁存储设备或上述任意适合的组合。在本 文档的上下文中，计算机可读存储介质可以是任何能够包含或存储由指令 执行系统、装置或设备使用或与指令执行系统、装置或设备结合的程序的 有形介质。

计算机可读信号介质可以包括其中包含计算机可读程序代码（例如， 在基带中或作为载波的一部分）的传播数据信号。此类传播信号可以采取 各种形式中的任一种，包括但不限于电磁、光或其中任意适合的组合。计 算机可读信号介质可以是任何不属于计算机可读存储介质并且能够传送、 传播或传输由指令执行系统、装置或设备使用或与指令执行系统、装置或 设备结合的程序的计算机可读介质。

可以使用任何适当的介质（包括但不限于无线、线缆、光缆、RF等 或上述任意适合的组合）来传输包含在计算机可读介质中的程序代码。

用于执行本发明的各方面的操作的计算机程序代码可以使用包含一种 或多种编程语言的任意组合来编写，所述编程语言包括诸如Java、 Smalltalk、C++之类的面向对象的编程语言以及诸如“C”编程语言或类 似的编程语言之类的常规过程编程语言。所述程序代码可以完全地在用户 计算机上执行、部分地在用户计算机上执行、作为独立的软件包、部分地 在用户计算机上并部分地在远程计算机上执行，或者完全地在远程计算机 或服务器上执行。在后者的情况中，所述远程计算机可以通过包括局域网 （LAN）或广域网（WAN）的任何类型网络与用户的计算机相连，或者 可以与外部计算机进行连接（例如，使用因特网服务提供商通过因特网连 接）。

在此将参考根据本发明的实施例的方法、装置（系统）和计算机程序 产品的流程图和/或方块图对本发明的各方面进行描述。将理解，所述流程 图和/或方块图的每个方块以及所述流程图和/或方块图中的方块的组合可 以由计算机程序指令来实现。这些计算机程序指令可以被提供给通用计算 机、专用计算机或其它可编程数据处理装置的处理器以产生机器，以便通 过所述计算机或其它可编程数据处理装置的处理器执行的所述指令产生用 于实现在一个或多个流程图和/或方块图方块中指定的功能/操作的装置。

这些计算机程序指令也可以被存储在能够引导计算机、其它可编程数 据处理装置或其它设备以特定方式执行功能的计算机可读介质中，以便存 储在所述计算机可读介质中的所述指令产生一件包括实现在一个或多个流 程图和/或方块图方块中指定的功能/操作的指令的制品。

所述计算机程序指令还可被加载到计算机、其它可编程数据处理装置 或其它设备，以导致在所述计算机、其它可编程装置或其它设备上执行一 系列操作步骤以产生计算机实现的过程，从而在所述计算机或其它可编程 装置上执行的所述指令提供用于实现在一个或多个流程图和/或方块图方 块中指定的功能/操作的过程。

附图中的流程图和方块图示出了根据本发明的各种实施例的系统、方 法和计算机程序产品的可能实施方式的架构、功能和操作。在此方面，所 述流程图或方块图中的每个方块都可以表示代码的模块、段或部分，所述 代码包括用于实现指定的逻辑功能（多个）的一个或多个可执行指令。还 应指出，在某些备选实施方式中，在方块中说明的功能可以不按图中说明 的顺序发生。例如，示为连续的两个方块可以实际上被基本同时地执行， 或者某些时候，取决于所涉及的功能，可以以相反的顺序执行所述方块。 还将指出，所述方块图和/或流程图的每个方块以及所述方块图和/或流程 图中的方块的组合可以由执行指定功能或操作的基于专用硬件的系统或专 用硬件和计算机指令的组合来实现。

在此使用的术语只是为了描述特定的实施例并且并非旨在作为本发明 的限制。如在此所使用的，单数形式“一”、“一个”和“该”旨在同样 包括复数形式，除非上下文明确地另有所指。还将理解，当在此说明书中 使用时，术语“包括”和/或“包含”指定了声明的特性、整数、步骤、操 作、元素和/或组件的存在，但是并不排除一个或多个其它特性、整数、步 骤、操作、元素、组件和/或其组的存在或增加。

以下的权利要求中的对应结构、材料、操作以及所有功能性限定的装 置或步骤的等同替换，旨在包括任何用于与在权利要求中具体指出的其它 单元相组合地执行该功能的结构、材料或操作。所给出的对本发明的描述 其目的在于示意和描述，并非是穷尽性的，也并非是要将本发明限定到所 表述的形式。对于本领域技术人员来说，在不偏离本发明范围和精神的情 况下，显然可以作出许多修改和变型。对实施例的选择和说明，是为了最 好地解释本发明的原理和实际应用，使本领域技术人员能够明了，本发明 可以有适合所要的特定用途的具有各种改变的各种实施方式。

在此示出的流程图只是一个实例。其中描述的示意图或步骤（或操作） 可以存在许多变化而不偏离本发明的精神。例如，可以以不同的顺序执行 所述步骤，或者可以添加、删除或修改步骤。所有这些变化都被视为要求 保护的发明的一部分。

尽管描述了本发明的优选实施例，但本领域的技术人员将理解的是， 可以在现在和将来进行各种落入以下权利要求的范围内的改进和增强。这 些权利要求应被理解为维护对最初描述的本发明的正确保护。