計(jì)算機(jī)組成原理教學(xué)課件：3-Arithmetic for Computers

Computer

Organization&Design

—TheHardware/SoftwareInterface2023/1/111ArithmeticforComputersArithmeticforComputersOperationsonintegersAdditionandsubtractionMultiplicationanddivisionWhataboutfractionsandrealnumbers?RepresentationandoperationsHowareoverflowscenarioshandled?e.g.AnoperationcreatesanumberbiggerthancanberepresentedHowdoeshardwarereallymultiplyanddividenumbers?MIPSArithmeticLogicUnit(ALU)MustsupporttheArithmetic/LogicoperationsoftheISAadd,addi,addiu,addusub,subumult,multu,div,divusqrtand,andi,nor,or,ori,xor,xoribeq,bne,slt,slti,sltiu,sltu323232m(operation)resultABALU4zeroovf11Withspecialhandlingforsignextend–addi,addiu,slti,sltiuzeroextend–andi,ori,xorioverflowdetection–add,addi,subComputerwordsarecomposedofbits;thuswordscanberepresentedasbinarynumbers.Whataboutfractionsandotherrealnumbers?WhathappenifanoperationscreatesanumberbiggerthancanberepresentedAndunderlyingthesequestionsisamystery:Howdoeshardwarereallymultiplyordividenumbers?3.1Introduction2023/1/114DifferentRepresentationsofNaturalNumbers XXVII Romannumerals(notpositional) 27 Radix-10ordecimalnumber(positional) 110112 Radix-2orbinarynumber(alsopositional)Fixed-radixpositionalrepresentationwithkdigitsNumberNinradixr=(dk–1dk–2...d1d0)r Value=dk–1×rk–1+dk–2×rk–2+…+d1×r+d0Examples: (11011)2=1×24+1×23+0×22+1×2+1=27 (2103)4=2×43+1×42+0×4+3=147PositionalNumberSystemsBinaryNumbersEachbinarydigit(calledbit)iseither1or0Bitshavenoinherentmeaning,canrepresentUnsignedandsignedintegersCharactersFloating-pointnumbersImages,sound,etc.BitNumberingLeastsignificantbit(LSB)isrightmost(bit0)Mostsignificantbit(MSB)isleftmost(bit7inan8-bitnumber)10011101272625242322212001234567MostSignificantBitLeastSignificantBitConvertingBinarytoDecimalEachbitrepresentsapowerof2Everybinarynumberisasumofpowersof2DecimalValue=(dn-1

2n-1)+...+(d1

21)+(d0

20)Binary(10011101)2=27+24+23+22+1=157Somecommonpowersof2ConvertUnsignedDecimaltoBinaryRepeatedlydividethedecimalintegerby2Eachremainderisabinarydigitinthetranslatedvalue37=(100101)2leastsignificantbitmostsignificantbitstopwhenquotientiszeroHexadecimalIntegers16HexadecimalDigits:0–9,A–FMoreconvenienttousethanbinarynumbersBinary,Decimal,andHexadecimalEquivalentsConvertingBinarytoHexadecimalEachhexadecimaldigitcorrespondsto4binarybitsExample: Convertthe32-bitbinarynumbertohexadecimal

11101011000101101010011110010100Solution:0100410019011171010A01106000111011B1110EMultiplyeachdigitbyitscorrespondingpowerof16Value=(dn-1

16n-1)+(dn-2

16n-2)+...+(d1

16)+d0Examples: (1234)16=(1163)+(2162)+(316)+4= DecimalValue4660 (3BA4)16=(3163)+(11162)+(1016)+4= DecimalValue15268ConvertingHexadecimaltoDecimalConvertingDecimaltoHexadecimalDecimal422=1A6hexadecimalstopwhenquotientiszeroleastsignificantdigitmostsignificantdigitRepeatedlydividethedecimalintegerby16EachremainderisahexdigitinthetranslatedvalueIntegerStorageSizesWhatisthelargest20-bitunsignedinteger?Answer:220–1=1,048,575StorageTypeUnsignedRangePowersof2Byte0to2550to(28–1)HalfWord0to65,5350to(216–1)Word0to4,294,967,2950to(232–1)DoubleWord0to18,446,744,073,709,551,6150to(264–1)StorageSizesBinaryAdditionStartwiththeleastsignificantbit(rightmostbit)AddeachpairofbitsIncludethecarryintheaddition,ifpresent0001110100110110+(54)(29)(83)1carry01234bitposition:56711101010011HexadecimalAdditionStartwiththeleastsignificanthexadecimaldigitsLetSum=summationoftwohexdigitsIfSumisgreaterthanorequalto16Sum=Sum–16andCarry=1Example:AFCDB01111C37286A9395E84B+A+B=10+11=21Since21≥16Sum=21–16=5Carry=151carry:SignedIntegersSeveralwaystorepresentasignednumberSign-MagnitudeBiased1'scomplement2'scomplementDividetherangeofvaluesinto2equalpartsFirstpartcorrespondstothepositivenumbers(≥0)Secondpartcorrespondtothenegativenumbers(<0)Focuswillbeonthe2'scomplementrepresentationHasmanyadvantagesoverotherrepresentationsUsedwidelyinprocessorstorepresentsignedintegersTwo'sComplementRepresentation8-bitBinaryvalueUnsignedvalueSignedvalue0000000000000000011+1000000102+2.........01111110126+12601111111127+12710000000128-12810000001129-127.........11111110254-211111111255-1PositivenumbersSignedvalue=UnsignedvalueNegativenumbersSignedvalue=Unsignedvalue–2nn=numberofbitsNegativeweightforMSBAnotherwaytoobtainthesignedvalueistoassignanegativeweighttomost-significantbit=-128+32+16+4=-76FormingtheTwo'sComplementSumofanintegerandits2'scomplementmustbezero:00100100+11011100=00000000(8-bitsum)IgnoreCarryAnotherwaytoobtainthe2'scomplement:Startattheleastsignificant1Leaveallthe0stoitsrightunchangedComplementallthebitstoitsleftstartingvalue00100100=+36step1:reversethebits(1'scomplement)11011011step2:add1tothevaluefromstep1+1sum=2'scomplementrepresentation11011100=-36BinaryValue=00100

1

002'sComplement=11011

1

00leastsignificant1SignBitHighestbitindicatesthesign1=negative0=positiveForHexadecimalNumbers,checkmostsignificantdigitIfhighestdigitis>7,thenvalueisnegativeExamples:8AandC5arenegativebytesB1C42A00isanegativeword(32-bitsignedinteger)SignExtensionStep1:Movethenumberintothelower-significantbitsStep2:FillalltheremaininghigherbitswiththesignbitThiswillensurethatbothmagnitudeandsignarecorrectExamplesSign-Extend10110011to16bitsSign-Extend01100010to16bitsInfinite0scanbeaddedtotheleftofapositivenumberInfinite1scanbeaddedtotheleftofanegativenumber10110011=-771111111110110011=-7701100010=+980000000001100010=+98Two'sComplementofaHexadecimalToformthetwo'scomplementofahexadecimalSubtracteachhexadecimaldigitfrom15Add1Examples:2'scomplementof6A3D=95C2+1=95C32'scomplementof92F15AC0=6D0EA53F+1=6D0EA5402'scomplementofFFFFFFFF=00000000+1=00000001NoneedtoconverthexadecimaltobinaryBinarySubtractionWhensubtractingA–B,convertBtoits2'scomplementAddAto(–B) 01001101 01001101 00111010 11000110(2'scomplement) 00010011 00010011(sameresult)Finalcarryisignored,becauseNegativenumberissign-extendedwith1'sYoucanimagineinfinite1'stotheleftofanegativenumberAddingthecarrytotheextended1'sproducesextendedzeros–+borrow:carry:1111111HexadecimalSubtractionWhenaborrowisrequiredfromthedigittotheleft,then Add16(decimal)tothecurrentdigit'svalueLastCarryisignoredBorrow:-576CF41B742AE938E2421BD216+5=21111EBD4121+576CF41B9BD516C7(2'scomplement)(sameresult)Carry:211121RangesofSignedIntegersForn-bitsignedintegers:Rangeis-2n–1to(2n–1–1)Positiverange:0to2n–1–1Negativerange:-2n–1to-1Practice:Whatistherangeofsignedvaluesthatmaybestoredin20bits?StorageTypeUnsignedRangePowersof2Byte–128to+127–27to(27–1)HalfWord–32,768to+32,767–215to(215–1)Word–2,147,483,648to+2,147,483,647–231to(231–1)DoubleWord–9,223,372,036,854,775,808to+9,223,372,036,854,775,807–263to(263–1)3.2Addition&subtractionAddingbitbybit,carries->nextdigitSubtractionDirectlyAdditionof2'scomplement2023/1/1125OverflowThesumoftwonumberscanexceedanyrepresentationThedifferenceoftwonumberscanexceedanyrepresentation2'scomplement: Numberschange signandsize2023/1/1126OverflowGeneraloverflowconditions2023/1/1127CarryandOverflowExamplesWecanhavecarrywithoutoverflowandvice-versaFourcasesarepossible(Examplesare8-bitnumbers)CarryandOverflowCarryisimportantwhen…AddingorsubtractingunsignedintegersIndicatesthattheunsignedsumisoutofrangeEither<0or>maximumunsignedn-bitvalueOverflowisimportantwhen…AddingorsubtractingsignedintegersIndicatesthatthesignedsumisoutofrangeOverflowoccurswhenAddingtwopositivenumbersandthesumisnegativeAddingtwonegativenumbersandthesumispositiveCanhappenbecauseofthefixednumberofsumbitsUnsignedIntegers:n-bitrepresentationSignedIntegers:n-bit2'scomplementrepresentationRange,Carry,Borrow,andOverflowmax=2n–1min=0Carry=1AdditionNumbers>maxBorrow=1SubtractionNumbers<minPositiveOverflowNumbers>maxNegativeOverflowNumbers<minmax=2n-1–1FiniteSetofSignedIntegers0min=-2n-1FiniteSetofUnsignedIntegersOverflowReactiononoverflowIgnore?ReactionoftheOSSignallingtoapplication(Ada,Fortran,...)HardwaredetectionintheALUGenerationofanexception(interrupt)Savetheinstructionaddress(notPC)inspecialregisterEPCJumptospecificroutineinOSCorrect&returntoprogramReturntoprogramwitherrorcodeAbortprogram2023/1/1131OverflowOverflowsinsignedarithmeticinstructionscauseexceptions:addaddimmediatesubtractOverflowsinunsignedarithmeticinstructionsdon’tcauseexceptions:addunsignedaddimmediateunsignedSubtractunsignedHandlewithcare!2023/1/1132ConstructinganALUStepbystep:buildasinglebitALUandexpandittothedesiredwidthFirstfunction:logicANDandOR2023/1/1133AhalfadderSum=ab+abCarry=ab2023/1/1134AfulladderAcceptsacarryinSum=AxorBxorCarryInCarryOut=BCarryIn+ACarryIn+ABInputsOutputsComments(two)ABCarryInCarryOutSum000000+0+0=00001010+0+1=01010010+1+0=01011100+1+1=10100011+0+0=01101101+0+1=10110101+1+0=10111111+1+1=112023/1/1135FulladderFulladderin2-leveldesign2023/1/11361bitALUALUANDORADDCascadeElement2023/1/1137Basic32bitALUInputsparallelCarryiscascadedRipplecarryadderSlow,butsimple1stCarryIn=02023/1/1138Extended1bitALUSubtraction a-bInvertingb1stCarryIn=12023/1/1139Extended1bitALUFunctionsANDORAddSubtractMissing:comparisonSltrd,rs,rtIfrs<rt,rd=1,elserd=0Allbits=0excepttheleastsignificantSubtraction(rs-rt),iftheresultisnegative->rs<rtUseofsignbitasindicator2023/1/1140Extended1bitALUALUbitwithinputforLessdata2023/1/1141MostsignificantbitSetforcomparisonOverflowdetect2023/1/1142CompleteALUInputABControllinesBinvertOperationCarryinOutputResultOverflow2023/1/1143CompleteALUAddaZerodetector2023/1/1144ALUsymbol&controlFunctiontableSymboloftheALUALUControlLinesFunction000And001Or010Add110Sub111Setonlessthan2023/1/1145SpeedconsiderationsPreviouslyused:ripplecarryadderDelayforthesum:twounitsDelayforthecarry:two-threeunits2023/1/1146SpeedconsiderationsDelayofoneadder2timeunitsTotaldelayfor stages:

2nunitdelaysNotappropriatefor highspeedapplication2023/1/1147FastaddersAllfunctionscanberepresentedin2-levellogic.But:ThenumberofinputsofthegateswoulddrasticallyriseTarget: Optimumbetweenspeedandsize2023/1/1148FastaddersCarrylook-aheadadderCalculatingthecarriesbeforethesumisreadyCarryskipadderAcceleratingthecarrycalculationbyskippingsomeblocksCarryselectadderCalculatetworesultsandusethecorrectone...2023/1/1149Carrylookaheadadder(CLA)SeparationofaddoperationcarrycalculationFactorisationCi+1=(bi*ci)+(ai*ci)+(ai*bi) =(ai*bi)+(ai+bi)*ciGenerategi=ai*biPropagatepi=ai+bi2023/1/1150CarrylookaheadadderCi+1=gi+pi*ciCarrygenerate:gi=ai*biIfaandbare'1'-> wealwayshaveacarryoutindependentofciCarrypropagate:pi=ai+biIfonlyoneofaandbis'1'-> thecarryoutdependsonthecarryinpipropagatesthecarry2023/1/1151Fourbitcarrylookaheadadderc1=g0+(p0*c0)c2=g1+p1*c1=g1+(p1*g0)+(p1*p0*c0)c3=g2+p2*c2=g2+(p2*g1)+(p2*p1*g0)+(p2*p1*p0*c0)c4=g3+p3*c3=g3+(p3*g2)+(p3*p2*g1) +(p3*p2*p1*g0)+(p3*p2*p1*p0*c0)COMMENT: Thiskindofadderwillbefasterthantheripplecarryadder,andsmallerthantheadderwiththetow-levellogic.PROBLEM: Ifthenumberoftheadderbitsisverylarge,thiskindofadderwillbetoolarge.Sowemustseekmoreefficientways.2023/1/1152FourbitcarrylookaheadadderLet’sconsidera16-bitadder.Divide16bitsinto4groups.Eachgrouphas4bits.Asweknow: c4=g3+p3*g2+p3*p2*g1+p3*p2*p1*g0+p3*p2*p1*p0*c0So,wecangetthefollowing:c8=g7+p7*g6+p7*p6*g5+p7*p6*p5*g4+p7*p6*5*p4*c4c12=g11+p11*g10+p11*p10*g9+p11*p10*p9*g8+p11*p10*p9*p8*c8c16=g15+p15*g14+p15*p14*g13+p15*p14*p13*g12+p15*p14*p13*p12*c12Assume: G0=g3+p3*g2+p3*p2*g1+p3*p2*p1*g0

G1=g7+p7*g6+p7*p6*g5+p7*p6*p5*g4

G2=g11+p11*g10+p11*p10*g9+p11*p10*p9*g8

G3=g15+p15*g14+p15*p14*g13+p15*p14*p13*g12

P0=p3*p2*p1*p0 P1=p7*p6*p5*p4 P2=p11*p10*p9*p8 P3=p15*p14*p13*p122023/1/1153FourbitcarrylookaheadadderThenweget: c4=G0+P0*c0;c8=G1+P1*c4 c12=G2+P2*c8;c16=G3+P3*c12Assume:C1=c4,C2=c8,C3=c12,C4=c16Then: C1=G0+P0*c0;C2=G1+P1*C1 C3=G2+P2*C2;C4=G3+P3*C3And,wecanfurtherget:C1=G0+P0*c0;C2=G1+P1*C1=G1+P1*G0+P1*P0*c0C3=G2+P2*C2=G2+P2*G1+P2*P1*G0+P2*P1*P0*c0C4=G3+P3*C3=G3+P3*G2+P3*P2*G1+P3*P2*P1*G0+P3*P2*P1*P0*c02023/1/1154Four4-bitALUsusingcarrylookaheadtoforma16-bitadder.2023/1/1155HybridCLA+RipplecarryRealisation:

RipplecarryaddersandCarrylookaheadlogic2023/1/11563.3MultiplicationBinarymultiplication Multiplicand*Multiplier 1000*1001 1000

1001 1000 0000 0000 ___1000_____Product1001000LookatcurrentbitpositionIfmultiplieris1thenaddmultiplicandElseadd0shiftmultiplicandleftby1bit2023/1/1157MultiplicationStartwithlong-multiplicationapproach1000×100110000000000010001001000LengthofproductisthesumofoperandlengthsmultiplicandmultiplierproductMultiplierSequentialVersionRequires32iterationsAdditionShiftComparisonAlmost100cyclesVerybig,Tooslow!2023/1/1159MultiplyexampleusingalgorithminFigure3.5.2023/1/1160MultiplierV2Realadditionisperformedonlywith32bitsLeastsignificantbitsoftheproductdon'tchangeNewidea:Don’tshiftthemultiplicandInstead,shiftthe

productShiftthemultiplierALUreducedto32bits!2023/1/1161MultiplierV2--LogicDiagramDiagramoftheV2multiplierOnlylefthalfofproduct

registerischanged2023/1/1162MultiplierV2----AlgorithmicruleAdditionperformed onlyonlefthalfof productregisterShiftofproductregister2023/1/1163Revised4-bitexamplewithV2Multiplicandxmultiplier:0001x0111

Multiplicand:0001Multiplier:×011100000000#Initialvaluefortheproduct100010000#Afteradding0001,Multiplier=1000010000#Aftershiftingrighttheproductonebit0001200011000#Afteradding0001,Multiplier=1000011000#Aftershiftingrighttheproductonebit0001#Afteradding0001,Multiplier=1300011100000011100#Aftershiftingrighttheproductonebit0000400001110#Afteradding0001,Multiplier=0000001110#AftershiftingrighttheproductonebitShiftout2023/1/1164MultiplierV3FurtheroptimizationAttheinitialstatetheproductregistercontainsonly'0'Thelower32bitsaresimplyshiftedoutIdea: usetheselower32bitsforthemultiplier00010000000110000000111000000001110000000001110000multiplier2023/1/1165MultiplierV3LogicDiagram2023/1/1166MultiplierV3--AlgorithmicruleSetproductregisterto'0'Loadlowerbitsofproduct registerwithmultiplierTestleast significantbit

ofproduct register2023/1/1167ExamplewithV3Multiplicandxmultiplier:0001x0111Multiplicand:0001Multiplier:×011100000111#Initialvaluefortheproduct100010111#Afteradding0001,Multiplier=1000010111#Aftershiftingrighttheproductonebit0001200011011#Afteradding0001,Multiplier=1000011011#Aftershiftingrighttheproductonebit0001#Afteradding0001,Multiplier=1300011101000011101#Aftershiftingrighttheproductonebit0000400001110#Afteradding0001,Multiplier=0000001110#AftershiftingrighttheproductonebitShiftout2023/1/1168SignedmultiplicationBasicapproach:StorethesignsoftheoperandsConvertsignednumberstounsignednumbers (mostsignificantbit(MSB)=0)PerformmultiplicationIfsignbitsofoperandsareequal signbit=0,else signbit=12023/1/1169SignedMultiplicationSofar,wehavedealtwithunsignedintegermultiplicationFirstAttempt:ConvertmultiplierandmultiplicandintopositivenumbersIfnegativethenobtainthe2'scomplementandrememberthesignPerformunsignedmultiplicationComputethesignoftheproductIfproductsign<0thenobtainthe2'scomplementoftheproductBetterVersion:UsetheunsignedmultiplicationhardwareWhenshiftingright,extendthesignoftheproductIfmultiplierisnegative,thelaststepshouldbeasubtractSignedMultiplication(Pencil&Paper)Case1:PositiveMultiplier

Multiplicand

11002=-4

Multiplier×01012=+5

11111100

111100

Product 111011002=-20Case2:NegativeMultiplier

Multiplicand

11002=-4

Multiplier

×11012=-3

11111100

111100

00100(2'scomplementof1100)

Product 000011002=+12Sign-extensionSign-extensionALUproduces32-bitresult+SignbitCheckforoverflowNooverflow

Extendsign-bitofresultOverflowInvertextendedsignbitSequentialSignedMultiplier=0StartLO[0]?First31iterations:HI=HI+MultiplicandLastiteration:HI=HI–Multiplicand32ndRepetition?Done=1NoYesHI=0,LO=MultiplierShiftRight(Sign,HI,LO)1bit32-bitALUControl64bits32bitswriteadd,subLO[0]Multiplicandshiftright32bitsHILO32bitssignSignedMultiplicationExampleConsider:11002(-4)×11012(-3),Product=000011012

Checkforoverflow:NooverflowExtendsignbitLastiteration:add2'scomplementofMultiplicand1100Shift(Sign,HI,LO)right1bit1101100

1LO[0]=0=>DoNothing1100Shift(Sign,HI,LO)right1bit111100111100Shift(Sign,HI,LO)right1bit11100110Shift(Sign,HI,LO)right1bit000011002110000001101Initialize(HI=0,LO=Multiplier)0134MultiplicandProduct=HI,LOSignIteration11100

1101LO[0]=1=>ADD+11011

0

011LO[0]=1=>ADD+010000001

1001LO[0]=1=>SUB(ADD2'scompl)+補(bǔ)充Improvedmethod:

Booth'sAlgorithm Assumption:additionandsubtractionareavailable2023/1/1174Booth'sAlgorithmIdea:Ifyouhaveasequenceof'1'ssubtractatfirst'1'inmultipliershiftforthesequenceof'1'saddwherepriorstephadlast'1‘Result:PossiblylessadditionsandmoreshiftsFaster,ifshiftsarefasterthanadditions2023/1/1175ExampleforBooth'sAlgorithmLogicrequiredidentifyingtherun2023/1/1176Booth'sAlgorithmruleAnalysisoftwoconsecutivebitsAction10 subtractmultiplicandfromleft11 noarithmeticoperation01 addmultiplicandtolefthalf00 noarithmeticoperationBit-1='0'Arithmeticshiftright:keepstheleftmostbitconstantnochangeofsignbit!2023/1/1177Examplewithnegativenumbers2*-3=-60010*1101=11111010iterationstepMultiplicandproduct0InitialValues001000001101011.c:10→Prod=Prod-Mcand00101110110102:shiftrightProduct001011110110121.b:01→Prod=Prod+Mcand00100001011012:shiftrightProduct001000001011031.c:10→Prod=Prod-Mcand00101110101102:shiftrightProduct001011110101141.d:11→nooperation00101111010112:shiftrightProduct00101111101012023/1/1178UsingMultipleAdders32-bitadderforeachbitofthemultiplier31addersareneededfora32-bitmultiplierANDmultiplicandwitheachbitofmultiplierProduct=accumulatedshiftedsumEachadderproducesa33-bitoutputMostsignificantbitisacarrybitLeastsignificantbitisaproductbitUpper32bitsgotonextadderArraymultipliercanbeoptimizedCarrysaveaddersreducedelays32-bitAB132bitsAB032-bitAB232bits32bits133bits32bits133bits32-bitAB332bits32bits133bits32-bitAB3132bits32bits1bit33bitsP1P2P3P31P63..32..32bits...P01FasterMultiplication2023/1/1180WallaceTreeMultiplier-1of2SupposewewanttomultiplytwonumbersAandBExampleon4-bitnumbers:A=a3a2a1a0andB=b3b2b1b0Step1:AND(multiply)eachbitofAwitheachbitofBRequiresn2ANDgatesandproducesn2productbitsPositionofaibj=(i+j).Forexample,Positionofa2b3=2+3=5a0b0a1b0a2b0a3b0a0b1a1b1a2b1a3b1a0b2a1b2a2b2a3b2a0b3a1b3a2b3a3b3A×BWallaceTreeMultiplier–2of2Step2:UsecarrysaveadderstoaddthepartialproductsReducethepartialproductstojusttwonumbersStep3:Addlasttwonumbersusingacarry-propagateadderP0+a2b0a1b1+++a3b0a2b1a0b0+a1b0a0b1++++++a3b1a2b2+a3b2a2b3a3b3a1b3a0b3a1b2a0b2P1P2P3P4P5P6P7CarrySaveAdderCarryPropagateAdderCarrySaveAddersUsedwhenaddingmultiplenumbers(asinmultipliers)Allthebitsofacarry-saveadderworkinparallelThecarrydoesnotpropagateasinacarry-propagateadderThisiswhyacarry-saveisfasterthanacarry-propagateadderAcarry-saveadderhas3inputsandproducestwooutputsItadds3numbersandproducespartialsumandcarrybitsCarry-PropagateAdder+a0b0s0+a1b1s1+a31b31s31...coutcinCarry-SaveAdder...+a31b31s'31c'31c31+a1b1s'1c'1c1+a0b0s'0c'0c0MIPSMultiplicationTwo32-bitregistersforproductHI:most-significant32bitsLO:least-significant32-bitsInstructionsmultrs,rt/multurs,rt64-bitproductinHI/LOmfhird/mflordMovefromHI/LOtordCantestHIvaluetoseeifproductoverflows32bitsmulrd,rs,rtLeast-significant32bitsofproduct–>rdCheckfor0divisorLongdivisionapproachIfdivisor≤dividendbits1bitinquotient,subtractOtherwise0bitinquotient,bringdownnextdividendbitRestoringdivisionDothesubtract,andifremaindergoes<0,adddivisorbackSigneddivisionDivideusingabsolutevaluesAdjustsignofquotientandremainderasrequired100110001001010-1000101011010-100010n-bitoperandsyieldn-bit

quotientandremainderquotientdividendremainderdivisorDivisionV1--LogicDiagramAtfirst,thedivisorisinthelefthalfofthedivisorregister,

thedividendisintherighthalfoftheremainderregister.Shiftrightthedivisorregistereachstep2023/1/1186AlgorithmV1Eachstep:SubtractdivisorDependingonResultLeaveorRestoreDependingonResultWrite'1'orWrite'0'2023/1/1187Example7/2forDivisionV12023/1/1188DivisionV2ReductionofDivisorandALUwidthbyhalfShiftingoftheremainderSaving1iteration2023/1/1189DivisionV3Remainderregisterkeepsquotient

Noquotientregisterrequired2023/1/1190AlgorithmV3Muchthesamethan thelastoneExceptchangeof register usage2023/1/1191Example7/2forDivisionV3Wellknownnumbers:00000111/0010iterationstepDivisorRemainder0InitialValues001000000111ShiftRemleft100100000111011.Rem=Rem-Div0010111011102b:Rem<0→+Div,sllR,R0=000100001110021.Rem=Rem-Div0010111101102b:Rem<0→+Div,sllR,R0=000100011100031.Rem=Rem-Div0010000110002a:Rem>0→sllR,R0=100100011000141.Rem=Rem-Div0010000100112a:Rem>0→sllR,R0=1001000100011ShiftlefthalfofRemright12023/1/1192SigneddivisionKeepthesignsinmindforDividendandRemainder(+7)÷(+2)=+3 Remainder=+1 7=3×2+(+1)=6+1(-7)÷(+2)=-3 Remainder=-1 -7=-3×2+(-1)=-6-1(+7)÷(-2)=-3 Remainder=+1(-7)÷(-2)=+3 Remainder=-12023/1/1193Thefollowingequationmustalwayshold:

Dividend=Quotient×Divisor+RemainderMIPSDivisionUseHI/LOregistersforresultHI:32-bitremainderLO:32-bitquotientInstructionsdivrs,rt/divurs,rtUsemfhi,mflotoaccessresultNooverflowordivide-by-0checkingSoftwaremustperformchecksifrequiredFasterDivisionCan’tuseparallelhardwareasinmultiplierSubtractionisconditionalonsignofremainderFasterdividers(e.g.SRTdivision)generatemultiplequotientbitsperstepGuessesquotientbitsusingatablelookupbasedonupperbitsofdividend,remainderSubsequentstepscorrectwrongguessesStillrequiremultiplestepsOtherfasterdividersexistnonrestoringdividers,nonperformingdividers,…3.5FloatingpointnumbersReasoningLargernumberrangethanintegerrageFractionsNumberslikee(2.71828)andπ(3.14159265....)RepresentationSignSignificantExponentMorebitsforsignificand:moreaccuracyMorebitsforexponent:increasestherange2023/1/1196FloatingPointRepresentationfornon-integralnumbersIncludingverysmallandverylargenumbersLikescient