计算机结构(六)

CS4100：^算檄结情

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)

气方国交清第大摩Arithmetic-1ComputerArchitecture

NationalTsingHuaUniversityCTKing

Problem：DesigningMIPSALU

♦Requirements:mustsupportthefollowingarithmetic

andlogicoperations

•add,sub:two'scomplementadder/subtractorwith

overflowdetection

•and,or:logicalAND,logicalOR

•sit(setonlessthan):two'scomplementadderwith

inverter,checksignbitofresult

中国五清善大摩Arithmetic-2ComputerArchitecture

NationalTsingHuaUniversityCTKing

FunctionalSpecification

Fig.4.21

000and

001or

010add

110subtract

Fig.4.20

111set-on-less-than

中国五清善大摩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

中国五清善大摩Arithmetic-6ComputerArchitecture

NationalTsingHuaUniversityCTKing

HowaboutSubtraction?

♦2'scomplement:takeinverseofeverybitandadd1

(atcinoffirststage)

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

•Bit-wiseinverseofBisB'

中国五清善大摩Arithmetic-7ComputerArchitecture

NationalTsingHuaUniversityCTKing

RevisedDiagram

♦LSBandMSBneedtodoalittleextra

气方国交清第大摩Arithmetic-8ComputerArchitecture

NationalTsingHuaUniversityCTKing

Overflow

DecimalBinaryDecimal2*scomplement

0000000000

0001-11111

20010-21110

30011-31101

40100-41100

50101-51011

60110-61010

70111-71001

-81000

01117

中国五清善大摩Arithmetic-9ComputerArchitecture

NationalTsingHuaUniversityCTKing

OverflowDetection

♦Overflow:resulttoobig/smalltorepresent

•-8<4-bitbinarynumber<7

•Whenaddingoperandswithdifferentsigns,overflow

cannotoccur!

•Overflowoccurswhenadding:

■2positivenumbersandthesumisnegative

■2negativenumbersandthesumispositive

=>signbitissetwiththevalueoftheresult

•Overflowif:CarryintoMSBwCarryoutofMSB

中国五清善大摩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

中国五清善大摩Arithmetic-11ComputerArchitecture

NationalTsingHuaUniversityCTKing

ZeroDetectionLogic

♦ZeroDetectionLogicisaoneBIGNOTgate

NationalTsingHuaUniversityCTKing

PuttingItAltogether(I)

♦1-bitinALU

ALUop

b

Less

Fig.4.17a

CarryOut

气方国交清第大摩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

气方国交清年大摩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)

气方国五清善大摩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.

中国五清善大摩Arithmetic-18ComputerArchitecture

NationalTsingHuaUniversityCTKing

CascadedCarryLookahead

♦Expensivetobuilda“full”carrylookaheadadder

•JustimaginelengthoftheequationforCin31

♦Commonpractices:

•ConnectsseveralN-bitlookaheadadderstoformabig

one

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

中国五清善大摩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

气方国交清第大摩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)

中国五清善大摩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

中国五清善大摩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

中国五清善大摩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

中国五清善大摩Arithmetic-26ComputerArchitecture

NationalTsingHuaUniversityCTKing

UnsignedMultiply

Paperandpencilexample(unsigned):

Multiplicand1000由

MultiplierX1001ten

1000

0000

0000

1000

Product01001000ten

♦mbitsxnbits=m+nbitproduct

♦Binarymakesiteasy:

•0=>place0(Oxmultiplicand)

•1=>placeacopy(lxmultiplicand)

♦3versionsofmultiplyhardwareandalgorithm

中国五清善大摩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?

气方国交清第大摩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

气方国交清第大摩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

中国五清善大摩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)

气方国交清笨大，裂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

气方国交清第大摩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

中国五清善大摩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

中国五清善大摩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)

气方国交清第大摩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

中国五清善大摩Arithmetic-42ComputerArchitecture

NationalTsingHuaUniversityCTKing

DivideHardware(Version1)

♦64-bitDivisorregister(initializedwith32-bitdivisorin

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

(initializedwith64-bitdividend),32-bitQuotient

register

中国五清善大摩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

气方国交清第大摩Arithmetic-45ComputerArchitecture

NationalTsingHuaUniversityCTKing

DivideHardware(Version2)

♦32-bitDivisorregister,32-bitALU,64-bitRemainder

register,32-bitQuotientregister

NationalTsingHuaUniversityCTKing

Gtart:PlaceDividendinRemainderD

DivideAlgorithm1.ShiftRemainderregisterleft1bit

(Version2)

区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

气方国交清第大摩Arithmetic-48ComputerArchitecture

NationalTsingHuaUniversity