計(jì)組計(jì)算機(jī)組成原理

1、第 八 章 運(yùn) 算 方 法 本章我們?cè)敿?xì)說明幾種常用數(shù)據(jù)格式的算術(shù)運(yùn)算算法和它們的硬件實(shí)現(xiàn)。包括定點(diǎn)數(shù)表示及其加、減、乘、除過程和硬件實(shí)現(xiàn)，二十進(jìn)制（或BCD）碼的格式和操作。 接下來討論一些提高算術(shù)操作性能的專用硬件，包括流水線、查找表、華萊士樹 。 最后介紹浮點(diǎn)數(shù)的格式和它們的算術(shù)操作。包括浮點(diǎn)數(shù)的格式，性質(zhì)，以及加、減、乘、除過程和硬件實(shí)現(xiàn)，還有IEEE 754 浮點(diǎn)數(shù)標(biāo)準(zhǔn)。 執(zhí)行算術(shù)和邏輯運(yùn)算的指令以及微操作是任何CPU的一個(gè)必不可少的重要部分。 8.1 無符號(hào)表示法 本節(jié)討論二進(jìn)制數(shù)無符號(hào)表示法的加、減、乘、除的基本算法以及實(shí)現(xiàn)這些算法的硬件。這些算法同時(shí)也是二進(jìn)制數(shù)帶符號(hào)表示法、B

2、CD碼和浮點(diǎn)表示法的算術(shù)運(yùn)算基礎(chǔ)。非負(fù)數(shù)碼：表示0或一個(gè)正數(shù)。n位非負(fù)數(shù)碼的數(shù)值范圍為0（所有位都為0）到2n-1（所有位都為1）。2的補(bǔ)碼（簡(jiǎn)稱補(bǔ)碼）：既能表示正數(shù)又能表示負(fù)數(shù)。n位數(shù)的數(shù)值范圍為 -2n-1-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ǔ)碼，簡(jiǎn)稱為反碼），加1。 有兩種常用的無符號(hào)表示法： 例如，求-5的4位補(bǔ)碼表示，首先求出它的絕對(duì)值5（0101），產(chǎn)生反碼值1010，再加1得補(bǔ)碼1011。 下表列出了8位二進(jìn)制數(shù)的非負(fù)數(shù)碼和補(bǔ)碼表示的數(shù)值。

3、表8.1 無符號(hào)表示的數(shù)值 8.1.1 加法和減法 加法直接采用二進(jìn)制加法實(shí)現(xiàn)，硬件中通過使用一個(gè)并行加法器來實(shí)現(xiàn)，如下圖所示。 X和Y是8位寄存器，該電路實(shí)現(xiàn)微操作 ADD：XX+Y。 只要結(jié)果在正常范圍內(nèi)（對(duì)非負(fù)數(shù)碼而言為0到2n-1，對(duì)2的補(bǔ)碼而言為-2n-1-1到2n-1-1），該電路就能得到正確的結(jié)果。 圖8.1 微操作XX+Y的實(shí)現(xiàn) 當(dāng)結(jié)果不能表示為一個(gè)8位數(shù)值時(shí)就會(huì)導(dǎo)致溢出：例如，非負(fù)數(shù)碼加法255 +1，即1111 1111 + 0000 0001，直接加得 1 0000 0000，有9位，不能存于8位寄存器中。 并行加法器產(chǎn)生額外的進(jìn)位輸出，它用來標(biāo)志算術(shù)溢出。在非負(fù)數(shù)碼中，

4、這個(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)生溢出。見下圖：圖8.2 補(bǔ)碼加法的溢出產(chǎn)生 在（a）和（c）中最高位的進(jìn)位輸入和進(jìn)位輸出相等，不產(chǎn)生溢出；而在（b）和（d）中兩者不等，產(chǎn)生溢出。 減法可以轉(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：XXY的一種硬件實(shí)現(xiàn)。圖8.3 微操作XXY的實(shí)現(xiàn) 對(duì)于

5、非負(fù)數(shù)碼，減法的結(jié)果不會(huì)比2n-1大，但可能比0小。例如，12執(zhí)行為0000 0001 = 1111 1111，即255。圖中（b）和（d）溢出，而（a）和（c）沒有溢出。 圖8.4 無符號(hào)2的補(bǔ)碼減法的溢出產(chǎn)生 同樣，補(bǔ)碼減法也將XY轉(zhuǎn)換成X +（Y）來執(zhí)行，而判斷溢出的條件與補(bǔ)碼加法相同。 此時(shí)，如果減法（通過補(bǔ)碼加法實(shí)現(xiàn)）產(chǎn)生了進(jìn)位輸出0而不是1時(shí)，則發(fā)生了溢出。8.1.2 乘法 乘法可以看成加法的重復(fù)。一個(gè)數(shù)乘以n與n個(gè)該數(shù)相加的結(jié)果相同?？梢杂孟铝兴惴▉韺?shí)現(xiàn)乘法xy。 z = 0； FOR i = 1 TO y DO z = z + x 這種算法不理想，原因是速度慢、計(jì)算xy的時(shí)間不

6、確定。我們希望不論x 、y取何值，執(zhí)行乘法的時(shí)間相同。 x = 2 7 y = 2 5 3 8 1 1 3 5 5 4 6 8 3 1 考慮人工計(jì)算： 首先，27乘以乘數(shù)y 的最低位3。接著，27乘以乘數(shù)y 的次低位5，結(jié)果放在前一個(gè)積的左邊一位處，因?yàn)槌藬?shù)5在3的左一位上。然后，27乘以2，結(jié)果進(jìn)一步左移一位。最后，將所有值加在一起。 這個(gè)過程被稱為移位相加乘法。首先計(jì)算每個(gè)部分積并左移到正確位置，然后再將所有的部分積相加。 對(duì)這個(gè)算法稍做修改，使得硬件實(shí)現(xiàn)更為簡(jiǎn)單，就可得到無符號(hào)非負(fù)二進(jìn)制數(shù)的乘法基本算法。 第一個(gè)修改是每求出一個(gè)部分積后就計(jì)算和： x = 2 7 y = 2 5 3 8

7、1 1 3 5 1 4 3 1 計(jì)算的和 5 4 6 8 3 1 最終計(jì)算的和 因?yàn)橛布?，二輸入加法器很容易?shí)現(xiàn)，而三輸入或多輸入的加法器則變得非常復(fù)雜。 任何時(shí)候都沒有多于兩個(gè)數(shù)的加。 注意：每一個(gè)部分積都逐次左移一位，因此排列的位置不同。在當(dāng)前和與部分積的相加中，某些位的運(yùn)算不必要。 第二個(gè)修改用右移當(dāng)前和代替左移部分積： x = 27 y = 253 81 右移一位 81 1被右移出，故不參加加法運(yùn)算 135 1431 右移一位 1431 3 1被右移出，故不參加加法運(yùn)算 54 6831 最后右移一位 6831 每次都是相同的兩列數(shù)字進(jìn)行加法。已經(jīng)右移到這兩列右邊的數(shù)字只是簡(jiǎn)單的寫下，

8、不進(jìn)行加法。 若用二進(jìn)制，被乘數(shù)不是乘以0就是乘以1，因此部分積不是0（X0 = 0）就是被乘數(shù)的值（X1 = X）。 下面算法實(shí)現(xiàn)兩個(gè)n位寄存器的值X和Y的移位相加乘法，結(jié)果保存在兩個(gè)n位寄存器U和V中，其中U保存結(jié)果的高n位，V保存結(jié)果的低n位。C是一位寄存器，用來保存執(zhí)行加法時(shí)的進(jìn)位。 U = 0； FOR i = 1 TO n DO IF Y0 = 1 THEN CU = U + X； 線性右移 CUV； 循環(huán)右移 Y 考慮乘法1311，即11011011，表8.2 列出了運(yùn)行該算法時(shí)所有寄存器的值。初始化X = 1101，Y = 1011。容易驗(yàn)證該算法得出了正確結(jié)果。 表8.2 移

9、位相加算法的執(zhí)行步驟 算法的RTL代碼如下所示。注意：當(dāng)i = 0時(shí)，Z = 1；而1，2，3是連續(xù)的狀態(tài)，即算法是由狀態(tài)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代碼的執(zhí)行步驟。同樣初始化X = 1101，Y = 1011。除了在每個(gè)周期增加了滿足的條件和執(zhí)行的微操作外，表8.3同表8.2一樣。 表8.3 移位相加乘法RTL代碼的執(zhí)行軌跡 根據(jù) RTL代碼設(shè)計(jì)硬件。硬件包括兩個(gè)部分：寄存器部分，微操作在此執(zhí)行；控制部分，產(chǎn)生需要的控制信號(hào)和狀

10、態(tài)值。 為了簡(jiǎn)化設(shè)計(jì)，我們用n位寄存器實(shí)現(xiàn)X；n位移位寄存器實(shí)現(xiàn)Y、U、V，當(dāng)SHR信號(hào)有效時(shí)它們右移一位。寄存器i是有足夠位數(shù)來存儲(chǔ)值n的遞減計(jì)數(shù)器。C和FINISH用一位寄存器實(shí)現(xiàn)。在寄存器之間設(shè)置數(shù)據(jù)通路來實(shí)現(xiàn)RTL代碼中的微操作所要求的數(shù)據(jù)傳送。 將i的所有位異或在一起產(chǎn)生Z，即僅當(dāng)i的所有位都為0（i = 0）時(shí)，Z才為1。這比比較i和n的大小要簡(jiǎn)單，并且只需要一個(gè)異或門，而不是一個(gè)n位比較器，這就是i從n到0遞減計(jì)數(shù)而不是從0到n遞增計(jì)數(shù)的原因。 圖8.5給出了移位相加乘法算法的硬件實(shí)現(xiàn)。 圖8.5 移位相加乘法算法的硬件實(shí)現(xiàn) 考察圖8.5給出的控制部分，看它是如何實(shí)現(xiàn)RTL代碼的

11、。 當(dāng)START置1時(shí)，State Counter和FINISH清零，Decoder工作。Decoder輸出1，使U清零，數(shù)n裝載到i中。 State Counter加1到01， Decoder輸出2。使i減1，并且，若Y0 = 1，將U + X保存在CU中；若Y0 = 0，則C、U的值不變。 State Counter加1到10， Decoder輸出3。此時(shí)，C、U、V都右移一位。以下兩件事必有一件發(fā)生：當(dāng)Z = 0時(shí)，State Counter被裝載值01， Decoder輸出2，實(shí)現(xiàn)操作“GOTO 2”。否則Z = 1時(shí)，F(xiàn)INISH置1，Decoder使能端置0，不再輸出1，2，3，硬

12、件停止工作。 如果不要求保存原值，則可以進(jìn)一步優(yōu)化算法，使硬件實(shí)現(xiàn)更簡(jiǎn)單。特別是如果Y值不要求保存，可將其值保存在V寄存器中，則乘法轉(zhuǎn)換為UVX V。每次檢查V的最低位V0，若為1，執(zhí)行加法。下一步執(zhí)行右移時(shí)，該位將丟棄，因?yàn)樗辉傩枰褂?。修改后的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信號(hào)改為V02，以及去掉了寄存器Y之外，該代碼的硬件實(shí)現(xiàn)與圖8.5的相同。 下表顯示改

13、進(jìn)后的RTL代碼執(zhí)行13 11的步驟。表8.4 改進(jìn)后的RTL代碼的執(zhí)行步驟 除了初始化V寄存器和去掉Y寄存器之外，該表與表8.3相同。 8.1.2.1 布斯算法 對(duì)于無符號(hào)補(bǔ)碼數(shù)據(jù)，上面的算法并不總能得出正確的結(jié)果。上一個(gè)例子（ 13 11 ）中，1101 和1011的補(bǔ)碼表示分別為3和-5，它們的積應(yīng)是+15；而上面的算法將得出結(jié)果1000 1111，即 113，顯然是錯(cuò)的。 原因是該算法僅能處理兩個(gè)正數(shù)相乘，當(dāng)有一個(gè)或兩個(gè)操作數(shù)為負(fù)數(shù)時(shí)，通過執(zhí)行下面的程序，上面的算法仍然可以使用： IF 被乘數(shù) 0 THEN 被乘數(shù) - 被乘數(shù)； IF 乘數(shù) 71，商至少有3位，比商寄存器的位數(shù)（2位）

14、還要多一位，因此產(chǎn)生溢出。 這種溢出檢測(cè)的附加好處是可以防止除以0的操作，此時(shí)也會(huì)產(chǎn)生溢出。 采用二進(jìn)制更簡(jiǎ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 X THEN 產(chǎn)生溢出并終止算法； Y = 0；C = 0； FOR i = 1 TO n DO 線性右移 CUV； 線形右移 Y； IF CU X THEN Y0 = 1，U = CU X 考慮第一步就終止的情況。如1127，若n =

15、4，則UV = 0111 0000，X = 0111。由于UX，均為0111，將終止算法。如果繼續(xù)執(zhí)行，將產(chǎn)生商16（1 0000）和余數(shù)0。但值1 0000不能保存在4位的Y中，產(chǎn)生溢出。 下表列出了該算法執(zhí)行14713的步驟。初始化時(shí)，U = 1001，V = 0011，X = 1101，n = 4。 表8.7 移位相減算法的執(zhí)行步驟 算法的RTL代碼。其中X、U、V、Y為n位值，C和OVERFLOW為1位值。當(dāng)i = 0時(shí)，Z = 1；當(dāng)UX時(shí)，G = 1。FINISHI置1則算法結(jié)束。1，2，3，4是連續(xù)的狀態(tài)。 G 1： FINISH1，OVERFLOW1 2： Y0，C0，OVER

16、FLOW0，in 3： shl(CUV)，shl(Y)，ii-1（C + G）4： Y0 1，UU + X + 1 Z4： GOTO 3 Z 4： FINISH1 大部分的RTL語(yǔ)句由算法直接轉(zhuǎn)換而成，注意條件 CUX等價(jià)于條件 UX（G）或（C =1），即（C + G）；補(bǔ)碼加法：U U + X + 1實(shí)現(xiàn)算法中的U = CU X 。 下表列出了該RTL代碼執(zhí)行除法：14713的執(zhí)行步驟。初始化時(shí)U = 1001，V = 0011，X = 1101，n = 4。 表8.8 移位相減除法的RTL代碼的執(zhí)行步驟 該算法的硬件實(shí)現(xiàn)。圖8.7 移位相減除法的硬件實(shí)現(xiàn) 以上稱為不恢復(fù)余數(shù)的除法算法，這

17、種算法是僅當(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ù)為原來值。 恢復(fù)余數(shù)的算法。被除數(shù)初始化時(shí)

18、保存在UV中，除數(shù)保存在X中，商保存在Y中，余數(shù)最后保存在U中。U、V、X、Y都是n位值，C是1位值。 CU = U + X + 1； U = U + X，IF C = 1 THEN 產(chǎn)生溢出并終止算法； 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的比較如C = 1，則CU一定比X大，執(zhí)行減法U U + X + 1，并且使C仍保持1值，表示CU X。如C = 0，執(zhí)行減法CU

19、U + X + 1。該減法僅當(dāng)CU X時(shí)，使C置1。結(jié)果是：無論執(zhí)行哪個(gè)減法，都有U = U X，以及當(dāng)CU X時(shí)C置1，否則置0。CU與X的比較。 操作C U = U + X + 1實(shí)際上實(shí)現(xiàn)了兩個(gè)功能：顯式的功能是減法U = U X ，而隱含的功能是U和X的比較。如果U X，該操作將C置1，否則將C置0。 在（a）和（b）中，C置1，表示U X； 在（c）中，C置0，表示U X。 圖8.8 在計(jì)算C U = U + X + 1的同時(shí)比較了U和X：（a）正結(jié)果，（b）零結(jié)果，（c）負(fù)結(jié)果 整個(gè)算法的分析。 頭兩條語(yǔ)句是比較U和X的大小。如果U X，將產(chǎn)生溢出，此時(shí)U U + X + 1將C置

20、1。否則不溢出，它將C置0。第二條語(yǔ)句是將U恢復(fù)為原來值，如果沒有溢出，將初始化Y并進(jìn)入移位相減循環(huán)。 移位相減循環(huán)從左移CUV和Y 開始的。而下一條語(yǔ)句實(shí)現(xiàn)了減法（U = U X）和CU與X的比較（如果CU X則C = 1）。 下一條語(yǔ)句當(dāng)C = 1時(shí)，CU X，減法有效，不需要恢復(fù)余數(shù)，只需在商的相應(yīng)位（Y0）上商1。而當(dāng)C = 0時(shí)，CU X，加法將U恢復(fù)為原來值。 如C = 1，則CU一定比X大，執(zhí)行減法U U + X + 1，并且使C仍保持1值，表示CU X。如C = 0，執(zhí)行減法CU U + X + 1。該減法僅當(dāng)CU X時(shí)，使C置1。結(jié)果是：無論執(zhí)行哪個(gè)減法，都有U = U X，

21、以及當(dāng)CU X時(shí)C置1，否則置0。兩個(gè)例子。 第一個(gè)例子為22513，它的執(zhí)行步驟如表8.9（a）所示。首先初始化X = 1101，n = 4。第一個(gè)減法將C置1，說明將產(chǎn)生溢出。（實(shí)際上，由于22513 = 17 余4，而17的二進(jìn)制是1 0001，因此不能存于4位的寄存器中。）下一步恢復(fù)U值并終止算法。 表8.9 恢復(fù)余數(shù)除法算法的執(zhí)行步驟（a）有溢出， 另一個(gè)例子14713，執(zhí)行步驟如表8.9（b）所示。沒有溢出。算法的前幾步檢測(cè)溢出和初始化Y。接下來每三步為一組表示循環(huán)的一次迭代。該算法正確地計(jì)算了14713，結(jié)果是：商為11，余數(shù)為4。 表8.9 恢復(fù)余數(shù)除法算法的執(zhí)行步驟（b）無溢

22、出 每次迭代都執(zhí)行相似的移位和減法 / 比較操作。 每次迭代的最后一步不是更新商（保存在Y中）就是將余數(shù)恢復(fù)為原來值（保存在U中）。恢復(fù)余數(shù)除法算法的RTL代碼。 它采用的值與不恢復(fù)余數(shù)算法中采用的值基本相同。除了以下幾點(diǎn)，它與不恢復(fù)余數(shù)算法非常接近。 OVERFLOW為1位值，當(dāng)溢出發(fā)生時(shí)置1，否則置0。 FINISH為1位值，當(dāng)算法終止時(shí)置1。不管是循環(huán)結(jié)束的正常終止還是溢出，都要將FINISH置1。這與本章其他算法的RTL代碼是相同的。 與其他算法相同，計(jì)數(shù)器i的值從n遞減到0。當(dāng)i = 0時(shí)，Z = 1。 除非遇到GOTO操作，在正常情況下狀態(tài)從11到12到2到3到41到42。狀態(tài)11

23、和12等價(jià)于不恢復(fù)余數(shù)算法中的狀態(tài)1，而狀態(tài)41和42等價(jià)于不恢復(fù)余數(shù)算法中的狀態(tài)4。 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 RTL代碼。 表8.10列出了該RTL代碼執(zhí)行除法14713的步驟。它與表8.9（b）類似，同樣得出正確結(jié)果。 表8.10 恢復(fù)余數(shù)除法算法的RTL代碼的執(zhí)

24、行步驟 該算法的硬件實(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) 補(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ù) 0 THEN 被除數(shù) - 被除數(shù)； IF 除數(shù) Y、X = Y還是X Y時(shí)，U應(yīng)為X Y ，即X + Y + 1。當(dāng)X Y時(shí)，Us與Xs的值相同；X Y時(shí)，C = 1，Z = 0；當(dāng)X = Y時(shí)，C = 1，Z

25、 = 1；當(dāng)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、PM = 1且X = Y、PM = 1且X Y、X = Y和X T1 / k，降低了加速比。鑒于此，應(yīng)該使每段流水線的延時(shí)盡可能相等，從而提高加速比。 實(shí)際上，鎖存器需要一定的時(shí)間來保存數(shù)據(jù)。這是流水線的額外開銷。對(duì)前例，若鎖存器的延時(shí)為2 ns，則實(shí)際加速比為： S100 = n T1 = 10020ns =1.6

26、5 (k + n 1) Tk (2 + 100 1)12ns 若只計(jì)算一個(gè)值A(chǔ)1，則加速比小于1： S1 = n T1 = 120ns =0.83 (k + n 1) Tk (2 + 1 1)12ns 此時(shí)流水線的速度實(shí)際上比非流水線的低，這是因?yàn)槊慷瘟魉€都增加了鎖存器的延時(shí)。 以上是基本的流水線技術(shù)。在11章中我們將看到，流水線也用于加快CPU中的取指令，指令譯碼和執(zhí)行指令。 8.4.2 查找表 理論上，每一組合電路都可通過將ROM配置成查找表來實(shí)現(xiàn)：組合電路的輸入數(shù)據(jù)作為該ROM的輸入地址，而組合電路的輸出結(jié)果作為該地址中保存的數(shù)據(jù)。對(duì)組合電路的任何輸入，通過編程，ROM都能輸出正確的結(jié)

27、果。 例如，用一個(gè)41的ROM來模擬一個(gè)2輸入的與門。下圖給出了該與門和它等價(jià)的查找表。 與門的輸入作為ROM的輸入地址，而ROM的輸出數(shù)據(jù)對(duì)應(yīng)于與門的輸出。通過編程ROM，對(duì)于所有可能的X和Y，ROM的輸出與與門的完全相同。 用查找表ROM計(jì)算UVXY的實(shí)現(xiàn)方法如圖所示。寄存器X和Y提供查找表的輸入地址，查找表的輸出數(shù)據(jù)為X與Y的積，它被輸入到寄存器UV中。 U、V、X、Y均為4位的寄存器，X與Y 的積為8比特?cái)?shù)據(jù)，因此共需要256個(gè)地址來保存所有的積。例如，地址1011 1101保存數(shù)據(jù)1000 1111，即143，它是1011（11）與1101（13）的積。 圖8.16 用查找表實(shí)現(xiàn)的乘

28、法器 很多算法可以通過查找表ROM來實(shí)現(xiàn)，而且與前面的算法實(shí)現(xiàn)相比，查找表可能更具有優(yōu)勢(shì)。例如，圖8.16給出的硬件實(shí)現(xiàn)比圖8.5給出的移位相加的硬件實(shí)現(xiàn)更簡(jiǎn)單，執(zhí)行速度更快。 隨著操作數(shù)位數(shù)的增加，查找ROM的大小將迅速增大。實(shí)現(xiàn)4位乘法器的ROM大小為2568，而等價(jià)的8位乘法器將需要64K16的ROM。 8.4.3 Wallace樹 Wallace樹是用來實(shí)現(xiàn)兩數(shù)相乘的一種組合電路。盡管與移位相加的乘法器相比，所需的元器件要多一些，但它的運(yùn)行速度要快得多。Wallace樹使用幾個(gè)進(jìn)位保存加法器和僅僅一個(gè)并行加法器實(shí)現(xiàn)乘法。 進(jìn)位保存加法器能同時(shí)執(zhí)行三數(shù)相加，而不是兩數(shù)加。它不是輸出一個(gè)結(jié)

29、果，而是輸出一個(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必須左移一位。 為了使用進(jìn)位保存加法器實(shí)現(xiàn)乘法

30、，首先求出每一個(gè)部分積，再將這些部分積輸入到進(jìn)位保存加法器中，例如： x = 111 y = 110 000 PP0 111 PP1 111 PP2 101010 求出的最終和 根據(jù)Y的每一位為1還是為0，部分積選擇X或0并左移到正確的位置。 本例中，因?yàn)镻P2為Y2的部分積，要將X的值111左移2位，即PP2實(shí)際為11100。類似的，由于PP1為Y1的部分積，要左移1位。 圖8.18給出了為本例生成部分積的一種方法。 圖8.18 用Wallace樹生成乘法的部分積 可以用一個(gè)5位的進(jìn)位保存加法器對(duì)部分積PP0、PP1、PP2進(jìn)行加法。然后用一個(gè)并行加法器將輸出S和C相加，就可以得到X與Y的最

31、終乘積。下圖給出了該乘法的硬件實(shí)現(xiàn)。 圖8.19 用進(jìn)位保存加法器實(shí)現(xiàn)33的乘法器 圖8.19給出的是一個(gè)最小Wallace樹，不能完整的說明Wallace樹的設(shè)計(jì)原則。下圖給出兩個(gè)4位數(shù)相乘的Wallace樹的設(shè)計(jì)。 考慮乘法10111110。它產(chǎn)生部分積PP0 = 000 0000，PP1 = 001 0110，PP2 = 010 1100，PP3 = 101 1000。第一個(gè)進(jìn)位保存加法器的輸出為：S = 011 1010，C = 0000 1000。第二個(gè)進(jìn)位保存加法器的輸出為：S = 0110 1010，C = 0 0011 0000。并行加法器輸出最終積：1001 1010。 第一

32、個(gè)進(jìn)位保存加法器實(shí)現(xiàn)PP0、PP1、PP2的加法；第二個(gè)進(jìn)位保存加法器將PP3 與S和C相加；最后通過一個(gè)并行加法器輸出積。 圖8.20 44的Wallace樹乘法器 部分積的個(gè)數(shù)隨著乘數(shù)位數(shù)的增加而增加。因此當(dāng)乘數(shù)位數(shù)較大時(shí)，Wallace樹可以利用并行操作。圖中給出兩個(gè)8位數(shù)相乘的Wallace樹。 圖8.21 88的Wallace樹乘法器 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.2

33、345678103，其中符號(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á)：.1234567104，而不能是1.234567103或1234567.10-3。規(guī)格化 0不能被規(guī)格化。要用一個(gè)特殊值表示0，在運(yùn)算中，還要把0做為特殊情況處理。 類似的，正無窮大和負(fù)無窮大也要用一個(gè)特殊值來表示，并且也需要特殊處理。 另外，非法操作，如/或?qū)ω?fù)數(shù)開平方，我們稱其結(jié)果為不存在的數(shù)，記為NaN。NaN也要用一個(gè)特殊值來表示，在浮

34、點(diǎn)數(shù)算法中NaN也要求特殊處理。特殊值 浮點(diǎn)數(shù)格式。每個(gè)浮點(diǎn)數(shù)包括1位符號(hào)，定長(zhǎng)的有效值和階。浮點(diǎn)數(shù)X記為XSXFXE ，其中XS表示符號(hào)，XF表示有效值，XE表示階。例如，值1234.5678（= 1.2345678104 ）被保存為XS = 1，XF = 12345678，XE = 4。 因?yàn)槊總€(gè)數(shù)據(jù)都以正常格式存儲(chǔ)，因此它隱含表示基數(shù)點(diǎn)位于有效值的最高有效位的左邊，并且不需要明確地表示出來。浮點(diǎn)數(shù)格式 階沒有符號(hào)位，階值可用補(bǔ)碼表示，但最好是用移碼。階的移碼是在實(shí)際階值上加一個(gè)偏移量，其和被保存在階中。 假設(shè)XE有四位，它可以表示從8到7的所有階碼，將實(shí)際階值加一個(gè)偏移量8，其和保存在X

35、E中，則最小階值8的移碼為 8 + 8 = 0 或二進(jìn)制的 0000，最大階值7的移碼為7 + 8 = 15 = 1111。 二進(jìn)制表示的規(guī)格化浮點(diǎn)數(shù)（除了0、+/- 、NaN）的有效值的最高位為1，在有效值寄存器中可以不保存該位。移碼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ù)格式：?jiǎn)尉雀↑c(diǎn)數(shù)和雙精度浮點(diǎn)數(shù)。雙精度浮點(diǎn)數(shù)的位數(shù)是單精度浮點(diǎn)數(shù)的兩倍。 間距為兩個(gè)相鄰值的差的絕對(duì)值。其大小由階值的大小決定。例如，浮點(diǎn)數(shù)：.1011 101023

36、，它的2個(gè)相鄰值為：.1011 101123和.1011 100123，間距為：.0000 000123 = 2-5。浮點(diǎn)數(shù)X的間距可以表示為2（X E precision）。 浮點(diǎn)數(shù)固有特性 范圍由浮點(diǎn)數(shù)格式所能表示的最大值和最小值決定。例如，一個(gè)有8位有效值（假設(shè)首位1也保存在有效值寄存器中）和4位階碼（表示階值 8 7）的浮點(diǎn)數(shù)的范圍為 .1111 111127 .1111 111127 ，即 127.5 +127.5。 例如，某浮點(diǎn)數(shù)格式，有1位符號(hào)位，8位階且偏移量為128，23位有效值（類似于IEEE 754 單精度浮點(diǎn)數(shù)）。則精度為23位，范圍為 .111 1111 1111 1

37、111 1111 11112127 .111 1111 1111 1111 1111 11112127，或1.7 1038 +.71038。間距由實(shí)際的浮點(diǎn)數(shù)決定，對(duì) .12127，間距為2（127 23）= 2104；對(duì) .1 2-128，間距為2（-128 23）= 2 -151。 舉例 當(dāng)浮點(diǎn)數(shù)操作所產(chǎn)生的結(jié)果不能存于計(jì)算機(jī)的浮點(diǎn)寄存器時(shí)，就發(fā)生了溢出。對(duì)有8位有效值和4位階（偏移量為8）的浮點(diǎn)數(shù)，浮點(diǎn)數(shù) .126 和 .125相乘將得積 .01211 = .1210，積的階值大于該格式所允許的最大階值7，因此產(chǎn)生了溢出。 溢出和下溢 溢出可為正或?yàn)樨?fù)，由溢出值的符號(hào)決定。溢出值可以處理

38、為+/- ，或NaN，或像定點(diǎn)數(shù)一樣置溢出標(biāo)志為1。 當(dāng)結(jié)果在0到最小正值或最小負(fù)值之間時(shí)，將產(chǎn)生下溢。例如，在上例格式中，執(zhí)行乘法（.12-6）（.12-5），所得結(jié)果為 .12 -12，它在0 與最小正值 .12 8之間，因此產(chǎn)生下溢。下溢也可以為正或?yàn)樨?fù)。下溢值可以處理為0，或者設(shè)置下溢標(biāo)志位。 當(dāng)操作結(jié)果有效值的位數(shù)太多而不能放入CPU的寄存器中（例如，8位有效值的浮點(diǎn)數(shù)相乘，得到16位有效值的積），此時(shí)必須將該值進(jìn)行舍入處理，使之能放入規(guī)定位數(shù)的有效值寄存器中。 就近舍入法（也稱為無偏舍入法）的目標(biāo)是使舍入后的結(jié)果盡可能接近實(shí)際值。例如，將值 .1011 0101舍入為4位，得到值

39、.1100。它的最大誤差為 +/- 0.5LSB（LSB為舍入后結(jié)果的最低有效位值）。舍入處理表8.16 不同舍入方法的比較 常見的舍入方法還有：截?cái)喾?、?+舍入法、朝 -舍入法。下表給出了數(shù)值在不同的舍入方法下的舍入結(jié)果。 除了“截?cái)喾ā保鞣N舍入法都要求在最終的表示之外增加額外的幾位，通常只要1、2位就足夠了。這些位的最高位稱為舍入位，次高位稱為保護(hù)位。在浮點(diǎn)數(shù)運(yùn)算的算法中，這些位是對(duì)結(jié)果的補(bǔ)充。第三位稱為粘滯位，粘滯位置1后，值就不再改變。 例如，（.101123）-（.110022），有效值分別為1011和1100，二者直接相減不能得出正確結(jié)果。由于減數(shù)的階比被減數(shù)的階小1，它的有效

40、值必須右移一位。本質(zhì)上，這種對(duì)齊是將減數(shù)由 .110022轉(zhuǎn)換為 .011023。只有當(dāng)操作數(shù)的階相等時(shí)，才能執(zhí)行有效值的相減。8.5.3 加法和減法 浮點(diǎn)數(shù)加減法與符號(hào)幅值表示加減法相似，但有兩個(gè)不同：首先要能檢測(cè)出操作數(shù)為0、或NaN以及結(jié)果為0或的情況。其次由于階可能不等，因此要能進(jìn)行有效值的對(duì)齊。 移位/對(duì)齊/相減（相加）的過程能處理大部分規(guī)格化浮點(diǎn)數(shù)的加減法。但當(dāng)操作數(shù)為0、或NaN時(shí)，浮點(diǎn)數(shù)算法必須對(duì)其單獨(dú)處理。 表中列出了對(duì)不同的操作數(shù)X和Y，UXY的執(zhí)行結(jié)果。當(dāng)X與Y相加時(shí)，AS = 0；相減時(shí)，AS = 1。 1、IF Y = 0，THEN UX0 = X，即UX， ELSE

41、 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 當(dāng)AS = 0時(shí)UY，否則U Y， ELSE 7、用常規(guī)的加減法步驟計(jì)算U。 上表根據(jù)以下規(guī)則求出：表8.17 對(duì)特殊形式的浮點(diǎn)數(shù)的操作結(jié)果 浮點(diǎn)加減算法。每一個(gè)值有3個(gè)寄存器：一個(gè)1位的符號(hào)寄存器（US），一個(gè)n位的有效值寄存器（UF）和一個(gè)m位的階碼寄存器（UE）。 （

42、IXNY + NX + ZY ）1：UX，F(xiàn)INISH1（NYZX ZY +IXIYNX）1：U(YSAS)YFYE，F(xiàn)INISH1 （IY NX + NXNY）1：UY，F(xiàn)INISH1 EXY2：shr(YF)，YEYE + 1，GOTO 2 EYX2：shr(XF)，XEXE + 1，GOTO 2 PM3：CUFXF + YF PM 3：CUFXF + YF + 1 3：USXS，UEXE，CE0 CPM 4：shr(CUF)，CEUEUE + 1 CE PM5：UUS PM 5：FINISH1 CPM 4：USUS，UFUF + 1 ZUCEUF(n 1) PM 5：shl(UF)，CE

43、UEUE 1，GOTO 5 (ZU + CE)PM 5：U0，F(xiàn)INISH1 CEUF(n 1)PM5：FINISH1 AS = 0表示加法，AS = 1表示減法，PM =XSASYS。REG（X或Y）= NaN時(shí)，NREG = 1；REG = 0時(shí)， ZREG = 1；REG = 時(shí)，IREG = 1。XE YE 時(shí)，EXY = 1；YE XE時(shí)，EYX = 1。 狀態(tài)1當(dāng)X或Y為特殊值（0、或NaN）時(shí)得出正確結(jié)果并終止算法。 狀態(tài)2對(duì)齊有效值。右移階值小的操作數(shù)的有效值，同時(shí)讓其階碼加1，直到兩階值相等。例如，X = .110125，Y = .100023 時(shí)，Y的有效值UF要右移2位，

44、同時(shí)Y的階碼將增加2。得YF = 0010，YE = 5，即 .001025。 狀態(tài)3執(zhí)行有效值加減，并設(shè)置結(jié)果的符號(hào)。這時(shí)算法分為兩種情況考慮。 當(dāng)PM = 0時(shí)，有效值相加。如果加法使C置1，則結(jié)果的形式為1.xxxx，此時(shí)必須將其有效值右移一位，并且階碼加1，使其規(guī)格化。如果這使得階碼溢出，則最終結(jié)果被置為，否則將得到正確結(jié)果。表8.18給出了（.110123）+（.111022）的執(zhí)行步驟（此時(shí)PM = 0）。 表8.18 執(zhí)行（X = .110123）+（Y = .111022）的RTL代碼軌跡 狀態(tài)1檢測(cè)操作數(shù)是否為特殊值，不執(zhí)行任何操作。 狀態(tài)2。由于XE YE ，因此EXY =

45、 1，將Y的有效值右移一位同時(shí)將Y的階碼加1。然后回到狀態(tài)2，重復(fù)操作直到階碼相等。這里循環(huán)一次就使得XE = YE 。當(dāng)XE = YE 時(shí)，EXY 和EXY 均為0，無操作，進(jìn)入狀態(tài)3。 由于PM = 0，狀態(tài)3執(zhí)行有效值相加。進(jìn)位C記錄溢出。設(shè)置結(jié)果符號(hào)、階碼，將CE 初始化為0。 狀態(tài)4檢查并且規(guī)格化結(jié)果形式為1.xxxx的情況。因C置1，因此進(jìn)行規(guī)格化，即有效值右移一位同時(shí)階碼加1到4。 規(guī)格化處理中可能產(chǎn)生溢出。但本例中并沒有發(fā)生，則狀態(tài)5 FNISH置1并終止算法。 最終（.110123）+（.111022）=（.101024），即6.5 + 3.5 =10。 PM = 0 當(dāng)PM

46、 = 1時(shí)，執(zhí)行有效值相減。若相減使C置0，則結(jié)果的有效值取負(fù)（UF UF + 1），符號(hào)取反（US US），在狀態(tài)4中進(jìn)行。狀態(tài)4結(jié)束時(shí)，結(jié)果的形式只可能為 .0 xxx或 .1xxx。 如果以0開頭（UF（n-1），則有效值左移一位同時(shí)階碼減1。重復(fù)這一操作，直到出現(xiàn)以下3種情況：UF（n-1）= 1、UF = 0、階值小于最小階（即CE = 1，下溢）。當(dāng)出現(xiàn)第一種情況時(shí)，結(jié)果完成規(guī)格化，得出正確結(jié)果并終止算法。當(dāng)出現(xiàn)其他兩種情況時(shí)，結(jié)果必須被置0。 表8.19給出了減法（.110123）（.111022）的執(zhí)行步驟。 該算法的硬件設(shè)計(jì)類似于符號(hào)幅值表示加減法算法的硬件設(shè)計(jì)。（略） 狀態(tài)

47、1檢查特殊值，狀態(tài)2對(duì)齊有效值。在狀態(tài)3執(zhí)行有效值相減并設(shè)置結(jié)果的符號(hào)和階。 若需要，在狀態(tài)4中要將結(jié)果取負(fù)，符號(hào)取反。但對(duì)于本例不必。 狀態(tài)5將結(jié)果規(guī)格化。對(duì)本例，有效值中只有一個(gè)先導(dǎo)0，因此只需進(jìn)行一次左移。當(dāng)算法回到狀態(tài)5時(shí)，已規(guī)格化，且階碼沒有下溢，算法完成。 最終（.110123）（.111022）=（.110022），即6.53.5 = 3。表8.19 執(zhí)行（X = .110123）（Y = .111022）的RTL代碼軌跡 PM = 18.5.4 乘法和除法 與符號(hào)幅值表示法一樣，浮點(diǎn)數(shù)乘法采用移位相加的算法實(shí)現(xiàn)，但要作修改。 首先檢測(cè)操作數(shù)是否為特殊值，接著通過有效值相乘和階值

48、相加實(shí)現(xiàn)乘法。同時(shí)檢查是否溢出和下溢。有效值相乘所得積的形式為 .1xxx或 .01xx。若為 .01xx，要規(guī)格化并重新檢查下溢。兩個(gè)規(guī)格化浮點(diǎn)數(shù)相乘，積的有效值不可能小于.01。在最糟的情況下，結(jié)果為 .1000.1000 = .01xx。 狀態(tài)1檢測(cè)操作數(shù)是否有特殊值（ 0、NaN和）并進(jìn)行相應(yīng)的處理。有則進(jìn)行特殊值處理后終止算法，否則設(shè)置結(jié)果的符號(hào)位和階。 若至少一個(gè)操作數(shù)為0，則結(jié)果為0；均不為0且至少有一個(gè)為NaN，則結(jié)果為NaN；均不為0和NaN且至少有一個(gè)為，則為，并設(shè)置符號(hào)。浮乘要點(diǎn) 積的階碼為兩操作數(shù)階碼之和。每個(gè)操作數(shù)階碼中都包含了偏移量，簡(jiǎn)單地加階碼將包含偏移量?jī)纱?。?/p>

49、此設(shè)置階碼時(shí)，將階碼之和減去一個(gè)偏移量才能得到積的正確階碼。 例如，（.110123）（.111022），偏移量為8，則兩個(gè)階碼的移碼分別為11（=3+8）和10（=2+8），相加得21，當(dāng)偏移量為8時(shí)，該移碼對(duì)應(yīng)于213（13 = 21 8），顯然積不可能在213附近，這個(gè)結(jié)果是錯(cuò)誤的。錯(cuò)誤的原因是偏移量被加了2次，一次在11中，一次在10中。從21中減去多余的偏移量得階碼13，對(duì)應(yīng)于25（5 = 13 8），這才是正確的階碼。 檢查階碼是否溢出和下溢。若溢出，則根據(jù)狀態(tài)1中得出的結(jié)果符號(hào)設(shè)結(jié)果為；若下溢，則置0。溢出或下溢到此終止算法。 有效值相乘。類似符號(hào)幅值表示采用移位相加算法。 最后，執(zhí)行規(guī)格化和舍入操作。由于可能下溢，算法重新檢查是否下溢，下溢則將結(jié)果置0。 算法RTL代碼。UR、UG、UT分別為寄存器U的舍入位、保護(hù)位和粘滯位。當(dāng)UE Y時(shí)產(chǎn)生溢出，但浮除在XF YF時(shí)不溢出，此時(shí)將XF 右移一位同時(shí)將階碼XE加1。接著設(shè)置結(jié)果的階碼，并執(zhí)行有效值相除（過