算术逻辑单元ALU

算术逻辑单元（ALU）

在前面我们讲过计算机五大组件之一的运算器，其中，他的组成如下：

其中这个ALU就是运算器的核心元件，算术逻辑单元，它主要的功能是：

1. 算术运算：加、减、乘、除等
2. 逻辑运算：与、或、非、异或等
3. 辅助功能：移位、求补等

他的工作流程如下：

就是传入两个或者多个操作数，然后通过运算指令译码产生的信号进行算数逻辑运算，然后输出运算结果，这里的具体工作原理和结构组成，我们以经典的4位ALU芯片（74181）为例进行学习。74181的结构如下：

74181能执行16种逻辑运算和16中算术运算，可工作于正/负逻辑操作方式下，所以刚好可以用电流的两种状态代表两种运算状态，所以这里的M位是用来区分进行的是逻辑运算还是算术运算的，M=0表示算术运算，M=1表示逻辑运算。其中剩余的S0~S3是表示具体的算术运算或者逻辑运算的位，比如在M=1,S3~S0-1001时，是在做逻辑运算A⊕B。

74181是4位并行加法器（并行就是同时进行，OS中有细讲），其4位进行位也是同时产生的，所以如果我们使用4片74181芯片可以组成一个16位的ALU。但是如果是串接，那么虽然片内进位是快速的，但是片间进位却仍然是逐片传递的，即组内并行，但是组间串行，因此总的形成时间还是很慢，其具体放的演示如下：

那么我们肯定是要优化合作组成的结构来加快运算速度。

我们可以把16位ALU的每4位作为一组，即将74181和74182芯片（先行进位芯片）配合，用类似位间快速进位的方法来实现16位ALU（4片ALU组成），则能得到16位的两级先行进位ALU，即组内并行，组件并行。如下：

其实说白了就是每一个4位ALU看成是一位，这样4个组间进位就可以看成是74182的4个位间进位了。也就是形成了一个两级进位，这样就实现了组内并行，组间并行的进位ALU了。和74181类似的片位式芯片的还有Am2901,这个芯片也是4位并行加法器，可以和先行进位芯片Am2902配合，而此芯片还有16个16位寄存器，因此也称为是片位式运算器。

数字电路基础知识

我们在讲解具体如何通过电路来实现算术逻辑运算之前，先来学习一下数字电路的基础知识。

基本逻辑

在电路逻辑表示中，我们通常将断电称为0，通电称为1，即：

首先我们来学习以下基本的逻辑运算符号：

与运算

其逻辑表达式如下

$$Y是A与B的结果：Y=A·B$$

他的电路表示为：

我们在物理电路中学过，此时是串联电路，如果想要Y通电（即真值为1），那么A,B必须都通电（即A，B真值都为1）才可以，所以真值表为：

他的电路符号是：

或运算

其逻辑表达式如下：

$$Y是A或B的结果：Y=A+B$$

他的电路表示为：

此时要想Y通电，只要满足至少A,B有一个通电（至少A,B有一个真值为1）即可。所以真值表如下：

他的电路符号是：

非运算

其逻辑表达式为：

$$Y是非A的结果：Y=\overline{A}$$

他的电路表示为：

所以当A为断点（即A真值为0）时，Y通电，所以真值表如下：

他的电路符号是：

复合逻辑

上面就是借用电路的串联，并联，短路三种形式实现的简单的逻辑运算，当然是用复合电路我们也可以实现复杂的复合逻辑运算如下：

与非运算

其逻辑表达式为：

$$Y是A与非B的结果：Y=\overline{A·B}=\overline{A}+\overline{B}$$

他的电路不好直接通过复合拼接表示，一般借用了半导体，所以就不给出电路图了。我们来看一下真值表：

电路符号是：

或非运算

其逻辑表达式为：

$$Y是A或非B的结果：Y=\overline{A+B}=\overline{A}·\overline{B}$$

其真值表如下：

电路符号是：

异或运算

其逻辑表达式为：

$$Y是A异或B的结果：Y=A⊕B$$

其真值表为：

他的电路符号是：

对于异或运算，我们不太好记忆规律，可以通过下图记忆：

所以只有0和1时异或才能使得低位为1，也就是相同为0，不同为1。

同或运算

这里我们再来了解一个很特殊的逻辑运算同或运算，其逻辑表达式如下：

$$Y是A同或B的结果：Y=A⊙B$$

他的真值表如下：

实际上我们看完真值表，发现只不过是和异或相反了，现在是相同取1，不同取0了， 所以结果总是异或的非。

电路符号：

加法器

我们回忆一下前面讲的运算器中的算术逻辑单元ALU并联系之前所学的各种算术逻辑运算的实现原理，我们很容易就可以知道所有的运算实际上最终都可以转换成加法。所以可以见到ALU中最重要的部件就是加法器，所以ALU才会出现复杂的进位问题，那么接下来我们就详细学习一下几种加法器。

一位全加器

一位全加器（FA）顾名思义模拟的就是一个位的加法，所以会涉及到两个问题：

1. 本位最终是填写0还是填写1
2. 向自己的高位是进位1还是进位0（即不进位）

而能决定这两个问题就是两个操作数的位以及自己的低位产生的进位，所以输入有三个值，而输出有两个值分别是（假设我们现在讨论第i位的加法）

$$\begin{cases} A_i:操作数A的第i位数值\\ B_i:操作数B的第i位数值\\ C_{i-1}:A_{i-1}和B_{i-1}相加产生的向结果i位进位数值\\ C_i:A_i和B_i相加产生的向结果i+1位进位的数值\\ S_i:答案的第i位数值 \end{cases}$$

所以我们需要给出根据上面3个输入来计算出下面两个输出的方法：

这里我们首先给出Si（又称为本位和）的逻辑表达式为：

$$S_i=A_i⊕B_i⊕C_i$$

根据上面表达式我们很轻松就可以推断出有以下结论：当这三个位有奇数个1时，本位和数值就是1，否则就是0，这和二进制加法的规律相同。所以我们知道对于一位加法，是使用异或运算来模拟的。

思考：为什么公加法式如上，异或运算为什么可以来模拟本位加法？

你可能会有点小疑惑上面是如何模拟的，所以就有了这个解答，一定要透彻理解。我们以一个例子来讲解：

我们发现对于上面的公式就是模拟的上图的这三种情况的运算，其中三个输入一目了然，他们很显然一同决定了本位和与进位数值，那么确实当三个输入有奇数个1时就是本位和为1，否则为0。并且使用异或运算就刚好符合加法的规律。

接下来我们再给出进位的逻辑表达式：

$$C_i=A_i·B_i+(A_i⊕B_i)·C_i$$

好家伙，可是够复杂，别慌我们先解读一下这个式子。很显然Ci若要为1，可以有以下几种情况：

$$\begin{cases} 情况1：A_i与B_i都是1\\ 情况2：A_i和B_i的有一个为1同时C_i也是1 \end{cases}$$

我们思考一下这两种情况只要有一种情况出现那么Ci就会为1，而他刚好也是符合加法运算的规律的，我们看一下下图就是两个情况演示：

我们发现情况1Ci-1实际上已经不决定是否产生进位1了，因为Ai和Bi之和就已经决定了必须产生进位了，此时Ci-1只是决定本位和是1还是0了。而对于情况2Ci-1为1才使得决定了最终第i位要想第i+1高位产生进位1。

所以上面两个公式完美模拟实现了一位的加法，所以这就是一位全加器的功能原理，那么我们就可以给出他的电路逻辑结构了：

串行加法器

在串行加法器中，只有一个全加器，所以一次只能够进行一个位的加法运算，因此若操作数长n位，那么加法就要分n次进行，每次产生一个位的和，并且串行逐位的送回寄存器。进位触发器用来存储进位信号，以便参与下一次的运算。因为只需要一个一位全加器即可，所以串行加法器具有器件少，成本低的优点，但是运算速度缓慢，常用于某些低速的专用计算器。

并行加法器

很显然，并行加法器就是解决串行加法器计算过慢问题的。并行加法器一般是由多个一位全加器组成，其位数和机器的字长相同，各个位数据同时运算。并行计算器可同时对数据的各位相加，但是存在一个加法的最长运算时间问题，我们思考一下原因，虽然操作数的各位是提供的，但是我们知道对于一个位的计算除了需要两个操作数以外，还需要一个从低位传进来的进位信号，其数值也会影响本位和以及向高位的进位输出。因此并行加法器的最长运算时间主要是由进位信号的传递时间决定的，计算时间远远要短于进位信号的传递时间。因此提高并行加法器速度的关键就是尽量要加快进位的产生和传递的速度。并行加法器的产生个传递如下：

并行加法器中的每个全加器都有一个从低位送进来的进位输入和一个传送给高位的进位输出。通常将传递进位信号的逻辑线路连接起来构成的进位网络称为进位链。进位表达式如下：

$$C_i=G_i+P_iC_{i-1}(G_i=1或者P_iC_{i-1}=1时，C_i=1)$$

并且有

$$\begin{cases}G_i=A_iB_i:进位产生函数\\P_i=A_i⊕B_i：进位传递函数\end{cases}$$

我们分析一下上面的式子，发现这就是一位全加器进位表达式，只不过换了一下形式而已。因为Ai和Bi都为1时，就已经可以肯定会向高位产生一个进位信号1了，所以Gi被称为进位产生函数，而PiCi-1均为1时，就要求低位向本位传递的进位信号为1时才可以使本位向高位传递一个进位信号1，所以Pi被称为进位传递函数。那么并行加法器的进位通常可以分为以下两种：

串行进位

很好理解，就是将n各一位全加器串接起来，就可以进行两个n位数的相加，这种加法器称为串行进位的并行加法器。如下图：

那么每级进位直接依赖于前一级的进位，即进位信号时逐级形成的。那么就有以下推导：

$$C_1=A_1B_1+(A_1⊕B_1)C_0$$

$$C_2=A_2B_2+(A_2⊕B_2)C_1$$

$$...$$

$$C_n=A_nB_n+(A_n⊕B_n)C_n-1$$

所以，低位运算产生的进位所需要的时间会影响至最高位运算的时间，所以并行加法器的最长运算时间主要是由进位信号的传递时间决定的，位数越多延迟时间越长，而全加器本身的求和延迟是次要因素，所以加快进位信号产生和传递的速度是关键。

并行进位

我们思考一下串行进位信号产生和传递速度慢的原因，主要是因为第i位的进位信号是Ci-1，所以需要等待Ci-1完成才可以进行，所以导致了延迟时间积累到了高位。而并行进位尝试解决了这一困局，并行进位又称为先行进位，同时进位，其特点是各级进位信号同时产生，而不再是像串行进位那样需要逐级等待了。所以采用并行进位的方案可以进一步提高进位产生和传递的速度，即将各级低位产生的本级G和P信号一次同时传递到高位，那么并行进位是如何做到的呢？我们将上面的式子进行拆解：

$$C_1=G_1+P_1C_0$$

$$C_2=G_2+P_2C_1=G_2+P_2G_1+P_2P_1C_0$$

$$C_3=G_3+P_3C_2=G_3+P_3G_2+P_3P_2G_1+P_3P_2P_1C_0$$

我们不难发现，实际上所有进位信号Ci都可以拆分成C0的多项式，所以所有位的进位输出信号实际上仅有Gi,Pi,C0决定，而不依赖于其低位的进位输入Ci-1，因此各个进位可以并行同时产生和传递。

这种进位方式很显然很快速，与字长无关，但是局限性是随着加法器位数的增加，Ci的逻辑表达式会变得越来越长，输入变量会越来越多，使得计算电路泰国复杂。所以采用并行进位不现实。所以我们还需要改进，这里又有两种改进方法：

单级先行进位方式

即我们退求其次，不要求全部并行进位了，以16位为例。我们不再尝试16位同时进位的纯并行进位方式，而是先将16位划分成4个组，每一个组是一个4位加法器，这一组内是并行进位同时产生进位，而这4个组之间使用的是串行进位，这样，就不会导致高位的计算逻辑过于复杂，同时也保证了计算性能的优化，其结构图如下：

注意这个图和上面的纯串行进位的并行加法器是有区别的，这里的每一个加法器不再是一位全加器FA，而是4位CLA加法器。此时是组内并行，组间串行。我们从低位到高位将4个组编号成1~4，那么对于1号CLA，根据C0同时产生C3,C2,C1然后计算输出C4,2号CLA会根据C4同时并行产生C7,C6,C5，然后计算输出C8，以此类推。

多级先行进位方式

我们还是将其16位分成4个组，每个组是4位CLA加法器，但是此时我们将这四个4位加法器不串接，而是再次使用并行进位的方式连接，这样就形成了两级并行进位的计算方式。如下图：

此时是组内并行，组间也并行。我们从低位到高位将4个组编号成1~4，那么1号CLA的进位输出C4可以改写成

$$C_4=G_4+P_4G_3+P_4P_3G_2+P_4P_3P_2G_1+P_4P_3P_2P_1C_0=G_1^*+P_1^*C_0$$

其中

$$G_i^*是组内进位产生函数,P_i^*是组进位传递函数$$

这两个函数至于Pi,Gi有关，而与进位信号C无直接联系。所以以此类推我们可以推出：

$$C_8=G_2^*+P_2^*C_4=G_2^*+P_2^*G_1^*+P_2^*P_1^*C_0$$

$$C_{12}=G_3^*+P_3^*C_8=G_3^*+P_3^*G_2^*+P_3P_2^*G_1^*+P_3^*P_2^*P_1^*C_0$$

以此类推，但是这种方法需要对CLA进行改进，此时4个4位加法器都不再计算C4,C8,C12了。

1. 第一组内根据C0同时产生G1*,P1*,C3,C2,C1,不产生C4。
2. 第二组内根据C4同时产生G2*,P2*,C7,C6,C5,不产生C8。
3. 第三组内根据C8同时产生G3*,P3*,C11,C10,C9,不产生C12。
4. 第四组内根据C12同时产生G4*,P14*,C15,C14,C13,不产生C16。

那么各组所需要的的C0,C4,C8,C12怎么得来呢？因为他们不能从低位获得进位信号，此时我们就引入了CLA电路，即上面最长的那个，而4位的加法器改名为了BCLA。那么此时CLA可以根据BCLA提供的不同的Gi*,Pi*以及上面推出的公式，用C0并行同时计算出来个BCLA所需要的C4,C8,C12，所以两个并行加法同时进行的，就很强。

思考：两个不同优化改进方式的异同点？

单级先行进位改进方法是牺牲了部分计算速度，但是大大降低了计算逻辑，同时造价也简单。而多级先行进位改进方法没有牺牲计算速度，但是需要加入一个辅助电路CLA来帮助计算复杂的逻辑运算，造价较高。

思考：算术逻辑单元的计算方式

我们学完了计算方式再来思考一下之前讲到的算术逻辑单元的计算方式，我们不难看出实际上算术逻辑单元采用的就是这两种改进版的并行进位计算方法，而都没有使用串行进位计算方法。

总结