第3章 运算器2015

1、Chapter 3Chapter 3 算术运算 Chapter 3 Arithmetic for Computers 2 算术运算算术运算 n整数运算 n加减法 n乘除法 n溢出处理 n浮点运算 n浮点表示 n操作 3.1 Introduction ALU (Arithmetic Logic Unit) Add And Or Sub Chapter 3 Arithmetic for Computers 3 And and Or operations nAnd a b And result nOr a b Or result Chapter 3 Arithmetic for Computers

2、4 Chapter 3 Arithmetic for Computers 5 InputInputOutputOutput CommentsComments abCarryInCarryOutSum 000000+0+0=00two 001010+0+1=01two 010010+1+0=01two 011100+1+1=10two 100011+0+0=01two 101101+0+1=10two 110101+1+0=10two 111111+1+1=11two baCarryInaCarryInbCarryOut Chapter 3 Arithmetic for Computers 6

3、7 1-Bit ALU That can Do Subtraction 1-Bit Full ALU Chapter 3 Arithmetic for Computers 8 InputInputOutputOutput CommentsComments abCarryInCarryOutSum 000000+0+0=00two 001010+0+1=01two 010010+1+0=01two 011100+1+1=10two 100011+0+0=01two 101101+0+1=10two 110101+1+0=10two 111111+1+1=11two CarryInbaCarryI

4、nbaCarryInbaCarryInbaSum Chapter 3 Arithmetic for Computers 9 11 Supporting Branch Instructions nWe need to be able to test if two numbers are the same 12 Supporting Set Less Than nSet less than instruction produces 1 if rs rt, and 0 otherwise nIt needs to set all but the least significant bit to 0

5、nThe least significant bit is set according to the comparison nWhich can be done using subtraction nThat is, do a subtraction, check the sign bit (bit 31). Chapter 3 Arithmetic for Computers 13 整数加法整数加法 n例子: 7 + 6 3.2 Addition and Subtraction n结果超出表示范围就会发生溢出(定义) n正数和负数相加，不会溢出 n两个正数相加 n符号位为1，表示发生溢出 n

6、两个负数相加 n符号位为0，表示发生溢出 Chapter 3 Arithmetic for Computers 14 整数减法整数减法 n减法：加上加数的负值 n例如: 7 6 = 7 + (6) +7:0000 0000 0000 0111 6:1111 1111 1111 1010 +1:0000 0000 0000 0001 n结果超出范围就会溢出 n相同符号位相减，不会溢出 n一个负数减去一个正数 n符号位为0，表示发生溢出 n一个正数减去一个负数 n符号位为1，表示发生溢出 Chapter 3 Arithmetic for Computers 15 Overflow Detectio

7、n 16 Overflow Detection nSo, we can detect the overflow by checking if the CarryIn and CarryOut of the most significant bit are different 17 Overflow nThe sign bit is correct if there is no overflow nIf there is overflow, the sign bit will be wrong and needs to be inverted 18 32-bit ALU that Support

8、s Set Less Than Final 32-Bit ALU 20 Final 32-Bit ALU nALU control lines are 1-bit Ainvert line, 1-bit Bnegate line, and 2-bit operation lines 21 ALU Symbol Chapter 3 Arithmetic for Computers 22 如何处理溢出如何处理溢出 n有些高级语言不处理异常 nMIPS： addu, addui, subu 指令不发生溢出 n其他语言 (Ada, Fortran) 溢出时会发出异常： n使用MIPS add, add

9、i, sub 指令 n溢出发生时，发生异常 n保存PC指针到EPC (Excetion Program Counter)寄 存器 n跳转到异常处理句柄 nmfc0 (move from coprocessor reg) n指令从EPC中恢复PC的值 Chapter 3 Arithmetic for Computers 23 多媒体算术运算多媒体算术运算 n图像和媒体计算一般针对8位或16位的数据 n64位地址，分区进位 n88-bit, 416-bit, or 232-bit nSIMD (单指令、多数据) n饱和操作(Saturating) n溢出时，结果保持为最大值 nE.g., 音频的剪

10、切，视频中的饱和 Chapter 3 Arithmetic for Computers 24 算术运算算术运算 n整数运算 n加减法 n乘除法 n溢出处理 n浮点运算 n浮点表示 n操作 3.1 Introduction 移位操作移位操作 逻辑移位逻辑移位 ：数码位置变化，数值：数码位置变化，数值不变不变。 1. 移位类型移位类型 算术移位算术移位 1 0 0 0 1 1 1 1 循环左移：循环左移：0 ：数码位置变化，数值：数码位置变化，数值变化变化, 符号位不变。符号位不变。 1 0 0 1 1 1 1 算术左移：算术左移：1 0 0 1 1 1 1 1 0 1 1 1 1 0 (-15)

11、 (-30) （1）单符号位）单符号位 ： 0 0111 0 1110 （2）双符号位：）双符号位： 00 1110 00 0111 2.正数补码移位规则正数补码移位规则 （3 3）移位规则）移位规则 左移左移 右移右移 右移右移 0 0111 0 0011 左移左移 左移左移 右移右移 右移右移 01 1100 00 1110 00 0111 数符不变数符不变（单：符号位不变；双：第一符号（单：符号位不变；双：第一符号 位不变）。位不变）。 空位补空位补0（右移时第二符号位移至尾数最高位）。（右移时第二符号位移至尾数最高位）。 （1）单符号位）单符号位 ： 1 1011 1 0110 （2）

12、双符号位：）双符号位： 10 1100 11 0110 3.负数补码移位规则负数补码移位规则 （3 3）移位规则）移位规则 左移左移 右移右移 右移右移 1 1011 1 1101 左移左移 右移右移 右移右移 11 0110 11 1011 数符不变数符不变（单：符号位不变；双：第一符号 （单：符号位不变；双：第一符号 位不变）。位不变）。 左移空位补左移空位补0 （第二符号位移至尾数最高位）。（第二符号位移至尾数最高位）。右移空位补右移空位补1 3.2.1.4 舍入方法舍入方法 1. 0 0舍舍1 1入（原码、补码）入（原码、补码） 0 00100原原 1 00101原原 1 11011补

13、补 2. 末位恒置末位恒置1 1（原码、补码）（原码、补码） 0 00100原原 1 11011补补 1 00101原原 0 0010原原 1 0011原原 1 1110补补 0 0011原原 1 0011原原 1 1101补补 1 0011原原 1 1101补补 例例. 保留保留4位尾数：位尾数： 例例. 保留保留4位尾数：位尾数： Chapter 3 Arithmetic for Computers 29 乘法乘法 1000 1001 1000 00000 000000 1000000 1001000 Length of product is the sum of operand leng

14、ths 乘积的位数是乘数和 被乘数之和 Multiplicand 被乘数 Multiplier乘数 Product 乘积 3.3 Multiplication Chapter 3 Arithmetic for Computers 30 乘法硬件乘法硬件 Initially 0 圆圈圈起来的是下一步要检测的位圆圈圈起来的是下一步要检测的位 迭代步骤乘数被乘数积product 0初始值0010000 00100000 0000 1 1:1积=积+被乘数00110000 00100000 0010 2：左移被乘数00110000 01000000 0010 3：右移乘数0000000 0100000

15、0 0010 2 1:1积=积+被乘数00010000 01000000 0110 2：左移被乘数00010000 10000000 0110 3：右移乘数000 00000 10000000 0110 3 1: 无操作00000000 10000000 0110 2：左移被乘数00000001 00000000 0110 3：右移乘数000 00001 00000000 0110 4 1：无操作00000001 00000000 0110 2：左移被乘数00000010 00000000 0110 3：右移乘数00000010 00000000 0110 Chapter 3 Arithmet

16、ic for Computers 32 改进后的乘法器改进后的乘法器 n操作并行: add/shift n一个时钟完成一次积:频率较低 Chapter 3 Arithmetic for Computers 33 快速乘法器快速乘法器 n使用多个加法器,成本/效率的折衷 n可以流水执行:几个加法可以同步执行（不同的阶段） Chapter 3 Arithmetic for Computers 34 MIPS Multiplication n2个32位的寄存器来保存积 nHI: 高32 bits nLO: 低32-bits n指令 nmult rs, rt / multu rs, rt n64-bi

17、t product in HI/LO nmfhi rd / mflo rd n传送 HI/LO 到 rd n可以检查HI的值来判断结果是否超过32位 nmul rd, rs, rt n低32位存入rd寄存器 Chapter 3 Arithmetic for Computers 35 除法除法 n除数判0 n除法步骤 n 除数 被除数 n商添加1, 执行减法 n否则 n商添加0，从被除数中提取下一个bit n恢复余数法 n直接执行减法，结果小于0后再把除数 加回去 n带符号位的除法 n用绝对值进行除 n根据需要调整商和余数的符号 1001 1000 1001010 -1000 10 101 10

18、10 -1000 10 n-bit 操作产生 n-bit 商和余数 商 被除数 余数 除数 3.4 Division Chapter 3 Arithmetic for Computers 36 除法器的硬件除法器的硬件 Initially dividend Initially divisor in left half Chapter 3 Arithmetic for Computers 37 改进后的除法器改进后的除法器 n一个时钟周期做一次减法 n和乘法器类似 Chapter 3 Arithmetic for Computers 38 除法除法 n有符号除法 n保持余数与被除数符号一致 除法

19、算法 数字迭代型函数型 恢复余数型不恢复余数型GoldschmidtNewton-Raphson SRT Chapter 3 Arithmetic for Computers 39 MIPS除法除法 nHI/LO寄存器存储结果 nHI: 32位余数 nLO: 32位商 n指令 ndiv rs, rt / divu rs, rt n不会溢出和除0检查 n如果需要，软件必须进行检查 n使用mfhi, mflo指令访问结果 MIPS 算术操作算术操作 Chapter 2 Instructions: Language of the Computer 40 类别类别指令指令示例示例含义含义注释注释 算术

20、 加法add $s1,$s2,$s3$s1=$s2 + $s3三操作数；检测溢出 减法sub $s1,$s2,$s3$s1=$s2 - $s3三操作数；检测溢出 立即数加法addi $s1,$s2,20$s1=$s2 + 20加常数；检测溢出 无符号加addu $s1,$s2,$s3$s1=$s2 + $s3三操作数；不检测溢出 无符号减subu $s1,$s2,$s3$s1=$s2 - $s3三操作数；不检测溢出 无符号加立即数addiu $s1,$s2,100$s1=$s2 + 100加常数；不检测溢出 从协处理器 寄存器中获得 mfc0 $s1,$epc$s1=$epc复制异常PC到专用

21、寄存器 乘法乘法multmult $s2,$s3$s2,$s3 Hi,LoHi,Lo=$s2=$s2$3$3 6464位有符号积存在位有符号积存在Hi,LoHi,Lo 无符号乘法无符号乘法multumultu $s2,$s3$s2,$s3Hi,LoHi,Lo=$s2=$s2$3$36464位无符号积存在位无符号积存在Hi,LoHi,Lo 除法除法div div $s2,$s3$s2,$s3 Lo=$s2Lo=$s2/$3/$3 Hi=$s2Hi=$s2 mod mod $3$3 HiHi= =余数余数,Lo,Lo= =商商 无符号除法无符号除法divudivu $s2,$s3$s2,$s3 L

22、o=$s2Lo=$s2/$3/$3 Hi=$s2Hi=$s2 mod mod $3$3 HiHi= =余数余数,Lo,Lo= =商商 从从HiHi中获得中获得mfhimfhi $s1$s1$s1$s1=Hi=Hi获得获得HiHi值值 从从LoLo中获得中获得mflomflo $s1$s1$s1$s1=o=o获得获得LoLo值值 数数 n3.1415926510 ( pi ) n2.7182810 ( e ) n0.00000000110 ( 纳秒 ) n1.01010-9 n3 155 760 00010 ( 一百年的秒数 ) n3.1557610109 n9 460 730 472 580.

23、810 ( 一光年的千米数 ) n9.4607347258081012 Chapter 3 Arithmetic for Computers 41 Chapter 3 Arithmetic for Computers 42 浮点数浮点数 n表达非整型的数 n可以表达很小和很大的数 n和科学计数法类似 n2.34 1056 n+0.002 104 n+987.02 109 n二进制表示 n1.xxxxxxx2 2yyyy nC语言中的类型：float和double 规格化规格化 非规格化非规格化 3.5 Floating Point Chapter 3 Arithmetic for Comput

24、ers 43 浮点数标准浮点数标准 nIEEE 754标准-1985 n消除表达的不一致性 n科学计算中的可移植性 n现在被普遍采用 n2种精度 n单精度(32-bit) n双精度 (64-bit) nIEEE- Institute of Electrical and Electrionics Engineers 电气电子工程师协会，1963年1月1日，总部美国纽约 Chapter 3 Arithmetic for Computers 44 IEEE浮点数标准格式浮点数标准格式 nS: 符号位(0 非负数, 1 负数) n有效位的规格化: 1.0 |有效位| 0.5 nGuard = 1, R

25、ound = 1, Sticky = 0 Round to even ValueFractionGRSIncr?Rounded 1281.0000000000N 1.000 151.1010000100N 1.101 171.0001000010N 1.000 191.0011000110Y 1.010 1381.0001010111Y 1.001 631.1111100111Y10.000 1.BBGRXXX Guard bit: LSB of result Round bit: 1st bit removed Sticky bit: OR of remaining bits Chapter

26、 3 Arithmetic for Computers 58 精度（精度（3.5.5） nIEEE754 定义了多种舍入控制策略 n多存储几个位 (舍入,保护，粘贴) n可以选择不同的舍入模式 n允许程序员微调计算中的行为 n不是所有的硬件都实现了IEEE754的舍入策略 n大部分语言和类库只是用缺省的策略 n是硬件复杂度、效率和市场需求的折衷 Chapter 3 Arithmetic for Computers 59 浮点加法的硬件实现浮点加法的硬件实现 n比整数复杂很多 n如果在一个时钟周期内完成，就会要求时钟 周期非常的长 n比整数运算更费时 n较慢的时钟会对所有的指令产生影响 n浮点加

27、法器通常需要花费几个时钟周期 n可以被流水化 Chapter 3 Arithmetic for Computers 60 浮点加法浮点加法 Step 1 Step 2 Step 3 Step 4 Chapter 3 Arithmetic for Computers 61 浮点乘法浮点乘法 n1. 指数相加 n2. 有效位相乘 n3. 规格化 n4. 检查上溢和下溢 n5. 舍入，如需要返回3 n6. 计算符号位 Chapter 3 Arithmetic for Computers 62 浮点乘法浮点乘法 n下面是一个4位的二进制数的例子 n1.0002 21 1.1102 22 (0.5 0.

28、4375) n1. 阶码相加 n无偏移: 1 + 2 = 3 n有偏移: (1 + 127) + (2 + 127) = 3 + 254 127 = 3 + 127 n2. 有效位相乘 n1.0002 1.1102 = 1.1102 1.1102 23 n3.规格化，同时检查上溢和下溢 n1.1102 23 无溢出，也不需规格化 n4.舍入，可能还需要进一步规格化 n1.1102 23 (no change) n5.计算符号位: +ve ve ve n1.1102 23 = 0.21875 Chapter 3 Arithmetic for Computers 63 浮点乘法浮点乘法 n下面是一

29、个4位的二进制数的例子 n1.0002 21 1.1102 22 (0.5 0.4375) n1. 阶码相加 n无偏移: 1 + 2 = 3 n有偏移: (1 + 127) + (2 + 127) = 3 + 254 127 = 3 + 127 n2. 有效位相乘 n1.0002 1.1102 = 1.1102 1.1102 23 n3.规格化，同时检查上溢和下溢 n1.1102 23 无溢出，也不需规格化 n4.舍入，可能还需要进一步规格化 n1.1102 23 (no change) n5.计算符号位: +ve ve ve n1.1102 23 = 0.21875 Chapter 3 Ar

30、ithmetic for Computers 64 浮点运算硬件浮点运算硬件 n浮点乘法和加法的硬件复杂度类似 n有效位上进行乘法而不是加法 n浮点运算通常需要的操作是 n加法, 减法, 乘法, 除法, 求倒数, 平方根 n浮点数和整数间的转换 n通常需要多个时钟周期 n很容易用流水实现 流水方式 Chapter 3 Arithmetic for Computers 66 MIPS中的浮点指令中的浮点指令 n浮点数使用协处理器 n通过ISA相连的协处理器 n独立的浮点寄存器 n32个单精度: $f0, $f1, $f31 n配对为双精度: $f0/$f1, $f2/$f3, nRelease

31、2 of MIPs ISA supports 32 64-bit FP regs n浮点指令只操作浮点寄存器 n程序通常不会在浮点寄存器上进行整数操作，或在整数 寄存器上进行浮点操作 n因此可以提供更多的寄存器，而不影响指令的长度 n浮点数读取、存储指令 nlwc1, ldc1, swc1, sdc1 ne.g., ldc1 $f8, 32($sp) Chapter 3 Arithmetic for Computers 67 MIPS中的浮点指令中的浮点指令 n单精度 nadd.s, sub.s, mul.s, div.s ne.g., add.s $f0, $f1, $f6 n双精度 nad

32、d.d, sub.d, mul.d, div.d ne.g., mul.d $f4, $f4, $f6 n比较 nc.xx.s, c.xx.d (xx is eq, lt, le, ) nSets or clears FP condition-code bit ne.g. c.lt.s $f3, $f4 n分支 nbc1t, bc1f ne.g., bc1t TargetLabel Chapter 3 Arithmetic for Computers 68 示例示例: F to C nC语言: float f2c (float fahr) return (5.0/9.0)*(fahr - 32

33、.0); nFahr变量存在$f12, $f0存结果, 常量存在全局 共享内存 n编译后的MIPS指令: f2c: lwc1 $f16, const5($gp) lwc2 $f18, const9($gp) div.s $f16, $f16, $f18 lwc1 $f18, const32($gp) sub.s $f18, $f12, $f18 mul.s $f0, $f16, $f18 jr $ra Chapter 3 Arithmetic for Computers 69 示例示例: 数组乘法数组乘法 nX = X + Y Z n都是32 32 矩阵, 64-bit 双精度 nC 语言:

34、void mm (double x, double y, double z) int i, j, k; for (i = 0; i! = 32; i = i + 1) for (j = 0; j! = 32; j = j + 1) for (k = 0; k! = 32; k = k + 1) xij = xij + yik * zkj; nx, y, z 指针存储在 $a0, $a1, $a2, i, j, k 在 $s0, $s1, $s2中 Chapter 3 Arithmetic for Computers 70 示例示例: 数组乘法数组乘法 n MIPS code: li $t1,

35、32 # $t1 = 32 (row size/loop end) li $s0, 0 # i = 0; initialize 1st for loop L1: li $s1, 0 # j = 0; restart 2nd for loop L2: li $s2, 0 # k = 0; restart 3rd for loop sll $t2, $s0, 5 # $t2 = i * 32 (size of row of x) addu $t2, $t2, $s1 # $t2 = i * size(row) + j sll $t2, $t2, 3 # $t2 = byte offset of ij addu $t2, $a0, $t2 # $t2 = byte address of xij l.d $f4, 0($t2) # $f4 = 8 bytes of xij L3: sll $t0, $s2, 5 # $t0 = k * 32 (size of row of z) addu $t0, $t0, $s1 # $t0 = k * size(row) + j sll $t0, $t0, 3 # $t0 = byte o