计算机组成原理：第4章 运算器设计与实现（加减法）2010

运算器设计与实现

定点数加/减法部分第四章

(1/3)

运算器是计算机进行算术运算和逻辑运算的主要部件，运算器的逻辑结构取决于机器的指令系统、数据表示方法和运算方法等。本章主要讨论数值数据在计算机中实现算术运算和逻辑运算的方法，以及运算部件的基本结构和工作原理。运算器

80486运算器简化框图运算器内部结构运算器部分内容提要一.定点数加/减法二.定点数乘/除法三.定点数逻辑运算四.浮点数的运算--

定点数加/减法运算方法及实现--定点数加/减法运算中的溢出问题--定点数乘法算法及实现--定点数除法算法及实现--逻辑运算及实现--位移运算及实现--浮点数运算及实现运算器部分内容提要一.定点数加/减法二.定点数乘/除法三.定点数逻辑运算四.浮点数的运算--

定点数加/减法运算方法及实现--定点数加/减法运算中的溢出问题--定点数乘法算法及实现--定点数除法算法及实现--逻辑运算及实现--位移运算及实现--浮点数运算及实现一.定点数加/减法定点数加/减法运算方法原码加减运算对原码表示的两个数进行加减运算时，符号位不参与运算，仅仅是两数的绝对值参与运算。计算机的实际操作是加还是减，不仅取决于指令的操作码，还取决于两个操作数的符号，例如：加法时可能要做减法（两数异号）；减法时又可能做加法（两数异号），所以原码加减运算的实现是比较复杂的。补码加减运算1.补码加法两个补码表示的数相加，符号位参加运算，且两数和的补码等于两数补码之和，即

[X+Y]补=[X]补+[Y]补2.补码减法根据补码加法公式可推出：

[X-Y]补=[X+(-Y)]补=[X]补+[-Y]补已知[Y]补求[-Y]补的方法是：将[Y]补连同符号位一起求反，末尾加“1”。

[-Y]补被称为[Y]补的机器负数，由[Y]补求[-Y]补的过程称为对[Y]补变补（求补），表示为：

[-Y]补=[[Y]补]变补

我们要注意将“某数的补码表示”与“变补”这两个概念区分开来。一个负数由原码表示转换成补码表示时，符号位是不变的，仅对数值位的各位变反，末尾加“1”。而变补则不论这个数的真值是正是负，一律连同符号位一起变反，末尾加“1”。

[Y]补表示的真值如果是正数，则变补后[-Y]补所表示真值变为负数，反之亦然。定点数加/减法运算方法

［+1］补=0001［+1］补=0001+［+３］补=0011+［-3］补=1101

［+４］补=0100［-2］补=1110

［-1］补=1111+［+2］补=0010

［+1］补=10001Addition/SubtractionofTwosComplement

Carry-outisignoredInadd/suboftwo’scomplementsignbitcanbehandledasmagnitudebit

1+3=4

1-3=-2

-1+2=11-bitALUDesign

32-bitALUDesignOverflowDetectionLogicHowtoperformSubtractionontheALUCarrylookaheadlogicMenuofthetopic定点数加/减法实现电路

1.ANDgateABOut000010100111ABOut000011101111OutABABOutABOut0000111011104.XORgate(half-adder)AAOut1001OutABOut=A×BOut=A＋BOut=AOut=A＋

B2.ORgate3.InverterBasicLogicalUnit（1）5.MutiplexerABdout01dout01ABIFd==0out=AElseout=BABdoutBasicLogicalUnit（2）D103S1out....12S0D0D2D3数据选择控制输入S1S0选中的数据输出out00011011D0D1D2D30

0

0

01

1

1

0

D1BasicLogicalUnit（3）4:1MutiplexerThe1-bitlogicalunitforANDandORPerformsANDandOR1）Operation=0，选择OR输出2）Operation=1，选择AND输出(0)0000(0)00(0)(0)001111100111(0)(0)(0)(1)(1)(1)(1)(carry)+......Additionfor1-bitunitTherearethreeinputs(twooperandsandonecarry-in)twooutputs(sumandcarry-out)For1-bitadder:outputinputTruthtableforinput/outputAdditionfor1-bitunitTurntruthtableintoalogicalequation:◆

CarryOut=(b&CarryIn)∣(a&CarryIn)∣(a&b)∣(a&b&CarryIn)Simplifytheequationto：CarryOut=(b&CarryIn)∣(a&CarryIn)∣(a&b)◆

Sum=(a&b&CarryIn)∣(a&b&CarryIn)∣Sum=aXORbXORCarryIn(a&b&CarryIn)∣(a&b&CarryIn)

Additionfor1-bitunitSimplifytheequationto：Additionfor1-bitunit1-bitfulladderabCarryIn●●●●CarryOutresultabCarryOutCarryInOperation210OperationresultCarryInCarryOutALUPerformsAND,ORandaddition（完成1位“与”、“或”、“加”运算）andoradd1-bitFullAdder

1-bitALU221）Operation=0，选择AND输出2）Operation=1，选择OR输出3）Operation=2，选择Add输出a0CarryInresult0Operationresult1CarryInALU0CarryOutCarryInCarryInCarryInCarryOutCarryOutCarryOutALU1ALU2ALU31b0result2result31a1a2a31b1b2b31……Addition(注意):作为加法器时第一个进位输入为0CarryIn[0]=0A32-bitALUconstructedfrom321-bitALUsusuallyinterestedincalculationmorethantwobitsthismotivatestheneedfortheCascadedMulti-bitALU21）Operation=0，选择32bitAND输出2）Operation=1，选择32bitOR输出3）Operation=2，选择32bitAdd输出b0b1b2…b31a0a1a2…a31CarryOut32-bitALU(32位算术逻辑单元)

［+1］补=0001［+1］补=0001+［+３］补=0011+［-3］补=1101

［+４］补=0100［-2］补=1110

［-1］补=1111+［+2］补=0010

［+1］补=10001Addition/SubtractionofTwosComplement

Carry-outisignoredInadd/suboftwo’scomplementsignbitcanbehandledasmagnitudebit

1+3=4

1-3=-2

-1+2=1?

溢出问题概述

溢出的检测方法Menuofthetopic定点数加/减法运算中的溢出问题

7+3=10but... -4-5=-9but...01110011+1010111001011+0111110731–6–4–57Overflow:Whenaddingoperandswithsamesigns,theresultisdifferentExamples:

溢出问题概述5+3=-8!-7-2=+7!0000000100100011100001010110010010011010101111001101011111101111+0+1+2+3+4+5+6+7-8-7-6-5-4-3-2-10000000100100011100001010110010010011010101111001101011111101111+0+1+2+3+4+5+6+7-8-7-6-5-4-3-2-1ReasonofOverflowtheresultistoolarge(ortoosmall)torepresentproperlyOverflowConditionsOverflow:theresultistoolarge(ortoosmall)torepresentproperlyExample:rangeof4-bitbinarynumber（signed）

[-8,+7]Whenaddingoperandswithdifferentsigns,overflowcannotoccur!Overflowoccurswhenadding:2positivenumbersandthesumisnegative2negativenumbersandthesumispositiveOnyourown:Proveyoucandetectoverflowby:CarryintoMSBandCarryoutofMSB

CarryintoMSBCarryoutofMSB=1OverflowwhencarryintosigndoesnotequalcarryoutMethod1

（最高进位和次高进位法）当向符号位的进位（由次高位产生）不等于符号位产生的进位（由符号位产生）则发生溢出

溢出的检测方法Overflowwhencarryintosigndoesnotequalcarryout01110011+1010111001011+011111010Examplesoverflow73-6+-4-57+overflow01010010+01110000Nooverflow527+11011011+10001111Nooverflow-3-5-8+1Carry-outisignoredCarryInCarryInCarryOutCarryOutALU31ALU30…result31result30CarryIn29CarryIn31CarryIn30a31a30b31b30OverflowXYXXORY000011101110

CarryintoMSB&CarryoutofMSBForaN-bitALU:Overflow=CarryIn[N-1]XORCarryOut[N-1]Method1

（最高进位和次高进位法）OverflowDetectionLogic(溢出检测逻辑)[x]双补

=

x1＞x≥0２２+x0＞x≥–1（mod4）[x]双补=

0，x2n

＞x≥02n+２

+x0＞x≥2n（mod2n+２）[A]补=０0.1010[A]补=１1.0001

[B]补=０0.1001

[A

+

B]补=

０

1.0011

[B]补=１1.0101

[A

+

B]补=

１

0.0110UsingDoublesignsTwosComplementinoverflowdetectionMethod2:双符号位法

溢出的检测方法00,×××××11,×××××10,×××××01,×××××whentwosignbitsoftheresultaresamethereisnooverflowsumisnegativesumispositivewhentwosignbitsoftheresultaredifferentthereisoverflow

NegativeoverflowPositiveoverflowMSBisthesignoftheresult

溢出的检测方法CarryInCarryInCarryOutCarryOutALU31ALU30…result31(符号位)result30(符号位)CarryIn29CarryIn31CarryIn30a31a30b31b30OverflowMethod2:双符号位法UsingDoublesignsTwosComplementinoverflowdetectionwhentwosignbitsoftheresultaredifferentthereisoverflow

whentwosignbitsoftheresultaresamethereisnooverflow

Overflow=1，溢出；

0，没有溢出注：最高两位是符号位OverflowDetectionLogic(溢出检测逻辑)A-B=A+(–B)=A+B+1formtwocomplementbyinvertandaddoneSoweonlyneedadditionandcomplementcircuits

Taketwoscomplimentofsubtrahendandaddtominuend-i.e.a-b=a+(-b)HowtoperformSubtractionontheALUweconstructedbefore?abCarryInCarryOutresultabCarryOutCarryIn＋Operation210OperationresultCarryInCarryOutALU01BinvertBinvertHowtoperformSubtractionontheALU

weconstructedbefore?WhenBinvert=1

inputsoffulladderareaandb

已有全加器加入输入为Ba0CarryIn=1result0Operationresult1CarryInALU0CarryOutCarryInCarryInCarryInCarryOutCarryOutCarryOutALU1ALU2ALU31b0result2result31a1a2a31b1b2b31……Binvert=1CarryIn=1Binvert=1Subtractionon32-bitALUForSubtractionA-B=A+(-B)=A+B+1a0CarryInresult0Operationresult1CarryInALU0CarryOutCarryInCarryInCarryInCarryOutCarryOutCarryOutALU1ALU2ALU31b0result2result31a1a2a31b1b2b31……CarryIn=0BinvertCarryIn=1Binvert=1Binvert=0Addition/Subtractionon32-bitALUForadditionForSubtraction

SoweonlyneedadditionandcomplementcircuitsA-B=A+(-B)=A+B+1a0CarryInresult0Operationresult1CarryInALU0CarryOutCarryInCarryInCarryInCarryOutCarryOutCarryOutALU1ALU2ALU31b0result2result31a1a2a31b1b2b31……lesslesslessless…SetoverflowBnegate=1Bnegate=0ForadditionForSubtractionBnegateCombiningtheBinvertandCarryIntoBnegatea0CarryInresult0Operationresult1CarryInALU0CarryOutCarryInCarryInCarryInCarryOutCarryOutCarryOutALU1ALU2ALU31b0result2result31a1a2a31b1b2b31……lesslesslessless…SetoverflowBnegateAddsaZerodetector…ZeroBinvert=1(A-B)Zero=1A=BZero=0A≠BControlsignsandcorrespondingoperationThevaluesofthethreeALUcontrollinesBnegate(1-bit)Andoperation(2-bit)andcorrespondingoperationsUniversalsymbolforacompleteALUThesymbolisalsotorepresentanadder,soitisnormallylabeledeitherwithALUorAdder

设计一个1位ALU,完成一位加法、AND、OR和NOT操作。输入为A、B，输出为z。当加法运算时，有进位输出CarryOut;当AND、OR和NOT操作时，CarryOut为O。在下图上通过连线完成上述设计（注：不能添加任何其他部件）。例:00011011全加器数据输入F0F1abCarryInCarryOut输出F0F1

功能00

ADD（A，B）01

AND（A，B）10

OR（A，B）11

NOT（A）CarryOut输出CarryIn数据输入2:4译码器Z例(cont)00011011全加器数据输入F0F1abCarryInCarryOut输出F0F1

功能00

ADD（A，B）解:

ADD（A，B）00011011全加器数据输入F0F1abCarryInCarryOut输出F0F1

功能01

AND（A，B）

AND（A，B）00011011全加器数据输入F0F1abCarryInCarryOut输出F0F1

功能10

OR（A，B）OR（A，B）00011011全加器数据输入F0F1abCarryInCarryOut输出F0F1

功能11

NOT（A）NOT（A）00011011全加器数据输入F0F1abCarryInCarryOut输出功能实现逻辑图RippleCarryCriticaldelay:thepropagationofcarryfromlowtohighorderstagesCO

A14

B14

A1B1A0B0S15S14S1S0C-11-bitFullAdderB15A15

1-bitFullAdder1-bitFullAdder1-bitFullAdder….C15C1C1416stageadderfinalsumAndcarryCarrylookaheadlogictwogatedelaystocomputeCOlatearrivingsignal2delaystocomputesumbutlastcarrynotreadyuntil30delayslaterT0:InputstotheadderarevalidT2:Stage0carryout(C0)T4:Stage1carryout(C1)T30:Stage14carryout(C14)T32:Stage15carryout(C15)RippleCarry…AfastaddercircuitmustspeedupthegenerationofthecarrysignalsCriticaldelay:thepropagationofcarryfromlowtohighorderstagesCi=Ai●Bi

＋(AiBi)Ci-1

Ci

=Gi＋Pi●Ci-1Gi=Ai●BiPi=AiBiCi-1carryinforstagei(fromstagei-1)Cicarryoutforstagei(tostagei+1)AnalysisofCarryThelogicexpressionsforsi(sum)ansci(carry-out)ofstageiare:Wecanwrite:

Where:CarryGenerateforstageimustgeneratecarrywhenA=B=1CarryPropagateforstageiCarryoutwillequalcarryinhereForstagei,outputcarryCiindependentoninputcarryCi–1Wecanre-expressedcarryintermsofgenerate/propagate:Onlydependentonstage0carryC–1

C0=G0＋P0C-1

C1

=G1＋P1C0

=G1＋P1(G0＋P0C-1)=G1＋P1G0＋P1P0C-1

C2

=G2＋P2C1=G2＋P2G1＋P2P1G0＋P2P1P0C-1

C3=G3＋P3C2=G3＋P3G2＋P3P2G1＋P3P2P1G0＋P3P2P1P0

C-1…

C15

=G15＋P15C14=G15＋P15G14＋P15P14G13＋P15P14P13G12＋P15P14P13P12G11

＋…＋P15P14P13P12P11P10P9P8P8P7P6P5P4P3P2P1P0C-1AnalysisofCarryPlumbingasCarryLookaheadAnalogy

C0=G0＋P0C-1

C1

=G1＋P1C0

=G1＋P1(G0＋P0C-1)=G1＋P1G0＋P1P0C-1

C2

=G2＋P2C1=G2＋P2G1＋P2P1G0＋P2P1P0C-1

C3=G3＋P3C2=G3＋P3G2＋P3P2G1＋P3P2P1G0＋P3P2P1P0

C-14bitadderswithinternalcarrylookaheadEachofthecarryequationscanbeimplementedinatwo-levellogicnetworkVariablesaretheadderinputsandcarryintostage0!Re-expressthecarrylogicasfollows:CarryLookaheadImplementationAdderwithPropagateandGenerateOutputsIncreasinglycomplexlogic

4bitadderswithripplecarry

4bitadderswithcarrylookahead×××

4bitadderswithcarrylookahead4bitadderswithinternalcarrylookaheadConstructingfastadder-1Method1Using4bitadderswithinternalcarrylookaheadasagroup,CascadedMulti-groupAdderbyripplecarrybetweengroups

16-bitadderbuiltfrom4-bitcarrylookaheadadderbymethod1sumscomputedmuchfasterTimingdiagramofCascadedMulti-groupAdderbyripplecarrybetweengroups

Constructingfastadder-1Constructingfastadder-2Method2Using4bitadderswithinternalcarrylookaheadasagroup,CombiningMulti-groupAdderbyusingsecondlevelcarrylookaheadunit,extendscarrylookaheadforgroups4bitadderswithinternalcarrylookaheadsecondlevelcarrylookaheadunit,extendslookaheadto16bitsGroupP=P3P2P1P0GroupG=G3+P3G2+P3P2G1+P3P2P1G0AnalysisofCarryforgroupsCarryofeachgroup:C3C7

C11

C15Thelogicexpressionfor

C3

C3=G3＋P3G2＋P3P2G1＋P3P2P1G0＋P3P2P1P0

C-1=G3*

＋P3*

C-1G3*

=G3＋P3G2＋P3P2G1＋P3P2P1G0P3*

=P3P2P1P0where：gruop1

C3C7C11C15C-1A0-3A7-4A11-8A15-12B15-12B11-8S11-8B7-4S7-4B0-3S0-3S15-12AnalysisofCarryforgroupsCarryGenerateforgroup1CarryPropagateforgroup1gruop2

gruop4

gruop4

Dividing16bitaddersinto4groups,eachgroup4bitsWithinternalcarrylookahead2ndlevelCarry,PropagateasPlumbing

C3=G3*

＋P3*

C-1

C7

=G7*

＋P7*

C3

=G7*

＋P7*

G3*

＋P7*P3*

C-1

C11

=G11*

＋P11*

C7*=G11*

＋P11*

G7*

＋P11*

P7*

G3*

＋P11*

P7*

P3*

C-1

C15=G15*

＋P15*

C11

=G15*

＋P15*

G11*

＋P15*

P11*

G7*

＋P15*

P11*

P7*

G3*

＋P15*

P11*

P7*

P3*

C-1Carryofeachgroup

C3，C7

，C11

，C15

：AnalysisofCarryforgroupsG7*

=G7＋P7G6＋P7P6G5＋P7P6P5G4

P7*

=P7P6P5P4G11*

=G11＋P11G10＋P11P10G9＋P11P10P9G8P11*

=P11P10P9P8P15*

=P15P14P13P