第3章 運算方法和運算部件

1、2022-2-7第一講第一講 不同層次程序員看到的運算及不同層次程序員看到的運算及ALU第二講第二講 定點數(shù)運算及其運算部件定點數(shù)運算及其運算部件第三講第三講 浮點數(shù)運算及其運算部件浮點數(shù)運算及其運算部件Ch3: Arithmetic and Logic Operate and ALU運算方法和運算部件運算方法和運算部件2022-2-7第一講：第一講：不同層次程序員看到的運算及不同層次程序員看到的運算及ALU主主 要要 內(nèi)內(nèi) 容容uC語言程序中涉及的運算語言程序中涉及的運算 整數(shù)算術運、浮點數(shù)算術運算整數(shù)算術運、浮點數(shù)算術運算 按位、邏輯、移位、位擴展和位截斷按位、邏輯、移位、位擴展和位截斷u

2、指令集中與運算相關的指令（指令集中與運算相關的指令（ 以以MIPS為參考為參考 ） 涉及到的定點數(shù)運算涉及到的定點數(shù)運算-算術運算算術運算帶符號整數(shù)運算：取負 / 符號擴展 / 加 / 減 / 乘 / 除 / 算術移位無符號整數(shù)運算：0擴展 / 加 / 減 / 乘 / 除 -邏輯運算邏輯運算邏輯操作：與 / 或 / 非 / 移位操作：邏輯左移 / 邏輯右移 涉及到的浮點數(shù)運算：加、減、乘、除涉及到的浮點數(shù)運算：加、減、乘、除u基本運算部件基本運算部件ALU的設計的設計2022-2-7C語言程序中涉及的運算語言程序中涉及的運算u算術運算（最基本的運算）算術運算（最基本的運算）無符號數(shù)、帶符號整數(shù)

3、、浮點數(shù)的運算無符號數(shù)、帶符號整數(shù)、浮點數(shù)的運算u按位運算按位運算用途用途-對對位串位串實現(xiàn)實現(xiàn)“掩碼掩碼”（mask）操作或相應的其他處理）操作或相應的其他處理（主要用于對（主要用于對多媒體數(shù)據(jù)或控制信息多媒體數(shù)據(jù)或控制信息進行處理）進行處理）操作操作-按位或：按位或：“|” 【功能：置【功能：置1 + 保持】保持】-按位與：按位與：“&” 【功能：置【功能：置0 + 保持】保持】-按位取反：按位取反：“”-按位異或：按位異或：“” 【功能：【功能： 取反取反 + 保持】保持】問題：如何從一個問題：如何從一個16位采樣數(shù)據(jù)位采樣數(shù)據(jù)y中提取高位字節(jié)，并使低字節(jié)中提取高位字節(jié)，并使低字

4、節(jié)為為0？可用可用“&”實現(xiàn)實現(xiàn)“掩碼掩碼”操作：操作：y & 0 xFF00例如，當例如，當y=0 x2C0B時，通過掩碼操作得到結果為：時，通過掩碼操作得到結果為：0 x2C002022-2-7C語言程序中涉及的運算語言程序中涉及的運算u邏輯運算邏輯運算用途用途-用于關系表達式的運算用于關系表達式的運算例如，例如，if （xy and iy) & (i100) then -“!”表示表示“NOT”運算運算 與按位運算的差別與按位運算的差別-符號表示不同：符號表示不同：& & ；| ； -運算過程不同：運算過程不同：按位按位 整體整體-結果類型不同：結

5、果類型不同：位串位串 邏輯值邏輯值2022-2-7C語言程序中涉及的運算語言程序中涉及的運算u移位運算移位運算用途用途-提取部分信息提取部分信息-擴大或縮小數(shù)值的擴大或縮小數(shù)值的2、4、8倍倍操作操作-左移左移:：xk-不區(qū)分是邏輯移位還是算術移位，由不區(qū)分是邏輯移位還是算術移位，由x的類型確定的類型確定：邏輯左移、邏輯右移：邏輯左移、邏輯右移高（低）位移出，低（高）位補0，可能溢出！問題：何時可能發(fā)生溢出？如何判斷溢出？ 答：若高位移出的是1，則左移時發(fā)生溢出-帶符號整數(shù)：算術左移、算術右移帶符號整數(shù)：算術左移、算術右移左移：高位移出，低位補0。可能溢出！ 溢出判斷：溢出判斷：若移出的位不等

6、于新的符號位，則溢出。若移出的位不等于新的符號位，則溢出。右移：低位移出，高位補符，可能發(fā)生數(shù)據(jù)丟失。2022-2-7C語言程序中涉及的運算語言程序中涉及的運算u位擴展和位截斷運算位擴展和位截斷運算用途用途-類型轉換時可能需要數(shù)據(jù)擴展或截斷類型轉換時可能需要數(shù)據(jù)擴展或截斷操作操作-沒有專門操作運算符，根據(jù)類型轉換沒有專門操作運算符，根據(jù)類型轉換前后數(shù)據(jù)長短確定是擴展還是截斷前后數(shù)據(jù)長短確定是擴展還是截斷-擴展擴展：短轉長短轉長 無符號數(shù)：無符號數(shù)：0擴展，前面補擴展，前面補0 帶符號整數(shù)：符號擴展，前面補符帶符號整數(shù)：符號擴展，前面補符-截斷：長轉短截斷：長轉短 強行將高位丟棄，故可能發(fā)生強行

7、將高位丟棄，故可能發(fā)生“溢出溢出”例例1：在大端機上輸出：在大端機上輸出si, usi, i, ui的十進制和的十進制和十六進制值是什么？十六進制值是什么？short si = -12345;unsigned short usi = si;int i = si;unsingned ui = usi ;si = -12345 CF C7usi = 53191 CF C7i = -12345 FF FF CF C7 ui = 53191 00 00 CF C7例例2：i和和j是否相等？是否相等？int i = 53191;short si = (short) i;int j = si;不相等！不相

8、等！i = 53191 00 00 CF C7si = -12345 CF C7 j = -12345 FF FF CF C7原因：對原因：對i截斷時發(fā)生了截斷時發(fā)生了“溢出溢出”，即：，即：53191截斷為截斷為16位數(shù)時，有效位數(shù)時，有效數(shù)據(jù)丟失，無法被正確數(shù)據(jù)丟失，無法被正確表示！表示！2022-2-7MIPS定點算術運算指令定點算術運算指令InstructionExampleMeaningCommentsadd add $1,$2,$3$1 = $2 + $33 operands; exception possiblesubtractsub $1,$2,$3$1 = $2 $33 op

9、erands; exception possibleadd immediateaddi $1,$2,100$1 = $2 + 100+ constant; exception possibleadd unsignedaddu $1,$2,$3$1 = $2 + $33 operands; no exceptionssubtract unsigned subu $1,$2,$3$1 = $2 $33 operands; no exceptionsadd imm. unsign. addiu $1,$2,100 $1 = $2 + 100+ constant; no exceptionsmulti

10、ply mult $2,$3Hi, Lo = $2 x $3 64-bit signed productmultiply unsigned multu$2,$3Hi, Lo = $2 x $3 64-bit unsigned productdivide div $2,$3Lo = $2 $3,Lo = quotient, Hi = remainder Hi = $2 mod $3 divide unsigned divu $2,$3Lo = $2 $3,Unsigned quotient & remainder Hi = $2 mod $3涉及到的操作數(shù)：涉及到的操作數(shù)：32/16位位

11、 無符號數(shù)，無符號數(shù)， 32/16位帶符號數(shù)帶符號數(shù)涉及到的操作：加涉及到的操作：加 / 減減 / 乘乘 / 除（有符號除（有符號 / 無符號）無符號）2022-2-7MIPS 邏輯運算指令邏輯運算指令涉及到的操作數(shù)：涉及到的操作數(shù)：32/16位位 邏輯數(shù)邏輯數(shù)涉及到的操作：按位與涉及到的操作：按位與 / 按位或按位或 / 按位或非按位或非 / 左移左移 / 右移右移2022-2-7MIPS定點比較和分支指令定點比較和分支指令涉及到的操作數(shù)：涉及到的操作數(shù)：32/16位位 無符號數(shù)，無符號數(shù)， 32/16位帶符號數(shù)帶符號數(shù)涉及到的操作：大小比較和相等比較（有符號涉及到的操作：大小比較和相等比較

12、（有符號 / 無符號）無符號）通過減法運算實現(xiàn)通過減法運算實現(xiàn)“比較比較”操作操作! !2022-2-7MIPS定點數(shù)據(jù)傳送指令定點數(shù)據(jù)傳送指令涉及到的操作數(shù)：涉及到的操作數(shù)： 32/16位帶符號數(shù)（偏移量可以是負數(shù)）帶符號數(shù)（偏移量可以是負數(shù)）涉及到的操作：加涉及到的操作：加 / 減減 / 符號擴展符號擴展 / 0擴展擴展 2022-2-7MIPS中的浮點算術運算指令中的浮點算術運算指令涉及到的浮點操作數(shù)：涉及到的浮點操作數(shù)： 32位單精度位單精度 / 64位雙精度浮點數(shù)位雙精度浮點數(shù)涉及到的浮點操作：加涉及到的浮點操作：加 / 減減 / 乘乘 / 除除 MIPS提供專門的浮點數(shù)寄存器：提供

13、專門的浮點數(shù)寄存器： 32個個32位單精度浮點數(shù)寄存器：位單精度浮點數(shù)寄存器：$f0, $f1, , $f31 連續(xù)兩個寄存器（一偶一奇）存放一個雙精度浮點數(shù)連續(xù)兩個寄存器（一偶一奇）存放一個雙精度浮點數(shù)2022-2-7MIPS中的浮點數(shù)傳送指令中的浮點數(shù)傳送指令涉及到的浮點操作數(shù)：涉及到的浮點操作數(shù)： 32位單精度浮點數(shù)位單精度浮點數(shù)涉及到的浮點操作：傳送操作（與定點傳送一樣）涉及到的浮點操作：傳送操作（與定點傳送一樣）還涉及到定點操作：加還涉及到定點操作：加 / 減（用于地址運算）減（用于地址運算） 例：將兩個浮點數(shù)從內(nèi)存取出相加后再存到內(nèi)存的指令序列為：例：將兩個浮點數(shù)從內(nèi)存取出相加后再

14、存到內(nèi)存的指令序列為： lwcl $f1, x($s1) lwcl $f2, y($s2) add.s $f4, $f1, $f2 swlc $f4, z(s3)2022-2-7MIPS中的浮點數(shù)比較和分支指令中的浮點數(shù)比較和分支指令涉及到的浮點操作數(shù)：涉及到的浮點操作數(shù)： 32 32位單精度浮點數(shù)位單精度浮點數(shù)/64/64位雙精度浮點數(shù)位雙精度浮點數(shù)涉及到的浮點操作：比較操作涉及到的浮點操作：比較操作（用（用 減法來實現(xiàn)比較）減法來實現(xiàn)比較）還涉及到的定點操作：加還涉及到的定點操作：加 / / 減（用于地址運算）減（用于地址運算） 有一個專門的浮點標志有一個專門的浮點標志cond，無需在指令

15、中明顯給出，無需在指令中明顯給出cond2022-2-7MIPS指令考察的結果指令考察的結果u涉及到的操作數(shù)：涉及到的操作數(shù)：無符號整數(shù)、帶符號整數(shù)無符號整數(shù)、帶符號整數(shù)邏輯數(shù)邏輯數(shù)浮點數(shù)浮點數(shù)u涉及到的運算涉及到的運算定點數(shù)運算定點數(shù)運算 帶符號整數(shù)運算：帶符號整數(shù)運算：取負取負 / 符號擴展符號擴展 / 加加 / 減減 / 乘乘 / 除除 / 算術移位算術移位 無符號整數(shù)運算：無符號整數(shù)運算：0擴展擴展 / 加加 / 減減 / 乘乘 / 除除 邏輯運算邏輯運算 邏輯操作：邏輯操作：與與 / 或或 / 非非 / 移位操作：移位操作：邏輯左移邏輯左移 / 邏輯右移邏輯右移浮點數(shù)運算：加、減、乘

16、、除浮點數(shù)運算：加、減、乘、除實現(xiàn)實現(xiàn)MIPS定點運算指令的思路：定點運算指令的思路：先實現(xiàn)一個能進行基本算術運算（加先實現(xiàn)一個能進行基本算術運算（加/減）和基本邏輯運算、并生成基本條減）和基本邏輯運算、并生成基本條件碼（件碼（ZF/OF/CF/NF）的）的ALU，再由，再由ALU和移位器實現(xiàn)乘、除運算器。和移位器實現(xiàn)乘、除運算器。ALU是運算部件的核心！以下介紹是運算部件的核心！以下介紹ALU的實現(xiàn)。的實現(xiàn)。2022-2-7ALU的功能說明的功能說明uALU Control Lines (ALUop) Function000 And001 Or010 Add110 Subtract111Se

17、t-on-less-thanALUNNNABResultOverflowZero3ALUopCarryOutALU可進行基本的加可進行基本的加/減減算術運算、基本邏輯運算算術運算、基本邏輯運算。其核心部件是加法器。其核心部件是加法器。有關串行加法器和并行加有關串行加法器和并行加法器的原理在數(shù)字邏輯電法器的原理在數(shù)字邏輯電路課已講過，在此僅簡單路課已講過，在此僅簡單回顧。回顧。2022-2-7回顧：串行進位加法器回顧：串行進位加法器假定與假定與/或門延遲為或門延遲為1ty，異或門，異或門3ty，則則“和和”與與“進位進位”的延遲為多少？的延遲為多少？FA全加器符號：全加器符號：串行加法器的缺點：

18、串行加法器的缺點：進位按串行方式傳遞，速度慢！進位按串行方式傳遞，速度慢！問題：問題：n位串行加法器從位串行加法器從C0到到Cn的的延遲時間為多少？延遲時間為多少？最后一位和數(shù)的延遲時間為多少？最后一位和數(shù)的延遲時間為多少？2n+1級門延遲！級門延遲！2n級門延遲！級門延遲！Sum延遲為延遲為6ty；Carryout延遲為延遲為2ty。FAFAFAn位串行位串行(行波行波)加法器：加法器：C0Cn2022-2-7回顧：并行進位加法器（回顧：并行進位加法器（CLA加法器）加法器）u為什么用先行進位方式？為什么用先行進位方式？ 串行進位加法器采用串行進位加法器采用串行逐級傳遞進位串行逐級傳遞進位，

19、電路延遲與位數(shù)成正比關系，電路延遲與位數(shù)成正比關系因此，現(xiàn)代計算機采用一種因此，現(xiàn)代計算機采用一種先行進位先行進位(Carry look ahead)方式方式。u如何產(chǎn)生先行進位？如何產(chǎn)生先行進位？ 定義輔助函數(shù)：定義輔助函數(shù)：Gi=XiYi進位生成函數(shù)進位生成函數(shù) Pi=Xi+Yi進位傳遞函數(shù)（或進位傳遞函數(shù)（或 Pi=Xi Yi ） 通常把實現(xiàn)上述邏輯的電路稱為通常把實現(xiàn)上述邏輯的電路稱為進位生成進位生成/傳遞部件傳遞部件 全加邏輯方程：全加邏輯方程：Si=Pi Ci Ci+1=Gi+PiCi (i=0,1,n) 設設n=4,則：則：C1=G0+P0C0 C2=G1+P1C1=G1+P1G

20、0+P1P0C0 C3=G2+P2C2=G2+P2G1+P2P1G0+P2P1P0C0 C4=G3+P3C3=G3+P3G2+P3P2G1+P3P2P1G0+P3P2P1P0C0 通常把實現(xiàn)上述邏輯的電路稱為通常把實現(xiàn)上述邏輯的電路稱為4位位CLA部件部件 通常把實現(xiàn)通常把實現(xiàn)Si=Pi Ci的電路稱為的電路稱為求和部件求和部件 CLA加法器由加法器由“進位生成進位生成/傳遞部件傳遞部件”、“CLA部件部件”和和“求和部件求和部件”構構成。成。 2022-2-7回顧：回顧： 8位全先行進位加法器位全先行進位加法器進位生成進位生成/ /傳遞部件傳遞部件A7A0B7B0P7P1P0G7G1G08位

21、位 CLA部件部件C0求和部件求和部件P7P1P0C0C1C7C8S7S0S13ty2ty3ty和的總延遲：和的總延遲：3+2+3=8ty；進位；進位C8的延遲：的延遲：3+2=5ty2022-2-7 多級先行進位加法器多級先行進位加法器單級單級(局部局部)先行進位加法器的進位生成方式：先行進位加法器的進位生成方式： “組內(nèi)并行、組間串行組內(nèi)并行、組間串行”所以，單級先行進位加法器雖然比行波加法器延遲時間短，但高位所以，單級先行進位加法器雖然比行波加法器延遲時間短，但高位組進位依賴低位組進位，故仍有較長的時間延遲組進位依賴低位組進位，故仍有較長的時間延遲通過引入組進位生成通過引入組進位生成/傳

22、遞函數(shù)實現(xiàn)傳遞函數(shù)實現(xiàn)“組內(nèi)并行、組間并行組內(nèi)并行、組間并行”進位方進位方式式 設設n=4,則：則：C1=G0+P0C0 C2=G1+P1C1=G1+P1G0+P1P0C0 C3=G2+P2C2=G2+P2G1+P2P1G0+P2P1P0C0 G3*=G3+P3C3=G3+P3G2+P3P2G1+P3P2P1G0 P3*=P3P2P1P0C4 =G3*+P3*C0。把實現(xiàn)上述邏輯的電路稱為把實現(xiàn)上述邏輯的電路稱為4位位BCLA部件。部件。回顧：回顧：多級先行進位加法器多級先行進位加法器2022-2-7回顧：回顧：多級先行進位加法器多級先行進位加法器關鍵路徑長度為多少？關鍵路徑長度為多少？最終進

23、位的延遲為多少？最終進位的延遲為多少？4位成組先行進位部件（4位BCLA部件）4 4位位CLACLA加法器加法器4 4位位CLACLA加法器加法器4 4位位CLACLA加法器加法器4 4位位CLACLA加法器加法器1616位兩級先行進位加法器位兩級先行進位加法器3+2+3 = 8ty3+2=5ty2022-2-7A 4-bit ALU 1-bit ALU 4-bit串行串行 ALUABFACarryOutMuxCarryInResultA0B01-bitALUResult0CarryIn0CarryOut0A1B11-bitALUResult1CarryIn1CarryOut1A2B21-bi

24、tALUResult2CarryIn2CarryOut2A3B31-bitALUResult3CarryIn3CarryOut3MUX是什么？（數(shù)字電路課學過）是什么？（數(shù)字電路課學過）關鍵路徑延遲長，速度慢！關鍵路徑延遲長，速度慢！2022-2-7先行進位先行進位ALUu先行進位先行進位ALU 芯片（芯片（SN74181）四位四位ALU芯片，中規(guī)模集成電路。在先行進位加法器基礎上附加部芯片，中規(guī)模集成電路。在先行進位加法器基礎上附加部分線路，具有基本的算術運算和邏輯運算功能。分線路，具有基本的算術運算和邏輯運算功能。SN74181的的邏輯圖和功能表邏輯圖和功能表SN74182是是4位位BCL

25、A (成組先行進位成組先行進位)芯片。芯片。u多芯片級聯(lián)構成先行進位多芯片級聯(lián)構成先行進位ALU1個個SN74181芯片直接構成一個芯片直接構成一個4位全先行進位位全先行進位ALU4個個SN74181芯片串行構成一個芯片串行構成一個16位單級先行進位位單級先行進位ALU4個個SN74181芯片與芯片與1個個SN74182芯片可構成芯片可構成16位兩級先行進位位兩級先行進位ALU16個個SN74181芯片與芯片與5個個SN74182芯片可構成芯片可構成64位先行進位位先行進位ALUSKIPALUALU中的中的“加加”運算電路相當于運算電路相當于n n檔二進制加法算盤檔二進制加法算盤。所有其他運算

26、都以所有其他運算都以ALU ALU 中中“加加”運算為基礎！運算為基礎！2022-2-7SN74181的引腳的引腳輸入端：輸入端：Ai和和Bi分別為第分別為第1和和2操作數(shù)，操作數(shù)，Cn為低位進位，為低位進位，M為功能選擇為功能選擇線，線，Si為操作選擇線，共為操作選擇線，共4位，故最多有位，故最多有16種運算。種運算。輸出端：輸出端：Fi為運算結果，為運算結果，Cn+4、P和和G為進位，為進位，“A=B”為相等標志為相等標志P輸入端輸入端輸出端輸出端2022-2-7SN74181邏輯電路圖邏輯電路圖2022-2-7SN74181正邏輯功能表正邏輯功能表BACK2022-2-7SN74182芯

27、片的引腳芯片的引腳輸入端：輸入端：Pi和和Gi分別為第分別為第i組的組內(nèi)進位傳遞函數(shù)和進位生成函數(shù)，組的組內(nèi)進位傳遞函數(shù)和進位生成函數(shù)， Cn為低位進位。為低位進位。輸出端：輸出端： Cn+4、Cn+8 、Cn+12為相應組的組內(nèi)進位，為相應組的組內(nèi)進位，P*和和G*分別分別為整個大組的組進位傳遞函數(shù)和進位生成函數(shù)。為整個大組的組進位傳遞函數(shù)和進位生成函數(shù)。2022-2-7SN74182芯片的邏輯電路圖芯片的邏輯電路圖BACK2022-2-7SN74181和和SN74182組成組成16位先行進位位先行進位ALU4位位ALU4位位ALU4位位ALU4位位ALU1616位兩級先行進位位兩級先行進位

28、ALUALUBACK2022-2-7第一講小結第一講小結uC C語言程序中涉及的運算語言程序中涉及的運算整數(shù)算術運算、浮點數(shù)算術運算整數(shù)算術運算、浮點數(shù)算術運算按位、邏輯、移位、位擴展和位截斷按位、邏輯、移位、位擴展和位截斷u指令集中與運算相關的指令（指令集中與運算相關的指令（ 以以MIPSMIPS為參考為參考 ）涉及到的定點數(shù)運算涉及到的定點數(shù)運算-算術運算算術運算 帶符號整數(shù)：取負 / 符號擴展 / 加 / 減 / 乘 / 除 / 算術移位 無符號整數(shù)：0擴展 / 加 / 減 / 乘 / 除 -邏輯運算邏輯運算 邏輯操作：與 / 或 / 非 / 移位操作：邏輯左移 / 邏輯右移涉及到的浮點

29、數(shù)運算：加、減、乘、除涉及到的浮點數(shù)運算：加、減、乘、除u基本運算部件基本運算部件ALUALU的設計的設計全加器、串行加法器、先行進位加法器全加器、串行加法器、先行進位加法器串行串行ALUALU、先行進位、先行進位ALUALU（單級（單級/ /多級）多級）定點運算包括：定點運算包括： 無符號數(shù)無符號數(shù) 按位邏輯運算按位邏輯運算 邏輯移位運算邏輯移位運算 位擴展和截斷運算位擴展和截斷運算 加加/ /減減/ /乘乘/ /除運算除運算 帶符號整數(shù)帶符號整數(shù) 算術移位運算算術移位運算 擴展運算和截斷運算擴展運算和截斷運算 補碼補碼加加/ /減減/ /乘乘/ /除運算除運算浮點運算包括：浮點運算包括：

30、原碼原碼加加/ /減減/ /乘乘/ /除運算除運算 移碼移碼加加/ /減運算減運算是一種模運算系統(tǒng)！是一種模運算系統(tǒng)！2022-2-7第二講：定點數(shù)運算及運算部件第二講：定點數(shù)運算及運算部件主主 要要 內(nèi)內(nèi) 容容u加加/ /減運算及其運算部件減運算及其運算部件 補碼補碼 / / 原碼原碼 / / 移碼移碼 加減運算加減運算u乘法運算及其運算部件乘法運算及其運算部件 原碼原碼 / / 補碼補碼 乘法運算乘法運算 快速乘法器快速乘法器u除法運算及其運算部件除法運算及其運算部件 原碼原碼 / / 補碼補碼 除法運算除法運算 快速除法器快速除法器u定點運算器定點運算器u十進制加減運算十進制加減運算注：

31、無符號數(shù)的按位邏輯運算可用邏輯門電路實現(xiàn)；無符號數(shù)的邏輯移位運算可用專門的移位器或斜送結果等多種方式來實現(xiàn)；帶符號數(shù)的算術移位運算、無符號數(shù)和帶符號整數(shù)的位擴展運算和截斷運算也可用簡單電路很容易地實現(xiàn)。2022-2-7補碼加補碼加/減運算及其部件減運算及其部件u補碼加減運算公式補碼加減運算公式A+B補補 = A補補 + B 補補 ( MOD 2n )AB補補 = A補補 + B 補補 ( MOD 2n )u補碼加減運算要點和運算部件補碼加減運算要點和運算部件加、減法運算統(tǒng)一采用加法來處理加、減法運算統(tǒng)一采用加法來處理符號位符號位(最高有效位最高有效位MSB)和數(shù)值位一起參與運算和數(shù)值位一起參與

32、運算直接用直接用ALU實現(xiàn)兩個數(shù)的加運算（模運算系統(tǒng)）實現(xiàn)兩個數(shù)的加運算（模運算系統(tǒng)） 問題：模是多少？問題：模是多少？運算結果高位丟棄，保留低運算結果高位丟棄，保留低n位，相當于取模位，相當于取模2n 實現(xiàn)減法的主要工作在于：求實現(xiàn)減法的主要工作在于：求B 補補問題：如何求問題：如何求 B B 補補？B 補補=B+1ALU444AResultZeroCarryInCarryOut4B401MuxSelSubBoverflow補碼加減運算部件補碼加減運算部件當控制端當控制端SubSub為為1 1時，做減法時，做減法當控制端當控制端SubSub為為0 0時，做加法時，做加法2022-2-7補碼加

33、補碼加/減運算與減運算與“溢出溢出”判斷判斷Ex1: -7- 6 = -7 + (-6) = +3 -3 - 5 = - 3 + (- 5) = - 811+00011110011101111000100011Ex2: 用用8位補碼計算位補碼計算107+46=？ 結果錯誤結果錯誤: 107 + 46 = -103.10710= 0110 10112 4610 = 0010 11102 0 1001 1001進位是真正的符號：進位是真正的符號：+153+15311溢出現(xiàn)象：溢出現(xiàn)象：(1) 最高位和次高位的進位不同最高位和次高位的進位不同 (2) 和的符號位和加數(shù)的符號位不同和的符號位和加數(shù)的符

34、號位不同X問題：若采用變形補碼結果怎樣？問題：若采用變形補碼結果怎樣？采用變形補碼時采用變形補碼時“溢出溢出”判斷條件判斷條件：結果的兩個符號位不同結果的兩個符號位不同變形補碼可保留運算中間結果。變形補碼可保留運算中間結果。從乘除運算過程可看出這點！從乘除運算過程可看出這點！2022-2-7Overflow Detection Logic(溢出判斷邏輯溢出判斷邏輯)uCarry into MSB ! = Carry out of MSBFor a N-bit ALU: Overflow = CarryIn N-1 XOR CarryOut N-1OverflowXYX XOR Y0001110

35、1110A0B01-bitALUResult0CarryIn0CarryOut0A1B11-bitALUResult1CarryIn1CarryOut1A2B21-bitALUResult2CarryIn2CarryOut2A3B31-bitALUResult3CarryIn3CarryOut30也可以用其他實現(xiàn)方式。也可以用其他實現(xiàn)方式。2022-2-7Zero Detection Logic(判判0邏輯邏輯)ZeroA0B01-bitALUResult0CarryIn0CarryOut0A1B11-bitALUResult1CarryIn1CarryOut1A2B21-bitALUResu

36、lt2CarryIn2CarryOut2A3B31-bitALUResult3CarryIn3CarryOut3 除除Result、Zero、Overflow外，許多機外，許多機器還生成進器還生成進/借位標志（借位標志（CF）、符號標志）、符號標志（NF / SF）等。）等。 標志在運算電路中產(chǎn)生，被記錄到專門標志在運算電路中產(chǎn)生，被記錄到專門的寄存器中，以便在分支指令中被用來作的寄存器中，以便在分支指令中被用來作為條件。為條件。 存放標志的寄存器通常稱為存放標志的寄存器通常稱為程序程序/狀態(tài)字狀態(tài)字寄存器寄存器或或標志寄存器。標志寄存器。每個標志對應標志每個標志對應標志寄存器中的一個標志位。

37、寄存器中的一個標志位。 2022-2-7原碼加原碼加/減運算減運算u用于浮點數(shù)尾數(shù)運算用于浮點數(shù)尾數(shù)運算u符號位和數(shù)值部分分開處理符號位和數(shù)值部分分開處理u僅對數(shù)值部分進行加減運算，符號位起判斷和控制作用僅對數(shù)值部分進行加減運算，符號位起判斷和控制作用u規(guī)則如下：規(guī)則如下： 比較兩數(shù)符號，對加法實行比較兩數(shù)符號，對加法實行“同號求和，異號求差同號求和，異號求差”，對減法實行，對減法實行“異號求和，同號求差異號求和，同號求差”。 求和：數(shù)值位相加，若最高位產(chǎn)生進位，則結果溢出。和的符號取求和：數(shù)值位相加，若最高位產(chǎn)生進位，則結果溢出。和的符號取被加數(shù)（被減數(shù)）的符號。被加數(shù)（被減數(shù)）的符號。 求

38、差：被加數(shù)（被減數(shù)）加上加數(shù)（減數(shù)）的補碼。求差：被加數(shù)（被減數(shù)）加上加數(shù)（減數(shù)）的補碼。-最高數(shù)值位產(chǎn)生進位表明加法結果為正，所得數(shù)值位正確。最高數(shù)值位產(chǎn)生進位表明加法結果為正，所得數(shù)值位正確。-最高數(shù)值位沒產(chǎn)生進位表明加法結果為負，得到的是數(shù)值位的補最高數(shù)值位沒產(chǎn)生進位表明加法結果為負，得到的是數(shù)值位的補碼形式，需對結果求補，還原為絕對值形式的數(shù)值位。碼形式，需對結果求補，還原為絕對值形式的數(shù)值位。 差的符號位：差的符號位：a)a)情況下，符號位取被加數(shù)（被減數(shù)）的符號；情況下，符號位取被加數(shù)（被減數(shù)）的符號； b) b)情況下，符號位為被加數(shù)（被減數(shù)）的符號取反。情況下，符號位為被加數(shù)（

39、被減數(shù)）的符號取反。2022-2-7原碼加原碼加/減運算減運算例例1：已知：已知 X原原 = 1.0011，Y原原 = 1.1010，要求計算，要求計算X+Y原原解：由原碼加減運算規(guī)則知：同號相加，則求和，和的符號同被加數(shù)符號。解：由原碼加減運算規(guī)則知：同號相加，則求和，和的符號同被加數(shù)符號。 所以：和的數(shù)值位為：所以：和的數(shù)值位為：0011 + 1010 = 1101 （ALU中無符號數(shù)相加）中無符號數(shù)相加） 和的符號位為：和的符號位為：1 X+Y原原 = 1.1101例例2 ：已知：已知 X原原 = 1.0011，Y原原 = 1.1010，要求計算，要求計算XY原原 解：由原碼加減運算規(guī)則

40、知：同號相減，則求差（補碼減法）解：由原碼加減運算規(guī)則知：同號相減，則求差（補碼減法） 差的數(shù)值位為：差的數(shù)值位為：0011+(1010)補補 = 0011 + 0110 = 1001 最高數(shù)值位沒有產(chǎn)生進位，表明加法結果為負，需對最高數(shù)值位沒有產(chǎn)生進位，表明加法結果為負，需對1001求補，還求補，還 原為絕對值形式的數(shù)值位。即：原為絕對值形式的數(shù)值位。即：(1001)補補= 0111 差的符號位為差的符號位為X原原的符號位取反，即：的符號位取反，即：0 XY原原 = 0.0111思考題：如何設計一個基于思考題：如何設計一個基于ALU的原碼加的原碼加/減法器？減法器？求和：直接加，有進位則溢出

41、，符號同被求和：直接加，有進位則溢出，符號同被求差：加補碼，不會溢出，符號分情況求差：加補碼，不會溢出，符號分情況2022-2-7移碼加移碼加/減運算減運算u用于浮點數(shù)階碼運算用于浮點數(shù)階碼運算u符號位和數(shù)值部分可以一起處理符號位和數(shù)值部分可以一起處理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

42、2n） 結論：移碼的和、差等于和、差的補碼！結論：移碼的和、差等于和、差的補碼！u運算規(guī)則運算規(guī)則 加法：直接將加法：直接將E1移移和和E2移移進行模進行模2n加，然后對結果的符號取反。加，然后對結果的符號取反。 減法：先將減數(shù)減法：先將減數(shù)E2移移求補（各位取反，末位加求補（各位取反，末位加1），然后再與被減），然后再與被減數(shù)數(shù) E1移移進行模進行模2n相加，最后對結果的符號取反。相加，最后對結果的符號取反。 溢出判斷：進行模溢出判斷：進行模2n相加時，如果兩個加數(shù)的符號相同，并且與和相加時，如果兩個加數(shù)的符號相同，并且與和數(shù)的符號也相同，則發(fā)生溢出。數(shù)的符號也相同，則發(fā)生溢出。補碼和移碼的

43、關系：符號位相反、數(shù)值位相同！補碼和移碼的關系：符號位相反、數(shù)值位相同！2022-2-7移碼加移碼加/減運算減運算例例1： 用四位移碼計算用四位移碼計算“7+（ 6）”和和“3 + 6”的值。的值。解：解：7移移 = 0001 6移移= 0010 3移移= 01016移移= 1110 7移移 + 6移移 = 0001 + 0010 = 0011 （兩個加數(shù)與結果符號都為（兩個加數(shù)與結果符號都為0，溢出），溢出） 3移移 + 6移移 = 0101 + 1110 = 0011， 符號取反后為符號取反后為 1011，其真值為，其真值為+3 問題：問題：7+(6)移移=? 3+(6)移移 =？ 例例2

44、： 用四位移碼計算用四位移碼計算“7 （ 6）”和和“3 5”的值。的值。解：解：7移移 = 0001 6移移= 0010 3移移= 01015移移= 1101 7移移 6移移 = 0001 + 1110 = 1111， 符號取反后為符號取反后為 0111，其真值為，其真值為1。 3移移 5移移 = 0101 + 0011 = 1000，符號取反后為，符號取反后為 0000，其真值為，其真值為 8。2022-2-7無符號數(shù)的乘法運算無符號數(shù)的乘法運算uPaper and pencil example: Multiplicand 1000Multiplier x 1001 1000 0000 0

45、000 1000 Product(積積) 0.1001000假定：假定：X原原=x0.x1xn，Y原原=y0.y1yn ，求，求xY原原數(shù)值部分數(shù)值部分 z1z2n = (0.x1xn ) (0. y1yn) (小數(shù)點位置約定，不區(qū)分小數(shù)還是整數(shù)小數(shù)點位置約定，不區(qū)分小數(shù)還是整數(shù))X y4 2-4X y3 2-3X y2 2-2X y1 2-1 4XY= (X yi2-i) i=1整個運算過程中用到兩種操作：加法整個運算過程中用到兩種操作：加法 + + 左移左移因而，也可用因而，也可用ALUALU和移位器來實現(xiàn)乘法運算和移位器來實現(xiàn)乘法運算2022-2-7無符號數(shù)的乘法運算無符號數(shù)的乘法運算u

46、手工乘法的特點：手工乘法的特點： 每步計算：每步計算：Xyi，若，若yi = 0，則得，則得0；若；若yi = 1，則得，則得X 把求得的各項結果把求得的各項結果X yi 逐次左移，可表示為逐次左移，可表示為X yi2-i 對中結果求和，即對中結果求和，即 (X yi2-i)，這就是兩個無符號數(shù)的乘積，這就是兩個無符號數(shù)的乘積u計算機內(nèi)部稍作以下改進：計算機內(nèi)部稍作以下改進： 每次得每次得Xyi后，與前面所得結果累加，得到后，與前面所得結果累加，得到Pi，稱之為部分積。因，稱之為部分積。因為不等到最后一次求和，減少了保存各次相乘結果為不等到最后一次求和，減少了保存各次相乘結果Xyi的開銷。的開

47、銷。 每次得每次得Xyi后，不將它左移與前次部分積后，不將它左移與前次部分積Pi相加，而將部分積相加，而將部分積Pi右右移后與移后與Xyi相加。因為加法運算始終對部分積中高相加。因為加法運算始終對部分積中高n位進行。故用位進行。故用n位加法器可實現(xiàn)二個位加法器可實現(xiàn)二個n位數(shù)相乘。位數(shù)相乘。 對乘數(shù)中為對乘數(shù)中為“1”的位執(zhí)行加法的位執(zhí)行加法和右移，對為和右移，對為“0”“0”的位只執(zhí)行右移，的位只執(zhí)行右移，而不執(zhí)行加法運算。而不執(zhí)行加法運算。2022-2-7無符號乘法運算的算法推導無符號乘法運算的算法推導u上述思想可寫成如下數(shù)學推導過程：上述思想可寫成如下數(shù)學推導過程：XY = X ( 0.

48、y1 y2 yn ) = X y12-1 +X y22-2 +X y32-3 + +X yn2-n =2-1 ( 2-1 (2-12-1 (2-1 (0 + X yn) + X yn-1) + + X y2 ) + X y1) n個個2-1u上述推導過程具有明顯的遞歸性質(zhì)，因此，無符號數(shù)乘法過程可歸結為循環(huán)上述推導過程具有明顯的遞歸性質(zhì)，因此，無符號數(shù)乘法過程可歸結為循環(huán)計算下列算式的過程：設計算下列算式的過程：設P0 = 0，每步的乘積為：，每步的乘積為： P1 = 2-1 (P0+ X yn) P2 = 2-1 (P1+ X yn-1) Pn = 2-1 (Pn-1+ X y1)u 其遞推

49、公式為：其遞推公式為：Pi+1 = 2-1 (Pi + Xyn-i) ( i = 0, 1, 2, 3, , n-1 ) u 最終乘積最終乘積Pn = XY迭代過程從乘數(shù)迭代過程從乘數(shù)最低位最低位yn和和P0=0開始，經(jīng)開始，經(jīng)n次次“判斷判斷加法加法右移右移”循環(huán)循環(huán)，直到求出，直到求出Pn為止。為止。2022-2-7寫使能寫使能控制邏輯控制邏輯右移右移32位位 ALU被乘數(shù)寄存器被乘數(shù)寄存器X X乘積寄存器乘積寄存器P3264 位位323232加加計數(shù)器計數(shù)器Cn時鐘時鐘C乘數(shù)寄存器乘數(shù)寄存器Y32位乘法運算的硬件實現(xiàn)位乘法運算的硬件實現(xiàn)u被乘數(shù)寄存器被乘數(shù)寄存器X：存放被乘數(shù)存放被乘數(shù)u

50、乘積寄存器乘積寄存器P：開始置初始部分積開始置初始部分積P0 = 0；結束時，存放的是；結束時，存放的是64位乘積的高位乘積的高32位位u乘數(shù)寄存器乘數(shù)寄存器Y：開始時置乘數(shù)；結束時，存放的是開始時置乘數(shù)；結束時，存放的是64位乘積的低位乘積的低32位位u進位觸發(fā)器進位觸發(fā)器C：保存加法器的進位信號保存加法器的進位信號u循環(huán)次數(shù)計數(shù)器循環(huán)次數(shù)計數(shù)器Cn：存放循環(huán)次數(shù)。初值存放循環(huán)次數(shù)。初值32，每循環(huán)一次，每循環(huán)一次，Cn減減1，Cn=0時結束時結束uALU：乘法核心部件。在控制邏輯控制下，對乘法核心部件。在控制邏輯控制下，對P和和X的內(nèi)容的內(nèi)容“加加”，在，在“寫使能寫使能”控制下運算結果被

51、送回控制下運算結果被送回P，進位位在，進位位在C中中每次循環(huán)都要對進位位每次循環(huán)都要對進位位C C、乘積寄存器、乘積寄存器P P和乘數(shù)寄存器實現(xiàn)和乘數(shù)寄存器實現(xiàn)同步同步“右移右移” 2022-2-7Example：無符號整數(shù)乘法運算：無符號整數(shù)乘法運算舉例說明：舉例說明：設設A=1110 B=1101 應用遞推公式：應用遞推公式： Pi=2-1(Abi+ Pi-1) C 乘積乘積P 乘數(shù)乘數(shù)R 0 0000 0 0000 11011101 + 1110 + 1110 0 1110 0 1110 11011101 0 0111 0 0 0111 0110110 0 0011 10 0 0011

52、101111 + 1110 + 1110 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。保留進位位。保留進位位。右移時進位、部分積和剩余乘右移時進位、部分積和剩余乘數(shù)一起進行數(shù)一起進行邏輯右移邏輯右移。驗證：驗證：A=14, B=13, A x B=1822022-2-7原

53、碼乘法算法原碼乘法算法u用于浮點數(shù)尾數(shù)乘運算用于浮點數(shù)尾數(shù)乘運算u符號與數(shù)值分開處理：積符異或得到，數(shù)值用無符號乘法運算符號與數(shù)值分開處理：積符異或得到，數(shù)值用無符號乘法運算例：設例：設x原原=0.1110 ，y原原=1.1101，計算，計算 XY原原 解：數(shù)值部分用無符號數(shù)乘法算法計算：解：數(shù)值部分用無符號數(shù)乘法算法計算：11101101= 1011 0110 符號位：符號位：0 1=1，所以：，所以： XY原原=1. 10110110原碼一位乘法：原碼一位乘法：每次只取乘數(shù)的一位判斷，需每次只取乘數(shù)的一位判斷，需n n次循環(huán)，速度慢。次循環(huán)，速度慢。原碼兩位乘法：原碼兩位乘法：每次取乘數(shù)兩

54、位判斷，只需每次取乘數(shù)兩位判斷，只需n/2n/2次循環(huán)，快一倍。次循環(huán)，快一倍。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) +Xyi-1 yi T操操 作作迭迭 代代 公公 式式0 0 0 0 0 10 1 0 0 1 1 1 0 01 0 1 1 1 0 1 1 1 0 T+X 0 T+X 0 T+2X 0 T+2X 0 TX 1 TX 1 T 1 T 2-2 (Pi )2-2

55、(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觸發(fā)器用來記錄下次是否要執(zhí)行觸發(fā)器用來記錄下次是否要執(zhí)行“+X”“+X”“X”“X”運算用運算用“+-X“+-X補補”實現(xiàn)！實現(xiàn)！3X3X時，本次時，本次-X-X，下次，下次+X+X！2022-2-7原碼兩位乘法舉例原碼兩位乘法舉例已知已知 X原原=0.111001， Y原原= 0.100111，用原碼兩位乘法計算，用原碼兩位乘法計算XY原原解：解： 先用無符號數(shù)乘法計算先用無符號數(shù)乘法計算111001100111，原碼兩位乘法過程如下：，

56、原碼兩位乘法過程如下：若用模若用模4 4補碼，補碼，則則P P和和Y Y同時右同時右移移2 2位時，得到位時，得到的的P3P3是負數(shù)，是負數(shù)，這顯然是錯誤這顯然是錯誤的！需要再增的！需要再增加一位符號。加一位符號。采用補碼右移采用補碼右移為模為模8 8補碼形式補碼形式( (三位符號位三位符號位) )，為什么？為什么？2022-2-7補碼乘法運算補碼乘法運算u用于定點整數(shù)乘法運算用于定點整數(shù)乘法運算u符號與數(shù)值統(tǒng)一處理符號與數(shù)值統(tǒng)一處理假定：假定：X補補=xn-1xn-2 x1x0 ， Y補補=yn-1yn-2 y1y0 ， 求：求：X x Y補補=？基于以下補碼性質(zhì)：基于以下補碼性質(zhì)： 令令Y

57、補補=yn-1yn-2 y1y0 ， 則則Y=-yn-1.2n-1+yn-2 .2n-2+ y1 .21+ y0 .20令：令：y-1 =0，則：，則：當當n=32時，時，Y=-y31.231+y30 .230+ 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推導如下：推導如下：

58、因為因為X x Y補補 X補補 x Y補補 ，故，故不能直接用無符號乘法計算。不能直接用無符號乘法計算。2-32.XxY補補= (y30 -y31 )X.2-1+(y29-y30)X.2-2+ + (y0y1).2-31 +(y-1-y0).2-32= 2-1(2-1(2-1(y-1-y0)X) + (y0y1)X) + + (y30 -y31)X)2022-2-7Booths 算法實質(zhì)算法實質(zhì)u當前位當前位右邊位右邊位 操作操作Example10減被乘數(shù)減被乘數(shù)000111100011加加0 (不操作不操作)000111100001加被乘數(shù)加被乘數(shù)000111100000加加0 (不操作不操

59、作) 0001111000u最初提出這種想法是因為在最初提出這種想法是因為在Booth的機器上移位操作比加法更快！的機器上移位操作比加法更快！u在在“1串串”中，第一個中，第一個1時做減法，最后一個時做減法，最后一個1做加法，其余情況只要移位做加法，其余情況只要移位。同前面算法一樣，將乘積寄存器同前面算法一樣，將乘積寄存器右移右移一位。一位。（這里是算術右移）（這里是算術右移）0 1 1 1 1 0beginning of runend of runmiddle of run2022-2-7布斯算法舉例布斯算法舉例已知已知X補補 = 1 101，Y補補 = 0 110，計算，計算XY補補 驗證

60、：驗證：X = -3，Y = 6，XY= - 0010010B = -18，結果正確！，結果正確！ -X補補 = 00112022-2-7Booths Example: 2 x 3 1a. P = P - m1110 + 11101110 1101 0shift P (sign ext)1b. 00101111 0110 101 - add + 00102a.0001 0110 1shift P2b.00100000 1011 010 - sub +11103a.00101110 1011 0shift3b.0010 1111 0101 111 - nop4a1111 0101 1 shift4b.00101111 1010 1 doneOpe