包括用于早期远分支预测的影子缓存的单周期多分支预测

摘要

本发明公开了一种标识指令的方法，该方法包括：访问包括多个分支指令的多个指令。对于多个分支指令中的每个分支指令，生成相应的第一掩码，该第一掩码代表如果采用分支则执行的指令。生成相应的第二掩码，该第二掩码代表如果不采用分支则执行的指令。接收预测输出，该预测输出包括对于每个分支指令的相应的分支预测。对于每个分支指令，使用该预测输出以从相应的第一掩码和第二掩码之中选择相应的结果掩码。对于每个分支指令，如果预测先前分支越过后续分支而分支，则使所述后续分支的结果掩码无效。对所有结果掩码执行逻辑操作以产生最终掩码。使用该最终掩码以选择用于执行的指令子集。

说明书

技术领域

本发明总体涉及数字计算机系统，更具体地涉及一种用于选择 包括指令序列的指令的系统和方法。

背景技术

改进计算机架构性能是困难的任务。已经通过频率缩放、单指 令多数据(SIMD)、超长指令字(VLIW)、多线程和多处理器技术 寻求改进。这些方法主要以提高程序执行的吞吐量为目标。这些技术 中的许多技术要求软件显式地揭示并行性。与此相反，频率缩放对吞 吐量和延时两者进行提高而无需并行性的软件显式注释。近来，频率 缩放遭遇功率壁垒，因此通过频率缩放的改进是困难的。因此，除非 表达大量的显式软件并行化，否则难以增加吞吐量。

关于单线程程序执行，程序执行由规定程序控制流程的分支指 令所控制。程序指令序列当分支指令是有条件的或者分支目标是间接 的时是动态的。在这些情况下，对于处理器的提取逻辑而言，对于条 件分支发现是否采用分支。这使提取逻辑能够引入如下指令的序列， 这些指令紧随分支目标或者紧随分支指令本身。然而问题在于，在提 取阶段，分支的条件的结果在分支本身执行之前是未知的。

在尝试克服该问题时，现有技术设计已经实现分支预测逻辑以 预测分支的结果。在微处理器的提取阶段，预测的结果使提取逻辑能 够预期从何处带来下一指令序列。然而问题仍然存在，因为如果在相 同周期中要处理多于一个的条件分支，则提取阶段的逻辑很快变得非 常复杂。原因在于该处理需要本质上是顺序的。需要首先处理当前分 支以便知道从何处带来下一指令序列。该方面可能引起序列中的下一 分支被跳过。因而提取阶段中的处理分支的顺序本质给微处理器的单 线程执行速度施加了性能瓶颈。

发明内容

本发明的实施例实现一种使微处理器的提取逻辑的并行化成为 可能以在每个单周期中处理多个分支的算法(例如，方法和装置)。 该算法还基于也在该单周期内的分支预测而形成最终的指令序列。

在一个实施例中，本发明实现为一种标识预测的执行路径的指 令的方法。该方法包括访问包括多个分支指令的多个指令。对于多个 分支指令中的每个分支指令，生成相应的第一掩码，该第一掩码代表 如果采用所述分支则执行的指令。生成相应的第二掩码，该第二掩码 代表如果不采用所述分支则执行的指令。接收预测输出，该预测输出 包括对于所述多个分支指令中的每个分支指令的相应的分支预测。对 于所述多个分支指令中的每个分支指令，使用所述预测输出以从所述 相应的第一掩码和第二掩码之中选择相应的结果掩码。对于每个分支 指令，如果预测先前分支越过后续分支而分支，则使所述后续分支的 结果掩码无效。对所有结果掩码执行逻辑操作以产生最终掩码。基于 所述最终掩码从所述多个指令选择用于执行的指令子集。

前文是概要并且因此必然地包含细节的简化、概括和省略；因 而，本领域技术人员将理解该概要仅是说明性的而并非旨在是以任何 方式进行限制的。如仅由权利要求所限定的，本发明的其它方面、发 明特征和优点将在下文阐述的非限制性的详细描述中变得显而易见。

附图说明

在附图的各图中通过示例而非通过限制来图示本发明，在附图 中，相同附图标记指代相同单元。

图1示出由本发明的一个实施例操作的示例性指令序列。

图2示出根据本发明的一个实施例所图示的具有用于每个分支 的相应代码段的顺序指令。

图3示出根据本发明的一个实施例的用于标识和提取指令的过 程的步骤的概况流程图，这些指令包括具有多个分支的指令序列的执 行路径。

图4示出根据本发明的一个实施例的图示用于标识和提取指令 的过程的操作的流程图，这些指令包括具有多个分支的指令序列的执 行路径。

图5示出根据本发明的一个实施例的远分支缓存和远跳转目标 指令缓存。

图6示出根据本发明的一个实施例的示例性微处理器流水线的 示图。

具体实施方式

虽然已经结合一个实施例描述本发明，但是本发明并非旨在限 于这里阐述的具体形式。恰好相反，它旨在覆盖如可以被合理地包括 在如由所附权利要求限定的本发明的范围内的这样的备选、修改和等 效物。

在下文的详细描述中，已经阐述许多具体细节(诸如具体方法 顺序、结构、单元和连接)。然而将理解，无需利用这些和其它具体 细节以实现本发明的实施例。在其它情况下，已经省略或者尚未特别 详细地描述公知结构、单元或者连接以避免不必要地使本描述难以理 解。

在说明书内对“一个实施例”或者“实施例”的引用旨在指示结合 该实施例所描述的特定特征、结构或者特性包含于本发明的至少一个 实施例中。在说明书内各处出现的短语“在一个实施例中”不必都指代 相同的实施例，也不必是与其它实施例互斥的单独的或者备选的实施 例。另外，描述了各种特征，这些特征可以由一些实施例而不由其它 实施例展示出来。类似地，描述了各种要求，这些要求可以是对于一 些实施例但并不对于其它实施例的要求。

依据对计算机存储器内的数据位的操作的流程、步骤、逻辑块、 处理和其它符号表示而呈现下文详细描述的一些部分。这些描述和表 示是数据处理领域的那些技术人员用来向本领域其他技术人员最有 效地传达他们的工作实质的手段。这里，流程、计算机执行的步骤、 逻辑块、过程等一般设想是导致期望结果的步骤或者指令的自一致序 列。步骤是需要物理操控物理量的步骤。通常(尽管不一定)，这些 量采用计算机可读存储介质的电信号或者磁信号的形式并且能够在 计算机系统中被存储、传送、组合、比较和以别的方式被操控。主要 出于普遍使用的原因，将这些信号称为位、值、单元、符号、字符、 项、数等已经被证实有时是方便的。

然而应当谨记，所有这些术语和相似术语将与适当物理量相关 联，并且仅为应用于这些量的方便标签。除非如从下文讨论中显而易 见地另有具体明示，贯穿本发明而理解的是，利用诸如“处理”或者“访 问”或者“写入”或者“存储”或者“复制”等术语的讨论指的是计算机系 统或者相似电子计算设备的动作和过程，该电子计算设备对被表示为 计算机系统的寄存器和存储器以及其它计算机可读介质内的物理(电 子)量的数据进行操纵并变换成同样地被表示为计算机系统存储器或 寄存器或者其他此类信息存储、传输或显示设备内的物理量的其他数 据。

本发明的实施例实现一种使微处理器的提取逻辑的并行化成为 可能以在每个单周期中处理多个分支的算法(例如，方法和装置)。 该算法还基于也在该单周期内的分支预测而形成最终的指令序列。执 行该任务而无需以顺序方式处理分支(例如，不以每周期一个分支的 速率逐个分支地处理指令序列)。反而，本发明的实施例使得每周期 多个分支的处理速率成为可能，由此使得大量指令提取和分配带宽成 为可能。应当注意，单个分支指令的处理可以不在单周期内完成，然 而处理器硬件可以每个周期处理多个分支，由此实现每周期多个分支 的吞吐量。以该方式，分支处理速率是每个周期，但是延时在单周期 内不是必需的。图1和图2示出由本发明的实施例操作的示例性指令 序列。随后，图3示出根据本发明的一个实施例的用于标识和提取指 令的过程的步骤的概况流程图，这些指令包括具有多个分支的指令序 列中的执行路径。

图1示出由本发明的一个实施例操作的示例性指令序列。如图 1中所示，指令序列100包括从图1的顶部进行至底部的16个指令。 如图1中可见，序列100包括四个分支指令101-104。

本发明的实施例的一个目的是在每个单周期中处理整组指令。 根据不同实施例，这些指令可以包括原生指令(例如，微处理器架构 的原生指令，诸如x86指令、MIPS指令等)。备选地，这些指令可 以包括微代码。

在一个实施例中，在相同单周期中处理整组16个指令。如前所 述，指令序列包括的分支越多，出现并且需要处理的组合和可能的所 得序列就越多。下面在图2中图示该特性。

图2示出根据本发明的一个实施例而图示的具有用于每个分支 的相应代码段的顺序指令100。如上所述，在指令序列中呈现的分支 越多，需要消除歧义的指令序列的可能性和组合就越多。此外，更多 分支带来可能跳过更多分支的可能性。

在图2中图示这一点，该图示出如果采用分支c1则出现的第一 所得序列“1”。如这里指代的那样，如果程序执行流程移向分支的目 标，则采用该分支。这由在每个分支指令的末尾处的括号内的两个数 字指示。例如，分支c1具有目标11并且造成跳过接下来的6个指令。 类似地，分支c2具有目标10并且造成跳过接下来的2个指令，以此 类推。

因此，示出第二所得序列“2”，并且如果采用分支c2则出现该 第二所得序列“2”。示出第三所得序列“3”作为如果采用分支c3则出现 该序列。类似地，示出第四所得序列“4”作为如果采用分支c4则出现 该序列。

如图2中所示，来自分支的所得序列相互重叠。这说明了指令 序列中的先前分支可以通过跳过后续分支而使该后续分支无效的方 式。因此如果采用分支c1，则跳过两个后续分支c2和c3并且由此使 这些分支无效或者使这些分支被呈现为与指令序列的执行路径无关。 类似地，如果不采用分支c1而采用分支c2，则将跳过后续分支c3并 且由此使该分支无效。

本发明的实施例实现一种使微处理器的提取逻辑的并行化成为 可能以在每个单周期中处理诸如分支c1至分支c4之类的多个分支的 算法(例如，方法和装置)。该算法还基于也在该单周期内的对于c1 至c4的分支预测而形成最终的指令序列。下文在图3中描述该算法。

图3示出根据本发明的一个实施例的用于标识和提取指令的过 程300的步骤的概况流程图，这些指令包括具有多个分支的指令序列 的执行路径。过程300示出了例如微处理器的指令提取模块的示例性 操作步骤。

过程300始于步骤301，在该步骤中，提取模块访问包括多个 分支指令的多个指令。如上所述，访问指令序列，其中该指令序列包 括多个分支指令(例如，图1的序列100的分支c1-c4)。

在步骤302中，对于多个分支指令中的每个分支指令，生成相 应的第一掩码。该第一掩码代表如果采用该特定分支则执行的指令。

在步骤303中，对于每个分支指令，生成相应的第二掩码。该 第二掩码代表如果不采用该特定分支则执行的指令。因此，在步骤303 结束时，指令序列内的每个分支将具有两个掩码(一个代表如果采用 该分支则执行的指令的掩码，以及另一个代表如果不采用该分支则执 行的指令的掩码)。

在步骤304中，由提取模块接收分支预测输出。该分支预测输 出对于指令序列的每个分支给出预测的采用状态或者不采用状态。

在步骤305中，分支预测输出用来在用于指令序列的每个分支 指令的第一掩码与第二掩码之间进行选择。例如，对于给定的分支， 如果分支预测输出指示将采用分支，则将选择用于分支的第一掩码。 如果分支预测输出指示将不采用分支，则将选择用于分支的第二掩 码。由分支预测输出所选择的这些掩码被称为结果掩码。

在步骤306中，对于指令序列的每个分支指令，如果预测先前 分支越过或者跳过后续分支，则使该后续分支的结果掩码无效。如上 所述，指令序列中的先前分支可以通过跳过后续分支来使该后续分支 无效。

在步骤307中，对所有结果掩码执行逻辑操作以产生最终掩码。 因此，该最终掩码标识如下指令，这些指令包括指令序列中的正如由 序列内的多个分支的预测结果所确定的执行路径。

在步骤308中，最终掩码用来从包括指令序列的多个指令之中 选出用于执行的指令子集。在这样做时，由提取模块产生紧凑的执行 路径指令序列。在一个实施例中，在每个单周期中产生该紧凑的执行 指令序列。

图4示出根据本发明的一个实施例的图示用于标识和提取指令 的过程的操作的流程图400，这些指令包括具有多个分支的指令序列 的执行路径。

如上所述，本发明的实施例的目的是在一个周期中处理整组指 令。在图4中图示这一点，其中由提取模块在一个周期中处理指令序 列100的所有16个指令。标识符401说明提取模块标识其中的每个 分支的方式。从指令序列100的顶部开始，标记所标识的第一分支、 标记所标识的第二分支并且以此类推，以使序列减少到仅为条件操作 (例如，分支)。仅用零标注普通指令(例如，除了分支指令之外的 指令)。

图4还图示追踪分支的段的分支段表402。在分支段表的左手 侧，每个对应分支具有开始于序列中的该分支编号并且结束于后续分 支编号的段。因此，如图4中所示，分支c1具有第一段5-7，该段是 如果不采用该分支则将执行的指令。类似地，在右手侧，分支c1具 有第二段11-14，该段是如果采用该分支则将执行的指令。用x标注 普通指令。

如上所述，对于多个分支指令中的每个分支指令，生成相应的 第一掩码。该第一掩码代表如果采用该特定分支则执行的指令。类似 地，对于每个分支指令，生成相应的第二掩码。该第二掩码代表如果 不采用该特定分支则执行的指令。因此，在步骤303结束时，指令序 列内的每个分支将具有两个掩码(一个代表如果采用分支则执行的指 令的掩码，以及另一个代表如果不采用分支则执行的指令的掩码)。 在一个实施例中，这些掩码包含位集合。

分支预测部件403检查指令段内的分支并且预测每个分支将被 采用(“T”)还是不被采用(“NT”)。在本实施例中，由提取模块的 比较和跳过逻辑部件404对分支预测部件403的输出进行处理。通过 比较和跳过模块404的操作，分支预测输出用来在用于指令序列的每 个分支指令的第一掩码或者第二掩码之间进行选择。

图4示出结果掩码410。如上所述，对于给定的分支，如果分 支预测输出指示将采用分支，则将选择用于分支的第一掩码。如果分 支预测输出指示将不采用分支，则将选择用于分支的第二掩码。由分 支预测输出所选择的掩码被示出为结果掩码410。

先前分支可以使结果掩码无效。在图4中示出这一点，其中结 果掩码410的顶部示出它们的相应状态为有效且采用(“VT”)或者无 效(“NV”)。如上所述，对于指令序列的每个分支指令，如果预测 先前分支越过或者跳过后续分支，则使该后续分支的结果掩码无效。 类似地，指令序列中的先前分支可以通过跳过后续分支来使该后续分 支无效。因此，即使由分支预测输出可以预测结果掩码为采用(“T”)， 但是先前分支可以然后使该结果掩码无效。在图4中示出这一点，其 中即使预测分支c3为采用，但是比较和跳过逻辑404使c3的结果掩 码无效。在图4的实施例中，掩码无效导致掩码的所有序列位置(例 如，1至16)用1填充。

图4还示出最终掩码420的输出指令序列。如上所述，提取模 块对所有结果掩码执行逻辑操作(例如，逻辑与(AND)操作)以产 生最终掩码。因而，该最终掩码标识如下指令，这些指令包括指令序 列中的正如由序列内的多个分支的预测结果所确定的执行路径。在一 个实施例中，仅对有效的结果掩码执行逻辑操作。在另一实施例中， 对所有掩码执行逻辑操作，其中无效掩码用全1填充。最终掩码420 用来从包括指令序列的多个指令之中选出用于执行的指令子集。在这 样做时，由提取模块产生紧凑的执行路径指令序列。在一个实施例中， 在每个单周期中产生该紧凑的执行指令序列。

应当注意，本发明的实施例的算法基于也在单周期内的分支预 测形成最终的指令序列。执行该任务而无需以顺序方式处理分支(例 如，不以每周期一个分支的速率逐个分支地处理指令序列)。

在一个实施例中，通过将每个分支与如下位进行关联来有助于 该算法，该位对指令序列中的分支位置进行标识。使用那些位，将每 个分支与2个段进行关联(例如，分支段表402)。如上所述，第一 段是跟随分支直至下一分支的指令序列。第二段是从分支的目标开始 直至下一分支的指令序列。在分支的目标(例如，正如由从当前分支 位置的偏移所指示的)旁边的分支标识位用来创建那些段。同时，在 分支预测表中并行查找所有分支以发现它们的预测；那些分支预测与 典型的单分支预测相似。

还应当注意，在一个实施例中，并行比较每个分支位置与先前 分支目标以标识该分支是在先前分支的范围以内还是在先前分支的 范围以外。然后确定该分支是否被从分支位置上跳转的先前有效分支 的目标跳过。通过分支预测的并行查找使该信息有资格来发现跳过哪 些分支并且因此在最终的指令序列中不包括它们的序列形成。最终的 指令序列如图4中所示由通过使用分支预测选择每个有效的(例如， 由于跳过它的先前有效分支而未被跳过)分支的预测段以生成那些分 支的结果掩码来汇编相关指令段而形成。

图5示出根据本发明的一个实施例的远分支缓存501和远跳转 目标指令缓存502。图5还示出远分支预测器503。

图5的实施例示出整个微处理器流水线的优化，其中向提取模 块(例如，指令序列消歧逻辑)呈现2个或者更多缓存行。在图5的 实施例中，先从多个缓存行收集指令。提取始于指向指令序列的开始 缓存行，在图5中示出为缓存行X。从缓存结构501提取该开始缓存 行和下一后续缓存行，缓存行X+1(或者更多)。如果指令序列恰好 具有在下一缓存行(例如，缓存行X+1)以外的远跳转，则远跳转目 标指令缓存结构502用来以远目标缓存行(例如，缓存行Y)替换该 下一缓存行。如果来自远分支预测器503的预测指示将采用远目标缓 存行，则选择远目标缓存行指令序列。否则，由提取模块忽略远目标 缓存行Y。

在另一实施例中，取代在缓存结构中存储全部缓存行，可以将 缓存行的部分串接在一起并且存储于缓存结构中。在一个实施例中， 在分支边界将缓存行的部分串接在一起以形成可以用来提高有效指 令序列的密度的全新缓存行。为了使得该功能成为可能，分支预测信 息与缓存行一起存储以声明如何将缓存行的部分进行串接，从而当实 际分支结果已知时可以验证那些预测。考虑到新串接的缓存行部分， 还可以修改或者添加远分支以向新目标进行跳转，由此提高传入指令 的前端吞吐量。

在一个实施例中，可以在2个阶段上完成这一点。第一阶段从 缓存结构提取多个缓存行。然后向指令序列汇编器呈现选择的缓存 行，该指令序列汇编器基于动态分支预测使分支消歧并且汇编最终的 指令序列。指令序列缓冲器结构设置于指令序列消歧逻辑的输出。指 令序列缓冲器用作对于流水线的下一阶段的缓冲器并且还有选择地 存储用于将来使用的某些指令序列。指令序列缓冲器可以存储频繁预 测的序列(当导致该序列的分支是可高度地预测的时)或者频繁错过 预测的序列(当导致该序列的分支是可高度地错过预测的时)的最终 汇编段。

该指令序列缓冲器将提高带宽并且减少对于前端的指令提取模 块的延时，因为在缓冲器中存储的那些序列无需经历使用分支预测表 和掩码的前述指令定序过程。

图6示出根据本发明的一个实施例的示例性微处理器流水线 600的示图。微处理器流水线600包括实现如上所述的用于标识和提 取包括执行的指令的过程的功能的提取模块601。在图6的实施例中， 在提取模块之后是解码模块602、分配模块603、调度模块604、执行 模块605和指令引退模块606。应当注意，微处理器流水线600仅为 实现上述本发明的实施例的功能的流水线的一个示例。本领域技术人 员将认识到，可以实现包括上述解码模块的功能的其它微处理器流水 线。

已经出于说明的目的参照具体实施例描述了前述说明书。然而， 上文所示讨论并非旨在是详尽的或者将本发明限于所公开的特定形 式。许多修改和变化鉴于上述教导是可能的。选择和描述实施例以便 最好地说明本发明的原理及其实际应用，由此使本领域其他技术人员 能够借助可以与设想的特定使用相适应的各种修改来最好地利用本 发明和各种实施例。