计算机体系结构

ComputerArchitecture

计算机体系结构

Lecture3.Instruction-LevelParallelismI

第三讲、指令级并行I

ChaoLi,PhD.

李超博士

SJTU-SE346,Spring2017

Review

•ISA,micro-architecture,physicaldesign

•EvolutionofISA

•CISCvsRISC,IA32andx86

•MIPSinstructionfields

•Machineinterface,userISAandsystemISA

•Goodinterfacedesign

•Hardwareelements

•SimpleMIPSpipeline

•Pipelinespeedupandpipelinedesignchallenge

2

Outlines

•PipelineHazards

•DynamicScheduling:Scoreboarding

•DynamicScheduling:TomasuloJsAlg.

匕产文名乂孝

J4GHAIT1AOTONGUNrVEUTTY

ProblemswithSimplePipeline

View1:

timetOt!t2t3t4t5

li:rl-(rO)+10IF1ID1EX1MA1WB1

I2:r2-(rl)+20IF2ID2D2ID2ID2EX2

StaledStages

13：r3<—r4+r5IF3F31F3IF3ID3

View2:timetOt1t2t3t4t5t6

g

nIF11I2

oI3I3I3I3

s

QID11I2I2I2I2I3

cr①EXbubblebubblebubble

」11I2

MA11bubblebubblebubble

WB11bubblebubble

Pipelinestalls(addbubble)toavoidhazards

4

DependencyandHazards

•Dependence:

-Reflectsoriginalprogramorder(whichaffectsexecutionresults)

-Indicatesthepossibilityforahazard

-Determinesthedegreeofparallelism

•Dependencesareapropertyofprograms

-Maynotcausehazardwithwell-designedpipeline

•Hazardsarepropertiesofthehardwareorganization

-Casedbyreorderedinstruction,overlappedexecution,etc.

•Threetypesofdependences:

-data,name,andcontrol

5

SHANGHAIIIDTONGUNrvBurn

DataDependence

•(True)Datadependences

-Instructioniproducesaresultthatmaybeusedbyinstructionj,or

-Instructionjisdatadependentoninstructionk,andinstructionkis

datadependentoninstructioni.

•Thereisdataexchangefortruedatadependence

c=a+b

\

e=c+d

•Easytodetermineforregisters(atthedecodestage)

•Hardformemorylocation(requireeffectiveaddress)

10(R1)==20(R2)?10(R1)!=10(R1)?

Q:pipelinehazardsduetomemorydatadependences?

命上芹；U"6

SHANGHAIJIAOTONGUNEVHUrn

NameDependence

•Namedependence:twoinstructionsusethesame

registerormemorylocation(calledaname)butdon't

actuallyexchangedata.

•Anti-dependence

-Instructionjwritesaregisterormemorylocationthatinstruction

readsfrom(instructionIisexecutedfirst)

•Outputdependence

-InstructionIandinstructionjwritethesameregisterormemory

location(mustpreserveprogramorder)

a=b+ca=b+c

/

b=c+da=d+e

Anti-dependenceOutputdependence

7

SHANGHAIJIAOTONGUNrvHisrrY

PossibleDataHazards

•RAW(readafterwrite)Hazard:Instrjgetstheoldvalue

Instri:r3<—(rl)op(r2)

\(Data-Dependence)

Instrj:r5<—(r3)op(r4)

•WAR(writeafterread)Hazard:Instigetsthenewvalue

Instri:r3<-(rl)op(r2)(Anti-Dependence)

Instrj:rl=(r4)op(r5)Q：possibleforatypicalpipeline?

WAW(writeafterwrite)Hazard:producewrongresults

Instri:r3<—(rl)op(r2)(Output-Dependence)

Instrj:r3<—(r4)op(r5)Q:possibleforatypicalpipeline?

趣乂孝8

SHANGHAIJIAOTONGUNEVIRSITY

ControlDependence

•Instructionsareoftencontrolledbysomesetofbranches

ifPl(

SI;

}s1iscontroldependentonp1

S;s2iscontroldependentonp2

Ifp2(sisneithercontroldependentonp1norp2

S2;

)

•CanbeviewedasaformofRAWhazardinvolvingthePC

Q:howdoyouunderstandthis?

®，而U乂券9

SHANGHAIJIAOTONGUNEVBRSITY

InstructionDependencyandPipelineHazard

•Instructionimayneedaresourcebeingused

byalaterinstructionj

-Maycausestructuralhazard

•Instructionimayproducearesultthatis

neededbyalaterinstructionj

-Maycausedatahazard(a.k.apipelinedatahazard)

•Instructionimaydeterminethenextinstruction

tobeexecuted

-Maycausecontrolhazard

10

SHANGHAIJIAOTONGUNEVIRSITY

OvercomingDataHazards

•Hiddendatahazardswithbypassingorforwarding:

-Ifdataisavailablesomewhereinthedatapathprovideabypass

(forwardingpath)togetittotherightstage

r3<—(rl)op(r2)

olddata

11

OvercomingDataHazards

•Freezeearlierstagesuntilthedatabecomesavailable:

-Thehardwaremechanismtodetectadatahazardandstallthe

pipelineisreferredtoaspipelineinterlock

r2_M[(rl)+10]

r4<—(r2)op(r3)

12

SHANGHAIJIAOTONGUNDTERSITY

FunctionalUnit

•Afunctionalunitisaprocessingelement(PE)that

computessomeresultsbasedonitsinput

-Adders,multipliers,ALUs,registerfiles,load/storeunits,etc.

•DifferenttypesofFUs:

-FUwithasingleclocktickofexecutiontime

-FUwithnclockticksofexecutiontime,non-pipelined

-FUwithnclockticksofexecutiontime,pipelined

-FUwithvariableexecutiontime,nonoverlapped

-FUwithvariableexecutiontime,overlapped

instr.

FUtype3pipelinedFUtype5withoverlapping

13

SHANGHAIJIAOTONGUNtVlRSlTY

Long-LatencyOperations

/MULrequiresmuchlongerEXstage

IFIDEXMAWB

IDEXMAWB

IFIDnopnopnopnopnopEXMAWB

WB

Startanyinstructionswhich

areindependentofthelong-

latencyinstruction?

WB

14

SHANGHAIJIAOTONGUNIVERSITY

Outlines

•PipelineHazards

•DynamicScheduling:Scoreboarding

•DynamicScheduling:TomasuloJsAlg.

J周文4乂摹15

SHANGHAIJIAOTONGUNIVERSITY

DynamicSchedulingandOut-of-orderExecution

•Idea:DynamicHWcontrolofhazardandissue

•Implementation:twoclassicalapproaches

-Control-centric:Scoreboarding

-Data-centric:Tomasulo'salgorithm

•Variantsoftheseschemesarealsoseentoday

1.lw$3,100($4)inexecution,cachemiss

In-orderexecution:

2,add$2,$3,$4waitsuntilthemississatisfied

(staticallyscheduled)

3,sub$5,$6,$7waitsfortheadd

1.lw$3,100($4)inexecution,cachemiss

Out-of-orderexecution:

(dynamicallyscheduled)3,sub$5,$6,$7canexecuteduringthecachemiss

2,add$2,$3,$4waitsuntilthemississatisfied

16

CDC6600

•Mainframesupercomputerin1964

•10parallelfunctionalunitsthatarenotpipelined

-4floating-pointunits:2Multipliers,1adder,1divider

掇J盾文4乂摹17

SHANGHAIJ1AOTONGUNIVIRSITy

Scoreboarding

•Scoreboard:Acentralcontroltopreventhazard

-Issue:checkforstructural/WAWhazard;stallissueuntilclear

-Readoperands:readoperandsifnoRAWhazards

-Execution:followedbynotificationtoscoreboard

-Writeresult:checksforWAR;stallwriteuntilclear

力上面U乂孝

ZSHANGHAIJIAOTONGUNtVERSlTY18

ScoreboardComponents

•Instructionstatus-whichofthe4stepstheinstructionisin

•Functionalunitstatus-9fields

-Op：Operationtoperformintheunit

-Fi:Destinationregisternumber

-Fj,Fk：Sourceregisternumber

-Qj,Qk:FunctionalunitsproducingFj,Fk.

-Rj,Rk：FlagsindicatingwhenFj,Fkareready

-Busy：Indicateswhethertheunitisbusyornot

•Registerresultsstatus

-Indicateswhichfunctionalunitwillwriteeachregister,ifoneexists.

Blankwhennopendinginstructionsthatwillwritethatregister.

孑产人〈八牙19

SHANGHAIJIAOTONGUNIVERSITY

ScoreboardExample

Register

InstructionStatus

jk

1.LDF634R2

2.LDF245R3

3.MUL.DF0F2F4

4.SUB.DF8F6F2

5.DIV.DF10F0F6

6.ADD.DF6F8F2

FunctionalUnitStatus

TimeNameBusyOpFiFjFkQiQkRiRk

IntegerNo

MultiNo

Mult2No

AddNo

DivideNo

20

ScoreboardExample:Cycle1

Register

InstructionStatusResultsStatus

jkISROEXWR

1.LDF634R2C1FO

2.LDF245R3F2

3.MUL.DFOF2F4F4

4.SUB.DF8F6F2F6Integer

5.DIV.DF10FOF6F8

6.ADD.DF6F8F2F10

FunctionalUnitStatusDest.SIS2FUforjFUforkFjok?Fkok?

TimeNameBusyOpFiFjFkQiQkRjRk

IntegerYesLDF6R2Yes

MultiNo

Mult2No

AddNo

DivideNo

21

ScoreboardExample:Cycle2

Register

InstructionStatusResultsStatus

jkISROEXWR

1.LDF634R2C1C2

2.LDF245R3

3.MUL.DFOF2F4

4.SUB.DF8F6F2

5.DIV.DF10FOF6

6.ADD.DF6F8F2

FunctionalUnitStatusDest.SIS2FUforj

TimeNameBusyOpFiFjFkQiQkRjRk

IntegerYesLDF6R2Yes

MultiNo

Mult2No

AddNo

DivideNo

MUL.Dcan'tissueduetoin-orderissue!

22

ScoreboardExample:Cycle3

Register

InstructionStatusResultsStatus

jkISROEXWR

1.LDF634R2C1C2C3FO

2.LDF245R3F2

3.MUL.DFOF2F4F4

4.SUB.DF8F6F2F6Integer

5.DIV.DF10FOF6F8

6.ADD.DF6F8F2F10

FunctionalUnitStatusDest.SIS2FUforjFUforkFjok?Fkok?

TimeNameBusyOpFiFjFkQiQkRiRk

IntegerYesLDF6R2Yes

MultiNo

Mult2No

AddNo

DivideNo

23

ScoreboardExample:Cycle4

Register

InstructionStatusResultsStatus

jkISROEXWR

1.LDF634R2C1C2C3C4

2.LDF245R3

3.MUL.DFOF2F4

4.SUB.DF8F6F2

5.DIV.DF10FOF6

6.ADD.DF6F8F2

FunctionalUnitStatusDest.SIS2FUforj

TimeNameBusyOpFiFjFkQiQkRiRk

IntegerYesLDF6R2Yes

MultiNo

Mult2No

AddNo

No

24

ScoreboardExample:Cycle5

Register

InstructionStatusResultsStatus

jkISROEXWR

1.LDF634R2C1C2C3C4

2.LDF245R3C5

3.MUL.DFOF2F4

4.SUB.DF8F6F2

5.DIV.DF10FOF6

6.ADD.DF6F8F2

FunctionalUnitStatusDest.SIS2FUforj

TimeNameBusyOpFiFjFkQiQkRiRk

IntegerYesLDF2R3Yes

MultiNo

Mult2No

AddNo

DivideNo

25

ScoreboardExample:Cycle6

Register

InstructionStatusResultsStatus

jkISROEXWR

1.LDF634R2C1C2C3C4FOMulti

2.LDF245R3C5C6F2Integer

3.MUL.DFOF2F4C6F4

4.SUB.DF8F6F2F6

5.DIV.DF10FOF6F8

6.ADD.DF6F8F2F10

FunctionalUnitStatusDest.SIS2FUforjFUforkFjok?Fkok?

TimeNameBusyOpFiFjFkQiQkRjRk

IntegerYesLDF2R3Yes

MultiYesMLFOF2F4IntegerNoYes

Mult2No

AddNo

DivideNo

26

ScoreboardExample:Cycle7

Register

InstructionStatusResultsStatus

jkISROEXWR

1.LDF634R2C1C2C3C4FOMulti

2.LDF245R3C5C6C7F2Integer

3.MUL.DFOF2F4C6F4

4.SUB.DF8F6F2C7F6

5.DIV.DF10FOF6F8Add

6.ADD.DF6F8F2F10

FunctionalUnitStatusDest.SIS2FUforjFUforkFjok?Fkok?

TimeNameBusyOpFiFjFkQiQkRjRk

IntegerYesLDF2R3Yes

MultiYesMLFOF2F4IntegerNoYes

Mult2No

AddYesSUF8F6F2IntegerYesNo

DivideNo

27

SHANGHAII1AOTONGUNtVERSHY

ScoreboardExample:Cycle8

Register

InstructionStatusResultsStatus

jkISROEXWR

1.LDF634R2C1C2C3C4FOMulti

2.LDF245R3C5C6C7C8F2Integer

3.MUL.DFOF2F4C6F4

4.SUB.DF8F6F2C7F6

5.DIV.DF10FOF6F8Add

6.ADD.DF6F8F2F10

FunctionalUnitStatusDest.SIS2FUforjFUforkFjok?Fkok?

TimeNameBusyOpFiFjFkQiQkRiRk

IntegerNo

MultiYesMLFOF2F4YesYes

Mult2No

AddYesSUF8F6F2YesYes

DivideNo

⑥学28

SHANGHAIJIAOTONGUNIVERSITY

ScoreboardExample:Cycle8

Regii>ter

InstructionStatusStatus

jkISROEXWR

1.LDF634R2C1C2C3C4FOMulti

2.LDF245R3C5C6C7C8F2Integer

3.MUL.DFOF2F4C6F4

4.SUB.DF8F6-2C7F6

5.DIV.DF10FO1=6C8F8Add

6.ADD.DF6F8二2F1CDivide

FunctionalUnitStatusDest.SIS2FUforjFUforkFjok?Fkok?

TimeNameBusyOpFiFjFkQiQkRjRk

IntegerNo

MultiYesMLFOF2F4YesYes

Mult2No

AddYesSUF8F6F2YesYes

DivideYesDIF10FOF6MultiNoYes

29

ScoreboardExample:Cycle9

Regii>ter

InstructionStatusStatus

jkISROEXWR

1.LDF634R2C1C2C3C4F0Multi

2.LDF245R3C5C6C7C8F2

3.MUL.DF0F2F4C6C9F4

4.SUB.DF8F6-2C7C9F6

5.DIV.DF10F01=6C8F8Add

6.ADD.DF6F81二2F1CDivide

FunctionalUnitStatusDest.SIS2FUforjFUforkFjok?Fkok?

TimeNameBusyOpFiFjFkQiQkRjRk

IntegerNo

10MultiYesMLF0F2F4YesYes

Mult2No

2AddYesSUF8F6F2YesYes

DivideYesDIF10F0F6MultiNoYes

Q盾文4乂券30

夕SHANGHAIJIAOTONGUNDTERSnY

ScoreboardExample:Cycle10

Register

InstructionStatusResultsStatus

jkISROEXWR

1.LDF634R2C1C2C3C4FOMulti

2.LDF245R3C5C6C7C8F2

3.MUL.DFOF2F4C6C9F4

4.SUB.DF8F6F2C7C9F6

5.DIV.DF10FOF6C8F8Add

6.ADD.DF6F8F2F10Divide

FunctionalUnitStatusDest.SIS2FUforjFUforkFjok?Fkok?

TimeNameBusyOpFiFjFkQjQkRjRk

IntegerNo

9MultiYesMLFOF2F4YesYes

Mult2No

1AddYesSUF8F6F2YesYes

DivideYesDIF10FOMultiNoYes

⑥¥盾文4乂挈31

SHANGHAIJIAOTONGUNIVERSITY

ScoreboardExample:Cycle11

Register

InstructionStatusResultsStatus

jkISROEXWR

1.LDF634R2C1C2C3C4FOMulti

2.LDF245R3C5C6C7C8F2

3.MUL.DFOF2F4C6C9F4

4.SUB.DF8F6F2C7C9C11F6

5.DIV.DF10FOF6C8F8Add

6.ADD.DF6F8F2F10Divide

FunctionalUnitStatusDest.SIS2FUforjFUforkFjok?Fkok?

TimeNameBusyOpFiFjFkQiQkRjRk

IntegerNo

8MultiYesMLFOF2F4YesYes

Mult2No

0AddYesSUF8F6F2YesYes

DivideYesDIF10FOF6MultiNoYes

32

ScoreboardExample:Cycle12

Register

InstructionStatusResultsStatus

jkISROEXWR

1.LDF634R2C1C2C3C4FOMulti

2.LDF245R3C5C6C7C8F2

3.MUL.DFOF2F4C6C9F4

4.SUB.DF8F6F2C7C9C11C12F6

5.DIV.DF10FOF6C8F8Add

6.ADD.DF6F8F2F10Divide

FunctionalUnitStatusDest.SIS2FUforjFUforkFjok?Fkok?

TimeNameBusyOpFiFjFkQjQkRjRk

IntegerNo

7MultiYesMLFOF2F4YesYes

Mult2No

AddNo

DivideYesDIF10FOMultiNoYes

藏¥盾文4乂孚33

SHANGHAIJIAOTONGUNrVERSiTY

ScoreboardExample:Cycle13

Regii>ter

InstructionStatusStatus

jkISROEXWR

1.LDF634R2C1C2C3C4FOMulti

2.LDF245R3C5C6C7C8F2

3.MUL.DFOF2F4C6C9F4

4.SUB.DF8F6-2C7C9C11C12F6Add

5.DIV.DF10FO1=6C8F8

6.ADD.DF6F8二2C13F1CDivide

FunctionalUnitStatusDest.SIS2FUforjFUforkFjok?Fkok?

TimeNameBusyOpFiFjFkQiQkRjRk

IntegerNo

6MultiYesMLFOF2F4Yes