L5 ALU

Transcription

1 Lecture 7: Arithmetic and Logic Operations and ALU 2

2 ALU 的功能说明 ALUop 3 A N Zero Result N Overflow B N ALU 可进行基本的加 / 减算 CarryOut 术运算 基本逻辑运算基本逻辑运算 其核心部件是加法器 ALU Control Lines (ALUop) Function 000 And 有关串行加法器和并行加 001 Or 法器的原理在数字逻辑电 010 Add 路课已讲过, 在此仅简单 110 Subtract 回顾 ALU 111 Set-on-less-than

3 回顾 : 串行进位加法器 全加器符号 : FA n 位串行 ( 行波 ) 加法器 : Cn FA FA FA C0 串行加法器的缺点 : 进位按串行方式传递, 速度慢! 问题 :n 位串行加法器从 C0 到 Cn 的延迟时间为多少? 假定与 / 或门延迟为 1ty, 异或门 3ty, 2n 级门延迟! 则 和 与 进位 的延迟为多少? 最后一位和数的延迟时间为多少? Sum 延迟为 6ty;Carryout 延迟为 2ty 2n+1 级门延迟!

4 回顾 : 并行进位加法器 (CLA 加法器 ) 为什么用先行进位方式? 串行进位加法器采用串行逐级传递进位串行逐级传递进位, 电路延迟与位数成正比关系 因此, 现代计算机采用一种先行进位 (Carry look ahead) 方式 如何产生先行进位? 定义辅助函数 :Gi=AiBi 进位生成函数 Pi=Ai+Bi 进位传递函数 ( 或 Pi=Ai Bi ) 通常把实现上述逻辑的电路称为进位生成 / 传递部件全加逻辑方程 :Si=Pi Ci Ci+1=Gi+PiCi (i=0,1, n) 设 n=4, 则 :C1=G0+P0C0 C2=G1+P1C1=G1+P1G0+P1P0C0 C3=G2+P2C2=G2+P2G1+P2P1G0+P2P1P0C0 C4=G3+P3C3=G3+P3G2+P3P2G1+P3P2P1G0+P3P2P1P0C0 由上式可知 : 各进位之间无等待, 相互独立并同时产生 通常把实现上述逻辑的电路称为 4 位 CLA 部件由此, 根据 Si=Pi Ci, 可并行求出各位和 通常把实现 Si=Pi Ci 的电路称为求和部件 CLA 加法器由 进位生成 / 传递部件 CLA 部件 和 求和部件 构成

5 回顾 : 8 位全先行进位加法器 A7 A0 B7 B0 进位生成 / 传递部件 P i =A i +B i ty P i =A i B i ----3ty 1ty ( 或 3ty) P7 P1 P0 G7 G1 G0 C8 8 位 CLA 部件 P7 C7 P1 C1 P0 C0 求和部件 C0 2ty 3ty S7 和的总延迟多少? 进位 C 8 的延迟多少? 和的总延迟 :1+2+3=6ty; 进位 C 8 的延迟 :1+2=3ty S1 S0

6 回顾 : 局部 ( 单级 ) 先行进位加法器 或称单级先行进位加法器 问题 : 所有和数产生的延迟为多少? =12ty

7 回顾 : 多级先行进位加法器 多级先行进位加法器 单级 ( 局部 ) 先行进位加法器的进位生成方式 : 组内并行 组间串行组间串行 所以, 单级先行进位加法器虽然比行波加法器延迟时间短, 但高位组进位依赖低位组进位, 故仍有较长的时间延迟 通过引入组进位生成 / 传递函数实现 组内并行 组间并行组间并行 进位方式设 n=4, 则 :C1=G0+P0C0 C2=G1+P1C1=G1+P1G0+P1P0C0 C3=G2+P2C2=G2+P2G1+P2P1G0+P2P1P0C0 G3 * =G3+P3C3=G3+P3G2+P3P2G1+P3P2P1G0 P3 * =P3P2P1P0 所以 C4 =G3 * +P3 * C0 把实现上述逻辑的电路称为 4 位 BCLA 部件

8 回顾 : 多级先行进位加法器 16 位两级先行进位加法器 4 位成组先行进位部件 (4 位 BCLA 部件 ) 4 位 CLA 加法器 4 位 CLA 加法器 4 位 CLA 加法器 4 位 CLA 加法器 关键路径长度为多少? 最终进位的延迟为多少? = 8ty 3+2=5ty

9 A 4-bit ALU 1-bit ALU 4-bit 串行 ALU A B CarryIn FA CarryOut Mux MUX 是什么?( 数字电路课学过 ) Result A0 B0 A1 B1 A2 B2 A3 B3 CarryIn0 CarryIn1 CarryIn2 CarryIn3 1-bit ALU 1-bit ALU 1-bit ALU 1-bit ALU CarryOut0 CarryOut1 CarryOut2 CarryOut3 Result0 Result1 Result2 Result3 关键路径延迟长, 速度慢!

10 先行进位 ALU 先行进位 ALU 芯片 (SN74181) 四位 ALU 芯片, 中规模集成电路 在先行进位加法器基础上附加部分线路, 具有基本的算术运算和逻辑运算功能 SN74181 的逻辑图和功能表 SN74182 是 4 位 BCLA ( 成组先行进位 ) 芯片 多芯片级联构成先行进位 ALU( 用于专用场合, 如教学机等 ) 1 个 SN74181 芯片直接构成一个 4 位全先行进位 ALU 4 个 SN74181 芯片串行构成一个 16 位单级先行进位 ALU 4 个 SN74181 芯片与 1 个 SN74182 芯片可构成 16 位两级先行进位 ALU 16 个 SN74181 芯片与 5 个 SN74182 芯片可构成 64 位先行进位 ALU 现代主流计算机中 ALU 是否通过芯片级联而成? ALU 的 加 运算电路相当于 n 档二进制加法算盘 所有其他运算都以 ALU 中 加 运算为基础! SKIP 无需芯片级联! 一个 CPU 芯片中有多个处理器核, 一个核中有多个 ALU!

11 回顾 :SN74181 的引脚 输入端输出端 P 输入端 :Ai 和 Bi 分别为第 1 和 2 操作数,Cn 为低位进位,M 为功能选择线,Si 为操作选择线, 共 4 位, 故最多有 16 种运算 输出端 :Fi 为运算结果,C n+4 P 和 G 为进位, A=B 为相等标志

12 SN74181 逻辑电路图

13 回顾 :SN74181 正逻辑功能表 BACK

14 回顾 :SN74182 芯片的引脚 输入端 :Pi 和 Gi 分别为第 i 组的组内进位传递函数和进位生成函数, Cn 为低位进位 输出端 : Cn+4 Cn+8 Cn+12 为相应组的组内进位,P* 和 G* 分别为整个大组的组进位传递函数和进位生成函数

15 SN74182 芯片的逻辑电路图 BACK

16 SN74181 和 SN74182 组成 16 位先行进位 ALU 4 位 ALU 4 位 ALU 4 位 ALU 4 位 ALU 16 位两级先行进位 ALU BACK

17 例 : 实现某 11 条 MIPS 指令的 ALU 在第 6 章 CPU 设计时详细介绍!

18 小结 高级语言程序中涉及的运算 (C 语言为例 ) 整数算术运算 浮点数算术运算 按位 逻辑逻辑 移位移位 位扩展和位截断位扩展和位截断 指令集中与运算相关的指令 (MIPS 为例 ) 涉及到的定点数运算 - 算术运算 带符号整数 : 取负 符号扩展符号扩展 加 减 乘 除 算术移位 无符号数 :0 扩展 加 减 乘 除 - 逻辑运算 逻辑操作 : 与 或 非 移位操作 : 逻辑左移 逻辑右移逻辑右移 涉及到的浮点数运算 : 加 减 乘 除 基本运算部件 ALU 的设计 是一种模运算系统! 全加器 串行加法器串行加法器 先行进位加法器 串行 ALU 先行进位 ALU( 单级 / 多级 ) MSI 芯片级联 直接做在 CPU 芯片内 需求转换 需求转换 CPU 中需提供哪些运算?Why Why? 定点运算 : 无符号数 按位逻辑运算 逻辑移位运算 位扩展和截断运算 加 / 减 / 乘 / 除运算 带符号整数 算术移位运算 扩展运算和截断运算 补码加 / 减 / 乘 / 除运算浮点运算 : 原码加 / 减 / 乘 / 除运算 移码加 / 减运算 下一讲开始介绍上述这些运算算法及其运算电路

19 定点数运算及运算部件 主要内容 加 / 减运算及其运算部件 补码 / 原码 / 移码加减运算 乘法运算及其运算部件 原码 / 补码乘法运算 快速乘法器 除法运算及其运算部件 原码 / 补码除法运算 快速除法器 定点运算器 十进制加减运算注 : 无符号数的按位逻辑运算可用逻辑门电路实现 ; 无符号数的逻辑移位运算可用专门的移位器或斜送结果等多种方式来实现 ; 带符号数的算术移位运算 无符号数和带符号整数的位扩展运算和截断运算也可用简单电路很容易地实现

20 补码加 / 减运算及其部件 补码加减运算公式 [A+B] 补 = [A] 补 + [B] 补 ( MOD 2 n ) [A B] 补 = [A] 补 + [ B] 补 ( MOD 2 n ) 补码加减运算要点和运算部件 加 减法运算统一采用加法来处理 符号位 ( 最高有效位 MSB) 和数值位一起参与运算 直接用 Adder 实现两个数的加运算 ( 模运算系统 ) 问题 : 模是多少? 运算结果高位丢弃, 保留低 n 位, 相当于取模 2 n 实现减法的主要工作在于 : 求 [ B] 补问题 : 如何求 [ B] 补? [ B] 补 =B+1 当控制端 Sub 为 1 时, 做减法当控制端 Sub 为 0 时, 做加法 B 4 B 4 Sub A CarryIn Sel 0 1 Mux 4 4 Adder 补码加 / 减运算部件 Zero Result 4 overflow CarryOut

21 补码加 / 减运算与 溢出 判断 Ex1: -7-6 = -7 + (-6) = +3 X -3-5 = (- 5) = Ex2: 用 8 位补码计算 =? 结果错误 : = 溢出现象 :(1) 最高位和次高位的进位不同 (2) 和的符号位和加数的符号位不同 问题 : 若采用变形补码结果怎样? 变形补码可保留运算中间结果 从乘除运算过程可看出这点! = = 进位是真正的符号 : 采用变形补码时 溢出 判断条件 : 结果的两个符号位不同

22 Overflow Detection Logic( 溢出判断逻辑 ) Carry into MSB! = Carry out of MSB For a N-bit ALU: Overflow = CarryIn [N-1] XOR CarryOut [N-1] A0 B0 A1 B1 A2 B2 A3 B3 CarryIn0 CarryIn1 CarryIn2 CarryIn3 1-bit ALU 1-bit ALU 1-bit ALU 1-bit ALU CarryOut0 CarryOut1 CarryOut2 CarryOut3 Result0 Result1 Result2 Result3 X Y X XOR Y 溢出标志 (Overflew Flag) 常用 OF 或 VF 表示 Overflow 也可以用其他实现方式

23 Zero Detection Logic( 判 0 逻辑 ) A0 B0 A1 B1 A2 B2 A3 B3 CarryIn0 1-bit Result0 ALU CarryIn1 CarryOut0 1-bit ALU CarryIn2 CarryOut1 1-bit ALU CarryIn3 CarryOut2 1-bit ALU CarryOut3 零标志 (Zero Flag) 常用 ZF 表示 Result1 Result2 Result3 问题 :MIPS 指令 bne $1,$2,25 的含义为 If ($1!=$2) goto PC else goto PC+4, 则执行 bne 指令需判断什么标志? Zero 除 Zero(ZF) Overflow(OF) 外, 许多机器还生成进 / 借位标志 (CF) 符号标志 (NF / SF) 等 标志 (Flag) 在运算电路中产生, 被记录到专门的寄存器中, 以便在分支指令中被用来作为条件 存放标志的寄存器通常称为程序 / 状态字寄存器或标志寄存器标志寄存器 每个标志对应标志寄存器中的一个标志位

24 原码加 / 减运算 用于浮点数尾数运算符号位和数值部分分开处理仅对数值部分进行加减运算, 符号位起判断和控制作用规则如下 : 比较两数符号, 对加法实行 同号求和, 异号求差, 对减法实行 异号求和, 同号求差 求和 : 数值位相加, 若最高位产生进位, 则结果溢出 和的符号取被加数 ( 被减数 ) 的符号 求差 : 被加数 ( 被减数 ) 加上加数 ( 减数 ) 的补码 a) 最高数值位产生进位表明加法结果为正, 所得数值位正确 b) 最高数值位没产生进位表明加法结果为负, 得到的是数值位的补码形式, 需对结果求补, 还原为绝对值形式的数值位 差的符号位 :a) 情况下, 符号位取被加数 ( 被减数 ) 的符号 ; b) 情况下, 符号位为被加数 ( 被减数 ) 的符号取反

25 原码加 / 减运算 例 1: 已知 [X] 原 = ,[Y] 原 = , 要求计算 [X+Y] 原解 : 由原码加减运算规则知 : 同号相加, 则求和, 和的符号同被加数符号 所以 : 和的数值位为 : = 1101 (ALU 中无符号数相加 ) 和的符号位为 :1 求和 : 直接加, 有进位则溢出, 符号同被 [X+Y] 原 = 例 2 : 已知 [X] 原 = ,[Y] 原 = , 要求计算 [X Y] 原解 : 由原码加减运算规则知 : 同号相减, 则求差 ( 补码减法 ) 差的数值位为 :0011+(1010) 补 = = 1001 最高数值位没有产生进位, 表明加法结果为负, 需对 1001 求补, 还原为绝对值形式的数值位 即 :(1001) 补 = 0111 差的符号位为 [X] 原的符号位取反, 即 :0 [X Y] 原 = 求差 : 加补码, 不会溢出, 符号分情况思考题 : 如何设计一个基于 ALU 的原码加 / 减法器?

26 移码加 / 减运算 用于浮点数阶码运算符号位和数值部分可以一起处理运算公式 ( 假定在一个 n 位 ALU 中进行加法运算 ) [E1] 移 +[E2] 移 =2 n-1 +E1+2 n-1 +E2=2 n +E1+E2=[E1+E2] 补 (mod 2 n ) [E1] 移 [E2] 移 =[E1] 移 +[ [E2] 移 ] 补 =2 n-1 +E1+2 n [E2] 移 =2 n-1 +E1+2 n 2 n-1 E2 = 2 n +E1 E2 = [E1 E2] 补 (mod 2 n ) 结论 : 移码的和 差等于和差等于和 差的补码差的补码! 运算规则补码和移码的关系 : 符号位相反 数值位相同! 1 加法 : 直接将 [E1] 移和 [E2] 移进行模 2 n 加, 然后对结果的符号取反 2 减法 : 先将减数 [E2] 移求补 ( 各位取反, 末位加 1), 然后再与被减数 [E1] 移进行模 2 n 相加, 最后对结果的符号取反 3 溢出判断 : 进行模 2 n 相加时, 如果两个加数的符号相同, 并且与和数的符号也相同, 则发生溢出

27 移码加 / 减运算 例 1: 用四位移码计算 7+( 6) 和 的值 解 :[ 7] 移 = 0001 [ 6] 移 = 0010 [ 3] 移 = 0101 [6] 移 = 1110 [ 7] 移 + [ 6] 移 = = 0011 ( 两个加数与结果符号都为 0, 溢出 ) [ 3] 移 + [6] 移 = = 0011, 符号取反后为 1011, 其真值为 +3 问题 :[ 7+( 6)] 移 =? [ 3+(6)] 移 =? 例 2: 用四位移码计算 7 ( 6) 和 3 5 的值 解 :[ 7] 移 = 0001 [ 6] 移 = 0010 [ 3] 移 = 0101 [5] 移 = 1101 [ 7] 移 [ 6] 移 = = 1111, 符号取反后为 0111, 其真值为 1 [ 3] 移 [5] 移 = = 1000, 符号取反后为 0000, 其真值为 8

28 无符号数的乘法运算 假定 :[X] 原 =x 0.x 1 x n,[y] 原 =y 0.y 1 y n, 求 [x Y] 原 数值部分 z 1 z 2n = (0.x 1 x n ) (0. y 1 y n ) ( 小数点位置约定, 不区分小数还是整数 ) Paper and pencil example: Multiplicand 1000 Multiplier x Product( 积 ) X y X y X y X y X Y= (X y i 2 -i ) i=1 整个运算过程中用到两种操作 : 加法 + 左移因而, 也可用 ALU 和移位器来实现乘法运算

29 无符号数的乘法运算 手工乘法的特点 : 1 每步计算 :X yi, 若 yi = 0, 则得 0; 若 yi = 1, 则得 X 2 把 1 求得的各项结果 X yi 逐次左移, 可表示为 X yi 2 -i 3 对 2 中结果求和, 即 (X yi 2 -i ), 这就是两个无符号数的乘积 计算机内部稍作以下改进 : 1 每次得 X yi 后, 与前面所得结果累加, 得到 Pi, 称之为部分积 因为不等到最后一次求和, 减少了保存各次相乘结果 X yi 的开销 2 每次得 X yi 后, 不将它左移与前次部分积 Pi 相加, 而将部分积 Pi 右移后与 X yi 相加 因为加法运算始终对部分积中高 n 位进行 故用 n 位加法器可实现二个 n 位数相乘 3 对乘数中为 1 的位执行加法和右移, 对为 0 的位只执行右移, 而不执行加法运算

30 无符号乘法运算的算法推导 上述思想可写成如下数学推导过程 : X Y = X ( 0.y 1 y 2 y n ) = X y X y X y X y n 2 -n =2-1 ( 2-1 ( (2-1 (0 + X y n ) + X y n-1 ) + + X y 2 ) + X y 1 ) n 个 2-1 上述推导过程具有明显的递归性质, 因此, 无符号数乘法过程可归结为循环计算下列算式的过程 : 设 P 0 = 0, 每步的乘积为 : P 1 = 2-1 (P 0 + X y n ) P 2 = 2-1 (P 1 + X y n-1 ) P n = 2-1 (P n-1 + X y 1 ) 其递推公式为 :P i+1 = 2-1 (P i + X y n-i ) ( i = 0, 1, 2, 3,, n-1 ) 最终乘积 P n = X Y 迭代过程从乘数最低位 y n 和 P 0 =0 开始, 经 n 次 判断 加法 右移 循环, 直到求出 Pn 为止

31 32 位乘法运算的硬件实现 被乘数寄存器 X 位 ALU 加 每次循环都要对进位位 C 乘积寄存器 P 和乘数寄存器实现同步逻辑 右移 32 C 64 位乘积寄存器 P 乘数寄存器 Y 32 右移写使能 控制逻辑计数器 Cn 时钟 被乘数寄存器 X: 存放被乘数 乘积寄存器 P: 开始置初始部分积 P0 = 0; 结束时, 存放的是 64 位乘积的高 32 位 乘数寄存器 Y: 开始时置乘数 ; 结束时, 存放的是 64 位乘积的低 32 位 进位触发器 C: 保存加法器的进位信号 循环次数计数器 Cn: 存放循环次数 初值 32, 每循环一次,Cn 减 1,Cn=0 时结束 ALU: 乘法核心部件 在控制逻辑控制下, 对 P 和 X 的内容 加, 在 写使能 控制下运算结果被送回 P, 进位位在 C 中

32 Example: 无符号整数乘法运算 举例说明 : 设 A=1110 B=1101 应用递推公式 : P i =2-1 (Ab i + P i-1 ) C 乘积 P 乘数 R 可用一个双倍字长的乘积寄存器 ; 也可用两个单倍字长的寄存器 部分积初始为 0 保留进位位 右移时进位 部分积和剩余乘数一起进行逻辑右移逻辑右移 验证 :A=14, B=13, A x B=182

33 原码乘法算法 用于浮点数尾数乘运算 符号与数值分开处理 : 积符异或得到, 数值用无符号乘法运算 例 : 设 [x] 原 =0.1110,[y] 原 =1.1101, 计算 [X Y] 原解 : 数值部分用无符号数乘法算法计算 : = 符号位 :0 1=1, 所以 : [X Y] 原 = 原码一位乘法 : 每次只取乘数的一位判断, 需 n 次循环, 速度慢 原码两位乘法 : 每次取乘数两位判断, 只需 n/2 次循环, 快一倍 P.94 表 3.3 原码两位乘法递推公式 : 00 :P i+1 =2-2 P i 01 :P i+1 =2-2 (P i +X) 10 :P i+1 =2-2 (P i +2X) 11 :P i+1 =2-2 (P i +3X)=2-2 (P i +4X-X) =2-2 (Pi -X) +X 3X 时, 本次 -X, 下次 +X! y i-1 y i T 操 作 0 T +X 0 T +X 0 T +2X 0 T +2X 0 T X 1 T X 1 T 1 T 迭代公式 T 触发器用来记录下次是否要执行 +X +X X 运算用 +[ +[-X] 补 实现! 2-2 (P i ) 2-2 (P i + X) 2-2 (P i + X) 2-2 (P i + 2X) 2-2 (P i + 2X) 2-2 (P i X) 2-2 (P i X) 2-2 (P i )

34 原码两位乘法举例 已知 [X] 原 = , [Y] 原 = , 用原码两位乘法计算 [X Y] 原解 : 先用无符号数乘法计算 , 原码两位乘法过程如下 : 采用补码算术右移为模 8 补码形式 ( 三位符号位 ), 为什么? 若用模 4 补码, 则 P 和 Y 同时右移 2 位时, 得到的 P3 是负数, 这显然是错误的! 需要再增加一位符号

35 补码乘法运算 用于定点整数乘法运算 因为 [X x Y] 补 [X] 补 x [Y] 补, 故不能直接用无符号乘法计算 符号与数值统一处理 Booth s Algorithm 推导如下 : 假定 :[X] 补 =x n-1 x n-2 x 1 x 0, [ Y] 补 =y n-1 y n-2 y 1 y 0, 求 :[X x Y] 补 =? 基于以下补码性质 : 令 [Y] 补 =y n-1 y n-2 y 1 y 0, 则 Y=-y. n-1 2 n-1 +y. n-2 2 n-2 + y y 令 :y -1 =0, 则 : 当 n=32 时,Y=-y y y y y y (y y )+ +(y y )+ y (y 30 -y 31 ) (y 29 -y 30 ) (y 0 y 1 ) (y -1 -y 0 ) [XxY] 补 = (y 30 -y 31 )X (y 29 -y 30 )X (y 0 y 1 ) (y -1 -y 0 ) = 2-1 (2-1 (2-1 (y -1 -y 0 )X) + (y 0 y 1 )X) + + (y 30 -y 31 )X) 部分积公式 :P i =2-1 (P i-1 + (y i-1 -y i )X)

36 Booth s 算法实质 middle end of run of run beginning of run 当前位 右边位 操作 Example 1 0 减被乘数 加 0 ( 不操作 ) 加被乘数 加 0 ( 不操作 ) 最初提出这种想法是因为在 Booth 的机器上移位操作比加法更快! 在 1 串 中, 第一个 1 时做减法, 最后一个 1 做加法, 其余情况只要移位 同前面算法一样, 将乘积寄存器右移右移一位一位 ( 这里是算术右移 )

37 布斯算法举例 已知 [X] 补 = 1 101,[Y] 补 = 0 110, 计算 [X Y] 补 [-X] 补 = 验证 :X = -3,Y = 6,X Y= B = -18, 结果正确!

38 Booths Example: 2 x 3 mythical bit Operation Multiplicand Product next? 0. initial value > sub 1a. P = P - m shift P (sign ext) 1b > add a shift P 2b > sub a shift 3b > nop 4a shift 4b done 最后乘积

39 补码两位乘法 补码两位乘可用布斯算法推导如下 : [P i+1 ] 补 = 2-1 ( [P i ] 补 + ( y i-1 y i ) [X] 补 ) [P i+2 ] 补 = 2-1 ( [P i+1 ] 补 + ( y i y i+1 ) [X] 补 ) = 2-1 (2-1 ( [P i ] 补 + ( y i-1 y i ) [X] 补 ) + ( y i y i+1 ) [X] 补 ) = 2-2 ( [P i ] 补 + (y i-1 + y i 2y i+1 ) [X] 补 ) 开始置附加位 y -1 为 0, 乘积寄 存器最高位前面添加一位附加 符号位 0 最终的乘积高位部分在乘积寄 存器 P 中, 低位部分在乘数寄 存器 Y 中 因为字长总是 8 的倍数, 所以 补码的位数 n 应该是偶数, 因 此, 总循环次数为 n/2 y i+1 y i y i 操 作 0 +[X] 补 +[X] 补 +2[X] 补 +2[-X] 补 +[-X] 补 +[-X] 补 0 迭代公式 2-2 [P i ] 补 2-2 {[P i ] 补 +[X] 补 } 2-2 {[P i ] 补 +[X] 补 } 2-2 {[P i ] 补 +2[X] 补 } 2-2 {[P i ] 补 +2[-X] 补 } 2-2 {[P i ] 补 +[-X] 补 } 2-2 {[P i ] 补 +[-X] 补 } 2-2 [P i ] 补

40 补码两位乘法举例 已知 [X] 补 = 1 101, [Y] 补 = 0 110, 用补码两位乘法计算 [X Y] 补 解 :[ X] 补 = 0 011, 用补码二位乘法计算 [X Y] 补的过程如下的过程如下 P n P Y y -1 说明 开始, 设 y -1 = 0,[P 0 ] 补 = y 1 y 0 y -1 =100,+2[-X] 补 P 和 Y 同时右移二位 得 [P 2 ] 补 y 3 y 2 y 1 = 011,+2[X] 补 P 和 Y 同时右移二位 得 [P 4 ] 补因此 [X Y] 补 = , 与一位补码乘法 ( 布斯乘法 ) 所得结果相同, 但循环次数减少了一半 验证 :-3 6=-18 (-10010B)

41 快速乘法器 前面介绍的乘法部件的特点 通过一个 ALU 多次 加 / 减 + 右移 来实现 - 一位乘法 : 约 n 次 加 + 右移 - 两位乘法 : 约 n/2 次 加 + 右移 存在瓶颈 : 所需时间随位数增多而加长 设计快速乘法部件的必要性 大约 1/3 是乘法运算 快速乘法器的实现 流水线方式 硬件叠加方式 ( 如 : 阵列乘法器 ) 阵列乘法器 用一个实现特定功能的组合逻辑单元构成一个阵列

42 流水线方式的快速乘法器 为乘数的每位提供一个 n 位加法器 每个加法器的两个输入端分别是 : 本次乘数对应的位与被乘数相与的结果 ( 即 :0 或被乘数 ) 上次部分积 每个加法器的输出分为两部分 : 和的最低有效位 (LSB) 作为本位乘积 进位和高 31 位的和数组成一个 32 位数作为本次部分积 1

43 阵列乘法器的实现 手算乘法过程 阵列乘法器 进位输出 部分积输入全加器 Ai Bi 进位输入 被乘数 X 0 A 0 3 A 0 2 A 1 0 A 0 B 0 0 部分积输出 P 7 P 6 P 5 P 4 P 3 P 2 P 1 P 0 B 3 0 B 2 0 B 1 0 速度仅取决于逻辑门和加法器的传输延迟 无符号阵列乘法器增加符号处理电路 乘前及乘后求补电路, 即可实现带符号数乘法器

44 Divide: Paper & Pencil 1001 Quotient( 商 ) Divisor Dividend( 被除数 ) 中间余数 Remainder ( 余数 ) 手算除法的基本要点 被除数与除数相减, 够减则上商为 1; 不够减则上商为 0 每次得到的差为中间余数, 将除数右移后与上次的中间余数比较 用中间余数减除数, 够减则上商为 1; 不够减则上商为 0 重复执行第 2 步, 直到求得的商的位数足够为止

45 定点除法运算 除前预处理 1 若被除数 =0 且除数 0, 或定点整数除法 被除数 < 除数, 则商为 0, 不再继续 2 若被除数 0 除数 =0, 则发生 除数为 0 异常 3 若被除数和除数都为 0, 则有些机器产生一个不发信号的 NaN, 即 quiet NaN 当被除数和除数都 0, 且商 0 时, 才进一步进行除法运算 计算机内部无符号数除法运算 与手算一样, 通过被除数 ( 中间余数 ) 减除数来得到每一位商够减上商 1; 不够减上商 0 基本操作为减法 ( 用加法实现 ) 和移位, 故可与乘法合用同一套硬件

46 完全模拟手工的无符号数除法硬件实现 两个 n 位数相除的情况 : (1) 定点正整数 ( 即无符号数 ) 相除 : 在被除数的高位添 n 个 0 (2) 定点正小数 ( 即原码小数 ) 相除 : 在被除数的低位添加 n 个 0 这样, 就将所有情况都统一为 : 一个 2n 位数除以一个 n 位数 64 位除数寄存器, 后 n 位为 0 以下是 64 位数除以 32 位数 64 位余数寄存器, 初始为被除数的除法器逻辑结构 32 位商寄存器, 初始值为 0 64-bit ALU Divisor 64 bits Shift Right Quotient 32 bits Shift Left Remainder 64 bits Write Control

47 手工 Divide Algorithm 要点 : 1. 余数 - 除数 = 新余数 Start 1. Subtract the Divisor register from the Remainder register, and place the result in the Remainder register. 2(a) 新余数 <0, 商左移上 0 并恢复余数 2(b) 新余数 >=0, 商左移上 1 3. 除数右移 Remainder >=0 Test Remainder Remainder < 0 n 位除法需 n+1 步 2a. Shift the Quotient register to the left setting the new rightmost bit to 1. 2b. Restore the original value by adding the Divisor reg to the Remainder reg and place the sum in the Remainder reg. Also shift the Quotient register to the left, setting the new LSB to 0 3. Shift the Divisor register right1 bit. 33rd repetition? No: < 33 repetitions 举例 :7/2 = 3 余 1 Yes: 33 repetitions Done

48 Divide Algorithm--example Q: 0000 D: R: D = : R = R D Q: 0000 D: R: b: +D, sl Q, 0 Q: 0000 D: R: : Shr D Q: 0000 D: R: D = : R = R D Q: 0000 D: R: b: +D, sl Q, 0 Q: 0000 D: R: : Shr D Q: 0000 D: R: D = : R = R D Q: 0000 D: R: b: +D, sl Q, 0 Q: 0000 D: R: : Shr D Q: 0000 D: R: D = : R = R D Q: 0000 D: R: a: sl Q, 1 Q: 0001 D: R: : Shr D Q: 0001 D: R: D = : R = R D Q: 0001 D: R: a: sl Q, 1 Q: 0011 D: R: : Shr D Q: 0011 D: R: 验证 验证 :7/2=3 余 1 问题 :Q 中第一个 0 说明什么? 说明没有 溢出, 它不是真正的商!

49 完全模拟手工的无符号数除法硬件实现 问题 : 第一次试商为 1, 说明什么? 溢出! 若是无符号整数运算 (2n 位除以 n 位 ), 则说明将会得到多于 n+1 位的商, 因而结果 溢出 ( 即 : 无法用 n 位表示商 ) 例 : /1111 = 若是两个 n 位数相除, 则肯定不会溢出, 为什么? 最大商为 : /0001=1111 若是浮点数中尾数原码小数运算, 则说明尾数部分有 溢出, 可通过浮点数的 右规 消除 溢出 所以, 在浮点数运算器中, 第一次得到的商 1 要保留 例 : /0.1000=

50 对手算除法算法的观察 因为结果肯定不 溢出, 故第 1 次商肯定为 0, 不 1/2 bits in divisor( 除数寄存器 ) always 0 用先做减法试商, 而将第 能否考虑只用 32 位除数寄存器和 32 位 ALU? 一步换成先左移, 可减少 可用余数左移代替除数右移一次迭代 可使商通过和余数一起左移来取消商寄存器 开始时先使余数左移一位 ( 问题 : 为什么可这样做?) 两个寄存器的结合以及循环内次序的调换使得余数被多左移了一次 所以最后一步余数寄存器的左半边的余数必须向右移一位 Divisor 64 bits Shift Right 64-bit ALU Quotient 32 bits Shift Left Remainder 64 bits Write Control

51 无符号数除法算法的硬件实现 R 和 Q 同步 左移,Q 空出位上 商, 商的各位逐次左移到 Q 中 由控制逻辑根据 ALU 结果的符号决定商为 0 还是 1 除数寄存器 Y: 存放除数 余数寄存器 R: 初始时高位部分为高 32 位被除数 ; 结束时是余数 余数 / 商寄存器 Q: 初始时为低 32 位被除数 ; 结束时是 32 位商 循环次数计数器 Cn: 存放循环次数 初值是 32, 每循环一次,Cn 减 1, 当 Cn=0 时, 除法运算结束 ALU: 除法核心部件 在控制逻辑控制下, 对于寄存器 R 和 Y 的内容进行 加 / 减 运算, 在 写使能 控制下运算结果被送回寄存器 R

52 Divide Algorithm example 验证 :7 / 2 = 3 余 1 D = 1110 和书中的例子稍有不同, 书中没有省略判断溢出的过程 D: 0010 R: Shl R D: 0010 R: R = R D D: 0010 R: D, sl R, 0 D: 0010 R: R = R D D: 0010 R: D, sl R, 0 D: 0010 R: R = R D D: 0010 R: sl R, 1 D: 0010 R: R = R D D: 0010 R: sl R, 1 D: 0010 R: Shr R(rh) D: 0010 R: 从例子可看出 : 每次上商为 0 时, 需做加法以 恢复余数 所以, 称为 恢复余数法也可在下一步运算时把当前多减的除数补回来 这种方法称为 不恢复余数法, 又称 加减交替法 最后余数需向右移一位

53 不恢复余数除法 ( 加减交替法 ) 恢复余数法可进一步简化为 加减交替法 根据恢复余数法 ( 设 B 为除数,Ri 为第 i 次中间余数 ), 有 : 若 Ri<0, 则商上 0, 做加法恢复余数, 即 : Ri+1=2(Ri+2 n B )-2 n B =2Ri + 2 n B ( 负,0, 加 ) 若 Ri>0, 则商上 1, 不需恢复余数, 即 : Ri+1=2Ri - 2 n B ( 正,1, 减 ) 省去了恢复余数的过程注意 : 最后一次上商为 0 的话, 需要 纠余 处理, 即把试商时被减掉的除数加回去, 恢复真正的余数 不恢复余数法也称为加减交替法

54 带符号数除法 原码除法 o 商符和商值分开处理 商的数值部分由无符号数除法求得 商符由被除数和除数的符号确定 : 同号为 0, 异号为 1 o 余数的符号同被除数的符号 补码除法 o 方法 1: 同原码除法一样, 先转换为正数, 先用无符号数除法, 然后修正商和余数 o 方法 2: 直接用补码除法, 符号和数值一起进行运算, 商符直接在运算中产生 两个 n 位补码整数除法运算, 被除数需要进行符号扩展 若被除数为 2n 位, 除数为 n 位, 则被除数无需扩展

55 原码除法举例 已知 [X] 原 = [Y] 原 = 用恢复余数法恢复余数法计算 [X/Y] 原解 : 商的符号位 :0 1 = 1 减法操作用补码加法实现, 是否够减通过中间余数的符号来判断, 所以中间余数要加一位符号位 [ X ] 补 = [ Y ] 补 = [ Y ] 补 = 小数在低位扩展 0 确认不溢出时可省略 思考 : 若实现无符号数相除, 即 1011 除以 1101, 则有何不同? 结果是什么?

56 原码除法举例 已知 [X] 原 = [Y] 原 = 用加减交替法加减交替法计算 [X/Y] 原解 :[ X ] 补 = [ Y ] 补 = [ Y ] 补 = 加减交替法 的要点 : 正 1 减负 0 加得到的结果与恢复余数法一样! 问题 : 用被除数 ( 中间余数 ) 减除数试商时, 怎样确定是否 够减? 中间余数的符号! 补码除法能否这样来判断呢?

57 实现补码除法的基本思想 补码除法判断是否 够减 的规则 (1) 当被除数 ( 或中间余数 ) 与除数同号时, 做减法, 若新余数的符号与除数符号一致表示够减, 否则为不够减 ; (2) 当被除数 ( 或中间余数 ) 与除数异号时, 做加法, 若得到的新余数的符号与除数符号一致表示不够减, 否则为够减 上述判断规则用表表示为 : 中间余数 R 除数 Y 新中间余数 : R Y( 正商 ) 0 1 新中间余数 : R+Y( 负商 ) 够减不够减 不够减够减 够减不够减 不够减够减 SKIP

58 实现补码除法的基本思想 从上表可得到补码除法的基本算法思想 : (1) 运算规则 : 当被除数 ( 或中间余数 ) 与除数同号时, 做减法 ; 异号时, 做加法 (2) 上商规则 : 若余数符号不变, 则够减, 商 1; 否则不够减, 商 0 商为正时 : 若新余数与除数符号一致, 则够减, 商 1; 否则不够减, 商 0 ( 原码 ) 商为负时 : 若新余数与除数符号不一致, 够减, 商 0; 否则不够减, 商 1 ( 反码 ) 补码除法也有 : 恢复余数法和不恢复余数法 SKIP

59 补码恢复余数法 算法要点 : (1) 操作数的预置 : 除数装入除数寄存器 Y, 被除数经符号扩展后装入余数寄存器 R 和余数 / 商寄存器 Q (2) R 和 Q 同步串行左移一位 (3) 若 R 与 Y 同号, 则 R = R Y; 否则 R = R+Y, 并按以下规则确定商值 q 0 : 1 若中间余数 R Q = 0 或 R 操作前后符号未变, 表示够减, 则 q 0 置 1, 转下一步 ; 2 若操作前后 R 的符号已变, 表示不够减, 则 q 0 置 0, 恢复 R 值后转下一步 ; (4) 重复第 (2) 和第 (3) 步, 直到取得 n 位商为止 (5) 若被除数与除数同号, 则 Q 中就是真正的商 ; 否则, 将 Q 求补后是真正的商 ( 即 : 若商为负值, 则需要 各位取反, 末位加 1 来得到真正的商 ) (6) 余数在 R 中 问题 : 如何恢复余数? 通过 做加法 来恢复吗? 无符号数 ( 或原码 ) 除法通过 做加法 恢复余数, 但补码不是! 若原来为 R = R Y, 则执行 R = R+Y 来恢复余数, 否则, 若原来是 R = R+Y, 则执行 R = R Y

60 举例 :7/3=? (-7)/3=? 被除数 : A Q M= 减 除数 恢复 ( 加 ) 商 减 恢复 ( 加 ) 商 减 符同商 减 恢复 ( 加 ) 商 余 :0001/ 商 :0010 验证 :7/3 = 2, 余数为 1 被除数 : 除数 A Q M= 加 恢复 ( 减 ) 商 加 恢复 ( 减 ) 商 加 符同商 加 恢复 ( 减 ) 商 商为负数, 需求补 : 余 :1111/ 商 :1110 验证 :-7/3 =- 2, 余数为 -1

61 补码不恢复余数法 算法要点 : (1) 操作数的预置 : 除数装入除数寄存器 Y, 被除数经符号扩展后装入余数寄存器 R 和余数 / 商寄存器 Q (2) 根据以下规则求第一位商 q n : 若被除数 X 与 Y 同号, 则 R1=X Y; 否则 R1 =X+Y, 并按以下规则确定商值 q n : 1 若新的中间余数 R1 与 Y 同号, 则 q n 置 1, 转下一步 ; 判断是否同号与恢复余数 2 若新的中间余数 R1 与 Y 异号, 则 q n 置 0, 转下一步 ; 法不同, 不是新老余数! q n 用来判断是否溢出, 而不是真正的商 以下情况下会发生溢出 : 是余数和除数之间同号则够减, 商 1? 若 X 与 Y 同号且上商 q n =1, 或者, 若 X 与 Y 异号且上商 q n = 0 异号则不够减, 商 0? (3) 对于 i =1 到 n, 按以下规则求出 n 位商 : 错! 参看前面的表 1 若 Ri 与 Y 同号, 则 q n-i 置 1,Ri+1 = 2Ri [Y] 补,i = i +1; 2 若 Ri 与 Y 异号, 则 q n-i 置 0,Ri+1 =2Ri+[Y] 补,i = i +1; (4) 商的修正 : 最后一次 Q 寄存器左移一位, 将最高位 q n 移出, 最低位置上商 q 0 若被除数与除数同号, Q 中就是真正的商 ; 否则, 将 Q 中商的末位加 1 商已经是 反码 (5) 余数的修正 : 若余数符号同被除数符号, 则不需修正, 余数在 R 中 ; 否则, 按下列规则进行修正 : 当被除数和除数符号相同时, 最后余数加除数 ; 否则, 最后余数减除数 补码不恢复余数法也有一个六字口诀 同 1 减; 异 0 加 其运算过程也呈加 / 减交替方式, 因此也称为 加减交替法

62 举例 :-9/2 将 X=-9 和 Y=2 分别表示成 5 位补码形式为 : [X] 补 = [Y] 补 = 被除数进行符号扩展为 : [X] 补 = [ Y] 补 = 同 1 减异 0 加 X/Y= 0100B = 4, 余数为 0001B = 1 将各数代入公式 : 除数 商 + 余数 = 被除数 进行验证, 得 : 2 ( 4) +( 1) = 9

63 快速除法器 问题 : 可以像乘法一样用 32 个 Adder 同时进行加 / 减运算来实现流水线方式的快速除法器吗? 不行! 每次做加法还是减法, 必须要知道上次余数的符号 很难实现流水化 比快速乘法器更难实现 阵列除法器比阵列乘法器复杂 P=1 Q Y 1 X 1 X 2 X 3 X 4 X 5 X 6 X 7 X 8 Y 2 Y 3 Y 4 右图是实现对两个正数按不恢复余数法进行相除的阵列除法器 第一次总是做减法, 故 P=1 使第一行做减法 ; 中间行最高位进位 Co 确定商和下次做加 / 减, 故 Co 连到 Qi 和下一行控制线 P Q 1 Q 2 Q 3 Q 4 控制线 P 进 / 借位出 Co s = x (p y ) ci Co = (x + Ci) (p y ) + xci p = 0 时,s = x y Ci, Co = xy + yci + xci p = 1 时,s = x y Ci, Co = xy + yci + xci y x s CAS P 进 / 借位入 Ci R 4 R 3 R 2 R 1 R 0 y p = 0 时,CAS 作为全加器单元 p = 1 时, 输入 y 被取反,CAS 作为全减器单元

64 定点运算部件 综合考虑各类定点运算算法后, 发现 : 所有运算都可通过 加 和 移位 操作实现以一个或多个 ALU( 或加法器 ) 为核心, 加上移位器和存放中间临时结果的若干寄存器, 在相应控制逻辑的控制下, 可以实现各种运算 运算部件通常指 ALU 移位器移位器 寄存器组, 加上用于数据选择的多路选择器和实现数据传送的总线等构成的一个运算数据通路 可用专门运算器芯片实现 ( 如 :4 位运算器芯片 AM2901) 可用若干芯片级联实现 ( 如 4 个 AM2901 构成 16 位运算器 ) 现代计算机把运算数据通路和控制器都做在 CPU 中, 为实现高级流水线,CPU 中有多个运算部件, 通常称为 功能部件 或 执行部件 运算器 (Operate Unit) 运算部件 (Operate Unit) 功能部件 (Function Unit) 执行部件 (Execution Unit) 和 数据通路 (DataPath) 的含义基本上一样, 只是强调的侧面不同 SKIP

65 定点运算器芯片举例 -AM2901A 问题芯片框图 : 如何用 如何用 AM2901A 芯片实现乘 / 除运算? A0-3 LA GRS LB B0-3 通用寄存器组 (General Register Set----GRS) DA0-3 MUX MUX DB0-3 G*/N P*/O Cn+4 ALU C0 SIO3 QIO3 ALU Shifter Q Shifter SIO0 QIO0 I0-8 ZERO CU Z 控制信号 Y Q ( 乘商 R) 问题 : 如何级联? 两个移位器如何连接?

66 AM2901A 的功能和结构 核心是 4 位 ALU( 含移位器 ), 可实现 A+B A B B A 和 与 或 异或 等 进位入 C0 进位出 Cn+4 组进位传递 / 溢出 P*/O 组进位生成 / 符号 G*/N - 串行级联时,C0 和 Cn+4 用来串行进位传递 - 多级级联时, 后两个信号用作组进位传递信号 P* 和组进位生成信号 G* ALU 的操作数来自主存或寄存器,B 输入端还可以是 Q 寄存器 4 位双口 GRS(16 个 ), 一个写入口 两个读口 A 和 B A 0 A 3 为读口 A 的编号,B 0 B 3 为写口或读口 B 的编号 A 和 B 口可同时读出, 分别 LA 和 LB 送到多路选择器 MUX 的输入端一个 Q 寄存器和 Q 移位寄存器, 主要用于实现乘 / 除运算 乘法的部分积和除法的中间余数都是双倍字长, 需放到两个单倍字长寄存器中, 并对其同时串行左移 ( 除法 ) 或右移 ( 乘法 ) Q 寄存器就是乘数寄存器或商寄存器 因此, 也被称为 Q 乘商寄存器 ALU 移位器和 Q 移位器一起进行左移或右移, 移位后,ALU 移位器内容送 ALU 继续进行下次运算, 而 Q 移位器内容送 Q 乘商寄存器 将 ALU 的结果进行判 0 后可通过 Z 输出端将 零 标志信息输出, ALU MUX 移位器等的控制信号来自 CCU, 通过对指令操作码 I 0 -I 8 译码, 得到控制信号 BACK

67 AM2901A 的功能和结构 思考题 : 如何用 AM2901A 芯片实现乘 / 除运算? 1 R0 被预置为 0 / 被除数高位,Q 寄存器被预置为 0 / 被除数低位,R1 被预置为被乘数 / 除数 2 控制 ALU 执行 加 或 减, 并使 ALU 移位器和 Q 移位器同时 右移 / 左移 ( 移位后 ALU 移位器中是高位部分积 / 中间余数,Q 移位器中是低位部分积 / 中间余数 ) 3 ALU 移位器送 ALU 的 A 端,Q 移位器送 Q 寄存器后, 再送回 Q 移位器 4 反复执行第 2 3 两个步骤, 直到得到所有乘积位或商 BACK

68 MIPS 中的乘 除运算处理 指令 : mult,multu;div,divu MIPS 中有一对 32 位寄存器 Hi & Lo ( 相当于 Q 乘商寄存器 ) 乘法和除法运算的硬件相同 : 仅需做加 减和 64 位寄存器的左 / 右移位 Hi 和 Lo 结合起来实现 64 位寄存器 - 乘法 : Hi 中存放高 32 位积, Lo 中存放低 32 位积 - 除法 :Hi 中存放 remainder, Lo 中存放 quotient mflo/mfhi 指令用来把 Lo/Hi 中的 32 位数据取到通用寄存器 两种乘法指令都忽略 overflow, 而由软件自行处理溢出问题 : 如何判断溢出? 软件通过 mfhi 指令取出 Hi 寄存器来判断是否溢出 溢出判断规则 : Hi 中为以下数值时不溢出, 否则溢出 - 无符号数乘指令 (multu) 时 : 全 0 - 带符号数乘 (mult ) 时 : Lo 中的符号 MIPS 指令不处理 除数为 0, 由软件自行处理

69 十进制数的加减运算 有的机器有十进制加减法指令, 用于对 BCD 码进行加减运算 所以这些机器中必须要有相应的十进制加减运算逻辑 以 NBCD 码 (8421 码 ) 为例, 讨论十进制整数的加减运算 一般规定数符在最高位 1100: 正,1101: 负或 0: 正, 1: 负例如 : 或 符号和数值部分分开处理!

70 十进制加法运算举例 例 =56 例 = 例 = 低位有进位, 则 进到高位, 同时 该低位 +6 校正 (1110) 2 >9 需 +6 校正问题 : 本位和在什么范围内需 +6 校正? 结果 <=9 时, 不需校正 ; 大于 9 或有进位时, 需 +6 校正 最高位有进位时, 发生溢出 大于 9:1010,1011,..,1111 有进位 :10000,10001,10010 和 最大为 19: 2x9+1=19, 范围为 10~19

71 一位十进制加法器 当结果在 10~19 之间时, 需校正 ( 最大可能 :2x9+1=19) 即: 1x1x 或 11xx 或有进位 (C4*=1 ) 所以, 校正逻辑表达式 : C4 C=C4*+S3*S1*+S3*S2* S3 S2 S1 S0 HA+ FA+ FA+ HA C0 C C4* S3* S2* S1* S0* FA+ FA+ FA+ HA + A3 B3 A2 B2 A1 B1 A0 B0

72 n 位十进制加法器 n 个一位十进制加法器 = 一个 n 位十进制串行加法器

73 十进制减法运算 方法 : 加补码 :N 1 -N 2 =N 1 +(10 n -N 2 ) (mod 10 n ) 十进制数的补码求法 : 每位求反, 末位加 1 一位十进制数 (NBCD 码 ) 求反的方法, 有 : 对各二进位求反, 再 +10 先 +6, 再各位求反 直接用求反电路 只要在加法器基础上增加求补逻辑和最终结果的修正逻辑 例 :[7] 反 = = = 0010 = 2 = = 1101 = 0010 = 2

74 十进制减法运算举例 例 =184 例 =-184 加补码 : = =-184(mod 10 3 ) 进位为 1, 表示被减数大于减数, 结果为正 无进位, 表示差值为负数, 故应将结果取补 取补 减法运算肯定不会溢出!

75 小结 逻辑运算 移位运算移位运算 扩展运算等电路简单主要考虑算术运算 定点运算涉及的对象无符号数 ; 带符号整数 ( 补码 ); 原码小数 ; 移码整数定点运算 :(ALU 实现基本算术和逻辑运算,ALU+ 移位器实现其他运算 ) 补码加 / 减 : 符号位和数值位一起运算, 减法用加法实现 同号相加时可能溢出原码加 / 减 : 符号位和数值位分开运算, 用于浮点数尾数加 / 减运算移码加减 : 移码的和 差等于和差等于和 差的补码差的补码, 用于浮点数阶码加 / 减运算

76 小结 乘法运算 : 无符号数乘法 : 加 + 右移 原码 ( 一位 / 两位 ) 乘法 : 符号和数值分开运算, 数值部分用无符号数乘法实现, 用于浮点数尾数乘法运算 补码 ( 一位 / 两位 ) 乘法 : 符号和数值一起运算, 采用 Booth 算法 快速乘法器 : 流水化乘法器 阵列乘法器除法运算 : 无符号数除法 : 用 加 / 减 + 左移, 有恢复余数和不恢复余数两种 原码除法 : 符号和数值分开, 数值部分用无符号数除法实现, 用于浮点数尾数除法运算 补码除法 : 符号位和数值位一起 有恢复余数和不恢复余数两种有恢复余数和不恢复余数两种 快速除法器 : 很难实现流水化除法器, 可实现阵列除法器定点部件 :ALU GRS MUX Shifter Q 寄存器等,CU 控制执行十进制数加 减运算及运算部件

77 浮点数运算 主要内容 指令集中与浮点运算相关的指令 ( 以 MIPS 为例 ) 涉及到的操作数 - 单精度浮点数 - 双精度浮点数 涉及到的运算 - 算术运算 : 加 / 减 / 乘 / 除 浮点数加减运算 浮点数乘除运算 浮点数运算的精度问题

78 MIPS 浮点运算指令的总结 浮点操作数的表示 32 位单精度浮点数 / 64 位双精度浮点数 浮点数的运算 加法 / 减法 / 乘法 / 除法 问题 :IA-32 中浮点数寄存器是 80 位, 这会给 float 和 double 类型变量的运算带来什么隐患? 例子 : 将以下程序编译为 MIPS 汇编语言 Float f2c (float fahr) { return ((5.0 / 9.0) * (fahr-32.0)); } 假设变量 fahr 存放在 $f12 中, 返 回结果存放在 $f0 中 三个常数存放在通过 $gp 能访问到 的存储单元中 f2c : lwcl $f16, const5($gp) lwcl $f18, const9($gp) div.s $f16, $f16, $f18 lwcl $f18, const32($gp) sub.s $f12, $f12, $f18 mul.s $f0, $f16, $f12 jr $ra

79 有关 Floating-point number 的问题 实现一套浮点数运算指令, 要解决的问题有 : Issues: Representation( 表示 ): Normalized form ( 规格化形式 ) 和 Denormalized form 单精度格式和双精度格式 Range and Precision ( 表数范围和精度 ) Arithmetic (+, -, *, / ) Rounding( 舍入 ) Exceptions (e.g., divide by zero, overflow, underflow) ( 异常处理 : 如除数为 0, 上溢, 下溢等 ) Errors ( 误差 ) 与精度控制

80 浮点数运算及结果 设两个规格化浮点数分别为 A=Ma. 2 Ea B=Mb. 2 Eb, 则 : A + B =(Ma + Mb. 2 -(Ea-Eb) ). 2 Ea ( 假设 Ea>=Eb ) A*B =(Ma * Mb). 2 Ea+Eb A/B =(Ma / Mb). 2 Ea-Eb 上述运算结果可能出现以下几种情况 : SP 最大指数为多少? 127! 阶码上溢 : 一个正指数超过了最大允许值 = + /- / 溢出阶码下溢 : 一个负指数超过了最小允许值 = +0/-0 SP 最小指数为多少? -126! 尾数溢出 : 最高有效位有进位 = 右规尾数溢出, 结果不一定溢出非规格化尾数 : 数值部分高位为 0 = 左规右规或对阶时, 右段有效位丢失 = 尾数舍入运算过程中添加保护位 IEEE 建议实现时为每种异常情况异常情况提供一个提供一个自陷允许位自陷允许位 若某异常对应的位为 1, 则发生相应异常时, 就调用一个特定的异常处理程序执行

81 IEEE754 标准规定的五种异常情况 1 无效运算 ( 无意义 ) 运算时有一个数是非有限数, 如 : 加 / 减 0 x / 等 结果无效, 如 : 源操作数是 NaN 0/0 x REM 0 REM y 等 2 除以 0( 即 : 无穷大 ) 3 数太大 ( 阶码上溢 ): 对于 SP, 指阶码 E > ( 指数大于 127) 4 数太小 ( 阶码下溢 ) : 对于 SP, 指阶码 E < ( 指数小于 -126 ) 5 结果不精确 ( 舍入时引起 ), 例如 1/3,1/10 等不能精确表示成浮点数上述情况硬件可以捕捉到, 因此这些异常可设定让硬件处理, 也可设定让软件处理 让硬件处理时, 称为硬件陷阱 注 : 硬件陷阱 : 事先设定好是否要进行硬件处理 ( 即挖一个陷阱 ), 当出现相应异常时, 就由硬件自动进行相应的异常处理 ( 掉入陷阱 )

82 浮点数加 / 减运算 十进制科学计数法的加法例子 其计算过程为 : = =( ) 10 5 = = 进行尾数加减运算前, 必须 对阶! 最后还要考虑舍入计算机内部的二进制运算也一样! 对阶 操作 : 目的是使两数阶码相等 小阶向大阶看齐, 阶小的那个数的尾数右移, 右移位数等于两个阶码差的绝对值 IEEE 754 尾数右移时, 要将隐含的 1 移到小数部分, 高位补 0, 移出的低位保留到特定的 附加位 上

83 浮点数加 / 减运算 - 对阶 问题 : 如何对阶? 通过计算 [ E] 补来判断两数的阶差 : [ E] 补 = [Ex Ey] 补 = [Ex] 移 + [ [Ey] 移 ] 补 (mod 2 n ) 问题 : 在 E 为何值时无法根据 [ E] 补来判断阶差? 溢出时! 例如,4 位移码,Ex=7,Ey=-7, 则 [ E] 补 = =1110, E<0, 错! 问题 : 对 IEEE754 SP 格式来说, E 大于多少时结果就等于阶大的那个数? 24! 1.xx x xx 01xx x( x( 右移 24 位后, 尾数变为 0) 问题 :IEEE754 SP 格式的偏置常数是 127, 这会不会影响阶码运算电路的复杂度? 对计算 [Ex Ey] 补 (mod 2 n ) 没有影响 [ E] 补 = 256+Ex Ey= Ex (127+Ey) = [Ex] 移 [Ey] 移 = [Ex] 移 +[ [Ey] 移 ] 补 (mod 256) 但 [Ex+Ey] 移和 [Ex Ey] 移的计算会变复杂! 浮点乘除运算涉及之

84 浮点数加减法基本要点 ( 假定 :Xm Ym 分别是 X 和 Y 的尾数, Xe 和 Ye 分别是 X 和 Y 的阶码 ) (1) 求阶差 : e=ye Xe ( 假定 Ye > Xe, 则结果的阶码为 Ye) (2) 对阶 : 将 Xm 右移 e 位, 尾数变为 Xm 2 Xe-Ye ( 保留右移部分 : 附加位 ) (3) 尾数加减 : Xm 2 Xe-Ye ± Ym (4) 规格化 : 当尾数高位为 0, 则需左规 : 尾数左移一次, 阶码减 1, 直到 MSB 为 1 每次阶码减 1 后要判断阶码是否下溢 ( 比最小可表示的阶码还要小 ) 当尾数最高位有进位, 需右规 : 尾数右移一次, 阶码加 1, 直到 MSB 为 1 每次阶码加 1 后要判断阶码是否上溢 ( 比最大可表示的阶码还要大 ) 阶码溢出异常处理 : 阶码上溢, 则结果溢出 ; 阶码下溢, 则结果为 0 (5) 如果尾数比规定位数长, 则需考虑舍入 ( 有多种舍入方式 ) (6) 若尾数是 0, 则需要将阶码也置 0 为什么? 尾数为 0 说明结果应该为 0, 即 : 阶码和尾数为全 0

85 浮点数加法运算举例 Example: 用二进制形式计算 0.5 +( ) =? 解 :0.5 = x 2-1, = x 2-2 对阶 : x x 2-1 加减 : x 2-1 +( x 2-1 ) = x 2-1 规格化 : x x 2 4 判溢出 : 无结果为 : x 2 4 = = 1/16 = 问题 : 为何 IEEE 754 加减运算右规时最多只需一次? 因为即使是两个最大的尾数相加, 得到的和的尾数也不会达到 4, 故尾数的整数部分最多有两位, 保留一个隐含的 1 后, 最多只有一位被右移到小数部分

86 IEEE 754 浮点数加法运算 在计算机内部执行上述运算时, 必须解决哪些问题? (1) 如何表示? 用 IEEE754 标准! (2) 如何判断阶码的大小? 求 [ΔE] 补 =? (3) 对阶后尾数的隐含位如何处理? (4) 如何进行尾数加减? (5) 何时需要规格化, 如何规格化? (6) 如何舍入? (7) 如何判断溢出? 右移到数值部分, 高位补 0, 保留移出低位部分 隐藏位还原后, 按原码进行加减运算, 附加位一起运算 ±1x.xx x 形式时, 则右规 : 尾数右移 1 位, 阶码加 1 ± x x 形式时, 则左规 : 尾数左移 k 位, 阶码减 k 最终须把附加位去掉, 此时需考虑舍入 (IEEE754 有四种舍入方式 ) 若最终阶码为全 1, 则上溢 ; 若尾数为全 0, 则下溢

87 IEEE 754 浮点数加法运算举例 已知 x=0.5, y= , 求 x+y=? ( 用 IEEE754 标准单精度格式计算 ) 解 : x=0.5=1/2=( )2=( )2x2-1 y= =( )2=( )2x2-2 [x] 浮 = ,00 0 [y] 浮 = ,110 0 对阶 : [ΔE] 补 = = ,ΔE=1 故对 y 进行对阶 :[y] 浮 = ( 高位补隐藏位 ) 尾数相加 : ( ) = ( 原码加法, 最左边一位为符号位 ) 左规 : +( )2x2-1 =+(1.00 0)2x2-4 ( 阶码减 3, 实际上是加了三次 ) [x+y] 浮 = x+y=(1.0)2x2-4 =1/16=0.0625

88 S x 浮点加 / 减法器 E x M x S y E y M y 小 ALU 阶码相减 阶 1 差 2 3 控制逻辑 4 右 移 阶小的数的尾数右移 大 ALU 尾数加 / 减 8 6 阶码增 / 减 7 5 左移或右移 规格化 9 舍 入 舍入 S b E b M b 可用流水线方式实现!

89 浮点数乘 / 除法基本要点 浮点数乘法 :A*B =(Ma * Mb). 2 Ea+Eb 浮点数除法 :A/B =(Ma / Mb). 2 Ea-Eb 浮点数尾数采用原码乘 / 除运算 浮点数乘 / 除法步骤 (Xm Ym 分别是 X 和 Y 的尾数, Xe 和 Ye 分别是 X 和 Y 的阶码 ) (1) 求阶 : Xe + Ye (2) 尾数相乘除 : Xm */Ym ( 两个形为 1.xxx 的数相乘 / 除 ) (3) 两数符号相同, 结果为正 ; 两数符号相异, 结果为负 ; (4) 当尾数高位为 0, 需左规 ; 当尾数最高位有进位, 需右规 (5) 如果尾数比规定的长, 则需考虑舍入 (6) 若尾数是 0, 则需要将指数也置 0 (7) 阶码溢出判断问题 1: 乘法运算结果最多左规几次? 最多右规几次? 问题 2: 除法呢? 不需左规! 最多右规 1 次! 左规次数不定! 不需右规!

90 求阶码的和 差 设 Ex 和 Ey 分别是两个操作数的阶码,Eb 是结果的阶码, 则 : 阶码加法公式为 : Eb Ex+Ey+129 ( mod 2 8 ) [E1+ E2] 移 = E1+ E2 = E E2 127 = [E1] 移 + [E2] 移 127 = [E1] 移 + [E2] 移 +[ 127] 补 = [E1] 移 + [E2] 移 B( mod 2 8 ) 阶码减法公式为 : Eb Ex+[ Ey] 补 +127 ( mod 2 8 ) [E1 E2] 移 = E1 E2 = 127+E1 (127+E2)+127 = [E1] 移 [E2] 移 +127 = [E1] 移 +[ [E2] 移 ] 补 B( mod 2 8 )

91 举例 设 Ex 和 Ey 分别是两个操作数的阶码,Eb 是结果的阶码例 : 若两个阶码分别为 10 和 -5, 求 10+(-5) 和 10-(-5) 的移码 解 :Ex = =137= B Ey = 127+ ( 5) = 122 = B [ Ey ] 补 = B 将 Ex 和 Ey 代入上述公式, 得 : Eb = Ex+Ey +129 = = B = 132 (mod 2 8 ) 其阶码的和为 = 5, 正好等于 10 + ( 5) = 5 Eb = Ex+[ Ey] 补 +127 = = B = 142 (mod 2 8 ) 其阶码的差为 = 15, 正好等于 10 ( 5) = 15 BACK

92 Extra Bits( 附加位 ) "Floating Point numbers are like piles of sand; every time you move one you lose a little sand, but you pick up a little dirt. 浮点数就像一堆沙, 每动一次就会失去一点 沙, 并捡回一点 脏 如何才能使失去的 沙 和捡回的 脏 都尽量少呢? 加多少附加位才合适? Add/Sub: 无法给出准确的答案! 在后面加附加位! 1.xxxxx 1.xxxxx 1.xxxxx 1.xxxxxxxx + 1.xxxxx 0.001xxxxx 0.01xxxxx -1.xxxxxxxx 1x.xxxxy 1.xxxxxyyy 1x.xxxxyyy 0.0 0xxxx IEEE754 规定 : 中间结果须在右边加 2 个附加位 (guard & round) Guard bit( 保护位 ): 在 significand 右边的位 Rounding bit( 舍入位 ): 在保护位右边的位 BACK 附加位的作用 : 用以保护对阶时右移的位或运算的中间结果 附加位的处理 : 1 左规时被移到 significand 中 ; 2 作为舍入的依据

93 Rounding Digits( 舍入位 ) 举例 : 十进制数, 最终有效位数为 3, 假定采用两位附加位 问题 : 若没有舍入位, 采用就近舍入到偶数, 则结果是什么? 结果为 2.36! 精度没有 2.37 高! * * * 10 IEEE Standard: four rounding modes( 用图说明 ) round to nearest (default) round towards plus infinity (always round up) round towards minus infinity (always round down) round towards 0 注 :ULP=units in round to nearest: 简称为就近舍入到偶数 the last place. round digit < 1/2 then truncate ( 截取 ) > 1/2 then round up (add 1 to ULP) = 1/2 then round to nearest even digit 可以证明默认方式得到的平均误差最小 2 2 2

94 IEEE 754 的舍入方式的说明 IEEE 754 的舍入方式 0 Z1 Z Z2 0 ( Z1 和 Z2 分别是结果 Z 的最近可表示的左 右数 ) (1) 就近舍入 : 舍入为最近可表示的数 非中间值 :0 舍 1 入 ; 中间值 : 强迫结果为偶数 - 慢 例 : ; ; ; ; (2) 朝 + 方向舍入 : 舍入为 Z2( 正向舍入 ) (3) 朝 - 方向舍入 : 舍入为 Z1( 负向舍入 ) (4) 朝 0 方向舍入 : 截去 正数 : 取 Z1; 负数 : 取 Z2 如 : 附加位为 01: 舍 11: 入 10:( 强迫结果为偶数 )

95 IEEE 754 的舍入方式的说明 IEEE 754 通过在舍入位后再引入 粘位 sticky bit 增强精度加减运算对阶过程中, 若阶码较小的数的尾数右移时, 舍入位之后有非 0 数, 则可设置 sticky bit 举例 : 1.24 x x 10 1 分别采用一位 二位二位 三位附加位时, 结果各是多少?( 就近舍入到偶数 ) 尾数精确结果为 , 所以分别为 : 1.24,1.24,1.25 BACK

96 溢出判断 以下情况下, 可能会导致阶码溢出 左规 ( 阶码 - 1) 时 - 左规 (- 1) 时 : 先判断阶码是否为全 0, 若是, 则直接置阶码下溢 ; 否则, 阶码减 1 后判断阶码是否为全 0, 若是, 则阶码下溢 右规 ( 阶码 +1) 时 - 右规 (+ 1) 时, 先判断阶码是否为全 1, 若是, 则直接置阶码上溢 ; 否则, 阶码加 1 后判断阶码是否为全 1, 若是, 则阶码上溢 问题 : 机器内部如何减 1? +[-1] 补 =

97 举例 以下情况下, 可能会导致阶码溢出 ( 续 ) 乘法运算求阶码的和时 - 若 Ex 和 Ey 最高位皆 1, 而 Eb 最高位是 0 或 Eb 为全 1, 则阶码上溢 - 若 Ex 和 Ey 最高位皆 0, 而 Eb 最高位是 1 或 Eb 为全 0, 则阶码下溢 除法运算求阶码的差时 - 若 Ex 的最高位是 1,Ey 的最高位是 0,Eb 的最高位是 0 或 Eb 为全 1, 则阶码上溢 - 若 Ex 的最高位是 0,Ey 的最高位是 1,Eb 的最高位是 1 或 Eb 为全 0, 则阶码下溢 例 : 若 Eb = , 则左规一次后, 结果的阶码 Eb =? 解 :Eb = Eb+[-1] 补 = = 阶码下溢! 例 : 若 Ex= ,Ey= , 则乘法运算时, 结果的阶码 Eb=? 解 :Eb = Ex+Ey+129 = = 阶码上溢!

98 实例 :PowerPC 和 80x86 中的浮点部件 PowerPC 中的浮点运算 比 MIPS 多一条浮点指令 : 乘累加指令 - 将两个操作数相乘, 再与另一个操作数相加, 作为结果操作数 - 可用一条乘累加指令代替两条 MIPS 浮点指令 - 可为中间结果多保留几位, 得到最后结果后再考虑舍入, 精度高 - 利用它来实现除法运算和平方根运算 浮点寄存器的数量多一倍 (32xSPR, 32xDPR) 80x86 中的浮点运算 采用寄存器堆栈结构 : 栈顶两个数作为操作数 寄存器堆栈的精度为 80 位 (MIPS 和 PowerPC 是 32 位或 64 位 ) 所有浮点运算都转换为 80 位扩展浮点数进行运算, 写回存储器时, 再转换位 32 位 (float) 或 64 位 (double), 有时会发生奇怪的现象 由浮点数访存指令自动完成转换 指令类型 : 访存 算术算术 比较比较 函数 ( 正弦 余弦余弦 对数等 )

99 小结 浮点运算指令 ( 以 MIPS 为参考 ) 浮点数的表示 (IEEE754 标准 ) 单精度 SP(float) 和双精度 DP(double) - 规格化数 (SP): 阶码 1~254, 尾数最高位隐含为 1-0( 阶为全 0, 尾为全 0) - ( 阶为全 1, 尾为全 0) - NaN( 阶为全 0, 尾为非 0) - 非规数 ( 阶为全 1, 尾为非 0) 浮点数加减运算 对阶 尾数加减尾数加减 规格化 ( 上溢 / 下溢处理 ) 舍入 浮点数乘除运算 求阶 尾数乘除尾数乘除 规格化 ( 上溢 / 下溢处理 ) 舍入 浮点数的精度问题 中间结果加保护位 舍入位 ( 和粘位 ) 最终进行舍入 ( 有四种舍入方式 ) - 就近 ( 中间值强迫为偶数 ) + 方向 - 方向 0 方向 - 默认为 就近 舍入方式

100 本章总结 (1) 定点数运算 : 由 ALU + 移位器实现各种定点运算 移位运算 逻辑移位 : 对无符号数进行, 左 ( 右 ) 边补 0, 低 ( 高 ) 位移出 算术移位 : 对带符号整数进行, 移位前后符号位不变, 编码不同, 方式不同 循环移位 : 最左 ( 右 ) 边位移到最低 ( 高 ) 位, 其他位左 ( 右 ) 移一位 扩展运算 零扩展 : 对无符号整数进行高位补 0 符号扩展 : 对补码整数在高位直接补符加减运算 补码加 / 减运算 : 用于整数加 / 减运算 符号位和数值位一起运算, 减法用加法实现 同号相加时, 若结果的符号不同于加数的符号, 则会发生溢出 原码加 / 减运算 : 用于浮点数尾数加 / 减运算 符号位和数值位分开运算, 同号相加, 异号相减 ; 加法直接加 ; 减法用加负数补码实现 乘法运算 : 用加法和右移实现 补码乘法 : 用于整数乘法运算 符号位和数值位一起运算符号位和数值位一起运算 采用 Booth 算法 原码乘法 : 用于浮点数尾数乘法运算 符号位和数值位分开运算符号位和数值位分开运算 数值部分用无数值部分用无符号数乘法实现 除法运算 : 用加 / 减法和左移实现 补码除法 : 用于整数除法运算 符号位和数值位一起运算符号位和数值位一起运算 原码除法 : 用于浮点数尾数除法运算 符号位和数值位分开运算符号位和数值位分开运算 数值部分用无数值部分用无符号数除法实现

101 本章总结 (2) 浮点数运算 : 由多个 ALU + 移位器实现 加减运算 - 对阶 尾数相加减尾数相加减 规格化处理规格化处理 舍入舍入 判断溢出 乘除运算 - 尾数用定点原码乘 / 除运算实现, 阶码用定点数加 / 减运算实现 溢出判断 - 当结果发生阶码上溢时, 结果发生溢出, 发生阶码下溢时, 结果为 0 精确表示运算结果 - 中间结果增设保护位 舍入位舍入位 粘位 - 最终结果舍入方式 : 就近舍入 / 正向舍入 / 负向舍入 / 截去四种方式 ALU 的实现 算术逻辑单元 ALU: 实现基本的加减运算和逻辑运算 加法运算是所有定点和浮点运算 ( 加 / 减 / 乘 / 除 ) 的基础, 加法速度至关重要 进位方式是影响加法速度的重要因素 并行进位方式能加快加法速度 通过 进位生成 和 进位传递 函数来使各进位独立 并行产生