第三章 运算方法和运算部件

1、2021-7-1 第一讲第一讲 不同层次程序员看到的运算及不同层次程序员看到的运算及ALU 第二讲第二讲 定点数运算及其运算部件定点数运算及其运算部件 第三讲第三讲 浮点数运算及其运算部件浮点数运算及其运算部件 Ch3: Arithmetic and Logic Operate and ALU 运算方法和运算部件运算方法和运算部件 2021-7-1 第一讲：不同层次程序员看到的运算及第一讲：不同层次程序员看到的运算及ALUALU 主主 要要 内内 容容 u高级语言程序中涉及的运算（以高级语言程序中涉及的运算（以C语言为例）语言为例） 整数算术运算、浮点数算术运算整数算术运算、浮点数算术运算 按

2、位、逻辑、移位、位扩展和位截断按位、逻辑、移位、位扩展和位截断 u指令集中涉及到的运算（指令集中涉及到的运算（ 以以MIPS为例为例 ） 涉及到的定点数运算涉及到的定点数运算 - 算术运算算术运算 带符号整数运算：带符号整数运算：取负取负 / 符号扩展符号扩展 / 加加 / 减减 / 乘乘 / 除除 / 算术移位算术移位 无符号整数运算：无符号整数运算：0扩展扩展 / 加加 / 减减 / 乘乘 / 除除 - 逻辑运算逻辑运算 逻辑操作：逻辑操作：与与 / 或或 / 非非 / 移位操作：移位操作：逻辑左移逻辑左移 / 逻辑右移逻辑右移 涉及到的浮点数运算：加、减、乘、除涉及到的浮点数运算：加、减

3、、乘、除 u基本运算部件基本运算部件ALU的设计的设计 为什么房子里要有厨为什么房子里要有厨 房、卫生间、卧室？房、卫生间、卧室？ CPUCPU中需提供哪些运中需提供哪些运 算部件？算部件？WhyWhy？ 人的需要人的需要! ! 程序的需要！程序的需要！ 我们从程序对运算的需求我们从程序对运算的需求 开始分析。开始分析。 浮点数有没有移位操作浮点数有没有移位操作 和扩展操作？为什么？和扩展操作？为什么？ 2021-7-1 C语言程序中涉及的运算语言程序中涉及的运算 u算术运算（最基本的运算）算术运算（最基本的运算） 无符号数、带符号整数、浮点数的无符号数、带符号整数、浮点数的+、-、*、/ 运

4、算等运算等 u按位运算按位运算 用途用途 -对对位串位串实现实现“掩码掩码”（mask）操作或相应的其他处理）操作或相应的其他处理 （主要用于对（主要用于对多媒体数据或状态多媒体数据或状态/控制信息控制信息进行处理）进行处理） 操作操作 -按位或：按位或：“|” -按位与：按位与：“ unsigned short usi = si; int i = si; unsingned ui = usi ; si = -32768 80 00 usi = 32768 80 00 i = -32768 FF FF 80 00 ui = 32768 00 00 80 00 例例2（截断操作）：（截断操作）：

5、i和和 j是否相等？是否相等？ int i = 32768; short si = (short) i; int j = si; 不相等！不相等！ i = 32768 00 00 80 00 si = -32768 80 00 j = -32768 FF FF 80 00 原因：对原因：对i i截断时发生截断时发生 了了“溢出溢出”，即：，即： 32768截断为截断为16位数时位数时 ，因其超出，因其超出16位能表位能表 示的最大值，故无法示的最大值，故无法 截断为正确的截断为正确的16位数位数 ！ 2021-7-1 如何实现高级语言源程序中的运算？如何实现高级语言源程序中的运算？ u总结：总

6、结：C语言程序中的基本数据类型及其基本运算类型语言程序中的基本数据类型及其基本运算类型 基本数据类型基本数据类型 -无符号数、带符号整数、浮点数、位串、字符（串）无符号数、带符号整数、浮点数、位串、字符（串） 基本运算类型基本运算类型 -算术、按位、逻辑、移位、扩展和截断、匹配算术、按位、逻辑、移位、扩展和截断、匹配 u计算机如何实现高级语言程序中的运算？计算机如何实现高级语言程序中的运算？ 将各类表达式编译（转换）为指令序列将各类表达式编译（转换）为指令序列 计算机直接执行指令来完成运算计算机直接执行指令来完成运算 例：例：C语言赋值语句语言赋值语句“f = (g+h) (i+j);”中变量

7、中变量i、j、f、g、h由编译器分别由编译器分别 分配给分配给MIPS寄存器寄存器$t0$t4。寄存器。寄存器$t0$t7的编号对应的编号对应815，上述程序段对，上述程序段对 应的应的MIPS机器代码和汇编表示（机器代码和汇编表示（#后为注释）如下：后为注释）如下： 000000 01011 01100 01101 00000 100000 add $t5, $t3, $t4 # g+h 000000 01000 01001 01110 00000 100000 add $t6, $t0, $t1 # i+j 000000 01101 01110 01010 00000 100010 sub

8、 $t2, $t5, $t6 # f =(g+h)(i+j) 下面以下面以MIPSMIPS为例，看指令中会提供哪些运算？能否完全支持高级语言需求？为例，看指令中会提供哪些运算？能否完全支持高级语言需求？ 2021-7-1 MIPS定点算术运算指令定点算术运算指令 InstructionExampleMeaningComments add add $1,$2,$3$1 = $2 + $33 operands; exception possible subtractsub $1,$2,$3$1 = $2 $33 operands; exception possible add immediatea

9、ddi $1,$2,100$1 = $2 + 100+ constant; exception possible add unsignedaddu $1,$2,$3$1 = $2 + $33 operands; no exceptions subtract unsigned subu $1,$2,$3$1 = $2 $33 operands; no exceptions add imm. unsign. addiu $1,$2,100 $1 = $2 + 100+ constant; no exceptions multiply mult $2,$3Hi, Lo = $2 x $3 64-bi

10、t signed product multiply unsigned multu$2,$3Hi, Lo = $2 x $3 64-bit unsigned product divide div $2,$3Lo = $2 $3,Lo = quotient, Hi = remainder Hi = $2 mod $3 divide unsigned divu $2,$3Lo = $2 $3,Unsigned quotient for (i = 0; i = len1; i+) sum += ai; return sum; 当参数len为0时，返回值应该是0 ，但是在机器上执行时，却发生了 存储器访

11、问异常。 Why? i在EAX中，len在EDX中 EAX: 0000 0000 EDX: 0000 0000 subl 指令的执行结果是什么？ cmpl 指令的执行结果是什么？ 2021-7-1 subl $1, %edx指令的执行结果指令的执行结果 “subl $1, %edx”执行时：A=0000 0000H，B为0000 0001H，Sub=1，因此Result是32个1。 Result 加法器加法器 n n n A ZF Ci Co n B n 0 1 多路选择器多路选择器 Sub B OF 加加/ /减运算部件减运算部件 CF=Co Sub SF 当当SubSub为为1 1时，做减

12、法时，做减法 当当SubSub为为0 0时，做加法时，做加法 已知EDX中为len=0000 0000H 2021-7-1 cpml %edx,%eax指令的执行结果指令的执行结果 “cmpl %edx,%eax”执行时：A=0000 0000H，B为FFFF FFFFH ，Sub=1，因此Result是001, CF=1, ZF=0, OF=0, SF=0 Result 加法器加法器 n n n A ZF Ci Co n B n 0 1 多路选择器多路选择器 Sub B OF 加加/ /减运算部件减运算部件 CF=Co Sub SF 当当SubSub为为1 1时，做减法时，做减法 当当Sub

13、Sub为为0 0时，做加法时，做加法 已知EDX中为len-1=FFFF FFFFH EAX中为i=0000 0000H 2021-7-1 jb .L3指令的执行结果指令的执行结果 指令转移条件说明 JA/JNBE labelCF=0 AND ZF=0无符号数AB JAE/JNB labelCF=0 OR ZF=1无符号数AB JB/JNAE labelCF=1 AND ZF=0无符号数AB JBE/JNA labelCF=1 OR ZF=1无符号数AB JG/JNLE labelSF=OF AND ZF=0有符号数AB JGE/JNL labelSF=OF OR ZF=1有符号数AB JL/

14、JNGE labelSFOF AND ZF=0有符号数AB JLE/JNG labelSFOF OR ZF=1有符号数AB “cmpl %edx,%eax”执行结果是 CF=1, ZF=0, OF=0, SF=0，说明满 足条件，应转移到.L3执行！ 显然，对于每个i都满足条件，因为任何无 符号数都比32个1小，因此循环体被不断执行，最终导致数组访问越界而 发生存储器访问异常。 2021-7-1 例子：程序的机器级表示与执行例子：程序的机器级表示与执行 正确的做法是将参数len声明 为int型。 Why? len在EAX中，i在MEBP-4中 i: 0000 0000 len: 0000 00

15、00 subl 指令的执行结果是什么？ cmpl 指令的执行结果是什么？ 例： float sum (int a , int len) int i，sum = 0; for (i = 0; i = len1; i+) sum += ai; return sum; 2021-7-1 subl $1, %eax指令的执行结果指令的执行结果 “subl $1, %eax”执行时：A=0000 0000H，B为0000 0001H， Sub=1，因此Result是32个1。 Result 加法器加法器 n n n A ZF Ci Co n B n 0 1 多路选择器多路选择器 Sub B OF 加加/

16、 /减运算部件减运算部件 CF=Co Sub SF 当当SubSub为为1 1时，做减法时，做减法 当当SubSub为为0 0时，做加法时，做加法 已知EAX中为len=0000 0000H 2021-7-1 cpml -4(%ebp),%eax指令的执行结果指令的执行结果 “cmpl -4(%ebp),%eax”执行时A=FFFFFFFFH，B为00000000H， Sub=1，因此Result是111, CF=0, ZF=0, OF=0, SF=1 Result 加法器加法器 n n n A ZF Ci Co n B n 0 1 多路选择器多路选择器 Sub B OF 加加/ /减运算部件

17、减运算部件 CF=Co Sub SF 当当SubSub为为1 1时，做减法时，做减法 当当SubSub为为0 0时，做加法时，做加法 已知MEBP-4为i=00000000H EAX中为len-1=FFFF FFFFH 2021-7-1 jg .L3指令的执行结果指令的执行结果 指令转移条件说明 JA/JNBE labelCF=0 AND ZF=0无符号数AB JAE/JNB labelCF=0 OR ZF=1无符号数AB JB/JNAE labelCF=1 AND ZF=0无符号数AB JBE/JNA labelCF=1 OR ZF=1无符号数AB JG/JNLE labelSF=OF AN

18、D ZF=0有符号数AB JGE/JNL labelSF=OF OR ZF=1有符号数AB JL/JNGE labelSFOF AND ZF=0有符号数AB JLE/JNG labelSFOF OR ZF=1有符号数AB “cmpl -4(%ebp),%eax”执行结果是 CF=0, ZF=0, OF=0, SF=1 ，说 明不满足条件，应跳出循环执行，执行结果正常。 2021-7-1 原码加原码加/减运算（减运算（ （自学，不作要求）（自学，不作要求） u用于浮点数尾数运算用于浮点数尾数运算 u符号位和数值部分分开处理符号位和数值部分分开处理 u仅对数值部分进行加减运算，符号位起判断和控制作

19、用仅对数值部分进行加减运算，符号位起判断和控制作用 u规则如下：规则如下： 比较两数符号，对加法实行比较两数符号，对加法实行“同号求和，异号求差同号求和，异号求差”，对减法实行，对减法实行 “异号求和，同号求差异号求和，同号求差”。 求和：数值位相加，和的符号取被加数（被减数）的符号。若最高求和：数值位相加，和的符号取被加数（被减数）的符号。若最高 位产生进位，则结果溢出。位产生进位，则结果溢出。 求差：被加数（被减数）加上加数（减数）的补码。求差：被加数（被减数）加上加数（减数）的补码。 -最高数值位产生进位表明加法结果为正，所得数值位正确。最高数值位产生进位表明加法结果为正，所得数值位正确

20、。 -最高数值位没产生进位表明加法结果为负，得到的是数值位的补最高数值位没产生进位表明加法结果为负，得到的是数值位的补 码形式，需对结果求补，还原为绝对值形式的数值位。码形式，需对结果求补，还原为绝对值形式的数值位。 差的符号位：差的符号位：a)a)情况下，符号位取被加数（被减数）的符号；情况下，符号位取被加数（被减数）的符号； b)b)情况下，符号位为被加数（被减数）的符号取反。情况下，符号位为被加数（被减数）的符号取反。 2021-7-1 原码加原码加/减运算（自学，不作要求）减运算（自学，不作要求） 例例1：已知：已知 X原 原 = 1.0011， ，Y原 原 = 1.1010，要求计算

21、 ，要求计算X+Y原 原 解：由原码加减运算规则知：同号相加，则求和，和的符号同被加数符号。解：由原码加减运算规则知：同号相加，则求和，和的符号同被加数符号。 所以：和的数值位为：所以：和的数值位为：0011 + 1010 = 1101 （ALU中无符号数相加）中无符号数相加） 和的符号位为：和的符号位为：1 X+Y原 原 = 1.1101 例例2 ：已知：已知 X原 原 = 1.0011， ，Y原 原 = 1.1010，要求计算 ，要求计算XY原 原 解：由原码加减运算规则知：同号相减，则求差（补码减法）解：由原码加减运算规则知：同号相减，则求差（补码减法） 差的数值位为：差的数值位为：00

22、11+(1010)求补 求补 = 0011 + 0110 = 1001 最高数值位没有产生进位，表明加法结果为负，需对最高数值位没有产生进位，表明加法结果为负，需对1001求补，还求补，还 原为绝对值形式的数值位。即：原为绝对值形式的数值位。即：(1001)补 补= 0111 差的符号位为差的符号位为X原 原的符号位取反，即： 的符号位取反，即：0 XY原 原 = 0.0111 思考题：如何设计一个基于加法器的原码加思考题：如何设计一个基于加法器的原码加/减法器？减法器？ 求和：直接加，有进位则溢出，符号同被求和：直接加，有进位则溢出，符号同被 求差：加补码，不会溢出，符号分情况求差：加补码，

23、不会溢出，符号分情况 2021-7-1 移码加移码加/减运算（自学，不作要求）减运算（自学，不作要求） u用于浮点数阶码运算用于浮点数阶码运算 u符号位和数值部分可以一起处理符号位和数值部分可以一起处理 u运算公式运算公式（假定在一个（假定在一个n位位ALU中进行加法运算）中进行加法运算） E1移 移+E2移移=2n-1+E1+2n-1+E2=2n+E1+E2=E1+E2补补 （ （mod 2n） E1移 移E2移移=E1移移+E2移移补补=2n-1+E1+2nE2移移 =2n-1+E1+2n2n-1E2 = 2n+E1E2 = E1E2补 补 （ （mod 2n） 结论：移码的和、差等于和、

24、差的补码！结论：移码的和、差等于和、差的补码！ u运算规则运算规则 加法：直接将加法：直接将E1移 移和 和E2移 移进行模 进行模2n加，然后对结果的符号取反。加，然后对结果的符号取反。 减法：先将减数减法：先将减数E2移 移求补（各位取反，末位加 求补（各位取反，末位加1），然后再与被减），然后再与被减 数数 E1移 移进行模 进行模2n相加，最后对结果的符号取反。相加，最后对结果的符号取反。 溢出判断：进行模溢出判断：进行模2n相加时，如果两个加数的符号相同，并且与和相加时，如果两个加数的符号相同，并且与和 数的符号也相同，则发生溢出。数的符号也相同，则发生溢出。 补码和移码的关系：符号

25、位相反、数值位相同！补码和移码的关系：符号位相反、数值位相同！ 2021-7-1 移码加移码加/减运算（不作要求）减运算（不作要求） 例例1： 用四位移码计算用四位移码计算“7+（ 6）”和和“3 + 6”的值。的值。 解：解：7移 移 = 0001 6移移= 0010 3移 移= 0101 6移 移= 1110 7移 移 + 6移移 = 0001 + 0010 = 0011 （两个加数与结果符号都为 （两个加数与结果符号都为0，溢出），溢出） 3移 移 + 6移移 = 0101 + 1110 = 0011， ， 符号取反后为符号取反后为 1011，其真值为，其真值为+3 问题：问题：7+(6

26、)移 移=? 3+(6)移移 =？ ？ 例例2： 用四位移码计算用四位移码计算“7 （ 6）”和和“3 5”的值。的值。 解：解：7移 移 = 0001 6移移= 0010 3移 移= 0101 5移 移= 1101 7移 移 6移移 = 0001 + 1110 = 1111， ， 符号取反后为符号取反后为 0111，其真值为，其真值为1。 3移 移 5移移 = 0101 + 0011 = 1000，符号取反后为 ，符号取反后为 0000，其真值为，其真值为 8。 思考题：如何设计一个基于加法器的移码加思考题：如何设计一个基于加法器的移码加/减法器？减法器？ 在补码加在补码加/减法器结果的最高

27、位（减法器结果的最高位（MSB）加一个反相器！）加一个反相器！ 2021-7-1 无符号数的乘法运算无符号数的乘法运算 uPaper and pencil example: Multiplicand 1000 Multiplier x 1001 1000 0000 0000 1000 Product(积积) 0.1001000 假定：假定：X原 原=x0.x1 xn，Y原 原=y0.y1 yn ，求，求xY原原 数值部分数值部分 z1z2n = (0.x1xn ) (0. y1yn) (小数点位置约定，不区分小数还是整数小数点位置约定，不区分小数还是整数) X y4 2-4 X y3 2-3

28、X y2 2-2 X y1 2-1 4 XY= (X yi2-i) i=1 整个运算过程中用到两种操作：加法整个运算过程中用到两种操作：加法 + + 左移左移 因而，可用因而，可用ALUALU和移位器来实现乘法运算和移位器来实现乘法运算 n=4 2021-7-1 无符号数的乘法运算无符号数的乘法运算 u手工乘法的特点：手工乘法的特点： 每步计算：每步计算：Xyi，若，若yi = 0，则得，则得0；若；若yi = 1，则得，则得X 把求得的各项结果把求得的各项结果X yi 逐次左移，可表示为逐次左移，可表示为X yi2-i 对中结果求和，即对中结果求和，即 (X yi2-i)，这就是两个无符号数

29、的乘积，这就是两个无符号数的乘积 u计算机内部稍作以下改进：计算机内部稍作以下改进： 每次得每次得Xyi后，与前面所得结果累加，得到后，与前面所得结果累加，得到Pi，称之为部分积。因，称之为部分积。因 为不等到最后一次求和，减少了保存各次相乘结果为不等到最后一次求和，减少了保存各次相乘结果Xyi的开销。的开销。 每次得每次得Xyi后，不将它左移与前次部分积后，不将它左移与前次部分积Pi相加，而将部分积相加，而将部分积Pi右右 移后与移后与Xyi相加。因为加法运算始终对部分积中高相加。因为加法运算始终对部分积中高n位进行。故用位进行。故用n 位加法器可实现二个位加法器可实现二个n位数相乘。位数相

30、乘。 对乘数中为对乘数中为“1”的位执行加法的位执行加法和右移，对为和右移，对为“0 0”的位只执行右移，而的位只执行右移，而 不执行加法运算。不执行加法运算。 2021-7-1 无符号乘法运算的算法推导无符号乘法运算的算法推导 u上述思想可写成如下数学推导过程：上述思想可写成如下数学推导过程： XY = X ( 0.y1 y2 yn ) = Xy12-1 +Xy22-2 + +Xyn-12-(n-1) +Xyn2-n = 2-n Xyn+ 2-(n-1) Xyn-1 + + 2-2Xy2 + 2-1Xy1 =2-1 ( 2-1 (2-12-1 (2-1 (0 + Xyn) + Xyn-1)

31、+ + Xy2 ) + Xy1) n个个2-1 u上述推导过程具有明显的递归性质，因此，无符号数乘法过程可归结为循环计上述推导过程具有明显的递归性质，因此，无符号数乘法过程可归结为循环计 算下列算式的过程：设算下列算式的过程：设P0 = 0，每步的乘积为：，每步的乘积为： P1 = 2-1 (P0+ X yn) P2 = 2-1 (P1+ X yn-1) Pn = 2-1 (Pn-1+ X y1) u 其递推公式为：其递推公式为：Pi+1 = 2-1 (Pi + Xyn-i) ( i = 0, 1, 2, 3, , n-1 ) u 最终乘积最终乘积Pn = XY 迭代过程从乘数迭代过程从乘数最

32、低位最低位yn和和P0=0开始，经开始，经n次次 “判断判断加法加法右移右移”循环，直到求出循环，直到求出Pn为止为止 。 2021-7-1 写使能写使能 控制逻辑控制逻辑 右移右移 32位位 ALU 被乘数寄存器被乘数寄存器X X 乘积寄存器乘积寄存器P 32 64 位位 32 32 32 加加 计数器计数器Cn 时钟时钟 C乘数寄存器乘数寄存器Y 32位乘法运算的硬件实现位乘法运算的硬件实现 u被乘数寄存器被乘数寄存器X：存放被乘数存放被乘数 u乘积寄存器乘积寄存器P：开始置初始部分积开始置初始部分积P0 = 0；结束时，存放的是；结束时，存放的是64位乘积的高位乘积的高32位位 u乘数寄

33、存器乘数寄存器Y：开始时置乘数；结束时，存放的是开始时置乘数；结束时，存放的是64位乘积的低位乘积的低32位位 u进位触发器进位触发器C：保存加法器的进位信号保存加法器的进位信号 u循环次数计数器循环次数计数器Cn：存放循环次数。初值存放循环次数。初值32，每循环一次，每循环一次，Cn减减1，Cn=0时结束时结束 uALU：乘法核心部件。在控制逻辑控制下，对乘法核心部件。在控制逻辑控制下，对P和和X的内容的内容“加加”，在，在“写使能写使能” 控制下运算结果被送回控制下运算结果被送回P，进位位在，进位位在C中中 每次循环都要对进位位每次循环都要对进位位C C、乘积寄存器、乘积寄存器 P P和乘

34、数寄存器实现和乘数寄存器实现同步逻辑同步逻辑“右移右移” 2021-7-1 Example：无符号整数乘法运算：无符号整数乘法运算 举例说明：若需计算举例说明：若需计算z=x*y; x、y和和z都是都是unsigned类型。类型。 设设x=1110 y=1101 应用递推公式：应用递推公式： Pi=2-1(x*yi+ Pi-1) C 乘积乘积P 乘数乘数R 0 0000 0 0000 11011101 + 1110 + 1110 0 1110 0 1110 11011101 0 0111 0 0 0111 0110110 0 0011 10 0 0011 101111 + 1110 + 111

35、0 1 0001 10 1 0001 101111 0 1000 110 0 1000 1101 1 + 1110 + 1110 1 0110 110 1 0110 1101 1 0 1011 0110 0 1011 0110 可用一个双倍字长的乘积寄可用一个双倍字长的乘积寄 存器；也可用两个单倍字长存器；也可用两个单倍字长 的寄存器。的寄存器。 部分积初始为部分积初始为0 0。 保留进位位。保留进位位。 右移时进位、部分积和剩余乘右移时进位、部分积和剩余乘 数一起进行数一起进行逻辑右移逻辑右移。 验证：验证：x=14, y=13, z=x*y=182 当当z取取4位时，结果发生溢出，因为位时

36、，结果发生溢出，因为 高高4位不为全位不为全0！ 2021-7-1 原码乘法算法原码乘法算法 u用于浮点数尾数乘运算用于浮点数尾数乘运算 u符号与数值分开处理：积符异或得到，数值用无符号乘法运算符号与数值分开处理：积符异或得到，数值用无符号乘法运算 例：设例：设x原 原=0.1110 ， ，y原 原=1.1101，计算 ，计算 xy原 原 解：数值部分用无符号数乘法算法计算：解：数值部分用无符号数乘法算法计算：11101101= 1011 0110 符号位：符号位：0 1=1，所以：，所以： xy原 原=1. 10110110 原码一位乘法：原码一位乘法：每次只取乘数的一位判断，需每次只取乘数

37、的一位判断，需n n次循环，速度慢。次循环，速度慢。 原码两位乘法：原码两位乘法：每次取乘数两位判断，只需每次取乘数两位判断，只需n/2n/2次循环，快一倍。次循环，快一倍。 u原码两位乘法递推公式：原码两位乘法递推公式： 00 ：Pi+1=2-2 Pi 01 ：Pi+1=2-2 (Pi +X) 10 ：Pi+1=2-2 (Pi +2X) 11 ：Pi+1=2-2 (Pi +3X)=2-2 (Pi +4X-X) =2-2 (Pi -X) +X yi-1 yi T操 作迭 代 公 式 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 0 T +X 0

38、 T +X 0 T +2X 0 T +2X 0 T X 1 T X 1 T 1 T 2-2 (Pi ) 2-2 (Pi + X) 2-2 (Pi + X) 2-2 (Pi + 2X) 2-2 (Pi + 2X) 2-2 (Pi X) 2-2 (Pi X) 2-2 (Pi ) T T触发器用来记录下次是否要执行触发器用来记录下次是否要执行“+X+X” “X X”运算用运算用“+-X+-X补 补” ”实现！实现！ 3X3X时，本次时，本次-X-X，下次，下次+X+X！ 部分积右移两位，相当于部分积右移两位，相当于4X4X P.94 表表3.3 2021-7-1 原码两位乘法举例（自学，不作要求）原

39、码两位乘法举例（自学，不作要求） 已知已知 X原 原=0.111001， ， Y原 原= 0.100111，用原码两位乘法计算 ，用原码两位乘法计算XY原 原 解：解： 先用无符号数乘法计算先用无符号数乘法计算111001100111，原码两位乘法过程如下：，原码两位乘法过程如下： 若用模若用模4 4补码，补码， 则则P P和和Y Y同时右同时右 移移2 2位时，得到位时，得到 的的P3P3是负数，是负数， 这显然是错误这显然是错误 的！需要再增的！需要再增 加一位符号。加一位符号。 采用补码算术采用补码算术 右移，与一位右移，与一位 乘法不同，乘法不同， WhyWhy？ 为模为模8 8补码形

40、补码形 式式( (三位符号三位符号 位位) )，WhyWhy？ 速度快，但代价也大速度快，但代价也大 2021-7-1 补码乘法运算（自学，不作要求）补码乘法运算（自学，不作要求） 用于对什么类型数据计算？用于对什么类型数据计算？ 带符号整数！如带符号整数！如int型型 假定：假定：X补 补=xn-1xn-2 x1x0 ， Y补补=yn-1yn-2 y1y0 ，求： 求：XxY补 补=？ ？ 基于基于以下补码性质以下补码性质： Y=-yn-1.2n-1+yn-2 .2n-2+ y1 .21+ y0 .20 令：令：y-1 =0，则：，则： 当当n=32时，时，Y=-y31.231+y30 .2

41、30+ y1 .21+ y0.20 + y-1 .20 -y31.231+(y30.231-y30.230)+ +(y0.21-y0.20)+ y-1.20 (y30 -y31 ).231+(y29-y30).230+ + (y0y1).21 +(y-1-y0).20 部分积公式：部分积公式：Pi=2-1(Pi-1+ (yi-1-yi)X) Booths Algorithm推导如下：推导如下： 因为因为XxY补 补 X补补xY补补 ，故不能直接用无 ，故不能直接用无 符号数乘法计算。例如，若符号数乘法计算。例如，若x=-5,求求x*x=？ 2-32.XxY补 补= (y30 -y31 )X.2

42、-1+(y29-y30)X.2-2+ + (y0y1)X.2-31 +(y-1-y0) X.2-32 = 2-1(2-1(2-1(y-1-y0)X) + (y0y1)X) + + (y30 -y31)X) 符号与数值统一处理符号与数值统一处理 SKIP 2021-7-1 如何求补码的真值（自学，不作要求）如何求补码的真值（自学，不作要求） 根据补码各位上的根据补码各位上的“权权”，可以求出一个补码的值，可以求出一个补码的值 真值范围：真值范围： 令：令：A补 补= an-1an-2 a1a0 则：则： A= -an-1.2n-1+an-2 .2n-2+ a1 .21+ a0 .20 符号为符号

43、为0 0，则为正数，数值部分同，则为正数，数值部分同 符号为符号为1 1，则为负数，数值各位取反，末位加，则为负数，数值各位取反，末位加1 1 例如：补码例如：补码“11010110”的真值为：的真值为：-0101010=-(32+8+2)=-42 BACK 2021-7-1 Booths 算法实质（自学，不作要求）算法实质（自学，不作要求） u当前位当前位右边位右边位操作操作Example 10减被乘数减被乘数0001111000 11加加0 (不操作不操作)0001111000 01加被乘数加被乘数0001111000 00加加0 (不操作不操作) 0001111000 u在在“1串串”中

44、，第一个中，第一个1时做减法，最后一个时做减法，最后一个1做加法，其余情况只要移位。做加法，其余情况只要移位。 u最初提出这种想法是因为在最初提出这种想法是因为在Booth的机器上移位操作比加法更快！的机器上移位操作比加法更快！ 同前面算法一样，将乘积寄存器同前面算法一样，将乘积寄存器右移右移一位。一位。（这里是算术右移）（这里是算术右移） 0 1 1 1 1 0 beginning of runend of run middle of run 2021-7-1 布斯算法举例（自学，不作要求）布斯算法举例（自学，不作要求） 已知已知X补 补 = 1 101， ，Y补 补 = 0 110，计算

45、，计算XY补 补 验证：当验证：当XY取取8位时，结果位时，结果 - 0010010B = -18；为；为4位时，结果溢出！位时，结果溢出！ -X补 补 = 0011 1 1 1 1 X = -3，Y = 6，XY=-18，XY补 补应等于 应等于11101110或结果溢出或结果溢出 如何判断结如何判断结 果是否溢出？果是否溢出？ 高高4位是否全位是否全 为符号位！为符号位！ 2021-7-1 补码两位乘法（自学，不作要求）补码两位乘法（自学，不作要求） u补码两位乘可用布斯算法推导如下：补码两位乘可用布斯算法推导如下： Pi+1补 补 = 2-1 ( Pi补补 + ( yi-1 yi ) X

46、补补) Pi+2补 补 = 2-1 ( Pi+1补补 + ( yi yi+1) X补补) = 2-1 (2-1 ( Pi补 补 + ( yi-1 yi ) X补补) + ( yi yi+1) X补补) = 2-2 ( Pi补 补+ (yi-1 + yi 2yi+1) X补补) u开始置附加位开始置附加位y-1为为0，乘积寄，乘积寄 存器最高位前面添加一位附加存器最高位前面添加一位附加 符号位符号位0。 u最终的乘积高位部分在乘积寄最终的乘积高位部分在乘积寄 存器存器P中，低位部分在乘数寄中，低位部分在乘数寄 存器存器Y中。中。 u因为字长总是因为字长总是8的倍数，所以的倍数，所以 补码的位数补

47、码的位数n应该是偶数，因应该是偶数，因 此，总循环次数为此，总循环次数为n/2。 yi+1 yi yi-1操 作迭 代 公 式 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 0 +X补 +X补 +2X补 +2-X 补 +-X补 +-X补 0 2-2Pi补 2-2Pi补+X补 2-2Pi补+X补 2-2Pi补+2X补 2-2Pi补+2-X补 2-2Pi补+-X补 2-2Pi补+-X补 2-2Pi补 2021-7-1 补码两位乘法举例（自学，不作要求）补码两位乘法举例（自学，不作要求） u已知已知 X补 补 = 1 101， ， Y补 补 = 0

48、110，用补码两位乘法计算 ，用补码两位乘法计算XY补 补。 。 u解：解：X补 补= 0 011，用补码二位乘法计算 ，用补码二位乘法计算XY补 补的过程如下。 的过程如下。 Pn P Y y-1 说明说明 0 0 0 0 0 0 1 1 0 0 开始，设开始，设y-1 = 0，P0补 补 = 0 + 0 0 1 1 0 y1y0y-1 =100，+2-X补 补 0 0 1 1 0 P和和Y同时右移二位同时右移二位 0 0 0 0 1 1 0 0 1 1 得得P2补 补 + 1 1 0 1 0 y3y2y1 = 011，+2X补 补 1 1 0 1 1 P和和Y同时右移二位同时右移二位 1

49、1 1 1 0 1 1 1 0 得得P4补 补 因此因此 X Y补补=1110 1110 ，与一位补码乘法（布斯乘法）所得结果，与一位补码乘法（布斯乘法）所得结果 相同，但循环次数减少了一半。相同，但循环次数减少了一半。 验证：验证：-3 6=-18 （-10010B） 2 2 2021-7-1 快速乘法器（自学，不作要求）快速乘法器（自学，不作要求） u前面介绍的乘法部件的特点前面介绍的乘法部件的特点 通过一个通过一个ALUALU多次做多次做“加加/ /减减+ +右移右移”来实现来实现 - 一位乘法：约一位乘法：约n n次次“加加+ +右移右移” - 两位乘法：约两位乘法：约n/2n/2次次

50、“加加+ +右移右移” 所需时间随位数增多而加长，由时钟和控制电路控制所需时间随位数增多而加长，由时钟和控制电路控制 u设计快速乘法部件的必要性设计快速乘法部件的必要性 大约大约1/31/3是乘法运算是乘法运算 u快速乘法器的实现（由特定功能的组合逻辑单元构成）快速乘法器的实现（由特定功能的组合逻辑单元构成） 流水线方式流水线方式 硬件叠加方式（如：阵列乘法器）硬件叠加方式（如：阵列乘法器） 2021-7-1 流水线方式的快速乘法器（自学，不作要求流水线方式的快速乘法器（自学，不作要求 ） u为乘数的每位提供一个为乘数的每位提供一个n n位加法器位加法器 u每个加法器的两个输入端分别是：每个加

51、法器的两个输入端分别是： 本次乘数对应的位与被乘数相与的本次乘数对应的位与被乘数相与的 结果（即：结果（即：0 0或被乘数）或被乘数） 上次部分积上次部分积 u每个加法器的输出分为两部分：每个加法器的输出分为两部分： 和的最低有效位和的最低有效位(LSB)(LSB)作为本位乘积作为本位乘积 进位和高进位和高3131位的和数组成一个位的和数组成一个3232位数位数 作为本次部分积作为本次部分积 1 组合逻辑电路！组合逻辑电路！ 无需控制器控制无需控制器控制 2021-7-1 阵列乘法器的实现（自学，不作要求）阵列乘法器的实现（自学，不作要求） u手算乘法过程手算乘法过程 u阵列乘法器阵列乘法器

52、全加器全加器 被乘数被乘数X 部分积输入部分积输入 Ai Bi 进位输入进位输入进位输出进位输出 部分积输出部分积输出 B0 0 P7P6P5P4 P3P2P1 P0 B1 0 B2 0 B3 0 A3A2A1A0 0 0 00 速度仅取决速度仅取决 于逻辑门和于逻辑门和 加法器的传加法器的传 输延迟输延迟 无符号阵列乘法器无符号阵列乘法器 增加符号处理电路增加符号处理电路 、乘前及乘后求补、乘前及乘后求补 电路，即可实现带电路，即可实现带 符号数乘法器。符号数乘法器。 2021-7-1 Divide: Paper every time you move one you lose a litt

53、le sand, but you pick up a little dirt.“ “浮点数就像一堆沙，每动一次就会失去一点浮点数就像一堆沙，每动一次就会失去一点沙沙，并捡回一点，并捡回一点 脏脏 ” 如何才能使失去的如何才能使失去的“沙沙” 和捡回的和捡回的“脏脏”都尽量少呢？都尽量少呢？ 加多少附加位才合适？加多少附加位才合适？ IEEE754规定规定: 中间结果须在右边加中间结果须在右边加2个附加位个附加位 （guard 作为舍入的依据。作为舍入的依据。 BACK 在后面加附加位！在后面加附加位！ 无法给出准确的答案！无法给出准确的答案！ 2021-7-1 Rounding Digits(

54、舍入位舍入位) 举例：十进制数，最终有效位数为举例：十进制数，最终有效位数为 3，采用两位附加位（，采用两位附加位（G、R）。）。 2.3400 * 10 0.0253 * 10 2.3653 * 10 2 2 2 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 round t

55、o nearest: round digit 1/2 then round up (add 1 to ULP) = 1/2 then round to nearest even digit 可以证明默认方式得到的平均误差最小可以证明默认方式得到的平均误差最小。 注：注：ULP=units in the last place. 简称为就近舍入到偶数简称为就近舍入到偶数 问题：若没有舍入位，采用就近问题：若没有舍入位，采用就近 舍入到偶数，则结果是什么？舍入到偶数，则结果是什么？ 结果为结果为2.36！精度没有！精度没有2.37高！高！ 2021-7-1 IEEE 754的舍入方式的说明的舍入方式

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

57、结果为偶数) 例：例：1.110111 1.1110; 1.110101 1.1101; 1.110110 1.1110; 1.111110 10.0000; 2021-7-1 IEEE 754建议可通过在舍入位后再引入粘位建议可通过在舍入位后再引入粘位“ sticky bit”增强精度增强精度 加减运算对阶过程中，若阶码较小的数的尾数右移时，舍入位之后加减运算对阶过程中，若阶码较小的数的尾数右移时，舍入位之后 有非有非0数，则可设置数，则可设置sticky bit。 举例：举例： 1.24 x 104 + 5.03 x 101 分别采用一位、二位、三位附加位时，分别采用一位、二位、三位附加位

58、时， 结果各是多少？（就近舍入到偶数）结果各是多少？（就近舍入到偶数） 尾数精确结果为尾数精确结果为1.24503, 所以分别为：所以分别为： 1.24，1.24，1.25 BACK IEEE 754的舍入方式说明的舍入方式说明 2021-7-1 溢出判断溢出判断 以下情况下，可能会导致阶码溢出以下情况下，可能会导致阶码溢出 左规（阶码左规（阶码 - 1）时）时 -左规（左规（- 1）时：先判断阶码是否为全）时：先判断阶码是否为全0，若是，则直接，若是，则直接 置阶码下溢；否则，阶码减置阶码下溢；否则，阶码减1后判断阶码是否为全后判断阶码是否为全0，若，若 是，则阶码下溢。是，则阶码下溢。 右

59、规（阶码右规（阶码 +1）时）时 -右规（右规（+ 1）时，先判断阶码是否为全）时，先判断阶码是否为全1，若是，则直接，若是，则直接 置阶码上溢；否则，阶码加置阶码上溢；否则，阶码加1后判断阶码是否为全后判断阶码是否为全1，若，若 是，则阶码上溢。是，则阶码上溢。 问题：机器内部如何减问题：机器内部如何减1？ +-1补 补 = + 111 2021-7-1 举例举例 例：若例：若Eb = 0000 0001，则左规一次后，结果的阶码，则左规一次后，结果的阶码 Eb = ? 解：解：Eb = Eb+-1补 补 = 0000 0001 + 1111 1111 = 0000 0000 阶码下溢！ 阶

60、码下溢！ 例：若例：若Ex=1111 1110，Ey=1000 0000，则乘法运算时，结果的阶码，则乘法运算时，结果的阶码 Eb=? 解：解：Eb = Ex+Ey+129 = 1111 1110 + 1000 0000 + 1000 0001 = 1111 1111 阶码上溢！阶码上溢！ 以下情况下，可能会导致阶码溢出（续）以下情况下，可能会导致阶码溢出（续） 乘法运算求阶码的和时乘法运算求阶码的和时 -若若Ex和和Ey最高位皆最高位皆1，而，而Eb最高位是最高位是0或或Eb为全为全1，则阶码上溢，则阶码上溢 -若若Ex和和Ey最高位皆最高位皆0，而，而Eb最高位是最高位是1或或Eb为全为全