在内容感知预取器中识别候选虚拟地址的方法和装置

1.一种用于识别高速缓存线中的虚拟地址的方法，包括：
接收高速缓存线，所述高速缓存线包括处理单元所请求的数据；
从所述高速缓存线获取有效地址；
从所述高速缓存线读取具有地址大小的字，所述高速缓存线包括多个 具有地址大小的字；
将所述具有地址大小的字的高N位与所述高速缓存线的所述有效地址 的高N位相比较；以及
如果所述具有地址大小的字的所述高N位与所述有效地址的所述高N 位相匹配，则将所述具有地址大小的字识别为候选虚拟地址，并且生成对 于所述候选虚拟地址的预取请求。
2.如权利要求1所述的方法，还包括如果所述具有地址大小的字的所 述高N位与所述有效地址的所述高N位不匹配，则丢弃所述具有地址大小 的字。
3.如权利要求1所述的方法，其中所述高N位包括从8个到12个 位。
4.如权利要求1所述的方法，其中所述高速缓存线是存储器对齐的， 所述方法还包括如果所述具有地址大小的字的K个最低有效位中的任何一 个是非零的，则丢弃所述具有地址大小的字。
5.如权利要求4所述的方法，其中所述高速缓存线是2字节对齐、4 字节对齐、8字节对齐和16字节对齐中的一种。
6.如权利要求4所述的方法，其中所述K个最低有效位包含从1个到 4个位。
7.如权利要求1所述的方法，还包括：
如果所述有效地址的所述高N位的每个都是为零的位，则检查所述具 有地址大小的字的所述高N位之后的M个过滤位；以及
如果所述M个过滤位中的一个是非零的位，则将所述具有地址大小的 字识别为候选虚拟地址。
8.如权利要求7所述的方法，还包括如果所述M个过滤位的每个都是 为零的位，则丢弃所述具有地址大小的字。
9.如权利要求7所述的方法，其中所述M个过滤位包含从1个到4个 位。
10.如权利要求1所述的方法，还包括：
如果所述有效地址的所述高N位的每个都是为1的位，则检查所述具 有地址大小的字的所述高N位之后的M个过滤位；以及
如果所述M个过滤位中的一个是非1的位，则将所述具有地址大小的 字识别为候选虚拟地址。
11.如权利要求10所述的方法，还包括如果所述M个过滤位的每个都 是为1的位，则丢弃所述具有地址大小的字。
12.如权利要求10所述的方法，其中所述M个过滤位包含从1个到4 个位。
13.一种能够识别高速缓存线中的虚拟地址的设备，包括：
高速缓存存储器，所述高速缓存存储器接收处理单元所请求的填充内 容，所述填充内容包括高速缓存线；
与所述高速缓存存储器相耦合的内容预取器，所述内容预取器包括：
用于接收所述高速缓存线的拷贝的装置，
用于从所述高速缓存线获取有效地址的装置，
用于从所述高速缓存线读取具有地址大小的字的装置，所述高速 缓存线包括多个具有地址大小的字，
用于将所述具有地址大小的字的高N位与所述高速缓存线的所述 有效地址的高N位相比较的装置，以及
用于如果所述具有地址大小的字的所述高N位与所述有效地址的 所述高N位相匹配，则将所述具有地址大小的字识别为候选虚拟地 址，并且生成对于所述候选虚拟地址的预取请求的装置。
14.如权利要求13所述的设备，其中所述内容预取器包括用于如果所 述具有地址大小的字的所述高N位与所述有效地址的所述高N位不匹配， 则丢弃所述具有地址大小的字的装置。
15.如权利要求13所述的设备，其中所述高N位包括从8个到12个 位。
16.如权利要求13所述的设备，其中所述高速缓存线是存储器对齐 的，所述内容预取器包括如果所述具有地址大小的字的K个最低有效位中 的任何一个是非零的，则丢弃所述具有地址大小的字的装置。
17.如权利要求16所述的设备，其中所述高速缓存线是2字节对齐、 4字节对齐、8字节对齐和16字节对齐中的一种。
18.如权利要求16所述的设备，其中所述K个最低有效位包含从1个 到4个位。
19.如权利要求13所述的设备，其中所述内容预取器包括：
用于如果所述有效地址的所述高N位的每个都是为零的位，则检查所 述具有地址大小的字的所述高N位之后的M个过滤位的装置；以及
用于如果所述M个过滤位中的一个是非零的位，则将所述具有地址大 小的字识别为候选虚拟地址的装置。
20.如权利要求19所述的设备，其中所述内容预取器包括如果所述M 个过滤位的每个都是为零的位，则丢弃所述具有地址大小的字的装置。
21.如权利要求19所述的设备，其中所述M个过滤位包含从1个到4 个位。
22.如权利要求13所述的设备，其中所述内容预取器包括：
用于如果所述有效地址的所述高N位的每个都是为1的位，则检查所 述具有地址大小的字的所述高N位之后的M个过滤位的装置；以及
用于如果所述M个过滤位中的一个是非1的位，则将所述具有地址大 小的字识别为候选虚拟地址的装置。
23.如权利要求22所述的设备，其中所述内容预取器包括如果所述M 个过滤位的每个都是为1的位，则丢弃所述具有地址大小的字的装置。
24.如权利要求22所述的设备，其中所述M个过滤位包含从1个到4 个位。
25.一种用于识别高速缓存线中的虚拟地址的方法，包括：
从存储器对齐的高速缓存线获取有效地址；
从所述存储器对齐的高速缓存线读取具有地址大小的字；
如果所述具有地址大小的字的K个最低有效位中的任何一个是非零 的，则丢弃所述具有地址大小的字；
将所述具有地址大小的字的高N位与所述高速缓存线的所述有效地址 的高N位相比较；以及
如果所述具有地址大小的字的所述高N位与所述有效地址的所述高N 位相匹配，则将所述具有地址大小的字识别为候选虚拟地址。
26.如权利要求25所述的方法，还包括如果所述具有地址大小的字的 所述高N位与所述有效地址的所述高N位不匹配，则丢弃所述具有地址大 小的字。
27.如权利要求25所述的方法，其中所述高N位包含从8个到12个 位。
28.如权利要求25所述的方法，其中所述存储器对齐的高速缓存线是 2字节对齐、4字节对齐、8字节对齐和16字节对齐中的一种。
29.如权利要求25所述的方法，其中所述K个最低有效位包含从1个 到4个位。

技术领域
本发明一般地涉及处理器，更具体地说，涉及用于内容感知预取的方 法和装置。
背景技术
传统处理器一般以比处理器所耦合的主存储器更快的速度操作。为了 克服主存储器的固有延迟，使用了存储器层次，其中所述主存储器通常包 括动态随机存取存储器(DRAM)。存储器层次包括一级或多级高速缓 存，每个高速缓存包括被配置来保存处理器最近访问的或预期将要访问的 数据的相对较快的存储器设备或电路。高速缓存的目的是保证处理器所需 的大多数数据迅速对处理器可用，而不需访问主存储器，因为与处理器的 速度或处理器可以访问高速缓存的速度相比，访问主存储器的过程非常 慢。
一般，存储器层次包括多级高速缓存，其中每一级别都比下一较低级 别快，并且最接近处理器的级别表现出最高的速度和性能。高速缓存可以 位于处理器自身上，即，“片上”高速缓存，或者高速缓存可以包括外部 存储器设备，即，“片外”高速缓存。例如，处理器可以包括高级别片上 高速缓存，它经常被称为“L1”高速缓存，其中处理器与较低级别的片外 高速缓存耦合，它经常被称为“L2”高速缓存。或者，处理器可以包括片 上L1高速缓存，以及片上L2高速缓存。当然，存储器层次可以包括任何 适当数目的高速缓存，各高速缓存位于片上或片外。
如上所述，每个级别的高速缓存可以保存存储器最近所访问的数据， 由于时间和空间的局部性原理，这样的最近被访问的数据很可能不久以后 再被处理器需要。但是，通过预测处理器的需要，系统性能可以进一步加 强，并且存储器延迟降低。如果可以以一定程度的准确性来预测处理器不 久以后所需的数据，则可以预先取出或“预取”该数据，使得数据被高速 缓存，并且迅速对处理器可用。通常，利用某种类型的算法来预测处理器 的需要，并且任何预取方案的价值依赖于这些需求可以被准确地预测的程 度。
一种传统类型的预取器通常称为“跨度(stride)”预取器。跨度预取 器通过检查处理器所请求的数据的地址(即，“需求加载(demand load)”)以判断所请求的地址是否表现出规则的模式，来预测处理器的 需要。如果处理器(或者执行于其上的应用程序)使用从地址到地址的恒 定偏移量(即，恒定跨度)在存储器中步进，则跨度预取器尝试识别该恒 定跨度，并根据这种可识别模式来预取数据。但是跨度预取器的确表现出 了明显的缺点。当一系列的需求加载的地址模式不规则时，即，没有恒定 跨度时，跨度预取器不能良好地发挥作用，这例如在动态存储器分配中可 能发生。
另一种数据预取的方法利用了转换后援缓冲器(translation look-aside buffer，TLB)，它是用于虚拟到物理地址转换的高速缓存。根据该方法， 检查与需求加载相关联的“填充内容”，即，所请求的数据，并且，如果 具有地址大小的数据值与包含在TLB中的地址匹配，则该数据值很可能对 应于“指针加载(pointer load)”，即，一种需求加载，其中，所请求的 数据是指向存储器位置的地址，并且该数据值因而被认为是候选地址。接 着，可以发出对该候选地址的预取请求。因为所请求的数据的内容(与其 地址相对)被检查，所以该方法可以称为基于内容的预取，或者内容感知 预取。这样的引用TLB(或者，更一般地，引用任何外部源或地址索引) 的内容感知预取方案具有明显的限制：可能的地址被限制在被高速缓存在 TLB中的那些地址，并且这种约束明显地降低了预取机会的数量。并且， 这种内容感知预取方案要求大量对TLB的访问；从而，必须向TLB增加 附加的端口来应付内容预取器的开销。
发明内容
根据本发明的一个方面，提供了一种用于识别高速缓存线中的虚拟地 址的方法，包括：接收高速缓存线，所述高速缓存线包括处理单元所请求 的数据；从所述高速缓存线获取有效地址；从所述高速缓存线读取具有地 址大小的字，所述高速缓存线包括多个具有地址大小的字；将所述具有地 址大小的字的高N位与所述高速缓存线的所述有效地址的高N位相比较； 以及如果所述具有地址大小的字的所述高N位与所述有效地址的所述高N 位相匹配，则将所述具有地址大小的字识别为候选虚拟地址，并且生成对 于所述候选虚拟地址的预取请求。
根据本发明的另一个方面，提供了一种能够识别高速缓存线中的虚拟 地址的设备，包括：高速缓存存储器，所述高速缓存存储器接收处理单元 所请求的填充内容，所述填充内容包括高速缓存线；与所述高速缓存存储 器相耦合的内容预取器。所述内容预取器包括：用于接收所述高速缓存线 的拷贝的装置；用于从所述高速缓存线获取有效地址的装置；用于从所述 高速缓存线读取具有地址大小的字的装置，所述高速缓存线包括多个具有 地址大小的字；用于将所述具有地址大小的字的高N位与所述高速缓存线 的所述有效地址的高N位相比较的装置；以及用于如果所述具有地址大小 的字的所述高N位与所述有效地址的所述高N位相匹配，则将所述具有地 址大小的字识别为候选虚拟地址，并且生成对于所述候选虚拟地址的预取 请求的装置。
根据本发明的另一个方面，提供了一种用于识别高速缓存线中的虚拟 地址的方法，包括：从存储器对齐的高速缓存线获取有效地址；从所述存 储器对齐的高速缓存线读取具有地址大小的字；如果所述具有地址大小的 字的K个最低有效位中的任何一个是非零的，则丢弃所述具有地址大小的 字；将所述具有地址大小的字的高N位与所述高速缓存线的所述有效地址 的高N位相比较；以及如果所述具有地址大小的字的所述高N位与所述有 效地址的所述高N位相匹配，则将所述具有地址大小的字识别为候选虚拟 地址。
附图说明
图1是系统的示例实施例的示意图，该系统包括具有内容预取器的处 理器。
图2是处理器的示例实施例的示意图，该处理器包括具有虚拟地址预 测器的内容预取器实施例。
图3是图示了内容感知预取方法的实施例的流程图。
图4是图示了内容感知预取方法的另一实施例的流程图。
图5是图示了内容感知预取方法的又一实施例的流程图。
图6是图示了识别候选虚拟地址的方法的实施例的流程图。
图7到图9是示意图，其中的每一个进一步图示了图6所示的方法。
图10是图示了用于将高速缓存线中的具有地址大小的字与高速缓存 线的有效地址相比较的过程的实施例的示意图。
图11是图示了识别候选虚拟地址的方法的另一实施例的流程图。
图12是图示了用于将高速缓存线中的具有地址大小的字与高速缓存 线的有效地址相比较的过程的另一实施例的示意图。
图13是图示了识别候选虚拟地址的方法的又一实施例的流程图。
具体实施方式
参照图1，系统100包括总线110，处理器200与总线110耦合。处理 器200可以包括任何适合的处理设备或电路。如下面将讨论的，在一个实 施例中，处理器200只包括片上高速缓存。但是，在替代的实施例中，处 理器200可以包括与处理器200相耦合的片外高速缓存170，该片外高速 缓存170可以被单独配备或者与片上高速缓存结合配备。
主存储器120与总线110耦合，主存储器120包括例如动态随机存取 存储器(DRAM)。主存储器120可以包含处理器200执行应用程序时将 使用的数据和/或指令。只读存储器(ROM)130也可以耦合到总线110。 ROM 130可以存储用于在处理器200上执行的指令。另外，诸如硬盘驱动 器或其他适合的非易失性存储器的数据存储设备140可以与总线110相耦 合。
系统100还可以包括一个或多个与总线110耦合的输出设备150。普 通的输出设备150包括视频监视器、打印机和音频输出设备(例如声卡和/ 或扬声器)。系统100还可以包括一个或多个耦合到总线110的输入设备 160。一般的输入设备包括键盘、诸如鼠标的点选设备以及扫描仪和其他 数据输入设备。应该理解系统100可以包括图1所示的那些组件之外的其 他组件，包括可拆卸存储介质(例如，软盘驱动器、CD-ROM驱动器)、 网络接口、与处理器耦合的芯片组以及附加的信号线和总线，为了清楚将 它们省略了。
参照图2，处理器200包括CPU(中央处理单元)核心210。与CPU 核心210相耦合的是第一级片上高速缓存，或“L1高速缓存”220。第二 级别高速缓存，或“L2高速缓存”230也被放置在处理器200中。这里将 被称为“L2仲裁器”的仲裁器240耦合到L1和L2高速缓存220和230的 每一个。这里将被称为“总线仲裁器”的另一个仲裁器250耦合到L2高 速缓存。总线仲裁器250也耦合到总线接口单元260。总线接口单元260 将处理器200与总线110相耦合，从而使得处理器200和主存储器120之 间能够通信。L1和L2高速缓存220和230可以各自包括任何适当类型的 存储器或电路。
L1高速缓存220和L2高速缓存230与主存储器120相结合提供了用 于CPU核心120的存储器层次。通常，L1高速缓存220表现出相对于 CPU核心210的最高的速度，而主存储器120表现出最低的相对速度。L2 高速缓存230工作得比主存储器120快得多，但可以比L1高速缓存220 慢。数据存储设备140(见图1)也可以被认为是存储器层次的一部分， 数据存储装置140是该层次中最慢的元件。L1和L2高速缓存220和230 中的每一个都存储CPU核心210最近所访问的或预期将访问的数据和/或 指令。
在操作期间，如果CPU核心210请求数据，即“需求加载”或“需求 请求”，则访问L1高速缓存220以确定它是否含有所请求的数据，如果 有，则数据被提供给CPU核心210。如果L1高速缓存220不含有所请求 的数据，即“高速缓存未命中”，则需求请求被传递到L2仲裁器240。 L2仲裁器240接着向L2高速缓存230提供需求请求，并且L2高速缓存 230被访问以确定它是否含有所请求的数据。如果L2高速缓存230含有所 请求的数据，则所请求的数据，即“填充内容”，被转发到L1高速缓存 220，并继而到CPU核心210。如果需求加载未被L2高速缓存230满足， 则该加载被传递到总线仲裁器250。如果主存储器120保存有所请求的数 据，则填充内容沿着存储器层次向上被传递到CPU核心210。如果主存储 器120不能满足该需求请求，则可以访问数据存储设备140。L2仲裁器和 总线仲裁器240、250中的每一个都包括缓冲存储器，并且如果进行中有 多个加载，则L2仲裁器和总线仲裁器240、250可以缓冲需求请求。在存 储器请求仲裁期间，L2仲裁器和总线仲裁器240、250也可以缓冲预取请 求，这将在下面解释。
在CPU核心210中执行的进程可以访问虚拟地址空间。一般地，这样 的虚拟地址空间由存储器管理单元或MMU(图中未示出)来维护。为了 访问虚拟地址的数据，虚拟地址(或多个虚拟地址)必须被映射到物理地 址，即主存储器120中的真实位置。这样，应该理解，当数据穿过存储器 层次时，数据可以经历虚拟到物理的地址转换。例如，L1高速缓存220可 以被虚拟索引，并且L2高速缓存230被物理索引；从而，如果在L1高速 缓存220出现高速缓存未命中，则在访问L2高速缓存230之前，请求虚 拟到物理地址转换。
如上面所提出的，可以通过预测CPU核心210的需要并预取CPU核 心210可能即将请求的任何数据，来增强系统性能。处理器200可以包括 与L2仲裁器240和L2高速缓存230耦合的跨度预取器270。跨度预取器 270监视L1未命中流通量，即在L1高速缓存220未命中的需求加载，以 及L2未命中流通量，即在L2高速缓存230未命中的需求加载，并且尝试 检测所请求的地址中的恒定跨度。如果检测到恒定跨度，则基于被检测到 的跨度向L2仲裁器240提供预取(PF)请求。但是，如上面所提到的， 当连续的需求请求的地址模式不规则并且没有恒定跨度时(例如，这可以 发生在动态存储器分配期间)，跨度预取器270不能充分发挥作用。
处理器200还包括新型内容预取器290。内容预取器290与L2高速缓 存230相耦合，并接收导向L2高速缓存230的所有填充内容的拷贝，填 充内容包括一个或多个高速缓存线。但是，更一般地，内容预取器290可 以与处理器的存储器层次中的任何级别相耦合，并接收导向该级别的所有 填充内容的拷贝。另外，尽管处理器200的内容预取器290与片上L2高 速缓存230相耦合，但是应该理解内容预取器290也可以与片外高速缓存 相耦合，例如图1所示的片外高速缓存170。内容预取器290还与L2仲裁 器240相耦合。
内容预取器290包括虚拟地址预测器295。如前面所描述的，内容预 取器290接收在L2高速缓存230所收到的每个高速缓存线的拷贝。虚拟 地址预测器295检查高速缓存线，并将包含在高速缓存线中的候选虚拟地 址与其他数据值和随机位组合区别开，而不用参照任何外部地址源，即 TLB，所述外部地址源可能不必要地约束了可能的地址范围，从而约束了 可能预取机会。虚拟地址预测器295包含如下的任何适合的电路和/或指 令：所述电路和/或指令能够基于高速缓存线自身中所包含的数据来识别高 速缓存线中的候选虚拟地址，而不用访问外部地址参考。
参照图3所示的内容感知预取的方法300，可以更好地理解内容预取 器290和虚拟地址预测器295的操作。参照图3中的参考标号310，在L2 高速缓存230处收到填充内容。填充内容的拷贝被提供给内容预取器 290，如320所表示的。填充内容包括高速缓存线(或者替代地，填充内 容包括两个或多个高速缓存线)。如参考标号330所示，扫描高速缓存线 以寻找候选虚拟地址。如果虚拟地址预测器295识别出候选虚拟地址，见 参考标号340，则内容预取器290生成对应于所识别的候选虚拟地址的预 取请求，如参考标号350所示。内容预取器290接着向L2仲裁器240提 供预取请求，见参考标号360，其中L2仲裁器240可以基于存储器请求仲 裁来缓冲预取请求和/或向主存储器120发出预取请求，这将在下面描述。
上述过程被继续，直到整个高速缓存线已经被扫描。当整个高速缓存 线已经被扫描，见参考标号370，并且高速缓存线中所包含的所有候选虚 拟地址都已经被识别时，高速缓存线的扫描结束，如380所示。如下面将 更详细描述的，可以并行地扫描整个高速缓存线或其一部分。
如上所述，被导向L2高速缓存230的所有填充内容的拷贝被提供给 内容预取器290。这样，对于CPU核心210所发出的导致在L2高速缓存 230处高速缓存未命中的每个需求请求，或者，更一般地说，导致在与内 容预取器290相耦合的高速缓存级别上的高速缓存未命中的每个需求请 求，内容预取器290将接收所请求数据的拷贝。与已经在存储器层次中的 某个级别的高速缓存处未命中的需求请求相关联的填充内容可以被称为 “需求参考流”。但是，其他填充内容将作为L2仲裁器240(或总线仲裁 器250)所发出的预取请求的结果，即“预取参考流”，而被导向L2高速 缓存230，并且与该预取参考流相关联的填充内容的拷贝也被提供给内容 预取器290。这样，通过检查与需求参考流相关联的填充内容以及与预取 参考流相关联的填充内容，内容预取器290包括递归组件，并且可以基于 先前的预取请求来提供预取请求。这样的递归组件允许内容预取器290沿 着例如“链接数据结构”(即，一种数据结构，其中每个元素包含指向该 结构的下一个元素的指针)的数据结构中的递归路径前进。由内容预取器 290基于先前的预取请求而提供的预取请求可以被称为“链联”预取请 求。
当L2仲裁器240从内容预取器290接收预取请求(对应于由虚拟地 址预测器295所识别的候选虚拟地址的预取请求)时，L2仲裁器240可以 缓冲预取请求并延迟该请求的发出。因为总线110的低带宽以及主存储器 120的低访问速度，所以对L2仲裁器中的预取请求(以及某些情况下的需 求请求)的缓冲可能是(并且，在大多数情况下是)必须的。因此，L2仲 裁器240以及总线仲裁器250可以实现优先级划分方案，来确定被包含在 其缓冲器中的多个预取请求以及多个需求请求中的哪个应当首先被发出。 这种对存储器请求进行优先级划分并根据每个请求的优先级来发出需求或 预取请求的过程可以被称为存储器请求仲裁。
因为需求请求对应于CPU核心210当前所需要的数据，所以需求请求 通常应该被给予最高的优先级。预取请求通常被给予低于需求请求的优先 级；然而，不是预取请求递归链中所有的预取请求都可能表示CPU核心 210迫切需要的数据，即，它们更加具有推测性，因此，它们应该被指定 不同的优先级。内容预取器290提供了递归组件，这引出了“请求深度” 的概念，所述递归组件提供了预取链，其中，链中的第一个预取请求是基 于与需求请求相关联的填充内容的，链中的每个随后的预取请求是基于由 前一预取所产生的填充内容的。如果需求请求例如被指定了为零(0)的 请求深度，则由与需求请求相关联的填充内容所产生的预取请求被指定为 一(1)的请求深度，并且每个随后的链联的预取被指定的请求深度比该 链联的预取请求所基于的预取请求的请求深度大一(1)。
上述请求深度提供了预取请求中的置信度(confidence)的测量，并且 在仲裁存储器请求以确定预取请求的优先级期间，L2仲裁器240以及总 线仲裁器250可以使用请求深度。具有最低请求深度的存储器请求可以被 指定最高的优先级，并且被L2仲裁器240(或者总线仲裁器250)首先发 出。需求请求具有例如为零的请求深度，并被指定最高的优先级。由与需 求加载相关联的填充内容所产生的预取请求被指定下一个最高优先级。链 联的预取请求被指定与其请求深度相称的优先级，所指定的优先级与请求 深度成反比。因此，表现出较高请求深度的链联的预取请求被指定较低的 优先级，因为它们可能是更具推测性的。具有大于预定阈值的请求深度的 链联预取请求被取消，并且仲裁器不发出预取请求，在该阈值，预取请求 的置信度低。相同优先级(即，相同请求深度)的预取请求被调度以由L2 仲裁器240(或总线仲裁器250)按照先到先服务的方式发出。
内容感知预取和确定每个预取请求的优先级的方法400示于图4中。 应该注意到示于图4中的方法400包括许多与图3的方法300相同的元 素，并且类似的元素在图4中保留相同的参考标号。
参照图4的参考标号310，在L2高速缓存230处收到填充内容，并且 填充内容的拷贝被提供给内容预取器290(见参考标号320)。填充内容 包括高速缓存线(或者替代地，填充内容包括两个或多个高速缓存线)。 如330所表示的，高速缓存线然后被扫描以寻找候选虚拟地址。如果虚拟 地址预测器295识别出候选虚拟地址，见参考标号340，则内容预取器 290生成对于该地址的预取请求，如标号350所示。
现在参照图4中的参考标号410，如上面所描述的，内容预取器290 确定预取请求的请求深度。如果请求深度大于预定阈值，见参考标号 420，则该预取请求被取消，如440所表示的。如果请求深度没有超过预 定阈值，则为该预取指定优先级，见参考标号430，其中如前面所描述 的，该优先级是基于请求深度的。
一旦为预取请求被指定了优先级，则内容预取器290向L2仲裁器240 提供该预取请求，如360所示。L2仲裁器240基于它的缓冲器中所保存的 每个预取请求的优先级，在缓冲存储器中对等待进行存储器请求仲裁的预 取请求进行排对。此外，需求请求具有最高的优先级，并且由L2仲裁器 240(或者总线仲裁器250)首先发出。优先级低于需求请求的预取请求按 照它们各自的优先级被L2仲裁器240(或总线仲裁器250)发出。此外， 预取请求的优先级是基于预取请求的请求深度的。该过程被继续，直到整 个高速缓存线已经被扫描，当整个高速缓存线已经被扫描(见参考标号 370)并且高速缓存线中所包含的所有候选虚拟地址都已经被识别时，高 速缓存线的扫描结束，如380所示。
内容感知预取另一个实施例的方法500示于图5中。应该注意到示于 图5中的方法500包括许多与图3的方法300相同的元素，类似的元素在 图5中保留相同的参考标号。并且，内容感知预取的方法500类似于图3 中所示的方法300，对那些前面描述过的元素不再重复详细说明。
参照参考标号510，如果候选虚拟地址已经被识别出(见参考标号 340)，则L2仲裁器和总线仲裁器240、250都被轮询以察看匹配的存储 器请求当前是否在进行中(in-flight)，即对应于候选虚拟地址的存储器请 求已经被发出。如果匹配的存储器请求在进行中，则预取请求被取消，如 参考标号530所示。在预取请求由于进行中的存储器请求而被取消的事件 中，高速缓存线的扫描继续(见参考标号330、370)。
如前面所描述的，等待进行存储器请求仲裁的预取请求在L2仲裁器 240(或总线仲裁器250)的缓冲存储器中被排队。在某些例子中，L2仲 裁器240的缓冲器可能变满。如果在L2仲裁器240中无缓冲器空间可 用，见参考标号520，则预取请求被取消，如参考标号530所示。在预取 请求由于缺少可用的缓冲器空间而被取消的事件中，因为存储器空间可以 在L2仲裁器240的缓冲器中再次变为可用，所以高速缓存线的扫描可以 继续，见参考标号330、370。
如上面所提出的，内容预取器290的虚拟地址预测器295不用参照任 何外部地址源，而将候选虚拟地址从被包含在高速缓存线中的随机位组合 和数据值中区分开，所述外部地址源例如是TLB，其可能限制了预取机会 的范围。现在公开可以由虚拟地址预测器295实现的识别候选虚拟地址的 方法。应该注意到，因为被导向CPU核心210的填充内容中所包含的可能 的地址是在虚拟地址空间中，所以识别候选虚拟地址的方法“查找”虚拟 地址(与物理地址相对)，即使在存储器层次中可能已经发生虚拟到物理 地址转换。
识别候选虚拟地址的方法是基于如下假定：如果指针加载(即，一种 需求加载，其中所请求的数据是指向存储器位置的地址)从存储器被加 载，则有很大的可能性，该指针加载的地址将是未来的需求请求的有效地 址。该假定的核心是如下观念：数据结构的基址经由指针加载被提供，并 且共享该基址的该结构中的任何数据值可以被认为是指向同一数据结构的 另一个成员的指针。假设所有的需求请求潜在地包括指针加载，则响应于 共享该基址的需求请求而返回的高速缓存线中所包含的任何具有地址大小 的字被认为是候选虚拟地址。如果具有地址大小的字的许多高位与高速缓 存线的有效地址中的相同数目的高位相匹配，则这些匹配的高位表明，该 具有地址大小的字和高速缓存线的有效地址是从相同的基址计算而来的， 从而，该具有地址大小的字可能对应于未来的需求加载的有效地址。
识别候选虚拟地址的示例实施例的方法600示于图6中。参照参考标 号610，虚拟地址预测器295接收高速缓存线。该高速缓存线被包括在内 容预取器290处所接收的填充内容中(见图3，项目310和320)，在内 容预取器290处所接收的填充内容包含被导向L2高速缓存230的填充内 容的拷贝，如上面所提到的。接着，获取高速缓存线的有效地址，如参考 标号620所示。扫描高速缓存线(见图3，参考标号330)，并且从高速 缓存线读取具有地址大小的字，如参考标号630所示。对于一般的处理 器，具有地址大小的字对应三十二(32)位或者四(4)字节；但是，具 有地址大小的字可以是任何适合的长度。
从高速缓存线读取具有地址大小的字(或多个字)的过程进一步示于 图7到图9中。参照图7，示例高速缓存线700包含六十四(64)个字节 705。但是，应该理解，高速缓存线可以是任何适合的长度(例如，128字 节)。可以从高速缓存线读取第一个具有地址大小的字710(即，第一个 四字节)。可以从高速缓存线读取第二个具有地址大小的字720，其中第 二个具有地址大小的字720的开头与第一个具有地址大小的字710的开头 相距一(1)个字节的偏移量708。类似地，可以从高速缓存线读取第三个 具有地址大小的字730，其中第三个具有地址大小的字730与第二个具有 地址大小的字720相距一(1)个字节的偏移量。可以以类似的方式从高 速缓存线读取其他具有地址大小的字，直到从高速缓存线读取了最后的具 有地址大小的字790。
示于图8的扫描高速缓存线的过程类似于图7所示的过程；但是偏移 量增加了，从高速缓存线读取的具有地址大小的字的数目减少了。高速缓 存线800包括例如六十四(64)个字节805。从高速缓存线800读取具有 地址大小的字810、820、830、...、890，每个具有地址大小的字的开头与 前一个具有地址大小的字相距两(2)个字节的偏移量808。这样，高速缓 存线扫描的间隔大小可以通过改变偏移量808、708而变化，从而，改变 了将被检查的具有地址大小的字的数目。另外，如上所述，高速缓存线 800(或700)可以被并行地扫描，其中整个高速缓存线同时被扫描。但 是，应该理解，当可以从高速缓存线读取的数据的数量受到例如总线带宽 的限制时，高速缓存线可以分部分地被扫描，其中每个部分被并行地扫 描。
参照图9，高速缓存线900包含六十四(64)个字节905。从高速缓 存线900读取第一个具有地址大小的字910，第一个具有地址大小的字包 括高速缓存线900的第一个四字节。从高速缓存线读取第二个具有地址大 小的字920，其中第二个具有地址大小的字920的开头对应于第一个具有 地址大小的字910的结尾。换句话说，第一个和第二个具有地址大小的字 910、920相距四(4)个字节的偏移量，这也是将从高速缓存线900读取 的每个具有地址大小的字的长度。从高速缓存线900读取的第三个具有地 址大小的字930类似地从前一个具有地址大小的字偏移四字节。
存储在存储器中的数据结构，其中该数据结构的每个元素从字的边界 开始读取，被称为是“存储器对齐”的或“J字节对齐”的。例如，示于 图9中的高速缓存线900是“4字节对齐”的，而图8的高速缓存线800 是2字节对齐的。如下面将解释的，这种存储器对齐的数据表现出某些特 性，虚拟地址预测器295可以在操作中有益地利用这些特性。
再次参照图6，一旦具有地址大小的字已经从高速缓存线被读取，则 具有地址大小的字的某个数量的高位与高速缓存线的有效地址中的相同数 目的高位相比较，如640所示。具体地说，具有地址大小的字的N个高位 与高速缓存线的有效地址的高N位相比较。该过程参考图10更好地被图 示。高速缓存线的有效地址1010的高N位与被包含在高速缓存线中的具 有地址大小的字1020的高N位相比较。有效地址1010和具有地址大小的 字1020中的每一个的高N位都分别被称为比较位1030。高N位或者比较 位1030可以包含任何适合数目的位。例如，对于32位的具有地址大小的 字，N位比较位可以包含8到12之间的位。
位组合可以被认为是指针加载、数据值或者简单的随机位。如果具有 地址大小的字的高N位与高速缓存线的有效地址的高N位相匹配，这表明 具有地址大小的字和高速缓存线的有效地址是从相同的基址计算而来的， 则具有地址大小的字被认为是指向数据结构成员的指针。如果具有地址大 小的字的高N位与高速缓存线的有效地址的高N位相匹配，见参考标号 650，则该具有地址大小的字被识别为候选虚拟地址，如660所示，并且 内容预取器290可以提供对于所识别的候选虚拟地址的预取请求(见图3 到图5)。如果高N位不匹配，则该具有地址大小的字被丢弃，如参考标 号670所示。在高速缓存线扫描期间，上述过程(见参考标号630、640、 650、660、670)被应用于从高速缓存线读取的每个具有地址大小的字。
识别候选虚拟地址的方法的另一个实施例示于图11中。如前面所描 述的，高速缓存线可以是存储器对齐的。例如，数据结构可以是2字节对 齐、4字节对齐、8字节对齐、16字节对齐，或者更一般地，J字节对齐。 如果高速缓存线中的数据是J字节对齐的，则任何候选虚拟地址的某个数 目的最低有效位(见图10，参考标号1090)将为零(0)。例如，对于2 字节对齐的数据，最低有效位将为零，对于4字节对齐的数据，两个最低 有效位将为零，对于8字节对齐的数据，三个最低有效位将为零，对于16 字节对齐的数据，四个最低有效位将为零。更一般地，对于J字节对齐的 数据，K个最低有效为将为零。虚拟地址预测器295可以使用存储器对齐 数据的假设来取消候选虚拟地址的资格。假设存储器对齐，如果具有地址 大小的字的K个最低有效位的任何一个是非零，则该具有地址大小的字可 以被取消作为候选虚拟地址的资格。参照图11，其示出了基本上类似于 图6所示的方法600的方法1100(所有相似的元素保留相同的参考标 号)，如果从高速缓存线读取的具有地址大小的字的K个最低有效位的任 何一个是非零，见参考标号1110，则该具有地址大小的字被丢弃，如670 所示。
上面所描述的识别候选虚拟地址的方法600(以及方法1100)一般可 作用于高速缓存线的有效地址的高位中所包含的任何位组合，但有两个例 外：高N位全为0的情况和高N位全为1的情况(在该情况中，负数可能 被错误地识别为候选虚拟地址)。但是，与当有效地址的比较位全为0或 全为1时不进行预测相比，更好的方法是在比较中使用附加的过滤位来将 候选虚拟地址从数据值或者随机位组合区分开。参照图12，高速缓存线的 有效地址1210的比较位1230或者全是1，或者全是0。如果高速缓存线 的具有地址大小的字1220的高N位与有效地址的高N位(其或者全是 1，或者全是0)相匹配，则检查具有地址大小的字的附加过滤位1240。 过滤位1240包含高N位或比较位1230之后的下面的M个位。如果比较 位1230全是0，并且在具有地址大小的字的过滤位范围中发现了非零位， 或者，如果比较位1230全是1，并且在具有地址大小的字的过滤位范围中 发现了非1的位，则该具有地址大小的字被视为候选虚拟地址。
利用过滤位识别候选虚拟地址的方法1300示于图13中。方法1300类 似于参照图6所描述和示出的识别候选虚拟地址的方法600，并且相似的 元素保留相同的参考标号。如参考标号610所示，虚拟地址预测器295接 收高速缓存线。再次，高速缓存线被包括在内容预取器290所接收的填充 内容的拷贝中。接着，获取高速缓存线的有效地址，如参考标号620所 示。扫描高速缓存线，并从高速缓存线读取(或以其他方式访问)具有地 址大小的字，如参考标号630所示。参照参考标号640，具有地址大小的 字的高N位然后与有效地址的高N位相比较。
如果具有地址大小的字的比较位和高速缓存线的有效地址的比较位相 匹配，见参考标号650，并且有效地址的高N位全为0，见参考标号 1310，则检查具有地址大小的字的下M个过滤位。参照参考标号1320， 如果具有地址大小的字的下M个过滤位中的任何一个是非零位，则该具有 地址大小的字是候选虚拟地址(见参考标号660)。如果在过滤位范围中 没有发现非零位，则该具有地址大小的字被丢弃，如670所示。类似地， 如果具有地址大小的字的比较位和有效地址的比较位相匹配，参考见标号 650，并且有效地址的高N位全是1，见参考标号1330，则具有检查地址 大小的字的下M个过滤位。如参考标号1340所示，如果具有地址大小的 字的下M个过滤位中的任何一个是非1位，则该具有地址大小的字是候选 虚拟地址(见参考标号660)。如果在过滤位范围中没有发现非1位，则 该具有地址大小的字被丢弃，如670所示。
过滤位范围可以包含任何适合数目的位。例如，对于32位的具有地 址大小的字，认为1到4位的过滤位范围被认为是适合的。当高速缓存线 的有效地址的比较位全为0或全为1时，不使用过滤位导致没有虚拟地址 预测，而增加过滤位的数目放松了对可能的候选虚拟地址的要求。
这里已经描述了具有虚拟地址预测器295的内容预取器290的实施例 以及识别候选虚拟地址的方法600、1100和1300，本领域技术人员将意识 到它们的优点。虚拟地址预测器识别从高速缓存接收到的填充内容的拷贝 中的候选虚拟地址，而不用求助于外部源或地址索引，例如TLB，从而潜 在预取的范围没有被不必要地限制。虚拟地址预测器可以提供递归组件， 引起链联的预取，并且可以基于预取的请求深度来为该预取指定优先级。 识别候选虚拟地址的方法通过将从高速缓存线读取的具有地址大小的字的 高N位与高速缓存线的有效地址的高N位相比较，来将候选虚拟地址与数 据值和随机位组合区分开。如果比较位相匹配，则具有地址大小的字被识 别为候选虚拟地址，并且对于该地址的预取请求可以被排队；否则，该具 有地址大小的字被丢弃。在另一个实施例中，当高速缓存线的有效地址的 高N位全为1或全为0时，检查具有地址大小的字内的过滤位范围，从而 最小化错误预测，这例如当填充内容包括多个负数时可能发生。并且，识 别候选虚拟地址的方法可以利用存储器对齐数据，来容易地排除没有可能 对应于虚拟地址的具有地址大小的字。
前面的详细描述和附图只是示例性的，而不是限制性的。提供它们主 要是为了清楚和全面地理解本发明，不应该将其理解为是不必要的限制。 本领域的技术人员可以设计许多对于这里所描述的实施例的添加、删除和 修改，以及替换的安排，而不脱离本发明的精神和所附权利要求的范围。
相关申请
本申请涉及与本申请共同提交的标题为“Method and Apparatus for Content-Aware Prefetching(用于内容感知预取的方法和装置)”的申请 No.XX/XXX,XXX。