計算機體系結構

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.

匕產(chǎn)文名乂孝

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.

孑產(chǎn)人〈八牙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