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

第一講

不同層次程序員看到的運算及ALU

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

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

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

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

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

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

FF

FFCFC7原因：對i截斷時發(fā)生了“溢出”，即：53191截斷為16位數(shù)時，無法正確表示！MIPS定點算術(shù)運算指令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位無符號數(shù)，32/16位帶符號數(shù)涉及到的操作：加/減/乘/除（有符號/無符號）MIPS邏輯運算指令涉及到的操作數(shù)：32/16位邏輯數(shù)涉及到的操作：按位與/按位或/按位或非/左移/右移MIPS定點比較和分支指令涉及到的操作數(shù)：32/16位無符號數(shù)，32/16位帶符號數(shù)涉及到的操作：大小比較和相等比較（有符號/無符號）通過減法運算實現(xiàn)“比較”操作!MIPS定點數(shù)據(jù)傳送指令涉及到的操作數(shù)：32/16位帶符號數(shù)（偏移量可以是負數(shù)）涉及到的操作：加/減/符號擴展/0擴展MIPS中的浮點算術(shù)運算指令涉及到的浮點操作數(shù)：32位單精度/64位雙精度浮點數(shù)涉及到的浮點操作：加/減/乘/除

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

lwcl$f1,x($s1)

lwcl$f2,y($s2)

add.s$f4,$f1,$f2

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

減法來實現(xiàn)比較）還涉及到的定點操作：加/減（用于地址運算）

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

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和美國國防部確定其為標準硬件描述語言進位輸入進位輸出運算結(jié)果操作數(shù)A操作數(shù)BALU的功能說明ALUControlLines(ALUop) Function000 And001 Or010 Add110 Subtract111 Set-on-less-thanALUNNNABResultOverflowZero3ALUopCarryOutALU可進行基本的加/減算術(shù)運算、基本邏輯運算。其核心部件是加法器。有關(guān)串行加法器和并行加法器的原理在數(shù)字邏輯電路課已講過，在此僅簡單回顧?；仡櫍捍羞M位加法器Sum延遲為6ty；進位Carryout延遲為２ty(假定一個與門/或門延遲為1ty，異或門的延遲則為３ty)FA全加器符號：FAFAFAn位串行(行波)加法器：串行加法器的缺點：進位按串行方式傳遞，速度慢！問題：n位串行加法器從C0到Cn的延遲時間為多少？最后一位和數(shù)的延遲時間為多少？2n+1級門延遲！2n級門延遲！回顧：并行進位加法器為什么用先行進位方式？串行（行波）進位加法器采用串行逐級傳遞進位，電路的延遲與位數(shù)成正比關(guān)系。

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

）

通常把實現(xià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由上式可知:各進位之間無等待，相互獨立并同時產(chǎn)生。通常把實現(xiàn)上述邏輯的電路稱為4位CLA部件由此，根據(jù)Si=Pi⊕Ci，可并行求出各位和。通常把實現(xiàn)Si=Pi⊕Ci的電路稱為求和部件CLA加法器由“進位生成/傳遞部件”、“CLA部件”和“求和部件”構(gòu)成。

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

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

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

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

按位邏輯運算邏輯移位運算位擴展和截斷運算加/減/乘/除運算帶符號整數(shù)

算術(shù)移位運算擴展運算和截斷運算

補碼加/減/乘/除運算浮點運算包括：

原碼加/減/乘/除運算

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

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

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

0

10011001

11111

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

1.和的符號位和加數(shù)的符號位不同2.最高位和次高位的進位不同溢出時，符號位的進位是真正的符號：+15311溢出現(xiàn)象：(1)最高位和次高位的進位不同(2)和的符號位和加數(shù)的符號位不同X√問題：若采用變形補碼則結(jié)果怎樣？有何好處？結(jié)果的值為010011001，左邊第一位為真正的符號，數(shù)值部分進到了右邊符號位上。采用變形補碼時的“溢出”判斷條件：結(jié)果的兩個符號位不同采用變形補碼時，可保留運算中間結(jié)果。從乘除運算過程可看出這點！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”標志（OF）外，許多機器還提供進位標志（CF）、符號標志（NF/SF）等。標志在運算電路中產(chǎn)生，被記錄到專門的寄存器中，以便在分支指令中被用來作為條件。存放標志的寄存器通常稱為程序/狀態(tài)字寄存器或標志寄存器。每個標志對應標志寄存器中的一個標志位。

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

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

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

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

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

[E1]移

+[E2]移

=2n-1+E1+2n-1+E2=2n+E1+E2=[E1+E2]補（mod2n）

[E1]移

–[E2]移

=[E1]移

+[–[E2]移]補=2n-1+E1+2n–[E2]移

=2n-1+E1+2n–2n-1–E2=2n+E1–E2=[E1–E2]補（mod2n）

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

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

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

-[Ey]移=[Ex]移+[-[Ey]移]補

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

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

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

Multiplier x1001

1000

0000

0000

1000

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

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

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

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

=0.x1

xn，[Y]

=0.y1

yn

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

4X×Y=

(X×yi×2-i)

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

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個2-1上述推導過程具有明顯的遞歸性質(zhì)，因此，無符號數(shù)乘法過程可歸結(jié)為循環(huán)計算下列算式的過程：設(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迭代過程從乘數(shù)最低位yn和P0=0開始，經(jīng)n次“判斷–加法–右移”循環(huán)，直到求出Pn為止。假定每次循環(huán)需要一個時鐘周期，則n位乘法需要n個時鐘周期完成。寫使能控制邏輯右移32位

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

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

解：數(shù)值部分用無符號數(shù)乘法算法計算：1110×1101=10110110

符號位：0

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

每次只取乘數(shù)中的一位進行判斷，需n次循環(huán)，速度相對較慢。原碼兩位乘法的思想：對乘數(shù)的每兩位取值進行判斷，每步求出對應兩位的部分積。原碼兩位乘法的操作的遞推公式：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ā)器用來記錄下次是否要執(zhí)行“+X”“–X”運算用“+[-X]補”實現(xiàn)！采用兩位一乘，運算速度提高多少？運算次數(shù)減少一半，速度提高一倍！3X時，本次-X，下次+X！原碼兩位乘法舉例已知[X]原=0.111001，[Y]原=0.100111，用原碼兩位乘法計算[X×Y]原解：先采用無符號數(shù)乘法計算111001×100111的乘積，原碼兩位乘法過程如下：若采用模4補碼，則進行P和Y同時右移2位操作時，按照補碼右移規(guī)則，得到的P3是負數(shù)，顯然，兩個正數(shù)相乘，乘積不可能是負數(shù)采用補碼右移數(shù)據(jù)為模8補碼形式（三位符號位），為什么？補碼乘法運算用于定點整數(shù)乘法運算符號與數(shù)值統(tǒng)一處理假定：[A]補=an-1an-2……

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

[

B]補=bn-1bn-2……

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

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

a1a0，

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

……

a1.21+

a0.20令：a-1=0，則：當n=32時，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推導如下：因為[Ax

B]補

[A]補

x[B]補，故不能直接用無符號乘法計算。Booth’s算法實質(zhì)當前位

右邊位 操作 Example 1 0 減被乘數(shù) 0001111000 1 1 加0(不操作) 0001111000 0 1 加被乘數(shù) 0001111000 0 0 加0(不操作) 0001111000最初提出這種想法是因為在Booth的機器上移位操作比加法更快！在“1串”中，第一個1時做減法，最后一個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最后乘積補碼兩位乘法補碼兩位乘可用布斯算法推導如下：[Pi+1]補

=2-1([Pi]補

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

=2-1([Pi+1]補

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

+(yi-1–yi)[X]補)+(yi–yi+1)[X]補)=2-2([Pi]補+(yi-1+yi–2yi+1)[X]補)開始置附加位y-1為0，乘積寄存器最高位前面添加一位附加符號位0。最終的乘積高位部分在乘積寄存器P中，低位部分在乘數(shù)寄存器Y中。因為字長總是8的倍數(shù)，所以補碼的位數(shù)n應該是偶數(shù)，因此，總循環(huán)次數(shù)為n/2。yi+1

yi

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

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

=1101，[Y]補

=0110，用補碼兩位乘法計算[X×Y]補。解：[–X]補=0011，用補碼二位乘法計算[X×Y]補的過程如下。

PnPYy-1

說明

0000001100

開始，設(shè)y-1=0，[P0]補

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

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

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

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

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

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

1001010 Dividend(被除數(shù))

-1000

10

101

1010

-1000

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

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

這樣，就將所有情況都統(tǒng)一為：一個2n位數(shù)除以一個n位數(shù)以下是64位數(shù)除以32位數(shù)的例子問題：第一次試商為1，說明什么？若是無符號整數(shù)運算，則說明將會得到n+1位的商，因而結(jié)果“溢出”。但若是兩個n位數(shù)相除，則肯定不會溢出，為什么？若是浮點數(shù)中尾數(shù)原碼小數(shù)運算，則說明尾數(shù)部分有“溢出”，可通過浮點數(shù)的“右規(guī)”消除“溢出”。所以，在浮點數(shù)運算器中，第一次得到的商“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驗證：7/2=3余1問題：這里Q中第一個“0”說明什么？不是真正的商，而是表示沒有“溢出”!對手算除法算法的觀察1/2bitsindivisor（除數(shù)寄存器）always0

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

（問題：為什么可這樣做？）因為余數(shù)寄存器的左移實際上使左半部的余數(shù)和右半部的商同時左移，所以循環(huán)里面只包含了兩步。兩個寄存器的結(jié)合以及循環(huán)內(nèi)次序的調(diào)換使得余數(shù)被多左移了一次。所以最后一步余數(shù)寄存器的左半邊的余數(shù)必須向右移一位。RemainderQuotientDivisor64-bitALUShiftRightShiftLeftWriteControl32bits64bits64bits完全模擬手工的除法算法因為結(jié)果肯定不“溢出”，故第1次商肯定為0，不用先做減法試商，即：將第一步換成先左移，可減少一次迭代無符號數(shù)除法算法的硬件實現(xiàn)除數(shù)寄存器Y：存放除數(shù)。余數(shù)寄存器R：置初始中間余數(shù)R0的高位部分為高32位被除數(shù)；結(jié)束時，存放的是余數(shù)。余數(shù)/商寄存器Q：開始時，置初始中間余數(shù)R0的低位部分為低32位被除數(shù)；結(jié)束時，存放的是32位商。因為寄存器Q中存放的并不是商的全部位數(shù)，而是部分為被除數(shù)或中間余數(shù)，部分為商，只有到最后一步才是商的全部位數(shù)。循環(huán)次數(shù)計數(shù)器Cn：存放循環(huán)次數(shù)。初值是32，每循環(huán)一次，Cn減1，當Cn=0時，除法運算結(jié)束。ALU：除法核心部件。在控制邏輯控制下，對于余數(shù)寄存器R和除數(shù)寄存器Y的內(nèi)容進行“加/減”運算，在“寫使能”控制下運算結(jié)果被送回余數(shù)寄存器R。R和Q同步“左移”，Q最高位移入R的最低位，Q空出的最低位上“商”，商的各位逐次左移到Q中。由控制邏輯根據(jù)ALU結(jié)果符號決定上商為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驗證：7/2=3余1Divisor Remainder0010 00000111從例子可看出：每次上商為0時，需做加法，以“恢復余數(shù)”。所以，稱為“恢復余數(shù)法”。也可在下一步運算時把當前多減的除數(shù)補回來。這種方法稱為“不恢復余數(shù)法”，又稱“加減交替法”。最后的余數(shù)需向右移一位。不恢復余數(shù)除法(加減交替法)根據(jù)恢復余數(shù)法(設(shè)B為除數(shù)，Ri為第i次中間余數(shù))，有：若Ri<0,則商上“０”，做加法恢復余數(shù)，即：Ri+1=2(Ri+2n|B|)-2n|B|=2Ri+2n|B|(由上式可知：“負，０，加”)若Ri>0,則商上“1”，不需恢復余數(shù)，即：Ri+1=2Ri-2n|B|(由上式可知：“正，１，減”)省去了恢復余數(shù)的過程注意：最后一次上商為“０”的話，需要“糾余”處理，即把試商時被減掉的除數(shù)加回去，恢復真正的余數(shù)。不恢復余數(shù)法也稱為加減交替法恢復余數(shù)法可進一步簡化為“加減交替法”帶符號數(shù)除法原碼除法商符和商值分開處理商的數(shù)值部分由無符號數(shù)除法求得商符由被除數(shù)和除數(shù)的符號確定：同號為０，異號為１余數(shù)的符號同被除數(shù)的符號補碼除法方法1：同原碼除法一樣，先轉(zhuǎn)換為正數(shù)，先用無符號數(shù)除法，然后修正商和余數(shù)。方法2：直接用補碼除法，符號和數(shù)值一起進行運算，商符直接在運算中產(chǎn)生。對于兩個n位補碼整數(shù)的除法運算，被除數(shù)需要進行符號擴展。若被除數(shù)為2n位，除數(shù)為n位，則被除數(shù)無需擴展。

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

1=1商的數(shù)值位采用恢復余數(shù)法。減法操作用補碼加法實現(xiàn)，是否夠減通過中間余數(shù)的符號來判斷，所以中間余數(shù)要加一位符號位。因此，需先計算出:[|X|]補=0.1011[|Y|]補=0.1101[–|Y|]補=1.0011因為是原碼定點小數(shù)，所以在被除數(shù)低位擴展0思考：若實現(xiàn)無符號數(shù)相除即：1011除以1101，則有何不同？結(jié)果是什么？在確認不會溢出時可省略原碼除法舉例已知[X]原=0.1011[Y]原=1.1101用不恢復余數(shù)法計算[X/Y]原解：[|X|]補=0.1011[|Y|]補=0.1101[–|Y|]補=1.0011

“加減交替法”的要點：

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