极客时间已完结课程限时免费阅读

14 | 乘法器：如何像搭乐高一样搭电路（下）？

14 | 乘法器：如何像搭乐高一样搭电路（下）？-极客时间

14 | 乘法器：如何像搭乐高一样搭电路（下）？

2019-05-27 徐文浩 来自北京
《深入浅出计算机组成原理》
课程介绍

讲述：徐文浩

时长12:51大小11.75M

和学习小学数学一样，学完了加法之后，我们自然而然就要来学习乘法。既然是退回到小学，我们就把问题搞得简单一点，先来看两个 4 位数的乘法。这里的 4 位数，当然还是一个二进制数。我们是人类而不是电路，自然还是用列竖式的方式来进行计算。
十进制中的 13 乘以 9，计算的结果应该是 117。我们通过转换成二进制，然后列竖式的办法，来看看整个计算的过程是怎样的。

顺序乘法的实现过程

从列出竖式的过程中，你会发现，二进制的乘法有个很大的优点，就是这个过程你不需要背九九乘法口诀表了。因为单个位置上，乘数只能是 0 或者 1，所以实际的乘法，就退化成了位移和加法。
在 13×9 这个例子里面，被乘数 13 表示成二进制是 1101，乘数 9 在二进制里面是 1001。最右边的个位是 1，所以个位乘以被乘数，就是把被乘数 1101 复制下来。因为二位和四位都是 0，所以乘以被乘数都是 0，那么保留下来的都是 0000。乘数的八位是 1，我们仍然需要把被乘数 1101 复制下来。不过这里和个位位置的单纯复制有一点小小的差别，那就是要把复制好的结果向左侧移三位，然后把四位单独进行乘法加位移的结果，再加起来，我们就得到了最终的计算结果。
对应到我们之前讲的数字电路和 ALU，你可以看到，最后一步的加法，我们可以用上一讲的加法器来实现。乘法因为只有“0”和“1”两种情况，所以可以做成输入输出都是 4 个开关，中间用 1 个开关，同时来控制这 8 个开关的方式，这就实现了二进制下的单位的乘法。
我们可以用一个开关来决定，下面的输出是完全复制输入，还是将输出全部设置为 0
至于位移也不麻烦，我们只要不是直接连线，把正对着的开关之间进行接通，而是斜着错开位置去接就好了。如果要左移一位，就错开一位接线；如果要左移两位，就错开两位接线。
把对应的线路错位连接，就可以起到位移的作用
这样，你会发现，我们并不需要引入任何新的、更复杂的电路，仍然用最基础的电路，只要用不同的接线方式，就能够实现一个“列竖式”的乘法。而且，因为二进制下，只有 0 和 1，也就是开关的开和闭这两种情况，所以我们的计算机也不需要去“背诵”九九乘法口诀表，不需要单独实现一个更复杂的电路，就能够实现乘法。
为了节约一点开关，也就是晶体管的数量。实际上，像 13×9 这样两个四位数的乘法，我们不需要把四次单位乘法的结果，用四组独立的开关单独都记录下来，然后再把这四个数加起来。因为这样做，需要很多组开关，如果我们计算一个 32 位的整数乘法，就要 32 组开关，太浪费晶体管了。如果我们顺序地来计算，只需要一组开关就好了。
我们先拿乘数最右侧的个位乘以被乘数，然后把结果写入用来存放计算结果的开关里面，然后，把被乘数左移一位，把乘数右移一位，仍然用乘数去乘以被乘数，然后把结果加到刚才的结果上。反复重复这一步骤，直到不能再左移和右移位置。这样，乘数和被乘数就像两列相向而驶的列车，仅仅需要简单的加法器、一个可以左移一位的电路和一个右移一位的电路，就能完成整个乘法。
乘法器硬件结构示意图
你看这里画的乘法器硬件结构示意图。这里的控制测试，其实就是通过一个时钟信号，来控制左移、右移以及重新计算乘法和加法的时机。我们还是以计算 13×9，也就是二进制的 1101×1001 来具体看。
这个计算方式虽然节约电路了，但是也有一个很大的缺点，那就是慢。
你应该很容易就能发现，在这个乘法器的实现过程里，我们其实就是把乘法展开，变成了“加法 + 位移”来实现。我们用的是 4 位数，所以要进行 4 组“位移 + 加法”的操作。而且这 4 组操作还不能同时进行。因为下一组的加法要依赖上一组的加法后的计算结果，下一组的位移也要依赖上一组的位移的结果。这样，整个算法是“顺序”的，每一组加法或者位移的运算都需要一定的时间。
所以，最终这个乘法的计算速度，其实和我们要计算的数的位数有关。比如，这里的 4 位，就需要 4 次加法。而我们的现代 CPU 常常要用 32 位或者是 64 位来表示整数，那么对应就需要 32 次或者 64 次加法。比起 4 位数，要多花上 8 倍乃至 16 倍的时间。
换个我们在算法和数据结构中的术语来说就是，这样的一个顺序乘法器硬件进行计算的时间复杂度是 O(N)。这里的 N，就是乘法的数里面的位数。

并行加速方法

那么，我们有没有办法，把时间复杂度上降下来呢？研究数据结构和算法的时候，我们总是希望能够把 O(N) 的时间复杂度，降低到 O(logN)。办法还真的有。和软件开发里面改算法一样，在涉及 CPU 和电路的时候，我们可以改电路。
32 位数虽然是 32 次加法，但是我们可以让很多加法同时进行。回到这一讲开始，我们把位移和乘法的计算结果加到中间结果里的方法，32 位整数的乘法，其实就变成了 32 个整数相加。
前面顺序乘法器硬件的实现办法，就好像体育比赛里面的单败淘汰赛。只有一个擂台会存下最新的计算结果。每一场新的比赛就来一个新的选手，实现一次加法，实现完了剩下的还是原来那个守擂的，直到其余 31 个选手都上来比过一场。如果一场比赛需要一天，那么一共要比 31 场，也就是 31 天。
目前的乘法实现就像是单败淘汰赛
加速的办法，就是把比赛变成像世界杯足球赛那样的淘汰赛，32 个球队捉对厮杀，同时开赛。这样一天一下子就淘汰了 16 支队，也就是说，32 个数两两相加后，你可以得到 16 个结果。后面的比赛也是一样同时开赛捉对厮杀。只需要 5 天，也就是 O(log2N) 的时间，就能得到计算的结果。但是这种方式要求我们得有 16 个球场。因为在淘汰赛的第一轮，我们需要 16 场比赛同时进行。对应到我们 CPU 的硬件上，就是需要更多的晶体管开关，来放下中间计算结果。
通过并联更多的 ALU，加上更多的寄存器，我们也能加速乘法

电路并行

上面我们说的并行加速的办法，看起来还是有点儿笨。我们回头来做一个抽象的思考。之所以我们的计算会慢，核心原因其实是“顺序”计算，也就是说，要等前面的计算结果完成之后，我们才能得到后面的计算结果。
最典型的例子就是我们上一讲讲的加法器。每一个全加器，都要等待上一个全加器，把对应的进入输入结果算出来，才能算下一位的输出。位数越多，越往高位走，等待前面的步骤就越多，这个等待的时间有个专门的名词，叫作门延迟（Gate Delay）。
每通过一个门电路，我们就要等待门电路的计算结果，就是一层的门电路延迟，我们一般给它取一个“T”作为符号。一个全加器，其实就已经有了 3T 的延迟（进位需要经过 3 个门电路）。而 4 位整数，最高位的计算需要等待前面三个全加器的进位结果，也就是要等 9T 的延迟。如果是 64 位整数，那就要变成 63×3=189T 的延迟。这可不是个小数字啊！
除了门延迟之外，还有一个问题就是时钟频率。在上面的顺序乘法计算里面，如果我们想要用更少的电路，计算的中间结果需要保存在寄存器里面，然后等待下一个时钟周期的到来，控制测试信号才能进行下一次移位和加法，这个延迟比上面的门延迟更可观。
那么，我们有什么办法可以解决这个问题呢？实际上，在我们进行加法的时候，如果相加的两个数是确定的，那高位是否会进位其实也是确定的。对于我们人来说，我们本身去做计算都是顺序执行的，所以要一步一步计算进位。但是，计算机是连结的各种线路。我们不用让计算机模拟人脑的思考方式，来连结线路。
那怎么才能把线路连结得复杂一点，让高位和低位的计算同时出结果呢？怎样才能让高位不需要等待低位的进位结果，而是把低位的所有输入信号都放进来，直接计算出高位的计算结果和进位结果呢？
我们只要把进位部分的电路完全展开就好了。我们的半加器到全加器，再到加法器，都是用最基础的门电路组合而成的。门电路的计算逻辑，可以像我们做数学里面的多项式乘法一样完全展开。在展开之后呢，我们可以把原来需要较少的，但是有较多层前后计算依赖关系的门电路，展开成需要较多的，但是依赖关系更少的门电路。
我在这里画了一个示意图，展示了一下我们加法器。如果我们完全展开电路，高位的进位和计算结果，可以和低位的计算结果同时获得。这个的核心原因是电路是天然并行的，一个输入信号，可以同时传播到所有接通的线路当中。
C4 是前 4 位的计算结果是否进位的门电路表示
如果一个 4 位整数最高位是否进位，展开门电路图，你会发现，我们只需要 3T 的延迟就可以拿到是否进位的计算结果。而对于 64 位的整数，也不会增加门延迟，只是从上往下复制这个电路，接入更多的信号而已。看到没？我们通过把电路变复杂，就解决了延迟的问题。
这个优化，本质上是利用了电路天然的并行性。电路只要接通，输入的信号自动传播到了所有接通的线路里面，这其实也是硬件和软件最大的不同。
无论是这里把对应的门电路逻辑进行完全展开以减少门延迟，还是上面的乘法通过并行计算多个位的乘法，都是把我们完成一个计算的电路变复杂了。而电路变复杂了，也就意味着晶体管变多了。
之前很多同学在我们讨论计算机的性能问题的时候，都提到，为什么晶体管的数量增加可以优化计算机的计算性能。实际上，这里的门电路展开和上面的并行计算乘法都是很好的例子。我们通过更多的晶体管，就可以拿到更低的门延迟，以及用更少的时钟周期完成一个计算指令。

总结延伸

讲到这里，相信你已经发现，我们通过之前两讲的 ALU 和门电路，搭建出来了乘法器。如果愿意的话，我们可以把很多在生活中不得不顺序执行的事情，通过简单地连结一下线路，就变成并行执行了。这是因为，硬件电路有一个很大的特点，那就是信号都是实时传输的。
我们也看到了，通过精巧地设计电路，用较少的门电路和寄存器，就能够计算完成乘法这样相对复杂的运算。是用更少更简单的电路，但是需要更长的门延迟和时钟周期；还是用更复杂的电路，但是更短的门延迟和时钟周期来计算一个复杂的指令，这之间的权衡，其实就是计算机体系结构中 RISC 和 CISC 的经典历史路线之争。

推荐阅读

如果还有什么细节你觉得还没有彻底弄明白，我推荐你看一看《计算机组成与设计：硬件 / 软件接口》的 3.3 节。

课后思考

这一讲里，我为你讲解了乘法器是怎么实现的。那么，请你想一想，如果我们想要用电路实现一个除法器，应该怎么做呢？需要注意一下，除法器除了要计算除法的商之外，还要计算出对应的余数。
欢迎你在留言区写下你的思考和疑问，和大家一起探讨。你也可以把今天的文章分享给你朋友，和他一起学习和进步。
分享给需要的人，Ta购买本课程，你将得20元
生成海报并分享

赞 43

提建议

© 版权归极客邦科技所有，未经许可不得传播售卖。 页面已增加防盗追踪，如有侵权极客邦将依法追究其法律责任。
上一篇
13 | 加法器：如何像搭乐高一样搭电路（上）？
下一篇
15 | 浮点数和定点数（上）：怎么用有限的Bit表示尽可能多的信息？
unpreview
 写留言

精选留言(49)

  • 一步
    2019-06-02
    最后一个的展开电路图，没有看懂

    编辑回复: 这里想要解决的问题是，如果电路的“层数”太深，意味着一次运算需要的时钟循环数会太多，这样CPU就会“慢”，所以我们就把原先的电路尽量展开到比较少的层数，虽然这可能意味着电路的晶体管数量的增加。 具体到这里的加法，是把两个4位的二进制数相加，一个数A，从高位到低位是 A3A2A1A0，第二个数B，从高位到低位是 B3B2B1B0 我们加完之后的和，应该是 C4C3C2C1C0，变成5位，最高位的C4是代表这两个数相加之后是否会溢出一位需要进位。 不展开的情况下，我们计算C4，需要先算出A0和B0的和，以及是否进位，然后把是否进位，再和A1和B1相加，在看是否进位，这样一层层上来，这样的话，整个计算就需要至少5层（现在图里的是3层） 但是实际上我们可以把整个电路图展开，C4这个进位，只有这几种情况： 1. A3+B3 需要进位（两个都是1） 2. A3+B3是1（通过一个一个异或门）并且 A2+B2 进位。这里前面的这个就是图里第二列第一行的P3，后面是同一个节点里面的G2 3. A3+B3是1，并且 A2+B2 是1，并且 A1+B1进位。对应的就是第二列第二行的 P3，P2，G1 4. A3+B3是1，并且 A2+B2 是1，并且 A1+B1是1，并且A0+B0进位。对应的就是第二列第三行的 P3，P2，P1，G1 5. A3+B3是1，并且 A2+B2 是1，并且 A1+B1是1，并且A0+B0是1，并且下面进位上来的标志C0是1，对应的就是第二列第四行的P3，P2，P1，P0，C0 这5个结果就是图里面的第二列的电路，都是与门。然后任意一个条件满足，C4就需要进位，所以C4是这五个 与门 并联之后的 或门。

    共 11 条评论
    80
  • 旺旺
    2019-05-27
    从加法到乘法，先是计算过程变得复杂了，步骤变得更多，可以像人一样，逐位计算，但线性带来时间复杂度高。从而可以考虑通过增加线路/硬件复杂度，从空间换时间的思路，加快乘法速度。 空间 vs 时间。 但CPU毕竟也是很珍贵的资源，晶体管也不宜太多，这中间需要相互平衡。

    作者回复: 总结得很好，其实这也可以认为是CISC和RISC的路线之争最朴素的由来

    共 2 条评论
    37
  • Dylan
    2020-02-25
    CPU做除法时和做乘法时是相反的，乘法是右移，除法是左移，乘法做的是加法，除法做的是减法。除数右移，商左移，商左移后最右位补0还是1取决于，本次余数和除数相减后余数最高位，最高位1则，回退；0那么商左移后最右位补1。
    共 1 条评论
    14
  • 活的潇洒
    2019-05-27
    “这之间的权衡，其实就是计算机体系结构中的RISC和CISC的经典历史路线之争” 这句才是重点，day14 笔记：https://www.cnblogs.com/luoahong/p/10929985.html

    作者回复: 👍

    共 3 条评论
    13
  • WB
    2019-05-27
    最后一张图片中的加法器是一个与门和一个或门？？ 加法器不是由一个与门和一个异或门组成的吗？

    作者回复: WB同学你好， 最后一张图是表示如果我们不希望有太多的门延迟的情况下，我们怎么让加法器里面高位的是否获得进位，不用等待前面低位的全加器的计算结果。而不是一个完整的加法器。 我们重新复习一下 13 和 14 两讲的内容 完整的加法器可以由很多个全加器串联起来 全加器由两个半加器外加一个或门组成 半加器由一个与门和一个异或门组成 半加器只是整个加法器中最基础的一个零件

    11
  • -W.LI-
    2019-06-16
    老师好!前面的意思大概看懂了，最后那个优化版本的加法器看不懂了。。。
    共 1 条评论
    5
  • 愤怒的虾干
    2019-05-27
    老师好，最近在看您推荐的计算机组成公开课，x86保护模式下会使用全局符号描述表寻址，同时操作系统又是使用页表来分配地址、映射物理和逻辑地址。我想问全局符号描述表和页表在寻址上有什么区别与联系？

    作者回复: 全局符号表是虚拟内存内的内存寻址和跳转。 页表是虚拟内存和物理内存之间的映射关系。

    5
  • 冰凉的咖啡
    2021-03-13
    晶体管的增加，意味着功耗的增加吧，这也就是为什么移动端的ARM架构的CPU采用的精简指令集，而PC的X86架构却采用的是复杂指令集。
    3
  • DreamItPossible
    2019-08-14
    除法器算法实现描述： 步骤1 从余数寄存器中减去除数寄存器中的值，将结果保存在除数寄存器中； 步骤2 测试余数是否小于0 如果余数小于0，则执行步骤2b； 否则，执行步骤2a； 步骤2a 将商寄存器左移，且最低位设置为1； 步骤2b 将余数寄存器的值跟除数寄存器的值相加，结果存放在余数寄存器中；将商寄存器左移，最低位设置为0； 步骤3 将除数寄存器右移1位 步骤4 测试是否第N+1次执行 如果是，则结束；否则，跳转到步骤1执行；
    展开
    3
  • Become a architect
    2019-12-18
    我想现在并发编程的思想起源于此吧。效率确实高了，但是编程的复杂度变高了。

    作者回复: Become a architect同学， 你好，并发的思路是一个很直观的思路，并不是发源于乘法器，反而是乘法器设计的时候，可以去想想并发的思路。 而且这里最后的乘法器，前后的计算其实有依赖关系，我们只是通过分析电路，让部分前后的计算依赖关系解耦合，通过一个更复杂的电路来实现。

    2
  • 木心
    2019-09-27
    4位加法器的最大门延迟是进位，是2＊4＋1 9个门延迟

    作者回复: 木心同学， 你好，这是一个问题么？电路并行这部分我已经写了，可以做到没有那么多门延迟的。

    共 2 条评论
    2
  • J.D.Chi
    2019-09-21
    “把结果加到刚才的结果上”，想起了编程语言里的 sum = sum + i 之类的语句。

    作者回复: J.D.同学， 你好，是很像的

    2
  • X
    2022-08-04 来自上海
    这章看的好吃力了，已经过了两遍了，继续加油。 不言放弃，这次要补回大学欠下的东西。
    1
  • 苏格拉没底
    2021-05-13
    就是时间与空间的互换,和软件中的算法一样
    1
  • 李二木
    2021-04-18
    可以配套看视频https://www.bilibili.com/video/BV1VE411o7nx?p=21
    1
  • 花仙子
    2019-07-03
    对于最后那个优化版本的加法器，我的理解是这样的：每一位都是又全加器组成，而每个全加器由两个半加器和一个或门电路组成，其中一个半加器是计算每个位相加的和进位信息无关，所以这个半加器在各个位上可以同时并行计算，同时计算后每个位会得出相加结果Y和进位信息U，Y与上一位的进位信息W0用另一个半加器相加后得到结果Z和进位信息V，Z为此位最终相加结果，U和V通过或门电路计算可得出最终进位信息W提供给下一位进行同样的计算。这样看来似乎第二个半加器和或门电路计算还是要依赖上一位同样的计算得出的进位信息，貌似这里无法并行。但是真的就此结束了吗？看老师给出的图我的理解是这样的：每一位的运算公式是这样的：W=U||V，Z=（Y+W0）1，V=（Y+W0）2，（请允许我这里用+表示半加器，后缀1表示半加器得到的相加结果，后缀2代表半加器得到的进位信息），而W0=U0||V0，所以有Z=（Y+（U0||V0））1，W=U||（Y+W0）2，这样以来即便是最高位也能得到一个基于各位第一个半加器计算结果的逻辑表达式，对于人类来解这个表达式似乎也没有优化效果，但是正如老师所说电路的天然并行行，我们将这个很长的表达式展开，硬件就可以并行计算很多小步骤，从而得到空间换时间的巨大效率提升。
    展开
    1
  • Ethan New
    2022-11-03 来自浙江
    是用更少更简单的电路，但是需要更长的门延迟和时钟周期；还是用更复杂的电路，但是更短的门延迟和时钟周期来计算一个复杂的指令，这之间的权衡，其实就是计算机体系结构中 RISC 和 CISC 的经典历史路线之争。
  • 张无忌
    2022-10-11 来自浙江
    1个半加器有2个门电路：异或门+与门，1个全加器由2个半加器和1个或门组成，也就是一个全加器共有5个门，所以没太明白为什么全加器的门延迟是3T，而不是5T。希望老师解答，谢谢！
  • 张无忌
    2022-10-10 来自浙江
    “把被乘数左移一位，把乘数右移一位”，那他们两个岂不是错开两位？
    共 1 条评论
  • X
    2022-08-05 来自上海
    弄懂了7788了吧，顺序乘法器、并行乘法器，引出了门延迟和时钟频率带来的性能影响。使用“牺牲空间，追求时间”的方法，提升更多的晶体管，复杂电路的方式，追求更好的计算性能。