計(jì)算機(jī)結(jié)構(gòu)(六)

CS4100：^算檄結(jié)情

ComputerArithmetic

11立清莘大工程擘系

九十三擘年度第一擘期

AdaptedfromclassnotesofD.PattersonandW.Dally

Copyright1998,2000UCB

氣方圓交清星大擘

NationalTsingHuaUniversity

Outline

?Numberrepresentations(Sec.4.2)

?Arithmeticandlogicoperations(Sec.4.3,4.4)

?Constructinganarithmeticlogicunit(Sec.4.5)

?Multiplication(Sec.4.6)

?Division(Sec.4.7)

?Floatingpoint(Sec.4.8)

氣方國(guó)交清第大摩Arithmetic-1ComputerArchitecture

NationalTsingHuaUniversityCTKing

Problem：DesigningMIPSALU

?Requirements:mustsupportthefollowingarithmetic

andlogicoperations

?add,sub:two'scomplementadder/subtractorwith

overflowdetection

?and,or:logicalAND,logicalOR

?sit(setonlessthan):two'scomplementadderwith

inverter,checksignbitofresult

中國(guó)五清善大摩Arithmetic-2ComputerArchitecture

NationalTsingHuaUniversityCTKing

FunctionalSpecification

Fig.4.21

000and

001or

010add

110subtract

Fig.4.20

111set-on-less-than

中國(guó)五清善大摩Arithmetic-3ComputerArchitecture

NationalTsingHuaUniversityCTKing

ABit-sliceALU

?Designtrick1:divideandconquer

?Breaktheproblemintosimplerproblems,solvethem

andgluetogetherthesolution

?Designtrick2:solvepartoftheproblemandextend

A1-bitALU

?Designtrick3:takepiecesyouknow(orcan

imagine)andtrytoputthemtogether

Fig.4.14

ComputerArchitecture

CTKing

A4-bitALU

1-bitALU4-bitALU

中國(guó)五清善大摩Arithmetic-6ComputerArchitecture

NationalTsingHuaUniversityCTKing

HowaboutSubtraction?

?2'scomplement:takeinverseofeverybitandadd1

(atcinoffirststage)

?A+B!+1=A+(BJ+1)=A+(-B)=A-B

?Bit-wiseinverseofBisB'

中國(guó)五清善大摩Arithmetic-7ComputerArchitecture

NationalTsingHuaUniversityCTKing

RevisedDiagram

?LSBandMSBneedtodoalittleextra

氣方國(guó)交清第大摩Arithmetic-8ComputerArchitecture

NationalTsingHuaUniversityCTKing

Overflow

DecimalBinaryDecimal2*scomplement

0000000000

0001-11111

20010-21110

30011-31101

40100-41100

50101-51011

60110-61010

70111-71001

-81000

01117

中國(guó)五清善大摩Arithmetic-9ComputerArchitecture

NationalTsingHuaUniversityCTKing

OverflowDetection

?Overflow:resulttoobig/smalltorepresent

?-8<4-bitbinarynumber<7

?Whenaddingoperandswithdifferentsigns,overflow

cannotoccur!

?Overflowoccurswhenadding:

■2positivenumbersandthesumisnegative

■2negativenumbersandthesumispositive

=>signbitissetwiththevalueoftheresult

?Overflowif:CarryintoMSBwCarryoutofMSB

中國(guó)五清善大摩Arithmetic-10ComputerArchitecture

NationalTsingHuaUniversityCTKing

OverflowDetectionLogic

?Overflow=Carryln[N-1]XORCarryOut[N-1]

AO.

XYXXORY

BO

000

A1.011

101

B1

110

A2.

B2

Overflow

A3.

B3

中國(guó)五清善大摩Arithmetic-11ComputerArchitecture

NationalTsingHuaUniversityCTKing

ZeroDetectionLogic

?ZeroDetectionLogicisaoneBIGNOTgate

NationalTsingHuaUniversityCTKing

PuttingItAltogether(I)

?1-bitinALU

ALUop

b

Less

Fig.4.17a

CarryOut

氣方國(guó)交清第大摩Arithmetic-13ComputerArchitecture

NationalTsingHuaUniversityCTKing

PuttingItAltogether(II)

?SignbitinALU

NationalTsingHuaUniversityCTKing

BnegateOperationARippleCarry

Adder

ALUopFunction

000and

001or

010add

nosubtract

一

Result31]set-less-than

a31?Carryinin

b31?ALU31—Set

0?LessaOverflow

Fig.4.19

ProblemswithRippleCarryAdder

?CarrybitmayhavetopropagatefromLSBtoMSB=>

worstcasedelay:N-stagedelay

AO

BO

A1

B1

A2

B2

A3DesignTrick:lookfor

B3parallelismandthrow

hardwareatit

氣方國(guó)交清年大摩Arithmetic-16ComputerArchitecture

NationalTsingHuaUniversityCTKing

CarryLookahead：Theory(I)

?CarryOut=(B*Carryln)+(A*Carryln)+(A*B)

?Cin2=Coutl=(Bl*Cinl)+(A1*Cin1)+(Al*Bl)

?Cinl=CoutO=(BO*CinO)+(AO*CinO)+(AO*BO)

?SubstitutingCinlintoCin2:

?Cin2=(Al*A0*B0)+(A1*A0*Cin0)+(A1*BO*CinO)

+(B1*AO*BO)+(B1*AO*CinO)+(Bl*BO*CinO)

+(A1*B1)

氣方國(guó)五清善大摩Arithmetic-17ComputerArchitecture

NationalTsingHuaUniversityCTKing

CarryLookahead：Theory(II)

?Nowdefinetwonewterms:

?GenerateCarryatBiti:gi=Ai*Bi

?PropagateCarryviaBiti:pi=Ai+Bi

?Wecanrewrite:

?Cinl=gO+(pO*CinO)

?Cin2=gl+(pl*gO)+(p1*pO*CinO)

?Cin3=g2+(p2*gl)+(p2*pl*g0)+(p2*pl*pO*CinO)

?Carrygoingintobit3is1if

?Wegenerateacarryatbit2(g2)

?Orwegenerateacarryatbit1(gi)and

bit2allowsittopropagate(p2*gl)

?Orwegenerateacarryatbit0(gO)and

bit1aswellasbit2allowsittopropagate.

中國(guó)五清善大摩Arithmetic-18ComputerArchitecture

NationalTsingHuaUniversityCTKing

CascadedCarryLookahead

?Expensivetobuilda“full”carrylookaheadadder

?JustimaginelengthoftheequationforCin31

?Commonpractices:

?ConnectsseveralN-bitlookaheadadderstoformabig

one

Result[31:24]Result[23:16]Result[15:8]Result[7:0]

中國(guó)五清善大摩Arithmetic-19ComputerArchitecture

NationalTsingHuaUniversityCTKing

CarryIn

aO?CarryInACarryLookahead

bO?aResultO—3

a1.

b1?

ALUOAdder

a2?

POPi

b2?GOgi

a3.

b3—?Carry-lookaheadun

ci+1

a4■?CarryIn

b4?Result4—7

a5??ABCout

b5.ALU1

a6tP1pi+1000kill

b6.G1gi+1

a7.

b7.01Cinpropagate

ci+210Cinpropagate

a8.CarryIn

b8?Result8-11

a91?111generate

b9?ALU2

a1O?P2pi+2

b1O?G2gi+2

a11?

b11?

ci+3G=A*B

a12?CarryInP=A+B

b12?Resultl2—15

a13?

3

b13.P3

a14.G3

b14?

a15?C4

b15?ci+4Fig.4.24

Carry-selectAdder

CP(2n)=2*CP(n)n-bitaddern-bitadder

CP(2n)=CP(n)+CP(mux)

Cout,Designtrick:guess

氣方國(guó)交清第大摩Arithmetic-21ComputerArchitecture

NationalTsingHuaUniversityCTKing

AddXORtoALU

?Expandmultiplexor

Outline

?Numberrepresentations(Sec.4.2)

?Arithmeticandlogicoperations(Sec.4.3,4.4)

?Constructinganarithmeticlogicunit(Sec.4.5)

?Multiplication(Sec.4.6)

?Division(Sec.4.7)

?Floatingpoint(Sec.4.8)

中國(guó)五清善大摩Arithmetic-23ComputerArchitecture

NationalTsingHuaUniversityCTKing

MultiplicationinMIPS

mul$tl,$t2#tl*t2

?Nodestinationregister:productcouldbe*264;need

twospecialregisterstoholdit

?3-stepprocess:

$tl01111111111111111111111111111111

X$t20000000000000000000000000000000

0001111111111111111111111111111111000|000000000000000000000000000

Lo

mfhi$t3$t300011111111111111111111111111111

mflo$t4$t411000000000000000000000000000000

中國(guó)五清善大摩Arithmetic-24ComputerArchitecture

NationalTsingHuaUniversityCTKing

DivisioninMIPS

div$tl,$t2#tl/t2

?QuotientstoredinLozremainderinHi

mflo$t3#copyquotienttot3

mfhi$t4#copyremaindertot4

?3-stepprocess

?Unsignedmultiplicationanddivision:

mulu$tl,$t2#tl*t2

divu$tl,$t2#tl/t2

?Justlikemulzdiv,exceptnowinterprettl,t2as

unsignedintegersinsteadofsigned

?Answersarealsounsigned,usemfhizmflotoaccess

中國(guó)五清善大摩Arithmetic-25ComputerArchitecture

NationalTsingHuaUniversityCTKing

MIPSMultiply/bivideSummary

?Startmultiply,divide

?MULTrszrtHI-LO=rsxrt//64-bitsigned

?MULTUrszrtHI-LO=rsxst//64-bitunsigned

?DIVrs,4LO=rs+rt;HI=rsmodrt

?DIVUrs,rt

?Moveresultfrommultiply,divide

?MFHIrdrd=HI

?MFLOrdrd=LO

?MovetoHIorLO

?MTHIrdHI=rd

?MTLOrdLO=rd

中國(guó)五清善大摩Arithmetic-26ComputerArchitecture

NationalTsingHuaUniversityCTKing

UnsignedMultiply

Paperandpencilexample(unsigned):

Multiplicand1000由

MultiplierX1001ten

1000

0000

0000

1000

Product01001000ten

?mbitsxnbits=m+nbitproduct

?Binarymakesiteasy:

?0=>place0(Oxmultiplicand)

?1=>placeacopy(lxmultiplicand)

?3versionsofmultiplyhardwareandalgorithm

中國(guó)五清善大摩Arithmetic-27ComputerArchitecture

NationalTsingHuaUniversityCTKing

UnisignedMultiplier(Ver.1)

?64-bitmultiplicandregister(with32-bitmultiplicand

atrighthalf),64-bitALU,64-bitproductregister,32-bit

multiplierregister

NationalTsingHuaUniversityCTKing

Multi

0010x0011

Product

00000000

00000010

00000110

00000110

00000110000000100000IYes：32repetitions

CDone)Fig.4.26

Observations：MultiplyVer.1

?1clockpercycle=>?100clockspermultiply

?Ratioofmultiplytoadd5:1to100:1

?Halfofthebitsinmultiplicandalways0

=>64-bitadderiswasted

?O'sinsertedinleftofmultiplicandasshifted

=>leastsignificantbitsofproductneverchanged

onceformed

?Insteadofshiftingmultiplicandtoleft,shiftproductto

right?

氣方國(guó)交清第大摩Arithmetic-30ComputerArchitecture

NationalTsingHuaUniversityCTKing

UnisignedMultiplier(Ver.2)

?32-bitmultiplicandregister,32-bitALU,64-bit

productregister,32-bitmultiplierregister

NationalTsingHuaUniversityCTKing

Multim(Start)

MultiplierO=11.TestMultiplier。=0

ultiplierO

1a.Addmultiplicandtolefthalfofproductand

placetheresultinlefthalfofProductreqister

ProductMultiplierMultiplicand

0000000000110010(add)

001000002.ShiftProductregisterright1bit

0001000000010010(add)

00110000I3.ShiftMultiplierregisterright1bif

0001100000000010(nop)

0000110000000010(nop)

000001100000001032ndo:<32repetitions

epetitio

?Observation:Productregisterwastes|Yes:32repetitions

space=>combineMultiplierand

CDone)

ProductregisterFig.4.29

UnisignedMultiplier(Ver.3)

?32-bitMultiplicandregister,32-bitALU,64-bitProduct

register(HI&LOinMIPS),(O-bitMultiplierregister)

口9.4.31

氣方國(guó)交清第大摩Arithmetic-33ComputerArchitecture

NationalTsingHuaUniversityCTKing

Multi

1a.Addmultiplicandtolefthalfofproductand

placetheresultinlefthalfofProductregister

MultiplicandProduct

001000000011

00100011

001000010001

00110001

001000011000

001000001100

001000000110p.432|Yes:32repetitions

,CDone)

Observations：MultiplyVer.3

?2stepsperbitbecausemultiplierandproduct

registerscombined

?MIPSregistersHiandLoareleftandrighthalfof

Productregister

=>thisgivestheMIPSinstructionMuItU

?Whataboutsignedmultiplication?

?Theeasiestsolutionistomakebothpositiveand

rememberwhethertocomplementproductwhen

done(leaveoutsignbitrunfor31steps)

?Applydefinitionof2'scomplement

■sign-extendpartialproductsandsubtractatend

?Booth'sAlgorithmisanelegantwaytomultiplysigned

numbersusingsamehardwareasbeforeandsave

cycles

中國(guó)五清善大摩Arithmetic-35ComputerArchitecture

NationalTsingHuaUniversityCTKing

Booth'sAlgorithm：Motivation

Example:2x6=0010x0110:

0010two

+0000shift(0inmultiplier)

+0010add(1inmultiplier)

+0010add(1inmultiplier)

+0000shift(0inmultiplier)

0001100two

Cangetsameresultinmorethanoneway:

6=-2+80110=-00010+01000

?Basicidea:replaceastringof1swithaninitial

subtractonseeingaoneandaddafterlastone

0010two

0110two

-QUUU■shift(0inmultiplier)

0010sub(first1inmultiplier)

0000shift(midstringofIs)

+0010add(priorstephadlast1)

氣方國(guó)交清笨大，裂0001100tw。Arithmetic-36ComputerArchitecture

NationalTsingHuaUniversityCTKing

Booth'sAlgorithm：Rationale

rniddleofrun

)°

endofrun0(J111beginningofrun

CurrentBittoExplanationExampleOp

bitright

10BeginsrunofIs00001111000sub

11MiddlerunofIsoooomiooonone

01EndofrunofIs00001111000add

00MiddlerunofOs00001111000none

Originallyforspeed(whenshiftwasfasterthanadd)

?Whyitworks?

+10000

01111

氣方圓立清屋大摩Arithmetic-37ComputerArchitecture

NationalTsingHuaUniversityCTKing

Booth'sAlgorithm

1.Dependingonthecurrentandpreviousbits,

dooneofthefollowing:

00:Middleofastringof0sznoarithmeticop.

01:EndofastringofIs,soaddmultiplicandto

theIe什halfoftheproduct

10:BeginningofastringofIs,sosubtract

multiplicandfromthelefthalfoftheproduct

11:Middleof?stringofIs,sonoarithmeticop.

2.Asinthepreviousalgorithm,shifttheProduct

registerright(arithmetically)1bit

氣方國(guó)交清第大摩Arithmetic-38ComputerArchitecture

NationalTsingHuaUniversityCTKing

BoothsExample(2x7)

OperationMultiplicandProductnext?

0.initialvalueooioooooonio10->sub

la.P=P-m1110+1110

111001110shiftP(signext)

lb.ooion11ooi1111->nopzshift

2.ooiomilooii11->nop,shift

3.001011111100101->add

4a.0010+0010

000111001shift

4b.0010000011100done

中國(guó)五清善大摩Arithmetic-39ComputerArchitecture

NationalTsingHuaUniversityCTKing

BoothsExample(2x-3)

OperationMultiplicandProductnext?

0.initialvalue001000001101010->sub

la.P=P-m1110+1110

111011010shiftP(signext)

lb.0010nil0110101->add

+0010

2a.000101101shiftP

2b.001000001011010->sub

+1110

3a.0010111010110shift

3b.001011110101111->nop

4a111101011shift

4b.0010111110101done

中國(guó)五清善大摩Arithmetic-40ComputerArchitecture

NationalTsingHuaUniversityCTKing

Outline

?Numberrepresentations(Sec.4.2)

?Arithmeticandlogicoperations(Sec.4.3,4.4)

?Constructinganarithmeticlogicunit(Sec.4.5)

?Multiplication(Sec.4.6)

?Division(Sec.4.7)

?Floatingpoint(Sec.4.8)

氣方國(guó)交清第大摩Arithmetic-41ComputerArchitecture

NationalTsingHuaUniversityCTKing

Divide：Paper&Pencil

1001tenQuotient

Divisor1000tAnI1001010tAnDividend

-1000

10

101

1010

-TOGO

10tenRemainder

?Seehowbiganumbercanbesubtracted,creating

quotientbitoneachstep

Binary=>1*divisoror0*divisor

?Threeversionsofdivide,successiverefinement

?Bothdividendanddivisorare32-bitpositiveintegers

中國(guó)五清善大摩Arithmetic-42ComputerArchitecture

NationalTsingHuaUniversityCTKing

DivideHardware(Version1)

?64-bitDivisorregister(initializedwith32-bitdivisorin

Ie什half),64-bitALU,64-bitRemainderregister

(initializedwith64-bitdividend),32-bitQuotient

register

中國(guó)五清善大摩Arithmetic-43ComputerArchitecture

NationalTsingHuaUniversityCTKing

Gtart:PlaceDividendinRemainderD

DivideAlgorithm

(Version1)1.SubtractDivisorregisterfrom

Remainderregister,andplacethe

resultinRemainderreaister

QuotDivisorRem.

00000010000000000111

11100111

00000111

00000001000000000111

11110111

00000111

00000000100000000111

11111111

00000111

00000000010000000111

00000011

000100000011

00010000001000000011

00000001

001100000001

00110000000100000001

Observations：DivideVersion1

?Halfofthebitsindivisorregisteralways0

=>1/2of64-bitadderiswasted

=>1/2ofdivisoriswasted

?Insteadofshiftingdivisortoright

shiftremaindertoleft?

?1ststepcannotproducea1inquotientbit

(otherwisequotientistoobigfortheregister)

=>switchordertoshiftfirstandthensubtract

=>save1iteration

氣方國(guó)交清第大摩Arithmetic-45ComputerArchitecture

NationalTsingHuaUniversityCTKing

DivideHardware(Version2)

?32-bitDivisorregister,32-bitALU,64-bitRemainder

register,32-bitQuotientregister

NationalTsingHuaUniversityCTKing

Gtart:PlaceDividendinRemainderD

DivideAlgorithm1.ShiftRemainderregisterleft1bit

(Version2)

區(qū)SubtractDivisorregisterfromtheleft

Quot.Remain.DivisorhalfofRemainderregister,andplacethe

00000000001110010resultinthelefthalfofRemainderregister

1.1000000001110

1.211101110

1.3b000000001110

2.1000000011100

2.211111100

2.3b000000011100

3.1000000111000

3.200011000

3.3a000100011000

4.1000100110000

4.200010000

4.3a001100010000

001100010000

Observations：DivideVersion2

?EliminateQuotientregisterbycombiningwith

Remainderregisterasshiftedleft

?StartbyshiftingtheRemainderregisterleftasbefore

?Thereafterloopcontainsonlytwostepsbecausethe

shiftingofRemainderregistershiftsboththeremainder

inthelefthalfandthequotientintherighthalf

?Theconsequenceofcombiningthetworegisters

togetherandtheneworderoftheoperationsinthe

loopisthattheremainderwillbeshiftedleftonetime

toomany

?Thusthefinalcorrectionstepmustshiftbackonlythe

remainderinthelefthalfoftheregister

氣方國(guó)交清第大摩Arithmetic-48ComputerArchitecture

NationalTsingHuaUniversity