双重分支目标缓冲器和分支目标处理系统及处理方法

摘要

本发明公开了一种双重分支目标缓冲器，包括：第一分支目标缓冲器和第二分支目录缓冲器，所述第一分支目标缓冲器包括多路组相连接结构的第一指令缓存单元，所述第一指令缓存单元用于临时存储预取的指令，每路组包括第一存储器和第二存储器；所述第二分支目标缓冲器包括多路组相连接结构的第二指令缓存单元，所述第二指令缓存单元用于临时存储预取指令，每个路组包括第三存储器和第四存储器。本发明双重分支目标缓冲器，有两个分支目标缓冲器，减少不同的命令在相同的index里登陆的可能，提高分支目标缓冲器正确的预测精度，有效加快中央处理器的速度。

说明书

技术领域

本发明涉及具有分支预测单元的处理器，特别是涉及一种分支预测单元内的分支目标缓冲器（Branch target buffer，BTB）。

背景技术

现有的计算器通常为流水线体系结构，“流水线”（或也称作“推测执行”）是一个术语，通常指其中使用一系列功能步骤或处理阶段来处理指令序列的操作方法，每个处理阶段通常在单个时钟周期内完成。每个处理阶段通常在单个时钟周期内完成它的一个或多个构成操作。

与在开始下一指令之前将每条指令处理完成的非流水线处理器不同，流水线处理器在流水线的不同处理阶段同时处理几条指令。流水线阶段可以由设计者任意指定，但通常包括：指令获取（fetch）、指令译码（Decode）、指令执行（Execute）、执行解析阶段。

指令获取阶段从指令当前被存储的任何所在（例如，主系统存储器或者指令队伍）检索指令。一旦获取，指令被传递到译码器阶段，其通常确定指令地址和/或指令操作数。指令从译码器阶段传递到执行由指令指示的一个或多个操作的执行阶段。执行解析阶段通常涉及将通过执行指令生成的结果（例如，结果数据）回写（write-back）到一个或多个寄存器或存储器以备以后使用。

流水线提供了毫无疑问的性能收益，只要待处理的指令序列保持高度线性或者可预测。不幸的是，大多数指令序列包含众多的能够引入非顺序执行路径的指令。所谓的“分支指令”（包括，例如，跳转，返回和条件分支指令）在流水线处理器中产生了显著的性能损害，除非实现分支预测的有效形式。在未预测到（或错误预测）的分支指令引起偏离处理器内当前流水线中的指令序列时出现性能损害。如果发生这种情况，则当前流水指令序列就必须被扔掉或“清除”，而新的指令序列必须加载到流水线中。流水线清除浪费了众多时钟周期并且通常使处理器的执行变慢。

分支目标缓冲器预测的成败影响着中央处理器(CPU)的速度，越来越被重视。分支目标缓冲器用来预测分支命令的下一个命令的地址的。它在CPU中的回路构成如图1所示。

现有分支目标缓冲器构成以及预测方法如下：PC为Program Counter，它为命令所在的地址，它被分为Tag 和Index；BTB为现有分支目标缓冲器，它包含了分支命令的地址的Tag 和分支命令所目标地址(Target Address)；它的动作包括下一个地址的预测，和得到地址之后的BTB的更新。

详细动作是：当分支命令到来时，开始预测，在BTB中，用PC的index从对应的Index中取出BTB的Tag，并与PC的tag进行比较，生成miss/hit 信号，如果2个tag相同，信号为hit, 如果2个tag不相同，信号为miss。这将作为BTB下方的选择器的控制信号。另外从对应的Index中取出Target Address，投入BTB下方的选择器，待被选择。

上述BTB存在的问题为：不同的命令有在相同的index里登陆的可能，这样将导致分支目标缓冲器无法正确的预测。

有文献（J. K. F. Lee and A. J. Smith, "Branch prediction strategies and branch target buffer design," IEEE Comput. Mag. pp. 6-22, Jan. 1984）公开了如图2所示的BTB结构，这种方法虽然能缓解BTB的错误，但是仍存在大量的错误。不同的命令有在相同的index里登陆的可能，这样将导致分支目标缓冲器无法正确的预测。

另一文献（Y. Ishii , T. Sawada, K. Kuroyanagi, M. Inaba, K. Hiraki, "Bimode Cascading: Adaptive Rehashing for ITTAGE Indirect Branch Predictor",2nd JILP Workshop on Computer Architecture Competitions(JWAC-2),2011）公开了如图3所示的BTB结构，这个方法是利用不同长的Globe History Register(GHR) 和PC(Program Counter)来生成index，从而检索对因的地址来作为下一个命令的地址。

发明内容

本发明主要解决的技术问题是提供一种双重分支目标缓冲器，能够减少预测错误，有效加快中央处理器（CPU）的速度。

为解决上述技术问题，本发明采用的一个技术方案是：提供一种双重分支目标缓冲器，包括：第一分支目标缓冲器和第二分支目录缓冲器，所述第一分支目标缓冲器包括多路组相连接结构的第一指令缓存单元，所述第一指令缓存单元用于临时存储预取的指令，每路组包括第一存储器和第二存储器，所述第一存储器用于存储地址标签位，所述第二存储器用于存储所述地址标签位所对应的有条件分支命令目标地址；所述第二分支目标缓冲器包括多路组相连接结构的第二指令缓存单元，所述第二指令缓存单元用于临时存储预取指令，每个路组包括第三存储器和第四存储器，所述第三存储器存储指令地址，所述第四存储器存储指令地址所对应的无条件分支命令目标地址。

本发明同时提供一种分支目标处理系统，包括：CPU整数单元、双重分支目标缓冲器、分支目标预测单元、加法器、比较器和选择器；

所述CPU整数单元，采用流水线结构，包括指令提取单元和位于所述指令提取单元后续的指令执行单元，所述指令提取单元将提取的指令地址分别传输给双重分支目标缓冲器、加法器和分支目标预测单元，所述指令执行单元的后续单元将执行结果地址分别传输给双重分支目标缓冲器和分支目标预测单元；

所述分支目标预测单元，对分支条件成立与否进行预测，并将结果传输给选择器；

所述加法器，将所述执行指令地址进行处理，得到顺序的下一条指令地址，并将结果传输给选择器；

所述双重分支目标缓冲器，包括：第一分支目标缓冲器和第二分支目录缓冲器，所述第一分支目标缓冲器包括多路组相连接结构的第一指令缓存单元，所述第一指令缓存单元用于临时存储预取的指令，每路组包括第一存储器和第二存储器，所述第一存储器用于存储地址标签位，所述第二存储器用于存储所述地址标签位所对应的有条件分支命令目标地址；所述第二分支目标缓冲器包括多路组相连接结构的第二指令缓存单元，所述第二指令缓存单元用于临时存储预取指令，每个路组包括第三存储器和第四存储器，所述第三存储器存储指令地址，所述第四存储器存储指令地址所对应的无条件分支命令目标地址；

指令地址包括索引位和标签位，所述指令地址的索引位取出对应第一分支目标缓冲器中的标签位传输给比较器，与指令地址的标签位相比较，将结果传输给选择器，同时将所述第一分支目标缓冲器中的标签位对应的目标地址传输给选择器；同时检索所述第三存储器，如果存在相同的指令地址，则取出与指令地址相对应的目标地址传输给选择器；

所述选择器，对上述输入的数据进行选择，将待执行的下一条指令传输给所述CPU整数单元。

本发明还提供一种分支目标处理方法，具体步骤包括：

（100）提供一种分支目标处理系统，包括：CPU的整数单元、双重分支目标缓冲器、分支目标预测单元、加法器、比较器和选择器；所述CPU的整数单元，采用流水线结构，至少包括指令提取单元和位于所述指令提取单元后续的指令执行单元；所述双重分支目标缓冲器，包括：第一分支目标缓冲器和第二分支目录缓冲器，所述第一分支目标缓冲器包括多路组相连接结构的第一指令缓存单元，所述第一指令缓存单元用于临时存储预取的指令，每路组包括第一存储器和第二存储器，所述第一存储器用于存储地址标签位，所述第二存储器用于存储所述地址标签位所对应的有条件分支命令目标地址；所述第二分支目标缓冲器包括多路组相连接结构的第二指令缓存单元，所述第二指令缓存单元用于临时存储预取指令，每个路组包括第三存储器和第四存储器，所述第三存储器存储指令地址，所述第四存储器存储指令地址所对应的无条件分支命令目标地址；

（200）、所述指令提取单元提取指令地址分别传输给双重分支目标缓冲器、加法器和分支目标预测单元，

（300）、所述分支目标预测单元，对分支条件成立与否进行预测，并将预测结果传输给选择器；所述加法器，将所述执行指令地址进行处理，得到顺序的下一条指令地址，并将计算结果传输给选择器；

（400）、指令地址包括索引位和标签位，所述指令地址的索引位取出对应第一分支目标缓冲器中的标签位传输给比较器，与指令地址的标签位相比较，将比较结果传输给选择器，同时将所述第一分支目标缓冲器中的标签位对应的目标地址传输给选择器；同时检索所述第三存储器，如果存在相同的指令地址，则取出与指令地址相对应的目标地址传输给选择器；

（500）、如果预测结果为成立，同时比较结果为相同，选择器选择所述第一分支目标缓冲器中的目标地址传输给所述CPU的整数单元；如果检测结果为成立，而比较结果为不同，选择器选择所述第二分支目标缓冲器中的目标地址传输给所述CPU的整数单元；如果预测结果为不成立，选择器则选择加法器的计算结果传输给所述CPU的整数单元。

在本发明一个较佳实施例中，还包括步骤（600）、分支命令执行完毕后，进行更新：如果分支命令是无条件分支命令的话，检索第二分支目标缓冲器，如果有相同指令地址存在就不用登陆，如果没有相同的存在，寻找空处，将指令地址登陆到第三存储器中，下一个命令的地址登陆到第四存储器中；如果命令是有条件分支命令而且预测结果为成立的情况下，将在第一支目标缓冲器的对应的索引位内登陆标签位和目标地址。

在本发明一个较佳实施例中，所述第二分支目标缓存器的第四存储单元为CAM构造，以先进先出的原则进行覆盖。

本发明的有益效果是：本发明双重分支目标缓冲器，有两个分支目标缓冲器，减少不同的命令在相同的index里登陆的可能，提高分支目标缓冲器正确的预测精度，有效加快中央处理器（CPU）的速度。

附图说明

图1是现有技术中一种分支目标缓存器的结构示意图；

图2是现有技术中又一种分支目标缓存器的结构示意图；

图3是现有技术中再一种分支目标缓存器的结构示意图；

图4是本发明分支目标处理系统的结构示意图；

图5是本发明分支目标预测错误比率图；

图6是本发明双重目标缓存器的提速效果示意图。

具体实施方式

下面结合附图对本发明的较佳实施例进行详细阐述，以使本发明的优点和特征能更易于被本领域技术人员理解，从而对本发明的保护范围做出更为清楚明确的界定。

请参阅图1，本发明实施例包括：

一种分支目标处理系统，包括：CPU的整数单元（未标注）、双重分支目标缓冲器（未标注）、比较器5、加法器（adder）6、分支目标预测单元（PHT）7和选择器8；

所述CPU的整数单元，采用流水线结构，依次包括指令提取（fetch）单元21、指令译码（decode）单元22、指令执行（execute）单元23、存储器访问（memory access）单元24和写入（write back）单元25，所述指令提取单元21将从指令存储器1中提取的指令地址（PC）分别传输给双重分支目标缓冲器、加法器6和分支目标预测单元7，所述指令执行单元23的后续单元存储器访问单元24将执行结果地址分别传输给双重分支目标缓冲器和分支目标预测单元7；

所述分支目标预测单元7，对分支条件成立与否进行预测，并将预算结果taken/not taken传输给选择器8；

所述加法器6，将所述执行指令地址进行处理，得到顺序的下一条指令地址，并将结果传输给选择器，以一条指令32bit为例，顺序的下一条指令PC+4；

所述双重分支目标缓冲器，包括：第一分支目标缓冲器和第二分支目录缓冲器，所述第一分支目标缓冲器包括第一指令缓存单元41，用于临时存储预取的指令，采用多路组相连接结构，每个路包括第一存储器和第二存储器，所述第一存储器存储地址标签位（tag），所述第二存储器存储所述标志位相对应的有条件分支命令目标地址（target address）；所述第二分支目标缓冲器包括第二指令缓存单元42，用于临时存储预取指令，采用多路组相连接结构，每个路包括第三存储器和第四存储器，所述第三存储器存储指令地址(PC)，所述第四存储器存储指令地址相对应的无条件分支命令目标地址（target address）；

指令地址包括索引位（index）和标签位（tag），所述指令地址的索引位取出对应第一分支目标缓冲器中的标签位传输给比较器5，与指令地址的标签位相比较，将比较结果传输给选择器，同时将所述第一分支目标缓冲器中的标签位对应的目标地址传输给选择器8；同时检索所述第三存储器，存在相同的指令地址，则取出与指令地址相对应的目标地址传输给选择器8；

所述选择器8，将上述结果进行选择，将待执行的下一条指令（next PC ） 传输给指令存储器1和存储器访问单元24。

当分支命令到来时，开始预测: 

1．在CBTB中，用PC的index从对应的Index中取出BTB的Tag，并与PC的tag进行比较，生成miss/hit 信号，如果2个tag相同，信号为hit, 如果2个tag不相同，信号为miss。这将作为CBTB下方的选择器的控制信号。

另外从对应的Index中取出Target Address，投入CBTB下方的选择器，待被选择。

2．在NBTB中，检索相同的PC，如果存在取出对应的Target Address，投入CBTB下方的选择器，待被选择。

同时利用加法器（Adder） 将Address加上4，投入CBTB下方的选择器，待被选择。  

最后如果PHT的控制信号是Taken时，

如果miss/hit是Hit,选择CBTB，生成的Target Address作为下一个命令的地址。

如果检索到相同的PC，选择NBTB，生成的Target Address作为下一个命令的地址。

如果都没有，则等待命令执行完毕。

如果PHT的控制信号是Not Taken时，则选择加法器（Adder）的结果

当分支命令执行完毕后，开始登陆（更新）

这时候由于结果都出来了 所以利用计算结果登陆即可。

关于NBTB：

如果命令是non-conditional分支命令的话，检索NBTB，如果有相同命令存在就不用登陆，如果没有相同的存在，寻找空处，将地址等陆到PC里，下一个命令的地址等陆到Target Address里。

另外因为NBTB为CAM构造，所以存在变满的情况，所以我们给CAM一个Check point,实现CAM的FIFO(First In First Out)机能。也就是说当满了的时候，新的non-conditional分支命令将覆盖掉最先被登陆NBTB的index中。

关于CBTB 

如果命令是conditional分支命令而且结果是PHT为Taken的情况下，将在CBTB的对应的index内登陆Tag 和Target Address。

分支命令分为无条件（non-conditional）分支命令和有条件（conditional）分支命令。

分支命令出错主要分成以下几种情况：

1、不一样的non-conditional分支命令连续Aceess 相同的BTB entry 时会出错；

2、non-conditional分支命令后为conditional分支命令Taken的话，连续Aceess 相同的BTB entry 时会出错；

3、non-conditional分支命令后为conditional分支命令NotTaken的话，连续Aceess 相同的BTB entry 时不会出错；

4、conditional分支命令Taken后为的non-conditional分支命令后为话，连续Aceess 相同的BTB entry 时会出错；

5、conditional分支命令NotTaken后为的non-conditional分支命令后为话，连续Aceess 相同的BTB entry 时不会出错；

 以上为所有Parten 3/5 都会出错。

图5为各种情况的在相关程序中所有错误中的比率 

CB_CB _Miss为：conditional分支命令后为conditional分支命令，出错的比率；

CB_NB _Miss为：conditional分支命令后为non-conditional分支命令，出错的比率；

NB_CB _Miss为：non-conditional分支命令后为conditional分支命令，出错的比率；

NB_NB _Miss为：non-conditional分支命令后为non-conditional分支命令，出错的比率；

我们发现预测的失败与无条件命令的关系比较强，无条件跳转总是要执行的，所以总是要使用BTB表，有条件跳转不一定执行，当判断条件不成立（not taken），就不需要使用BTB表。而且，non-conditional的种类不是十分很多。因而使用non-conditional分支命令用和conditional分支命令用的新的双重分支目标缓冲器的方案，可有效提高预测正确率且不会带来较高的硬件成本。第一分支目标缓冲器是利用了原来的BTB，用于conditional分支命令的预测的机构（第一分支目标缓冲器为SRAM构成）， 第二分支目标缓冲器是追加的用于non-conditional分支命令的预测（CAM）。 第二分支目标缓冲器里放的是non-conditional分支命令的地址(PC)和目标地址(Target Address)，更新和预测是通过检索PC来实现的。

图6表示了提案的效果。 128entry的时候得到了4%的提速，256entry的时候达到5%的提速。

以上所述仅为本发明的实施例，并非因此限制本发明的专利范围，凡是利用本发明说明书及附图内容所作的等效结构或等效流程变换，或直接或间接运用在其他相关的技术领域，均同理包括在本发明的专利保护范围内。