计算机组成 -- 乘法器

13 × 9

顺序乘法

二进制的乘法，在单个位上，乘数只能是0或1，所以实际的乘法，就退化成位移和加法
被乘数13表示成二进制是1101，乘数9表示成二进制是1001
- 最后边的个位是1，个位乘以被乘数，被乘数1101得以保留
- 二位和四位都是0，所以乘以被乘数都是0，保留下来的都是0000
- 八位是1，仍然需要把被乘数1101复制下来，但需要把复制好的结果向左移动三位
- 然后把上面四个乘法加位移的结果再加起来
  - 最后一步的加法可以用上一讲的加法器来实现
二进制乘法因为只有0和1两种情况，所以可以做成输入输出都是4个开关，中间有一个开关
- 中间的开关决定，下面的输出是完全复制输入，还是将输出全部设置为0
位移：左移一位，就错开一位接线；左移两位，就错开两位接线

节约开关（晶体管）

为了节省资源（开关，即晶体管）
- 类似13×9这样两个四位数的乘法，不需要把四次单位乘法的结果都用四组独立的开关单独记录然后再加起来
- 否则，如果计算一个32位的整数乘法，就要32组开关，非常浪费
- 如果顺序地计算，只需要一组开关就好
先拿乘数最右侧的个位乘以被乘数，然后把结果写入用来存放计算结果的开关里面
然后，把被乘数左移一位，把乘数右移一位，仍然用乘数的个位去乘以被乘数，然后把结果加到刚才的结果上
反复重复上面的步骤，直到不能再左移和或右移位置
这样，乘数和被乘数就像两列相向行驶的列车
- 仅仅需要一个加法器，一个可以左移一位的电路，一个可以右移一位的电路，就能完成整个乘法
- 下图中控制测试的含义：通过一个时钟信号，控制左移、右移和重新计算乘法和加法的时机
缺点：慢
- 在上面乘法器的实现过程中，其实就是把乘法展开，变成了加法+位移的实现
- 如果是4位数乘法，就要进行4组位移+加法的操作，而且这4组操作不能同时进行
  - 下一组的加法要依赖上一组的加法后的计算结果，下一组的位移也要依赖上一组的位移结果
- 这样，整个算法都是顺序的，最终该乘法的计算速度，其实和我们要计算的位数N有关，时间复杂度为O(N)！！

并行加速

目标：O(N) -> O(logN)
前面顺序乘法器硬件的实现，类比于体育比赛里面的单败淘汰赛，只有一个擂台会存下最新的计算结果，时间复杂度为**O(N)**
加速的办法，就是把比赛变成世界杯那样的淘汰赛，时间复杂度为**O(logN)**
- 对应到CPU的硬件上，就需要更多的晶体管开关，来存放中间计算结果

电路并行

顺序乘法器的计算会慢的核心原因是顺序计算
加法器（顺序计算的典型例子）
- 每一个全加器，都需要等待上一个全加器的输出结果
- 位数越多，越往高位走，等待前面的步骤就越多，这个等待的时间叫作门延迟（Gate Delay）
每通过一个门电路，就要等待门电路的计算结果，就是一层的门电路延迟，一般取一个T作为符号
- 一个全加器，对应3T的延迟
- 4位整数，最高位的计算需要等待前面三个全加器的进位结果，即9T的延迟
- 64位整数，对应就是63×3=189T的延迟，非常长！
时钟频率
- 上面的顺序乘法器中，如果想要用更少的电路，中间的计算结果需要保存在寄存器里面
- 然后等待下一个时钟周期的到来，控制测试信息才能进行下一次位移和加法，这个延迟比门延迟更可观
并行的前提
- 如果相加的两个数是确定的，那高位是否会进位其实也是确定的
并行的目标
- 让高位和低位的计算同时出结果
- 高位不需要等待低位的进位结果，把低位的所有输入信号都放进来，直接计算出高位的计算结果和进位结果
并行的方案
- 把进位部分的电路完全展开，类似于多项式乘法一样完全展开
- 把需要较少，但有较多层前后计算依赖关系的门电路，展开成需要较多，但依赖关系更少的门电路
- 如果完成展开电路，高位的进位和计算结果，可以与低位的计算结果同时获得
  - 核心原因：电路是天然并行的（电信号实时传输），一个输入信号，可以同时传播到所有接通的线路当中
下图是4位加法器的完全展开的门电路图，只需要3T的延迟就可以拿到是否进位的计算结果
- 对于64位的加法器，也不会增加门延迟，只是从上往下复制这个电路，接入更多信号而已
不论把对应的门电路逻辑进行完全展开来减少门延迟，还是并行计算多个位的乘法，都是把电路变复杂了，这意味着晶体管变多
- 通过更多的晶体管，可以拿到更低的门延迟，以及用更少的时钟周期完成一个计算指令
RISC Vs CISC
- 用简单电路，但需要更长的门延迟和时钟周期
- 用复杂电路，但更短的门延迟和时钟周期来计算一个复杂的指令