Computer-Organization NOTES

Chapter3-2-1 Binary Multipliters 整数乘法

Posted by LvKouKou on October 17, 2022

3-2-1 Binary Multipliters 整数乘法

如果忽略符号位， m位 x n位 = m+n 位乘积 （即最大m+n位）

二进制乘法使用的是“Shift and Add” Multiplier

image-20221016164022966

v1 无符号移位-加法乘法器

image-20221016164100388

  • 需要32次迭代（加法移位⽐较）
  • ⼏乎⽤ 100 时钟周期

  • ⾮常⼤, 太慢

  • 64位被乘数寄存器、 64位ALU、 64位乘积寄存器、32位乘数寄存器

第⼀种乘法的启示

  • 每个周期 1个时钟 => 每次乘法⼤约100（32*3） 个时钟乘法与加法的出现频率⽐ 5:1 ~ 100:1
  • 64位被乘数中 1/2的位数 总是为 0 => 使⽤64位加法器, 太浪费 !!!
  • 在被乘数左移的过程中, 在右边插⼊ 0 => ⼀旦产⽣了乘积的最低位, 它就永远不变 !!!
  • ⽤乘积右移 替代 被乘数左移? 这样的话被乘数不用移动，就不用64位的了

改进方案：

被乘数固定不动， 乘积右移 ALU reduced to 32 bits!

Multiplier V2– Logic Diagram

32位被乘数寄存器、 32位ALU、 64位乘积寄存器、 32位乘数寄存器 （与v1比，被乘数寄存器变成32位，ALU变成32位）

步骤：把v1算法流程图中 被乘数左移1位改成乘积右移动一位

image-20221016165512814

第二种乘法的启示

乘积寄存器的低 32 bits 只是简单地被移出去 ，而刚好乘数和乘积都是要右移。乘积寄存器浪费的空间正好 与乘数中⽆⽤的空间相同

改进方案：

把乘积寄存器的低32位⽤作乘数寄存器，高32位初始化为0，32次操作后，乘数则会被全部移出去，此时这个64位寄存器中的64位整体即为乘积结果

Multiplier V 3 (Final Version)

此时乘积寄存器的高32位一开始初始化为0，低32位是乘数

image-20221016170627244

步骤：

以下操作要重复n次，n为乘数和被乘数位数（32位为例）

  • 检查乘积寄存器的最后一位（因为乘积寄存器低32位存的是乘数，所以其实就是乘数的最后一位）
    • 若为1，则乘积=乘积+被乘数（只有乘积寄存器的高32位与被乘数的32位相加，而乘积寄存器的低32位不变）
    • 若为0，不用加
  • 乘积寄存器右移（此时整体的64位都要右移，零扩展）

Signed Multiplication 有符号乘法

有符号数乘法如何?

  • 简单地策略是 假设两个源操作数都是正数, 在运算结束时再对乘积进⾏修正 (不算符号位, 运算31步)

  • 使⽤补码-需要对部分乘积进⾏符号扩展， 在最后再进⾏减法

==比较合理的版本:==

  • 使用无符号乘法硬件（即假设两个源操作数都是正数）
  • 右移时， 扩展乘积的符号位（乘积进⾏符号扩展）
  • 如果乘数是负数（即最后一步的时候乘数最右一位为1）， 最后一步应该是减法（也可以将被乘数转为补码相加）

image-20221016172433668

image-20221016172634536

Booth‘s Algorithm 布斯算法改进

如果乘数中有连续的1，则可以用此算法

key idea

看⼀下1的串 : 2 x 30 = 00010 x 011110 30 = -2 + 32 011110 = - 000010 + 100000

乘: • 加 000010 4次 (w/ shifts) （ 011110） - 或 - • 加 100000 ⼀次 减 000010 ⼀次 (w/ shifts) （ - 000010 + 100000 ）

Idea:乘数中间有’1’的串 ⽤在第⼀次看⻅1时的⼀次初始减法 和 在最后⼀个1后的⼀次加法代替

image-20221016173452968

早期, 由于移位⽐加法速度更快, 采⽤该算法主要为了速度

算法步骤: 如果乘数有连续个 ‘1’

  • 乘数第⼀个1做减法
  • 对‘1’移位
  • 最后⼀个1做加法

Booth’s Algorithm rule

image-20221016173629470

算数右移即要做符号扩展

example

image-20221016173802639

Array Multiplier 阵列乘法器

基本思路

若将所有的部分积aibj都同时算出来， 剩下的就是带进位位的加法求和。 这种乘法器要实现n位* n位时， 需要n(n-1)个全加器和n 个“与”⻔。

image-20221016173953458

ALU设计

image-20221016174054348

image-20221016174109749

image-20221016174123780

阵列乘法存在的问题

  • 存在的问题： ■ 第0级的加法没有必要 ■ 每⼀级加法采⽤串⾏进位， 速度受到影响

  • 改进措施： 采⽤CSA——保存进位加法器(Carry Save Adder) ■ CSA输出每⼀位相加的部分和， 同时将每⼀位的进位保存下来， 作为⼀个输出结果供下⼀级加法器来处理， ⽽不是向同⼀级的下⼀位进位 ■ 由于CSA不存在同级每个位之间的串⾏进位， 所以能以更快的速度得到进位和部分和

乘法器

image-20221016174328605

  • 从结构和逻辑上看， 1位CSA就是⼀个1位全加器
  • 采⽤CSA构造阵列乘法器， 前⾯⼏级采⽤不考虑进位的CSA， 最后⼀级采⽤常规的进位传播加法器CPA(Carry Propagate Adder)产⽣最后的乘积结果
  • CPA可以采⽤串⾏进位加法器， 也可以采⽤先⾏进位加法器

例子：

image-20221016174424310

CATALOG
    FEATURED TAGS
    Computer-Organization NOTES Project AI OS ML PatternRecognition Blog Distributed-System ANN CPU设计 CompilationPrinciple