8.2　简单运算器设计

在计算机发展的早期阶段，运算部件指的就是算术逻辑单元（Arithmetic Logic Unit，简称ALU）。ALU可以做算术运算、逻辑运算、比较运算和移位运算。后来功能部件不断发展扩充，可以执行乘法、除法、开方等运算。本节主要介绍定点补码加法器的设计。

加法是许多运算的基础。根据不同的性能和面积需求，加法器有很多种实现方式。进位处理是加法器的核心。根据进位处理方法的不同，常见的加法器包括：行波进位加法器（Ripple Carry Adder，简称RCA），先行进位加法器（Carry Look-ahead Adder，简称CLA），跳跃进位加法器（Carry Skip Adder，简称CSKA），进位选择加法器（Carry Select Adder，简称CSLA），进位递增加法器（Carry Increment Adder，简称CIA），等等。其中行波进位加法器最为简单直接，而先行进位加法器使用较为广泛。

8.2.1　定点补码加法器

1.一位全加器

一位全加器是构成加法器的基本单元。一位全加器实现两位本地二进制数以及低位的进位位相加，求得本地和以及向高位的进位。它有三个1位二进制数输入A、B和C_in，其中A和B分别为本地的加数和被加数，C_in为低位来的进位。它有两个1位二进制数输出S和C_out，其中S是本地和，C_out是向高位的进位。一位全加器的真值表如表8.4所示。

表8.4　一位全加器真值表

根据表8.4，可以写出全加器的逻辑表达式如下：

S=~A＆~B＆C_in|~A＆B＆~C_in|A＆~B＆~C_in|A＆B＆C_in

C_out=A＆B|A＆C_in|B＆C_in

上述表达式中，～表示取反操作，＆表示与操作，|表示或操作，其中～操作的优先级最高，＆操作次之，|操作优先级最低。上述表达式还可以简单解释为：当输入的三个数中有奇数个1时，本地和为1；当输入的三个数中有两个1时，向高位的进位为1。

根据上面的逻辑表达式，图8.17给出了用非门和与非门搭建的一位全加器的逻辑电路图及其示意图。如果我们不严格区分非门和与非门，以及不同数目输入与非门之间的延迟差异，则可近似认为每个一位全加器需要2或3级的门延迟。

图8.17　一位全加器逻辑电路图与示意图

接下来将介绍如何用一位全加器构建一个N（N＞1）位的带进位加法器。

2.行波进位加法器

构建N位带进位加法器的最简单的方法是将N个一位全加器逐个串接起来。图8.18给出了32位行波进位加法器的示意图。其中输入A=a₃₁…a₀和B=b₃₁…b₀分别是加数和被加数，C_in是最低位的进位；输出为和S=s₃₁…s₀以及最高位向上的进位C_out。所谓“行波”，是指每一级的一位全加器将来自低位的一位全加器的进位输出C_out作为本级的进位输入C_in，如波浪一般层层递进下去。这种串行的进位传递方式与人们日常演算十进制加法时采用的进位方式原理一样，非常直观。但是，这种加法器的电路中每一位的数据相加都必须等待低位的进位产生之后才能完成，即进位在各级之间是顺序传递的。回顾一下上文关于一位全加器的延迟的大致估算，可知一位全加器输入到S的最长延迟是3级门、输入到C_out的最长延迟是2级门。因此，32位行波进位加法器中，从最低位的输入A₀、B₀、C_in到最高位的进位输出C_out存在一条进位链，其总延迟为2×32=64级门；从最低位的输入A₀、B₀、C_in到最高位的进位输入C_in的延迟为2×31=62级门，所以从最低位的输入A₀、B₀、C_in到最高位的加和S₃₁的总延迟为62+3=65级门。从这个例子可以看出，虽然行波进位加法器直观简单，但是其延迟随着加法位数N的增加而线性增长，N越大时，行波进位加法器的延迟将越发显著。在CPU设计中，加法器的延迟是决定其主频的一个重要参数指标，如果加法器的延迟太长，则CPU的主频就会降低。例如，对于一个64位的高性能通用CPU来说，在良好的流水线切分下，每级流水的延迟应控制在20级门以内，所以64位行波进位加法器高达129级门的延迟太长了。

图8.18　32位行波进位加法器

3.先行进位加法器

为了改进行波进位加法器延迟随位数增加增长过快的缺点，人们提出了先行进位加法器的电路结构。其主要思想是先并行地计算每一位的进位，由于每一位的进位已经提前算出，这样计算每一个的结果只需要将本地和与进位相加即可。下面详细介绍先行进位（或者说并行进位）加法器的设计原理。

（1）并行进位逻辑

假设两个N位数A和B相加，A记作a_N-1a_N-2…a_ia_i-1…a₁a₀，B记作b_N-1b_N-2…b_ib_i-1…b₁b₀。定义第i位的进位输入为c_i，进位输出为c_i+1，且将加法器的输入C_in记作c₀以方便后面描述的统一。每一位进位输出c_i+1的计算为：

c_i+1=a_i＆b_i|a_i＆c_i|b_i＆c_i=a_i＆b_i|（a_i|b_i）＆c_i

设g_i=a_i＆b_i，p_i=a_i|b_i，则c_i+1的计算可以表达为：

c_i+1=g_i|p_i＆c_i

从上式可以看出，当g_i=1时，在c_i+1必定产生一个进位，与c_i无关；当p_i=1时，如果c_i有一个进位输入，则该进位可以被传播至c_i+1。我们称g_i为第i位的进位生成因子，p_i为第i位的进位传递因子。

下面以4位加法器的进位传递为例，根据公式c_i+1=g_i|p_i＆c_i逐级展开可得到：

c₁=g₀|p₀＆c₀

c₂=g₁|p₁＆g₀|p₁＆p₀＆c₀

c₃=g₂|p₂＆g₁|p₂＆p₁＆g₀|p₂＆p₁＆p₀＆c₀

c₄=g₃|p₃＆g₂|p₃＆p₂＆g₁|p₃＆p₂＆p₁＆g₀|p₃＆p₂＆p₁＆p₀＆c₀

扩展之后，每一位的进位输出c_i+1可以由仅使用本地信号生成的g和p直接得到，不用依赖前一位的进位输入c_i。图8.19给出了4位先行进位的逻辑电路图及其示意图。从图8.19中可以看出，采用先行进位逻辑，产生第4位的进位输出只需要2级门延迟，而之前介绍的行波进位逻辑则需要8级门延迟，先行进位逻辑的延迟显著地优于行波进位逻辑。当然，这里为了电路逻辑的简洁以及计算的简便，我们使用了四输入、五输入的与非门，这些与非门的延迟比行波进位逻辑中采用的二输入、三输入的与非门的延迟要长，但我们不再做进一步细致的区分，均视作相同延迟。而且实际实现时也很少采用五输入的与非门，其N管网络上串接五个NMOS管，电阻值较大，电路速度慢。

图8.19　块内并行的4位先行进位逻辑

（2）块内并行、块间串行逻辑

理论上可以把上述并行进位方法扩展成更多位的情况，但那需要很多输入的逻辑门，在实现上是不现实的。实现更多位的加法器时通常采用分块的进位方法，将加法器分为若干个相同位数的块，块内通过先行进位的方法计算进位，块间通过行波进位的方法传递进位。图8.20给出了16位加法器中采用该方式构建的进位逻辑。由于块内并行产生进位只需要2级门延迟，因此从p_i和g_i产生c₁₆最多只需要8级门延迟，而非行波进位逻辑的32级门延迟。

图8.20　块内并行、块间串行的16位先行进位加法器的进位逻辑

（3）块内并行、块间并行逻辑

为了进一步提升加法器的速度，可以在块间也采用先行进位的方法，即块内并行、块间也并行的进位实现方式。与前面类似，对于块内进位，定义其进位生成因子为g和进位传递因子为p，对于块间的进位传递，定义其进位生成因子为G和进位传递因子为P，则其表达式如下：

P=p₃＆p₂＆p₁＆p₀

G=g₃|p₃＆g₂|p₃＆p₂＆g₁|p₃＆p₂＆p₁＆g₀

上面的表达式可以解释为，当G为1时表示本块有进位输出生成，当P为1时表示当本块有进位输入时该进位可以传播至该块的进位输出。图8.21给出了包含块间进位生成因子和进位传递因子的4位先行进位的逻辑电路及其示意图。

图8.21　包含块间进位生成因子和进位传递因子的4位先行进位逻辑

定义上述的块间进位生成因子和进位传递因子是因为这种逻辑设计具有很好的层次扩展性，即以层次化的方式构建进位传递逻辑，把下一级的P和G输出作为上一级的p_i和g_i输入。图8.22给出了一个采用两层并行进位结构的16位先行进位逻辑，采用了5块4位先行进位逻辑。其计算步骤是：

图8.22　块内并行且块间并行的16位先行进位逻辑

1）下层的4块4位先行进位逻辑根据各块所对应的p_i和g_i生成各自的块间进位生成因子G和块间进位传递因子P；

2）上层的4位先行进位逻辑把下层的先行进位逻辑生成的P和G作为本层的p_i和g_i输入，生成块间的进位c₄、c₈和c₁₂；

3）下层的每块4位先行进位逻辑分别把c₀以及上层计算出的c₄、c₈和c₁₂作为各自块的进位输入c₀，再结合本地的p_i和g_i分别计算出本块内部所需要的每一位进位。

可以看出，从p_i和g_i生成下层各块的P、G需要2级门延迟，上层根据自身p_i和g_i输入生成进位输出c₁～c₃需要2级门延迟，下层各块从c₀输入至生成进位输出c₁～c₃也需要2级门延迟。所以整体来看，从p_i和g_i生成进位c₁～c₁₆最长的路径也只需要6级门延迟，这比前面介绍的块内并行但块间串行的电路结构更快。而且进一步分析可知，块间并行的电路结构中，最大的与非门的扇入为4，而前面分析块间串行电路结构延迟时，那个电路中最大的与非门的扇入为5。

这种块间并行的电路结构在设计更多位的加法器时，只需要进一步进行层次化级联就可以。例如，仍采用4位先行进位逻辑作为基本块，通过3层的树状级联就可以得到64位加法器的进位生成逻辑，其从p_i和g_i输入到所有进位输出的最长路径的延迟为10级门。感兴趣的读者可以自行推导一下其具体的结构和连接关系。

采用块内并行且块间并行的先行进位逻辑所构建的加法器，其延迟随着加法位数的增加以对数的方式增长，因而在高性能通用CPU设计中被广泛采用。

8.2.2　减法运算实现

在8.1.1节中我们提到，现代通用计算机中定点数都是用补码表示的。补码表示的一个显著优点就是补码的减法可以通过补码加法来实现，即补码运算具有如下性质：

［A］_补-［B］_补=［A-B］_补=［A］_补+［-B］_补

而［-B］_补可以通过将［B］_补“按位取反，末位加1”的法则进行计算。所以，只需要将被减数直接接到加法器的A输入，减数按位取反后接到加法器的B输入，同时将加法器的进位输入C_in置为1，就可以用加法器完成［A］_补-［B］_补的计算了，如图8.23所示。在此基础之上，可以将加法和减法统一到一套电路中予以实现，如图8.23所示，其中SUB作为加、减法的控制信号。当SUB信号为0时，表示进行加法运算；当SUB信号为1时，表示进行减法运算。

图8.23　利用加法器实现减法

8.2.3　比较运算实现

常见基本运算中除了加减法外还有比较运算。比较运算主要包含两种类型：一是判断两个数的相等情况，二是判断两个数的大小情况。

判断两个数相等所需要的逻辑电路比较简单，图8.24给出了一个4位相等比较的逻辑电路及其示意图。电路首先采用异或逻辑逐位比较输入A和B的对应位是否相同，所得到的结果中只要出现一个1则表示两者不相等，输出结果为0；否则结果为1。更多位数的相等比较的电路原理与所举的例子基本一致，只是在实现时判断异或结果中是否有1需要多级逻辑完成以降低逻辑门的扇入数目。

图8.24　4位相等比较器逻辑电路及其示意图

我们通过分析A-B的结果来比较A和B的大小。这里需要注意的是结果溢出的情况。如果减法操作没有发生溢出，则减法结果的符号位为1时表示A＜B；如果发生溢出，则结果符号位为0时才表示A＜B。假设A和B是两个64位的有符号数，A=a₆₃…a₀，B=b₆₃…b₀，A-B的结果为S=s₆₃…s₀，则A＜B成立的条件可以表示为：

Cond_A＜B=~Overflow＆s₆₃|Overflow＆~s₆₃

=a₆₃＆s₆₃|~b₆₃＆s₆₃|a₆₃＆~b₆₃

当然，最终的表示方式也可以直接得到，即A＜B成立的条件仅包括三种情况：①A是负数且B是非负数；②A是负数（且B也是负数）且结果是负数；③B是非负数（且A是非负数）且结果是负数。

由于能够通过减法来做大小的比较，且相等比较的逻辑资源并不多，所以在设计ALU时，比较操作的实现并不会新增很多逻辑资源消耗。

8.2.4　移位器

常见基本运算中除了加减、比较运算外，还有移位运算。移位运算不仅在进行位串处理时十分有用，而且常用于计算乘以或除以2的幂次方。移位运算通常有四种：逻辑左移、逻辑右移、算术右移和循环右移。其中左移、右移的概念如同其名字中的表述，是直观明了的。逻辑右移和算术右移的区别在于前者从高位移入的是0，后者从高位移入的是源操作数的符号位。算术右移之所以名字中使用“算术”这个词，是因为当用移位操作计算有符号数（补码表示）除以2的幂次方时，只有从高位移入符号位才能保证结果的正确。由此也可以知晓为什么没有定义“算术左移”这种移位操作。因为无论是有符号数还是无符号数，其乘以2的幂次方都只需要在低位移入0就可以了。循环右移操作，顾名思义，右移时从最低位移出去的比特位并不被丢弃，而是重新填入到结果的最高位。也正是因为这种循环移位的特点，循环左移操作其实可以用循环右移操作来实现，故不单独定义循环左移操作。例如：5位二进制数11001，其逻辑左移2位的结果是00100，逻辑右移2位的结果是00110，算术右移2位的结果是11110，循环右移2位的结果是01110。

N位数的移位器实现，实质上是N个N:1的多路选择器。图8.25中依次给出了4位数的逻辑左移、逻辑右移、算术右移和循环右移的逻辑电路示意图。其中A=a₃a₂a₁a₀是被移位数，shamt_1..0是移位量，Y=y₃y₂y₁y₀是移位结果。更多位数的移位器的实现原理与示例一致，只是选择器的规模更大。由于位数多时多路选择器消耗的电路资源较多，所以在实现时，可以将逻辑右移、算术右移和循环右移的电路糅合到一起，以尽可能复用多路选择器的资源。

图8.25　4位移位器逻辑