适用于微处理器中执行位扫描指令的硬件装置与方法

摘要

适用于微处理器中执行位扫描指令的硬件装置与方法。该硬件装置，用以执行指定包括了N个字节的输入运算元的位扫描指令，上述N至少为2。第一编码器针对输入运算元中的每个字节进行前行位扫描编码以产生N个第一位向量。零值检测器针对输入运算元中的每个字节进行零值检测以产生第二位向量。第二编码器针对第二位向量进行前行位扫描编码以产生第三位向量。第一N对1多工器由第三位向量控制以选择N个第一位向量中的一个为输出的第四位向量。其中第三位向量与第四位向量被连接成为第五位向量，第五位向量指示输入运算元中最低有效被设位的位索引值。

说明书

技术领域

本发明涉及微处理器的技术领域，尤其涉及在微处理器中执行位扫描指令的技术。

背景技术

x86指令集架构包括了前行位扫描(Bit Scan Forward，BSF)以及逆行位扫描(Bit Scan Reverse，BSR)指令，或通称为位扫描指令。在传统的微处理器中以微码实际操作上述位扫描指令，也就是说，当微处理器的指令转译器遇到(encounter)上述位扫描指令时，指令转译器会将控制权转移至存储于微码只读存储器中的微码例程(microcode rountine)，而微码例程却需要耗用许多时钟周期去执行位扫描指令。因此，亟需有一种较为快速的方式去执行位扫描指令。

发明内容

本发明的一实施例提供了一种适用于一微处理器中执行一位扫描指令的硬件装置，其中上述位扫描指令指定(specify)包括N个字节的一输入运算元，且上述N至少为2。该硬件装置包括了一第一编码器，用以针对上述输入运算元中的每个字节进行前行位扫描编码(forward bit scan encode)以产生N个第一位向量。该硬件装置还包括一零值检测器，用以针对上述输入运算元中的每个字节进行零值检测(zero-detect)以产生一第二位向量。该硬件装置还包括一第二编码器，用以针对上述第二位向量进行前行位扫描编码以产生一第三位向量。该硬件装置还包括一第一N对1多工器，由上述第三位向量控制以选择上述N个第一位向量中的一个为输出的一第四位向量。该硬件装置将上述第三位向量与上述第四位向量连接为一第五位向量，上述第五位向量指示(indicate)上述输入运算元中最低有效被设位(least significant set bit)的位索引值。在一实施例中，该硬件装置处理了前行与逆行位扫描指令。一第三编码器，用以针对上述输入运算元中的每个字节的一位逆向结果(bit-reversed version)进行前行位扫描编码以产生N个第六位向量。一第四编码器，用以针对上述第二位向量的一位逆向结果进行前行位扫描编码以产生一第七位向量。一第二N对1多工器，由上述第七位向量控制以选择上述N个第六位向量中的一个为输出的一第八位向量。一选择逻辑单元，用以接收指示上述位扫描指令为一前行或逆行位扫描指令的一输入，其中上述选择逻辑单元于上述输入指示上述位扫描指令为一前行位扫描指令时选择由上述第三位向量与上述第四位向量连接成为上述第五位向量，以及在上述输入指示上述位扫描指令为一逆行位扫描指令时选择由上述第七位向量与上述第八位向量连接成为上述第五位向量的一反相结果(inverted version)。

本发明的另一实施例提供了一种适用于一微处理器中执行一位扫描指令的方法，其中上述位扫描指令指定包括N个字节的一输入运算元，上述N至少为2，该方法包括了针对上述输入运算元中的每个字节进行前行位扫描编码以产生N个第一位向量。该方法还包括针对上述输入运算元中的每个字节进行零值检测以产生一第二位向量。该方法还包括用以针对上述第二位向量进行前行位扫描编码以产生一第三位向量。该方法还包括根据上述第三位向量选择上述N个第一位向量中的一个为输出的一第四位向量。该方法还包括将上述第三位向量与上述第四位向量连接为一第五位向量，其中上述第五位向量指示上述输入运算元中最低有效被设位的位索引值。

附图说明

图1根据本发明所述的微处理器的方块图。

图2A与图2B所示的细部方块图描述本发明图1中用以执行实际操作位扫描指令(前行/逆行位扫描指令)的微指令的执行单元。

图3根据本发明另一实施例所述如图1中用以执行实际操作位扫描指令(前行/逆行位扫描指令)的第二微指令的执行单元细部方块图。

【主要元件符号说明】

100～微处理器；

102～指令快取；

104～指令转译器；

106～寄存器别名表；

108～微指令；

112～保留站；

114～执行单元；

118～重排缓冲器；

122～通用寄存器集合；

202～来源运算元；

204～运算元大小；

206～零值遮罩逻辑单元；

208、222、225、272、274、276、299、333、325～结果；

212、216、218、252、256、262、264、266～逻辑单元；

211、213、215～3位数值；

214、258～位逆向结果；

217、222、224、223、233、242～输出；

221、231、238、321、331～2对1多工器；

226、228～8对1多工器；

227、327、347～反相器；

229、337、349～反相结果；

232、234、329～输入；

235～补零位；

236、336～控制输入；

282～A寄存器；

284～B寄存器；

286～C寄存器；

288～D寄存器。

具体实施方式

本发明的实施例所述的微处理器以硬件、而非以传统的微码方式执行位扫描指令，从而有效地降低执行每个位扫描指令时所需耗用的时钟周期数。

图1根据本发明一实施例所述的微处理器的方块图。在此实施例中，微处理器100为一非循序(out-of-order)执行微处理器，包括了指令快取102以存储包括位扫描指令在内的程序指令。微处理器100包括指令转译器104以将宏指令转译为多个微指令108，例如实际操作位扫描指令的微指令。在一实施例中，指令转译器104会响应遇到一位扫描指令而产生两个微指令108，且每个微指令108的执行在各自的执行单元114中耗用一个时钟周期。然而，在另一实施例中，指令转译器104会响应遇到一位扫描指令而产生单一微指令108，特别是微处理器100的时钟周期时间能允许如图2A与第2B或图3所示的逻辑电路(将于后续段落进一步说明)在单一时钟周期内产生一结果。在一实施例中，指令转译器104为响应解码一位扫描指令，而用以将上述位扫描指令直接转译为一或多个微指令，而非将上述位扫描指令储放至(trapping to)一微码存储器。

寄存器别名表(Register Alias Table，RAT)106产生微指令108的相依性，特别是在指令转译器104会响应遇到一位扫描指令而产生两个微指令108的实施例中，寄存器别名表106会根据第一微指令的结果产生第二微指令的相依性，寄存器别名表106将微指令108发送(dispatch)至保留站112，而当微指令108准备好要执行时，意即当其相依性被满足且有一执行单元114可用时，保留站112再将微指令108送到(issue)各自的执行单元114。

特别是，一执行单元114的存在为了执行由指令转译器104所产生的微指令108以实际操作位扫描指令。执行单元114亦自一通用寄存器集合接收运算元。尤其是一位扫描指令的来源运算元是来自于通用寄存器集合122，且该位扫描指令的结果会被写回到通用寄存器集合122。重排缓冲器(ReOrder Buffer，ROB)118能够确保微指令108及其相关微指令的引退(retirement)。

位扫描指令可指定六种基本运算，这是因为位扫描指令能指定16位、32位、或64位的来源运算元，且再根据每种来源运算元指定一前行位扫描以找出最低有效被设位(二进制值「1」)，或根据每种来源运算元指定一逆行位扫描以找出最高有效被设位。一般而言，通过将来源运算元的相关较高位遮罩掉、在适当时机使产生的8字节的位顺序逆向(reverse)、针对该字节的每个位执行前行位扫描与零值检测运算、以及将结果适时地反相等步骤(将于后续段落进一步说明)，用以执行位扫描指令的一或多个执行单元114就能将上述的六种基本运算减少至单一个64位的前行扫描运算。

图2所示的细部方块图系描述本发明图1中用以执行实际操作位扫描指令(前行/逆行位扫描指令)的微指令108的执行单元114。图2由图2A与图2B所组成。根据此实施例，图2A所描述的部分是执行单元114中用以执行实际操作位扫描指令的第一微指令108，而图2B所描述的部分是执行单元114中用以执行实际操作位扫描指令的第二微指令108。

图2A中的执行单元114包括位扫描指令的一来源运算元202。位扫描指令可指定来源运算元大小204为16位、32位、或64位，且不论来源运算元202的大小为何，执行单元114都接收由位扫描指令所指定的64位来源寄存器中的全部8字节。(在位扫描指令指定来自存储器的一来源运算元的情况下，指令转译器104产生一载入微指令以自存储器载入来源运算元202，而第一微指令相依于该载入运算)来源运算元202中的最低有效字节以「字节0」标示，其次为「字节1」，以此类推至最高有效字节，标示为「字节7」。

零值遮罩逻辑单元206接收字节2至7，且于位扫描指令指定一16位的来源运算元202时，将字节2至7全部遮罩为零，以及在位扫描指令指定一32位的来源运算元202，将字节4至7全部遮罩为零，而在位扫描指令指定一64位的来源运算元202时，不执行任何动作。零值遮罩逻辑单元206的输出再与字节0与字节1连接成为一8字节的结果208。

逻辑单元212使结果208的每个字节中的位逆向(reverse)以产生一个8字节的位逆向结果214，也就是说，在每个字节中，位0被移至位7的位置、位1被移至位6的位置、位2被移至位5的位置、位3被移至位4的位置、位4被移至位3的位置、位5被移至位2的位置、位6被移至位1的位置、位7被移至位0的位置。

逻辑单元216接收位逆向结果214并针对每个字节执行一前行位扫描编码运算(forward bit scan encode operation)以产生八个3位结果222，每个3位结果222为一无符号(unsigned)整数值，指定位逆向结果214中对应的最低有效被设位(二进制值「1」)的位索引值(bit index)。在一实施例中，逻辑单元216为一编码器(encoder)(第三编码器)。

逻辑单元218接收结果208并针对每个字节执行一前行位扫描编码运算以产生八个3位结果224，每个3位结果224为一无符号整数值，指定结果208中对应的最低有效被设位(二进制值「1」)的位索引值。在一实施例中，逻辑单元218为一编码器(第一编码器)。

第一个8对1多工器226由其八个输入接收八个3位结果222，并根据一控制输入272选择八个3位结果222之一作为单一的3位输出232。第二个8对1多工器228由其八个输入接收八个3位结果224，并根据一控制输入274选择八个3位结果224之一作为单一的3位输出234。2对1多工器238由其两个输入接收8对1多工器226与228的输出232与234，并选择输出232与234中的一个作为单一的3位输出242。如果控制输入236指示该位扫描指令为一逆行位扫描指令，则2对1多工器238选择输出232(意即选择了前行位扫描编码的位逆向结果)；反之，如果控制输入236指示该位扫描指令为一前行位扫描指令，则2对1多工器238选择输出234(意即选择了前行位扫描编码的非位逆向结果)。2对1多工器238的输出242存储于A寄存器282以供第二微指令之用。

逻辑单元252针对结果208的每个字节执行一零值检测运算以产生8位的结果254，如果结果254的位的对应字节208为零时，则结果254中对应位的值为伪(false)。在一实施例中，逻辑单元252为一零值检测器(zero detector)。

逻辑单元256使结果254的位逆向以产生一8位的逆向结果258。

逻辑单元262接收上述位逆向的结果258并执行一前行位扫描编码运算以产生一3位的结果272，结果272即为8对1多工器226的控制输入。在一实施例中，逻辑单262为一编码器(第四编码器)。

3位的结果272为一无符号整数值，用以指定位逆向的结果258中最低有效位(二进制值「1」)的位索引值。逻辑单元262的输出272存储于B寄存器274中以供第二微指令之用。

逻辑单元264接收结果254并执行一前行位扫描编码运算以产生一3位的结果274，结果274即为8对1多工器228的控制输入。编码后的3位结果274为一无符号整数值，用以指定结果254中最低有效位(二进制值「1」)的位索引值。逻辑单元264的输出274存储于C寄存器286中以供第二微指令之用。在一实施例中，逻辑单元264为一编码器(第二编码器)。

逻辑单元266针对结果254执行一零值检测运算以产生一1位的结果276，结果276于结果254为零时(也就是当被遮罩的结果208为零时)则值为伪。逻辑单元266的结果276存储于D寄存器288中以供第二微指令之用。

图2B所示的细部方块图描述本发明用以执行实际操作位扫描指令(前行/逆行位扫描指令)的第二微指令108的执行单元114。

图2B中的执行单元114包括了图2A中用以存储第一微指令的结果的A寄存器282、B寄存器284、C寄存器286、以及D寄存器288。

2对1多工器221从两输入端口接受来自B寄存器284的3位数值211与来自C寄存器286的3位数值213，并且根据图2A中所示的控制输入236选择上述两者其中之一作为单一的3位输出223。多工器221于控制输入236指示该位扫描指令为一逆行位扫描指令时选择输入211；相反地，多工器221于控制输入236指示该位扫描指令为一前行位扫描指令时选择输入213。输出223的三个位与A寄存器282的输出215连接(concatenate)在一起而组成一6位的结果225，其中结果225的第4到6位(Bits[5:3])为输出223，而结果225的第1到3位(Bits[2:0])为A寄存器282的输出215。

反相器227接收6位的结果225并产生一反相的结果229。2对1多工器231从两输入端口接受6位的结果225与反相的结果229，并且根据图2A所示的控制输入236选择上述两者其中之一作为单一的6位输出233。2对1多工器231于控制输入236指示上述位扫描指令为一逆行位扫描指令时选择输出229；相反地，多工器231于控制输入236指示上述位扫描指令为一前行位扫描指令时选择输出225。

输出233的6个位再与补零位(zero padding bits，“0”bits)235连接而组成大小等同输入来源(8位、16位、32位)的一结果299，结果299的第1到6位(Bits[5:0])为输出233，而结果299的其余的位则为补零位235。

D寄存器288的输出217被提供至图1所示的重排缓冲器118，重排缓冲器118于D寄存器288的输出217指示该位扫描指令的来源运算元不为零时，将结果299写入由该位扫描指令所指定的目的寄存器。

虽然附图中的A寄存器282、B寄存器284、C寄存器286、以及D寄存器288为各自分离的寄存器，但在一实施例中，第一微指令的10位结果(包括输出242、272、274、276)可存储于一单一寄存器。需注意的是，上述成果虽然是通过图2所示逻辑单元去实现，但在其它实施例中，也可使用不同逻辑单元去实现相同成果。举例来说，如图3所示的实施例则使用了不同逻辑单元而实现了与第2B的实施例相同的成果。

图3根据本发明另一实施例所述如图1中用以执行实际操作位扫描指令(前行/逆行位扫描指令)的第二微指令108的执行单元114细部方块图。图3与图2B的实施例中系使用相同的元件编号来表示类似的设计部分。

反相器327接收B寄存器284的3位输出211并且产生3位的反相结果337。

2对1多工器321从两个输入端口从反相器327与C寄存器286各自接收反相后的3位结果337与3位的数值213，并且根据控制输入336选择上述两者的其中之一作为单一的3位输出323。多工器321于控制输入336指示该位扫描指令为一前行位扫描指令时选择输入337；反之，多工器321于控制输入336指示该位扫描指令为一逆行位扫描指令时选择输入213。

反相器347接收A寄存器282的3位输出215并且产生3位的反相输出349。

由三个2输入异或门331所组成的集合(set)针对3位的反相输出349与3位输入329中的对应位执行一布尔异或(Boolean XOR)运算。3位输入329由复制控制输入336三次而得到，异或门331的3位输出为一3位结果333。在一实施例中，当位扫描指令为一前行位扫描时，3位输入329的值全为布尔1，而于位扫描指令为一逆行位扫描时，3位输入329的值全为布尔0。因此，如果位扫描指令为一前行位扫描指令，则结果333为A寄存器282的输出215的反相(inverted version)；反之，则结果333为A寄存器282的输出215。

2对1多工器321的输出323的三个位与异或门331的输出333连接而组成6位结果325。其中，6位结果325中的第4到6位(Bits[5:3])为输出323，而第1到3位(Bits[2:0])为异或门331的输出333。结果325的六个位与补零位235连接而组成结果299，结果299中的第1到6位(Bits[5:0])为输出325，而结果299中的其余位则为补零位235。

本发明虽以各种实施例公开如上，然而其仅为范例参考而非用以限定本发明的范围，本领域技术人员在不脱离本发明的精神和范围内，当可做些许的更动与润饰。举例来说，软件可实现相关于本发明的装置与方法的功能、制造、建模(modeling)、仿真(simulation)、描述(description)、和/或测试等等。该软件可使用一般程序设计语言(如：C、C++)、硬件描述语言(Hardware Description Language，HDL)(如：Verilog HDL、VHDL等等)、或其它可得的程序来实际操作。且该软件可配置于任何公知的计算机可使用介质中，例如：半导体、磁盘、或光盘(如只读存储器光盘(Compact Disc Read-Only Memory，CD-ROM)、数字多功能光盘(Digital Versatile Disc Read-Only Memory，DVD-ROM)等等)。本发明所述的装置与方法的实施例可包括于一半导体知识产权内核(semiconductor intellectual property core)中，例如：微处理器内核(如：嵌入于硬件描述语言中)，再进一步转换为硬件的集成电路产品。另外，本发明所述的装置与方法可以硬件与软件的一组合方式嵌入。因此，上述实施例并非用以限定本发明的范围，本发明的保护范围当视所附权利要求书所界定者为准。特别是，本发明可实际操作于一微处理器装置，且该微处理器装置可使用于一般用途的计算机。最后，本领域技术人员应当可理解在不脱离本发明的精神和范围内，以上述所公开的实施例与概念设计出与本发明相同目的的其它架构。