《計(jì)算機(jī)組成與系統(tǒng)結(jié)構(gòu)》(清華大學(xué)出版社)(袁春風(fēng)編著)第三章課件

第一講

不同層次程序員看到的運(yùn)算及ALU

第二講定點(diǎn)數(shù)運(yùn)算及其運(yùn)算部件

第三講浮點(diǎn)數(shù)運(yùn)算及其運(yùn)算部件Ch3:ArithmeticandLogicOperateandALU

運(yùn)算方法和運(yùn)算部件第一講：不同層次程序員看到的運(yùn)算及ALU主要內(nèi)容C語(yǔ)言程序中涉及的運(yùn)算整數(shù)算術(shù)運(yùn)、浮點(diǎn)數(shù)算術(shù)運(yùn)算按位、邏輯、移位、位擴(kuò)展和位截?cái)嘀噶罴信c運(yùn)算相關(guān)的指令（以MIPS為參考）涉及到的定點(diǎn)數(shù)運(yùn)算算術(shù)運(yùn)算帶符號(hào)整數(shù)運(yùn)算：取負(fù)/符號(hào)擴(kuò)展/加/減/乘/除/算術(shù)移位無(wú)符號(hào)整數(shù)運(yùn)算：0擴(kuò)展/加/減/乘/除邏輯運(yùn)算邏輯操作：與/或/非/…移位操作：邏輯左移/邏輯右移涉及到的浮點(diǎn)數(shù)運(yùn)算：加、減、乘、除基本運(yùn)算部件ALU的設(shè)計(jì)C語(yǔ)言程序中涉及的運(yùn)算算術(shù)運(yùn)算（最基本的運(yùn)算）無(wú)符號(hào)數(shù)、帶符號(hào)整數(shù)、浮點(diǎn)數(shù)的運(yùn)算按位運(yùn)算用途對(duì)一個(gè)位串實(shí)現(xiàn)“掩碼”（mask）操作或相應(yīng)的其他處理（主要用于對(duì)多媒體數(shù)據(jù)或控制信息進(jìn)行處理）操作按位或：“|”按位與：“&”按位取反：“~”按位異或：“^”問(wèn)題：如何從一個(gè)16位采樣數(shù)據(jù)y中提取高位字節(jié)，并使低字節(jié)為0？可用“&”實(shí)現(xiàn)“掩碼”操作：y&0xFF00例如，當(dāng)y=0x2C0B時(shí)，通過(guò)掩碼操作得到結(jié)果為：0x2C00C語(yǔ)言程序中涉及的運(yùn)算邏輯運(yùn)算用途用于關(guān)系表達(dá)式的運(yùn)算例如，if（x>yandi<100）then……中的“and”運(yùn)算操作“‖”表示“OR”運(yùn)算“&&”表示“AND”運(yùn)算

例如，if((x>y)&&(i<100))then……“!”表示“NOT”運(yùn)算與按位運(yùn)算的差別符號(hào)表示不同：&~&&；|~‖；……運(yùn)算過(guò)程不同：按位~整體結(jié)果類型不同：位串~邏輯值C語(yǔ)言程序中涉及的運(yùn)算移位運(yùn)算用途提取部分信息擴(kuò)大或縮小數(shù)值的2、4、8…倍操作左移:：x<<k;右移：x>>k不區(qū)分是邏輯移位還是算術(shù)移位，由x的類型確定無(wú)符號(hào)數(shù)：邏輯左移、邏輯右移高（低）位移出，低（高）位補(bǔ)0問(wèn)題：何時(shí)可能發(fā)生溢出？如何判斷溢出？若高位移出的是1，則左移時(shí)發(fā)生溢出帶符號(hào)整數(shù)：算術(shù)左移、算術(shù)右移左移：高位移出，低位補(bǔ)0。溢出判斷：若移出的位不等于新的符號(hào)位，則溢出。右移：低位移出，高位補(bǔ)符，可能發(fā)生數(shù)據(jù)丟失。C語(yǔ)言程序中涉及的運(yùn)算位擴(kuò)展和位截?cái)噙\(yùn)算用途在進(jìn)行類型轉(zhuǎn)換時(shí)，可能需要數(shù)據(jù)的擴(kuò)展或截?cái)嗖僮鳑](méi)有專門的操作運(yùn)算符，根據(jù)類型轉(zhuǎn)換前后數(shù)據(jù)長(zhǎng)短來(lái)確定是擴(kuò)展還是截?cái)唷皵U(kuò)展”：短數(shù)轉(zhuǎn)為長(zhǎng)數(shù)；“截?cái)唷保L(zhǎng)數(shù)轉(zhuǎn)為短數(shù)擴(kuò)展無(wú)符號(hào)數(shù)：0擴(kuò)展，即：前面補(bǔ)0帶符號(hào)整數(shù)：符號(hào)擴(kuò)展，即：前面補(bǔ)符號(hào)截?cái)?/p>

強(qiáng)行將一個(gè)長(zhǎng)數(shù)的高位丟棄，故可能會(huì)發(fā)生“溢出”例1：在大端機(jī)上輸出si,usi,i,ui的十進(jìn)制和十六進(jìn)制值是什么？shortsi=-12345;unsignedshortusi=si;inti=si;unsingned

ui=usi;si=-12345CFC7usi=53191CFC7i=-12345FFFFCFC7ui=531910000CFC7例2：在大端機(jī)上執(zhí)行后，i和j是否相等？inti=53191;shortsi=(short)i;intj=si;不相等！i=531910000CFC7si=-12345CFC7j=-12345

FF

FFCFC7原因：對(duì)i截?cái)鄷r(shí)發(fā)生了“溢出”，即：53191截?cái)酁?6位數(shù)時(shí)，無(wú)法正確表示！MIPS定點(diǎn)算術(shù)運(yùn)算指令I(lǐng)nstruction Example Meaning Commentsadd add$1,$2,$3 $1=$2+$3 3operands;exceptionpossiblesubtract sub$1,$2,$3 $1=$2–$3 3operands;exceptionpossibleaddimmediate addi$1,$2,100 $1=$2+100 +constant;exceptionpossibleaddunsigned addu$1,$2,$3 $1=$2+$3 3operands;noexceptionssubtractunsigned subu$1,$2,$3 $1=$2–$3 3operands;noexceptionsaddimm.unsign. addiu$1,$2,100 $1=$2+100 +constant;noexceptionsmultiply mult$2,$3 Hi,Lo=$2x$3 64-bitsignedproductmultiplyunsigned multu$2,$3 Hi,Lo=$2x$3 64-bitunsignedproductdivide div$2,$3 Lo=$2÷$3, Lo=quotient,Hi=remainder Hi=$2mod$3divideunsigned divu$2,$3 Lo=$2÷$3, Unsignedquotient&remainder Hi=$2mod$3涉及到的操作數(shù)：32/16位無(wú)符號(hào)數(shù)，32/16位帶符號(hào)數(shù)涉及到的操作：加/減/乘/除（有符號(hào)/無(wú)符號(hào)）MIPS邏輯運(yùn)算指令涉及到的操作數(shù)：32/16位邏輯數(shù)涉及到的操作：按位與/按位或/按位或非/左移/右移MIPS定點(diǎn)比較和分支指令涉及到的操作數(shù)：32/16位無(wú)符號(hào)數(shù)，32/16位帶符號(hào)數(shù)涉及到的操作：大小比較和相等比較（有符號(hào)/無(wú)符號(hào)）通過(guò)減法運(yùn)算實(shí)現(xiàn)“比較”操作!MIPS定點(diǎn)數(shù)據(jù)傳送指令涉及到的操作數(shù)：32/16位帶符號(hào)數(shù)（偏移量可以是負(fù)數(shù)）涉及到的操作：加/減/符號(hào)擴(kuò)展/0擴(kuò)展MIPS中的浮點(diǎn)算術(shù)運(yùn)算指令涉及到的浮點(diǎn)操作數(shù)：32位單精度/64位雙精度浮點(diǎn)數(shù)涉及到的浮點(diǎn)操作：加/減/乘/除

MIPS提供專門的浮點(diǎn)數(shù)寄存器：32個(gè)32位單精度浮點(diǎn)數(shù)寄存器：$f0,$f1,……,$f31連續(xù)兩個(gè)寄存器（一偶一奇）存放一個(gè)雙精度浮點(diǎn)數(shù)MIPS中的浮點(diǎn)數(shù)傳送指令涉及到的浮點(diǎn)操作數(shù)：32位單精度浮點(diǎn)數(shù)涉及到的浮點(diǎn)操作：傳送操作（與定點(diǎn)傳送一樣）還涉及到定點(diǎn)操作：加/減（用于地址運(yùn)算）例：實(shí)現(xiàn)將兩個(gè)浮點(diǎn)數(shù)從內(nèi)存取出相加后再存回到內(nèi)存的指令序列為：

lwcl$f1,x($s1)

lwcl$f2,y($s2)

add.s$f4,$f1,$f2

swlc$f4,z(s3)MIPS中的浮點(diǎn)數(shù)比較和分支指令涉及到的浮點(diǎn)操作數(shù)：32位單精度浮點(diǎn)數(shù)/64位雙精度浮點(diǎn)數(shù)涉及到的浮點(diǎn)操作：比較操作（用

減法來(lái)實(shí)現(xiàn)比較）還涉及到的定點(diǎn)操作：加/減（用于地址運(yùn)算）

有一個(gè)專門的浮點(diǎn)標(biāo)志cond，無(wú)需在指令中明顯給出condMIPS指令考察的結(jié)果涉及到的操作數(shù)：無(wú)符號(hào)整數(shù)、帶符號(hào)整數(shù)邏輯數(shù)浮點(diǎn)數(shù)涉及到的運(yùn)算定點(diǎn)數(shù)運(yùn)算帶符號(hào)整數(shù)運(yùn)算：取負(fù)/符號(hào)擴(kuò)展/加/減/乘/除/算術(shù)移位無(wú)符號(hào)整數(shù)運(yùn)算：0擴(kuò)展/加/減/乘/除邏輯運(yùn)算邏輯操作：與/或/非/…移位操作：邏輯左移/邏輯右移浮點(diǎn)數(shù)運(yùn)算：加、減、乘、除實(shí)現(xiàn)MIPS定點(diǎn)運(yùn)算指令的思路：首先實(shí)現(xiàn)一個(gè)能進(jìn)行基本算術(shù)運(yùn)算（加/減）和基本邏輯運(yùn)算（與/或/或非）、并能生成基本條件碼（ZF/VF/CF/NF）的ALU，再由ALU和移位器實(shí)現(xiàn)乘除運(yùn)算器。ALU是運(yùn)算部件的核心！以下介紹ALU的實(shí)現(xiàn)。ALU的位置ALU（Arithmeticlogicunit）:算術(shù)邏輯部件功能：能進(jìn)行基本算術(shù)、邏輯運(yùn)算，并生成條件碼CPUDatapathControlALURegsShifterNandGateWearenowhere.硬件功能描述（DesignasRepresentation）(1)FunctionalSpecification(功能說(shuō)明)

Inputs:2x16bitoperands－A,B;1bitcarryinput－Cin.Outputs:1x16bitresult－S;1bitcarryoutput－Cout.Operations:PASS,ADD(A+B+Cin),SUB(A-B),AND,XOR,OR,COMPARE(equality)"VHDLBehavior"(2)BlockDiagram/Schematic（框圖/原理圖表示）ALUABMCinCoutS1616163操作控制"VHDLEntity"VHDL(Very-High-SpeedIntegratedCircuitHardwareDescriptionLanguage)1987年底IEEE和美國(guó)國(guó)防部確定其為標(biāo)準(zhǔn)硬件描述語(yǔ)言進(jìn)位輸入進(jìn)位輸出運(yùn)算結(jié)果操作數(shù)A操作數(shù)BALU的功能說(shuō)明ALUControlLines(ALUop) Function000 And001 Or010 Add110 Subtract111 Set-on-less-thanALUNNNABResultOverflowZero3ALUopCarryOutALU可進(jìn)行基本的加/減算術(shù)運(yùn)算、基本邏輯運(yùn)算。其核心部件是加法器。有關(guān)串行加法器和并行加法器的原理在數(shù)字邏輯電路課已講過(guò)，在此僅簡(jiǎn)單回顧?；仡櫍捍羞M(jìn)位加法器Sum延遲為6ty；進(jìn)位Carryout延遲為２ty(假定一個(gè)與門/或門延遲為1ty，異或門的延遲則為３ty)FA全加器符號(hào)：FAFAFAn位串行(行波)加法器：串行加法器的缺點(diǎn)：進(jìn)位按串行方式傳遞，速度慢！問(wèn)題：n位串行加法器從C0到Cn的延遲時(shí)間為多少？最后一位和數(shù)的延遲時(shí)間為多少？2n+1級(jí)門延遲！2n級(jí)門延遲！回顧：并行進(jìn)位加法器為什么用先行進(jìn)位方式？串行（行波）進(jìn)位加法器采用串行逐級(jí)傳遞進(jìn)位，電路的延遲與位數(shù)成正比關(guān)系。

因此，現(xiàn)代計(jì)算機(jī)采用一種先行進(jìn)位(Carrylookahead)方式。如何產(chǎn)生先行進(jìn)位？定義兩個(gè)輔助函數(shù)：Gi=XiYi…進(jìn)位生成Pi=Xi+Yi…進(jìn)位傳遞（或Pi=Xi⊕Yi

）

通常把實(shí)現(xiàn)上述邏輯的電路稱為進(jìn)位生成/傳遞部件

全加邏輯方程：Si=Pi⊕CiCi+1=Gi+PiCi

(i=0,1,…n)

設(shè)n=4,則：C1=G0+P0C0C2=G1+P1C1=G1+P1G0+P1P0C0

C3=G2+P2C2=G2+P2G1+P2P1G0+P2P1P0C0

C4=G3+P3C3=G3+P3G2+P3P2G1+P3P2P1G0+P3P2P1P0C0由上式可知:各進(jìn)位之間無(wú)等待，相互獨(dú)立并同時(shí)產(chǎn)生。通常把實(shí)現(xiàn)上述邏輯的電路稱為4位CLA部件由此，根據(jù)Si=Pi⊕Ci，可并行求出各位和。通常把實(shí)現(xiàn)Si=Pi⊕Ci的電路稱為求和部件CLA加法器由“進(jìn)位生成/傳遞部件”、“CLA部件”和“求和部件”構(gòu)成。

回顧：8位全先行進(jìn)位加法器進(jìn)位生成/傳遞部件A7A0B7B0P7P1P0G7G1G08位CLA部件C0求和部件P7P1P0C0C1C7C8S7S0S13ty2ty3ty和的總延遲：3+2+3=8ty；進(jìn)位C8的延遲：3+2=5ty回顧：局部先行進(jìn)位加法器問(wèn)題：所有和數(shù)產(chǎn)生的延遲為多少？或稱單級(jí)先行進(jìn)位加法器5+2+2+5=14ty(3)多級(jí)先行進(jìn)位加法器單級(jí)(局部)先行進(jìn)位加法器的進(jìn)位生成方式：“組內(nèi)并行、組間串行”所以，單級(jí)先行進(jìn)位加法器雖然比行波加法器延遲時(shí)間短，但高位組進(jìn)位依賴低位組進(jìn)位，故仍有較長(zhǎng)的時(shí)間延遲通過(guò)引入組進(jìn)位生成/傳遞函數(shù)來(lái)實(shí)現(xiàn)“組內(nèi)并行、組間并行”進(jìn)位方式設(shè)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*=P3P2P1P0所以C4=G3*+P3*C0。把實(shí)現(xiàn)上述邏輯的電路稱為4位BCLA部件?；仡櫍憾嗉?jí)先行進(jìn)位加法器關(guān)鍵路徑長(zhǎng)度為多少？最終進(jìn)位的延遲為多少？4位成組先行進(jìn)位部件（4位BCLA部件）4位先行進(jìn)位加法器4位先行進(jìn)位加法器4位先行進(jìn)位加法器4位先行進(jìn)位加法器16位兩級(jí)先行進(jìn)位加法器3+2+3=8ty3+2=5tyA4-bitALU

1-bitALU 4-bit串行ALUAB1-bitFullAdderCarryOutMuxCarryInResultA0B01-bitALUResult0CarryIn0CarryOut0A1B11-bitALUResult1CarryIn1CarryOut1A2B21-bitALUResult2CarryIn2CarryOut2A3B31-bitALUResult3CarryIn3CarryOut3MUX是什么？（數(shù)字電路課學(xué)過(guò)）關(guān)鍵路徑延遲長(zhǎng)，速度慢！先行進(jìn)位ALU先行進(jìn)位ALU

芯片（SN74181）四位ALU芯片，中規(guī)模集成電路。在先行進(jìn)位加法器基礎(chǔ)上附加部分線路，具有基本的算術(shù)運(yùn)算和邏輯運(yùn)算功能。SN74181的邏輯圖和功能表SN74182是4位BCLA(成組先行進(jìn)位)芯片。多芯片級(jí)聯(lián)構(gòu)成先行進(jìn)位ALU1個(gè)SN74181芯片直接構(gòu)成一個(gè)4位全先行進(jìn)位ALU4個(gè)SN74181芯片串行構(gòu)成一個(gè)16位單級(jí)先行進(jìn)位ALU4個(gè)SN74181芯片與1個(gè)SN74182芯片可構(gòu)成16位兩級(jí)先行進(jìn)位ALU16個(gè)SN74181芯片與5個(gè)SN74182芯片可構(gòu)成64位先行進(jìn)位ALUSKIPALU中的“加”運(yùn)算電路相當(dāng)于n檔二進(jìn)制加法算盤。所有其他運(yùn)算都以ALU中“加”運(yùn)算為基礎(chǔ)！SN74181的引腳輸入端：Ai和Bi分別為第1和2操作數(shù)，Cn為低位進(jìn)位，M為功能選擇線，Si為操作選擇線，共4位，故最多有16種運(yùn)算。輸出端：Fi為運(yùn)算結(jié)果，Cn+4、P和G為進(jìn)位，“A=B”為相等標(biāo)志P輸入端輸出端SN74181邏輯電路圖SN74181正邏輯功能表BACKSN74182芯片的引腳輸入端：Pi和Gi分別為第i組的組內(nèi)進(jìn)位傳遞函數(shù)和進(jìn)位生成函數(shù)，Cn為低位進(jìn)位。輸出端：

Cn+4、Cn+8、Cn+12為相應(yīng)組的組內(nèi)進(jìn)位，P*和G*分別為整個(gè)大組的組進(jìn)位傳遞函數(shù)和進(jìn)位生成函數(shù)。SN74182芯片的邏輯電路圖BACKSN74181和SN74182組成16位先行進(jìn)位ALU4位ALU4位ALU4位ALU4位ALU16位兩級(jí)先行進(jìn)位ALUBACK第一講小結(jié)C語(yǔ)言程序中涉及的運(yùn)算整數(shù)算術(shù)運(yùn)算、浮點(diǎn)數(shù)算術(shù)運(yùn)算按位、邏輯、移位、位擴(kuò)展和位截?cái)嘀噶罴信c運(yùn)算相關(guān)的指令（以MIPS為參考）涉及到的定點(diǎn)數(shù)運(yùn)算算術(shù)運(yùn)算帶符號(hào)整數(shù)運(yùn)算：取負(fù)/符號(hào)擴(kuò)展/加/減/乘/除/算術(shù)移位無(wú)符號(hào)整數(shù)運(yùn)算：0擴(kuò)展/加/減/乘/除邏輯運(yùn)算邏輯操作：與/或/非/…移位操作：邏輯左移/邏輯右移涉及到的浮點(diǎn)數(shù)運(yùn)算：加、減、乘、除基本運(yùn)算部件ALU的設(shè)計(jì)全加器、串行加法器、先行進(jìn)位加法器串行ALU、先行進(jìn)位ALU（單級(jí)/多級(jí)）定點(diǎn)運(yùn)算包括：無(wú)符號(hào)數(shù)

按位邏輯運(yùn)算邏輯移位運(yùn)算位擴(kuò)展和截?cái)噙\(yùn)算加/減/乘/除運(yùn)算帶符號(hào)整數(shù)

算術(shù)移位運(yùn)算擴(kuò)展運(yùn)算和截?cái)噙\(yùn)算

補(bǔ)碼加/減/乘/除運(yùn)算浮點(diǎn)運(yùn)算包括：

原碼加/減/乘/除運(yùn)算

移碼加/減運(yùn)算切記：ALU中的“加”運(yùn)算電路相當(dāng)于n檔二進(jìn)制加法算盤。所有其他運(yùn)算都以ALU“加”運(yùn)算為基礎(chǔ)！是模運(yùn)算系統(tǒng)！第二講：定點(diǎn)數(shù)運(yùn)算及運(yùn)算部件主要內(nèi)容加/減運(yùn)算及其運(yùn)算部件補(bǔ)碼/原碼/移碼加減運(yùn)算乘法運(yùn)算及其運(yùn)算部件原碼/補(bǔ)碼乘法運(yùn)算快速乘法器除法運(yùn)算及其運(yùn)算部件原碼/補(bǔ)碼除法運(yùn)算快速除法器定點(diǎn)運(yùn)算器十進(jìn)制加減運(yùn)算注：無(wú)符號(hào)數(shù)的按位邏輯運(yùn)算可用邏輯門電路實(shí)現(xiàn)；無(wú)符號(hào)數(shù)的邏輯移位運(yùn)算可用專門的移位器或斜送結(jié)果等多種方式來(lái)實(shí)現(xiàn)；帶符號(hào)數(shù)的移位運(yùn)算、無(wú)符號(hào)數(shù)和帶符號(hào)整數(shù)的位擴(kuò)展運(yùn)算和截?cái)噙\(yùn)算也可用簡(jiǎn)單電路很容易地實(shí)現(xiàn)。補(bǔ)碼加/減運(yùn)算及其部件補(bǔ)碼加減運(yùn)算公式[X+Y]補(bǔ)=[X]補(bǔ)+[Y]補(bǔ)(MOD2n)[X–Y]補(bǔ)=[X]補(bǔ)+[–Y]補(bǔ)(MOD2n)補(bǔ)碼加減運(yùn)算要點(diǎn)和運(yùn)算部件加、減法運(yùn)算統(tǒng)一采用加法來(lái)處理符號(hào)位(最高有效位MSB)和數(shù)值位一起參與運(yùn)算直接用ALU實(shí)現(xiàn)兩個(gè)數(shù)的加運(yùn)算（模運(yùn)算系統(tǒng)）

問(wèn)題：模是多少？運(yùn)算結(jié)果的高位丟棄，保留低n位，相當(dāng)于對(duì)和數(shù)取模2n

實(shí)現(xiàn)減法的主要工作在于：求[–Y]補(bǔ)問(wèn)題：如何求[–Y]補(bǔ)？[–B]補(bǔ)=B+1ALU444AResultZeroCarryInCarryOut4B401MuxSelSubBoverflow補(bǔ)碼加減運(yùn)算部件當(dāng)控制端Sub為1時(shí)，做減法，實(shí)現(xiàn)A–B當(dāng)控制端Sub為0時(shí)，做加法，實(shí)現(xiàn)A+B問(wèn)題：補(bǔ)碼加減運(yùn)算的用途是什么？用于實(shí)現(xiàn)帶符號(hào)整數(shù)的加減運(yùn)算！補(bǔ)碼加/減運(yùn)算與“溢出”判斷Example1:-7-6=-7+(-6)=+3 -3-5=-3+(-5)=-811++00011110011101111000100011Example2:用8位補(bǔ)碼求107和46的“和”結(jié)果錯(cuò)誤:107+46=-103.10710=0110101124610=001011102

0

10011001

11111

有兩種“溢出”判斷規(guī)則:

1.和的符號(hào)位和加數(shù)的符號(hào)位不同2.最高位和次高位的進(jìn)位不同溢出時(shí)，符號(hào)位的進(jìn)位是真正的符號(hào)：+15311溢出現(xiàn)象：(1)最高位和次高位的進(jìn)位不同(2)和的符號(hào)位和加數(shù)的符號(hào)位不同X√問(wèn)題：若采用變形補(bǔ)碼則結(jié)果怎樣？有何好處？結(jié)果的值為010011001，左邊第一位為真正的符號(hào)，數(shù)值部分進(jìn)到了右邊符號(hào)位上。采用變形補(bǔ)碼時(shí)的“溢出”判斷條件：結(jié)果的兩個(gè)符號(hào)位不同采用變形補(bǔ)碼時(shí)，可保留運(yùn)算中間結(jié)果。從乘除運(yùn)算過(guò)程可看出這點(diǎn)！OverflowDetectionLogic(溢出判斷邏輯)CarryintoMSB!=CarryoutofMSBForaN-bitALU:Overflow=CarryIn[N-1]XORCarryOut[N-1]OverflowXYXXORY00011101110A0B01-bitALUResult0CarryIn0CarryOut0A1B11-bitALUResult1CarryIn1CarryOut1A2B21-bitALUResult2CarryIn2CarryOut2A3B31-bitALUResult3CarryIn3CarryOut30也可以用其他判斷方法。ZeroDetectionLogic(判0邏輯)ZeroA0B01-bitALUResult0CarryIn0CarryOut0A1B11-bitALUResult1CarryIn1CarryOut1A2B21-bitALUResult2CarryIn2CarryOut2A3B31-bitALUResult3CarryIn3CarryOut3除Result、“0”（ZF）、“Overflow”標(biāo)志（OF）外，許多機(jī)器還提供進(jìn)位標(biāo)志（CF）、符號(hào)標(biāo)志（NF/SF）等。標(biāo)志在運(yùn)算電路中產(chǎn)生，被記錄到專門的寄存器中，以便在分支指令中被用來(lái)作為條件。存放標(biāo)志的寄存器通常稱為程序/狀態(tài)字寄存器或標(biāo)志寄存器。每個(gè)標(biāo)志對(duì)應(yīng)標(biāo)志寄存器中的一個(gè)標(biāo)志位。

問(wèn)題：MIPS指令bne$1,$2,25的含義為：If($1!=$2)gotoPC+4+100elsegotoPC+4執(zhí)行beq指令，需要判斷什么標(biāo)志？原碼加/減運(yùn)算用于浮點(diǎn)數(shù)尾數(shù)運(yùn)算符號(hào)位和數(shù)值部分分開(kāi)處理僅對(duì)數(shù)值部分進(jìn)行加減運(yùn)算，符號(hào)位起判斷和控制作用規(guī)則如下：比較兩數(shù)符號(hào)，對(duì)加法實(shí)行“同號(hào)求和，異號(hào)求差”，對(duì)減法實(shí)行“異號(hào)求和，同號(hào)求差”。求和：數(shù)值位相加，若最高位產(chǎn)生進(jìn)位，則結(jié)果溢出。和的符號(hào)取被加數(shù)（被減數(shù)）的符號(hào)。求差：被加數(shù)（被減數(shù)）加上加數(shù)（減數(shù)）的補(bǔ)碼。分二種情況討論：最高數(shù)值位產(chǎn)生進(jìn)位，表明加法結(jié)果為正，所得數(shù)值位正確。最高數(shù)值位沒(méi)有產(chǎn)生進(jìn)位，表明加法結(jié)果為負(fù)，得到的是數(shù)值位的補(bǔ)碼形式，需對(duì)結(jié)果求補(bǔ)，還原為絕對(duì)值形式的數(shù)值位。差的符號(hào)位：a)情況下，符號(hào)位取被加數(shù)（被減數(shù)）的符號(hào)

b)情況下，符號(hào)位為被加數(shù)（被減數(shù)）的符號(hào)取反原碼加/減運(yùn)算例1：已知[X]原=1.0011，[Y]原=1.1010，要求計(jì)算[X+Y]原解：根據(jù)原碼加減運(yùn)算規(guī)則，知：兩數(shù)同號(hào)，用加法求和，和的符號(hào)同被加數(shù)符號(hào)。所以：和的數(shù)值位為：0011+1010=1101（ALU中無(wú)符號(hào)數(shù)加）和的符號(hào)位為：1

[X+Y]原=1.1101例2：已知[X]原=1.0011，[Y]原=1.1010，要求計(jì)算[X–Y]原解：根據(jù)原碼加減運(yùn)算規(guī)則，知：兩數(shù)同號(hào)，用減法求差（補(bǔ)碼減法）差的數(shù)值位為：0011+(1010)補(bǔ)=0011+0110=1001

最高數(shù)值位沒(méi)有產(chǎn)生進(jìn)位，表明加法結(jié)果為負(fù)，需對(duì)1001求補(bǔ)，還原為絕對(duì)值形式的數(shù)值位。即：（1001）補(bǔ)=0111差的符號(hào)位為[X]原的符號(hào)位取反，即：0

[X–Y]原=0.0111思考題：如何設(shè)計(jì)一個(gè)基于ALU的原碼加/減法器？求和：直接加，有進(jìn)位則溢出，符號(hào)同被求差：加補(bǔ)碼，不會(huì)溢出，符號(hào)分情況移碼加/減運(yùn)算用于浮點(diǎn)數(shù)階碼運(yùn)算符號(hào)位和數(shù)值部分可以一起處理運(yùn)算公式（假定在一個(gè)n位ALU中進(jìn)行加法運(yùn)算）

[E1]移

+[E2]移

=2n-1+E1+2n-1+E2=2n+E1+E2=[E1+E2]補(bǔ)（mod2n）

[E1]移

–[E2]移

=[E1]移

+[–[E2]移]補(bǔ)=2n-1+E1+2n–[E2]移

=2n-1+E1+2n–2n-1–E2=2n+E1–E2=[E1–E2]補(bǔ)（mod2n）

結(jié)論：移碼的和、差等于和、差的補(bǔ)碼！運(yùn)算規(guī)則①加法：直接將[E1]移和[E2]移進(jìn)行模2n相加，然后對(duì)結(jié)果的符號(hào)取反。②減法：先將減數(shù)[E2]移求補(bǔ)（各位取反，末位加1），然后再與被減數(shù)[E1]移進(jìn)行模2n相加，最后對(duì)結(jié)果的符號(hào)取反。③溢出判斷：進(jìn)行模2n相加時(shí)，如果兩個(gè)加數(shù)的符號(hào)相同，并且與和數(shù)的符號(hào)也相同，則發(fā)生溢出。補(bǔ)碼和移碼的關(guān)系：符號(hào)位相反、數(shù)值位相同！思考題：如何設(shè)計(jì)一個(gè)基于ALU的移碼加/減法器？

IEEE754SP格式的偏置常數(shù)是127，這會(huì)不會(huì)影響階碼運(yùn)算電路的復(fù)雜度？對(duì)計(jì)算[E1–E2]補(bǔ)（mod2n）沒(méi)有影響，但[E1+E2]移和[E1–E2]移的計(jì)算變復(fù)雜！[

E]補(bǔ)=256+Ex–Ey=256+127+Ex-(127+Ey)=256+[Ex]移

-[Ey]移=[Ex]移+[-[Ey]移]補(bǔ)

(mod256)移碼加/減運(yùn)算例1：用四位移碼計(jì)算“–7+（–6）”和“–3+6”的值。解：[–7]移=0001[–6]移=0010 [–3]移=0101 [6]移=1110[–7]移+[–6]移=0001+0010=0011（兩個(gè)加數(shù)與結(jié)果符號(hào)都為0，溢出）[–3]移+[6]移=0101+1110=0011，符號(hào)取反后為1011，其真值為+3

問(wèn)題：[–7+(–6)]移=?[–3+(6)]移=？

例2：用四位移碼計(jì)算“–7–（–6）”和“–3–5”的值。解：[–7]移=0001[–6]移=0010 [–3]移=0101 [5]移=1101 [–7]移–[–6]移=0001+1110=1111，符號(hào)取反后為0111，其真值為–1。[–3]移–[5]移=0101+0011=1000，符號(hào)取反后為0000，其真值為–8。無(wú)符號(hào)數(shù)的乘法運(yùn)算Paperandpencilexample: Multiplicand1000

Multiplier x1001

1000

0000

0000

1000

Product(積)1001000手工乘法的特點(diǎn)：每步計(jì)算：X×yi，若yi=0，則得0；若yi=1，則得X把①求得的各項(xiàng)結(jié)果X×yi

逐次左移，可表示為X×yi×2-i

對(duì)②中求得的結(jié)果求和，即

(X×yi×2-i)，這就是兩個(gè)無(wú)符號(hào)數(shù)的乘積計(jì)算機(jī)內(nèi)部稍作以下改進(jìn)：每次得X×yi后，與前面所得結(jié)果累加，得到Pi，稱之為部分積。因?yàn)闆](méi)有等到全部計(jì)算后一次求和，所以減少了保存每次相乘結(jié)果X×yi的開(kāi)銷。每次得X×yi后，不將它左移與前次部分積Pi相加，而將部分積Pi右移后與X×yi相加。因?yàn)榧臃ㄟ\(yùn)算始終對(duì)部分積中高n位進(jìn)行。故用n位加法器可實(shí)現(xiàn)二個(gè)n位數(shù)相乘。乘數(shù)中為“1”位執(zhí)行加法和右移，對(duì)為“0”位只執(zhí)行右移，而不執(zhí)行加法運(yùn)算。(乘數(shù))(被乘數(shù))假定：[X]

=0.x1

xn，[Y]

=0.y1

yn

，則：z1z2n=(0.x1xn)×(0.y1yn)(小數(shù)點(diǎn)位置約定，不區(qū)分小數(shù)還是整數(shù))X×y4×2-4X×y3×2-3X×y2×2-2X×y1×2-1

4X×Y=

(X×yi×2-i)

i=1整個(gè)運(yùn)算過(guò)程中用到兩種操作：加法+左移因而，可用ALU和移位器來(lái)實(shí)現(xiàn)乘法運(yùn)算思考題：若計(jì)算機(jī)完全模擬這樣做，則如何實(shí)現(xiàn)？陣列乘法器或流水線乘法器無(wú)符號(hào)乘法運(yùn)算的算法推導(dǎo)上述改進(jìn)思想可寫成如下數(shù)學(xué)推導(dǎo)過(guò)程：

X×Y=X×(0.y1y2…yn) =X×y1×2-1+X×y2×2-2+X×y3×2-3+…+X×yn×2-n

=2-1(2-1(2-1…2-1(2-1(0+X×yn)+X×yn-1)+…+X×y2)+X×y1)n個(gè)2-1上述推導(dǎo)過(guò)程具有明顯的遞歸性質(zhì)，因此，無(wú)符號(hào)數(shù)乘法過(guò)程可歸結(jié)為循環(huán)計(jì)算下列算式的過(guò)程：設(shè)P0=0，每步的乘積為：

P1=2-1(P0+X×yn)P2=2-1(P1+X×yn-1)…………

Pn=2-1(Pn-1+X×y1)其遞推公式為：Pi+1=2-1(Pi+X×yn-i)(i=0,1,2,3,…,n-1)最終乘積Pn=X×Y迭代過(guò)程從乘數(shù)最低位yn和P0=0開(kāi)始，經(jīng)n次“判斷–加法–右移”循環(huán)，直到求出Pn為止。假定每次循環(huán)需要一個(gè)時(shí)鐘周期，則n位乘法需要n個(gè)時(shí)鐘周期完成。寫使能控制邏輯右移32位

ALU被乘數(shù)寄存器X乘積寄存器P3264位323232加計(jì)數(shù)器Cn時(shí)鐘C乘數(shù)寄存器Y32位乘法運(yùn)算的硬件實(shí)現(xiàn)被乘數(shù)寄存器X：存放被乘數(shù)乘積寄存器P：開(kāi)始時(shí)，置初始部分積P0=0；結(jié)束時(shí)，存放的是64位乘積的高32位乘數(shù)寄存器Y：開(kāi)始時(shí)，置乘數(shù)；結(jié)束時(shí)，存放的是64位乘積的低32位進(jìn)位觸發(fā)器C：保存加法器的進(jìn)位信號(hào)循環(huán)次數(shù)計(jì)數(shù)器Cn：存放循環(huán)次數(shù)。初值32，每循環(huán)一次，Cn減1，Cn=0時(shí)結(jié)束ALU：乘法核心部件。在控制邏輯控制下，對(duì)乘積寄存器P和被乘數(shù)寄存器X的內(nèi)容進(jìn)行“加”運(yùn)算，在“寫使能”控制下運(yùn)算結(jié)果被送回乘積寄存器P，進(jìn)位位存放在C中每次循環(huán)都要對(duì)進(jìn)位位C、乘積寄存器P和乘數(shù)寄存器實(shí)現(xiàn)同步“右移”

Example：無(wú)符號(hào)整數(shù)乘法運(yùn)算舉例說(shuō)明：設(shè)A=1110B=1101應(yīng)用遞推公式：Pi=2-1(Abi+Pi-1)C乘積P乘數(shù)R000001101+1110011101101001110110000111011+1110100011011010001101+1110101101101010110110可用一個(gè)雙倍字長(zhǎng)的乘積寄存器；也可用兩個(gè)單倍字長(zhǎng)的寄存器。部分積初始為0。保留進(jìn)位位。右移時(shí)進(jìn)位、部分積和剩余乘數(shù)一起進(jìn)行邏輯右移。驗(yàn)證：A=14,B=13,AxB=182原碼乘法算法用于浮點(diǎn)數(shù)尾數(shù)乘運(yùn)算符號(hào)與數(shù)值分開(kāi)處理：積符用兩個(gè)符號(hào)異或得到，數(shù)值用無(wú)符號(hào)乘法運(yùn)算例：設(shè)[x]原=0.1110，[y]原=1.1101，計(jì)算[X×Y]原

解：數(shù)值部分用無(wú)符號(hào)數(shù)乘法算法計(jì)算：1110×1101=10110110

符號(hào)位：0

1=1，所以：[X×Y]原=1.10110110上述算法稱為原碼一位乘法，其實(shí)現(xiàn)思想為：

每次只取乘數(shù)中的一位進(jìn)行判斷，需n次循環(huán)，速度相對(duì)較慢。原碼兩位乘法的思想：對(duì)乘數(shù)的每?jī)晌蝗≈颠M(jìn)行判斷，每步求出對(duì)應(yīng)兩位的部分積。原碼兩位乘法的操作的遞推公式：00—Pi+1=2-2Pi

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操作迭代公式0000010100111001011101110

T+X0T+X0T+2X0T+2X0T–X1T–X1T1T

2-2(Pi)2-2(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觸發(fā)器用來(lái)記錄下次是否要執(zhí)行“+X”“–X”運(yùn)算用“+[-X]補(bǔ)”實(shí)現(xiàn)！采用兩位一乘，運(yùn)算速度提高多少？運(yùn)算次數(shù)減少一半，速度提高一倍！3X時(shí)，本次-X，下次+X！原碼兩位乘法舉例已知[X]原=0.111001，[Y]原=0.100111，用原碼兩位乘法計(jì)算[X×Y]原解：先采用無(wú)符號(hào)數(shù)乘法計(jì)算111001×100111的乘積，原碼兩位乘法過(guò)程如下：若采用模4補(bǔ)碼，則進(jìn)行P和Y同時(shí)右移2位操作時(shí)，按照補(bǔ)碼右移規(guī)則，得到的P3是負(fù)數(shù)，顯然，兩個(gè)正數(shù)相乘，乘積不可能是負(fù)數(shù)采用補(bǔ)碼右移數(shù)據(jù)為模8補(bǔ)碼形式（三位符號(hào)位），為什么？補(bǔ)碼乘法運(yùn)算用于定點(diǎn)整數(shù)乘法運(yùn)算符號(hào)與數(shù)值統(tǒng)一處理假定：[A]補(bǔ)=an-1an-2……

a1a0(an-1為數(shù)符）

[

B]補(bǔ)=bn-1bn-2……

b1b0(bn-1為數(shù)符）求：[A

B]補(bǔ)=？基于以下補(bǔ)碼性質(zhì)：令：[A]補(bǔ)=an-1an-2……

a1a0，

則：A=-an-1.2n-1+an-2.2n-2+

……

a1.21+

a0.20令：a-1=0，則：當(dāng)n=32時(shí)，A=-a31.231+a30.230+

……

a1.21+

a0.20

+

a-1.20

-a31.231+(a30.231-a30.230)+……+(a0.21-a0.20)+a-1.20

(a30-a31).231+(a29-a30).230+……+(a0–a1).21+(a-1-a0).20

部分積公式：Pi=2-1((ai-1-ai)×B+Pi-1)Booth’sAlgorithm推導(dǎo)如下：因?yàn)閇Ax

B]補(bǔ)

[A]補(bǔ)

x[B]補(bǔ)，故不能直接用無(wú)符號(hào)乘法計(jì)算。Booth’s算法實(shí)質(zhì)當(dāng)前位

右邊位 操作 Example 1 0 減被乘數(shù) 0001111000 1 1 加0(不操作) 0001111000 0 1 加被乘數(shù) 0001111000 0 0 加0(不操作) 0001111000最初提出這種想法是因?yàn)樵贐ooth的機(jī)器上移位操作比加法更快！在“1串”中，第一個(gè)1時(shí)做減法，最后一個(gè)1做加法，其余情況只要移位。同前面算法一樣，將乘積寄存器右移一位。（這里是算術(shù)右移）Multiplicand Product(2x7)

0010 000001110Multiplicand Product(2x-3)

0010 000011010例：BoothsExample:2x71a.P=P-m 1110+ 1110 111001110 shiftP(signext)1b. 0010 11110011

1 11->nop,shift2. 0010 11111001

1 11->nop,shift3. 0010 11111100

1 01->add4a. 0010+ 0010

00011100

1

shift4b. 0010 000011100 done Operation Multiplicand Product|Multiplier next?0.initialvalue 0010 000001110 10->submythicalbit最后乘積BoothsExample:2x–31a.P=P-m 1110+ 1110 111011010 shiftP(signext)1b. 0010 11110110

1 01->add +0010 2a. 00010110

1 shiftP2b. 0010 00001011

0 10->sub + 11103a. 0010 11101011

0 shift3b. 0010 111101011 11->nop4a 111101011 shift4b. 0010 11111010

1 done Operation Multiplicand Product next?0.initialvalue 0010 000011010 10->submythicalbit最后乘積補(bǔ)碼兩位乘法補(bǔ)碼兩位乘可用布斯算法推導(dǎo)如下：[Pi+1]補(bǔ)

=2-1([Pi]補(bǔ)

+(yi-1–yi)[X]補(bǔ))[Pi+2]補(bǔ)

=2-1([Pi+1]補(bǔ)

+(yi–yi+1)[X]補(bǔ))=2-1(2-1([Pi]補(bǔ)

+(yi-1–yi)[X]補(bǔ))+(yi–yi+1)[X]補(bǔ))=2-2([Pi]補(bǔ)+(yi-1+yi–2yi+1)[X]補(bǔ))開(kāi)始置附加位y-1為0，乘積寄存器最高位前面添加一位附加符號(hào)位0。最終的乘積高位部分在乘積寄存器P中，低位部分在乘數(shù)寄存器Y中。因?yàn)樽珠L(zhǎng)總是8的倍數(shù)，所以補(bǔ)碼的位數(shù)n應(yīng)該是偶數(shù)，因此，總循環(huán)次數(shù)為n/2。yi+1

yi

yi-1操作迭代公式0000010100111001011101110+[X]補(bǔ)+[X]補(bǔ)+2[X]補(bǔ)+2[-X]

補(bǔ)+[-X]補(bǔ)+[-X]補(bǔ)02-2[Pi]補(bǔ)2-2{[Pi]補(bǔ)+[X]補(bǔ)}2-2{[Pi]補(bǔ)+[X]補(bǔ)}2-2{[Pi]補(bǔ)+2[X]補(bǔ)}2-2{[Pi]補(bǔ)+2[-X]補(bǔ)}2-2{[Pi]補(bǔ)+[-X]補(bǔ)}2-2{[Pi]補(bǔ)+[-X]補(bǔ)}2-2[Pi]補(bǔ)補(bǔ)碼兩位乘法舉例已知[X]補(bǔ)

=1101，[Y]補(bǔ)

=0110，用補(bǔ)碼兩位乘法計(jì)算[X×Y]補(bǔ)。解：[–X]補(bǔ)=0011，用補(bǔ)碼二位乘法計(jì)算[X×Y]補(bǔ)的過(guò)程如下。

PnPYy-1

說(shuō)明

0000001100

開(kāi)始，設(shè)y-1=0，[P0]補(bǔ)

=0+00110y1y0y-1=100，+2[-X]補(bǔ)00110P和Y同時(shí)右移二位0000110011得[P2]補(bǔ)+11010y3y2y1=011，+2[X]補(bǔ)11011P和Y同時(shí)右移二位111101110得[P4]補(bǔ)因此[X×Y]補(bǔ)=11101110

，與一位補(bǔ)碼乘法（布斯乘法）所得結(jié)果相同，但循環(huán)次數(shù)減少了一半。驗(yàn)證：-3×6=-18（-10010B）快速乘法器前面介紹的乘法部件的特點(diǎn)：通過(guò)一個(gè)ALU多次“加/減+右移”來(lái)實(shí)現(xiàn)一位乘法：約n次“加+右移”兩位乘法：約n/2次“加+右移”存在瓶頸：所需時(shí)間隨位數(shù)增多而加長(zhǎng)設(shè)計(jì)快速乘法部件的必要性：大約1/3是乘法運(yùn)算快速乘法器的實(shí)現(xiàn)流水線方式硬件疊加方式（如：陣列乘法器）陣列乘法器用一個(gè)實(shí)現(xiàn)特定功能的組合邏輯單元構(gòu)成一個(gè)陣列流水線方式的快速乘法器為乘數(shù)的每位提供一個(gè)n位加法器每個(gè)加法器的兩個(gè)輸入端分別是：本次乘數(shù)對(duì)應(yīng)的位與被乘數(shù)相與的結(jié)果（即：0或被乘數(shù)）上次部分積每個(gè)加法器的輸出分為兩部分：和的最低有效位(LSB)作為本位乘積進(jìn)位和高31位的和數(shù)組成一個(gè)32位數(shù)作為本次部分積1問(wèn)題：右圖有沒(méi)有問(wèn)題？乘數(shù)第0位和乘數(shù)第1位對(duì)應(yīng)的兩個(gè)被乘數(shù)直接相加，有問(wèn)題嗎？可以如何改進(jìn)？陣列乘法器的實(shí)現(xiàn)手算乘法過(guò)程陣列乘法器全加器被乘數(shù)X部分積輸入AiBi進(jìn)位輸入進(jìn)位輸出

部分積輸出B00P7P6P5P4P3P2P1P0B10B20B30A3A2A1A00000乘法速度僅取決于邏輯門和加法器的傳輸延遲

在無(wú)符號(hào)數(shù)陣列乘法器的基礎(chǔ)上，增加符號(hào)處理電路、乘前及乘后求補(bǔ)電路，即可實(shí)現(xiàn)帶符號(hào)數(shù)乘法器。

定點(diǎn)除法運(yùn)算除前預(yù)處理①若被除數(shù)為0、除數(shù)不為0，或定點(diǎn)整數(shù)除法|被除數(shù)|<|除數(shù)|，則商為0，不再繼續(xù)執(zhí)行②若被除數(shù)不為0、除數(shù)為0，則發(fā)生“除數(shù)為0”異常③若被除數(shù)和除數(shù)都為0，則有些機(jī)器產(chǎn)生一個(gè)不發(fā)信號(hào)的NaN，即“quietNaN”只有當(dāng)被除數(shù)和除數(shù)都不為0，并且商也不可能為0時(shí)，才進(jìn)一步進(jìn)行除法運(yùn)算。手算除法的基本要點(diǎn)被除數(shù)與除數(shù)相減，若夠減，則上商為1；若不夠減，則上商為0。每次得到的差為中間余數(shù)，將除數(shù)右移后與上次的中間余數(shù)比較。用中間余數(shù)減除數(shù)，若夠減，則上商為1；若不夠減，則上商為0。重復(fù)執(zhí)行第②步，直到求得的商的位數(shù)足夠?yàn)橹?。?jì)算機(jī)內(nèi)部無(wú)符號(hào)數(shù)除法運(yùn)算與手算一樣，通過(guò)被除數(shù)（中間余數(shù)）減除數(shù)來(lái)得到每一位商

夠減上商1；不夠減上商0基本操作為減法（用加法實(shí)現(xiàn)）和移位，故可與乘法合用同一套硬件Divide:Paper&Pencil1001 Quotient(商)Divisor1000

1001010 Dividend(被除數(shù))

-1000

10

101

1010

-1000

10 Remainder(余數(shù))手算除法的基本要點(diǎn)被除數(shù)與除數(shù)相減，若夠減，則上商為1；若不夠減，則上商為0。每次得到的差為中間余數(shù)，將除數(shù)右移后與上次的中間余數(shù)比較。用中間余數(shù)減除數(shù)，若夠減，則上商為1；若不夠減，則上商為0。重復(fù)執(zhí)行第②步，直到求得的商的位數(shù)足夠?yàn)橹?。中間余數(shù)完全模擬手工的無(wú)符號(hào)數(shù)除法硬件實(shí)現(xiàn)64位Divisor（除數(shù)R，后n位為0）64位Rem.余數(shù)R，初始為被除數(shù)）32位Quotient（商R，初始值為0）RemainderQuotientDivisor64-bitALUShiftRightShiftLeftWriteControl32bits64bits64bits兩個(gè)n位數(shù)相除的情況：(1)兩個(gè)n位定點(diǎn)正整數(shù)（即：兩個(gè)n位無(wú)符號(hào)數(shù)

）相除：在被除數(shù)的高位添n個(gè)0(2)兩個(gè)n位定點(diǎn)正小數(shù)（即兩個(gè)作為浮點(diǎn)數(shù)尾數(shù)的n位原碼小數(shù)）相除：在被除數(shù)的低位添加n個(gè)0

這樣，就將所有情況都統(tǒng)一為：一個(gè)2n位數(shù)除以一個(gè)n位數(shù)以下是64位數(shù)除以32位數(shù)的例子問(wèn)題：第一次試商為1，說(shuō)明什么？若是無(wú)符號(hào)整數(shù)運(yùn)算，則說(shuō)明將會(huì)得到n+1位的商，因而結(jié)果“溢出”。但若是兩個(gè)n位數(shù)相除，則肯定不會(huì)溢出，為什么？若是浮點(diǎn)數(shù)中尾數(shù)原碼小數(shù)運(yùn)算，則說(shuō)明尾數(shù)部分有“溢出”，可通過(guò)浮點(diǎn)數(shù)的“右規(guī)”消除“溢出”。所以，在浮點(diǎn)數(shù)運(yùn)算器中，第一次得到的商“1”要保留。最大商為:11…11/00…01=11…11.SubtracttheDivisorregisterfromthe

Remainderregister,andplacetheresultinthe

Remainderregister.TestRemainderRemainder<0Remainder>=02a.ShifttheQuotientregistertotheleft

settingthenewrightmostbitto1.2b.RestoretheoriginalvaluebyaddingtheDivisorregtotheRemainderregandplacethesumintheRemainderreg.AlsoshifttheQuotientregistertotheleft,settingthenewLSBto03.ShifttheDivisorregisterright1bit.33rd

repetition?No:<33

repetitionsDoneYes:33

repetitionsStart手工DivideAlgorithmn位除法需n+1steps舉例：7/2=3余1DivideAlgorithm--example

Q:0000 D:00100000 R:00000111–D=111000001:R=R–DQ:0000D:00100000 R:111001112b:+D,slQ,0Q:0000

D:00100000 R:000001113:ShrD Q:0000 D:00010000 R:00000111–D=111100001:R=R–DQ:0000 D:00010000 R:111101112b:+D,slQ,0Q:0000 D:00010000 R:000001113:ShrD Q:0000 D:00001000 R:00000111–D=111110001:R=R–DQ:0000 D:00001000 R:111111112b:+D,slQ,0Q:0000 D:00001000 R:000001113:ShrD Q:0000 D:00000100 R:00000111–D=111111001:R=R–DQ:0000 D:00000100 R:000000112a:slQ,1Q:0001 D:00000100 R:000000113:ShrD Q:0001 D:00000010 R:00000011–D=111111101:R=R–DQ:0001 D:00000010 R:000000012a:slQ,1Q:0011 D:00000010 R:000000013:ShrD Q:0011D:00000001 R:00000001驗(yàn)證：7/2=3余1問(wèn)題：這里Q中第一個(gè)“0”說(shuō)明什么？不是真正的商，而是表示沒(méi)有“溢出”!對(duì)手算除法算法的觀察1/2bitsindivisor（除數(shù)寄存器）always0

=>1/2of64-bitadder、1/2ofdivisoriswasted能否考慮只用32位除數(shù)寄存器和32位ALU?可用余數(shù)左移代替除數(shù)右移可使商通過(guò)和余數(shù)一起左移來(lái)取消商寄存器開(kāi)始時(shí)先使余數(shù)左移一位

（問(wèn)題：為什么可這樣做？）因?yàn)橛鄶?shù)寄存器的左移實(shí)際上使左半部的余數(shù)和右半部的商同時(shí)左移，所以循環(huán)里面只包含了兩步。兩個(gè)寄存器的結(jié)合以及循環(huán)內(nèi)次序的調(diào)換使得余數(shù)被多左移了一次。所以最后一步余數(shù)寄存器的左半邊的余數(shù)必須向右移一位。RemainderQuotientDivisor64-bitALUShiftRightShiftLeftWriteControl32bits64bits64bits完全模擬手工的除法算法因?yàn)榻Y(jié)果肯定不“溢出”，故第1次商肯定為0，不用先做減法試商，即：將第一步換成先左移，可減少一次迭代無(wú)符號(hào)數(shù)除法算法的硬件實(shí)現(xiàn)除數(shù)寄存器Y：存放除數(shù)。余數(shù)寄存器R：置初始中間余數(shù)R0的高位部分為高32位被除數(shù)；結(jié)束時(shí)，存放的是余數(shù)。余數(shù)/商寄存器Q：開(kāi)始時(shí)，置初始中間余數(shù)R0的低位部分為低32位被除數(shù)；結(jié)束時(shí)，存放的是32位商。因?yàn)榧拇嫫鱍中存放的并不是商的全部位數(shù)，而是部分為被除數(shù)或中間余數(shù)，部分為商，只有到最后一步才是商的全部位數(shù)。循環(huán)次數(shù)計(jì)數(shù)器Cn：存放循環(huán)次數(shù)。初值是32，每循環(huán)一次，Cn減1，當(dāng)Cn=0時(shí)，除法運(yùn)算結(jié)束。ALU：除法核心部件。在控制邏輯控制下，對(duì)于余數(shù)寄存器R和除數(shù)寄存器Y的內(nèi)容進(jìn)行“加/減”運(yùn)算，在“寫使能”控制下運(yùn)算結(jié)果被送回余數(shù)寄存器R。R和Q同步“左移”，Q最高位移入R的最低位，Q空出的最低位上“商”，商的各位逐次左移到Q中。由控制邏輯根據(jù)ALU結(jié)果符號(hào)決定上商為0還是1。

DivideAlgorithmexample

D:0010 R:00000111ShlR D:0010 R:00001110R=R–D D:0010 R:11101110+D,slR,0 D:0010 R:0001

1100R=R–D D:0010R:11111100+D,slR,0 D:0010 R:0011

1000R=R–D D:0010 R:00011000slR,1D:0010 R:0011

0001R=R–DD:0010R:00010001slR,1 D:0010 R:0010

0011Shr

R(rh) D:0010 R:0001

0011驗(yàn)證：7/2=3余1Divisor Remainder0010 00000111從例子可看出：每次上商為0時(shí)，需做加法，以“恢復(fù)余數(shù)”。所以，稱為“恢復(fù)余數(shù)法”。也可在下一步運(yùn)算時(shí)把當(dāng)前多減的除數(shù)補(bǔ)回來(lái)。這種方法稱為“不恢復(fù)余數(shù)法”，又稱“加減交替法”。最后的余數(shù)需向右移一位。不恢復(fù)余數(shù)除法(加減交替法)根據(jù)恢復(fù)余數(shù)法(設(shè)B為除數(shù)，Ri為第i次中間余數(shù))，有：若Ri<0,則商上“０”，做加法恢復(fù)余數(shù)，即：Ri+1=2(Ri+2n|B|)-2n|B|=2Ri+2n|B|(由上式可知：“負(fù)，０，加”)若Ri>0,則商上“1”，不需恢復(fù)余數(shù)，即：Ri+1=2Ri-2n|B|(由上式可知：“正，１，減”)省去了恢復(fù)余數(shù)的過(guò)程注意：最后一次上商為“０”的話，需要“糾余”處理，即把試商時(shí)被減掉的除數(shù)加回去，恢復(fù)真正的余數(shù)。不恢復(fù)余數(shù)法也稱為加減交替法恢復(fù)余數(shù)法可進(jìn)一步簡(jiǎn)化為“加減交替法”帶符號(hào)數(shù)除法原碼除法商符和商值分開(kāi)處理商的數(shù)值部分由無(wú)符號(hào)數(shù)除法求得商符由被除數(shù)和除數(shù)的符號(hào)確定：同號(hào)為０，異號(hào)為１余數(shù)的符號(hào)同被除數(shù)的符號(hào)補(bǔ)碼除法方法1：同原碼除法一樣，先轉(zhuǎn)換為正數(shù)，先用無(wú)符號(hào)數(shù)除法，然后修正商和余數(shù)。方法2：直接用補(bǔ)碼除法，符號(hào)和數(shù)值一起進(jìn)行運(yùn)算，商符直接在運(yùn)算中產(chǎn)生。對(duì)于兩個(gè)n位補(bǔ)碼整數(shù)的除法運(yùn)算，被除數(shù)需要進(jìn)行符號(hào)擴(kuò)展。若被除數(shù)為2n位，除數(shù)為n位，則被除數(shù)無(wú)需擴(kuò)展。

原碼除法舉例已知[X]原=0.1011[Y]原=1.1101用恢復(fù)余數(shù)法計(jì)算[X/Y]原解：分符號(hào)位和數(shù)值位兩部分進(jìn)行。商的符號(hào)位：0

1=1商的數(shù)值位采用恢復(fù)余數(shù)法。減法操作用補(bǔ)碼加法實(shí)現(xiàn)，是否夠減通過(guò)中間余數(shù)的符號(hào)來(lái)判斷，所以中間余數(shù)要加一位符號(hào)位。因此，需先計(jì)算出:[|X|]補(bǔ)=0.1011[|Y|]補(bǔ)=0.1101[–|Y|]補(bǔ)=1.0011因?yàn)槭窃a定點(diǎn)小數(shù)，所以在被除數(shù)低位擴(kuò)展0思考：若實(shí)現(xiàn)無(wú)符號(hào)數(shù)相除即：1011除以1101，則有何不同？結(jié)果是什么？在確認(rèn)不會(huì)溢出時(shí)可省略原碼除法舉例已知[X]原=0.1011[Y]原=1.1101用不恢復(fù)余數(shù)法計(jì)算[X/Y]原解：[|X|]補(bǔ)=0.1011[|Y|]補(bǔ)=0.1101[–|Y|]補(bǔ)=1.0011

“加減交替法”的要點(diǎn)：

正、1、減負(fù)、0、加最后一步得到的結(jié)果與恢復(fù)余數(shù)法一樣！問(wèn)題：對(duì)于原碼小數(shù)和無(wú)符號(hào)整數(shù)的除法運(yùn)算，用被除數(shù)（中間余數(shù)）減除數(shù)進(jìn)行試商時(shí)，根據(jù)什么來(lái)確定是否“夠減”？中間余數(shù)的符號(hào)！補(bǔ)碼除法能否這樣來(lái)判斷呢？實(shí)現(xiàn)補(bǔ)碼除法的基本思想補(bǔ)碼