CN102855121B - 分支处理方法与系统 - Google Patents

Abstract

一种控制处理器流水线操作的方法。该处理器连接一个包含可执行的计算机指令的存储器。该方法包括判断处理器即将执行的指令是否是分支指令，并提供该分支指令的分支目标指令地址和该分支指令在程序序列中的后一指令地址。该方法还包括至少根据分支目标指令的地址对分支指令的分支判定，并根据该分支判断，在分支指令到达其在流水线中的执行段前，至少选择分支目标指令和后一指令中的一个作为执行单元将要执行的指令，使得无论分支指令的转移是否发生都不会导致流水线操作的暂停。

Description

分支处理方法与系统

技术领域

本发明涉及电子计算机和微处理器体系结构领域，具体涉及分支处理方法与系统。

背景技术

控制相关(control hazards)也称为分支(Branch)，是流水线性能损失的一大原因。在处理分支指令时，传统处理器无法提前知道应该从哪里获取分支指令之后执行的下一条指令，而是需要等到分支指令完成后才能知道，使得流水线中分支指令之后出现空周期。图1是显示了传统流水线结构，其中的流水线段对应了一条分支指令。

表1分支指令的流水线段(分支转移发生时)

顺序

i

IF

ID

EX

MEM

WB

i+1

IF

stall

stall

stall

目标

IF

ID

EX

MEM

目标+1

IF

ID

EX

目标+2

IF

ID

指令地址

i

i+1

目标

目标+1

目标+2

目标+3

目标+4

获取指令

i

i+1

目标

目标+1

目标+2

目标+3

时钟周期

1

2

3

4

5

6

7

结合图1与表1一同说明，表1中的列表示流水线中的时钟周期，而行表示按顺序的指令。指令地址是提供给指令存储器用于在获取指令时进行寻址，之后指令存储器的输出被送到译码器对获取到的指令进行译码。该流水线包括指令获取(IF)、指令译码(ID)、执行(EX)、存储器访问(MEM)和写回(WB)。停止(“stall”)表示流水线暂停或空周期。

表1显示了一个被标记为‘i’的分支指令，该指令在时钟周期‘1’被获取到。此外，‘i+1’表示紧跟在该分支指令之后的指令，“目标”表示该分支点的分支目标指令，而“目标+1”、“目标+2”、“目标+3”和“目标+4”表示紧跟在该分支目标指令之后的顺序指令。

如表1所示，在时钟周期‘2’，处理器获取到分支指令‘i’。在时钟周期‘3’，处理器获取到指令‘i+1’，并对分支指令‘i’进行译码。假设在该分支指令译码段的结尾可以计算出分支目标地址，并完成分支判定。如果分支判定为分支转移发生，那么分支目标地址就被保存为下一地址用于获取下一指令。在时钟周期‘4’，获取分支目标指令，并在之后周期进行译码和执行。从这里开始，流水线处理分支目标指令后面的指令。然而，在这种情况下，已经被获取到的紧跟在分支指令之后的指令‘i+1’是不应该被执行的，因此流水线会因为指令‘i+1’而暂停。这样，当分支转移成功发生时，流水线会有一个时钟周期的暂停，这会导致流水线操作性能明显降低。

为了减少分支处理对流水线性能的不利影响，已经有各种静态或动态的分支预测方法被提出，如：延时槽、分支预测缓冲、分支目标缓冲和跟踪缓存(tracecache)等。然而，这些预测方法通常根据处理器之前的运行结果进行预测，因此仍然会有预测错误而导致的性能损失。

本发明提出的方法与系统可用于解决上述一个或多个问题，以及其他问题。

发明内容

本发明提出一种控制处理器流水线操作的方法。该处理器连接一个包含可执行的计算机指令的存储器。该方法包括判断处理器即将执行的指令是否是分支指令，并提供该分支指令的分支目标指令地址和该分支指令在程序序列中的后一指令地址。该方法还包括至少根据分支目标指令的地址对分支指令的分支判定，并根据该分支判断，在分支指令到达其在流水线中的执行段前，至少选择分支目标指令和后一指令中的一个作为执行单元将要执行的指令，使得无论分支指令的转移是否发生都不会导致流水线操作的暂停。

本发明还提出一种用于控制处理器流水线操作的流水线控制系统。该处理器连接一个包含可执行的计算机指令的存储器。该系统包括一个审查单元、一个寻址单元、一个分支逻辑单元和一个选择器。该审查单元用于判断处理器即将执行的指令是否为分支指令。该寻址单元连接处理器，用于提供分支指令的分支目标指令地址和分支指令在程序序列中的后一指令地址。此外，分支逻辑单元用于至少根据寻址单元提供的分支目标指令地址决定关于该分支指令的分支判定。该选择器用于根据分支逻辑单元提供的分支判断，在分支指令到达其在流水线中的执行段之前，至少选择分支目标指令和后一指令中的一个作为所述执行单元将要执行的指令，使得无论该分支指令的转移是否发生都不会导致流水线操作的暂停。

本发明还提出一种控制处理器流水线操作的方法。该处理器连接一个包含可执行的计算机指令的存储器。该方法包括判断处理器即将执行的指令是否是 分支指令，并提供该分支指令的分支目标指令地址和该分支指令在程序序列中的后一指令地址。该方法还包括根据分支目标指令地址和后一指令地址分别获取分支目标指令和后一指令。此外，该方法还包括对获取到的分支目标指令和后一指令进行译码，并根据处理器提供的分支判断选择分支目标指令的译码结果和后一指令的译码结果送到执行单元，使得无论分支指令的转移是否发生都不会导致流水线操作的暂停。

本发明还提出一种用于控制处理器流水线操作的流水线控制系统。该处理器连接一个包含可执行的计算机指令的存储器。该流水线控制系统包括一个连接处理器的寻址单元，用于提供分支指令的分支目标指令地址和分支指令在程序序列中的后一指令地址。该流水线控制系统还包括一个连接在存储器和处理器之间的读缓冲，用于至少存储分支指令的分支目标指令和后一指令中的一个。此外，该读缓冲还包括一个连接处理器的选择器，用于在分支指令被执行时，向处理器提供分支目标指令或后一指令中的一个，使得无论分支指令的分支转移是否发生都不会导致流水线操作的暂停。

对于本领域专业人士，还可以在本发明的说明、权利要求和附图的启发下，理解、领会本发明所包含其他方面内容。

有益效果：

本发明所述的系统和方法可以为流水线处理器的分支处理提供一种基本的解决方法。该系统和方法在分支点被执行前获取分支目标指令的地址，并使用各种分支判断逻辑以消除因错误的分支预测而造成的效率损失。对于本领域技术人员而言，也可以推导出本发明的其他优点和有益效果。

附图说明

图1是现有普通流水线的控制结构；

图2是本发明所述的一个流水线控制结构的实施例；

图3是本发明所述的一个处理器系统的实施例；

图4是本发明所述的轨道表的实施例；

图5A是本发明所述的另一个流水线控制结构的实施例；

图5B是本发明所述的另一个流水线控制结构的实施例；

图6是本发明所述的另一个处理器系统的实施例；

图7是本发明所述的另一个处理器系统的实施例；

图8是本发明所述的操作中的不同指令值的实施例；

图9是本发明所述的另一个流水线控制结构的实施例；

图10是本发明所述的处理器环境的一个实施例；

图11是本发明所述的分支预测方法的一个示意图；和

图12是本发明所述的分支预测的实施例。

具体实施方式

虽然该发明可以以多种形式的修改和替换来扩展，说明书中也列出了一些具体的实施图例并进行详细阐述。应当理解的是，发明者的出发点不是将该发明限于所阐述的特定实施例，正相反，发明者的出发点在于保护所有基于由本权利声明定义的精神或范围内进行的改进、等效转换和修改。同样的元器件号码也可以被用于所有附图以代表相同的或类似的部分。

图2显示了一个与本公开发明一致的流水线控制结构1的例子。为了便于说明，流水线操作包括取指令(IF)、指令译码(ID)、执行(EX)、存储器访问(MEM)和写回(WB)。也可以使用其它流水线结构。如图2所示，译码器11通过指令总线16从指令存储器(或指令缓存)10取指令。译码器11将取得的指令译码并为后续操作准备操作数。译码后的指令与操作数被送往执行与程序计数器12(EX/PC)做执行操作并计算程序系列中下条指令的地址21。下一条指令的地址21被作为选择器20的输入。

同时，如果一个取得的指令是一个分支点，分支目标的指令地址在程序计数器到达该分支点前已被预先算出，如后续的段落细节描述。预先算出的分支目标指令地址被作为选择器20的另一个输入18。另外，一个分支判断单元13提供了一个分支控制信号14用以控制选择器20。可以基于分支类型与分支条件(或一个条件标志)产生分支控制信号14。分支控制信号14控制选择器20选择输出哪一路输入被输出到寄存器17和地址总线19。之后，总线19上的输出被用于从指令存储器10提取下条指令。

图3显示了对应本发明所述流水线控制结构1的处理器环境300。如图3所示，处理器环境300包含一个低层次存储器122、一个高层次存储器124和一个处理器核125。此外，处理器环境300包含一个填充/生成器123、一个主动表121、一个轨道表126、一个循迹器170和一个分支判断逻辑210(对应于图2中的分支判断逻辑13)。应当理解的是，这里列出各种部件的目的是为了便于描述，还可以包含其他部件，而某些部件也可以被省略。这里的各种部件可以分布在多个系统中，可以是物理上存在的或是虚拟的，可以是硬件实现(如：集 成电路)、软件实现或由硬件和软件组合实现。

高层次存储器124和低层次存储器122可以包含任何合适的存储设备，如：静态存储器(SRAM)、动态存储器(DRAM)和闪存存储器(flash memory)。在这里，存储器的层次指的是存储器与处理器核之间的接近程度。越接近处理器核的层次越高。此外，一个高层次的存储器通常比低层次的存储器速度快但容量小。高层次存储器124可以作为系统的一个缓存工作，或当有其他缓存存在时作为一级缓存工作，且可以被分割成复数个被称为块(如存储块)的用于存储处理器核125要访问的数据(即在指令块和数据块中的指令和数据)的存储片段。

处理器核125可以是能以流水线方式并与缓存系统协同工作的任意合适的处理器。处理器核125可以使用分开的指令缓存与数据缓存，并可以包含一些用于缓存操作的指令。当处理器核125执行一条指令时，处理器核125首先需要从存储器中读入指令和/或数据。主动表121、轨道表126、循迹器170和填充/生成器123用于将处理器核125将要执行到的指令填充到高层次存储器124中，使处理器核125能从高层次存储器124中以非常低的缓存缺失率读到所需的指令。在本实施例中，术语“填充”表示将数据/指令从较低层次的存储器移动到较高层次的存储器中，术语“存储器访问”表示处理器核125对最接近的存储器(即高层次存储器124或一级缓存)进行读或写。

此外，填充/生成器123可以根据适当的地址获取指令或指令块，并可以对从低层次存储器122中获取来以填充到高层次存储器124中的每一条指令进行审查，并提取出某些信息，如：指令类型、指令地址和分支指令的分支目标信息。该指令以及包含分支目标信息的被提取出的信息被用于计算地址并送到其他模块，如主动表121和轨道表126。在本实施例中一条分支指令或一个分支点指的是任何适当的能导致处理器核125改变执行流(如：非按顺序执行一条指令)的指令形式。如果分支目标信息对应的指令块尚未被填充到高层次存储器124中，那么在将该指令块填充到高层次存储器124中的同时，建立对应的轨道。轨道表126中的轨道和高层次存储器124中的存储块一一对应，且都由同一指针152指向。处理器核125将要执行的任何指令，都可以在执行前被填充到高层次存储器124中。

填充/生成器123可以根据指令和分支目标信息确定地址信息，如：指令类型、分支源地址和分支目标地址信息。例如，指令类型可以包括条件分支指令、无条件分支指令和其他指令等。指令类别还可以包括条件分支指令的子类别，如相等时分支转移、大于时分支转移等。在某些情况下，可以认为无条件分支指令是条件分支指令的一种特例，即条件总是成立。因此，指令类型可以分为 分支指令和其他指令等。分支源地址可以指分支指令本身的地址，分支目标地址可以指当分支成功发生时将被转移到的地址。此外，还可以包括其他信息。

此外，可以基于预先计算的信息建立一个轨道表用于提供地址以填充高层次存储器124。图4是一个如本发明所公开的轨道表操作的例子。如图4所示，轨道表126与循迹器170相互作用以提供缓存与分支处理所需的地址。

轨道表126可包含处理器核125执行的指令的轨道，循迹器170基于轨道表126提供不同的地址，并为轨道表126提供一个读取指针。这里说的轨道的意思是对要被执行的一系列指令(比如一个指令块)的一种表达形式。这种表达形式可以包括任何适当的数据类型，如地址，块号码，或者其它数字。此外，当一个轨道包含一个分支点，该分支点有一个改变了程序流向的分支目标时，或当一条指令后的另一条指令是在一个不同的指令块，比如是下一个指令块中的一条指令、或一个异常程序、或另外一个程序线程等时，可以建立一个新轨道。

轨道表126可包括复数条轨道，其中轨道表126种每条轨道与轨道表中的标有一个行号或者块号(BN)的一行有对应关系，该块号指向一个相应的存储器块。一条轨道可包括复数个轨迹点，而一个轨迹点可以对应于一条或多条指令。此外，由于一条轨道对应于轨道表126中的一行，因此一个轨迹点对应于轨道表126中一行的一个表项(比如一个存储单元)。这样，一条轨道中的总的轨迹点可以等于轨道表126中一行中的表项总数。也可用其它组织方式。

一个轨迹点(即，在表的项中的一项)可含有这个轨道中一条指令的信息，比如分支指令。这样，一个轨迹点的内容可以包含相应指令的类别与分支目标的信息。通过检查一个轨迹点的内容，基于其中的分支目标地址可以确定一个分支目标点。

例如，如图4所示，处理器核125可用一种(M+Z)位的指令地址读取操作用的指令，在此M与Z是整数。地址中的M位部分可以被称为高位地址，Z位部分可被称为偏移地址。轨迹表126可包含2^M行，即总共2^M个轨道，而高位地址可以被用于轨道表126的寻址每一行可包含2^Z个轨道项，即总数为2^Z个轨迹点，偏移地址可用于在相应的行中寻址以确定一个特定的轨迹点。

此外，行中的每个表项或轨迹点的内容格式可以包括一个类别部分57、一个XADDR部分58和一个YADDR部分59。也可包含其它部分。类别部分57表示轨迹点对应指令的类别。如前所述，指令类别可包括条件分支指令、非条件分支指令和其它指令。指令类别还可以包括条件分支指令的子类别，如相等时分支转移、大于时分支转移等。XADDR部分58可以包含M位地址，也可以 被称为一个第一维地址或者简称为第一地址。YADDR部分59可以包含Z位地址，也可以被称为第二维地址或简称为第二地址。

当一条包含一个分支点(一个分支轨迹点)的新轨道被建立时，该新轨道可以被建立在轨道表126的一个可用行中，而分支轨迹点可以被建立在该行的一个可用表项中。该行和该表项的位置由分支点的源地址(即分支源地址)确定。例如，可以根据分支源地址的高位地址确定该行号码或块号码，根据分支源地址的偏移地址确定表项。

此外，新轨迹点的内容可以对应分支目标指令。换句话说，分支轨迹点的内容存储了分支目标地址信息。例如，轨道表126中的对应与一条分支目标指令的特定的行的行号或块号被作为第一地址存储到分支轨迹点的内容中。此外，偏移地址表示分支目标指令在其轨道中的位置，而该偏移地址被作为第二地址存储到该分支轨迹点的内容中。这样，在分支点的内容中，第一地址被用做行地址，而第二地址被用做列地址对该行中的分支目标轨迹点进行寻址。

指令存储器46可以是高层次存储器124的一部分，用于指令访问，并可以由任意合适的高性能存储器构成。指令存储器46可以包含2^M个存储块，每个存储块包含2^Z个字节或字。这就是说，指令存储器46可以存储所有被M和Z位(即指令地址)寻址的指令，使得这M位可以被用于对某个特定的存储块，而这Z位可以被用于对该特定存储块中的特定字节或字进行寻址。

循迹器170可以由各种部件或设备构成，如：寄存器、选择器、栈和/或其他存储模块，用于确定处理器核125执行的下一轨道。循迹器170可以根据轨道表126中的当前轨道、轨迹点信息和是否因处理器核125的执行发生分支转移等信息确定下一轨道。

例如，在运行过程中，当处理器核125执行分支指令时，总线55上传递了分支指令的(M+Z)位指令地址。M位地址通过总线56被作为第一地址或XADDR(或X地址)送到轨道表126，Z位地址通过总线53被作为第二地址或YADDR(或Y地址)送到轨道表126。根据该第一地址和第二地址，轨道表126可以找到一个分支指令表项，并将该分支指令的分支目标地址输出到总线51上。

如果该分支指令的分支转移条件不成立，那么分支转移不发生，选择器49选择总线53上的YADDR经增一逻辑48增加一(1)个字节或字后得到新的第二地址54，而第一地址保持不变，可以在总线52上输出该新地址。根据处理器核125来的控制信号60(如：一个不成功的分支转移)，寄存器50保持第一地址不变，由增一逻辑48不断对第二地址增一(1)直至指向当前轨道表行上的下一个分支指令。

另一方面，如果所述分支指令的分支转移条件成立，那么分支转移发生，选择器49选择总线51上的分支点对应的轨道表项的内容中存储的分支目标地址作为输出送到总线52上。根据处理器核125来的控制信号60(如：一个成功的分支转移)，寄存器50保持该改变后的对应新轨道的第一地址，并将(M+Z)位的新地址提供到总线55上。

这样，为了进行存储器寻址，轨道表126和循迹器170提供了一个块地址，而处理器核125只提供一个偏移量。处理器核125反馈分支指令执行状态使得循迹器170能够进行判断操作。

在执行一条新轨道之前，对应于该轨道的指令块被填充到指令存储器46中。重复该过程可以使处理器核125将要执行的所有指令都不会发生缓存缺失。

回到图3，为了提升效率并减小存储器容量，主动表121可以被用于存储任何已建立的轨道信息，并建立地址(或地址中一部分)与块号码之间的映射关系，使得可以使用轨道表126中的任何可用行建立轨道。例如，当建立一条轨道时，轨道中所有分支点的分支目标地址信息都被存储在主动表121中。这样，主动表21可以存储程序中所有分支目标轨迹点的轨道的映射信息。也可以使用其他的配置结构。

这样，主动表121可以被用于存储高层次存储器124中指令块的块号。块号也对应于轨道表126中的行号。在审查过程中，可以通过对地址和主动表121中表项进行匹配的方式得到分支目标地址的块号。匹配成功的结果，即块号(前述的第一地址)可以与指令在轨道中的偏移量(前述的第二地址)一起用于确定轨迹点的位置。

如果匹配不成功，表示该地址对应的轨道尚未建立。由主动表121指定一个块号并将该地址对应的指令段填充到高层次存储器124中由该块号索引的位置中，在轨道表126中建立对应这个块号的一条新轨道，使得主动表121可以表示这条已建立的轨道及相关地址。因此，之前所述主动表121和填充/生成器123的操作可以在分支点被处理器核125获取并执行之前，将分支点的分支目标指令对应的指令段填充到缓存124(即高层次存储器124)中。

这样，轨道表126可以被配置成一种二维表，其中，由第一地址BNX对每一行索引，对应一个存储块或一个存储行，而第二地址BNY对每一列索引，对应相应指令(数据)在存储块中的偏移量。简单来说，轨道表的写地址对应指令的源地址。此外，对于一个特定的分支源地址，由主动表121根据高位地址分配一个BNX，而BNY就等于偏移量。然后，BNX和BNY就可以组成一个指向被写表项的写地址。

此外，当指令被填充到高层次存储器124中时，可以通过计算分支指令地址及分支目标指令的分支偏移量之和的方法得到所有分支指令的分支目标地址。该分支目标地址(高位地址、偏移量)被送到主动表121以对高位地址部分进行匹配，而主动表121可以分配一个BNX。该分配到的BNX与从生成器130来的指令类型以及偏移量(BNY)一起构成每个分支指令轨道表项内容。该内容被存储在由相应写地址寻址的分支点中。

此外，循迹器170可以被用于向轨道表126提供一个读指针151。读指针151也可以是BNX和BNY的形式。由读指针指向的轨道表项的内容与该表项的BNX和BNY(源BNX和源BNY)一起被读出并被循迹器170检查。循迹器170可以根据该内容进行多种不同的读指针更新操作。例如，如果该表项不是一个分支点，循迹器170可以用新BNX＝源BNX、新BNY＝源BNY+1的方法更新读指针。

如果该表项是一个条件分支，循迹器170等待处理器核125送来的该分支点的分支指令被执行时产生的控制信号(TAKEN)。如果该控制信号表明分支转移没有发生，循迹器170可以用新BNX＝源BNX、新BNY＝源BNY+1的方法更新读指针。然而，如果该分支成功发生，循迹器170可以用新BNX＝目标BNX、新BNY＝目标BNY的方法更新读指针。

如果该表项是一个无条件分支(或跳转)，循迹器170可以将其视为一个条件成立的条件分支，也就是在该分支指令被执行时用新BNX＝目标BNX、新BNY＝目标BNY的方法更新读指针。

循迹器170与轨道表126及主动表121一起实现基于轨道的操作。这样，分支指令、分支目标指令和紧跟分支指令之后的指令的地址信息都能事先确定。这些信息可以被流水线控制结构1用于在不暂停流水线的情况下进行分支处理操作。

具体地，如图3所示，当读指针151到达一个分支点时，循迹器170接收到从轨道表126经总线150来的分支目标地址。该分支目标地址的高位地址(目标BNX)被作为一个选择器的一个输入，另一个输入是当前BNX(BN 151的高位地址，或源BNX)。该选择器的输出是下一BNX。此外，该分支目标地址的偏移量部分(目标BNY)被作为另一个选择器的一个输入，而另一个输入是来源于处理器核125的PC偏移量155。该选择器的输出被用做高层次存储器124的“偏移量1”地址，以对由BNX 152确定的缓存块中的指令进行寻址。

读指针151(BNX 152、BNY 153)以比PC更快的速度移动(如：循迹器170运行在更高的时钟频率等)。读指针151沿轨道移动，当从轨道表126的表 项中读出的内容表示该表项是一条带有分支目标地址(BNX和BNY)的分支指令时，读指针151停止移动，等待处理器核125执行该分支点，并等待从分支判断逻辑210来的控制信号‘TAKEN’信号212和‘BRANCH/JUMP’信号213。处理器核125提供一个PC偏移量以对高层次存储器124中的指令寻址，而循迹器170提供BNY 153以对轨道表126中的分支点寻址。这两个信号也被送到分支判断逻辑210进行比较。如果PC偏移量155与BNY 153相等，那么表示处理器核125正在获取该分支点。这就是说，BNY 153与PC偏移量155的匹配可以被用于控制分支处理的时机，使得分支判断逻辑210在PC偏移量155等于BNY 153时进行分支判定。或者，也可以在PC偏移量155离BNY153还差预设数目条指令时就可以开始进行分支处理。

当PC偏移量155等于或离BNY 153还差预设数目条指令时，处理器核125获取分支点。分支判断逻辑210可以对分支转移是否发生进行判定。在某些情况下，可以根据分支类型和分支条件(或条件标志)进行分支判定。分支类型211(来源于轨道表126)可以表示分支指令的特定类型，如：当分支条件等于零时分支转移或当分支条件大于零时分支转移等。分支条件可以由处理器核125的处理器操作产生。根据处理器结构、分支指令和/或流水线操作的不同，一条特定的分支指令的分支条件可以在处理器核125的多个流水线段有效。

分支判断逻辑210可以包含任何合适的电路用以进行分支判定。如之前所述，分支判断逻辑210可以在PC偏移量155等于BNY 153或在PC偏移量155与BNY 153形成某种关系(如：大于)时进行分支判定，该分支判定可以给出条件标志已经准备好的信号。之后，分支判断逻辑210的结果被作为‘TAKEN’信号212和‘BRANCH/JUMP’信号213。该‘BRANCH/JUMP’信号通知循迹器170处理器核125已经到达分支指令并使读指针151能够更新。该‘TAKEN’信号是正在执行的程序的真实结果并选择正确的下一条该被执行的指令。

这样，当检测到‘BRANCH/JUMP’信号时，如果分支转移不发生，那么下一BNX＝源BNX，而下一BNY＝源BNY+1，这样，选择没有改变的BNX 152(源BNX)送到“块选择1”，并选择来源于处理器核125的下条指令的指令地址偏移量(PC偏移量155)送到“偏移量1”以对该分支指令之后的指令进行寻址。然而如果分支转移发生，下一BNX＝目标BNX，而下一BNY＝目标BNY，这样，选择改变后的BNX 152(目标BNX)送到“块选择1”，并选择来源与轨道表126的分支目标指令的偏移量(目标BNY)送到“偏移量1”以对该分支指令的分支目标指令进行寻址。这样，根据从轨道表126来的分支类型信息和从处理器核125来的分支条件标志，可以在事先由轨道表126提供了分支目标指令的地址信息，PC提供了分支指令之后的指令的地址信息，而分支判断逻辑 210对分支转移进行了判定。

因此，如果分支转移发生，那么处理器核125用于获取分支目标指令(目标BNX152、目标BNY 150)的正确地址已经被准备好提供到高层次存储器124的端口“块选择1”和“偏移量1”。这样，处理器核125可以在不等待的情况下继续流水线操作。表2显示了分支转移成功发生时的流水线段图示。在表2中，被标记为“指令地址”的行是对应指令存储器124“块选择1”(高位地址)和“偏移量1”(低位地址)的指令存储地址，而标记为“获取指令”的行对应高层次存储器124“读端口1”上的指令。这里假设从指令地址有效到指令有效需要一个时钟周期的时延。此外，指令‘i’是分支指令，而‘目标’是分支目标指令，‘目标+1’是分支目标指令的后一条指令，依此类推。

表2流水线段图示(分支转移发生时)

顺序

I

IF

ID

EX

MEM

WB

目标

IF

ID

EX

MEM

WB

目标+1

IF

ID

EX

MEM

目标+2

IF

ID

EX

目标+3

IF

ID

指令地址

i

目标

目标+1

目标+2

目标+3

目标+4

获取指令

i

目标

目标+1

目标+2

目标+3

时钟周期

1

2

3

4

5

6

7

另一方面，如果分支转移不发生，那么处理器核125用于获取紧跟在分支指令之后的指令的正确地址(源BNX 152、PC偏移量155)也已经准备好提供到高层次存储器124的端口“块选择1”和“偏移量1”。这样，处理器核125可以在不等待的情况下继续流水线操作。此外，循迹器170可以如之前所述，在控制信号的控制下使用读指针获取下一分支点以继续分支处理。表3显示了分支转移不成功时的流水线段图示。指令‘i’是分支指令，‘i+1’是分支指令的后一条指令，依此类推。

表3流水线段图示(分支转移不发生时)

顺序

I

IF

ID

EX

MEM

WB

i+1

IF

ID

EX

MEM

WB

i+2

IF

ID

EX

MEM

i+3

IF

ID

EX

i+4

IF

ID

指令地址

i

i+1

i+2

i+3

i+4

获取指令

i

i+1

i+2

i+3

i+4

时钟周期

1

2

3

4

5

6

7

图5A显示了本发明所述的另一个流水线控制结构2。如图5A所示，译码器11对获取到的指令进行译码并提供执行所需的操作数。得到的指令译码结果和操作数被送到执行单元和程序计数器(EX/PC)以执行并计算程序流中的下一指令地址21。然而，与图2所述的流水线控制结构1不同，下一指令地址21和分支目标指令地址18通过寄存器24和23分别被送到指令存储器(或指令缓存)22。指令存储器22可以包含多个端口供读/写操作。

这样，指令存储器22可以包含两个地址端口用于输出下一指令地址21和分支目标指令地址18。当接收到下一指令地址21和分支目标指令地址18后，指令存储器22可以分别在输出端口28和29上提供相应指令。此外，在输出端口28和29上分别对应下一指令地址21和分支目标指令地址18的两条指令被输入到选择器26，而分支判断逻辑13可以向选择器26提供一个控制信号14以选择来源于端口28和29的输入并送到译码器11。

如果分支判断逻辑13判定分支点转移发生，输出对应分支目标指令地址18的指令29到译码器11。如果分支判断逻辑13判定分支点转移不发生，输出对应下一指令地址21的指令28到译码器11。此外，由于分支判断逻辑13在分支点到达其执行段或在其后指令译码之前就进行该判定，因此不会因为等待分支判定而造成流水线的时钟周期损失。

图6显示了对应流水线控制结构2的处理器环境400的实施例。如图6所示，处理器环境400与图3中的处理器环境300类似。然而，处理器环境400与处理器环境300的不同点在于分支判断逻辑被包含在处理器核125中，且高层次存储器124提供两个地址端口“块选择1、偏移量1”和“块选择2、偏移量2”，以及两个读端口“读端口1”127和“读端口2”128。

如图6所示，在处理分支指令时，轨道表126可以向地址端口“块选择2、偏移量2”提供分支目标指令地址目标BNX 201和目标BNY 202。此外，读指针151向“块选择1”提供下一指令的块地址BNX 152，而处理器核125向“偏移量1”提供下一指令的偏移地址。

当接收到分支目标指令地址和下一指令地址时，高层次存储器124分别取出分支目标指令和下一指令，并将获取到的分支目标指令和下一指令分别作为 获取到的指令204和获取到的指令203送到“读端口2”128和“读端口1”127。获取到的指令204和获取到的指令203也是受控制信号207(即来源于处理器核125的TAKEN信号)控制的选择器205的两个输入。此外，选择器205根据TAKEN信号，在处理器核125对获取到的指令进行译码之前，选择被获取到的指令中的正确的一个作为输出206送到处理器核125。如果分支转移发生，那么选择获取到的分支目标指令，而如果分支转移不发生，那么选择获取到的下一指令。

处理器核125还向循迹器170提供BRANCH/JUMP信号用以表示处理器核125已经到达一条分支指令，此时的TAKEN信号是程序执行的真实结果并选择正确的下一条该被执行的指令。这样，当检测到BRANCH/JUMP信号时，循迹器170用新地址作为BN 151。

如果分支转移发生，获取到的对应分支目标指令的指令204(目标BNX 201，目标BNY 202)已经作为输出206被送到处理器核125。这样，处理器核125可以不间断地继续流水线操作。当前，如果分支判断是无条件的，该无条件分支指令可以被视为一个条件满足、不需要进一步判断的特殊分支点。表4显示了在分支转移发生的情况下的流水线段的图示。在表4中，被标记为“指令地址”的行是对应指令存储器124“块选择1”(高位地址)和“偏移量1”(低位地址)的指令存储地址，而标记为“获取指令”的行对应选择器205的输出206上的指令。

表4流水线段图示(分支转移发生时)

顺序

I

IF

ID

EX

MEM

WB

目标

IF

ID

EX

MEM

WB

目标+1

IF

ID

EX

MEM

目标+2

IF

ID

EX

目标+3

IF

ID

指令地址

i

i+1

目标+1

目标+2

目标+3

目标+4

读端口1

i

i+1

目标+1

目标+2

目标+3

目标+4

读端口2

目标

目标

目标

目标

新目标

新目标

新目标

新目标

获取指令

i

目标

目标+1

目标+2

目标+3

目标+4

时钟周期

1

2

3

4

5

6

7

在分支指令的译码段(时钟周期3)，分支目标指令(“目标”)与下一指令(“+1”)一起从高层次存储器124中被获取到，并在该译码段结束前进行分支 判定。由于两条指令都被获取到了，因此无论该分支转移是否发生，正确的指令都可以被选出并在其译码段(时钟周期4)使用。这就是说，分支点之后获取到的指令总是一条有效的指令，且不需要暂停流水线。同样地，如表4所示，“读端口2”事先提供了下一分支目标指令。

当分支转移发生时，在时钟周期3选择从“读端口2”来的分支目标指令作为在时钟周期4进入译码段的指令。同样地，在时钟周期3的结尾，将处理器核125程序计数器(PC)强制设为分支目标指令的后一指令(目标+1)，而非分支目标指令(目标)。循迹器170输出源BNX 152按正常方式驱动“块选择1”，由于当分支转移发生时，循迹器170将包含分支目标地址信息的下一BN 151传送到BN 152，因此源BNX 152＝目标BNX。这样保证了下一个“目标+1”指令而非“目标”指令在时钟周期4能被获取到。这样，可以在不需要任何流水线暂停的情况下将程序流切换到分支目标。此外，指令地址按正常方式增加，直到到达下一分支点地址。

另一方面，如果分支转移不发生，获取到的对应下一指令(源BNX 152，PC偏移量155)的指令203作为输出206被送到处理器核125。这样，处理器核125不暂停而继续流水线操作。表5显示了分支转移不发生时的流水线段的图示。

表5流水线段图示(分支转移不发生时)

顺序

I

IF

ID

EX

MEM

WB

i+1

IF

ID

EX

MEM

WB

i+2

IF

ID

EX

MEM

i+3

IF

ID

EX

i+4

IF

ID

指令地址

i

i+1

i+2

i+3

i+4

i+5

读端口1

i

i+1

i+2

i+3

i+4

i+5

读端口2

目标

目标

目标

目标

新目标

新目标

新目标

新目标

获取指令

i

i+1

i+2

i+3

i+4

i+5

时钟周期

1

2

3

4

5

6

7

这样，当分支转移不发生时，在时钟周期3选择从“读端口1”来的分支指令之后的指令“i+1”作为在时钟周期4进入译码段的指令。从这点以后，指令地址以正常方式增加直到到达下一个分支点。

图5B显示了流水线控制结构3的框图。流水线控制结构3是上述流水线控 制结构2以外的另一种选择。流水线控制结构3与流水线控制结构2的不同点在于包含了一个额外的存储器40。存储器40可以包含与轨道表126的行数相同数目的存储块，每个存储块对应轨道表126中的一行。

此外，存储器40中的每个存储块可以包含一个与轨道表126中一行的轨迹点或表项数目相同的存储单元。这样，当一个轨迹点是分支点时，分支目标指令除了被存入指令存储器22中对应该分支目标指令的存储块中，还被存入存储器40相应的存储单元中。

分支目标地址18来源与轨道表126的表项。该表项的内容就是该表项或该分支轨迹点对应的分支目标指令的BNX和BNY。这样，BNX和BNY可以被用做索引以找到存储在存储器40中的相应分支目标指令。被选出的分支目标指令可以通过总线29被送到选择器26。此外，如之前所述，可以根据下一指令地址21从指令存储器22获取到下一指令，而该获取到的下一指令也可以通过总线28被送到选择器26。这样，图5B中的指令存储器22可以是一个单端口的存储设备，而不需要如图5A所示的双端口存储设备。

可选地，轨道表126中对应分支点的表项本身可以存储分支目标指令。这就是说，分支轨迹点的内容除了分支目标指令的地址和偏移量外，还包括了分支目标指令。这样，轨道表126可以直接向选择器26提供分支目标指令以供来源于分支判断逻辑13的控制信号14选择。这种配置结构可以被视为存储器40集成在轨道表126中。

这样，如前所述，由于分支目标指令地址可以事先确定，换句话说，由于分支目标信息和分支类型已经准备好的，因此可以在分支条件标志刚被处理器核操作设置完毕后就进行分支判定。这样，由于分支判定的主要功能就是计算分支目标地址并根据分支指令的分支类型和条件标志进行分支判定，因此可以早于分支指令本身到达其正常执行段时就进行分支判定。通常地，越早完成分支判定，需要的额外硬件资源就可以越少。根据从分支判断逻辑13来的预先分支判定，可以使用各种配置结构使得处理分支转移时流水线可以继续进行而不暂停。

图7显示了本发明所述处理器环境600的一个实施例。在处理器环境600中，使用了一个读缓冲用于提供处理器核125的程序流中一条分支指令的分支目标指令和中紧跟在该分支指令之后的指令。处理器环境600与图3中的处理器环境300类似，但有一些区别。如图7所示，处理器环境600除了缓存124、处理器核125、轨道表126和循迹器170外，还包含一个读缓冲229和一个选择器225。

读缓冲229连接在缓存124和处理器核125之间，并包含一个存储模块216和一个选择器214。存储模块216用于存储某些指令。例如，读缓冲229中的存储模块216存储并向外提供分支目标指令或后续指令中的一种，而另一种由缓存124直接提供，使得同样的缓存结构能提供更高的带宽。读缓冲229中的选择器214被用于根据分支判断选择分支目标指令和后续指令中的一种，使得在分支指令之后提供给处理器核125的指令是有效的或正确的。例如，选择器214被用于选择来源于存储模块216或缓存124的输出之一作为输出219送到处理器核125。此外，选择器220被用于选择来源于轨道表126或循迹器170的地址之一作为输出224送到缓存124(一个块地址)；而选择器225被用于选择来源于轨道表126或来源于处理器125的PC(程序计数器)偏移量中的一个作为输出224送到缓存124(一个偏移地址)。来源于循迹器170的控制信号215被用于控制选择器220和225以及存储模块216，而‘TAKEN’信号被用于控制选择器214。

在操作过程中，循迹器170提供BNX 152和BNY 153使得轨道表126可以输出一个对应于该BNX 152和BNY 153的轨迹点。该轨迹点被读出的内容中包含诸如指令类型和分支目标地址等的信息。该内容(如：指令类型和分支目标地址)可以通过总线150被送到循迹器170。此外，分支目标地址的高位部分(BNX)被送到选择器220作为一个输入。分支目标地址的BNY或该BNY的一部分(如：最高两位)也可以通过总线222被送到选择器225。选择器220的另一个输入可以是由循迹器170提供的BNX，而选择器225的另一个输入可以是PC偏移量或PC偏移量的一部分(如：最高两位)。

存储模块216可以包含根据其他部件的容量而预设数量的存储单元，用以存储指令。例如，如果一个存储块(如：指令块)总共包含16条指令，那么BNY和PC偏移量的长度可以是4位(4bit)。假设在一个时钟周期内从指令存储器或缓存124中获取4条指令，存储模块216可以存储4条指令，且BNY或PC偏移量的最高两位可以被用于从由BNX指向的存储块中读取4条指令，使用BNY或PC偏移量的最低两位从读出的4条指令中选择1条。

为便于描述，在此一个时钟周期获取的指令总数为4，而对于单发射或多发射处理器，每个时钟周期内获取的指令总数可以是任何合适的数目。此外，在一个时钟周期内获取的指令总数(如：4)可以超过处理器核125在一个时钟周期内执行指令的总数(如：1)。这样，可以在某个时钟周期使用轨道表126和其他相关部件装载存储模块216或填充缓存124。在某些实施例中，缓存124可以包含一个带宽大于处理器核125指令发射率的单端口存储模块，以支持循迹器170对存储模块216的填充，以及处理器核125的取指。

当循迹器170检测到一条指令是分支指令时，循迹器170暂停BNY的自增。当取指时间槽到来时，指令类型信息可以被用做控制信号215作为写使能信号控制存储模块216，将缓存124当前输出的4条指令通过总线217写入存储模块216。与此同时，根据指令类型信息(如：指令类型为分支指令)，信号215可以控制选择器220选择总线221上的分支目标指令的BNX作为指令块地址，并控制选择器225选择总线222上的分支目标地址的BNY的高两位在该指令块中找到4条指令。这4条指令包含可以在下一个读周期或下一时钟周期被读取的分支目标指令。此外，这包含分支目标指令在内的4条指令被存入存储模块216，而PC偏移量被再次用于读取下一指令。这样，当处理器核125执行一个分支点对应的分支指令时，可以同时提供分支目标指令和紧跟该分支点的后续指令，从而可以根据分支转移是否发生取到正确的指令。

图8显示了根据本发明技术方案在操作过程中读出指令的实施例。如图8所示，列226显示了存储模块216的输出218上的值，列227显示了缓存124的输出217上的值，而列228显示了处理器核125获取的当前指令。此外，假设指令I0、I1、I2和I3是对应同一PC偏移量的最高两位的4条连续的指令，其中I2是一条分支指令。再假设分支指令I2的分支目标指令是T1，而指令T0、T1、T2和T3是对应同一PC偏移量的最高两位的4条连续的指令。这里的行表示后续的时钟周期或执行周期(一个执行周期可能包含超过一个时钟周期)。4行分别对应周期i、周期i+1、周期i+2和周期i+3。此外，假设在分支指令被获取的后一个周期产生‘TAKEN’信号(即：该分支指令的分支转移是否发生)。

在周期i，假设PC偏移量指向I0，读指针到达对应分支指令I2的轨迹点。在该周期，选择器214选择来源于缓存124的输出作为输出219，而PC偏移量的最低两位可以被用于从4条连续的指令中选择处理器核125所需的指令I0。如之前所述，读指针停止在分支轨迹点，从缓存124输出的4条指令则被存入存储模块216，而分支目标地址被用做下一周期(即周期i+1)的指令地址用于获取包含分支目标指令在内的4条指令。

在周期i+1，存储模块216存储了指令I0、I1、I2和I3，而缓存124输出的指令为T0、T1、T2和T3。在周期i+1中，选择器214选择存储模块216的输出作为输出219，最低两位可以被用于从总线219上的4条指令中选择处理器核125所需的指令I1。此外，在周期i+1中，4条指令T0、T1、T2和T3被写入存储模块216，且读指针指向的轨迹点的BNX和PC偏移量被用做下个周期的指令(即指令I2)地址。

在周期i+2中，存储模块216存储并输出指令T0、T1、T2和T3，而缓存124输出的是指令I0、I1、I2和I3。在这个周期中，选择器214选择缓存124 的输出作为输出219，而PC骗移量的最低两位可以被用于从总线219上的4条指令中选择处理器核125所需的指令I2。下一条指令(即I3)的地址被用做下个周期的指令地址。

在周期i+3中，存储模块216存储并输出指令T0、T1、T2和T3，而缓存124输出的是指令I0、I1、I2和I3。在这个周期中，选择器214根据分支指令的分支转移是否发生，选择来源于缓存124的输出或来源于存储模块216的输出之一作为输出219。此外，还可以根据分支指令的分支转移是否发生，使用分支目标地址的BNY的最低两位或PC偏移量的最低两位相应选择处理器核所需的指令T1或I3。

这样，该‘TAKEN’信号(即分支指令的分支转移是否发生)可以被用于选择缓存124的输出或存储模块216的输出。或者，可以分别使用分支目标地址的BNY的最低两位和PC偏移量的最低两位，从包含分支目标指令在内的4条指令中选择一条指令，以及从包含下一指令在内的4条指令中选择另一条指令。

或者，可以同时向处理器核125提供指令I3和指令T1，而处理器核125可以对指令I3和指令T1进行分别译码，并同时得到指令I3和指令T1的操作数。根据分支指令的分支转移是否发生，处理器核125选择指令T1的译码结果或指令I3的译码结果，以及正确的操作数。具体地，当读指针到达分支指令I2对应的轨迹点时，如果处理器核125正在获取的指令离分支指令I2很近，如：正在获取指令I1，当指令I2被取到之后，缓存124就可以开始输出4条指令I0、I1、I2和I3。处理器核125可以仍然从缓存124和存储模块216分别获取I3和T1。例如，可以使用一个异或逻辑使控制选择器214的选择信号的值取反，从而分别从缓存124的输出中选择分支目标指令或包含分支目标指令在内的4条指令，或从存储模块216的输出中选择下一指令或包含下一指令在内的4条指令。在这种情况下，无论分支转移是否发生，4条指令T0、T1、T2和T3都不需要被存储在存储模块216中。

此外，图9显示了另一个本发明所述的流水线控制结构4。流水线控制结构4与图5中的流水线控制结构2类似。然而，流水线控制结构4与流水线控制结构2的不同点在于其包含两个独立的译码器：译码器25和译码器26，而不是只有一个译码器11。如图9所示，从指令存储器22获取到的两条指令进一步分别被译码器25和译码器26译码，而指令译码结果31和指令译码结果32被送到选择器33，由从分支判断逻辑13来的控制信号14选择。

如果分支判断逻辑13判定分支点转移发生，那么选择对应分支目标指令地 址18的指令译码结果32送到执行单元12。如果分支判断逻辑13判定分支点转移不发生，那么选择下一指令地址21对应的指令译码31送到执行单元12。此外，由于分支判断逻辑13可以在分支指令执行段结尾且下一指令的执行段之前完成该判定，因此流水线不会有任何等待分支结果而导致的时钟周期损失。

这样，分支判断逻辑13除了在执行该分支点之前进行分支转移的判定外，还可以在一个正常的流水线段中对分支转移进行判定，如在分支指令执行段的结尾进行。由于在分支点之后所有可能被处理器核125执行的指令都已经被获取并译码，且指令类型是已知的，因此不会有因分支判定而导致的流水线暂停。

此外，虽然如之前所述处理器核125每次执行一条指令，但处理器核125也可以每次执行超过一条指令(即一个多发射处理器)，对于上述例子也是可行的。类似地，虽然描述的是5段流水线操作，对于各种流水线结构中任何其他数目的流水线级数的流水线操作也是可行的。

此外，也可以通过对可执行指令的预处理或使用预定义的指令减少因分支指令处理而导致的时钟周期损失。例如，分支指令可以与非分支指令组合以构成一条复合指令，从而可以在处理该非分支指令的同时处理该分支指令，使得该分支指令所需的时钟周期代价被减少到零或最少。

例如，处理器指令集中通常包含一些保留或未使用的指令，或某些非分支指令中有保留位或未使用的部分。这些非分支指令可以被用于包含分支指令的分支条件和分支目标地址或偏移量等。这样，当执行这些非分支指令时，可以对分支条件进行判定，并在该非分支指令执行的过程中进行分支转移，从而实现零代价的分支处理。由于分支指令大致占处理器执行的指令总数的20％，减少可执行指令总数的20％可以显著增加处理器的性能。

例如，在一个32位指令集中，一类加法指令包含5位的指令码，以4位寄存器号形式出现的两个源操作数和一个目标操作数，这样，在这种情况下，一条加法指令总共用掉了17位，而剩下的15位没有被用到。

另一方面，一类分支指令通过比较两个寄存器的值进行分支判定。作为一条独立的指令，这类分支指令可以包含一个5位的指令码，5位的分支偏移量，以及每个都是4位的寄存器号。这样，该分支指令用掉了18位。

然而，当该加法指令和该分支指令组合在一起构成一条复合指令(如：加法并分支)时，可以对5位的指令码增加1位以表示这条复合指令。这样，这条“加法并分支”指令包含6位的指令码，三个用于加法操作的寄存器号共占12位，两个用于分支转移的寄存器号共占8位，以及5位分支偏移量，总共为31位。这样，在这个例子中，可以在该加法指令被执行的同时执行该分支指令， 从而实现零代价的分支处理。该方法使得零代价的分支转移成为可能。

在其他32位指令集的例子中某些执行类型的指令(如：加法、减法等)可以有一个6位的指令码，以及三个每个为5位寄存器号，总共为21位。这样，为附加的分支操作留下了11位。这种分支操作可以是固定类型的，如当某个特定寄存器的值非零时分支转移发生。这11位中的1位可以被称为分支位，而其他10位可以是分支偏移量。当该分支位被设为“0”时，该指令是一条普通的可执行指令。当该分支位被设为“1”时，该指令除了具有执行该可执行操作(加法等)的功能外，还是一条分支指令。此外，如果寄存器内容不等于零，该内容被减1，而该执行的结果是分支转移到地址为分支偏移量加上该复合指令地址的指令。另一方面，如果该寄存器内容等于零，那么分支转移不发生，下一被执行的指令为紧跟在该复合指令之后的指令。这种类型的指令能够为每次程序循环减少两个时钟周期。

图10显示了本发明所述处理器环境1000的一个实施例。在处理器环境1000中，使用了一个读缓冲229用于提供处理器核125的程序流中的一条分支指令和在该分支指令之后的后续指令。处理器环境与图7中的处理器环境600类似，但有一些区别。如图10所示，处理器环境1000除了缓存124、处理器核125、轨道表126和循迹器170外，还包含一个读缓冲229。

读缓冲229连接在缓存124和处理器核125之间，并包含一个存储模块216和一个选择器214。存储模块216用于存储某些指令，比如在缓存124中一个存储块中的内容。例如，读缓冲229中的存储模块216存储并向外提供分支目标指令及后续指令，而分支目标由缓存124直接提供，使得同样的缓存器124能提供更高的带宽。读缓冲229中的选择器214基于分支判断选择分支目标指令(来自缓存124)或分支指令的后续指令(来自存储模块216)中的一种作为输出219送到处理器核125，使得在分支指令之后提供给处理器核125的指令是有效的或正确的。此外，从轨道表126读出的总线150中的分支目标地址被送到缓存124作为块地址及块内偏移地址；来源于处理器125的PC偏移量155(块内偏移地址)被送到缓存存储模块216。而来自存储器125的‘TAKEN’信号被用于控制选择器214。

在操作过程中，循迹器170提供BNX 152和BNY 153寻址，使得轨道表126可以输出一个对应于该BNX 152和BNY 153的轨迹点。该轨迹点被读出的内容中包含诸如指令类型和分支目标地址等的信息。该内容可以通过总线150被送到循迹器170。当循迹器170检测到一个轨迹点包含一条分支指令的信息时，总线150上的分支目标块地址221(目标BNX)，及分支目标偏移地址222(目标BNY)被送到缓存124，以从缓存124中取出该分支目标指令(也可包括该 分支目标指令同一存储块上的其他指令)放到总线217上送到存储模块216的写端口(write port)以及选择器214的一个输入端。其中分支目标块地址221及分支目标偏移地址222可被寄存器锁存后再送往缓存124寻址。

存储模块216可以包含特定数量的存储单元，用以存储指令。例如，包含一个存储块(如：指令块)的所有指令。处理器核125向存储模块216提供块内偏移量(offset)155来寻址，从存储模块中存储的指令中选择单数或复数条处理器核将要执行的指令送到选择器214的另一个输入端。处理器核125也提供‘TAKEN’信号和‘BRANCH/JUMP’信号至循迹器170以传递分支与否信息。其中‘TAKEN’信号也被送至选择器214作为选择器214的输入，也被送至存储模块216选择是否用缓存124输出的指令块替换存储模块216的内容。

当分支判断时间槽到来时，从存储模块216中被选出放在选择器214的输入端上的指令包含有分支指令后的单数或复数条指令。如果判断结果是不进行分支，那么‘TAKEN’信号控制选择器214选择来自存储模块216的输出(分支指令后的指令)，也控制存储模块216保持现有内容不变。在此情况下，处理器核125执行分支指令后的指令。此时循迹器170移向轨道表同一行中下一个分支指令，重复以上操作。

但是，如果判断结果是进行分支，那么‘TAKEN’信号控制选择器214选择缓存124的输出(分支目标)，也控制存储模块216用缓存124的输出更新存储模块216的内容。在这个情况下，处理器核125执行分支目标指令及分支目标指令后的指令。

此时循迹器170移向轨道表中分支目标指令所在行的所在项。此后，PC偏移量155选择存储模块216中的指令(分支目标指令后的指令)供处理器核125执行，循迹器170移向轨道表同一行中下一个分支指令，重复以上操作。

如此，当处理器核125执行一个分支点对应的分支指令时，可以同时提供分支目标指令和紧跟该分支点的后续指令，从而可以根据分支转移是否发生取到正确的指令。

可以在轨道中最后一条指令之后增加一个无条件转移标志，其转移目标指令就是程序流中紧跟在上述最后一条指令之后的指令。采用前述相同方法，可以在每条轨道上的指令执行完毕后，在不暂停流水线操作的情况下执行之后的指令。

此外，还可以通过检测使分支指令进行分支条件判断所需要的条件最终被确定的指令位置或时间点，在该条件被确定之后就进行分支判定，提前确定分支指令后应执行的指令的地址，从而在不使用现有分支预测方法的情况下，实 现100％成功率的分支预测。图11显示了本发明所述分支预测方法的一个示意图1100。

如图11所示，指令流1101为一系列顺序执行的指令构成的指令流，且执行顺序为自左向右。指令流1101上的指令1102是分支指令。指令流1101上的指令1103、1104、1105均是改变分支指令1102分支条件(或条件标志)的指令，其中指令1105为这些指令中最后一个改变分支指令1102分支条件(或条件标志)的指令。与传统处理器的做法(执行到分支指令1102时再判断转移条件是否满足)不同，在本实施例中，在执行指令1105使得分支指令1102所需的分支条件(或条件标志)均被确定后，即可对分支转移条件是否满足进行判断。

图12是本发明所述分支预测的实施例1200。分支预测系统1200由三部分组成：指令缓冲1201、预检测控制单元1202和时间点检测单元1203。指令缓冲1201中存储了当前正在执行的指令1205和指令1205之后的后续指令。时间点检测单元1203中包含了对应每个分支转移判断条件(或条件标志)的位置寄存器。根据处理器指令集体系结构的不同，分支转移判断条件(或条件标志)可以是通用寄存器、状态寄存器或标志位。可以通过不同分支转移判断条件(或条件标志)进行相互比较，以得到分支转移是否发生的判定结果。也可以将分支转移判断条件(或条件标志)与预设的值进行比较，以得到分支转移是否发生的判定结果。

预检测控制单元1202控制领先指针1204以比处理器程序计数器(PC)更快的速度自当前指令1205沿指令缓冲扫描后续指令，直到到达第一个分支指令1206。在此过程中，读出领先指针指向的指令，送到时间点检测单元1203。由于处理器中可以用于分支转移判断的条件(或条件标志)数量是有限的，因此经时间点检测单元1203中译码器1207译码可知领先指针1204指向的指令是否会改变这些条件(或条件标志)中的一个或多个的值；如果该指令会改变分支转移判断的条件(或条件标志)值，那么同时能知道该指令将改变哪一个或哪些条件(或条件标志)的值。在扫描过程中，一旦发现领先指针1204指向的指令会改变分支转移判断条件(或条件标志)的值，就将该指令的指令位置信息写入时间点判断单元1203中对应被改变的那个或那些条件(或条件标志)的位置寄存器中。

为便于描述，分支预测系统1200以分支指令仅有两种判断条件(COND1和COND2)为例，当具有更多判断条件(或条件标志)时，也可以用同样方法推广实现。

以分支预测系统1200为例，通过对指令缓冲的扫描，从当前指令1205到 第一条分支指令1206之间一共有三条指令会改变判断条件，其中改变COND1值的指令1208的指令位置信息是‘3’，改变COND2值的指令1209的指令位置信息是‘4’，另一条改变COND2值的指令1210的指令位置信息是‘7’。

当领先指针1204指向指令1208时，将指令1208读出并通过总线1211送到译码单元1207，经译码后，发现该指令会改变COND1的值。因此将指令1208的指令位置信息‘3’写入COND1对应的位置寄存器1212中。

同理，当领先指针1204先后指向指令1209和指令1210时，将指令1209的指令位置信息‘4’和指令1210的指令位置信息‘7’先后写入COND2对应的位置寄存器1213中。这样，当领先指针1204到达分支指令1206时，位置寄存器1212和1213中分别存储了执行分支指令1206前最后更新条件值的指令的位置信息。此外，当领先指针1204到达指令1206处，该指令被读出并通过总线1211送到译码单元1207，经译码后发现是分支指令，则通过控制线1216将停止信号发送给预检测控制单元1202，使得领先指针1204停留在分支指令1206处。

同时，由于领先指针1204指向的是分支指令，译码单元1207译码后通过控制线1215选择所有分支条件对应的位置寄存器中与分支指令1206所需判断的条件相关的位置寄存器的值输出到比较单元1218。比较单元1218的另一个用于比较的输入为已完成条件值更新的当前指令的当前指令位置信息1214。

由于该位置寄存器中存储的是指令的位置信息，因此一旦执行完毕位于分支指令1206前的最后更新某个分支判断条件值的指令时，送到比较单元1218的当前指令位置信息1214的值就等于该指令的指令位置信息，即比较单元1218输出“相等”的结果送到控制单元1219，表示该判断条件值已被更新，可以被用于进行分支转移条件是否满足的判断。

按此方法进行，当分支指令1206所需的全部判断条件值均更新完毕时，控制单元1219即可发出“可以判断”的信号1220，允许处理器对分支指令1206进行分支判定，从而提前确定分支指令后应执行的指令的地址，实现100％成功率的分支预测。

虽然在图中没有明示，但是应该理解，时间点检测单元1203还可以从处理器中的寄存器、指令缓冲1201或其他任何合适的来源获取必要的信息，以产生信号1220。同时，时间点检测单元1203还可以向处理器发送必要的信息，以产生信号1220。

此外，在某些情况下，如处理器不进行乱序执行时，也可以不将所需分支判断条件对应的全部位置寄存器的值送到比较单元1218，而是由译码单元1207 译码后发出控制信号，选择所需分支判断条件对应的多个位置寄存器中最大的值(位置值)输出到比较单元1218。这样，当比较单元1218输出“相等”的结果送到控制单元1219，或该位置寄存器值大于等于当前指令位置信息1214的值时，分支指令所需的全部判断条件值均更新完毕。此时，也可以用程序计数器的值作为当前指令位置信息1214的值。

Claims (38)

1.一种控制处理器流水线操作的方法，所述处理器连接包含可执行的计算机指令的存储器；所述方法包括：

判断处理器即将执行的指令是否是分支指令；

提供所述分支指令的分支目标指令地址和所述分支指令在程序序列中的后一指令地址；

决定对应于分支指令的分支判定；和

根据所述分支判定，在所述分支指令到达其在流水线中的执行段前，选择至少所述分支目标指令和所述后一指令中的一个作为处理器中执行单元将要执行的指令，使得无论所述分支指令的转移是否发生都不会导致流水线操作的暂停；

通过审查可执行的计算机指令，提取出至少包含分支信息的指令信息；

根据提取的指令信息建立复数条轨道；和

根据所述复数条轨道确定分支目标指令的地址；

建立一个轨道表；所述轨道表包含对应复数条轨道的复数个轨道表行，每个表行对应一条轨道并包含复数个表项，每个表项对应一个轨迹点，每个所述轨迹点对应至少一条指令。

2.根据权利要求1所述方法，其特征在于：

根据分支类型和分支状态标志决定分支判定。

3.根据权利要求1所述方法，其特征在于所述选择进一步包括：

根据所述分支判定，选择分支目标指令地址和后一指令地址中的一个；和

根据分支目标指令地址和后一指令地址中被选择的一个地址，获取分支目标指令和后一指令中的一个供给执行单元。

4.根据权利要求1所述方法，其特征在于所述选择进一步包括：

使用分支目标指令地址和后一指令地址从存储器中相应获取分支目标指令和后一指令；和

根据分支判定，选择获取到的分支目标指令和获取到的后一指令中的一个供给执行单元。

5.根据权利要求1所述方法，其特征在于所述选择进一步包括：

根据分支目标指令的地址从一个储存装置中获取分支目标指令；

根据后一指令地址从存储器中获取后一指令；和

根据分支判定，选择获取到的分支目标指令和获取到的后一指令中的一个供给执行单元。

6.根据权利要求1所述方法，其特征在于所述方法进一步包括：

根据由第一地址确定的轨道号和由第二地址确定的轨道内偏移量对轨迹点寻址。

7.根据权利要求6所述方法，其特征在于：

由轨道表提供分支类型；和

由处理器提供分支状态标志。

8.根据权利要求6所述方法，其特征在于：

当处理器提供的程序计数器(PC)偏移量等于轨道表分支轨迹点中的偏移量时，进行分支判定。

9.根据权利要求6所述方法，其特征在于：

当处理器执行轨迹点对应的一条指令时，由第一地址确定包含所述指令的存储单元块，根据处理器提供的偏移量在所述存储单元块中可找到所述指令。

10.根据权利要求9所述方法，其特征在于所述方法进一步包括：

可以通过对所述分支指令所在存储单元块的块地址、所述分支指令在所述存储单元块中的偏移量、转移到分支目标指令的转移偏移量三者求和，计算出分支目标指令的地址。

11.根据权利要求10所述方法，其特征在于所述方法进一步包括：

将所述分支目标指令地址作为表项内容存储到轨道表中所述分支指令对应的表项中。

12.根据权利要求11所述方法，其特征在于所述方法进一步包括：

当转移成功时，将所述分支指令对应表项中存储的第一地址和第二地址相应作为下一第一地址和下一第二地址；和

当转移不成功时，保持当前第一地址不变作为下一第一地址，并对当前第二地址加一作为下一第二地址，从而到达轨道表中的下一轨迹点。

13.根据权利要求11所述方法，其特征在于所述方法进一步包括：

当转移成功时，将处理器的程序计数器强制置为分支目标指令的后一指令的地址，使得处理器在执行分支目标指令的同时获取所述分支目标指令的后一指令。

14.根据权利要求1所述方法，其特征在于：

分支指令可以与非分支指令结合，使所述分支指令的分支执行过程与所述非分支指令的执行过程同时进行。

15.一种用于控制处理器流水线操作的流水线控制系统；所述处理器连接包含可执行的计算机指令的存储器；所述系统包括：

一个审查单元，用于判断处理器即将执行的指令是否为分支指令；

一个连接处理器的寻址单元，用于提供所述分支指令的分支目标指令地址和所述分支指令在程序序列中的后一指令地址；

一个分支逻辑单元，用于至少根据轨道单元提供的分支目标指令地址决定关于所述分支指令的分支判定；和

一个选择器，用于根据分支逻辑单元提供的分支判定，在所述分支指令到达其在流水线中的执行段之前，选择分支目标指令和后一指令中的至少一个作为处理器中执行单元将要执行的指令，使得无论所述分支指令的转移是否发生都不会导致流水线操作的暂停；

其特征在于，所述审查单元可以进一步用于：

通过审查所述可执行的计算机指令，提取出至少包含分支信息的指令信息；和

为实现提供所述分支指令的分支目标指令地址和后一指令地址，所述轨道单元可以进一步用于：

根据提取的指令信息建立复数条轨道；和

根据所述复数条轨道确定分支目标指令的地址；

一个轨道表；所述轨道表包含对应复数条轨道的复数个轨道表行，每个表行对应一条轨道并包含复数个表项，每个表项对应一个轨迹点，每个所述轨迹点对应至少一条指令。

16.根据权利要求15所述系统，其特征在于：

所述选择器根据分支判定选择分支目标指令地址和后一指令地址中的一个，从而实现选择分支目标指令和后一指令中的至少一个；和

所述流水线控制系统进一步包括：

一个获取单元，用于根据分支目标指令地址和后一指令地址中被选出的一个地址从存储器中获取分支目标指令和后一指令中的一个，供给执行单元。

17.根据权利要求15所述系统，其特征在于：

所述流水线控制系统进一步包括：

一个获取单元，用于使用分支目标指令地址和后一指令地址相应地从存储器中获取分支目标指令和后一指令；和

所述选择器根据分支判定选择所述获取到的分支目标指令和所述获取到的后一指令中的一个供给执行单元，从而实现选择分支目标指令和后一指令中的至少一个。

18.根据权利要求15所述系统，其特征在于所述系统进一步包括：

一个获取单元和一个储存装置，其中：

所述获取单元用于：

根据分支目标指令地址从所述储存装置中获取分支目标指令；和

根据后一指令地址从存储器中获取后一指令；和

所述选择器根据分支判定选择所述获取到的分支目标指令和所述获取到的后一指令中的一个供给执行单元。

19.根据权利要求15所述系统，其特征在于：

分支指令可以与非分支指令结合，使所述分支指令的分支执行过程与所述非分支指令的执行过程同时进行。

20.根据权利要求15所述系统，其特征在于：

分支指令可以作为包含所述分支指令和一条非分支指令的复合指令的一部分。

21.根据权利要求20所述系统，其特征在于：

所述复合指令包括一个分支位用于表示所述复合指令中包含的分支指令是否将被执行；和

基于一个预先设置的寄存器的内容对所述复合指令中的分支指令进行分支判断。

22.一种控制处理器流水线操作的方法，所述处理器连接包含可执行的计算机指令的存储器；所述方法包括：

判断处理器即将执行的指令是否是分支指令；

提供所述分支指令的分支目标指令地址和所述分支指令在程序序列中的后一指令地址；

根据所述分支目标指令地址和所述后一指令地址相应获取分支目标指令和后一指令；

对所述获取到的分支目标指令和后一指令进行译码；和

根据处理器提供的分支判定选择所述被译码的分支目标指令和被译码的后一指令供给执行单元，使得无论所述分支指令的转移是否发生都不会导致流水线操作的暂停；

其特征在于：

通过审查所述可执行的计算机指令，提取出至少包含分支信息的指令信息；

根据提取的指令信息建立复数条轨道；和

根据所述复数条轨道确定分支目标指令的地址；

建立一个轨道表；所述轨道表包含对应复数条轨道的复数个轨道表行，每个表行对应一条轨道并包含复数个表项，每个表项对应一个轨迹点，每个所述轨迹点对应至少一条指令。

23.一种用于控制处理器流水线操作的流水线控制系统；所述处理器连接包含可执行的计算机指令的存储器；所述系统包括：

一个连接处理器的寻址单元，用于提供分支指令的分支目标指令地址和所述分支指令在程序序列中的后一指令地址；

所述寻址单元包括一个包含对应复数条轨道的复数个轨道表行的轨道表，每个表行对应一条轨道并包含复数个表项，每个表项对应一个轨迹点，每个轨迹点对应至少一条指令；

所述轨道表中存储了对应于轨道表中分支指令的作为表项的内容的分支目标指令地址；

一个连接存储器和处理器的读缓冲，用于至少存储分支指令的分支目标指令和所述后一指令中的一个；

其中，读缓冲还包括一个连接处理器的选择器，用于在分支指令被执行时，向处理器提供分支目标指令或后一指令中的一个，使得无论所述分支指令的转移是否发生都不会导致流水线操作的暂停；

其特征在于：

在第一个周期内，分支目标指令地址被送到存储器用于读出包含分支目标指令在内的至少两条指令；

在第二个周期内，存储器输出所述包含分支目标指令在内的至少两条指令，且分支指令地址被送到存储器用于读出包含分支指令在内的至少两条指令。

24.根据权利要求23所述系统，其特征在于：

所述存储器在一个周期内能够输出至少两条指令；和

所述读缓冲在一个周期内能够存储至少两条指令。

25.根据权利要求24所述系统，其特征在于：

所述存储器包括一个带宽高于处理器指令发射速率的单端口存储模块。

26.根据权利要求24所述系统，其特征在于：

指令地址中的一部分用于从存储器中的一个存储块中读出至少两条指令；和

指令地址中的另一部分用于从所述至少两条指令中选出所述指令。

27.根据权利要求23所述系统，其特征在于：

在第三个周期内，所述包含分支目标指令在内的至少两条指令被存储到读缓冲中，存储器输出所述包含分支指令在内的至少两条指令，且后一指令地址被送到存储器用于读出包含后一指令在内的至少两条指令。

28.根据权利要求27所述系统，其特征在于：

在第四个周期内，读缓冲输出所述包含分支目标指令在内的至少两条指令，且存储器输出所述包含后一指令在内的至少两条指令。

29.根据权利要求27所述系统，其特征在于：

一个来自处理器的表示分支是否成功发生的控制信号用于决定选择所述包含分支目标指令在内的至少两条指令，或选择所述包含后一指令在内的至少两条指令。

30.根据权利要求29所述系统，其特征在于：

程序计数器偏移量的一部分用于从所述包含分支目标指令在内的至少两条指令中选出分支目标指令，或从所述包含后一指令在内的至少两条指令中选出后一指令。

31.一种用于控制处理器流水线操作的流水线控制系统；所述处理器连接包含可执行的计算机指令的存储器；所述系统包括：

一个连接处理器的寻址单元，用于提供分支指令的分支目标指令地址和所述分支指令在程序序列中的后一指令地址；

一个连接存储器和处理器的读缓冲，用于存储当前指令所在的指令段；

其中，读缓冲还包括一个连接处理器的选择器，用于在分支指令被执行时，向处理器提供分支目标指令或分支指令的后一指令中的一个，使得无论所述分支指令的转移是否发生都不会导致流水线操作的暂停；

其特征在于：

所述寻址单元包括一个包含对应复数条轨道的复数个轨道表行的轨道表，每个表行对应一条轨道并包含复数个表项，每个表项对应一个轨迹点，每个轨迹点对应至少一条指令。

32.根据权利要求31所述系统，其特征在于：

使用来自寻址单元的分支目标地址从所述存储器中选出分支目标指令的后一指令；和

使用来自处理器的程序计数器偏移量从读缓冲中选出当前指令的后一指令。

33.根据权利要求32所述系统，其特征在于：

一个来自处理器的表示分支是否成功发生的控制信号用于决定选择来源于所述存储器的分支目标指令，或选择来源于读缓冲的当前指令的后一指令。

34.根据权利要求31所述系统，其特征在于：

可以根据当前指令的类型，对送到存储器的分支目标指令地址进行锁存。

35.根据权利要求31所述系统，其特征在于：

所述轨道表中存储了对应于轨道表中分支指令的作为表项的内容的分支目标指令地址。

36.一种用于控制处理器流水线操作的流水线控制系统；所述处理器连接一个包含可执行的计算机指令的存储器和一个比所述存储器速度更快的指令缓冲；其特征在于所述流水线控制系统包括：

通过审查可执行的计算机指令，提取出至少包含分支信息的指令信息；

根据提取出的指令信息建立对应指令段的轨道；

所述轨道包含复数个轨迹点，每个对应指令段中的一条指令；

一个预检测控制单元，用于控制一个沿读缓冲以比指向当前正在被处理器核执行的当前指令指针更快速度移动的领先指针；所述预检测控制单元可进一步对领先指针经过的指令进行审查，从而提取出至少包含分支指令信息和最后更新分支指令的分支判断条件或条件标志的指令信息的指令信息，使得领先指针停止在至少一条分支指令处；和

一个时间点检测单元，用于在最后更新该分支指令分支条件或条件标志的指令执行后进行分支判定，从而在所述分支指令执行前就可确定其后应被处理器执行的指令是分支目标指令还是所述分支指令后的指令，使得无论所述分支指令的转移是否发生都不会导致流水线操作的暂停。

37.根据权利要求36所述系统，其特征在于所述流水线控制系统进一步用于：

将所有更新分支指令分支条件或条件标志的指令的位置信息存储到相应的位置寄存器中；

对当前指令指针和存储在位置寄存器中的对应至少一条分支指令的位置信息进行比较；和

如果当前指令指针大于或等于存储在所述位置寄存器中的位置信息时，生成一个信号从而进行分支判定。

38.根据权利要求36所述系统，其特征在于：

所述分支指令信息包括直接寻址分支指令信息和间接寻址分支指令信息。