04.Integer Arithmetic

ALU

• 算术逻辑单元 (Arithmetic and Logic Unit, ALU) 是计算机实际完成数据算术逻辑运算的部件

  • 数据由寄存器 (Registers) 提交给ALU, 运算结果也存于寄存器

  • ALU可能根据运算结果设置一些标志 (Flags), 标志值也保存在处理器内的寄存器中

  • 控制器 (Control Unit) 提供控制ALU操作和数据传入送出ALU的信号

    

加法

全加器

• 注意: 异或门只能由2个输入端, 故需要6个门, 3个与门, 1个或门, 2个异或门

  

• 优化: 实际需要2个与门, 1个或门, 2个异或门, 但是延迟更高了

  

• 不足: 延迟高

串行进位 (行波进位) 加法器 RCA

• 实际就是将多个全加器连在一起

• 延迟:

  • C_n = 2n
  • F_n = C_n-1 + 3 = 2(n - 1) + 3 = 2n + 1 (n ≥ 3, 当n = 1 或 2 时, F = 6)

• 不足: 高位的运算必须等待低位的"进位输出信号"

• 思考: 能否提前计算出"进位输出信号"?

全先行进位加法器 CLA

• 设:

  • C₀, X_i, Y_i 都是已知输入
  • 生成 (Generate) 信号: G_i = X_i * Y_i
  • 传播 (Propagate) 信号: P_i = X_i + Y_i

​

​

• 延迟:

  • 1 (P和G同时计算) + 2 (C的与或门延迟依次计算) + 3 (F的第二个异或门延迟) = 6

• 优点: 延迟和加法器的位数无关

• 不足: 难以实现, 越到高位需要的与门越多

部分先行进位加法器

• 采用多个CLA并将其串联, 取得计算时间和硬件复杂度之间的权衡

​

• 延迟:

  • 3 (第一个CLA算出C₈的总延迟) + 2 (第二个CLA算C₁₆的与或门延迟) + 2 (同前一个) + 5 (同前一个外还有F的第二个异或门延迟) = 12

溢出问题

减法

• 溢出判断与加法相同

乘法

• 特征: 乘数右移一位, 被乘数左移一位, 中间结果直接与部分积累加

• 需要: n位支持右移寄存器, 2n位支持左移寄存器, 2n位寄存器和2n位加法器

​

流程优化

• 加法和移位并行

  

乘法器优化

• 减少不必要的硬件

​

• 需要: 1个n位加法器, 1个n位寄存器 (存被乘数), 1个2n位支持右移的寄存器 (乘数和乘积共用)

​

​

问题1 : [X * Y]_c ≠ [X]_c * [Y]_c

原码一位乘法

• 将被乘数和乘数由补码表示改为原码表示

• 符号位和数值位分开运算

• 将乘积结果由原码表示改为补码表示

​

补码一位乘法 – 布斯算法

• 运算步骤:

  1. 增加 y₀ = 0
  2. 根据 y_i+1y_i 决定是否执行 [P_i]_c + [±X]_c
  3. 右移部分积
  4. 重复 步骤2 和 步骤3 共n次, 得到最终结果

​

• 补的第n位 = 原第n位

  • 原来第n位为0, 右移后补0; 原来第n位为1, 右移后补1

问题2 : 溢出

• 对于带符号整数

  • 当 -2^n-1 ≤ x * y ≤ 2^n-1 - 1 时不溢出
  • 即: 当乘积的高n位全0或全1, 并等于低n位的最高位时, 不溢出

• 对于无符号整数

  • 当 0 ≤ x * y ≤ 2ⁿ - 1 时不溢出
  • 当乘积的高n位全0时, 不溢出

​

除法

• 在被除数的左侧补充符号位, 将除数的最高位与被除数的次高位对齐

• 从被除数中减去除数, 若够减, 则上商为1; 若不够减, 则上商为0

• 右移除数, 重复上述步骤

​

除法器

• 需要:

  • 一个2n位的加法器
  • 一个2n位的寄存器 : 被除数/余数
  • 一个2n位支持右移的寄存器 : 除数
  • 一个n位支持左移的寄存器 : 商

运算过程

流程图

除法器优化

• 余数和除数的减法运算中, 实际上只有n位参与了运算

• 余数和除数寄存器中, 至少有一个需要支持左移或右移

• 商寄存器必须支持左移, 且只需要n位

​

• 需要:

  • 一个n位加法器
  • 一个n位支持左移的寄存器 : 被除数/余数
  • 一个n位支持左移的寄存器 : 余数/商
  • 一个n位寄存器 : 除数

异号的除法

• 异号, 商需要取补码, 余数本身就是补码

​

比较余数和除数 (比较绕, 多理理)

• 如何判断 “够减” : 余数是否足够"大"

  • 如果余数和除数的符号相同 : 减法
  • 如果余数和除数的符号不同 : 加法
  • 够 : 补1; 不够 : 补0恢复

​

• 余数减除数后

  • 绝对值变小
  • 符号不能变 (0视为不变)

运算过程

流程图

问题 : 恢复余数成本高

• 思路: 不恢复余数

  • 只考虑减法
    • 如果余数R_i足够大 : R_i+1 = 2R_i - Y
    • 如果余数R_i不够大 : R_i+1 = 2(R_i + Y) - Y = 2R_i + Y

补码不恢复余数除法

• 最后还要判断余数和除数是否相同, 若相同要进行处理**(这是不恢复余数除法的固有bug)**

其他

• 只有一种情况发生溢出

  • 当 -2^n-1 / -1 = 2^n-1 时

• 编译器处理一个变量与2ⁿ相除时, 一般采用右移运算实现

  • 无符号: 逻辑右移
  • 带符号: 算术右移
  • 能整除时: 直接右移得到结果, 被移除的全为0
  • 不能整除时: 被移出数存在非0, 采取朝零舍入
    • 无符号: 直接右移得到结果, 移出的低位直接舍弃
    • 带符号: 加偏移量2^k - 1, 然后再移k位, 低位截断

​