用于低复杂性指令预取系统的方法和设备

摘要

本发明涉及用于低复杂性指令预取系统的方法和设备。当指令高速缓冲存储器中发生未命中时，使用使未命中率、存储器存取带宽和功率使用最小化的预取技术。所述预取技术中的一种预取技术在发生未命中时操作。接收获取地址在指令高速缓冲存储器中未命中的通知。分析引起所述未命中的所述获取地址以确定所述获取地址的属性，且基于所述属性，预取指令线。所述属性可指示所述获取地址是非循序操作的目标地址。另一个属性可指示所述获取地址是非循序操作的目标地址，且所述目标地址有大于X%进入高速缓冲存储器线中。其它属性可指示所述获取地址是所述指令高速缓冲存储器中的偶地址。可组合此些属性以确定是否进行预取。

说明书

分案申请的相关信息

本案是分案申请。该分案的母案是国际申请日为2007年12月3日、申请号为 200780044777.6、发明名称为“用于低复杂性指令预取系统的方法和设备”的专利申请。

技术领域

本发明大体上涉及指令高速缓冲存储器的领域，且更具体来说，涉及在指令高速缓 冲存储器中有未命中时的指令预取。

背景技术

许多便携式产品(例如，手机、膝上型计算机、个人数据助理(PDA)等)利用执 行程序(例如，通信和多媒体程序)的处理器。用于此些产品的处理系统包括用于存储 指令和数据的处理器与存储器复合体。与处理器循环时间相比，大容量主存储器通常具 有较慢的存取时间。因此，常规上基于高速缓冲存储器的容量和性能来按层级组织存储 器复合体，其中最高性能和最低容量的高速缓冲存储器位于最接近于处理器处。举例来 说，1级指令高速缓冲存储器和1级数据高速缓冲存储器将一般直接附接到处理器。而 2级统一高速缓冲存储器连接到1级(L1)指令和数据高速缓冲存储器。另外，系统存 储器连接到2级(L2)统一高速缓冲存储器。1级指令高速缓冲存储器通常以处理器速 度来操作，且2级统一高速缓冲存储器比1级高速缓冲存储器操作得慢，但具有比系统 存储器的存取时间快的存取时间。替代性存储器组织除了L1和L2高速缓冲存储器外大 量存在(例如)具有3级高速缓冲存储器的存储器层级。另一个存储器组织可仅使用1 级高速缓冲存储器和系统存储器。

为何可使用指令高速缓冲存储器的存储器层级背后的原理之一为倾向于从存储器 中的循序位置来存取指令。通过通过使高速缓冲存储器保存最近所使用的代码段，处理 器可以较高性能水平执行。由于程序还含有分支、调用和返回类型的指令，且支持其它 非循序操作(例如，中断)，所以可仅针对相当短的代码段维持循序位置的原理。归因 于此些非循序操作，对指令高速缓冲存储器的指令获取可未命中，使得将指令取响应用 于在较高存储器容量和较慢存取时间下操作的下一较高级存储器。未命中可使处理器中 止以等待指令。为了使处理器性能保持较高，高速缓冲存储器未命中率应为低。

指令高速缓冲存储器通常由位于指令高速缓冲存储器中的单个地址处的多个指令 构成。此多个指令通常被称为高速缓冲存储器线或简称为线。未命中可发生于高速缓冲 存储器线中任何地方的指令存取时。当未命中发生时，不再仅获取所需指令，而是还可 获取高速缓冲存储器线的剩余部分，即，从所未命中指令到高速缓冲存储器线的末端。 在一些系统中，将此种预取技术进一步扩展到在未命中时总是预取高速缓冲存储器线的 剩余部分和下一个高速缓冲存储器线。此种总是预取下一个高速缓冲存储器线的常规技 术是基于下一个高速缓冲存储器线含有不久将需要的指令的假定。对使用下一个高速缓 冲存储器线中的指令的此设想保持有效，即使是(例如)在所述线中遇到条件分支且条 件致使所述分支流沦为下一个循序指令。通过一直预取下一个高速缓冲存储器线，可减 少未命中。

当然，在程序中的某点处，对指令的循序存取的位置原理失败，且未命中确实归因 于由分支、调用和返回等引起的非循序操作而发生。举例来说，当在高速缓冲存储器线 的末端处获取指令，且下一个循序指令(其应驻存在下一个循序指令高速缓冲存储器线 中)不驻存在高速缓冲存储器中时，还可发生归因于循序存取的未命中。举例来说，当 遇到分支指令且所述分支使程序地址改变为新的位置且新位置处的指令不驻存在高速 缓冲存储器中时，可发生归因于非循序存取的未命中。一直预取下一个高速缓冲存储器 线的常规技术获取可能会不使用的指令且因此引起存储器存取带宽的不必要损失、增加 的功率使用和较低处理器性能。

发明内容

本发明认识到，当未命中发生时，需要减少未命中率、存储器存取带宽和功率使用 的预取技术。本发明的一个实施例提供一种用于指令预取的方法。当未命中发生时，接 收在指令高速缓冲存储器中未命中获取地址的通知。确定引起未命中的获取地址属性， 且基于所述属性，预取指令线。

本发明的另一个实施例针对指令高速缓冲存储器和预取系统。指令高速缓冲存储器 经配置以产生未命中获取地址的通知。预取决策逻辑经配置以确定引起未命中的获取地 址属性，且预取逻辑经配置以基于所述属性来预取指令线。

本发明的另一个实施例针对一种存储器系统。所述存储器系统使用经配置以产生未 命中获取地址的通知的指令高速缓冲存储器。预取决策逻辑经配置以确定引起未命中的 获取地址属性且基于未命中的获取地址和所述属性来产生未命中信息。系统存储器层级 经配置以用与所未命中获取地址相关联的指令来响应于所述未命中信息。

本发明的另一个实施例针对一种用于指令预取的方法，其包含：接收获取地址在指 令高速缓冲存储器中未命中的通知；以及确定引起所述未命中的所述获取地址的属性； 其特征在于还包括：当所述属性指示下列中的一个或者多个时，将与所述获取地址相关 联的下一连续指令线预取入所述指令高速缓冲存储器中：所述获取地址为非循序操作的 目标地址；所述获取地址为非循序操作的目标地址并且所述目标地址为进入高速缓冲存 储器线中大于或等于阈值X%的地址；以及所述获取地址为所述指令高速缓冲存储器中 的偶地址。

本发明的另一个实施例针对一种用于指令预取的设备，其包含：用于接收获取地址 在指令高速缓冲存储器中未命中的通知的装置；用于确定引起所述未命中的所述获取地 址的属性的装置；以及其特征在于还包括：用于在所述属性指示下列中的一个或者多个 时，将与所述获取地址相关联的下一连续指令线预取入所述指令高速缓冲存储器中的装 置：所述获取地址为非循序操作的目标地址；所述获取地址为非循序操作的目标地址并 且所述目标地址为进入高速缓冲存储器线中大于或等于阈值X%的地址；以及所述获取 地址为所述指令高速缓冲存储器中的偶地址。

应理解，通过以下详细描述，所属领域的技术人员将容易明白本发明的其它实施例， 其中以说明的方式来展示并描述本发明的各个实施例。如将认识到的，本发明能够具有 其它且不同的实施例，且其若干细节能够在各个其它方面受到修改，所述其它且不同实 施例和对其的修改均不脱离本发明。因此，图式和详细描述将被视为本质上为说明性的 而非限制性的。

附图说明

图1说明无线通信系统；

图2为处理器与存储器复合体的功能框图，其中可基于对存储器有效操作的试探来 调适对指令高速缓冲存储器线的预取；和

图3为展示低复杂性预取过程的流程图。

具体实施方式

在下文结合附图陈述的详细描述意欲作为对本发明的各种示范性实施例的描述且 不意欲表示可实践本发明的唯一实施例。所述详细描述包括特定细节以便达成提供对本 发明的彻底理解的目的。然而，所属领域的技术人员将明白，可在无这些特定细节的情 况下实践本发明。在一些情况下，以框图形式来展示众所周知的结构和组件以便避免混 淆本发明的概念。

图1说明示范性无线通信系统100，其中，可有利地采用本发明的实施例。出于说 明的目的，图1展示三个远程单元120、130和150和两个基站140。将认识到，典型无 线通信系统可具有许多更多远程单元和基站。远程单元120、130和150包括分别由组 件125A、125C和125B表示的硬件组件、软件组件或其两者，如下文中进一步所论述， 其已被调适以实施本发明。图1展示从基站140到远程单元120、130和150的前向链 路信号180和从远程单元120、130和150到基站140的反向链路信号190。

在图1中，将远程单元120展示为移动电话，将远程单元130展示为便携式计算机， 和将远程单元150展示为无线本地回路系统中的固定位置远程单元。举例来说，所述远 程单元可或者为手机、寻呼机、对讲机、手持式个人通信系统(PCS)单元、例如个人 数据助理的便携式数据单元，或例如仪表读取装备的固定位置数据单元。虽然图1说明 根据本发明的教示的示范性远程单元，但本发明不限于这些示范性的所说明单元。本发 明可适于用在具有带有指令高速缓冲存储器和系统存储器的处理器的任何装置中。

图2为处理器与存储器复合体200的功能框图，其中可基于对存储器有效操作的试 探来调适对指令高速缓冲存储器线的预取。处理器与存储器复合体200包括处理器202； 直接映射1级(L1)指令高速缓冲存储器(Icache)203，其包含L1 Icache线阵列204 和L1Icache控制单元206；和系统存储器层级208。如可用在各种类型的高速缓冲存储 器(例如，组相关联高速缓冲存储器)中，L1Icache控制单元206可包括预取逻辑和用 于指令标签匹配的指令内容可寻址存储器。出于论述清楚起见，不展示可连接到处理器 复合体的外围装置。处理器与存储器复合体200可适于用在用于执行存储于L1Icache 203和系统存储器层级208中的程序代码的组件125A到125C中。

L1Icache线阵列204可包括多个线，例如高速缓冲存储器线210和211。每一线分 别由多个指令(I0、I1、……、I7)212到219组成。标签220和线状态(LS)221(例 如，有效位)与每一线相关联。高速缓冲存储器线210和211分别驻存在L1 Icache线 阵列204中的线地址222和223处。L1Icache控制单元206含有对经由指令地址(IA) 接口225接收到的IA224作出响应的地址控制逻辑以存取高速缓冲存储器线。IA 224 可由标签226、线地址228、指令“I”字段232和字节“B”字段234组成。线地址228 由“line+”字段229和偶数“E”位230组成。

为了获取在处理器与存储器复合体200中的指令，处理器202产生待获取的所要指 令的指令地址(IA)224且将获取地址发送到L1Icache控制单元206。基于接收到的IA 224，L1Icache控制单元206查看所述指令是否存在于L1Icache线阵列204中。举例来 说，通过使用比较逻辑来完成此检查，所述比较逻辑检查由IA224所选的线210中的匹 配标签236。还通过验证线状态位(LS)221(例如，有效位238)来做出关于线是否含 有有效指令的确定。当存在所述指令时，匹配或命中发生，且L1Icache控制单元206 指示所述指令存在于L1Icache203中。如果所述指令不存在，那么将不发现匹配或未命 中，且L1Icache控制单元206提供所述指令不存在于Icache203中的未命中指示。

如果所述指令存在，那么从L1Icache线阵列204选择在指令获取地址处的指令。 接着在指令输出总线240上将所述指令发送到处理器202。

如果所述指令不存在于指令高速缓冲存储器中，那么经由未命中信号路径242将指 示未命中已发生的未命中信息提供给系统存储器层级208。在1级Icache203中检测到 未命中后，处理器与存储器复合体200试图获取所要指令，且如在下文更详细地描述， 可从系统存储器的较高级预取额外指令。举例来说，可从位于系统存储器层级208中的 2级(L2)统一高速缓冲存储器来预取指令。在存储器数据总线接口244上从系统存储 器层级208提供归因于所述未命中的所要指令和任何预取的指令。

当未命中发生时，可确定引起未命中的与获取地址相关联的一个或一个以上属性。 举例来说，可将获取地址归类为循序存取或非循序存取的目标。举例来说，可根据地址 是否有大于X%进入高速缓冲存储器线中来对获取地址作进一步归类。还可基于获取地 址在指令高速缓冲存储器中是否为偶地址来对获取地址进行归类。这些和其它归类界定 可以试探形式组合以智能地确定何时进行预取的属性。通过智能地预取，可节省功率， 可改进存储器带宽，可减少未命中率，且通常可改进处理器和系统性能。

可从获取地址动态地确定引起未命中的与获取地址相关联的属性。举例来说，通过 监视获取地址，可确定循序获取地址或非循序获取地址。基于获取地址和高速缓冲存储 器线长度，可动态地确定在高速缓冲存储器线中的存取位置。举例来说，当所确定位置 的比较等于或超过X%阈值时，此属性为相关的。而且，基于获取地址和高速缓冲存储 器线长度，可使用获取地址中的位来确定是对偶数高速缓冲存储器线还是奇数高速缓冲 存储器线进行存取。在下文更详细地描述这些属性。

在一个实施例中，在指令高速缓冲存储器中有未命中时，如果未命中属性中的一者 或一者以上为相关的，那么预取来自存储器层级的下一级的下一连续高速缓冲存储器 线。如果未命中属性中的一者或一者以上为不相关的，那么不预取下一连续高速缓冲存 储器线。请注意，一般来说，可预取不连续的高速缓冲存储器线。对预取高速缓冲存储 器线的确定可基于未命中属性、程序属性或此些属性的组合。举例来说，可使用来自分 支历史表或分支预测逻辑的信息来提供程序的执行流的属性，所述属性可用以确定是预 取连续的指令线还是非连续的指令线。

在另一个实施例中，如果指令高速缓冲存储器中的未命中是归因于非循序未命中 (例如，到不存在于指令高速缓冲存储器中的指令的地址的分支、子例行程序调用等)， 那么预取来自存储器层级的下一级的指令线。如果指令高速缓冲存储器中的未命中是归 因于循序未命中(例如，对不存在于指令高速缓冲存储器中的指令的循序存取)，那么 不进行预取操作。还请注意，预取操作的地址可为连续或非连续的指令线。

在另一个实施例中，如果指令高速缓冲存储器中的未命中发生在指令高速缓冲存储 器中为偶数的地址处，那么预取来自存储器层级的下一级的指令线。如果指令高速缓冲 存储器中的未命中发生在指令高速缓冲存储器中为奇数的地址处，那么不进行预取。

在另一个实施例中，如果指令高速缓冲存储器中的未命中是归因于在有大于或等于 X%进入高速缓冲存储器线中的地址处的非循序未命中，那么预取来自存储器层级的下 一级的指令线。如果指令高速缓冲存储器中的未命中是归因于有小于X%进入高速缓冲 存储器线中的地址处的未命中或为循序未命中，那么不进行预取。举例来说，如果未命 中发生在高速缓冲存储器线的末端附近的获取地址(例如，75%进入高速缓冲存储器线 中)处，那么从存储器层级的下一级预取指令线。进入高速缓冲存储器线中的百分数X 可固定为通过实验手段选择的值或可为可编程的，从而允许在操作中X%适于程序。举 例来说，如果对于图2的示范性说明来说，X%为62.5%，那么在具有八个指令线210 的情况下，所述线的62.5%与I4216相关联，五个指令进入所述线中。如果未命中发生 在I4216或更大的获取地址处，那么启用预取操作。如果未命中发生在I3215或更小的 获取地址处，那么不启用预取操作。在替代性实施方案中，如果指令高速缓冲存储器中 的未命中是归因于有大于X%进入高速缓冲存储器线中的地址处的未命中，那么进行预 取。对于X%=62.5%的上述实例来说，如果未命中发生在I5217或更大的获取地址处， 那么启用预取。否则，如果未命中处于小于或等于I4216进入高速缓冲存储器线中的地 址处，那么不进行预取。

在另一个实施例中，可组合未命中属性以确定是否进行预取。举例来说，如果指令 高速缓冲存储器中的未命中是归因于非循序未命中(例如，到不存在于指令高速缓冲存 储器中的指令的地址的分支、子例行程序调用等)，或如果指令高速缓冲存储器中的未 命中发生在指令高速缓冲存储器中为偶数的地址处，那么预取来自存储器层级的下一级 的指令线。否则，在未命中时，不进行预取。

用预取决策逻辑246来完成对是否进行预取的确定，预取决策逻辑246可与高速缓 冲存储器存取探针并行操作以确定所寻址的指令是否处于高速缓冲存储器中。预取决策 逻辑246可将未命中指示248、非循序操作(例如，分支、调用或返回操作)引起未命 中的非循序指示250、X%值252作为输入，且可包括(例如)所获取指令的IA224。未 命中指示248、非循序指示250和X%值252由L1Icache控制单元206提供。未命中与 非循序获取操作的获取地址相关联的确定可从来自处理器202的控制254获得。可进一 步从用于与指令相关联的非循序操作256(例如，分支、调用、返回等)的逻辑获得控 制254。或者，L1Icache控制单元206可将当前获取指令地址与先前获取指令地址进行 比较以确定获取是否与非循序操作相关联。请注意，预取决策逻辑246可位于指令高速 缓冲存储器外部，在需要时用信号进行连接。举例来说，预取决策逻辑可与产生指令地 址224的处理器202更紧密地相关联。

其它属性(例如，确定获取地址是否为偶地址高速缓冲存储器线)可基于偶数“E” 位230，其中对于偶数高速缓冲存储器线来说，E=0。“E”位230地址位位置或值可依 据指令高速缓冲存储器线阵列204中的线长度而变化。如图2所说明，两个位的B字段 234指示字中的多达四个字节，且三个位的I字段232指示线中的多达八个字。在此布 置下，“E”位230每八个字(对于32字节高速缓冲存储器线进行寻址的八个字)便改 变状态。

在其它实施例中，预取决策逻辑246可使高速缓冲存储器的探针确定待预取的高速 缓冲存储器线是否已经处于指令高速缓冲存储器中。如果与预取目标相关联的高速缓冲 存储器线已经处于高速缓冲存储器中，那么停止或阻止预取操作开始。

一旦已通过与指令高速缓冲存储器相关联的预取逻辑起始预取且由存储器层级的 较高级作出响应，那么可经由存储器数据总线(例如，存储器数据总线244)将多个指 令线转移到L1Icache。依据存储器数据总线接口244的物理总线宽度和所实施的信令协 议，可以固定大小数量或包(例如，32个字节、64个字节、128个字节、256个字节、 512个字节等等)来转移数据。通常，短数据包的多次转移通常比具有较大包大小的突 发转移的效率低，此归因于配置和发送数据过程中的额外开销。因此，在另一个实施例 中，当作出替代预取两个指令线而是(例如)在两个个别数据转移中进行预取的决策时， 请求长数据转移。与在较短独立转移中发送指令相比，在预取时的长数据转移使总转移 时间最小化。

图3为展示低复杂性预取过程300的流程图。通过描述来自处理器存储器复合体200 的元件可如何合适地协作以执行方法300来指示图3的方框与图2的元件之间的示范性 关系。

在方框302中，处理器(例如，处理器202)获取指令。在决策方框304中，确定 正获取的指令是否驻存在指令高速缓冲存储器中。举例来说，L1Icache控制单元206检 查确认指令是否存在。如果指令处于指令高速缓冲存储器中，那么过程300在方框306 中在高速缓冲存储器中获取指令且接着返回到方框302以等待下一个指令获取。举例来 说，将选定指令放置于指令输出总线240上且在处理器202中接收。

如果指令不处于指令高速缓冲存储器中，那么已检测到未命中情形。过程300前进 到决策方框308，其中，确定与当前指令地址相关联的下一个连续线是否已存在于指令 高速缓冲存储器中。可在不必直接存取L1Icache线阵列204的情况下在L1Icache控制 单元206中完成此确定。如果下一个连续线已处于L1Icache中，那么在方框310中将 获取发布到当前指令地址的存储器层级(例如，系统存储器层级208)。过程300接着返 回到方框302以等待下一个指令获取。并行地，在方框312中确定引起未命中的获取地 址属性。可在预取决策逻辑246中合适地完成此确定。

如果下一个连续线不处于高速缓冲存储器中，那么所述过程前进到决策方框314， 其中，确定在方框312中确定的未命中属性中的一者或一者以上是否相关。虽然可确定 多个属性，但固定或可编程功能可选择应用所述属性的子集或全部。如果未命中属性为 相关的，那么过程300前进到方框316以获取指令和来自下一级存储器的所确定预取高 速缓冲存储器线且返回到方框302以等待下一个指令获取。因此，当在决策方框314中 达到进行预取的决策时，不再(例如)以两次个别数据转移预取两个指令线，而是请求 长数据转移。如果未命中属性不相关，那么在方框318中将获取发布到当前指令地址的 存储器层级(例如，系统存储器层级208)。过程300接着返回到方框302以等待下一个 指令获取。

通过直接映射的高速缓冲存储器实施方案来说明对本文中所揭示的实施例的示范 性论述。请注意，可认为直接映射的高速缓冲存储器是组相关联高速缓冲存储器的特殊 情况(例如，单路组相关联高速缓冲存储器)。本文中所描述的原理还适用于N路组相 关联高速缓冲存储器(例如，4路组相关联高速缓冲存储器实施方案)。以类似方式，本 文中所描述的原理适用于全相关联高速缓冲存储器实施方案。

可通过通用处理器、数字信号处理器(DSP)、专用集成电路(ASIC)、现场可编程 门阵列(FPGA)或其它可编程逻辑组件、离散门或晶体管逻辑、离散硬件组件，或其 经设计以执行本文中所描述的功能的任何组合来实施或执行结合本文中所揭示的实施 例而描述的各种说明性逻辑区块、模块、电路、元件和/或组件。通用处理器可为微处理 器，但在替代实施方案中，所述处理器可为任何常规处理器、控制器、微控制器或状态 机。还可将处理器实施为计算组件的组合，例如，DSP与微处理器的组合、多个微处理 器的组合、一个或一个以上微处理器与DSP核心的联合，或任何其它此类配置。

结合本文中所揭示的实施例而描述的方法可直接以硬件、由处理器执行的软件模块 或以所述两者的组合来实施。软件模块可驻存在RAM存储器、快闪存储器、ROM存储 器、EPROM存储器、EEPROM存储器、寄存器、硬盘、可移除盘、CD-ROM，或此项 技术中已知的任何其它形式的存储媒体中。存储媒体可耦合到处理器，使得处理器可从 存储媒体读取信息以及将信息写入到存储媒体。在替代实施方案中，存储媒体可与处理 器整合。

虽然在实施例的上下文中揭示本发明，但将认识到，所属领域的技术人员可采用与 上文的论述和下文的权利要求一致的广泛多种实施方案。举例来说，主要在1级指令高 速缓冲存储器的上下文中揭示实施例。将了解，实施例还可使用2级指令高速缓冲存储 器、用于预取指令的2级统一高速缓冲存储器，或在存储器层级的对于处理器存储器复 合体来说为适当的其它级处。还将了解，指令高速缓冲存储器可与处理器核心整合或在 处理器核心外部。