分支预测器和用于操作分支预测器的方法

摘要

提供一种分支预测器和用于操作分支预测器的方法。分支预测器包含可用于访问指令高速缓存的指令字节块的块地址和指令字节块内的第一/第二字节偏移。散列逻辑将分支转移历史(branch pattern)和由块地址分别和各第一/第二字节偏移形成的第一/第二地址通过散列运算以生成各第一/第二索引。条件分支预测器接收第一/第二索引，并响应于此分别提供指令字节块中的第一/第二条件分支指令的第一/第二方向预测。在一个实施例中，分支目标地址高速缓存(BTAC)提供字节偏移，且第一/第二方向预测静态地与也由BTAC提供的第一/第二目标地址相关联。替代地，字节偏移是预定值，且第一/第二方向预测基于由BTAC提供的字节偏移的相对尺寸动态地与第一/第二目标地址相关联。

说明书

技术领域

本发明涉及处理器设计的领域，特别是涉及一种由块地址和多个字节偏移形成的多个地址与分支指令历史转移通过散列运算形成的多个条件分支指令预测器索引的分支预测器。

背景技术

在处理器设计的领域中对分支指令预测器的预测精度要求越来越高是公知的。随着处理器流水级、高速缓存存储器访问延迟和超标量体系结构中的指令发布宽度的增加，该需求更加强烈。分支指令预测器包括预测目标地址，和预测条件分支指令方向，即跳转或者不跳转。

典型地，以相对大的块为单位从指令高速缓存器中取指，例如，一次性从指令高速缓存取出16个字节指令。因此，在取出的指令块中可能存在多个分支指令。需要精确地预测取出的块中存在的分支指令，并预测它们的目标地址和它们的方向。因为块内分支指令的位置是相对随机的，所以这是有挑战的。对于固定长度指令如此，但是对于允许指令是可变长度的指令集架构(例如，x86或者ARM)尤其如此。例如，一条x86分支指令可能位于与从指令高速缓存取出的指令字节块的任何字节偏移处。

发明内容

根据本发明的一方面，提供一种分支预测器。该分支预测器可以包括：可用于访问处理器的指令高速缓存的指令字节块的块地址；所述指令字节块内的第一字节偏移；所述指令字节块内的第二字节偏移；散列逻辑，散列分支转移历史和由块地址和第一字节偏移形成的第一地址以生成第一索引，以及散列分支转移历史和由块地址和第二字节偏移形成的第二地址以生成第二索引；和条件分支预测器，接收第一索引和第二索引，并响应于此分别提供所述指令字节块中的第一和第二条件分支指令的第一和第二方向预测。

根据本发明的另一方面，提供一种用于操作分支预测器的方法。所述方法可以包括：使用块地址以访问处理器的指令高速缓存的指令字节块；提供所述指令字节块内的第一字节偏移和第二字节偏移；散列分支转移历史和由块地址和第一字节偏移形成的第一地址以生成第一索引，和散列分支转移历史和由块地址和第二字节偏移形成的第二地址以生成第二索引；和由条件分支预测器响应于接收第一索引和第二索引分别提供所述指令字节块中的第一条件分支指令和第二条件分支指令的第一方向预测和第二方向预测。

附图说明

图1是图示具有分支预测器的处理器的框图。

图2是图示图1的分支预测器的操作的流程图。

图3是图示具有常规的分支预测器的处理器的框图。

图4是图示具有根据替代实施例的分支预测器的处理器的框图。

图5是图示图4的分支预测器的操作的流程图。

具体实施方式

词汇

散列(hash)两个或更多个实体，比如地址和分支转移历史(branch pattern)，指的是关于两个或更多实体中的每一个的一个或多个位执行一个或多个与/或逻辑运算以生成具有比两个或更多实体中最大的实体的位数更少位数的结果。一个或多个与/或逻辑运算可以包括，但不限于：实体的预定位的选择；包括异或(XOR)、NAND、AND、OR、NOT、循环移位平移的布尔逻辑运算；和包括加、减、乘、除、取模的算术运算。为了通过示例图示，假定100位分支转移历史，32位地址，且结果是10位索引。散列地址和分支转移历史(即，对地址和分支转移历史进行散列运算)可以包括将分支转移历史的位[9:0]和位[19:10]与分支指令地址的位[9:0]异或。

实施例中的分支预测器，其通过使用条件分支指令地址与分支转移历史散列运算后的值为索引，得到的方向预测，精确度高于只使用条件分支指令的部分地址参与散列算法来索引条件分支预测器的结果。

现在参考图1，示出了具有分支预测器100的处理器103的框图。处理器103包括取指单元101、指令高速缓存102和分支预测器100或者分支预测单元100。该分支预测器100包括分支转移历史104、散列逻辑106、分支目标地址高速缓存(branch target addresscache,BTAC)108、条件分支预测器112和控制逻辑114。

取指单元101生成提供给指令高速缓存102、BTAC 108和散列逻辑106的块地址122。指令高速缓存102响应于块地址122提供架构指令字节块124。在一个实施例中，指令字节块124包括16个字节，虽然可考虑其他实施例。指令字节块124可以包括多个架构分支指令，如以下更详细地讨论的。如果控制逻辑114将目标地址128或者最终结果128提供到取指单元101，则取指单元101基于目标地址128更新块地址122，以从非顺序程序位置取出，这被称为重定向。否则，即，在没有到目标地址128的重定向的情况下，取指单元101在从指令高速缓存102取出指令字节块124之后递增块地址122。从处理器103向后面的流水线提供指令字节块124。

优选地，指令字节块124由指令队列(未示出)接收。指令字节从队列输出到指令译码器(未示出)，该指令译码器将架构指令124翻译为提供给执行流水线(未示出)以用于执行的微指令。队列缓冲多个指令字节块124以用于提供到指令译码器。只要指令缓存队列中具有可以输出给指令译码器的指令，指令译码器就可以把翻译之后的微指令提供到执行流水线处理，处理器就能有效地利用执行流水线。因此，分支预测器100的目标是避免指令队列过于接近地变空，以使得指令译码器不具有足够的指令来翻译以保持执行流水线良好地使用。

在一个实施例中，执行流水线是包括一个或多个架构寄存器、寄存器重命名单元、重排序缓冲器、保留站、多个执行单元和用于发射微指令到执行单元的指令调度器的超标量乱序执行流水线。执行单元可以包括以下执行单元类型的一个或多个：整数单元、浮点单元、媒体单元、单指令多数据(SIMD)单元、分支执行单元、访存单元。优选地，处理器103还包括存储器子系统，其包括存储器次序缓冲器、地址变换高速缓存(tanslation-lookasidebuffer,TLB)、tablewalk引擎、多级缓存和各种请求队列，例如一个或多个存储器访问队列、存储器存储队列、填充队列和/或存储器监听队列。

BTAC 108之前执行过的历史分支指令以及它们的分支目标地址、方向、在字节块中的位置124，为当前的字节块做预测。BTAC 108包括条目的一个或多个存储器阵列。优选地，该一个或多个存储器阵列组织结构是多路组相联的多侧的高速缓存。如以下更详细地描述的。每个条目保存与分支指令相关联的分支历史信息。在一个实施例中，BTAC 108中的每个条目包括以下字段：有效位、标签、分支类型、字节偏移、跨字节块标志位和目标地址。

分支指令的方向是分支是否跳转。也就是，如果分支指令不跳转，则程序流顺序地进行，即，沿着指令不跳转的方向，取该不跳转分支指令后面的一条指令地址。进行到在不跳转的分支指令的地址之后的地址顺序跟随分支指令的下一指令。但是，如果分支指令跳转，则该分支指令指令处理器103将程序流转向到目标地址而不是继续正常的顺序程序流。在无条件分支指令的情况下，比如调用、返回或者无条件跳转指令，总是跳转的。在条件分支指令的情况下，如果满足由条件分支指令指定的条件则跳转；否则，不跳转。条件跳转指令跳转的条件通常是处理器的一些架构状态，例如，架构条件标记是否满足标准，例如，大于、小于、等于、负的、正的、进位、零、溢出等。

可以以多种方式指定目标地址。在返回指令的情况下，目标地址(或者返回地址)典型地从堆栈弹出，该返回地址先前响应于先前执行的调用指令推入到该堆栈上。典型地，返回地址是调用指令之后的下一顺序指令。目标地址也可以指定为相对于分支指令的地址本身的有符号偏移。目标地址也可以保存在由通常被称为的间接分支指令的分支指令指定的架构寄存器中。

有效位指示条目是否有效。当分支指令由执行流水线执行完毕之后，将关于所执行的分支指令的相关信息传递回到分支预测器100时，分支预测器100确定用于该分支指令的条目是否已经存在于BTAC 108中。如果否，则分支预测器100为该分支指令在BTAC108中分配一个条目，并设置有效位，填充分配条目的各个字段。相反地，如果BTAC 108的条目预测指令字节块124中分支指令的存在，但执行流水线确定分支指令不再在指令字节块124中，则分支预测器100使该条目无效。因为操作系统加载新程序到与指令字节块124对应的存储器位置中，或者执行自修改代码，所以这是可能发生的。一旦用于分支指令的有效条目存在于BTAC 108中，BTAC 108就可以继续做出关于随后取出的指令字节块124中分支指令的存在的预测，以及做出取出的分支指令的方向和目标地址的预测。但是，如以下更详细地描述的，通常条件分支预测器112而不仅仅是BTAC 108用于预测条件分支指令的方向。

标签字段保存分支指令的地址的高位。块地址122的低位用于索引BTAC 108中的组。块地址122的高位与所选的组中的条目的标签比较。如果有效条目的标签匹配块地址122的标签位，则BTAC 108指示匹配条目的命中，并提供命中的分支指令的所预测的方向、目标地址和字节偏移，如以下更详细地描述的。

分支类型指示分支指令的类型，比如调用(例如x86CALL指令)、返回(例如，x86RET指令)、无条件跳转(例如，x86 JMP指令)和条件跳转(例如，x86 Jcc指令)。在一个实施例中，条目还包括可以在分支类型字段中编码的偏离位和强制偏离位(未示出)。当执行流水线第一次执行条件分支指令时，强制偏离位且以首次执行的正确方向填充偏离位。在后来包含该分支指令的块再次被取出，即，保存分支指令预测信息的条目命中，如果强制偏离位为高，则使用BTAC 108中偏离位为预测方向。第一次偏离位不正确地预测分支指令的方向时清除强制偏离位。优选地，每个BTAC 108条目还包括用于做出方向预测的其他字段。在一个实施例中，每个条目包括2位饱和双向计数器(saturating up-down counter)，其每次分支跳转向上计数且每次分支不跳转向下计数。如果计数器的高位被置位，则BTAC 108预测分支指令跳转；否则，BTAC 108预测分支指令不跳转。

字节偏移指定指令字节块124内分支指令的位置。优选地，字节偏移指定指令字节块124内分支指令的第一字节的位置。在一个实施例中，架构指令的长度是可变的，且特别地分支指令可以是不同长度，例如，如在x86指令集架构中那样。在可变长度指令集架构的情况下，分支指令可以跨越其开始的指令字节块124，以使得其在下一顺序指令字节块124中结束。在这种情况下，在分支指令的条目中置位跨块位。

控制逻辑114使用命中分支指令的字节偏移以确定指令字节块124中首先看到、跳转的分支指令(如果有的话)。“首先”指的是程序次序中的首先。“看到”指的是未看到位于当前架构指令指针值之前的分支指令的事实。因此，例如，如果对具有在不久将要取出的指令字节块124内字节偏移7的分支目标128进行重定向，则未看到BTAC 108预测在取出的指令字节块124内存在的任何分支指令参见，即，即使它们预测为跳转，它们不会被考虑，因为它们不在重定向的地址128处的指令的新线程中出现。如以下更详细地描述的，图1的实施例的散列逻辑106有效利用BTAC108预测出的字节偏移得到的地址来进行散列算法以产生到条件分支预测器112中的更精密的索引以尽可能潜在地改进条件分支预测器112的精度。

目标地址是基于分支指令的执行历史进行预测的分支指令转移地址。优选地，当执行流水线执行分支指令时，分支预测器100以正确的目标地址更新分支指令的BTAC 108条目。在一个实施例中，分支预测器100还包括用于预测返回指令的返回地址的调用/返回堆栈(未示出)，且如果BTAC 108指示分支指令的分支类型是返回指令，则控制逻辑114选择由调用/返回堆栈而不是由BTAC 108提供的返回地址。

优选地，BTAC 108布置为两“侧”，称为侧A和侧B。对于从指令高速缓存102取出的给定指令字节块124，BTAC 108的每一侧仅至多提供单个命中目标地址/字节偏移对。这是由于，对于从指令高速缓存102取出的给定指令字节块124，更新BTAC 108的逻辑允许BTAC108的一侧中的至多一个条目，即，BTAC 108更新逻辑仅允许取出的指令字节块内的最多一个分支指令占有每一侧的一个条目。因此，虽然BTAC 108的一侧可以具有相关性，即，具有多路组相联更新逻辑也仅允许该侧的多路中的一路有用于取出的指令字节块124中的分支指令的有效条目。在一个实施例中，BTAC 108具有两侧，且两侧中的每一个拥有具有两条路的的存储体。在替代实施例中，BTAC 108拥有具有四条路的单个存储器阵列，且其中两条路被分组为一侧且另外两条路被分组为另一侧。类似地，条件分支预测器112也可以在其一个或多个存储器阵列中具有相关性，和对于从指令高速缓存102取出的给定指令字节块124，条件分支预测器112每一侧仅提供至多单个命中方向预测。这是由于，对于从指令高速缓存102取出的给定指令字节块，条件分支预测器112更新逻辑允许条件分支预测器112的一侧中的至多一个条目，即，条件分支预测器112更新逻辑仅允许取出的指令字节块内的单个分支指令具有每一侧中的条目。

响应于块地址122，BTAC 108输出命中指示器132，侧A目标地址A 144和侧B目标地址B 146(集合地称为目标地址144/146)，和侧A字节偏移A154和侧B字节偏移B 156(集合地称为字节偏移154/156)，将其全部提供给控制逻辑114。优选地，命中指示器132指示BTAC108中哪一路中的标签与块地址中标签匹配上了。虽然未示出，优选地BTAC 108还向控制逻辑114提供对于每一侧的方向预测。在图1的实施例中，有益地，字节偏移154/156也被提供给散列逻辑106。

散列逻辑106除了块地址122和字节偏移154/156之外，还接收也被称为分支路径历史104的分支转移历史104。假定N位的分支转移历史104，分支转移历史104是以程序次序的最近N个分支指令中的每一个的方向的全局历史。在一个实施例中，如果跳转相应的分支指令则设置分支转移历史104的位，且如果不跳转分支指令则清除。在一个实施例中，N是100。如以下描述的，分支转移历史104可以以分支指令的地址(或者在相对于图3和图4描述的实施例的情况下其近似)进行散列，以获得到条件分支预测器112中的索引，以便不仅包括正被讨论的分支指令的历史，而且包括它周围的其他分支指令的全局历史，以增加预测分支指令的结果的精度。

在一个实施例中，每次分支指令提交时都用执行后的正确方向更新到分支转移历史104。在替代实施例中，每次预测分支指令时以预测的方向更新分支转移历史104，即使预测的方向可能是推测性的。前一实施例具有更精确这个优势，在于其仅包含可以提交的那些分支指令的信息，而不包含仅从预测时的预测方向而不考虑分支指令是否可以提交的角度更新分支转移历史的信息。前一实施例的缺点在于在当从指令高速缓存102取出分支指令X的实例时和当分支指令X的实例提交时之间可能有数十量级的时钟周期；因此，对于在取出分支指令X的实例之后和提交分支指令X的实例之前取出的分支指令做出的任何预测将不具有包括分支指令X的实例的方向的全局分支历史的益处。相反地，后一实施例具有的优点在于使用包括全部N个先前分支指令的全局分支转移历史104做出分支指令的预测，虽然其缺点在于分支转移历史104中可能包含那些最终不会得到提交的分支指令的历史。

散列逻辑106接收块地址122、字节偏移154/156和分支转移历史104并散列它们以生成第一索引A 164和第二索引B 166。更具体地说，优选地，散列逻辑106加上侧A字节偏移A 154与块地址122以形成指令字节块124中第一条件分支指令的存储器地址，并散列分支转移历史104和第一条件分支指令的地址以生成第一索引A 164；类似地，散列逻辑106加上侧B字节偏移B 156与块地址122以形成指令字节块124中第二条件分支指令的存储器地址，并散列分支转移历史104和第二条件分支指令的地址以生成第二索引B 166。将索引164/166提供给条件分支预测器112。优选地，散列逻辑106是可综合的组合逻辑。以下在条件分支预测器112的描述之后更加详细地描述散列。

条件分支预测器112从散列逻辑106接收索引154/156并从取指单元101接收块地址122，且响应于该块地址生成命中指示器172，侧A方向预测A 174和侧B方向预测B 176。条件分支预测器112包括保存用于做出条件分支指令的方向预测的信息的至少一个存储器阵列。在一个实施例中，类似BTAC108，条件分支预测器112布置为两侧，称为侧A和侧B。优选地，条件分支预测器112中的每个条目包括方向预测位。在一个实施例中，方向预测位是每次条件分支指令跳转则递增且每次条件分支指令不跳转则递减的饱和双向计数器(例如，3位)的最高有效位。在替代实施例中，饱和双向计数器的更新是通过依赖于条件分支指令是否正确预测的结果的状态机控制的。优选地，条件分支预测器112存储器阵列是包括两个端口的双端口存储器阵列，一个端口用于侧A且一个端口用于侧B，其接收各个侧A/B的索引164/166并响应于此提供各个侧A/B的方向预测174/176。在一个实施例中，条件分支预测器112的每个条目包括标签。由索引164/166选择的组中每一路中的标签与块地址122的标签部分比较以确定是否发生有效条目命中。在一个实施例中，不是简单地是分支指令地址的高位，每个标签是通过以分支指令地址的高位散列分支转移图案的位而生成的值。来自每一侧的命中条目的方向预测位作为各个方向预测174/176提供，将其与命中指示器172一起提供给控制逻辑114。

在一个实施例中，条件分支预测器112包括多个存储器阵列，也称为表，其生成每一侧的相应的多个方向预测，且对于每一侧仅多个方向预测之一被选为方向预测174/176。在这种实施例中，散列逻辑106生成多对索引164/166，并将它们提供到条件分支预测器112。例如，如果条件分支预测器112具有五个表，则散列逻辑106将五对索引164/166提供到条件分支预测器112。

在一个实施例中，条件分支预测器112是标签的几何长度(TAGE)预测器。在TAGE预测器实施例中，多个表中的每一个是单个双端口静态随机存取存储器(SRAM)。另外，表中的每个条目包括与块地址122的标签部分比较的标签。此外，每个表以由散列逻辑106生成的它自己的不同的一对索引164/166来索引，且使用不同长度的分支转移历史104生成索引。更具体地说，TAGE预测器的基本表简单地以由块地址122和字节偏移154/156的相加结果形成的条件分支指令地址的低位进行索引，即，不以分支转移历史104进行散列。然而，其他表从散列逻辑106接收它们各自的索引对164/166，且已经使用与其他表不同位数的分支转移历史104散列得到了每个表的索引对164/166。也就是，用每一个块地址对应的地址对与不同长度的分支转移历史进行散列运算以生成用于不同表的不同索引对164/166。例如，假定每个表的索引164/166是10位且分支转移历史104是100位。对于第一个表，散列逻辑106关于分支转移历史104的位[9:0]与分支指令地址的位[9:0]执行布尔异或(XOR)运算；对于第二个表，散列逻辑106执行分支转移历史104的位[9:0]与分支转移历史104的位[19:10]再与分支指令地址的位[9:0]的XOR的散列运算；对于第三个表，散列逻辑106执行分支转移历史104的位[9:0]与分支转移历史104的位[19:10]再与分支转移历史104的位[29:20]再与分支转移历史104的位[39:30]再与分支指令地址的位[9:0]的XOR的散列运算；以此类推。本实施例是举例性表示了分支转移历史和分支指令地址的散列算法，，其它实施例可以使用其他的散列算法，其中散列逻辑106使用分支转移历史和/或分支指令地址的位的不同集合并执行XOR以外的其他算术运算和/或逻辑运算。

控制逻辑114跳转BTAC命中指示器132、目标地址154/156、字节偏移154/156、条件分支预测器命中指示器172和方向预测174/176，并以程序次序确定指令字节块124中第一个有效、看到、跳转的分支指令(如果有的话)。如果找到这种分支指令，则控制逻辑114用信号通知取指单元101以将程序流重定向到由控制逻辑114生成的最终结果128；否则，取指单元101从下一顺序块地址122取出指令字节块124。

现在参考图2，示出了图示图1的分支预测器100的操作的流程图。图2意在图示以向下方式的时间的推移，和在水平地彼此平行的块中执行的动作实质上彼此并行地发生。流程始于块202。

在块202，取指单元101生成块地址122并将其提供到图1的指令高速缓存102、BTAC108和散列逻辑106。流程并行地进行到块204和206。

在块204，指令高速缓存102输出指令字节块124。在一个实施例中，指令高速缓存102具有从声明块地址122的时间直到指令高速缓存102提供指令字节块124为止3个时钟周期的等待时间，虽然可考虑其他实施例。流程进行到块208。

在块206，BTAC 108输出到每一侧，即，对于侧A和侧B的预测的目标地址144/146、字节偏移154/156和命中132。在一个实施例中，BTAC 108也具有从声明块地址122的时间直到BTAC 108提供其输出为止3个时钟周期的等待时间，虽然可考虑其他实施例。流程进行到块208。

在块208，散列逻辑106以分支转移历史104散列由块地址122和字节偏移154/156形成的两个分支指令地址中的每一个以生成侧A和侧B的索引164/166。流程进行到块212。

在块212，条件分支预测器112接收索引164/166并响应于此生成侧A和侧B的方向预测174/176和命中172。流程进行到块214。

在块214，控制逻辑114从其输入决定BTAC108和条件分支预测器112是否一起参与指令字节块124中可能存在的有效、跳转分支指令的方向预测。如果是的话，则控制逻辑114将其输出的最终结果，该侧预测的第一条有效跳转分支指令的分支目标地址144/146提供给取指单元101，以将程序流重定向到所选的目标地址144/146。流程在块214结束。

为了理解图1的分支预测器100的优点，现在将相对于图3描述常规的分支预测器300。图3的常规的分支预测器300在许多方面类似于图1的分支预测器100。但是，图3的散列逻辑306不从BTAC 108接收字节偏移154/156且不使用它们来形成每个条件分支指令的地址。而是，图3的散列逻辑306以分支转移历史104和块地址122进行散列，以生成提供给各个侧A和B的两个单独的条件分支预测器312A和312B两者的公用索引364。更具体地说，每一侧具有单独的存储器阵列，且常规的分支预测器300在其预测信息位于BTAC 108的侧A中的条件分支指令的执行时更新侧A条件分支预测器112A，并在其预测信息位于BTAC 108的侧B中的条件分支指令的执行时更新侧B条件分支预测器112B。

如可能观察到的，图1的分支预测器100具有由其散列逻辑106生成的索引164/166可能比由常规的散列逻辑306生成的索引364更精确的优点，因为常规的散列逻辑306仅使用块地址122进行散列，然而因为如上所述，图1的实施例的散列逻辑106具有使用条件分支指令的字节偏移154/156的益处，该散列逻辑106使用每一个条件分支指令的精确地址进行散列。

如另外可能观察到的，图1的分支预测器100具有每一索引164/166能够在比常规的分支预测器300更大的存储器阵列中查找方向预测信息的潜在优点。也就是，假定与图3的两个阵列312A和312B中条目的组合数目相同的图1的单个阵列112中的条目数目N，且给定图3的两个阵列312A和312B分开地更新且因此包括不同信息，图1的实施例的两个索引164/166每个开始搜索全部N个条目，然而常规的分支预测器300使得单个索引364搜索图3的两个阵列312A和312B的N个条目的每一半。应当理解，可能获得该潜在的优点作为因为图1的实施例的单个阵列112是双端口的然而图3的两个阵列312A和312B中的每一个可能是单端口的而图1的实施例的单个阵列112可能更大的事实的折衷。

如上所述，分支预测器100具有等待时间，即，其在接收块地址122和分支转移历史104之后可能需要多个时钟周期以将取指单元101重定向到最终预测的目标地址128。假定分支预测器100的等待时间是N个时钟周期。在一个实施例中，当取指单元101重定向时，取指单元101在目标地址128启动指令字节块124的取出，且对于下一N-1时钟周期启动顺序取出，同时分支预测器100生成在重定向的目标地址128取出的指令字节块124的预测。也就是，取指单元101假定分支不跳转。如果在N个时钟周期之后分支预测器100重定向，这指示该假定不正确，则使顺序地不正确地取出的N-1个指令字节块124无效，即，实际上从指令队列去除，这可能导致队列不提供足够的指令给指令译码器以保持执行流水线良好地使用。

因此，应该另外理解图1的实施例的潜在优点可以作为以下事实的折衷获得：在一些实现中，BTAC 108和散列逻辑106的等待时间可能充分地大以使得分支预测器100需要相对常规的分支预测器300的附加的时钟周期，这可能具有更频繁地保持队列较不满的后果。但是，特定的实现是否导致该折衷取决于处理技术、时钟周期时段和逻辑门路径长度。

现在描述的实施例具有的潜在优点在于它可以通过使用两个不同的分支指令地址生成两个分开的索引，来增加条件分支指令方向预测的精度，如图1的实施例所做的，但是不会导致与等待BTAC 108生成字节偏移154/156以执行散列以生成索引164/166相关联的延迟的产生，且因此更不可能增加分支预测器100的总体等待时间。应当理解，可以以比图1的实施例更少精度的代价(则是由于以分支转移历史104散列的两个形成的条件分支指令地址的更小精度)，潜在地获得第二个优点，如以下更详细地描述的。

现在参考图4，示出了图解根据替代实施例的具有分支预测器100的处理器103的框图。图4的实施例在许多方面与图1的实施例类似。但是，图4的散列逻辑406接收用于形成以分支转移历史104散列的两个不同的分支指令地址的两个预定值以生成提供给条件分支预测器112的侧A索引A 164和侧B索引B 166，而不是从BTAC 108接收字节偏移154/156。在图4中示出的实施例中，两个预定值是零(“0”)454和一(“1”)456。优选地，散列逻辑106通过级联该零值454与块地址122而形成第一分支指令地址，并通过级联该一值456与块地址122而形成第二分支指令地址，并以分支转移历史104散列这两个地址中的每一个以生成索引164/166。优选地，散列逻辑106以类似于相对于图1描述的方式执行两个散列，虽然可考虑其他散列实施例。

图1和图4的实施例之间的另一差异在于，与控制逻辑114关联方向A174与目标地址A 144和字节偏移A 154并关联方向B 176与目标地址B 146和字节偏移B 156的图1的实施例不同，图4的实施例的控制逻辑414关联方向A 174与两个目标地址144/146中具有两个字节偏移154/156中最小的字节偏移的一侧，并关联方向B 146与两个目标地址144/146中具有两个字节偏移154/156中最大的字节偏移的一侧。

图1和图4的实施例之间的又一差异在于，与条件分支指令的实际地址用于更新条件分支预测器112的图1的实施例不同，图4的实施例也保持由散列逻辑106计算的索引164/166，并使用他们中适当的一个来在已经执行了条件分支指令之后更新条件分支预测器112。

现在参考图5，示出了图示图4的分支预测器100的操作的流程图。类似图2，图5意在图示以向下方式的时间的推移，和在水平地彼此平行的块中执行的动作实质上彼此并行地发生。流程始于块202。

在块202，取指单元101生成块地址122并将其提供到图4的指令高速缓存102、BTAC108和散列逻辑406。流程并行地进行到块204、206和508。

在块204，指令高速缓存102输出指令字节块124。流程进行到块514。

在块206，BTAC 108输出对于每一侧，即，对于侧A和侧B的预测的目标地址144/146、字节偏移154/156和命中132。流程进行到块514。

在块508，散列逻辑406以分支转移历史104散列由块地址122和零值454和一值456形成的两个分支指令地址中的每一个以生成侧A和侧B的索引164/166。流程进行到块212。

在块212，条件分支预测器112接收索引164/166并响应于此生成侧A和侧B的方向预测174/176和命中172。流程进行到块514。

在块514，控制逻辑414检查字节偏移154/156以确定哪一个较小和哪一个较大。控制逻辑414关联方向预测A 174与其BTAC 108的一侧具有两个字节偏移154/156中较小的字节偏移的目标地址154/156，并关联方向预测B 176与其BTAC 108的一侧具有两个字节偏移154/156中较大的字节偏移的目标地址154/156。基于此，控制逻辑414确定BTAC 108和条件分支预测器112是否一起预测在指令字节块124中存在有效、看到、跳转的分支指令。如果是的话，则控制逻辑414在最终结果128上向取指单元101输出具有首个有效、看到、跳转的分支指令的一侧的目标地址144/146，以将程序流重定向到所选的目标地址144/146。流程在块514结束。

图4的实施例的潜在优点在于因为条件分支预测器112不使用由BTAC108生成的字节偏移154/156且因此不需要等待BTAC 108产生它们，所以条件分支预测器112在与BTAC108产生其输出的同一时钟周期中产生方向174/176(和命中172)。因此，在一些实现中，图4的分支预测器100能够使得其最终预测128比图1的分支预测器100早一时钟周期。在由于由散列逻辑406散列的分支指令地址的更小精度导致的潜在地更小的分支预测精度的缺点上理解该优点，这是因为使用恒定的零和一值而不是由BTAC 108提供的实际的字节偏移154/156形成分支指令地址。

另外，在当新分支指令分配到BTAC 108中时的潜在缺点上理解该优点。如上所述，这是因为图4的实施例的控制逻辑414基于它们关联的字节偏移154/156的相对大小来关联方向174/176与目标地址144/146的事实。更具体地说，新分支指令可能具有与它替换的分支指令的字节偏移不同的字节偏移。因此，相对于BTAC 108的另一侧的剩余字节偏移，指令字节块124内的两个分支指令的相对位置可能有改变(即，从较小的偏移改变为较大的偏移或者反之亦然)，以使得分支预测器100对于两个分支指令的几个实例可能使用错误的预测信息直到更新分支历史信息为止。

虽然在这里已经描述了本发明的各种实施例，应当理解它们已经通过示例的方式呈现，而不是限制。对于相关计算机领域中的普通技术人员很明显可以在其中做出形式和细节的各种改变而不脱离本发明的范围。例如，软件例如可以使能在这里描述的设备和方法的功能、制造、建模、模拟、描述和/或测试。这可以通过通用编程语言(例如，C，C++)、包括Verilog HDL、VHDL等的硬件描述语言(HDL)或者其他可用程序的使用实现。这种软件可以以任何已知的计算机可用介质配置，比如磁带、半导体、磁盘或者光盘(例如，CD-ROM、DVD-ROM等)、网络，有线线路或者其他通信介质。在这里描述的设备和方法的实施例可以包括在半导体知识产权核心中，比如处理器核心(例如，以HDL具实现或者指定)和可以变换为集成电路的生产中的硬件。另外，在这里描述的设备和方法可以具体表现为硬件和软件的组合。因此，本发明不应该由在这里描述的任何示例性实施例限制，而是应该仅根据以下权利要求和它们的等同物来定义。特别地，本发明可以在通用计算机中使用的处理器装置内实现。最终，本领域技术人员应该认可，他们可以容易地使用公开的概念和特定实施例作为设计或者修改其他结构以进行本发明的相同目的的基础，而不脱离本发明如所附权利要求所定义的精神和保护范围。