更新微处理器中的分支目标地址快取的方法及其微处理器

摘要

本发明提供一种更新微处理器中的分支目标地址快取的方法及其微处理器，其中该微处理器包括分支目标地址快取(BTAC)、执行单元及更新逻辑电路。执行单元执行事先从一指令快取的提取总量中提取的分支指令。更新逻辑电路耦接至BTAC与执行单元，更新逻辑电路判断BTAC是否已经储存位于提取总量中的N个分支指令的分支预测信息，其中N至少等于二；若BTAC尚未储存N个分支指令的分支预测信息，则使用分支指令的分支信息来更新BTAC；若BTAC已经储存N个分支指令的分支预测信息，则判断分支指令的替换优先权是否高于BTAC中的N个分支指令的替换优先权；以及若分支指令的替换优先权高于BTAC中的N个分支指令的替换优先权，则使用分支指令的分支信息来更新BTAC。

说明书

技术领域

本发明是关于微处理器，特别是关于微处理器中的分支目标地址快取(branch target address caches)。

背景技术

传统的分支目标地址快取(branch target address cache；BTAC)大约只能将两个分支指令储存至指令数据的一给定对齐(aligned)的16字节片段中。此设计选择是为了缩短耗时并减少功率消耗与晶粒尺寸。允许储存三个或四个分支指令要比储存两个分支指令复杂的多。虽然从指令快取中提取三个或多个分支指令(其初始字节皆在相同的16字节中)的情况并不多见，但此情况确实会发生并且会对效能产生负面影响。

发明内容

本发明提供一种微处理器，包括一分支目标地址快取、一执行单元以及一更新逻辑电路。分支目标地址快取中的各个项目用以储存至多N个分支指令的多个分支预测信息。执行单元用以执行事先从一指令快取的一提取总量中提取的一分支指令。更新逻辑电路耦接至分支目标地址快取与执行单元，更新逻辑电路用以判断分支目标地址快取是否已经储存位于提取总量中的N个分支指令的分支预测信息，其中N至少等于二；若分支目标地址快取尚未储存位于提取总量中的N个分支指令的分支预测信息，则使用分支指令的分支信息来更新分支目标地址快取；若分支目标地址快取已经储存位于提取总量中的N个分支指令的分支预测信息，则判断分支指令的替换优先权是否高于分支目标地址快取中的N个分支指令的替换优先权；以及若分支指令的替换优先权高于分支目标地址快取中的N个分支指令的替换优先权，则使用分支指令的分支信息来更新分支目标地址快取。

本发明提供一种更新微处理器中的一分支目标地址快取(BTAC)的方法， 其中分支目标地址快取中的各个项目用以储存来自一指令快取的一提取总量中至多N个分支指令的多个分支预测信息。上述方法包括执行事先从指令快取的提取总量中提取的一分支指令。判断分支目标地址快取是否已经储存位于提取总量中的N个分支指令的分支预测信息，其中N至少等于二。若分支目标地址快取尚未储存位于提取总量中的N个分支指令的分支预测信息，则使用分支指令的分支信息来更新分支目标地址快取。若分支目标地址快取已经储存位于提取总量中的N个分支指令的分支预测信息，则判断分支指令的替换优先权是否高于分支目标地址快取中的N个分支指令的替换优先权。若分支指令的替换优先权高于分支目标地址快取中的N个分支指令的替换优先权，则使用分支指令的分支信息来更新分支目标地址快取。

为让本发明的上述和其它目的、特征、和优点能更明显易懂，下文特举出较佳实施例，并配合所附图式，作详细说明如下。

附图说明

图1为本发明实施例的微处理器的方块图；

图2为本发明实施例的指令快取的方块图；

图3为图1中的分支目标地址快取的配置方块图；

图4为图1中的更新逻辑电路所使用的分支指令型式优先权的结构图；

图5A和5B为图1中的微处理器的操作流程图。

[主要元件标号说明]

100～微处理器；        102～指令快取；

104～提取单元；        106～指令解码器；

108～指令队列；        112～加法器；

116～寄存器别名表；    118～保留站；

122～执行单元；        124～引退单元；

126～第二分支历史表；  128～分支目标地址快取；

132～返回堆栈；        134～控制逻辑电路；

136～更新逻辑电路；    138～虚拟随机产生器；

142～提取地址；        144～下一个序列提取地址；

146～预测分支目标地址；148～预测返回地址；

152～正确目标地址；    154～分支目标地址；

162～整体分支样式；    164～第一分支历史表；

166～虚拟随机指标；    168～通用寄存器；

202～快取线；          302～项目；

304～分支目标地址预测；306～方向预测；

308～分支指令型式；    312～有效位。

具体实施方式

为了减少上述问题所造成的效能影响，以下实施例将提供一种替换策略(replacement policy)，适用于从指令快取中提取的快取线的相同部分或总量(例如16字节)中具有额外分支指令(例如第三分支指令)的情况。此替换策略为一种以相关分支指令的型式为基础的优先机制(priority scheme)，并且具有取代优先机制的虚拟随机措施(pseudo-random provision)用以适应不同的极端状况(corner cases)。

图1为本发明实施例的微处理器100的方块图。微处理器100包括一指令快取102以及一提取单元104，提取单元104提供的提取地址142用以存取指令快取102。提取单元104通过选择不同来源所提供的多个地址中的一者来输出提取地址142，上述来源包括：提取地址142本身、用以递增提取地址142的加法器112所提供的下一个序列提取地址144、分支目标地址快取(BTAC)128提供的预测分支目标地址146、返回堆栈(return stack)132提供的预测返回地址148、执行单元122提供的正确目标地址152，以及指令解码器106提供的分支目标地址154。控制逻辑电路134用以根据来自第一分支历史表164与第二分支历史表126的方向预测以及分支目标地址快取128的信息，控制提取单元104选择多个输入中的一者。举例而言，分支目标地址快取128的信息包括方向预测与分支指令预测的型式(例如呼叫/返回指令、间接分支(indirect branch)指令、条件相对(conditional relative)指令、非条件相对(unconditional relative)指令)。

指令快取102根据提取地址142提供指令字节的快取线202至指令解码器106。指令快取102在每个时钟周期提供部分快取线202而不是整个快取线202。如图2所示，在本实施例中各个快取线202为64字节，并且指令快取102在每个时钟周期提供部分快取线202(16字节)至指令解码器106或指令缓冲器(图未显示)。指令解码器106用以将指令字节解码。在本实施例中， 指令解码器106将x86架构指令转译成微指令(microinstructions)并提供至指令队列(instruction queue)108。当指令解码器106将一分支指令解码时(该分支指令的目标地址是以相对于分支指令的地址的偏移量来计算)，指令解码器106计算分支目标地址154并将分支目标地址154提供至提取单元104。此外，指令解码器106将分支指令的地址提供至第二分支历史表(branchhistory table)126。第二分支历史表126储存关于先前执行的分支指令的方向历史信息。若分支指令地址命中于(hits in)第二分支历史表126，则分支指令地址预测分支指令会被取用(taken)并将预测结果传送至控制逻辑电路134。控制逻辑电路134使用上述预测来控制提取单元104。

指令队列108将程序顺序中的指令提供至寄存器别名表(register alias table；RAT)116，寄存器别名表116用以维护并产生各个指令的相依性信息(dependency information)。寄存器别名表116将指令配送(dispatch)至保留站(reservation station)118，保留站118用以将指令(可能是程序顺序外的指令)发送至执行单元122。执行单元122用以执行分支指令。执行单元122也显示不同的分支预测器(分支目标地址快取128、返回堆栈132、第二分支历史表126以及第一分支历史表164)是否已正确地预测分支指令。执行单元122也根据分支指令的执行，使用历史信息来更新上述不同的分支预测器。执行单元122也将正确目标地址152提供至提取单元104。执行单元122也更新微处理器100所储存的整体分支样式(globalbranch pattern)162，当提取地址142出现于第一分支历史表164时，第一分支历史表164会使用整体分支样式162来执行方向预测。在执行单元122执行指令之后，引退单元(retire unit)124用以引退由重排序缓冲器(图未显示)所储存的程序顺序中的指令。

请参考图3，图3为图1中的分支目标地址快取128的配置方块图。分支目标地址快取128用以储存关于先前执行的分支指令的信息，并且在后续执行期间使用此信息来预测这些分支指令的目标地址、方向以及型式。如图3所示，分支目标地址快取128中的各个项目(entry)302包括一有效位312、一分支目标地址预测304、一方向预测306(即分支指令是否会被取用(taken)或不取用(not taken))以及一分支指令型式308。在一实施例中，分支指令型式308用以指定分支指令是否为一呼叫/返回指令、间接分支指令、条件相对分支指令或非条件相对分支指令。微处理器100中的更新逻辑电路136的 优点在于使用分支指令型式308用以明智地替换分支目标地址快取128中的项目302，细节将在以下做进一步说明。如图3所示，分支目标地址快取128可在指令快取102中的快取线202的各个部分或提取总量(fetchquantum)(例如16字节)中储存两个项目302(标记为“A”与“B”)。换言之，分支目标地址快取128可储存部分快取线202中的至多两个分支指令的预测信息。如上所述，在部分快取线202中具有超过两个分支指令的情况下，此限制会降低分支预测的效能。然而，更新逻辑电路136使用一明智的替换策略用以降低效能影响，细节将在以下做进一步说明。在一实施例中，分支目标地址快取128也包括各个A/B项目对(entry pairs)的一最近最少使用(least-recently-used；LRU)位(图未显示)，用以显示最近最少使用A侧还是B侧以便决定是否要替换A项目302或B项目302。在本实施例中，虽然分支目标地址快取128储存每个部分快取线202(16字节)中的两个分支指令的预测信息，但可依据设计需要来改变部分快取线202的大小以及每个部分快取线202中的分支指令的数目。

参考回图1，当提取地址142出现于分支目标地址快取128时，分支目标地址快取128将信息提供至提取单元104、指令解码器106、返回堆栈132以及控制逻辑电路134。仔细而言，分支目标地址快取128将作为预测分支目标地址146的分支目标地址预测304提供至提取单元104，并且将方向预测306与分支指令型式308提供至控制逻辑电路134。此外，分支指令型式308沿着具有分支指令的管线传递，并且执行单元122随后将分支指令型式308提供至更新逻辑电路136以便执行分支目标地址快取128的替换策略，细节将在以下做进一步说明。

返回堆栈132用以储存由呼叫指令产生的返回地址。当分支目标地址快取128显示提取地址142所指定的部分快取线202包含一呼叫指令时，返回堆栈132将具有一返回地址。当分支目标地址快取128显示提取地址142所指定的部分快取线202包含一返回指令时，返回堆栈132将预测返回地址148提供至提取单元104。

微处理器100也包括一虚拟随机产生器138用以提供一虚拟随机指针166至更新逻辑电路136。更新逻辑电路136的优点在于使用虚拟随机指针166来执行分支目标地址快取128的替换策略，用以改善以严格优先权为基础(strictly priority-based)的替换策略，细节将在以下做进一步说明。在一 实施例中，虚拟随机产生器138为一15位的线性反馈移位寄存器(linearfeedback shift register；LFSR)，用以在虚拟随机顺序中的所有2¹⁵个状态(除了全为0状态)内循环，并且在虚拟随机产生器138产生相同的重复产生样式(generation pattern repeats)之前，时钟周期数量为32767个时钟周期。当有需要时，可从15位中取样5位来产生虚拟随机指针166。因此，虚拟随机指标166大约每32个时钟周期平均为真值(true)一次。

请参考图4，图4为图1中的更新逻辑电路136所使用的分支指令型式优先权的结构图。如图4所示，间接型式的分支指令具有最高优先权(表示最后才被替换)，呼叫/返回型式的分支指令具有第二高优先权，条件相对型式的分支指令具有第三高优先权，而非条件相对型式的分支指令具有最低优先权(表示可最先被替换)。

相对型式的分支指令的目标地址是以相对于分支指令的地址的总偏移量来计算，并且偏移量为指令本身中的字段。因此，指令解码器106可正确地计算相对型式的分支指令(包括条件相对分支指令以及非条件相对分支指令)的分支目标地址154。此外，由于已经知道非条件相对分支指令的方向，因此指令解码器106可准确地解析(resolve)非条件相对分支指令。因此，分支目标地址快取128误预测(mispredict)一非条件相对分支指令所产生的代价(penalty)，相对小于误预测其它型式的分支指令所产生的代价。在一实施例中，误预测代价在最糟的情况下大约为七个时钟周期，但根据指令队列108的使用率(fullness)，误预测代价也会少于七个时钟周期。这就是为什么非条件相对分支指令具有最低优先权(表示可最先被替换)。在一实施例中，分支目标地址快取128的项目302包括一旗标(flag)用以显示分支指令是否为一非条件相对分支指令，因此若部分快取线202中具有超过两个分支指令，则更新逻辑电路136替换分支目标地址快取128中的非条件相对分支指令，并且更新逻辑电路136通常不会将其它型式的分支指令替换为一非条件相对分支指令。

与相对型式的分支指令相比，微处理器100的通用寄存器168中的某些操作数(operand)或存储器位置中的某些操作数可用来计算一间接型式的分支指令目标地址。因此，指令解码器106不会预测间接分支指令，并且是由执行单元122来计算间接分支指令目标地址。因此，分支目标地址快取128误预测一间接分支指令所产生的代价，通常会大于误预测其它型式的分支指 令所产生的代价。这就是为什么间接分支指令具有最高优先权(表示最后才被替换)。

此外，替换分支目标地址快取128中的呼叫/返回指令(返回堆栈132中具有该呼叫/返回指令的一有效返回地址)，会导致返回堆栈132未对齐(misaligned)使得返回堆栈132很有可能在之后会误预测，因而产生负面效能影响。这就是为什么呼叫/返回指令具有第二高优先权。

最后，虽然通过指令解码器106(目标地址)、第二分支历史表126(方向)以及分支目标地址快取128来预测条件相对分支指令，但由于在本实施例中的分支目标地址快取128的大小大于第二分支历史表126，因此分支目标地址快取128的方向预测会比较准确。此外，从分支目标地址快取128中移除条件相对分支指令会导致整体分支样式162产生误差。基于上述理由，条件相对分支指令是高于非条件相对分支指令因而具有第三高优先权。

请参考图5，图5为图1中的微处理器100的操作流程图。流程从步骤502开始。

在步骤502中，执行单元122执行一全新的分支指令并提供相关信息至更新逻辑电路136。流程前进至步骤504。

在步骤504中，更新逻辑电路136使用上述分支指令的地址用以在分支目标地址快取128中建立索引。流程前进至判断步骤506。

在判断步骤506中，更新逻辑电路136检查A项目302与B项目302的有效位312，用以判断快取线202的相同部分(same portion)中是否具有超过两个分支指令。若有，流程前进至步骤512；若没有，流程前进至步骤508。

在步骤508中，更新逻辑电路136使用与上述分支指令相关的执行信息来更新分支目标地址快取128。换言之，更新逻辑电路136写入无效的A项目302或B项目302。流程结束于步骤508。

在步骤512中，更新逻辑电路136检查执行单元122所提供的上述分支指令的分支指令型式308，以及A项目302与B项目302中的两个有效分支指令(根据不同实施例，上述两个有效分支指令是来自于分支目标地址快取128或执行单元122)的分支指令型式308。流程前进至判断步骤514。

在判断步骤514中，更新逻辑电路136判断上述分支指令的分支指令型式308是否高于A项目302与B项目302中的两个有效分支指令的分支指令型式308。若是，流程前进至步骤516；若否，流程前进至步骤518。

在步骤516中，更新逻辑电路136使用与上述分支指令相关的执行信息来更新分支目标地址快取128。换言之，更新逻辑电路136替换A项目302与B项目302中的两个有效分支指令中的一者。在一实施例中，更新逻辑电路136根据LRU位选择索引集合(indexed set)与选择路径(selected way)的A项目302或B项目302。流程结束于步骤516。

参考步骤518，更新逻辑电路136检查虚拟随机指针166。流程前进至判断步骤522。

在判断步骤522中，更新逻辑电路136判断上述分支指令是否为一非条件相对型式的分支指令。若是，流程前进至判断步骤524；若否，流程前进至判断步骤532。

在判断步骤524中，更新逻辑电路136检查虚拟随机指针166是否为真值。若是，流程前进至步骤526；若否，流程前进至步骤528。

在步骤526中，更新逻辑电路136使用新执行的分支指令的分支信息来更新分支目标地址快取128。流程结束于步骤526。

在步骤528中，更新逻辑电路136不使用新执行的分支指令的分支信息来更新分支目标地址快取128。流程结束于步骤528。

在判断步骤532中，更新逻辑电路136判断三个分支指令(即新执行的分支指令以及A项目302与B项目302中的两个分支指令)是否皆为条件相对分支指令。若是，流程前进至判断步骤534；若否，流程前进至步骤528。

在判断步骤534中，更新逻辑电路136判断指令解码器106或第二分支历史表126是否正确地预测新执行的分支指令。若是，流程前进至判断步骤524；若否，流程前进至步骤526。

本发明人观察到在部分快取线202中具有三个分支指令的情况下，程序有时会按顺序执行其指令而造成重复执行这三个分支指令的情形，因此有可能会替换分支目标地址快取128中的另一个分支指令。然而，大部分的时间只会执行这三个分支指令中的两个(或一个)分支指令，这将影响上述步骤502～516中以严格优先权为基础的替换策略的效能。举例而言，假设程序具有一外循环与一内循环，其中外循环包括一条件相对分支指令(例如第一x86JCC指令)，内循环包括一第二x86JCC指令与一非条件相对分支指令(例如x86JMP指令)，并且内循环跟随在x86JCC指令之后，x86JMP指令跟随在第二x86JCC指令之后。在此情况下，通常希望分支目标地址快取128的A 项目302与B项目302中包含内循环中的分支指令(第二x86JCC指令与x86JMP指令)，而不是包含外循环中的分支指令(第一x86JCC指令)。然而，由于x86JCC指令是高于x86JMP指令，因此根据以严格优先权为基础的替换策略，分支目标地址快取128中的A项目302与B项目302会包含两个x86JCC指令，并且更新逻辑电路136不会将这两个x86JCC指令中的任一者替换为x86JMP指令，这种结果是不理想的。

为了降低效能影响，虚拟随机产生器138提供虚拟随机指针166至更新逻辑电路136，相关细节请参考上述步骤518～528。值得注意的是，虚拟随机指针166随着微处理器100的时钟周期呈现规律性的变化，但由于大部分程序并不随着时钟周期规律地执行一给定的分支指令，因此虚拟随机指针166与分支指令的执行呈现随机性的变化。

因此，假设虚拟随机指标166大约每32个时钟周期平均为真值(true)一次，步骤518～528所实现的替换策略会使得更新逻辑电路136将外循环中的第一x86JCC指令替换为内循环的第32个执行实例(execution instance)中的x86JMP指令，并且内循环中的x86JMP指令会储存在分支目标地址快取128中，直到外循环中的第一x86JCC指令再次被执行。

此外，若在一给定的部分快取线202中具有三个x86JCC指令，更新逻辑电路136会检查指令解码器106或第二分支历史表126是否正确地预测x86JCC指令，若有正确地预测x86JCC指令，则根据步骤532、534以及528，更新逻辑电路136通常不会替换其它两个x86JCC指令中的一者。由于在本实施例中，第二分支历史表126的大小与所使用的算法复杂度皆小于分支目标地址快取128与第一分支历史表164，因此必须将难以预测(hard-to-predict)的x86JCC指令储存在方向预测最准确的分支目标地址快取128中。然而，为了避免上述类似情况(较常查见(see)三个x86JCC指令中的两者，并且很少执行三个x86JCC指令中的一者)，根据步骤532、534以及526，更新逻辑电路136会允许运作良好(well-behaved)的x86JCC指令(即内循环中被指令解码器106或第二分支历史表126所正确预测的x86JCC指令)继续执行(go ahead)，并且替换其它x86JCC指令中的一者(通常位于内循环的第32个执行实例(execution instance)中)。

本发明虽以各种实施例揭露如上，然其仅为范例参考而非用以限定本发明的范围，任何本领域技术人员，在不脱离本发明的精神和范围内，当可做 些许的更动与润饰。举例而言，可使用软件来实现本发明所述的装置与方法的功能、构造、模块化、模拟、描述及/或测试。此目的可通过使用一般程序语言(例如C、C++)、硬件描述语言(包括Verilog或VHDL硬件描述语言等等)、或其它可用的程序来实现。该软件可被设置在任何计算机可用的媒体，例如半导体、磁盘、光盘(例如CD-ROM、DVD-ROM等等)中。本发明实施例中所述的装置与方法可被包括在一半导体智慧财产权核心(semiconductorintellectual property core)，例如以硬件描述语言(HDL)实现的微处理器核心中，并被转换为硬件型态的集成电路产品。此外，本发明所描述的装置与方法可通过结合硬件与软件的方式来实现。因此，本发明不应该被本文中的任一实施例所限定，而当视所附的权利要求范围与其等效物所界定者为准。特别是，本发明是实现于一般用途计算机的微处理器装置中。最后，任何本领域技术人员，在不脱离本发明的精神和范围内，当可作些许更动与润饰，因此本发明的保护范围当视所附的权利要求范围所界定者为准。