计算机系统组成与结构PPT第8章.ppt

计算机组成与结构,湖南大学计算机与通信学院,8-1,第 八 章 运 算 方 法,计算机组成与结构,湖南大学计算机与通信学院,8-2,本章我们详细说明几种常用数据格式的算术运算算法和它们的硬件实现。包括定点数表示及其加、减、乘、除过程和硬件实现，二十进制（或BCD）码的格式和操作。,接下来讨论一些提高算术操作性能的专用硬件，包括流水线、查找表、华莱士树。,最后介绍浮点数的格式和它们的算术操作。包括浮点数的格式，性质，以及加、减、乘、除过程和硬件实现，还有IEEE 754 浮点数标准。,执行算术和逻辑运算的指令以及微操作是任何CPU的一个必不可少的重要部分。,计算机组成与结构,湖南大学计算机与通信学院,8-3,8.1 无专门符号位表示法,本节讨论二进制数无专门符号位表示法的加、减、乘、除的基本算法以及实现这些算法的硬件。这些算法同时也是二进制数带专门符号位表示法、BCD码和浮点表示法的算术运算基础。,非负数码：表示0或一个正数。n位非负数码的数值范围为0（所有位都为0）到2n-1（所有位都为1）。,2的补码（简称补码）：既能表示正数又能表示负数。n位数的数值范围为-2n-1到2n-1-1。当最高位为1时表示负数，最高位为0时表示正数（包括0）。正数（包括0）的补码与非负数码相同，负数的补码为其绝对值的2的补码，等于它的绝对值按位取反（该数的1的补码，简称为反码），加1。,有两种常用的无专门符号位表示法：,计算机组成与结构,湖南大学计算机与通信学院,8-4,例如，求-5的4位补码表示，首先求出它的绝对值5（0101），产生反码值1010，再加1得补码1011。下表列出了8位二进制数的非负数码和补码表示的数值。,表8.1 无符号表示的数值,计算机组成与结构,湖南大学计算机与通信学院,8-5,8.1.1 加法和减法,加法直接采用二进制加法实现，硬件中通过使用一个并行加法器来实现，如下图所示。,X和Y是8位寄存器，该电路实现微操作 ADD：XX+Y。,只要结果在正常范围内（对非负数码而言为0到2n-1，对2的补码而言为-2n-1到2n-1-1），该电路就能得到正确的结果。,图8.1 微操作XX+Y的实现,计算机组成与结构,湖南大学计算机与通信学院,8-6,当结果不能表示为一个8位数值时就会导致溢出：,例如，非负数码加法255+1，即1111 1111+0000 0001，直接加得 1 0000 0000，有9位，不能存于8位寄存器中。,并行加法器产生额外的进位输出，它用来标志算术溢出。在非负数码中，这个进位能置溢出标志，它提示系统产生了溢出，所得结果不完全正确，系统应进行相应的结果修复处理或错误处理。,在补码中，判断溢出不但要检查进位输出，还要检查结果最高位的进位输入。如果这两者相等，那么不产生溢出，否则产生溢出。见下图：,计算机组成与结构,湖南大学计算机与通信学院,8-7,图8.2 补码加法的溢出产生,在（a）和（c）中最高位的进位输入和进位输出相等，不产生溢出；而在（b）和（d）中两者不等，产生溢出。,计算机组成与结构,湖南大学计算机与通信学院,8-8,减法可以转换成加法，即X Y通过执行X+（-Y）来实现。首先将Y转换成 Y的补码，再将 Y的补码与X的补码相加即可得X Y的补码：X Y补=X补+-Y补,左图给出了执行微操作SUB：XXY的一种硬件实现。,图8.3 微操作XXY的实现,计算机组成与结构,湖南大学计算机与通信学院,8-9,对于非负数码，减法的结果不会比2n-1大，但可能比0小。例如，12执行为0000 0001+1111 1110=1111 1111，即255。,图中（b）和（d）溢出，而（a）和（c）没有溢出。,图8.4 非负数码减法的溢出产生,同样，补码减法也将XY转换成X+（Y）来执行，而判断溢出的条件与补码加法相同。,此时，如果减法（通过补码加法实现）产生了进位输出0而不是1时，则发生了溢出。,计算机组成与结构,湖南大学计算机与通信学院,8-10,8.1.2 乘法,乘法可以看成加法的重复。一个数乘以n与n个该数相加的结果相同。可以用下列算法来实现乘法xy。z=0；FOR i=1 TO y DO z=z+x,这种算法不理想，原因是速度慢、计算xy的时间不确定。我们希望不论x、y取何值，执行乘法的时间相同。,x=2 7 y=2 5 3 8 1 1 3 5 5 4 6 8 3 1,考虑人工计算：,首先，27乘以乘数y 的最低位3。接着，27乘以乘数y 的次低位5，结果放在前一个积的左边一位处，因为乘数5在3的左一位上。然后，27乘以2，结果进一步左移一位。最后，将所有值加在一起。,8.1.2.1 移位相加算法（非负数码乘法）,计算机组成与结构,湖南大学计算机与通信学院,8-11,这个过程被称为移位相加乘法。首先计算每个部分积并左移到正确位置，然后再将所有的部分积相加。对这个算法稍做修改，使得硬件实现更为简单，就可得到无符号非负数码的乘法基本算法。,第一个修改是每求出一个部分积后就计算和：,x=2 7 y=2 5 3 8 1 1 3 5 1 4 3 1 计算的和 5 4 6 8 3 1 最终计算的和,因为硬件上，二输入加法器很容易实现，而三输入或多输入的加法器则变得非常复杂。,任何时候都没有多于两个数的加。,注意：每一个部分积都逐次左移一位，因此排列的位置不同。在当前和与部分积的相加中，某些位的运算不必要。,计算机组成与结构,湖南大学计算机与通信学院,8-12,第二个修改用右移当前和代替左移部分积：,x=27 y=253 81 右移一位 81 1被右移出，故不参加加法运算 135 1431 右移一位 1431 3 1被右移出，故不参加加法运算 54 6831 最后右移一位 6831,每次都是相同的三列数字进行加法。已经右移到这三列右边的数字只是简单的写下，不进行加法。,计算机组成与结构,湖南大学计算机与通信学院,8-13,若用二进制，被乘数不是乘以0就是乘以1，因此部分积不是0（X0=0）就是被乘数的值（X1=X）。,下面算法实现两个n位寄存器的值X和Y的移位相加乘法，结果保存在两个n位寄存器U和V中，其中U保存结果的高n位，V保存结果的低n位。C是一位寄存器，用来保存执行加法时的进位。,U=0；FOR i=1 TO n DO IF Y0=1 THEN CU=U+X；线性右移 CUV；循环右移 Y,计算机组成与结构,湖南大学计算机与通信学院,8-14,算法的RTL代码如下所示。注意：当i=0时，Z=1；而1，2，3是连续的状态，即算法是由状态1到2再到3的。,1：U0，in Y02：CUU+X 2：ii-1 3：shr(CUV)，cir(Y)Z3：GOTO 2 Z 3：FINISH1,表8.3列出了1311的RTL代码的执行步骤。同样初始化X=1101，Y=1011。除了在每个周期增加了满足的条件和执行的微操作外，表8.3同表8.2一样。,计算机组成与结构,湖南大学计算机与通信学院,8-15,表8.3 移位相加乘法RTL代码的执行轨迹,计算机组成与结构,湖南大学计算机与通信学院,8-16,图8.5 移位相加乘法算法的硬件实现,计算机组成与结构,湖南大学计算机与通信学院,8-17,如果不要求保存原值，则可以进一步优化算法，使硬件实现更简单。特别是如果Y值不要求保存，可将其值保存在V寄存器中，则乘法转换为UVX V。每次检查V的最低位V0，若为1，执行加法。下一步执行右移时，该位将丢弃，因为它不再需要使用。修改后的RTL代码为：1：U0，in V02：CUU+X 2：ii-1 3：shr(CUV)Z3：GOTO 2 Z 3：FINISH1,与前面的代码有两处不同：一是CUU+X的条件由Y02改为V02；二是减少了cir(Y)的操作。,除了C和U的LD信号改为V02，以及去掉了寄存器Y之外，该代码的硬件实现与图8.5的相同。,计算机组成与结构,湖南大学计算机与通信学院,8-18,移位相加乘法改进算法的硬件实现,计算机组成与结构,湖南大学计算机与通信学院,8-19,8.1.2.1 布斯算法（补码乘法）,对于无专门符号位的补码数据，上面的算法并不总能得出正确的结果。上一个例子（13 11）中，1101 和1011的补码表示分别为3和-5，它们的积应是+15；而上面的算法将得出结果1000 1111，即 113，显然是错的。原因是该算法仅能处理两个正数相乘，当有一个或两个操作数为负数时，通过执行下面的程序，上面的算法仍然可以使用：,IF 被乘数 0 THEN 被乘数-被乘数；IF 乘数 0 THEN 乘数-乘数；用非负数乘法进行乘法运算；恢复被乘数和乘数的原值；IF 被乘数和乘数中有一个为负数，并且另一个非零，THEN 结果-结果,计算机组成与结构,湖南大学计算机与通信学院,8-20,这个算法很麻烦，而booths算法比它简单。该算法直接对补码数据进行运算，不需进行正数和负数之间的转换。booths算法也检查乘数的每一位，并把当前和右移一位。不同的是，并不是乘数的每个1都执行加法；而是对于一串1的第一个1执行减法，对于一串1的最后一个1执行加法。,U=0；Y-1=0；FOR i=1 TO n DO IF Y0Y-1=10 THEN U=U X；IF Y0Y-1=01 THEN U=U+X；算术右移 UV；循环右移 Y并将Y0复制给Y-1,booths乘法UVXY，U、V、X、Y为n位值，Y-1为1位值：,计算机组成与结构,湖南大学计算机与通信学院,8-21,检查Y的一串1的关键是要保留上一次Y的最低位。如果Y的最低位Y0和最后移出的位为：10，则该1开始了一串1，执行减法；01，则该0结束了一串1，执行加法；11，则在一串1中，不做任何操作。00，则该算法既不需要加法又不需要减法。为了检查这两位，用一个1位寄存器Y-1来保存最后移出的位。它被初始化为0，以保证Y的第一串1能被检查到。如果乘数的最高位为1，则最后一个循环中不可能出现加法。,计算机组成与结构,湖南大学计算机与通信学院,8-22,该算法的RTL代码。信号START和一位寄存器FINISH用于初始化和终止算法。算法中U、V、X、Y为n位值，Y-1为一位值。循环计数器i为递减计数器，由n递减到0。1：U0，Y-1 0，in Y0Y-1 2：UU+X+1 Y0Y-1 2：UU+X 2：ii-1 3：ashr(UV)，cir(Y)，Y-1 Y0 Z3：GOTO 2 Z 3：FINISH1 注意，条件Y0Y-1对应于一串1的开始，执行减法；Y0Y-1对应于一串1的结尾，执行加法。加、减法语句可合并一起：（Y0Y-1）2：UU+（XY0）+Y0,计算机组成与结构,湖南大学计算机与通信学院,8-23,合并后的RTL代码的硬件实现如图所示。,图8.6 booths算法的硬件实现,计算机组成与结构,湖南大学计算机与通信学院,8-24,8.1.3 除法,除法也可以看成减法的重复，z=xy可以这样实现：Z0；WHILE xy DO zz1；xxy 此算法效率低、执行时间随着z的最终值的不同而改变。,可采用移位相减算法减少执行时间，例：,096 71 6827 639 437 426 11,注意第一步操作是比较除数71和被除数的前两位68。由于71大于68，故该位商0。这在计算机的除法运算中是很重要的一步，它被用来检测商是否溢出。,8.1.3.1 非负数码除法,计算机组成与结构,湖南大学计算机与通信学院,8-25,将被除数左移，使得每次相减的结果总是送到同一位置上。,096 71 6827 00 68 除以71 商0 682 取出下一位 682 左移一位 639 682 除以71 商9 0437 取出下一位 0437 左移一位 426 437 除以71 商6 11 余数,左移出的位不参加减法计算,第一步检查68是否大于等于71，这是一个溢出检测,计算机组成与结构,湖南大学计算机与通信学院,8-26,采用二进制更简单，商只可能为0或1。当被除数大于等于除数时，商1；否则商0。下面的算法实现了两个二进制值的移位相减除法。被除数在初始化时加载到UV，其中U保存高n位，V保存低n位。除数和商分别保存在n位值X和Y中。余数保存在U中。C为1位值，用来保存U的移出位。,U X THEN 产生溢出并终止算法；Y=0；C=0；FOR i=1 TO n DO 线性左移 CUV；线性左移 Y；IF CU X THEN Y0=1，U=CU X,考虑第一步就终止的情况。如1127，若n=4，则UV=0111 0000，X=0111。由于UX，均为0111，将终止算法。如果继续执行，将产生商16（1 0000）和余数0。但值1 0000不能保存在4位的Y中，产生溢出。,计算机组成与结构,湖南大学计算机与通信学院,8-27,下表列出了该算法执行14713的步骤。初始化时，U=1001，V=0011，X=1101，n=4。,表8.7 移位相减算法的执行步骤,计算机组成与结构,湖南大学计算机与通信学院,8-28,算法的RTL代码。其中X、U、V、Y为n位值，C和OVERFLOW为1位值。当i=0时，Z=1；当UX时，G=1。FINISHI置1则算法结束。1，2，3，4是连续的状态。,G 1：FINISH1，OVERFLOW1 2：Y0，C0，OVERFLOW0，in 3：shl(CUV)，shl(Y)，ii-1（C+G）4：Y0 1，UU+X+1 Z4：GOTO 3 Z 4：FINISH1,大部分的RTL语句由算法直接转换而成，注意条件 CUX等价于条件 UX（G）或（C=1），即（C+G）；补码加法：U U+X+1实现算法中的U=CU X。,1.不恢复余数算法,计算机组成与结构,湖南大学计算机与通信学院,8-29,图8.7 移位相减除法的硬件实现,计算机组成与结构,湖南大学计算机与通信学院,8-30,课堂练习：P270 习题13,改进的RTL代码：G 1：FINISH11：Y0,C0,in,OVERFLOWG2：shl(CUV),shl(Y),ii-1(C+G)3：Y01,UU+X+1Z3：goto 2Z 3：FINISH1,计算机组成与结构,湖南大学计算机与通信学院,8-31,图8.7 移位相减除法的改进硬件实现,计算机组成与结构,湖南大学计算机与通信学院,8-32,被除数初始化时保存在UV中，除数保存在X中，商保存在Y中，余数最后保存在U中。U、V、X、Y都是n位值，C是1位值。,CU=U+X+1；U=U+X，IF C=1 THEN 产生溢出并终止算法；Y=0；FOR i=1 TO n DO 线性左移 CUV；线性左移 Y；IF C=1 THEN U=U+X+1 ELSE CU=U+X+1 IF C=1 THEN Y0=1 ELSE U=U+X,第一步为CU与X的比较，判溢出,做减法（CUX）以判断CUX？（若成立，C置1）,决定商，若上商0恢复余数,2.恢复余数算法,计算机组成与结构,湖南大学计算机与通信学院,8-33,CU与X的比较。操作C U=U+X+1实际上实现了两个功能：显式的功能是减法U=U X，而隐含的功能是U和X的比较。如果U X，该操作将C置1，否则将C置0。,在（a）和（b）中，C置1，表示U X；在（c）中，C置0，表示U X。,图8.8 在计算C U=U+X+1的同时比较了U和X：（a）正结果，（b）零结果，（c）负结果,计算机组成与结构,湖南大学计算机与通信学院,8-34,恢复余数除法的算法:它采用的值与不恢复余数算法中采用的值基本相同。,恢复余数法电路是6状态机。,11：CUU+X+1；12：UU+X C 12：FINISH1，OVERFLOW1 2：Y0，OVERFLOW0，in 3：shl(CUV)，shl(Y)，ii-1 C 41：UU+X+1 C41：CUU+X+1 C 42：Y0 1 C42：UU+X Z 42：FINISH1 Z42：GOTO 3,计算机组成与结构,湖南大学计算机与通信学院,8-35,减少了产生G的比较器，但并行加法器的输入更加复杂。因为此时要求它进行两种操作U+X或U X。同时，由于有6个状态，状态计数器和译码器要稍微大一些。,图8.9 恢复余数除法的硬件实现,计算机组成与结构,湖南大学计算机与通信学院,8-36,8.1.3.2 补码相除 补码相除没有一种通用的算法。一般是通过对正负数值进行转换来实现补码相除。该算法如下所示。除法可以使用恢复余数的硬件实现或不恢复余数的硬件实现。,IF 被除数 0 THEN 被除数-被除数；IF 除数 0 THEN 除数-除数；使用恢复余数或不恢复余数的硬件实现除法运算；IF 被除数和除数中有一个为负数 THEN 结果-结果,计算机组成与结构,湖南大学计算机与通信学院,8-37,8.2 带专门符号位表示法,无专门符号位表示法中的非负数码和补码是带专门符号位表示法中的符号幅值表示法（signed_magnitude notation）和符号补码表示法（signed_twos complement notation）的基础。稍做修改，无专门符号位表示法的运算算法也可以作为带专门符号位表示法的运算算法。,8.2.1 符号幅值表示法（signed_magnitude notation）,包括两个部分：符号部分为1位，0表示正数（或0），1表示负数；幅值部分为n位，以非负数码的形式表示数的绝对值。,用XsX 表示符号幅值表示法，其中Xs为1位的符号值，X为n位幅值。,例如：+3和-3有相同的幅值3，仅仅符号不同。在二进制中，+3表示为0（符号）0011，而-3表示为1（符号）0011。,计算机组成与结构,湖南大学计算机与通信学院,8-38,8.2.1.1 加法和减法,比非负数码的要复杂。由于两个操作数均可能为正或为负，因此它们的符号和相对幅值决定了操作如何执行。,操作UsUXsXYsY，定义AS为形式上的计算操作符。AS=0表示加，=1表示减。还定义PM=XsASYs，为实际上的计算操作。Xs、AS和Ys共有8种可能的组合。下表列出这些组合及其相应的PM值，同时分别给出了当X=3，Y=5和X=5，Y=3时这8种组合的结果。,表8.11 符号幅值数据的加法和减法,PM表示实际执行是加还是减,计算机组成与结构,湖南大学计算机与通信学院,8-39,完整的RTL代码（包括PM=0和PM=1两种情况）。,PM1：UsXs，CUX+Y PM 1：CUX+Y+1，OVERFLOW0 PM2：OVERFLOWC CZPM 2：UsXs CZ PM 2：Us0 CPM 2：UsXs，UU+1 2：FINISH1,为了说明这个算法，表8.12列出了当XsX和YsY取不同值时，RTL代码的执行过程。它包括了没有产生溢出时的四种可能情况：PM=0、PM=1且X Y、PM=1且X=Y、PM=1且X Y，以及产生溢出时的两种可能情况。,计算机组成与结构,湖南大学计算机与通信学院,8-40,表8.12 符号幅值表示法的加减法举例,计算机组成与结构,湖南大学计算机与通信学院,8-41,该RTL代码的硬件实现。,图8.10 符号幅值加减法的硬件实现,计算机组成与结构,湖南大学计算机与通信学院,8-42,8.2.1.2 乘法和除法,符号幅值表示法的乘除法与非负数码的乘除法几乎完全相同，唯一不同的是它必须设置结果的符号。,对计算CUXY的非负数码移位相加乘法算法稍加修改，就可以得到下列RTL代码，它进行符号幅值数据XsX和YsY的乘法。,1：UsXsYs，VsXsYs，U0，in Y02：CUU+X 2：ii-1 3：shr(CUV)，cir(Y)Z3：GOTO 2 ZT 3：Us0，Vs0 Z 3：FINISH1,当UV=0时T=1，否则T=0。当i=0时，Z=1。,计算机组成与结构,湖南大学计算机与通信学院,8-43,符号幅值表示法的移位相加乘法硬件实现,计算机组成与结构,湖南大学计算机与通信学院,8-44,除法可采用恢复余数算法或不恢复余数算法实现。与乘法相同，它也必须考虑结果的符号。因此乘法的RTL代码中所做的修改同样适用于除法的RTL代码。修改后的除法RTL代码及电路（略）。,计算机组成与结构,湖南大学计算机与通信学院,8-45,8.2.2 符号补码表示法（signed_twos complement notation）,类似于符号幅值表示法，符号补码表示法也包括1位的符号和n位的幅值，它同样被表示为XsX。唯一不同的是其负数的幅值采用2的补码表示。,+5和3的符号补码表示分别为：0（符号）0101和1（符号）1101,符号补码表示法的幅值部分等价于无符号表示法中的补码。,为了加减两个符号补码表示的数据，我们简单地把符号位当成幅值的最高位。例如，不将+5表示为0（符号）0101，而是简单地将其看成5位的值00101；,计算机组成与结构,湖南大学计算机与通信学院,8-46,这样，可以把符号补码表示法的加减法转换为无专门符号位补码的加减法。注意要使用（n+1）位的补码。把符号位看成幅值的最高位的另一个好处是：在执行补码加减法的同时能得出结果的符号。此时的溢出判断同补码加减法的溢出判断相同，即当最高位的进位输入和进位输出不相等时产生溢出。注意此时的最高位为符号位。,乘法也可以采用相同的方式实现。一旦把符号位看成它们的相对幅值的最高位，我们就能采用booths算法实现数据的乘法。除法也可以通过类似的方法，修改无符号补码除法来实现。,计算机组成与结构,湖南大学计算机与通信学院,8-47,8.3 BCD码（binary coded decimal）,上一节介绍的带符号表示是用二进制位来表示二进制数。这种表示的存储效率最高，因为每一比特都表示一个唯一有效的值。但在某些应用中，直接使用十进制来存储和运算将更为适合。例如，一个数字钟的应用，它的输出必须总是表示为十进制数，但内部元件可以采用二进制计时。此时如能使用一序列十进制数的存储格式，将可免去进制转换的麻烦。,用来表示十进制数的最常用格式是BCD码（binary coded decimal，“以二进制编码的十进制”，简称BCD）。本节将讨论BCD码的格式，及其加、减、乘、除算法和相应的硬件实现。,计算机组成与结构,湖南大学计算机与通信学院,8-48,8.3.1 BCD码的格式,BCD码用4位等值的二进制数表示一个十进制数字。例如，0000表示0，1001表示9。BCD码中不使用大于9的4位二进制数，从1010到1111。,n位的十进制数用n组4位二进制数保存。例如，27被存为0010 0111（在二进制中，它被存为0001 1011）。,BCD码是一种带符号表示法，它的值可以为正也可以为负或0。类似于符号幅值表示法，它有两个部分：1位用于表示符号，而幅值部分保存数的绝对值。例如+27和27分别表示为0（符号）0010 0111和1（符号）0010 0111。,计算机组成与结构,湖南大学计算机与通信学院,8-49,8.3.2 加法和减法,BCD码与符号幅值表示法仅有两个不同，只要对这两个不同进行修改，就可以得到BCD码加减法的算法。,首先要改变硬件以适应BCD码的加法。若BCD码的两个数字之和大于9，要将二进制加法器产生的结果加6以得到正确的结果。图8.11显示了两个BCD数字相加产生正确BCD码结果和进位的硬件（一位BCD加法器）。,例如，5+6=0101+0110=1011（无效数字）。8+9=1000+1001=1（进位）0001，即11。,第二个修改是对补码进行修改。BCD码的补码是9的补码。该值可以通过将999 99（n个9）减去自身获得。将其加1可得到10的补码，在BCD码中，用它来表示原值的负数。,计算机组成与结构,湖南大学计算机与通信学院,8-50,图8.11 一位BCD加法器,如果Adder 1的输出S3S2S1S0是无效的BCD数字，必有S3S2=1或S3S1=1；或X+Y产生进位，此时Cout1=1。在这两种情况下，多路复用器的控制位置1，使得6（0110）与S3S2S1S0相加，从而得到正确结果。,两个数字X和Y首先加在一起，然后加0或加6产生正确的BCD码和。,计算机组成与结构,湖南大学计算机与通信学院,8-51,下图为一个BCD数的9的补码生成器。将多个该硬件相连就可以得到一个多位BCD数的9的补码生成器。,图8.12 9的补码生成器,例如，631的9的补码为999 631=368，而10的补码为368+1=369。正如二进制中2的补码用于减法或取负运算一样，10的补码在BCD码中发挥同样的作用。,计算机组成与结构,湖南大学计算机与通信学院,8-52,经过以上两个修改，二进制的符号幅值表示法的加减算法可以用于BCD码的加减法中：,使用BCD加法器代替二进制并行加法器。使用9的补码生成器产生Y（在条件PM 1下）和U（在条件CPM 2下）。由于Xs为1位，在条件CPM 2下，Xs实际上是通过反向器而不是通过9的补码生成器得出Xs。,RTL代码。,PM1：UsXs，CUX+Y PM 1：CUX+Y+1，OVERFLOW0 PM2：OVERFLOWC CZPM 2：UsXs CZ PM 2：Us0 CPM 2：UsXs，UU+1 2：FINISH1,计算机组成与结构,湖南大学计算机与通信学院,8-53,BCD加减法的硬件实现如图所示。,图8.13 BCD加减法的硬件实现,计算机组成与结构,湖南大学计算机与通信学院,8-54,8.3.2 乘法和除法（自学）,虽然BCD的乘除法与符号幅值表示法的乘除法很相似，但与BCD的加减法相比，BCD的乘除法要做更多的修改。上节介绍的BCD加法器和9的补码生成器在BCD乘除法中同样需要。,在BCD中，乘数的每一位可能为09中的任何一个数字，因此每次循环迭代最多可能要执行9次加法。因此在算法中要增加一个内循环来实现多次加法。,采用十进制移位，每次移1位BCD数字，即每次移4位。十进制右移操作记为dshr。每次循环可能执行多次加法，因此进位Cd采用1位BCD数而不是1位二进制数。,计算机组成与结构,湖南大学计算机与通信学院,8-55,根据以上修改，我们可以把二进制符号幅值表示法的移位相加乘法算法转换成等价的BCD码乘法算法。实现BCD乘法UsUVXsXYsY的RTL代码（略）。,该RTL代码的硬件实现。（略）,除法可以采用恢复余数算法和不恢复余数算法。类似乘法，这里也要增加一个内循环实现多次减法。除法的RTL代码及其硬件实现。（略）,计算机组成与结构,湖南大学计算机与通信学院,8-56,8.5 浮点数,定点数仅能表示整数或纯小数，计算机用浮点数来表示灵活的数。,8.5.1 数据格式,浮点数的格式类似于科学记数法。一个数在科学记数法中包含：符号，小数或有效值（也叫尾数）和指数（通常叫阶）。例如，数1234.5678可以表示为 1.2345678103，其中符号为负号，有效值为1.23456789，指数为3。在这个例子中采用10作为基数，计算机一般都以2为基数表示浮点数。,必须对浮点数进行规格化，即浮点数的有效值是一个没有前导0的小数。于是1234.567就只有一个有效的浮点表达：.1234567104。不能是1.234567103或1234567.10-3，也不是-.001234567106。,规格化,计算机组成与结构,湖南大学计算机与通信学院,8-57,0不能被规格化。要用一个特殊值表示0，在运算中，还要把0做为特殊情况处理。类似的，正无穷大和负无穷大也要用一个特殊值来表示，并且也需要特殊处理。,另外，非法操作，如/或对负数开平方，我们称其结果为不存在的数，记为NaN。NaN也要用一个特殊值来表示，在浮点数算法中NaN也要求特殊处理。,特殊值,浮点数格式。每个浮点数包括1位符号，定长的有效值和阶。浮点数X记为XSXFXE，其中XS表示符号，XF表示有效值，XE表示阶。例如，值1234.5678（=.12345678104）被保存为XS=1，XF=12345678，XE=4。,因为每个数据都以正常格式存储，因此它隐含表示小数点位于有效值的最高有效位的左边，并且不需要明确地表示出来。,浮点数格式,计算机组成与结构,湖南大学计算机与通信学院,8-58,阶没有专门符号位，阶值可用补码表示，但最好是用移码。阶的移码是在实际阶值上加一个偏移量，其和被保存在阶中。假设XE有四位，它可以表示从8到7的所有阶码，将实际阶值加一个偏移量8，其和保存在XE中，则最小阶值8的移码为 8+8=0 或二进制的 0000，最大阶值7的移码为7+8=15=1111。,移码,尾数用符号补码表示（连同符号位XS一起）。,二进制表示的规格化浮点数（除了0、+/-、NaN）的有效值的最高位为1，在有效值寄存器中可以不保存该位。,计算机组成与结构,湖南大学计算机与通信学院,8-59,8.5.2 数据性质,精度表示浮点数的精确性，定义为有效值的位数。若计算机规定浮点数的有效值为8位，则它的精度为8位。有效值的位数越多，CPU的精度越高，表示的数据越精确。,许多计算机中有两种浮点数格式：单精度浮点数和双精度浮点数。双精度浮点数的位数是单精度浮点数的两倍。,间距为两个相邻值的差的绝对值。其大小由阶值的大小决定。例如，浮点数：.1011 101023，它的2个相邻值为：.1011 101123和.1011 100123，间距为：.0000 000123=2-5。浮点数X的间距可以表示为2（X E precision）。,浮点数固有特性,范围由浮点数格式所能表示的最大值和最小值决定。例如，一个有8位有效值（假设首位1也保存在有效值寄存器中）和4位阶码（表示阶值 8 7）的浮点数的范围为.1111 111127.1111 111127，即 127.5+127.5。,计算机组成与结构,湖南大学计算机与通信学院,8-60,例如，某浮点数格式，有1位符号位，8位阶且偏移量为128，23位有效值（类似于IEEE 754 单精度浮点数）。则精度为23位，范围为.111 1111 1111 1111 1111 11112127.111 1111 1111 1111 1111 11112127。间距由实际的浮点数决定，对.12127，间距为2（127 23）=2104；对.1 2-128，间距为2（-128 23）=2-151。,举例,当浮点数操作所产生的结果不能存于计算机的浮点寄存器时，就发生了溢出。,对有8位有效值和4位阶（偏移量为8）的浮点数，浮点数.126 和.125相乘将得积.01211=.1210，积的阶值大于该格式所允许的最大阶值7，因此产生了溢出。,溢出和下溢,溢出可为正或为负，由溢出值的符号决定。溢出值可以处理为+/-，或NaN，或像定点数一样置溢出标志为1。,计算机组成与结构,湖南大学计算机与通信学院,8-61,当结果在0到最小正值或最小负值之间时，将产生下溢。例如，在上例格式中，执行乘法（.12-6）（.12-5），所得结果为.12-12，它在0 与最小正值.12 8之间，因此产生下溢。下溢也可以为正或为负。下溢值可以处理为0，或者设置下溢标志位。,当操作结果有效值的位数太多而不能放入CPU的寄存器中（例如，8位有效值的浮点数相乘，得到16位有效值的积），此时必须将该值进行舍入处理，使之能放入规定位数的有效值寄存器中。,就近舍入法（也称为无偏舍入法）的目标是使舍入后的结果尽可能接近实际值。例如，将值.1011 0101舍入为4位，得到值.1100。它的最大误差为+/-0.5LSB（LSB为舍入后结果的最低有效位值）。,舍入处理,计算机组成与结构,湖南大学计算机与通信学院,8-62,表8.16 不同舍入方法的比较,常见的舍入方法还有：截断法、朝+舍入法、朝-舍入法。下表给出了数值在不同的舍入方法下的舍入结果。,计算机组成与结构,湖南大学计算机与通信学院,8-63,例如，（.101123）-（.110022），有效值分别为1011和1100，二者直接相减不能得出正确结果。由于减数的阶比被减数的阶小1，它的有效值必须右移一位。本质上，这种对齐是将减数由.110022转换为.011023。只有当操作数的阶相等时，才能执行有效值的相减。,8.5.3 加法和减法,浮点数加减法与符号幅值表示加减法相似，但有两个不同：首先要能检测出操作数为0、或NaN以及结果为0或的情况。其次由于阶可能不等，因此要能进行有效值的对齐。,移位/对齐/相减（相加）的过程能处理大部分规格化浮点数的加减法。但当操作数为0、或NaN时，浮点数算法必须对其单独处理。,计算机组成与结构,湖南大学计算机与通信学院,8-64,表中列出了对不同的操作数X和Y，UXY的执行结果。当X与Y相加时，AS=0；相减时，AS=1。,1、IF Y=0，THEN UX0=X，即UX，ELSE 2、IF X=0且YNaN，THEN U0Y。IF AS=0 THEN UY，否则UY，ELSE 3、IF X=NaN，THEN UX（=NaN），ELSE 4、IF Y=NaN，THEN UY（=NaN），ELSE 5、IF X=，THEN UX，ELSE 6、IF Y=，THEN 当AS=0时UY，否则U Y，ELSE 7、用常规的加减法步骤计算U。,上表根据以下规则求出：,计算机组成与结构,湖南大学计算机与通信学院,8-65,浮点加减算法,1、对阶（小阶向大阶对齐）2、有效值加减，阶码不变3、结果规格化,当PM=0时，有效值相加。如果加法使C置1，则结果的形式为1.xxxx，此时必须将其有效值右移一位，并且阶码加1，使其规格化。如果这使得阶码溢出，则最终结果被置为，否则将得到正确结果。,当PM=1时，执行有效值相减。若相减使C置0，则结果的有效值取负（UF UF+1），符号取反（US US)，结果的形式只可能为.0 xxx或.1xxx。如果以0开头（UF（n-1），则有效值左移一位同时阶码减1。重复这一操作，直到出现以下3种情况：UF（n-1）=1、UF=0、阶值小于最小阶（即CE=1，下溢）。当出现第一种情况时，结果完成规格化，得出正确结果并终止算法。当出现其他两种情况时，结果必须被置0。,计算机组成与结构,湖南大学计算机与通信学院,8-66,8.5.4 乘法和除法,与符号幅值表示法一样，浮点数乘法采用移位相加的算法实现，但要作修改。首先检测操作数是否为特殊值，接着通过有效值相乘和阶值相加实现乘法。同时检查是否溢出和下溢。有效值相乘所得积的形式为.1xxx或.01xx。若为.01xx，要规格化并重新检查下溢。,两个规格化浮点数相乘，积的有效值不可能小于.01。在最糟的情况下，结果为.1000.1000=.01xx。,第1步就检测操作数是否有特殊值（0、NaN和）并进行相应的处理。有则进行特殊值处理后终止算法，否则设置结果的符号位和阶。,若至少一个操作数为0，则结果为0；均不为0且至少有一个为NaN，则结果为NaN；均不为0和NaN且至少有一个为，则为，并设置符号。,浮乘要点,计算机组成与结构,湖南大学计算机与通信学院,8-67,积的阶码为两操作数阶码之和。每个操作数阶码中都包含了偏移量，简单地加阶码将包含偏移量两次。因此设置阶码时，将阶码之和减去一个偏移量才能得到积的正确阶码。,例如，（.110123）（.111022），偏移量为8，则两个阶码的移码分别为11（=3+8）和10（=2+8），相加得21，当偏移量为8时，该移码对应于213（13=21 8），显然积不可能在213附近，这个结果是错误的。错误的原因是偏移量被加了2次，一次在11中，一次在10中。从21中减去多余的偏移量得阶码13，对应于25（5=13 8），这才是正确的阶码。,检查阶码是否溢出和下溢。若溢出，则根据结果符号设结果为；若下溢，则置0。溢出或下溢到此终止算法。,计算机组成与结构,湖南大学计算机与通信学院,8-68,乘除算法,1、有效位相乘（除），阶码相加（减）。2、结果规格化。,除法采用移位相减算法，类似于符号幅值表示除法算法。首先检测特殊值。符号幅值表示除法在X Y时产生溢出，但浮除在XF YF时不溢出，此时将X