计算机组成与原理课件第八章运算方法

计算机组成与原理课件第八章运算方法

1.几种常用数据格式的算术运算算法和它们的硬件实现。包括定点数表示及其加、减、乘、除过程和硬件实现，二—十进制（或BCD）码的格式和操作。

2.提高算术操作性能的专用硬件。（流水线、查找表、华莱士树）

3.介绍浮点数的格式和它们的算术操作。包括浮点数的格式，性质，以及加、减、乘、除过程和硬件实现，还有IEEE754

浮点数标准。

执行算术和逻辑运算指令以及微操作是任何CPU的一个必不可少的重要部分。

第2页,共108页，2024年2月25日，星期天8.1无符号表示法

非负数码：表示0或一个正数。n位非负数码的数值范围为0（所有位都为0）到2n-1（所有位都为1）。2的补码（简称补码）：既能表示正数又能表示负数。n位数的数值范围为-2n-1到2n-1-1。当最高位为1时表示负数，最高位为0时表示正数（包括0）。正数（包括0）的补码与非负数码相同，负数的补码为其绝对值的2的补码，等于它的绝对值按位取反（该数的1的补码，简称为反码），加1。有两种常用的无符号表示法：第3页,共108页，2024年2月25日，星期天

例如，求-5的4位补码表示，首先求出它的绝对值5（0101），产生反码值1010，再加1得补码1011。下表列出了8位二进制数的非负数码和补码表示的数值。表8.1无符号表示的数值第4页,共108页，2024年2月25日，星期天8.1.1加法和减法

加法直接采用二进制加法实现，硬件中通过使用一个并行加法器来实现，如下图所示。X和Y是8位寄存器，该电路实现微操作

ADD：X←X+Y

只要结果在正常范围内（对非负数码而言为0到2n-1，对2的补码而言为-2n-1到2n-1-1），该电路就能得到正确的结果。图8.1微操作X←X+Y的实现第5页,共108页，2024年2月25日，星期天当结果不能表示为一个8位数值时就会导致溢出：例如，非负数码加法255+1，即11111111+00000001，直接加得100000000，有9位，不能存于8位寄存器中。

并行加法器产生额外的进位输出，它用来标志算术溢出。在非负数码中，这个进位能置溢出标志，它提示系统产生了溢出，所得结果不完全正确，系统应进行相应的结果修复处理或错误处理。

在补码中，判断溢出不但要检查进位输出，还要检查结果最高位的进位输入。如果这两者相等，那么不产生溢出，否则产生溢出。见下图：第6页,共108页，2024年2月25日，星期天图8.2补码加法的溢出产生

在（a）和（c）中最高位的进位输入和进位输出相等，不产生溢出；而在（b）和（d）中两者不等，产生溢出。溢出溢出第7页,共108页，2024年2月25日，星期天

非负数码的减法可以转换成加法，即X–Y通过执行X+（-Y）来实现。首先将Y转换成–Y的补码，再将–Y的补码与X的补码相加即可得X–Y的补码：[X–Y]补=[X]补+[-Y]补左图给出了执行微操作SUB：X←X–Y的一种硬件实现。图8.3微操作X←X–Y的实现第8页,共108页，2024年2月25日，星期天

对于非负数码，减法的结果不会比2n-1大，但可能比0小。例如，1–2执行为00000001+11111110=11111111，即255。图中（b）和（d）溢出，而（a）和（c）没有溢出。图8.4无符号2的补码减法的溢出产生

同样，补码减法也将X–Y转换成X+（–Y）来执行，而判断溢出的条件与补码加法相同。

此时，如果减法（通过补码加法实现）产生了进位输出0而不是1时，则发生了溢出。溢出溢出第9页,共108页，2024年2月25日，星期天8.1.2乘法

乘法可以看成加法的重复。一个数乘以n与n个该数相加的结果相同。可以用下列算法来实现乘法x×y。

z=0；

FORi=1TOyDO{z=z+x}

这种算法不理想，原因是速度慢、计算x×y的时间不确定。我们希望不论x、y取何值，执行乘法的时间相同。

x=27y=2538113554

6831第10页,共108页，2024年2月25日，星期天

这个过程被称为移位—相加乘法。首先计算每个部分积并左移到正确位置，然后再将所有的部分积相加。对这个算法稍做修改，使得硬件实现更为简单，就可得到无符号非负二进制数的乘法基本算法。

第一个修改是每求出一个部分积后就计算和：x=27y=253811351431←计算的和

54

6831←最终计算的和因为硬件上，二输入加法器很容易实现，而三输入或多输入的加法器则变得非常复杂。任何时候都没有多于两个数的加。注意：每一个部分积都逐次左移一位，因此排列的位置不同。在当前和与部分积的相加中，某些位的运算不必要。第11页,共108页，2024年2月25日，星期天第二个修改用右移当前和代替左移部分积：x=27y=25381←右移一位

81←1被右移出，故不参加加法运算

135

1431←右移一位

1431←31被右移出，故不参加加法运算

54

6831←最后右移一位

6831

每次都是相同的两列数字进行加法。已经右移到这两列右边的数字只是简单的写下，不进行加法。第12页,共108页，2024年2月25日，星期天

若用二进制，不是乘以0就是乘以1，因此部分积不是0（X×0=0）就是被乘数的值（X×1=X）。

算法：两个n位寄存器的值X和Y的移位相加乘法

n位寄存器U和V：保存结果（U保存结果的高n位，V保存结果的低n位）

一位寄存器C

：用来保存执行加法时的进位

C=0,U=0；

FORi=1TOnDO{IFY0=1THENCU=U+X；

线性右移

CUV；循环右移Y}

二进制乘法第13页,共108页，2024年2月25日，星期天考虑乘法：13×11，即X=1101，Y=1011,n=4表8.2第14页,共108页，2024年2月25日，星期天

算法的RTL代码如下所示。其中1，2，3是连续的状态。

1：

C←0，U←0，i←n

Y02：

CU←U+X

2：

i←i-1

3：

shr(CUV)，cir(Y)

Z’3：

GOTO2

Z3：FINISH←1

表8.3列出了13×11的RTL代码的执行步骤。同样初始化X=1101，Y=1011。除了在每个周期增加了满足的条件和执行的微操作外，表8.3同表8.2一样。

第15页,共108页，2024年2月25日，星期天表8.31101×1011移位相加乘法RTL代码的执行轨迹第16页,共108页，2024年2月25日，星期天根据RTL代码设计硬件。硬件包括两部分：寄存器部分:微操作在此执行；

控制部分:产生需要的控制信号和状态值。X——n位寄存器

Y、U、V——n位移位寄存器（当shr信号有效时它们右移一位）寄存器i——存储值n的递减计数器

C和FINISH——一位寄存器在寄存器之间设置数据通路来实现RTL代码中的微操作所要求的数据传送。由于在算法的RTL代码中，当i=0时，Z=1；因此将i的所有位异或在一起产生Z，从而满足仅当i的所有位都为0（i=0）时，Z才为1。否则，Z为0，用来驱动状态计数器装载1。

第17页,共108页，2024年2月25日，星期天图8.5移位——相加乘法算法的硬件实现3第18页,共108页，2024年2月25日，星期天

考察图8.5给出的控制部分，看它是如何实现RTL代码的。

当START置1时，StateCounter和FINISH清零，Decoder工作。Decoder输出1，使U清零，数n装载到i中。

StateCounter加1，

Decoder输出2。使i减1，并且，若Y0=1，将U+X保存在CU中；若Y0=0，则C、U的值不变。

StateCounter加1到10，Decoder输出3。此时，C、U、V都右移一位。以下两件事必有一件发生：当Z=0时，StateCounter被装载值01，

Decoder输出2，实现操作“GOTO2”。否则Z=1时，FINISH置1，Decoder使能端置0，不再输出1，2，3，硬件停止工作。第19页,共108页，2024年2月25日，星期天如果Y值不要求保存，可将其值保存在V寄存器中，则乘法转换为UV←X×V。每次检查V的最低位V0，若为1，执行加法。下一步执行右移时，该位将丢弃，因为它不再需要使用。修改后的RTL代码为：

1：

C←0，U←0，i←nV02：

CU←U+X

2：

i←i-1

3：

shr(CUV)Z’3：

GOTO2Z3：FINISH←1

与前面的RTL代码有两处不同：一是CU←U+X的条件由Y02改为V02；二是减少了cir(Y)的操作。

硬件实现上，除了C和U的LD信号改为V0∧2，以及去掉了寄存器Y之外，该代码的硬件实现与图8.5的相同。优化算法第20页,共108页，2024年2月25日，星期天下表显示改进后的RTL代码执行1101×1011的步骤。表8.4改进后的RTL代码的执行步骤除了初始化V寄存器和去掉Y寄存器之外，该表与表8.3相同。第21页,共108页，2024年2月25日，星期天8.1.2.1布斯算法

对于补码，上面的算法并不总能得出正确的结果。原因是该算法仅能处理两个正数相乘。例子（1101×1011

）中，补码表示分别为–3和-5，它们的积应是15；而上面的算法将得出结果10001111，即–113，显然是错的。

当有一个或两个操作数为负数时，执行下面的程序，上面的算法则可以使用：IF被乘数

<0THEN被乘数←

-被乘数；

IF乘数

<0THEN乘数←

-乘数；

用非负数乘法进行乘法运算；

恢复被乘数和乘数的原值；

IF被乘数和乘数中有一个为负数，并且另一个非零，

THEN结果←

-结果第22页,共108页，2024年2月25日，星期天

这个算法很麻烦，booth’s算法比它简单。该算法直接对补码数据进行运算，不需进行正数和负数之间的转换。

booth’s算法也检查乘数的每一位，并把当前和右移一位。不同的是，并不是乘数的每个1都执行加法；而是对于一串1的第一个1执行减法，对于一串1的最后一个1执行加法。

检查Y的一串1的关键是要保留上一次Y的最低位。如果Y的最低位Y0和最后移出的位为：

10，则该1开始了一串1，执行减法；

01，则该0结束了一串1，执行加法；

11，则在一串1中，不做任何操作。

00，则该算法既不需要加法又不需要减法。为了检查这两位，用一个1位寄存器Y-1来保存最后移出的位。它被初始化为0，以保证Y的第一串1能被检查到。第23页,共108页，2024年2月25日，星期天booth’s乘法UV←X×Y，U、V、X、Y为n位值，Y-1为一位值：U=0；Y-1=0；FORi=1TOnDO{IF一串1的开始THENU=U–X（=U+X’+1）；

IF一串1的结尾THENU=U+X；算术右移UV；循环右移Y并将Y0复制给Y-1}

表8.5列出了当X=-3（1101）和Y=-5（1011）时，该算法的步骤。第24页,共108页，2024年2月25日，星期天X=1101,Y=1011,X’=0010表8.5booth’s算法的步骤:X=-3（1101）,Y=-5（1011）第25页,共108页，2024年2月25日，星期天

该算法的RTL代码。信号START和一位寄存器FINISH用于初始化和终止算法。算法中U、V、X、Y为n位值，Y-1为一位值。循环计数器i为递减计数器，由n递减到0。

1：

U←0，Y-1

←0，i←n

Y0Y-1’

2：

U←U+X’+1Y0’Y-1

2：

U←U+X

2：

i←i-1

3：

ashr(UV)，cir(Y)，Y-1←Y0Z’3：

GOTO2Z3：FINISH←1

注意，条件Y0Y-1’对应于一串1的开始，执行减法；Y0’Y-1对应于一串1的结尾，执行加法。加、减法语句可合并一起：

（Y0⊕Y-1）2：U←U+（X⊕Y0）+Y0

第26页,共108页，2024年2月25日，星期天

该RTL代码执行（－3）×（－5）的步骤，X＝1101，Y＝1011。表8.6booth’s算法RTL代码的执行步骤

与移位—相加算法相同，该算法也可以通过将Y的值保存在V中来去掉Y寄存器

第27页,共108页，2024年2月25日，星期天图8.6booth’s算法的硬件实现31第28页,共108页，2024年2月25日，星期天8.1.3除法

除法可以看成减法的重复，z=x÷y可以这样实现：

Z＝0；

WHILEx≥yDO{z＝z＋1；x＝x－y}

此算法效率低、执行时间随着z的最终值的不同而改变。

可采用移位—相减算法减少执行时间，例：

09671682763943742611

注意第一步操作是比较除数71和被除数的前两位68。由于71大于68，故该位商0。这在计算机的除法运算中是很重要的一步，它被用来检测商是否溢出。第29页,共108页，2024年2月25日，星期天

将被除数左移，使得每次相减的结果总是送到同一位置上。09671682700←68除以71商0682←取出下一位

682←左移一位

639←682除以71商9437←取出下一位

437←左移一位

426←437除以71商611←余数左移出的位不参加减法计算

第一步检查68是否大于等于71，这是一个溢出检测

第30页,共108页，2024年2月25日，星期天溢出检测：在除法的硬件实现中，通常被除数（如6827）保存在一个2n位的寄存器或两个n位的寄存器中。除数（71）和商（96）保存在n位的寄存器中。余数保存在被除数的两个n位寄存器中的一个中。如果被除数的高n位大于等于除数，那么商将大于n位而不能保存在商寄存器中，此时产生溢出。例如，十进制的除法7827÷71，其中被除数为4位，除数为2位。由于78>71，商有3位，比商寄存器的位数（2位）还要多一位，因此产生溢出。这种溢出检测的好处是可以防止除以0的操作，此时也会产生溢出。第31页,共108页，2024年2月25日，星期天二进制值除法:二进制除法中，商只可能为0或1。当被除数大于等于除数时，商1；否则商0。下面的算法实现了两个二进制值的移位—相减除法。被除数在初始化时加载到UV，其中U保存高n位，V保存低n位。除数和商分别保存在n位值X和Y中。余数保存在U中。C为1位值，用来保存U的移出位。U≥XTHEN产生溢出并终止算法；

Y=0；C=0；

FORi=1TOnDO{线性左移CUV；线形左移Y；

IFCU≥XTHEN{Y0=1，U=CU–X}}

考虑第一步就终止的情况。如112÷7，若n=4，则UV=01110000，X=0111。由于U≥X，均为0111，将终止算法。如果继续执行，将产生商16（10000）和余数0。但值10000不能保存在4位的Y中，产生溢出。第32页,共108页，2024年2月25日，星期天

下表列出了该算法执行147÷13的步骤。即U=1001，V=0011，X=1101，n=4。表8.7移位——相减算法的执行步骤第33页,共108页，2024年2月25日，星期天

算法的RTL代码。其中X、U、V、Y为n位值，C和OVERFLOW为1位值。当i=0时，Z=1；当U≥X时，G=1。FINISHI置1则算法结束。1，2，3，4是连续的状态。G1：FINISH←1，OVERFLOW←1

2：Y←0，C←0，OVERFLOW←0，i←n3：shl(CUV)，shl(Y)，i←i-1（C+G）4：Y0←1，U←U+X’+1Z’4：GOTO3Z4：FINISH←1

大部分的RTL语句由算法直接转换而成，注意条件CU≥X等价于条件U≥X（G=1）或（C=1），即（C+G）；

算法中的U=CU–X使用补码加法U←U+X’+1实现。第34页,共108页，2024年2月25日，星期天

下表列出了该RTL代码执行除法：147÷13的执行步骤。初始化时U=1001，V=0011，X=1101，n=4。表8.8移位——相减除法的RTL代码的执行步骤第35页,共108页，2024年2月25日，星期天该算法的硬件实现。图8.7移位—相减除法的硬件实现2第36页,共108页，2024年2月25日，星期天

以上称为不恢复余数的除法算法，这种算法是仅当CU≥X时，才执行减法U←U–X。第二种类型的除法是恢复余数的除法算法。它不是在执行减法之前先检查是否CU≥X，它是先执行减法再比较CU是否大于等于X。如果CU<X，则该算法再执行一次U←U+X，使U恢复为原来值。

恢复余数的算法有相同的步骤：首先检测溢出。如果没有产生溢出，则进入移位—相减循环。它们的主要区别是处理比较的方式不同。不恢复余数的算法是先进行CU和X的比较，如果CU≥X则执行减法U←CU–X。恢复余数的算法则相反，先执行减法U←U–X，如果发现CU<X（结果为负），则说明不应执行减法，此时通过执行加法U←U+X，使U恢复为原来值。第37页,共108页，2024年2月25日，星期天

恢复余数的算法。被除数初始化时保存在UV中，除数保存在X中，商保存在Y中，余数最后保存在U中。U、V、X、Y都是n位值，C是一位值。

CU=U+X’+1；

U=U+X，IFC=1THEN产生溢出并终止算法；

Y=0；

FORi=1TOnDO{线性左移

CUV；

线形左移

Y；

IFC=1THEN{U=U+X’+1}ELSE{CU=U+X’+1}IFC=1THEN{Y0=1}ELSE{U=U+X}}算法第一步为CU与X的比较第38页,共108页，2024年2月25日，星期天CU与X的比较。操作CU=U+X’+1实际上实现了两个功能：显式的功能是减法U–X，而隐含的功能是U和X的比较。如果U≥X，该操作将C置1，否则将C置0。如下所示：在（a）和（b）中，U≥X，C置1；在（c）中，U<X，C置0。图8.8在计算CU=U+X’+1的同时比较了U和X：（a）正结果，（b）零结果，（c）负结果第39页,共108页，2024年2月25日，星期天整个算法的分析。头两条语句是比较U和X的大小。如果U≥X，将产生溢出，此时U←U+X’+1将C置1。否则不溢出，它将C置0。第二条语句是将U恢复为原来值，如果没有溢出，将初始化Y并进入移位—相减循环。

移位—相减循环从左移CUV和Y开始的。而第一条IF语句（IFC=1THENU=U+X’+1ELSECU=U+X’+1）实现了减法（U=U–X）和CU与X的比较（如果CU≥X则C=1）。

下一条IF语句（IFC=1THENY0=1ELSEU=U+X）当C=1时，CU≥X，减法有效，只需在商的相应位（Y0）上商1。而当C=0时，CU<X，加法将U恢复为原来值。如C=1，则CU一定比X大，执行减法U←U+X’+1，并且使C仍保持1值。如C=0，执行减法CU←U+X’+1。该减法仅当CU≥X时，使C置1。结果是：无论执行哪个减法，都有U=U–X，以及当CU≥X时C置1，否则置0。第40页,共108页，2024年2月25日，星期天两个例子。第一个例子为225÷13，它的执行步骤如表8.9（a）所示。首先初始化X=1101，n=4。第一个减法将C置1，说明将产生溢出。（实际上，由于225÷13=17余4，而17的二进制是10001，因此不能存于4位的寄存器中。）下一步恢复U值并终止算法。表8.9恢复余数除法算法的执行步骤（a）有溢出，

另一个例子147÷13，执行步骤如表8.9（b）所示。没有溢出。算法的前几步检测溢出和初始化Y。接下来每三步为一组表示循环的一次迭代。第41页,共108页，2024年2月25日，星期天该算法正确地计算了147÷13(X=1101)，商为11，余数为4。表8.9恢复余数除法算法的执行步骤（b）无溢出

每次迭代都执行相似的移位和减法/比较操作。每次迭代的最后一步不是更新商（保存在Y中）就是将余数恢复为原来值（保存在U中）。第42页,共108页，2024年2月25日，星期天恢复余数除法算法的RTL代码。它采用的值与不恢复余数算法中采用的值基本相同。它与不恢复余数算法非常接近。●OVERFLOW为1位值，当溢出发生时置1，否则置0。●FINISH为1位值，当算法终止时置1。不管是循环结束的正常终止还是溢出，都要将FINISH置1。●与其他算法相同，计数器i的值从n递减到0。当i=0时，Z=1。●除非遇到GOTO操作，在正常情况下状态从11--12—2—3--41--42。第43页,共108页，2024年2月25日，星期天11：CU←U+X’+1；

12：U←U+XC12：

FINISH←1，OVERFLOW←12：

Y←0，OVERFLOW←0，i←n3：

shl(CUV)，shl(Y)，i←i-1C41：

U←U+X’+1C’41：

CU←U+X’+1C42：

Y0←1C’42：

U←U+XZ42：

FINISH←1Z’42：GOTO3

CU=U+X’+1；

U=U+X，IFC=1THEN产生溢出并终止算法；

Y=0；

FORi=1TOnDO{线性左移

CUV；

线形左移

Y；

IFC=1THEN{U=U+X’+1}ELSE{CU=U+X’+1}IFC=1THEN{Y0=1}ELSE{U=U+X}}第44页,共108页，2024年2月25日，星期天表8.10恢复余数除法算法的RTL代码的执行步骤147÷13第45页,共108页，2024年2月25日，星期天该算法的硬件实现如图所示。减少了产生G的比较器，但并行加法器的输入更加复杂。因为此时要求它进行两种操作U+X或U–X。同时，由于有6个状态，状态计数器和译码器要稍微大一些。图8.9恢复余数除法的硬件实现42i第46页,共108页，2024年2月25日，星期天补码相除

补码相除没有一种通用的算法。一般是通过对正负数值进行转换来实现补码相除。该算法如下所示。除法可以使用恢复余数的硬件实现或不恢复余数的硬件实现。IF被除数

<0THEN被除数←

-被除数；

IF除数

<0THEN除数←

-除数；

使用恢复余数（或不恢复余数的）硬件实现除法运算；

IF被除数和除数中有一个为负数THEN结果←-结果第47页,共108页，2024年2月25日，星期天8.2带符号表示法符号—幅值表示法（signed_magnitudenotation）符号—补码表示法（signed_two’scomplementnotation）8.2.1符号—幅值表示法（signed_magnitudenotation）

包括两个部分：符号部分为1位，0表示正数（或0），1表示负数；幅值部分为n位，以非负数码的形式表示数的绝对值。

用XsX表示符号—幅值表示法，其中Xs为1位的符号值，X为n位幅值。

例如：+3和-3有相同的幅值3，仅仅符号不同。在二进制中，+3表示为0（符号）0011，而-3表示为1（符号）0011。第48页,共108页，2024年2月25日，星期天8.2.1.1加法和减法

操作UsU←XsX±YsY，定义AS为计算操作符。AS=0表示加，=1表示减。还定义PM=Xs⊕AS⊕Ys。Xs、AS和Ys共有8种可能的组合。下表列出这些组合及其相应的PM值，同时分别给出了当X=3，Y=5和X=5，Y=3时这8种组合的结果。表8.11符号—幅值数据的加法和减法第49页,共108页，2024年2月25日，星期天

执行何种操作由两个值决定：PM的值以及X和Y的相对幅值，相对幅值表示是X>Y、X=Y还是X<Y。分两种情况考虑：PM=0和PM=1。

第一种情况：PM=0

将X和Y的幅值加在一起；结果的符号总与第一个操作数的符号Xs相同。通过微操作Us←Xs，U←X+Y实现。

结合考虑溢出情况，可以用CU←X+Y代替U←X+Y，并将C的值赋给溢出标志。

因此PM=0时符号—幅值表示加减法的RTL代码为：

PM’1：Us←Xs，CU←X+YPM’2：OVERFLOW←C第50页,共108页，2024年2月25日，星期天第二种情况：PM=1X和Y相对幅值的问题。当X>Y时，U应为X–Y，即X+Y’+1。当X<Y时，X–Y将产生期望值Y–X的负数，该值必须取反；可通过取其2的补码，或（X–Y）’

+1来实现。减法CU←X+Y’+1同时也实现了X与Y的比较，通过C，可以判断是否要将结果（X–Y）取负。

0结果问题。当X=Y时，执行CU←X+Y’+1，得U=0且C=1。因0总是做为+0保存，要将结果的符号设置为0。X≠Y时结果的符号问题。从表8.11中发现，X>Y时，Us与Xs的值相同；X<Y时，Us与Xs的反码相同。第51页,共108页，2024年2月25日，星期天PM=1时符号—幅值表示加减法的RTL代码。注意，当X>Y时，C=1，Z=0；当X=Y时，C=1，Z=1；当X<Y时，C=0。另外将OVERFLOW设置为0，因为PM=1时不可能发生溢出。

PM1：CU←X+Y’+1，OVERFLOW←0CZ’PM2：Us←XsCZPM2：Us←0C’PM2：Us←Xs’，U←U’+1●CZ’为真时（C=1且Z=0，即X>Y），U中已保存了结果的正确幅值（X–Y）。此时仅需要考虑结果的符号，即把Xs赋给Us。●CZ为真时（C=1且Z=1，即X=Y），U中也已保存了结果的正确幅值0。此时仅需要把结果的符号设置为0，使结果以+0的格式保存。●C’为真时（C=0，即X<Y），保存在U中的值（X–Y）必须取反才为结果的正确幅值（Y–X），并且结果的符号为Xs的反码。第52页,共108页，2024年2月25日，星期天完整的RTL代码（包括PM=0和PM=1两种情况）。PM’1：Us←Xs，CU←X+YPM1：CU←X+Y’+1，OVERFLOW←0PM’2：OVERFLOW←CCZ’PM2：Us←XsCZPM2：Us←0C’PM2：Us←Xs’，U←U’+12：FINISH←1

为了说明这个算法，表8.12列出了当XsX和YsY取不同值时，RTL代码的执行过程。它包括了没有产生溢出时的四种可能情况：PM=0、PM=1且X>Y、PM=1且X=Y、PM=1且X<Y，以及产生溢出时的两种可能情况。第53页,共108页，2024年2月25日，星期天表8.12符号—幅值表示法的加减法举例第54页,共108页，2024年2月25日，星期天图8.10符号—幅值加减法的硬件实现第55页,共108页，2024年2月25日，星期天8.2.1.2乘法和除法

符号—幅值表示法的乘除法与非负数码的乘除法几乎完全相同，唯一不同的是它必须设置结果的符号。

对计算CU←X×Y的非负数码移位—相加乘法算法稍加修改，就可以得到下列RTL代码，它进行符号—幅值数据XsX和YsY的乘法。

1：Us←Xs⊕Ys，Vs←Xs⊕Ys，U←0，i←nY02：CU←U+X

2：

i←i-1

3：

shr(CUV)，cir(Y)Z’3：

GOTO2ZT3：

Us←0，Vs←0Z3：FINISH←1

当UV=0时T=1，否则T=0。当i=0时，Z=1。第56页,共108页，2024年2月25日，星期天下表列出了该RTL代码执行（-13）×（+11）的步骤。表8.13符号—幅值的移位—相加乘法的RTL代码轨迹类似于无符号非负数码乘法13×11，唯一不同的是多了设置结果符号Us和Vs的操作。第57页,共108页，2024年2月25日，星期天该RTL代码的硬件实现。（略）

除法可采用恢复余数算法或不恢复余数算法实现。与乘法相同，它也必须考虑结果的符号。因此乘法的RTL代码中所做的修改同样适用于除法的RTL代码。修改后的除法RTL代码。（略）第58页,共108页，2024年2月25日，星期天8.2.2符号—补码表示法

类似于符号—幅值表示法，符号—补码表示法也包括1位的符号和n位的幅值，它同样被表示为XsX。唯一不同的是其负数的幅值采用2的补码表示。+5和–3的符号—补码表示分别为：0（符号）0101和1（符号）1101

符号—补码表示法的幅值部分等价于无符号表示法中的补码。

为了加减两个符号—补码表示的数据，我们简单地把符号位当成幅值的最高位。例如，不将+5表示为0（符号）0101，而是简单地将其看成5位的值00101；第59页,共108页，2024年2月25日，星期天

这样，可以把符号—补码表示法的加减法转换为无符号补码的加减法。不过注意要使用（n+1）位的补码。把符号位看成幅值的最高位的另一个好处是：在执行补码加减法的同时能得出结果的符号。此时的溢出判断同补码加减法的溢出判断相同，即当最高位的进位输入和进位输出不相等时产生溢出。注意此时的最高位为符号位。

乘法也可以采用相同的方式实现。一旦把符号位看成它们的相对幅值的最高位，我们就能采用booth’s算法实现数据的乘法。除法也可以通过类似的方法，修改无符号补码除法来实现。第60页,共108页，2024年2月25日，星期天8.3BCD码（binarycodeddecimal）

上一节介绍的带符号表示是用二进制位来表示二进制数。这种表示的存储效率最高，因为每一比特都表示一个唯一有效的值。但在某些应用中，直接使用十进制来存储和运算将更为适合。例如，一个数字钟的应用，它的输出必须总是表示为十进制数，但内部元件可以采用二进制计时。此时如能使用一序列十进制数的存储格式，将可免去进制转换的麻烦。

用来表示十进制数的最常用格式是BCD码（binarycodeddecimal，“以二进制编码的十进制”，简称BCD）。本节将讨论BCD码的格式，及其加、减、乘、除算法和相应的硬件实现。第61页,共108页，2024年2月25日，星期天8.3.1BCD码的格式BCD码用4位等值的二进制数表示一个十进制数字。例如，0000表示0，1001表示9。BCD码中不使用大于9的4位二进制数，从1010到1111。n位的十进制数用n组4位二进制数保存。例如，27被存为00100111（在二进制中，它被存为00011011）。BCD码是一种带符号表示法，它的值可以为正也可以为负或0。类似于符号—幅值表示法，它有两个部分：1位用于表示符号，而幅值部分保存数的绝对值。例如:+27:0（符号）00100111

–27:1（符号）00100111第62页,共108页，2024年2月25日，星期天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的补码。例如：二进制U＝1010，则U’＝1111－1010＝0101BCD码的反码可以通过将999…

…99（n个9）减去自身获得。将其加1可得到10的补码，在BCD码中，用来表示原值的负数。第63页,共108页，2024年2月25日，星期天图8.11一位BCD加法器

如果Adder1的输出S3S2S1S0是无效的BCD数字，必有S3∧S2=1或S3∧S1=1,即1010～1111；或X+Y产生进位，此时Cout1=1。在这两种情况下，多路复用器的控制位置1，使得6（0110）与S3S2S1S0相加，从而得到正确结果。

两个数字X和Y首先加在一起，然后加0或加6产生正确的BCD码和。第64页,共108页，2024年2月25日，星期天

下图为一个1位BCD数的9的补码生成器。将多个该硬件相连就可以得到一个多位BCD数的9的补码生成器。图8.129的补码生成器例如，631的9的补码为999–631=368，而10的补码为368+1=369。正如二进制中2的补码用于减法或取负运算一样，10的补码在BCD码中发挥同样的作用。第65页,共108页，2024年2月25日，星期天

经过以上两个修改，二进制的符号—幅值表示法的加减算法可以用于BCD码的加减法中：

使用BCD加法器代替二进制并行加法器。使用9的补码生成器产生Y’（在条件PM1下）和U’（在条件C’PM2下）。由于Xs为1位，在条件C’PM2下，Xs实际上是通过反向器而不是通过9的补码生成器得出Xs’。BCD码加减法的RTL代码PM’1：Us←Xs，CU←X+YPM1：CU←X+Y’+1，OVERFLOW←0PM’2：OVERFLOW←CCZ’PM2：Us←XsCZPM2：Us←0C’PM2：Us←Xs’，U←U’+1

2：FINISH←1第66页,共108页，2024年2月25日，星期天

表中列出了取不同值时，RTL代码的执行过程。包括各种PM值、X>Y、X=Y和X<Y的情况。还有溢出的两个例子。表8.14BCD数的加减法的举例第67页,共108页，2024年2月25日，星期天BCD加减法的硬件实现如图所示。图8.13BCD加减法的硬件实现第68页,共108页，2024年2月25日，星期天8.3.2乘法和除法

虽然BCD的乘除法与符号—幅值表示法的乘除法很相似，但与BCD的加减法相比，BCD的乘除法要做更多的修改。上节介绍的BCD加法器和9的补码生成器在BCD乘除法中同样需要。

在BCD中，乘数的每一位可能为0～9中的任何一个数字，因此每次循环迭代最多可能要执行9次加法。因此在算法中要增加一个内循环来实现多次加法。

采用十进制移位，每次移1位BCD数字，即每次移4位。十进制右移操作记为dshr

。每次循环可能执行多次加法，因此进位Cd采用1位BCD数而不是1位二进制数。第69页,共108页，2024年2月25日，星期天

根据以上修改，我们可以把二进制符号—幅值表示法的移位—相加乘法算法转换成等价的BCD码乘法算法。实现BCD乘法UsUV←XsX×YsY的RTL代码如下所示。n为Y的十进制数的位数。Yd0为Y的BCD数据的最低位，或最低4位。当Yd0=0时，ZY0=1；当i=0时，Z=1。

1：Us←Xs⊕Ys，Vs←Xs⊕Ys，U←0，i←n，Cd←0ZY0’2：CdU←CdU+X，Yd0←Yd0–1，GOTO2ZY02：i←i–1

3：dshr(CdUV)，dshr(Y)Z’3：GOTO2ZT3：Us←0，Vs←0Z3：FINISH←1注意：由于Cd要参加加法，于是Cd必须初始化；由Yd0决定内循环次数，当Yd0＝0时，ZY0＝1。状态3要用十进制线性右移dshr。第70页,共108页，2024年2月25日，星期天

表中列出了一个BCD乘法71×23的执行步骤。该RTL代码的硬件实现。（略）表8.15BCD移位—相加乘法的执行轨迹

除法可以采用恢复余数算法和不恢复余数算法。类似乘法，这里也要增加一个内循环实现多次减法。除法的RTL代码及其硬件实现。（略）第71页,共108页，2024年2月25日，星期天8.4专用运算部件

提高计算速度的专用运算部件有：流水线、查找表和Wallace树乘法器，以及在历史视角中讨论的协处理器。8.4.1流水线

算术流水线类似于工厂的装配线。数据进入某段流水线，该段流水线对数据执行算术操作；然后将结果传给下一段，下一段又执行它的操作；如此等等，直到最后的计算被执行。

流水线不能提高单个计算的速度。额外开销实际延长了单个计算的执行时间。但通过重叠计算，即能同时在各个段处理不同的数据，流水线可以提高整体性能。

流水线提高了吞吐量（throughput），即每单位时间生成结果的数量。第72页,共108页，2024年2月25日，星期天考虑下面一行代码：

FORi=1TO100DO{A[i]←(B[i]×C[i])+D[i]}

假设每个加法和乘法的完成时间均为10ns。非流水线单处理器计算每个A[i]要20ns，完成整行代码要2000ns。一个流水线单元将A[i]的计算分为两段，如图所示，第一段执行乘法，第二段执行加法。注意，锁存器用来保存流水线每一段的输出。流水线完成整行代码只需1010ns。

第一个10ns，第一段执行乘法B[1]×C[1]。第二个10ns，第二段将该值加到D[1]并把结果保存在A[1]中，同时第一段执行下一个乘法B[2]×C[2]。第三个10ns，第一段计算B[3]×C[3]，第二段求出A[2]的值。第73页,共108页，2024年2月25日，星期天

用吞吐量和加速比（speedup）来衡量一个流水线的性能。加速比Sn为一个非流水线运算单元完成n个计算的时间与一个k段流水线完成相同计算的时间之比。

定义T1为一个非流水线运算单元每得出一个计算结果所需要的时间，它为该非流水线的时钟周期。Tk为一个k段流水线的时钟周期。如果每段具有不同的最小时钟周期，或段延时，则Tk取其中最大的周期。在上例中，T1=20ns，Tk=10ns。

流水线的加速比可以用下面的公式表示：Sn=nT1

(k+n–1)Tk

非流水线每隔T1时间产生一个结果，完成n个计算所需时间为n*T1。k段流水线在产生第一个结果之前要经过k个流水段，每个流水段需要Tk时间。其余的数据每个时钟周期都进入流水线，每个时钟周期生成一个计算结果。因此完成n个计算共需（k+n–1）个时钟周期。第74页,共108页，2024年2月25日，星期天

对前例，流水线的加速比为：S100=nT1=100×20ns=1.98

(k+n–1)Tk(2+100–1)×10nsn趋向于无穷大时可得稳态加速比的计算公式：

S∞=T1/Tk

当流水线每段延时相等时，可以得到最大加速比：

S∞=T1=T1=k

Tk(T1/k)

如果每段流水线的延时不等，则有些段的延时小于T1/k，有些大于T1/k。由于Tk为最大的延时，因此Tk>T1/k，降低了加速比。鉴于此，应该使每段流水线的延时尽可能相等，从而提高加速比。第75页,共108页，2024年2月25日，星期天

实际上，锁存器需要一定的时间来保存数据。这是流水线的额外开销。对前例，若锁存器的延时为2ns，则实际加速比为：S100=nT1=100×20ns=1.65

(k+n–1)Tk(2+100–1)×12ns

若只计算一个值A[1]，则加速比小于1：S1=nT1=1×20ns=0.83

(k+n–1)Tk(2+1–1)×12ns

此时流水线的速度实际上比非流水线的低，这是因为每段流水线都增加了锁存器的延时。

以上是基本的流水线技术。在11章中我们将看到，流水线也用于加快CPU中的取指令，指令译码和执行指令。第76页,共108页，2024年2月25日，星期天8.4.2查找表

理论上，每一组合电路都可通过将ROM配置成查找表来实现：组合电路的输入数据作为该ROM的输入地址，而组合电路的输出结果作为该地址中保存的数据。对组合电路的任何输入，通过编程，ROM都能输出正确的结果。

例如，用一个4×1的ROM来模拟一个2输入的与门。下图给出了该与门和它等价的查找表。与门的输入作为ROM的输入地址，而ROM的输出数据对应于与门的输出。通过编程ROM，对于所有可能的X和Y，ROM的输出与与门的完全相同。第77页,共108页，2024年2月25日，星期天

用查找表ROM计算UV←X×Y的实现方法如图所示。寄存器X和Y提供查找表的输入地址，查找表的输出数据为X与Y的积，它被输入到寄存器UV中。U、V、X、Y均为4位的寄存器，X与Y的积为8比特数据，因此共需要256个地址来保存所有的积。例如，地址10111101保存数据10001111，即143，它是1011（11）与1101（13）的积。图8.16用查找表实现的乘法器第78页,共108页，2024年2月25日，星期天

很多算法可以通过查找表ROM来实现，而且与前面的算法实现相比，查找表可能更具有优势。例如，图8.16给出的硬件实现比图8.5给出的移位—相加的硬件实现更简单，执行速度更快。随着操作数位数的增加，查找ROM的大小将迅速增大。实现4位乘法器的ROM大小为256×8，而等价的8位乘法器将需要64K×16的ROM。8.4.3Wallace树Wallace树是用来实现两数相乘的一种组合电路。尽管与移位—相加的乘法器相比，所需的元器件要多一些，但它的运行速度要快得多。Wallace树使用几个进位保存加法器和仅仅一个并行加法器实现乘法。第79页,共108页，2024年2月25日，星期天

进位保存加法器能同时执行三数相加，而不是两数加。它不是输出一个结果，而是输出一个和S以及一组进位位，如图。由于进位位通过加法器没有延时，因此它比并行加法器要快。它不生成最终和。图8.17一个进位保存加法器

每位Si是位Xi、Yi、Zi的二进制和，进位位Ci+1是该和产生的进位。要得到最终和，必须将S和C相加。

例如，X=0111，Y=1011，Z=0010，进位保存加法器将输出和S=1110，进位C=00110。

用一个并行加法器将S与C相加，就可以求出最终结果10100（20），即0111（7）+1011（11）+0010（2）的和。注意，因为在产生Si同时产生Ci+1，与S相比，C必须左移一位。第80页,共108页，2024年2月25日，星期天

为了使用进位保存加法器实现乘法，首先求出每一个部分积，再将这些部分积输入到进位保存加法器中，例如：x=111y=110000←PP0111←PP1111←PP2101010←求出的最终和

根据Y的每一位为1还是为0，部分积选择X或0并左移到正确的位置。

本例中，因为PP2为Y2的部分积，要将X的值111左移2位，即PP2实际为11100。类似的，由于PP1为Y1的部分积，要左移1位。

图8.18给出了为本例生成部分积的一种方法。第81页,共108页，2024年2月25日，星期天图8.18用Wallace树生成乘法的部分积第82页,共108页，2024年2月25日，星期天

可以用一个5位的进位保存加法器对部分积PP0、PP1、PP2进行加法。然后用一个并行加法器将输出S和C相加，就可以得到X与Y的最终乘积。下图给出了该乘法的硬件实现。图8.19用进位保存加法器实现3×3的乘法器第83页,共108页，2024年2月25日，星期天

图8.19给出的是一个最小Wallace树，不能完整的说明Wallace树的设计原则。下图给出两个4位数相乘的Wallace树的设计。

考虑乘法1011×1110。它产生部分积PP0=0000000，PP1=0010110，PP2=0101100，PP3=1011000。第一个进位保存加法器的输出为：S=0111010，C=00001000。第二个进位保存加法器的输出为：S=01101010，C=000110000。并行加法器输出最终积：10011010。第一个进位保存加法器实现PP0、PP1、PP2的加法；第二个进位保存加法器将PP3与S和C相加；最后通过一个并行加法器输出积。图8.204×4的Wallace树乘法器0第84页,共108页，2024年2月25日，星期天

部分积的个数随着乘数位数的增加而增加。因此当乘数位数较大时，Wallace树可以利用并行操作。图中给出两个8位数相乘的Wallace树。图8.218×8的Wallace树乘法器第85页,共108页，2024年2月25日，星期天8.5浮点数

定点数仅能表示整数而不能表示小数，计算机用浮点数来表示小数。8.5.1数据格式

浮点数的格式类似于科学记数法。一个数在科学记数法中包含：符号，小数或有效值（也叫尾数）和指数（通常叫阶）。例如，数–1234.5678可以表示为–1.2345678×103，其中符号为负号，有效值为1.23456789，指数为3。在这个例子中采用10作为基数，计算机一般都以