計(jì)算機(jī)組成與原理第八章運(yùn)算方法

計(jì)算機(jī)組成與原理課件第八章運(yùn)算方法第1頁，課件共108頁，創(chuàng)作于2023年2月

1.幾種常用數(shù)據(jù)格式的算術(shù)運(yùn)算算法和它們的硬件實(shí)現(xiàn)。包括定點(diǎn)數(shù)表示及其加、減、乘、除過程和硬件實(shí)現(xiàn)，二—十進(jìn)制（或BCD）碼的格式和操作。

2.提高算術(shù)操作性能的專用硬件。（流水線、查找表、華萊士樹）

3.介紹浮點(diǎn)數(shù)的格式和它們的算術(shù)操作。包括浮點(diǎn)數(shù)的格式，性質(zhì)，以及加、減、乘、除過程和硬件實(shí)現(xiàn)，還有IEEE754

浮點(diǎn)數(shù)標(biāo)準(zhǔn)。

執(zhí)行算術(shù)和邏輯運(yùn)算指令以及微操作是任何CPU的一個(gè)必不可少的重要部分。

第2頁，課件共108頁，創(chuàng)作于2023年2月8.1無符號(hào)表示法

非負(fù)數(shù)碼：表示0或一個(gè)正數(shù)。n位非負(fù)數(shù)碼的數(shù)值范圍為0（所有位都為0）到2n-1（所有位都為1）。2的補(bǔ)碼（簡稱補(bǔ)碼）：既能表示正數(shù)又能表示負(fù)數(shù)。n位數(shù)的數(shù)值范圍為-2n-1到2n-1-1。當(dāng)最高位為1時(shí)表示負(fù)數(shù)，最高位為0時(shí)表示正數(shù)（包括0）。正數(shù)（包括0）的補(bǔ)碼與非負(fù)數(shù)碼相同，負(fù)數(shù)的補(bǔ)碼為其絕對(duì)值的2的補(bǔ)碼，等于它的絕對(duì)值按位取反（該數(shù)的1的補(bǔ)碼，簡稱為反碼），加1。有兩種常用的無符號(hào)表示法：第3頁，課件共108頁，創(chuàng)作于2023年2月

例如，求-5的4位補(bǔ)碼表示，首先求出它的絕對(duì)值5（0101），產(chǎn)生反碼值1010，再加1得補(bǔ)碼1011。下表列出了8位二進(jìn)制數(shù)的非負(fù)數(shù)碼和補(bǔ)碼表示的數(shù)值。表8.1無符號(hào)表示的數(shù)值第4頁，課件共108頁，創(chuàng)作于2023年2月8.1.1加法和減法

加法直接采用二進(jìn)制加法實(shí)現(xiàn)，硬件中通過使用一個(gè)并行加法器來實(shí)現(xiàn)，如下圖所示。X和Y是8位寄存器，該電路實(shí)現(xiàn)微操作

ADD：X←X+Y

只要結(jié)果在正常范圍內(nèi)（對(duì)非負(fù)數(shù)碼而言為0到2n-1，對(duì)2的補(bǔ)碼而言為-2n-1到2n-1-1），該電路就能得到正確的結(jié)果。圖8.1微操作X←X+Y的實(shí)現(xiàn)第5頁，課件共108頁，創(chuàng)作于2023年2月當(dāng)結(jié)果不能表示為一個(gè)8位數(shù)值時(shí)就會(huì)導(dǎo)致溢出：例如，非負(fù)數(shù)碼加法255+1，即11111111+00000001，直接加得100000000，有9位，不能存于8位寄存器中。

并行加法器產(chǎn)生額外的進(jìn)位輸出，它用來標(biāo)志算術(shù)溢出。在非負(fù)數(shù)碼中，這個(gè)進(jìn)位能置溢出標(biāo)志，它提示系統(tǒng)產(chǎn)生了溢出，所得結(jié)果不完全正確，系統(tǒng)應(yīng)進(jìn)行相應(yīng)的結(jié)果修復(fù)處理或錯(cuò)誤處理。

在補(bǔ)碼中，判斷溢出不但要檢查進(jìn)位輸出，還要檢查結(jié)果最高位的進(jìn)位輸入。如果這兩者相等，那么不產(chǎn)生溢出，否則產(chǎn)生溢出。見下圖：第6頁，課件共108頁，創(chuàng)作于2023年2月圖8.2補(bǔ)碼加法的溢出產(chǎn)生

在（a）和（c）中最高位的進(jìn)位輸入和進(jìn)位輸出相等，不產(chǎn)生溢出；而在（b）和（d）中兩者不等，產(chǎn)生溢出。溢出溢出第7頁，課件共108頁，創(chuàng)作于2023年2月

非負(fù)數(shù)碼的減法可以轉(zhuǎn)換成加法，即X–Y通過執(zhí)行X+（-Y）來實(shí)現(xiàn)。首先將Y轉(zhuǎn)換成–Y的補(bǔ)碼，再將–Y的補(bǔ)碼與X的補(bǔ)碼相加即可得X–Y的補(bǔ)碼：[X–Y]補(bǔ)=[X]補(bǔ)+[-Y]補(bǔ)左圖給出了執(zhí)行微操作SUB：X←X–Y的一種硬件實(shí)現(xiàn)。圖8.3微操作X←X–Y的實(shí)現(xiàn)第8頁，課件共108頁，創(chuàng)作于2023年2月

對(duì)于非負(fù)數(shù)碼，減法的結(jié)果不會(huì)比2n-1大，但可能比0小。例如，1–2執(zhí)行為00000001+11111110=11111111，即255。圖中（b）和（d）溢出，而（a）和（c）沒有溢出。圖8.4無符號(hào)2的補(bǔ)碼減法的溢出產(chǎn)生

同樣，補(bǔ)碼減法也將X–Y轉(zhuǎn)換成X+（–Y）來執(zhí)行，而判斷溢出的條件與補(bǔ)碼加法相同。

此時(shí)，如果減法（通過補(bǔ)碼加法實(shí)現(xiàn)）產(chǎn)生了進(jìn)位輸出0而不是1時(shí)，則發(fā)生了溢出。溢出溢出第9頁，課件共108頁，創(chuàng)作于2023年2月8.1.2乘法

乘法可以看成加法的重復(fù)。一個(gè)數(shù)乘以n與n個(gè)該數(shù)相加的結(jié)果相同?？梢杂孟铝兴惴▉韺?shí)現(xiàn)乘法x×y。

z=0；

FORi=1TOyDO{z=z+x}

這種算法不理想，原因是速度慢、計(jì)算x×y的時(shí)間不確定。我們希望不論x、y取何值，執(zhí)行乘法的時(shí)間相同。

x=27y=2538113554

6831第10頁，課件共108頁，創(chuàng)作于2023年2月

這個(gè)過程被稱為移位—相加乘法。首先計(jì)算每個(gè)部分積并左移到正確位置，然后再將所有的部分積相加。對(duì)這個(gè)算法稍做修改，使得硬件實(shí)現(xiàn)更為簡單，就可得到無符號(hào)非負(fù)二進(jìn)制數(shù)的乘法基本算法。

第一個(gè)修改是每求出一個(gè)部分積后就計(jì)算和：x=27y=253811351431←計(jì)算的和

54

6831←最終計(jì)算的和因?yàn)橛布希斎爰臃ㄆ骱苋菀讓?shí)現(xiàn)，而三輸入或多輸入的加法器則變得非常復(fù)雜。任何時(shí)候都沒有多于兩個(gè)數(shù)的加。注意：每一個(gè)部分積都逐次左移一位，因此排列的位置不同。在當(dāng)前和與部分積的相加中，某些位的運(yùn)算不必要。第11頁，課件共108頁，創(chuàng)作于2023年2月第二個(gè)修改用右移當(dāng)前和代替左移部分積：x=27y=25381←右移一位

81←1被右移出，故不參加加法運(yùn)算

135

1431←右移一位

1431←31被右移出，故不參加加法運(yùn)算

54

6831←最后右移一位

6831

每次都是相同的兩列數(shù)字進(jìn)行加法。已經(jīng)右移到這兩列右邊的數(shù)字只是簡單的寫下，不進(jìn)行加法。第12頁，課件共108頁，創(chuàng)作于2023年2月

若用二進(jìn)制，不是乘以0就是乘以1，因此部分積不是0（X×0=0）就是被乘數(shù)的值（X×1=X）。

算法：兩個(gè)n位寄存器的值X和Y的移位相加乘法

n位寄存器U和V：保存結(jié)果（U保存結(jié)果的高n位，V保存結(jié)果的低n位）

一位寄存器C

：用來保存執(zhí)行加法時(shí)的進(jìn)位

C=0,U=0；

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

線性右移

CUV；循環(huán)右移Y}

二進(jìn)制乘法第13頁，課件共108頁，創(chuàng)作于2023年2月考慮乘法：13×11，即X=1101，Y=1011,n=4表8.2第14頁，課件共108頁，創(chuàng)作于2023年2月

算法的RTL代碼如下所示。其中1，2，3是連續(xù)的狀態(tài)。

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代碼的執(zhí)行步驟。同樣初始化X=1101，Y=1011。除了在每個(gè)周期增加了滿足的條件和執(zhí)行的微操作外，表8.3同表8.2一樣。

第15頁，課件共108頁，創(chuàng)作于2023年2月表8.31101×1011移位相加乘法RTL代碼的執(zhí)行軌跡第16頁，課件共108頁，創(chuàng)作于2023年2月根據(jù)RTL代碼設(shè)計(jì)硬件。硬件包括兩部分：寄存器部分:微操作在此執(zhí)行；

控制部分:產(chǎn)生需要的控制信號(hào)和狀態(tài)值。X——n位寄存器

Y、U、V——n位移位寄存器（當(dāng)shr信號(hào)有效時(shí)它們右移一位）寄存器i——存儲(chǔ)值n的遞減計(jì)數(shù)器

C和FINISH——一位寄存器在寄存器之間設(shè)置數(shù)據(jù)通路來實(shí)現(xiàn)RTL代碼中的微操作所要求的數(shù)據(jù)傳送。由于在算法的RTL代碼中，當(dāng)i=0時(shí)，Z=1；因此將i的所有位異或在一起產(chǎn)生Z，從而滿足僅當(dāng)i的所有位都為0（i=0）時(shí)，Z才為1。否則，Z為0，用來驅(qū)動(dòng)狀態(tài)計(jì)數(shù)器裝載1。

第17頁，課件共108頁，創(chuàng)作于2023年2月圖8.5移位——相加乘法算法的硬件實(shí)現(xiàn)3第18頁，課件共108頁，創(chuàng)作于2023年2月

考察圖8.5給出的控制部分，看它是如何實(shí)現(xiàn)RTL代碼的。

當(dāng)START置1時(shí)，StateCounter和FINISH清零，Decoder工作。Decoder輸出1，使U清零，數(shù)n裝載到i中。

StateCounter加1，

Decoder輸出2。使i減1，并且，若Y0=1，將U+X保存在CU中；若Y0=0，則C、U的值不變。

StateCounter加1到10，Decoder輸出3。此時(shí)，C、U、V都右移一位。以下兩件事必有一件發(fā)生：當(dāng)Z=0時(shí)，StateCounter被裝載值01，

Decoder輸出2，實(shí)現(xiàn)操作“GOTO2”。否則Z=1時(shí)，F(xiàn)INISH置1，Decoder使能端置0，不再輸出1，2，3，硬件停止工作。第19頁，課件共108頁，創(chuàng)作于2023年2月如果Y值不要求保存，可將其值保存在V寄存器中，則乘法轉(zhuǎn)換為UV←X×V。每次檢查V的最低位V0，若為1，執(zhí)行加法。下一步執(zhí)行右移時(shí)，該位將丟棄，因?yàn)樗辉傩枰褂?。修改后的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)的操作。

硬件實(shí)現(xiàn)上，除了C和U的LD信號(hào)改為V0∧2，以及去掉了寄存器Y之外，該代碼的硬件實(shí)現(xiàn)與圖8.5的相同。優(yōu)化算法第20頁，課件共108頁，創(chuàng)作于2023年2月下表顯示改進(jìn)后的RTL代碼執(zhí)行1101×1011的步驟。表8.4改進(jìn)后的RTL代碼的執(zhí)行步驟除了初始化V寄存器和去掉Y寄存器之外，該表與表8.3相同。第21頁，課件共108頁，創(chuàng)作于2023年2月8.1.2.1布斯算法

對(duì)于補(bǔ)碼，上面的算法并不總能得出正確的結(jié)果。原因是該算法僅能處理兩個(gè)正數(shù)相乘。例子（1101×1011

）中，補(bǔ)碼表示分別為–3和-5，它們的積應(yīng)是15；而上面的算法將得出結(jié)果10001111，即–113，顯然是錯(cuò)的。

當(dāng)有一個(gè)或兩個(gè)操作數(shù)為負(fù)數(shù)時(shí)，執(zhí)行下面的程序，上面的算法則可以使用：IF被乘數(shù)

<0THEN被乘數(shù)←

-被乘數(shù)；

IF乘數(shù)

<0THEN乘數(shù)←

-乘數(shù)；

用非負(fù)數(shù)乘法進(jìn)行乘法運(yùn)算；

恢復(fù)被乘數(shù)和乘數(shù)的原值；

IF被乘數(shù)和乘數(shù)中有一個(gè)為負(fù)數(shù)，并且另一個(gè)非零，

THEN結(jié)果←

-結(jié)果第22頁，課件共108頁，創(chuàng)作于2023年2月

這個(gè)算法很麻煩，booth’s算法比它簡單。該算法直接對(duì)補(bǔ)碼數(shù)據(jù)進(jìn)行運(yùn)算，不需進(jìn)行正數(shù)和負(fù)數(shù)之間的轉(zhuǎn)換。

booth’s算法也檢查乘數(shù)的每一位，并把當(dāng)前和右移一位。不同的是，并不是乘數(shù)的每個(gè)1都執(zhí)行加法；而是對(duì)于一串1的第一個(gè)1執(zhí)行減法，對(duì)于一串1的最后一個(gè)1執(zhí)行加法。

檢查Y的一串1的關(guān)鍵是要保留上一次Y的最低位。如果Y的最低位Y0和最后移出的位為：

10，則該1開始了一串1，執(zhí)行減法；

01，則該0結(jié)束了一串1，執(zhí)行加法；

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

00，則該算法既不需要加法又不需要減法。為了檢查這兩位，用一個(gè)1位寄存器Y-1來保存最后移出的位。它被初始化為0，以保證Y的第一串1能被檢查到。第23頁，課件共108頁，創(chuàng)作于2023年2月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的結(jié)尾THENU=U+X；算術(shù)右移UV；循環(huán)右移Y并將Y0復(fù)制給Y-1}

表8.5列出了當(dāng)X=-3（1101）和Y=-5（1011）時(shí)，該算法的步驟。第24頁，課件共108頁，創(chuàng)作于2023年2月X=1101,Y=1011,X’=0010表8.5booth’s算法的步驟:X=-3（1101）,Y=-5（1011）第25頁，課件共108頁，創(chuàng)作于2023年2月

該算法的RTL代碼。信號(hào)START和一位寄存器FINISH用于初始化和終止算法。算法中U、V、X、Y為n位值，Y-1為一位值。循環(huán)計(jì)數(shù)器i為遞減計(jì)數(shù)器，由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’對(duì)應(yīng)于一串1的開始，執(zhí)行減法；Y0’Y-1對(duì)應(yīng)于一串1的結(jié)尾，執(zhí)行加法。加、減法語句可合并一起：

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

第26頁，課件共108頁，創(chuàng)作于2023年2月

該RTL代碼執(zhí)行（－3）×（－5）的步驟，X＝1101，Y＝1011。表8.6booth’s算法RTL代碼的執(zhí)行步驟

與移位—相加算法相同，該算法也可以通過將Y的值保存在V中來去掉Y寄存器

第27頁，課件共108頁，創(chuàng)作于2023年2月圖8.6booth’s算法的硬件實(shí)現(xiàn)31第28頁，課件共108頁，創(chuàng)作于2023年2月8.1.3除法

除法可以看成減法的重復(fù)，z=x÷y可以這樣實(shí)現(xiàn)：

Z＝0；

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

此算法效率低、執(zhí)行時(shí)間隨著z的最終值的不同而改變。

可采用移位—相減算法減少執(zhí)行時(shí)間，例：

09671682763943742611

注意第一步操作是比較除數(shù)71和被除數(shù)的前兩位68。由于71大于68，故該位商0。這在計(jì)算機(jī)的除法運(yùn)算中是很重要的一步，它被用來檢測(cè)商是否溢出。第29頁，課件共108頁，創(chuàng)作于2023年2月

將被除數(shù)左移，使得每次相減的結(jié)果總是送到同一位置上。09671682700←68除以71商0682←取出下一位

682←左移一位

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

437←左移一位

426←437除以71商611←余數(shù)左移出的位不參加減法計(jì)算

第一步檢查68是否大于等于71，這是一個(gè)溢出檢測(cè)

第30頁，課件共108頁，創(chuàng)作于2023年2月溢出檢測(cè)：在除法的硬件實(shí)現(xiàn)中，通常被除數(shù)（如6827）保存在一個(gè)2n位的寄存器或兩個(gè)n位的寄存器中。除數(shù)（71）和商（96）保存在n位的寄存器中。余數(shù)保存在被除數(shù)的兩個(gè)n位寄存器中的一個(gè)中。如果被除數(shù)的高n位大于等于除數(shù)，那么商將大于n位而不能保存在商寄存器中，此時(shí)產(chǎn)生溢出。例如，十進(jìn)制的除法7827÷71，其中被除數(shù)為4位，除數(shù)為2位。由于78>71，商有3位，比商寄存器的位數(shù)（2位）還要多一位，因此產(chǎn)生溢出。這種溢出檢測(cè)的好處是可以防止除以0的操作，此時(shí)也會(huì)產(chǎn)生溢出。第31頁，課件共108頁，創(chuàng)作于2023年2月二進(jìn)制值除法:二進(jìn)制除法中，商只可能為0或1。當(dāng)被除數(shù)大于等于除數(shù)時(shí)，商1；否則商0。下面的算法實(shí)現(xiàn)了兩個(gè)二進(jìn)制值的移位—相減除法。被除數(shù)在初始化時(shí)加載到UV，其中U保存高n位，V保存低n位。除數(shù)和商分別保存在n位值X和Y中。余數(shù)保存在U中。C為1位值，用來保存U的移出位。U≥XTHEN產(chǎn)生溢出并終止算法；

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，將終止算法。如果繼續(xù)執(zhí)行，將產(chǎn)生商16（10000）和余數(shù)0。但值10000不能保存在4位的Y中，產(chǎn)生溢出。第32頁，課件共108頁，創(chuàng)作于2023年2月

下表列出了該算法執(zhí)行147÷13的步驟。即U=1001，V=0011，X=1101，n=4。表8.7移位——相減算法的執(zhí)行步驟第33頁，課件共108頁，創(chuàng)作于2023年2月

算法的RTL代碼。其中X、U、V、Y為n位值，C和OVERFLOW為1位值。當(dāng)i=0時(shí)，Z=1；當(dāng)U≥X時(shí)，G=1。FINISHI置1則算法結(jié)束。1，2，3，4是連續(xù)的狀態(tài)。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語句由算法直接轉(zhuǎn)換而成，注意條件CU≥X等價(jià)于條件U≥X（G=1）或（C=1），即（C+G）；

算法中的U=CU–X使用補(bǔ)碼加法U←U+X’+1實(shí)現(xiàn)。第34頁，課件共108頁，創(chuàng)作于2023年2月

下表列出了該RTL代碼執(zhí)行除法：147÷13的執(zhí)行步驟。初始化時(shí)U=1001，V=0011，X=1101，n=4。表8.8移位——相減除法的RTL代碼的執(zhí)行步驟第35頁，課件共108頁，創(chuàng)作于2023年2月該算法的硬件實(shí)現(xiàn)。圖8.7移位—相減除法的硬件實(shí)現(xiàn)2第36頁，課件共108頁，創(chuàng)作于2023年2月

以上稱為不恢復(fù)余數(shù)的除法算法，這種算法是僅當(dāng)CU≥X時(shí)，才執(zhí)行減法U←U–X。第二種類型的除法是恢復(fù)余數(shù)的除法算法。它不是在執(zhí)行減法之前先檢查是否CU≥X，它是先執(zhí)行減法再比較CU是否大于等于X。如果CU<X，則該算法再執(zhí)行一次U←U+X，使U恢復(fù)為原來值。

恢復(fù)余數(shù)的算法有相同的步驟：首先檢測(cè)溢出。如果沒有產(chǎn)生溢出，則進(jìn)入移位—相減循環(huán)。它們的主要區(qū)別是處理比較的方式不同。不恢復(fù)余數(shù)的算法是先進(jìn)行CU和X的比較，如果CU≥X則執(zhí)行減法U←CU–X?；謴?fù)余數(shù)的算法則相反，先執(zhí)行減法U←U–X，如果發(fā)現(xiàn)CU<X（結(jié)果為負(fù)），則說明不應(yīng)執(zhí)行減法，此時(shí)通過執(zhí)行加法U←U+X，使U恢復(fù)為原來值。第37頁，課件共108頁，創(chuàng)作于2023年2月

恢復(fù)余數(shù)的算法。被除數(shù)初始化時(shí)保存在UV中，除數(shù)保存在X中，商保存在Y中，余數(shù)最后保存在U中。U、V、X、Y都是n位值，C是一位值。

CU=U+X’+1；

U=U+X，IFC=1THEN產(chǎn)生溢出并終止算法；

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頁，創(chuàng)作于2023年2月CU與X的比較。操作CU=U+X’+1實(shí)際上實(shí)現(xiàn)了兩個(gè)功能：顯式的功能是減法U–X，而隱含的功能是U和X的比較。如果U≥X，該操作將C置1，否則將C置0。如下所示：在（a）和（b）中，U≥X，C置1；在（c）中，U<X，C置0。圖8.8在計(jì)算CU=U+X’+1的同時(shí)比較了U和X：（a）正結(jié)果，（b）零結(jié)果，（c）負(fù)結(jié)果第39頁，課件共108頁，創(chuàng)作于2023年2月整個(gè)算法的分析。頭兩條語句是比較U和X的大小。如果U≥X，將產(chǎn)生溢出，此時(shí)U←U+X’+1將C置1。否則不溢出，它將C置0。第二條語句是將U恢復(fù)為原來值，如果沒有溢出，將初始化Y并進(jìn)入移位—相減循環(huán)。

移位—相減循環(huán)從左移CUV和Y開始的。而第一條IF語句（IFC=1THENU=U+X’+1ELSECU=U+X’+1）實(shí)現(xiàn)了減法（U=U–X）和CU與X的比較（如果CU≥X則C=1）。

下一條IF語句（IFC=1THENY0=1ELSEU=U+X）當(dāng)C=1時(shí)，CU≥X，減法有效，只需在商的相應(yīng)位（Y0）上商1。而當(dāng)C=0時(shí)，CU<X，加法將U恢復(fù)為原來值。如C=1，則CU一定比X大，執(zhí)行減法U←U+X’+1，并且使C仍保持1值。如C=0，執(zhí)行減法CU←U+X’+1。該減法僅當(dāng)CU≥X時(shí)，使C置1。結(jié)果是：無論執(zhí)行哪個(gè)減法，都有U=U–X，以及當(dāng)CU≥X時(shí)C置1，否則置0。第40頁，課件共108頁，創(chuàng)作于2023年2月兩個(gè)例子。第一個(gè)例子為225÷13，它的執(zhí)行步驟如表8.9（a）所示。首先初始化X=1101，n=4。第一個(gè)減法將C置1，說明將產(chǎn)生溢出。（實(shí)際上，由于225÷13=17余4，而17的二進(jìn)制是10001，因此不能存于4位的寄存器中。）下一步恢復(fù)U值并終止算法。表8.9恢復(fù)余數(shù)除法算法的執(zhí)行步驟（a）有溢出，

另一個(gè)例子147÷13，執(zhí)行步驟如表8.9（b）所示。沒有溢出。算法的前幾步檢測(cè)溢出和初始化Y。接下來每三步為一組表示循環(huán)的一次迭代。第41頁，課件共108頁，創(chuàng)作于2023年2月該算法正確地計(jì)算了147÷13(X=1101)，商為11，余數(shù)為4。表8.9恢復(fù)余數(shù)除法算法的執(zhí)行步驟（b）無溢出

每次迭代都執(zhí)行相似的移位和減法/比較操作。每次迭代的最后一步不是更新商（保存在Y中）就是將余數(shù)恢復(fù)為原來值（保存在U中）。第42頁，課件共108頁，創(chuàng)作于2023年2月恢復(fù)余數(shù)除法算法的RTL代碼。它采用的值與不恢復(fù)余數(shù)算法中采用的值基本相同。它與不恢復(fù)余數(shù)算法非常接近?！馩VERFLOW為1位值，當(dāng)溢出發(fā)生時(shí)置1，否則置0?！馞INISH為1位值，當(dāng)算法終止時(shí)置1。不管是循環(huán)結(jié)束的正常終止還是溢出，都要將FINISH置1?！衽c其他算法相同，計(jì)數(shù)器i的值從n遞減到0。當(dāng)i=0時(shí)，Z=1。●除非遇到GOTO操作，在正常情況下狀態(tài)從11--12—2—3--41--42。第43頁，課件共108頁，創(chuàng)作于2023年2月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產(chǎn)生溢出并終止算法；

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頁，創(chuàng)作于2023年2月表8.10恢復(fù)余數(shù)除法算法的RTL代碼的執(zhí)行步驟147÷13第45頁，課件共108頁，創(chuàng)作于2023年2月該算法的硬件實(shí)現(xiàn)如圖所示。減少了產(chǎn)生G的比較器，但并行加法器的輸入更加復(fù)雜。因?yàn)榇藭r(shí)要求它進(jìn)行兩種操作U+X或U–X。同時(shí)，由于有6個(gè)狀態(tài)，狀態(tài)計(jì)數(shù)器和譯碼器要稍微大一些。圖8.9恢復(fù)余數(shù)除法的硬件實(shí)現(xiàn)42i第46頁，課件共108頁，創(chuàng)作于2023年2月補(bǔ)碼相除

補(bǔ)碼相除沒有一種通用的算法。一般是通過對(duì)正負(fù)數(shù)值進(jìn)行轉(zhuǎn)換來實(shí)現(xiàn)補(bǔ)碼相除。該算法如下所示。除法可以使用恢復(fù)余數(shù)的硬件實(shí)現(xiàn)或不恢復(fù)余數(shù)的硬件實(shí)現(xiàn)。IF被除數(shù)

<0THEN被除數(shù)←

-被除數(shù)；

IF除數(shù)

<0THEN除數(shù)←

-除數(shù)；

使用恢復(fù)余數(shù)（或不恢復(fù)余數(shù)的）硬件實(shí)現(xiàn)除法運(yùn)算；

IF被除數(shù)和除數(shù)中有一個(gè)為負(fù)數(shù)THEN結(jié)果←-結(jié)果第47頁，課件共108頁，創(chuàng)作于2023年2月8.2帶符號(hào)表示法符號(hào)—幅值表示法（signed_magnitudenotation）符號(hào)—補(bǔ)碼表示法（signed_two’scomplementnotation）8.2.1符號(hào)—幅值表示法（signed_magnitudenotation）

包括兩個(gè)部分：符號(hào)部分為1位，0表示正數(shù)（或0），1表示負(fù)數(shù)；幅值部分為n位，以非負(fù)數(shù)碼的形式表示數(shù)的絕對(duì)值。

用XsX表示符號(hào)—幅值表示法，其中Xs為1位的符號(hào)值，X為n位幅值。

例如：+3和-3有相同的幅值3，僅僅符號(hào)不同。在二進(jìn)制中，+3表示為0（符號(hào)）0011，而-3表示為1（符號(hào)）0011。第48頁，課件共108頁，創(chuàng)作于2023年2月8.2.1.1加法和減法

操作UsU←XsX±YsY，定義AS為計(jì)算操作符。AS=0表示加，=1表示減。還定義PM=Xs⊕AS⊕Ys。Xs、AS和Ys共有8種可能的組合。下表列出這些組合及其相應(yīng)的PM值，同時(shí)分別給出了當(dāng)X=3，Y=5和X=5，Y=3時(shí)這8種組合的結(jié)果。表8.11符號(hào)—幅值數(shù)據(jù)的加法和減法第49頁，課件共108頁，創(chuàng)作于2023年2月

執(zhí)行何種操作由兩個(gè)值決定：PM的值以及X和Y的相對(duì)幅值，相對(duì)幅值表示是X>Y、X=Y還是X<Y。分兩種情況考慮：PM=0和PM=1。

第一種情況：PM=0

將X和Y的幅值加在一起；結(jié)果的符號(hào)總與第一個(gè)操作數(shù)的符號(hào)Xs相同。通過微操作Us←Xs，U←X+Y實(shí)現(xiàn)。

結(jié)合考慮溢出情況，可以用CU←X+Y代替U←X+Y，并將C的值賦給溢出標(biāo)志。

因此PM=0時(shí)符號(hào)—幅值表示加減法的RTL代碼為：

PM’1：Us←Xs，CU←X+YPM’2：OVERFLOW←C第50頁，課件共108頁，創(chuàng)作于2023年2月第二種情況：PM=1X和Y相對(duì)幅值的問題。當(dāng)X>Y時(shí)，U應(yīng)為X–Y，即X+Y’+1。當(dāng)X<Y時(shí)，X–Y將產(chǎn)生期望值Y–X的負(fù)數(shù)，該值必須取反；可通過取其2的補(bǔ)碼，或（X–Y）’

+1來實(shí)現(xiàn)。減法CU←X+Y’+1同時(shí)也實(shí)現(xiàn)了X與Y的比較，通過C，可以判斷是否要將結(jié)果（X–Y）取負(fù)。

0結(jié)果問題。當(dāng)X=Y時(shí)，執(zhí)行CU←X+Y’+1，得U=0且C=1。因0總是做為+0保存，要將結(jié)果的符號(hào)設(shè)置為0。X≠Y時(shí)結(jié)果的符號(hào)問題。從表8.11中發(fā)現(xiàn)，X>Y時(shí)，Us與Xs的值相同；X<Y時(shí)，Us與Xs的反碼相同。第51頁，課件共108頁，創(chuàng)作于2023年2月PM=1時(shí)符號(hào)—幅值表示加減法的RTL代碼。注意，當(dāng)X>Y時(shí)，C=1，Z=0；當(dāng)X=Y時(shí)，C=1，Z=1；當(dāng)X<Y時(shí)，C=0。另外將OVERFLOW設(shè)置為0，因?yàn)镻M=1時(shí)不可能發(fā)生溢出。

PM1：CU←X+Y’+1，OVERFLOW←0CZ’PM2：Us←XsCZPM2：Us←0C’PM2：Us←Xs’，U←U’+1●CZ’為真時(shí)（C=1且Z=0，即X>Y），U中已保存了結(jié)果的正確幅值（X–Y）。此時(shí)僅需要考慮結(jié)果的符號(hào)，即把Xs賦給Us。●CZ為真時(shí)（C=1且Z=1，即X=Y），U中也已保存了結(jié)果的正確幅值0。此時(shí)僅需要把結(jié)果的符號(hào)設(shè)置為0，使結(jié)果以+0的格式保存。●C’為真時(shí)（C=0，即X<Y），保存在U中的值（X–Y）必須取反才為結(jié)果的正確幅值（Y–X），并且結(jié)果的符號(hào)為Xs的反碼。第52頁，課件共108頁，創(chuàng)作于2023年2月完整的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

為了說明這個(gè)算法，表8.12列出了當(dāng)XsX和YsY取不同值時(shí)，RTL代碼的執(zhí)行過程。它包括了沒有產(chǎn)生溢出時(shí)的四種可能情況：PM=0、PM=1且X>Y、PM=1且X=Y、PM=1且X<Y，以及產(chǎn)生溢出時(shí)的兩種可能情況。第53頁，課件共108頁，創(chuàng)作于2023年2月表8.12符號(hào)—幅值表示法的加減法舉例第54頁，課件共108頁，創(chuàng)作于2023年2月圖8.10符號(hào)—幅值加減法的硬件實(shí)現(xiàn)第55頁，課件共108頁，創(chuàng)作于2023年2月8.2.1.2乘法和除法

符號(hào)—幅值表示法的乘除法與非負(fù)數(shù)碼的乘除法幾乎完全相同，唯一不同的是它必須設(shè)置結(jié)果的符號(hào)。

對(duì)計(jì)算CU←X×Y的非負(fù)數(shù)碼移位—相加乘法算法稍加修改，就可以得到下列RTL代碼，它進(jìn)行符號(hào)—幅值數(shù)據(jù)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

當(dāng)UV=0時(shí)T=1，否則T=0。當(dāng)i=0時(shí)，Z=1。第56頁，課件共108頁，創(chuàng)作于2023年2月下表列出了該RTL代碼執(zhí)行（-13）×（+11）的步驟。表8.13符號(hào)—幅值的移位—相加乘法的RTL代碼軌跡類似于無符號(hào)非負(fù)數(shù)碼乘法13×11，唯一不同的是多了設(shè)置結(jié)果符號(hào)Us和Vs的操作。第57頁，課件共108頁，創(chuàng)作于2023年2月該RTL代碼的硬件實(shí)現(xiàn)。（略）

除法可采用恢復(fù)余數(shù)算法或不恢復(fù)余數(shù)算法實(shí)現(xiàn)。與乘法相同，它也必須考慮結(jié)果的符號(hào)。因此乘法的RTL代碼中所做的修改同樣適用于除法的RTL代碼。修改后的除法RTL代碼。（略）第58頁，課件共108頁，創(chuàng)作于2023年2月8.2.2符號(hào)—補(bǔ)碼表示法

類似于符號(hào)—幅值表示法，符號(hào)—補(bǔ)碼表示法也包括1位的符號(hào)和n位的幅值，它同樣被表示為XsX。唯一不同的是其負(fù)數(shù)的幅值采用2的補(bǔ)碼表示。+5和–3的符號(hào)—補(bǔ)碼表示分別為：0（符號(hào)）0101和1（符號(hào)）1101

符號(hào)—補(bǔ)碼表示法的幅值部分等價(jià)于無符號(hào)表示法中的補(bǔ)碼。

為了加減兩個(gè)符號(hào)—補(bǔ)碼表示的數(shù)據(jù)，我們簡單地把符號(hào)位當(dāng)成幅值的最高位。例如，不將+5表示為0（符號(hào)）0101，而是簡單地將其看成5位的值00101；第59頁，課件共108頁，創(chuàng)作于2023年2月

這樣，可以把符號(hào)—補(bǔ)碼表示法的加減法轉(zhuǎn)換為無符號(hào)補(bǔ)碼的加減法。不過注意要使用（n+1）位的補(bǔ)碼。把符號(hào)位看成幅值的最高位的另一個(gè)好處是：在執(zhí)行補(bǔ)碼加減法的同時(shí)能得出結(jié)果的符號(hào)。此時(shí)的溢出判斷同補(bǔ)碼加減法的溢出判斷相同，即當(dāng)最高位的進(jìn)位輸入和進(jìn)位輸出不相等時(shí)產(chǎn)生溢出。注意此時(shí)的最高位為符號(hào)位。

乘法也可以采用相同的方式實(shí)現(xiàn)。一旦把符號(hào)位看成它們的相對(duì)幅值的最高位，我們就能采用booth’s算法實(shí)現(xiàn)數(shù)據(jù)的乘法。除法也可以通過類似的方法，修改無符號(hào)補(bǔ)碼除法來實(shí)現(xiàn)。第60頁，課件共108頁，創(chuàng)作于2023年2月8.3BCD碼（binarycodeddecimal）

上一節(jié)介紹的帶符號(hào)表示是用二進(jìn)制位來表示二進(jìn)制數(shù)。這種表示的存儲(chǔ)效率最高，因?yàn)槊恳槐忍囟急硎疽粋€(gè)唯一有效的值。但在某些應(yīng)用中，直接使用十進(jìn)制來存儲(chǔ)和運(yùn)算將更為適合。例如，一個(gè)數(shù)字鐘的應(yīng)用，它的輸出必須總是表示為十進(jìn)制數(shù)，但內(nèi)部元件可以采用二進(jìn)制計(jì)時(shí)。此時(shí)如能使用一序列十進(jìn)制數(shù)的存儲(chǔ)格式，將可免去進(jìn)制轉(zhuǎn)換的麻煩。

用來表示十進(jìn)制數(shù)的最常用格式是BCD碼（binarycodeddecimal，“以二進(jìn)制編碼的十進(jìn)制”，簡稱BCD）。本節(jié)將討論BCD碼的格式，及其加、減、乘、除算法和相應(yīng)的硬件實(shí)現(xiàn)。第61頁，課件共108頁，創(chuàng)作于2023年2月8.3.1BCD碼的格式BCD碼用4位等值的二進(jìn)制數(shù)表示一個(gè)十進(jìn)制數(shù)字。例如，0000表示0，1001表示9。BCD碼中不使用大于9的4位二進(jìn)制數(shù)，從1010到1111。n位的十進(jìn)制數(shù)用n組4位二進(jìn)制數(shù)保存。例如，27被存為00100111（在二進(jìn)制中，它被存為00011011）。BCD碼是一種帶符號(hào)表示法，它的值可以為正也可以為負(fù)或0。類似于符號(hào)—幅值表示法，它有兩個(gè)部分：1位用于表示符號(hào)，而幅值部分保存數(shù)的絕對(duì)值。例如:+27:0（符號(hào)）00100111

–27:1（符號(hào)）00100111第62頁，課件共108頁，創(chuàng)作于2023年2月8.3.2加法和減法BCD碼與符號(hào)—幅值表示法僅有兩個(gè)不同，只要對(duì)這兩個(gè)不同進(jìn)行修改，就可以得到BCD碼加減法的算法。

首先要改變硬件以適應(yīng)BCD碼的加法。若BCD碼的兩個(gè)數(shù)字之和大于9，要將二進(jìn)制加法器產(chǎn)生的結(jié)果加6以得到正確的結(jié)果。圖8.11顯示了兩個(gè)BCD數(shù)字相加產(chǎn)生正確BCD碼結(jié)果和進(jìn)位的硬件（一位BCD加法器）。

例如，5+6=0101+0110=1011（無效數(shù)字）。8+9=1000+1001=1（進(jìn)位）0001，即11。

第二個(gè)修改是對(duì)補(bǔ)碼進(jìn)行修改。BCD碼的反碼是9的補(bǔ)碼。例如：二進(jìn)制U＝1010，則U’＝1111－1010＝0101BCD碼的反碼可以通過將999…

…99（n個(gè)9）減去自身獲得。將其加1可得到10的補(bǔ)碼，在BCD碼中，用來表示原值的負(fù)數(shù)。第63頁，課件共108頁，創(chuàng)作于2023年2月圖8.11一位BCD加法器

如果Adder1的輸出S3S2S1S0是無效的BCD數(shù)字，必有S3∧S2=1或S3∧S1=1,即1010～1111；或X+Y產(chǎn)生進(jìn)位，此時(shí)Cout1=1。在這兩種情況下，多路復(fù)用器的控制位置1，使得6（0110）與S3S2S1S0相加，從而得到正確結(jié)果。

兩個(gè)數(shù)字X和Y首先加在一起，然后加0或加6產(chǎn)生正確的BCD碼和。第64頁，課件共108頁，創(chuàng)作于2023年2月

下圖為一個(gè)1位BCD數(shù)的9的補(bǔ)碼生成器。將多個(gè)該硬件相連就可以得到一個(gè)多位BCD數(shù)的9的補(bǔ)碼生成器。圖8.129的補(bǔ)碼生成器例如，631的9的補(bǔ)碼為999–631=368，而10的補(bǔ)碼為368+1=369。正如二進(jìn)制中2的補(bǔ)碼用于減法或取負(fù)運(yùn)算一樣，10的補(bǔ)碼在BCD碼中發(fā)揮同樣的作用。第65頁，課件共108頁，創(chuàng)作于2023年2月

經(jīng)過以上兩個(gè)修改，二進(jìn)制的符號(hào)—幅值表示法的加減算法可以用于BCD碼的加減法中：

使用BCD加法器代替二進(jìn)制并行加法器。使用9的補(bǔ)碼生成器產(chǎn)生Y’（在條件PM1下）和U’（在條件C’PM2下）。由于Xs為1位，在條件C’PM2下，Xs實(shí)際上是通過反向器而不是通過9的補(bǔ)碼生成器得出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頁，創(chuàng)作于2023年2月

表中列出了取不同值時(shí)，RTL代碼的執(zhí)行過程。包括各種PM值、X>Y、X=Y和X<Y的情況。還有溢出的兩個(gè)例子。表8.14BCD數(shù)的加減法的舉例第67頁，課件共108頁，創(chuàng)作于2023年2月BCD加減法的硬件實(shí)現(xiàn)如圖所示。圖8.13BCD加減法的硬件實(shí)現(xiàn)第68頁，課件共108頁，創(chuàng)作于2023年2月8.3.2乘法和除法

雖然BCD的乘除法與符號(hào)—幅值表示法的乘除法很相似，但與BCD的加減法相比，BCD的乘除法要做更多的修改。上節(jié)介紹的BCD加法器和9的補(bǔ)碼生成器在BCD乘除法中同樣需要。

在BCD中，乘數(shù)的每一位可能為0～9中的任何一個(gè)數(shù)字，因此每次循環(huán)迭代最多可能要執(zhí)行9次加法。因此在算法中要增加一個(gè)內(nèi)循環(huán)來實(shí)現(xiàn)多次加法。

采用十進(jìn)制移位，每次移1位BCD數(shù)字，即每次移4位。十進(jìn)制右移操作記為dshr

。每次循環(huán)可能執(zhí)行多次加法，因此進(jìn)位Cd采用1位BCD數(shù)而不是1位二進(jìn)制數(shù)。第69頁，課件共108頁，創(chuàng)作于2023年2月

根據(jù)以上修改，我們可以把二進(jìn)制符號(hào)—幅值表示法的移位—相加乘法算法轉(zhuǎn)換成等價(jià)的BCD碼乘法算法。實(shí)現(xiàn)BCD乘法UsUV←XsX×YsY的RTL代碼如下所示。n為Y的十進(jìn)制數(shù)的位數(shù)。Yd0為Y的BCD數(shù)據(jù)的最低位，或最低4位。當(dāng)Yd0=0時(shí)，ZY0=1；當(dāng)i=0時(shí)，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決定內(nèi)循環(huán)次數(shù)，當(dāng)Yd0＝0時(shí)，ZY0＝1。狀態(tài)3要用十進(jìn)制線性右移dshr。第70頁，課件共108頁，創(chuàng)作于2023年2月

表中列出了一個(gè)BCD乘法71×23的執(zhí)行步驟。該RTL代碼的硬件實(shí)現(xiàn)。（略）表8.15BCD移位—相加乘法的執(zhí)行軌跡

除法可以采用恢復(fù)余數(shù)算法和不恢復(fù)余數(shù)算法。類似乘法，這里也要增加一個(gè)內(nèi)循環(huán)實(shí)現(xiàn)多次減法。除法的RTL代碼及其硬件實(shí)現(xiàn)。（略）第71頁，課件共108頁，創(chuàng)作于2023年2月8.4專用運(yùn)算部件

提高計(jì)算速度的專用運(yùn)算部件有：流水線、查找表和Wallace樹乘法器，以及在歷史視角中討論的協(xié)處理器。8.4.1流水線

算術(shù)流水線類似于工廠的裝配線。數(shù)據(jù)進(jìn)入某段流水線，該段流水線對(duì)數(shù)據(jù)執(zhí)行算術(shù)操作；然后將結(jié)果傳給下一段，下一段又執(zhí)行它的操作；如此等等，直到最后的計(jì)算被執(zhí)行。

流水線不能提高單個(gè)計(jì)算的速度。額外開銷實(shí)際延長了單個(gè)計(jì)算的執(zhí)行時(shí)間。但通過重疊計(jì)算，即能同時(shí)在各個(gè)段處理不同的數(shù)據(jù)，流水線可以提高整體性能。

流水線提高了吞吐量（throughput），即每單位時(shí)間生成結(jié)果的數(shù)量。第72頁，課件共108頁，創(chuàng)作于2023年2月考慮下面一行代碼：

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

假設(shè)每個(gè)加法和乘法的完成時(shí)間均為10ns。非流水線單處理器計(jì)算每個(gè)A[i]要20ns，完成整行代碼要2000ns。一個(gè)流水線單元將A[i]的計(jì)算分為兩段，如圖所示，第一段執(zhí)行乘法，第二段執(zhí)行加法。注意，鎖存器用來保存流水線每一段的輸出。流水線完成整行代碼只需1010ns。

第一個(gè)10ns，第一段執(zhí)行乘法B[1]×C[1]。第二個(gè)10ns，第二段將該值加到D[1]并把結(jié)果保存在A[1]中，同時(shí)第一段執(zhí)行下一個(gè)乘法B[2]×C[2]。第三個(gè)10ns，第一段計(jì)算B[3]×C[3]，第二段求出A[2]的值。第73頁，課件共108頁，創(chuàng)作于2023年2月

用吞吐量和加速比（speedup）來衡量一個(gè)流水線的性能。加速比Sn為一個(gè)非流水線運(yùn)算單元完成n個(gè)計(jì)算的時(shí)間與一個(gè)k段流水線完成相同計(jì)算的時(shí)間之比。

定義T1為一個(gè)非流水線運(yùn)算單元每得出一個(gè)計(jì)算結(jié)果所需要的時(shí)間，它為該非流水線的時(shí)鐘周期。Tk為一個(gè)k段流水線的時(shí)鐘周期。如果每段具有不同的最小時(shí)鐘周期，或段延時(shí)，則Tk取其中最大的周期。在上例中，T1=20ns，Tk=10ns。

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

(k+n–1)Tk

非流水線每隔T1時(shí)間產(chǎn)生一個(gè)結(jié)果，完成n個(gè)計(jì)算所需時(shí)間為n*T1。k段流水線在產(chǎn)生第一個(gè)結(jié)果之前要經(jīng)過k個(gè)流水段，每個(gè)流水段需要Tk時(shí)間。其余的數(shù)據(jù)每個(gè)時(shí)鐘周期都進(jìn)入流水線，每個(gè)時(shí)鐘周期生成一個(gè)計(jì)算結(jié)果。因此完成n個(gè)計(jì)算共需（k+n–1）個(gè)時(shí)鐘周期。第74頁，課件共108頁，創(chuàng)作于2023年2月

對(duì)前例，流水線的加速比為：S100=nT1=100×20ns=1.98

(k+n–1)Tk(2+100–1)×10nsn趨向于無窮大時(shí)可得穩(wěn)態(tài)加速比的計(jì)算公式：

S∞=T1/Tk

當(dāng)流水線每段延時(shí)相等時(shí)，可以得到最大加速比：

S∞=T1=T1=k

Tk(T1/k)

如果每段流水線的延時(shí)不等，則有些段的延時(shí)小于T1/k，有些大于T1/k。由于Tk為最大的延時(shí)，因此Tk>T1/k，降低了加速比。鑒于此，應(yīng)該使每段流水線的延時(shí)盡可能相等，從而提高加速比。第75頁，課件共108頁，創(chuàng)作于2023年2月

實(shí)際上，鎖存器需要一定的時(shí)間來保存數(shù)據(jù)。這是流水線的額外開銷。對(duì)前例，若鎖存器的延時(shí)為2ns，則實(shí)際加速比為：S100=nT1=100×20ns=1.65

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

若只計(jì)算一個(gè)值A(chǔ)[1]，則加速比小于1：S1=nT1=1×20ns=0.83

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

此時(shí)流水線的速度實(shí)際上比非流水線的低，這是因?yàn)槊慷瘟魉€都增加了鎖存器的延時(shí)。

以上是基本的流水線技術(shù)。在11章中我們將看到，流水線也用于加快CPU中的取指令，指令譯碼和執(zhí)行指令。第76頁，課件共108頁，創(chuàng)作于2023年2月8.4.2查找表

理論上，每一組合電路都可通過將ROM配置成查找表來實(shí)現(xiàn)：組合電路的輸入數(shù)據(jù)作為該ROM的輸入地址，而組合電路的輸出結(jié)果作為該地址中保存的數(shù)據(jù)。對(duì)組合電路的任何輸入，通過編程，ROM都能輸出正確的結(jié)果。

例如，用一個(gè)4×1的ROM來模擬一個(gè)2輸入的與門。下圖給出了該與門和它等價(jià)的查找表。與門的輸入作為ROM的輸入地址，而ROM的輸出數(shù)據(jù)對(duì)應(yīng)于與門的輸出。通過編程ROM，對(duì)于所有可能的X和Y，ROM的輸出與與門的完全相同。第77頁，課件共108頁，創(chuàng)作于2023年2月

用查找表ROM計(jì)算UV←X×Y的實(shí)現(xiàn)方法如圖所示。寄存器X和Y提供查找表的輸入地址，查找表的輸出數(shù)據(jù)為X與Y的積，它被輸入到寄存器UV中。U、V、X、Y均為4位的寄存器，X與Y的積為8比特?cái)?shù)據(jù)，因此共需要256個(gè)地址來保存所有的積。例如，地址10111101保存數(shù)據(jù)10001111，即143，它是1011（11）與1101（13）的積。圖8.16用查找表實(shí)現(xiàn)的乘法器第78頁，課件共108頁，創(chuàng)作于2023年2月

很多算法可以通過查找表ROM來實(shí)現(xiàn)，而且與前面的算法實(shí)現(xiàn)相比，查找表可能更具有優(yōu)勢(shì)。例如，圖8.16給出的硬件實(shí)現(xiàn)比圖8.5給出的移位—相加的硬件實(shí)現(xiàn)更簡單，執(zhí)行速度更快。隨著操作數(shù)位數(shù)的增加，查找ROM的大小將迅速增大。實(shí)現(xiàn)4位乘法器的ROM大小為256×8，而等價(jià)的8位乘法器將需要64K×16的ROM。8.4.3Wallace樹Wallace樹是用來實(shí)現(xiàn)兩數(shù)相乘的一種組合電路。盡管與移位—相加的乘法器相比，所需的元器件要多一些，但它的運(yùn)行速度要快得多。Wallace樹使用幾個(gè)進(jìn)位保存加法器和僅僅一個(gè)并行加法器實(shí)現(xiàn)乘法。第79頁，課件共108頁，創(chuàng)作于2023年2月

進(jìn)位保存加法器能同時(shí)執(zhí)行三數(shù)相加，而不是兩數(shù)加。它不是輸出一個(gè)結(jié)果，而是輸出一個(gè)和S以及一組進(jìn)位位，如圖。由于進(jìn)位位通過加法器沒有延時(shí)，因此它比并行加法器要快。它不生成最終和。圖8.17一個(gè)進(jìn)位保存加法器

每位Si是位Xi、Yi、Zi的二進(jìn)制和，進(jìn)位位Ci+1是該和產(chǎn)生的進(jìn)位。要得到最終和，必須將S和C相加。

例如，X=0111，Y=1011，Z=0010，進(jìn)位保存加法器將輸出和S=1110，進(jìn)位C=00110。

用一個(gè)并行加法器將S與C相加，就可以求出最終結(jié)果10100（20），即0111（7）+1011（11）+0010（2）的和。注意，因?yàn)樵诋a(chǎn)生Si同時(shí)產(chǎn)生Ci+1，與S相比，C必須左移一位。第80頁，課件共108頁，創(chuàng)作于2023年2月

為了使用進(jìn)位保存加法器實(shí)現(xiàn)乘法，首先求出每一個(gè)部分積，再將這些部分積輸入到進(jìn)位保存加法器中，例如：x=111y=110000←PP0111←PP1111←PP2101010←求出的最終和

根據(jù)Y的每一位為1還是為0，部分積選擇X或0并左移到正確的位置。

本例中，因?yàn)镻P2為Y2的部分積，要將X的值111左移2位，即PP2實(shí)際為11100。類似的，由于PP1為Y1的部分積，要左移1位。

圖8.18給出了為本例生成部分積的一種方法。第81頁，課件共108頁，創(chuàng)作于2023年2月圖8.18用Wallace樹生成乘法的部分積第82頁，課件共108頁，創(chuàng)作于2023年2月

可以用一個(gè)5位的進(jìn)位保存加法器對(duì)部分積PP0、PP1、PP2進(jìn)行加法。然后用一個(gè)并行加法器將輸出S和C相加，就可以得到X與Y的最終乘積。下圖給出了該乘法的硬件實(shí)現(xiàn)。圖8.19用進(jìn)位保存加法器實(shí)現(xiàn)3×3的乘法器第83頁，課件共108頁，創(chuàng)作于2023年2月

圖8.19給出的是一個(gè)最小Wallace樹，不能完整的說明Wallace樹的設(shè)計(jì)原則。下圖給出兩個(gè)4位數(shù)相乘的Wallace樹的設(shè)計(jì)。

考慮乘法1011×1110。它產(chǎn)生部分積PP0=0000000，PP1=0010110，PP2=0101100，PP3=1011000。第一個(gè)進(jìn)位保存加法器的輸出為：S=0111010，C=00001000。第二個(gè)進(jìn)位保存加法器的輸出為：S=01101010，C=000110000。并行加法器輸出最終積：10011010。第一個(gè)進(jìn)位保存加法器實(shí)現(xiàn)PP0、PP1、PP2的加法；第二個(gè)進(jìn)位保存加法器將PP3與S和C相加；最后通過一個(gè)并行加法器輸出積。圖8.204×4的Wallace樹乘法器0第84頁，課件共108頁，創(chuàng)作于2023年2月

部分積的個(gè)數(shù)隨著乘數(shù)位數(shù)的增加而增加。因此當(dāng)乘數(shù)位數(shù)較大時(shí)，Wallace樹可以利用并行操作。圖中給出兩個(gè)8位數(shù)相乘的Wallace樹。圖8.218×8的Wallace樹乘法器第85頁，課件共108頁，創(chuàng)作于2023年2月8.5浮點(diǎn)數(shù)

定點(diǎn)數(shù)僅能表示整數(shù)而不能表示小數(shù)，計(jì)算機(jī)用浮點(diǎn)數(shù)來表示小數(shù)。8.5.1數(shù)據(jù)格式

浮點(diǎn)數(shù)的格式類似于科學(xué)記數(shù)法。一個(gè)數(shù)在科學(xué)記數(shù)法中包含：符號(hào)，小數(shù)或有效值（也叫尾數(shù)）和指數(shù)（通常叫階）。例如，數(shù)–1234.5678可以表示為–1.2345678×103，其中符號(hào)為負(fù)號(hào)，有效值為1.23456789，指數(shù)為3。在這個(gè)例子中采用10作為基數(shù)，計(jì)算機(jī)一般都以2為基數(shù)表示浮點(diǎn)數(shù)。

必須對(duì)浮點(diǎn)數(shù)進(jìn)行規(guī)格化，即浮點(diǎn)數(shù)的有效值是一個(gè)沒有前導(dǎo)0的小數(shù)。于是–1234.567就只有一個(gè)有效的浮點(diǎn)表達(dá)：–.1234567×104，而不能是–1.234567×103或–1234567.×10-3。規(guī)格化第86頁，課件共108頁，創(chuàng)作于2023年2月

0不能被規(guī)格化。要用一個(gè)特殊值表示0，在運(yùn)算中，還要把0做為特殊情況處理。類似的，正無窮大和負(fù)無窮大也要用一個(gè)特殊值來表示，并且也需要特殊處理。

另外，非法操作，如∞/∞或?qū)ω?fù)數(shù)開平方，我們稱其結(jié)果為不存在的數(shù)，記為NaN。NaN也要用一個(gè)特殊值來表示，在浮點(diǎn)數(shù)算法中NaN也要求特殊處理。特殊值

浮點(diǎn)數(shù)格式。每個(gè)浮點(diǎn)數(shù)包括1位符號(hào)，定長的有效值和階。浮點(diǎn)數(shù)X記為XSXFXE

，其中XS表示符號(hào)，XF表示有效值，XE表示階。例如，值–1234.5678（=–.12345678×104）被保存為XS=1，XF=12345678，XE=4。

因?yàn)槊總€(gè)數(shù)據(jù)都以正常格式存儲(chǔ)，因此它隱含表示基數(shù)點(diǎn)位于有效值的最高有效位的左邊，并且不需要明確地表示出來。浮點(diǎn)數(shù)格式第87頁，課件共108頁，創(chuàng)作于2023年2月

階沒有符號(hào)位，階值可用補(bǔ)碼表示，但最好是用移碼。階的移碼是在實(shí)際階值上加一個(gè)偏移量，其和被保存在階中。假設(shè)XE有四位，它可以表示從–8到7的所有階碼，將實(shí)際階值加一個(gè)偏移量8，其和保存在XE中，則最小階值–8的移碼為–8+8=0或二進(jìn)制的0000，最大階值7的移碼為7+8=15=1111。

二進(jìn)制表示的規(guī)格化浮點(diǎn)數(shù)（除了0、+/-∞、NaN）的有效值的最高位為1，在有效值寄存器中可以不保存該位。移碼第88頁，課件共108頁，創(chuàng)作于2023年2月8.5.2數(shù)據(jù)性質(zhì)

精度表示浮點(diǎn)數(shù)的精確性，定義為有效值的位數(shù)。若計(jì)算機(jī)規(guī)定浮點(diǎn)數(shù)的有效值為8位，則它的精度為8位。有效值的位數(shù)越多，CPU的精度越高，表示的數(shù)據(jù)越精確。許多計(jì)算機(jī)中有兩種浮點(diǎn)數(shù)格式：單精度浮點(diǎn)數(shù)和雙精度浮點(diǎn)數(shù)。雙精度浮點(diǎn)數(shù)的位數(shù)是單精度浮點(diǎn)數(shù)的兩倍。

間距為兩個(gè)相鄰值的差的絕對(duì)值。其大小由階值的大小決定。例如，浮點(diǎn)數(shù)：.10111010×23，它的2個(gè)相鄰值為：.10111011×23和