本发明提供一种非循序执行暨循序引退的微处理器，包括：分支信息表以及重排序缓冲器。分支信息表包括N个分支信息项目，N个分支信息项目的每一者用以储存对应分支指令的相关分支信息。重排序缓冲器耦接于分支信息表，重排序缓冲器包括M个项目，M个项目的每一者用以储存微处理器内的未引退指令的相关信息，其中M个项目的每一者均包括第一字段，用以指示未引退指令是否为分支指令，若是，则还包括第二字段用来储存分支信息表的对应标签，对应标签用以指示分支信息表中储存分支指令的相关分支信息的对应分支信息项目，其中N小于M。
一分支预测器，被配置为预测从指令高速缓存提取的分支指令的存在，并产生与分支指令关联的信息；
一分支信息表，包括响应于该指令解码器解码分支指令而以程序顺序指派的N个项目的环形队列，上述N个项目的每一者用以储存由该分支预测器产生的与分支指令之一关联的信息，其中在执行分支指令之后归还已指派的项目；以及一重排序缓冲器，耦接于上述分支信息表，上述重排序缓冲器包括M个项目，上述M个项目的每一者用以储存上述微处理器内的一未引退指令的相关信息，其中上述M个项目的每一者均包括一第一字段，用以指示上述未引退指令是否为一分支指令，若是，则还包括一第二字段用来储存上述分支信息表的一对应标签，该对应标签用以指示上述分支信息表中储存上述分支指令的相关分支信息的一对应分支信息项目；
2.根据权利要求1所述的非循序执行暨循序引退的微处理器，其中该分支预测器进一步被配置为根据上述分支信息表，更新上述分支预测器的分支信息。
3.根据权利要求1所述的非循序执行暨循序引退的微处理器，还包括：一执行单元，用以通过储存于上述分支信息表中的上述对应分支指令的相关分支信息，执行上述对应分支指令，其中存储在所述分支信息表的N个项目的每一个中的与分支指令关联的信息包括该分支指令的预测目标地址，其中为了执行该分支指令，该执行单元利用来自与该分支指令关联的重排序缓冲器项目的标签获得预测目标地址，并且将预测目标地址与正确目标地址比较以确定该分支预测器是否错误预测了该分支指令的目标地址。
4.根据权利要求1所述的非循序执行暨循序引退的微处理器，还包括：一暂存器别名表，用以指派上述分支指令至上述重排序缓冲器的一项目，并将上述分支指令于上述分支信息表的该分支信息项目的一标签填入上述重排序缓冲器的该项目。
5.根据权利要求1所述的非循序执行暨循序引退的微处理器，其中上述指令解码器用以在无法指派上述分支信息表的上述N个分支信息项目的一者时，拖延上述微处理器的指令提取。
6.根据权利要求1所述的非循序执行暨循序引退的微处理器，其中储存于上述分支信息表的上述N个分支信息项目的每一者的上述对应分支指令的相关分支信息包括以下一者或其组合之一：上述对应分支指令的一预测目标地址；
多个分支型态位，用以指示上述对应分支指令的分支型态；以及上述对应分支指令的多个效能追踪位。
7.根据权利要求1所述的非循序执行暨循序引退的微处理器，其中储存于上述分支信息表的上述N个分支信息项目的每一者的上述对应分支指令的上述分支信息包括多个指示位，用以指示上述对应分支指令的一提取地址是否命中上述微处理器的一分支目标地址高速缓存。
8.根据权利要求1所述的非循序执行暨循序引退的微处理器，其中上述M个项目的每一者还包括一第三字段，用以指示上述分支指令是否发生。
9.一种关于非循序执行暨循序引退的微处理器的信息储存方法，包括：由一分支预测器预测从指令高速缓存提取的分支指令的存在，并产生与分支指令关联的信息；
在一分支信息表中存储与分支指令关联的信息，该分支信息表包括响应于该指令解码器解码分支指令而以程序顺序指派的N个项目的环形队列，其中上述N个项目的每一者用以储存由该分支预测器产生的与分支指令之一关联的信息，其中在执行分支指令之后归还已指派的项目；以及储存上述微处理器内的多个未引退指令的相关信息于一重排序缓冲器，上述重排序缓冲器包括M个项目，其中上述M个项目的每一者用以储存一未引退指令的相关信息，其中上述M个项目的每一者均包括一第一字段，用以指示上述未引退指令是否为一分支指令，若是，则还包括一第二字段用来储存上述分支信息表的一对应标签，该对应标签用以指示上述分支信息表中储存上述分支指令的相关分支信息的一对应分支信息项目；
10.根据权利要求9所述的关于非循序执行暨循序引退的微处理器的信息储存方法，还包括：根据上述分支信息表，更新该分支预测器的分支信息。
11.根据权利要求9所述的关于非循序执行暨循序引退的微处理器的信息储存方法，还包括：通过储存于上述分支信息表中的上述对应分支指令的相关分支信息，执行上述对应分支指令，其中存储在所述分支信息表的N个项目的每一个中的与分支指令关联的信息包括该分支指令的预测目标地址，其中所述执行分支指令包括，利用来自与该分支指令关联的重排序缓冲器项目的标签获得预测目标地址，并且将预测目标地址与正确目标地址比较以确定该分支预测器是否错误预测了该分支指令的目标地址。
12.根据权利要求9所述的关于非循序执行暨循序引退的微处理器的信息储存方法，还包括：指派上述分支指令至上述重排序缓冲器的一项目，并将上述分支指令于上述分支信息表的该分支信息项目的一标签填入上述重排序缓冲器的该项目。
13.根据权利要求9所述的关于非循序执行暨循序引退的微处理器的信息储存方法，还包括：在无法指派上述分支信息表的上述N个分支信息项目的一者时，拖延上述微处理器的指令提取。
14.根据权利要求9所述的关于非循序执行暨循序引退的微处理器的信息储存方法，其中储存于上述分支信息表的上述N个分支信息项目的每一者的上述对应分支指令的相关分支信息包括以下一者或其组合之一：上述对应分支指令的一预测目标地址；
多个分支型态位，用以指示上述对应分支指令的分支型态；以及上述对应分支指令的多个效能追踪位。
一种微处理器和其信息储存方法
技术领域
[0001] 本发明是有关于微处理器，特别是有关于非循序执行的微处理器内的分支预测。
背景技术
[0002] 微处理器的架构规格(例如x86架构微处理器)都要求指令依照程序的顺序将其结果写入微处理器架构的可视状态中(此时通常称为指令循序引退(in-order retirement))。然而，就指令执行而言，循序引退指令的微处理器的微架构是以非循序方式(out-of-order)(也就是不会依照程序顺序，或称乱序)执行指令以产生指令结果。这类的微处理器通常会使用一称为重排序缓冲器(reorder buffer，ROB)的硬件架构或是类似的架构，用以在指令非循序执行的情况下循序引退指令。
[0003] 重排序缓冲器用以储存处理器中每一个未引退指令的信息。未引退指令是指已经被提取、解码、甚至被执行(即执行单元已经产生其结果)，或者是等待发送以被执行的指令，其结果仍未写入微处理器架构的状态中。特别的是，重排序缓冲器储存的信息包含未引退指令之间的程序顺序(programorder)。此外，重排序缓冲器也用以储存每一个未引退指令的其它大量信息。
[0004] 所有微处理器都包括多个分支指令于其指令集内。一般而言，处理器会依序地提取指令。然而，分支指令却会指示处理器自不连续的位置(non-sequential location)提取指令。因为分支指令在微处理器管线的前级被提取，却在管线的后级才被执行(即分支方向(direction)和目标地址最后才被决定)，所以分支指令会造成管线泡(pipeline bubbles)，而使得微处理器无法有效利用，并且会增加指令时钟周期数(clocks per instruction，CPI)，这是微处理器设计领域常见的问题。
[0005] 为了克服上述问题，现今的微处理器都包括分支预测器(branchpredictors)，当指令被提取时，可用来预测分支指令和分支结果。分支预测是微处理器设计领域一种的技术手段。然而，当分支指令在管线中被执行时，大量的信息(分支信息)会被储存，用以修正分支指令的错误预测，以及用以更新分支预测器中的分支历史信息，使得分支预测器能够更正确地预测分支指令后续的执行操作。每一个分支指令需要储存的分支信息的位数(分支信息位)为200位。再者，用以储存分支信息的重排序缓冲器，其项目(entry)的数量也非常重要。当微处理器的执行资源(execution resources)增加时，重排序缓冲器中所需的项目数量亦需大幅增加，如此才能充分利用微处理器的执行资源。但是，如此一来，分支信息位的储存会造成重排序缓冲器的芯片面积变大，且亦会增加功率的消耗。
发明内容
[0006] 本发明一实施例提供一种非循序执行暨循序引退的微处理器，包括：分支信息表以及重排序缓冲器。分支信息表包括N个分支信息项目，N个分支信息项目的每一者用以储存对应分支指令的相关分支信息。重排序缓冲器耦接于分支信息表，重排序缓冲器包括M个项目，M个项目的每一者用以储存微处理器内的未引退指令的相关信息，其中M个项目的每一者均包括第一字段，用以指示未引退指令是否为分支指令，若是，则还包括第二字段用来储存分支信息表的对应标签，对应标签用以指示分支信息表中储存分支指令的相关分支信息的对应分支信息项目，其中N小于M。
[0007] 本发明另一实施例提供关于非循序执行暨循序引退的微处理器的信息储存方法，包括：储存分支信息表，其包括N个分支信息项目，其中N个分支信息项目的每一者用以储存对应分支指令的相关分支信息；以及储存微处理器内的多个未引退指令的相关信息于重排序缓冲器，重排序缓冲器包括M个项目，其中M个项目的每一者用以储存未引退指令的相关信息，其中M个项目的每一者均包括第一字段，用以指示未引退指令是否为分支指令，若是，则还包括第二字段用来储存分支信息表的对应标签，对应标签用以指示分支信息表中储存分支指令的相关分支信息的对应分支信息项目，其中N小于M。
附图说明
[0008] 图1为本发明的微处理器的方块图；
[0009] 图2为本发明的一方块图用以显示分支信息表内项目的内容；
[0010] 图3为一方块图用以显示重排序缓冲器内项目的内容；
[0011] 图4为图1的微处理器的操作流程图。
[0012] [主要元件标号说明]
[0013] 100～微处理器；102～指令高速缓存；
[0014] 104～x86指令字节队列；106～指令格式器；
[0015] 107～分支信息表；108～已格式化指令队列；
[0016] 112～指令转译器；116～暂存器别名表；
[0017] 117～重排序缓冲器；118～保留站；
[0018] 122～执行单元；126～提取单元；
[0019] 128～分支预测器；142～提取地址；
[0020] 144～加法器；146～预测目标地址；
[0021] 148～已执行目标地址；152～提取地址；
[0022] 154～分支信息；
[0023] 202～预测目标地址字段；
[0024] 204～全域分支样式字段；
[0025] 206～提取地址字段；
[0026] 208～传回堆栈指针/有效字段；
[0027] 212～分支目标地址高速缓存路径命中/有效字段；
[0028] 214～分支型态字段；216～效能追踪位；
[0029] 302～正常指令信息字段；304～分支旗标；
[0030] 306～分支发生旗标；308～分支信息表标签字段。
具体实施方式
[0031] 一般而言，分支指令仅占程序指令的15-20％。因此，发明人注意到：对多数混合程序指令来说，重排序缓冲器中的多数项目其所储存的分支信息是没有使用到的。根据本发明实施例，本发明使用一种分立架构(separatestructure)-『分支信息表』-来储存分支信息，即此分支信息对分支指令而言是具有独特性(unique)。本发明的优点在于：相较于重排序缓冲器中项目的数量，分支信息表中项目的数量较少。在一实施例中，重排序缓冲器的大小为48个项目，而分支信息表的大小为16个项目。分支信息表中的每一项目是由一个标签(tag)作为索引(index)。每一个重排序缓冲器的项目均具有一个字段(field)用以指示与此项目有关的指令是否为分支指令，以及另一个字段，用来储存分支指令对应分支信息表中一项目的标签。
[0032] 图1为根据本发明的微处理器100的方块图。微处理器100包括由多个级(stages)或多个功能单元所构成的管线，此管线包括提取单元126、指令高速缓存102、x86指令字节队列104(x86 instruction byte queue，XIBQ)、指令格式器(instruction formatter)106、已格式化指令队列(formattedinstruction queue)108、指令转译器112、暂存器别名表(register aliastable，RAT)116、多个保留站(reservation station)118以及多个执行单元122。提取单元126提供提取地址142至指令高速缓存102以选择一包含多个指令字节(instruction bytes)的快取列(cache line)，上述快取列被提供至x86指令字节队列104。微处理器100还包括加法器144，加法器144用以将目前的提取地址142增量(increment)而产生下一个接续的提取地址152至提取单元126。提取单元126也从分支预测器128接收预测目标地址(predictedtarget address)146。提取单元126由执行单元122接收已执行目标地址(executed target address)148。
[0033] 分支预测器128提供分支信息154至x86指令字节队列104。此外，分支信息154用以指示分支预测器128是否预测一分支指令将出现于x86指令字节队列104中的上述快取列。若分支信息154指示要取用(taken)此分支指令(亦即分支发生)，则提取单元126选择由分支预测器128提供的预测目标地址146。在一实施例中，分支信息154除了包含是否取用(taken/not taken，T/NT)分支指令的预测指示(prediction indicator)之外，还包括预测目标地址146、全域分支样式(global branch pattern)、提取快取列的提取地址142、对应一传回堆栈的多个指针(stack pointers)和有效位(valid bits)和由分支预测器128的分支目标地址高速缓存(branch target address cache，BTAC)所提供的多个指示位，其中全域分支样式用来作出预测结果(例如在gshare预测器中使用的预测)，分支预测器128使用提取快取列的提取地址142进行预测，前述多个指示位并包括多个路径命中/有效位(way hit/valid bits)和多个分支型态位(branch type bits)(例如条件分支型态、非条件分支型态、传回(return)型态、呼叫(call)型态)。上述多个路径命中/有效位用以指示提取分支指令的上述提取地址是否命中上述分支目标地址高速缓存。
[0034] x86指令字节队列104是包含多个项目的队列，其每一项目均包含来自于指令高速缓存102的多个字节的数据。一般而言，指令格式器106为一指令解码器。在一实施例中，微处理器100是x86架构的微处理器，其指令集包括可变长度指令(variable length instructions)。指令格式器106用以检查由x86指令字节队列104提取回来的多个指令字节的串流(stream)，并且决定串流内每一个指令的起始字节(beginning byte)和终止字节(endingbyte)，并且藉此将字节的串流断开(格式化)为多个x86指令的串流。已格式化的x86指令的串流被提供至已格式化指令队列108，并加以储存以让微处理器100剩余的管线处理。指令转译器112将巨指令(例如x86分支巨指令)转译为成多个微指令，用以实现此巨指令。在一实施例中，指令转译器112将每一个分支巨指令转译为一分支微指令。
[0035] 微处理器100也包括重排序缓冲器117，其耦接至暂存器别名表116、保留站118，以及执行单元122。微处理器100也包括分支信息表(branchinformation table，BIT)107，其耦接至指令格式器106、重排序缓冲器117，以及分支预测器128。重排序缓冲器117为具有多个项目的环形队列(关于重排序缓冲器117项目的细节如图3所示)。暂存器别名表116依程序顺序指派指令转译器112产生的多个微指令至重排序缓冲器117中的多个项目。分支信息表107为具有多个项目的环形队列(关于分支信息表107项目的细节如图2所示)。在一实施例中，分支信息表107中项目的数量小于重排序缓冲器117中项目的数量的一半。指令格式器106依程序顺序指派遇到(encounter)的多个分支指令至分支信息表107中的多个项目。以下将搭配图示详述重排序缓冲器117和分支信息表107的技术内容和相关操作。
[0036] 根据本发明的一实施例，图2为一方块图用以显示分支信息表107内一项目的内容。每一个项目都包括48位的预测目标地址字段202、40位的全域分支样式字段(global branch pattern field)204、32位的提取地址字段206、20位的传回堆栈指针/有效字段(return stack pointers/valid field)208、8位的分支目标地址高速缓存路径命中/有效字段(BTAC way hit/validfield)212、10位的分支型态字段(branch type field)214，以及多个效能追踪位(performance tracking bits)216。在一实施例中，在分支信息表107中每一个项目内储存的数据量约为170位。在另一实施例中，在分支信息表107中每一个项目内储存的数据量至少100个位。
[0037] 根据本发明的一实施例，图3为一方块图用以显示重排序缓冲器117内一项目的内容。每一个项目包括一正常指令信息字段302，用以储存被指派至该项目的一指令的正常指令信息(normal instruction information)，上述指令也包含分支指令。正常指令信息字段302储存上述指令的指令结果和指令状态。当该指令被不同的管线级处理时，该项目中的指令结果和指令状态(包括异常信息)会被更新。每一个项目也包括一分支旗标304，若指令为分支指令，分支旗标304则为真值。每一个项目也包括一分支发生旗标(branch taken flag)306，若分支预测器128预测分支指令被取用(亦即分支发生)，分支发生旗标306则为真值。最后，每一个项目包括分支信息表标签字段(BIT tag field)308，用以储存分支信息表107的一标签，而该标签为一索引，用以指示分支信息表107中具有与分支指令相关的分支信息的项目。
[0038] 根据本发明的实施例，图4为图1的微处理器100的操作流程图。流程始于步骤402。
[0039] 在步骤402，提取单元126从提取地址142提取指令高速缓存102中一包含多个指令字节的快取列。流程前进至步骤404。
[0040] 在步骤404，分支预测器128预测在已提取的快取列中具有一分支指令，并且产生相关的分支信息154。流程前进至步骤406。
[0041] 在步骤406，经由x86指令字节队列104向下递送分支信息154至指令格式器106。流程前进至步骤408。
[0042] 在步骤408，指令格式器106解码分支指令。流程前进至步骤412。
[0043] 在决定步骤412，指令格式器106判断分支信息表107是否填满(full)，即指令格式器106试图在分支信息表107中指派一个项目给分支指令，若不能够指派一个项目给分支指令，则表示分支信息表107是填满的。若分支信息表107是填满的，流程前进至步骤414；否则，流程前进至步骤416。
[0044] 在步骤414，指令格式器106设置一信号，用以拖延(stall)指令格式器106之上的指令提取管线，并且流程回到决定步骤412，直到分支信息表107不再是填满的。在一实施例中，指令提取管线将根据一设置信号暂停指令的提取。
[0045] 在步骤416，指令格式器106将与分支指令有关的分支信息填入分支信息表107中被指派到的项目之内。流程前进至步骤418。
[0046] 在步骤418，指令格式器106储存分支指令以及分支信息表107中被指派到的项目的分支信息表标签至已格式化指令队列108。流程前进至步骤422。
[0047] 在步骤422，在管线中向下递送分支信息表标签以及分支指令至暂存器别名表116。流程前进至步骤424。
[0048] 在步骤424，暂存器别名表116指派分支指令至重排序缓冲器117中的一个项目，并且将分支信息表标签填入重排序缓冲器117中被指派到的项目之内。流程前进至步骤426。
[0049] 在步骤426，执行管线使用分支信息表标签来存取分支信息表107中一项目的分支信息以执行分支指令。具体地说，执行单元122比较预测目标地址146与执行单元122计算出的实际目标地址(或正确目标地址)来判断是否有预测错误的情况发生。在一实施例中，执行单元122比较重排序缓冲器117中被指派一条件分支指令的一项目中的已预测的分支发生旗标306与执行单元122从条件码旗标(condition code flag)计算出的实际分支方向(或正确分支方向)来判断是否有预测错误的情况发生，以执行上述条件分支指令。此外，执行管线通知分支预测器128分支指令已经被执行，并且为了更新分支历史信息(branch history information)，分支预测器128对应地使用分支信息表107的标签来存取分支信息表107中其它项目的分支信息以更新分支信息。在一实施例中，微处理器100用以更新分支信息表107中的分支信息，例如效能追踪位216。流程前进至步骤428。
[0050] 在步骤428，当分支指令已被执行，重排序缓冲器117引退分支指令并归还(deallocate)分支信息表107中被指派给上述分支指令的项目，以及归还重排序缓冲器117中被指派给上述分支指令的项目。流程结束于步骤428。
[0051] 由前述可知，相较于已知的设计(即在每一个重排序缓冲器117的项目内储存分支信息)，本发明的优点在于：分支信息表107对于缩小芯片面积和降低消耗功率极有帮助。在另一方面，也可能会降低具有多个密集的分支指令的程序的效能，例如在一个由48个指令构成的指令群组中具有16个以上的分支指令。这是因为部分分支指令无法取得分支信息表而造成管线泡。
[0052] 虽然本发明已经由数种实施例揭露如上，但其仅用以作为例子，并非用以限定本发明。计算器领域的本领域技术人员应能理解，在不脱离本发明的精神的前提下，当可对本发明作些许更动。举例而言，软件能够致能本发明的装置和方法的功能、制造、模型建立、仿真、各种性质以及/或测试。其能够通过不同的程序语言而达成，例如程序语言(如C、C++)、硬件描述语言(hardware description language，HDL，如Verilog HDL、VHDL)，或是其它可能的程序语言。上述软件能够设置于任何已知的计算器可读取储存媒体(computer usable medium)，例如半导体、磁盘，或光盘(如CD-ROM、DVD-ROM)。本发明的装置和方法可能包括于任何半导体智慧财产核心(semiconductorIP core)之内，例如(以HDL嵌入的)微处理器核心，或是当集成电路制造时，转移至硬件。此外，本发明可能通过硬件和软件的组合而实现。因此，本发明不应被此处所述的任何实施例所限制，本发明应该是根据所附权利要求范围与其等效的装置/方法而被定义。特别的是，本发明能够设置于一般用途计算器的微处理器装置内。最后，本领域技术人员应能理解到：在不脱离由权利要求范围定义的本发明范畴的前提下，其能够以本发明揭露的概念和特定的实施例作为基础，用以设计或修改其它架构来执行与本发明相同的目的。
