ComputerArchitecture,Spring2008

TsinghuaUniversity

流水線基本技術

(Pipelining)

汪東升(Prof.DongshengWang)

wds@

清華大學計算機系科學與技術系

http:〃CPU.

21

1JL

ArelevantquestionTsinghuaUniversity

■Assumingyou'vegot:

□Onewasher(takes30minutes)

□Onedrier(takes40minutes)

□One“folder"(takes20minutes)

■Ittakes90minutestowash,dry,andfold1loadoflaundry.

□Howlongdoes4loadstake?

2

ComputerArchitecture,Spring2008

TheslowwayTsinghuaUniversity

6PM7891011Midnight

Time

304020304020304020304020

R7

CD

夕____%_

■Ifeachloadisdonesequentiallyittakes6hours

3

ComputerArchitecture,Spring2008

LaundryPipeliningTsinghuaUniversity

■Starteachloadassoonaspossible

□Overlaploads

6PM7891011Midnight

Time

30?40?-40l"40'-40W

^^51?

■Pipelinedlaundrytakes3.5hours

ComputerArchitecture,Spring2008

PipeliningLessonsTsinghuaUniversity

?Pipeliningdoesn'thelplatencyof

6PM789

singleload,ithelpsthroughputof

Timeentireworkload

?Pipelineratelimitedbyslowest

3040Tb2-40pipelinestage

■Multipletasksoperating

simultaneouslyusingdifferent

resources

■Potentialspeedup=Numberpipe

stages

■Unbalancedlengthsofpipestages

reducesspeedup

■Timeto“fill”pipelineandtimeto“drain”

itreducesspeedup

5

ComputerArchitecture,Spring2008

PipeliningisnotjustMultiprocessingTsinghuaUniversity

■Pipeliningdoesinvolveparallelprocessing,butinaspecificway.

■Bothmultiprocessingandpipeliningrelatetotheprocessingofmultiple

“things"usingmultiple"functionalunits"

□Multiprocessingimplieseachthingisprocessedentirelybyasingle

functionalunit

■e.g.,multiplelanesatthesupermarket

□Inpipelining,eachthingisbrokenintoasequenceofpieces,where

eachpieceishandledbyadifferent(specialized)functionalunit.

■Supermarketanalogy?

■Pipeliningandmultiprocessingarenotmutuallyexclusive

□Modernprocessorsdoboth,withmultiplepipelines(e.g.,

superscalar)

6

ComputerArchitecture,Spring2008

PipeliningTsinghuaUniversity

■Pipeliningisageneral-purposeefficiencytechnique

□Itisnotspecifictoprocessors

■Pipeliningisusedin:

□Assemblylines

□Bucketbrigades

□Fastfoodrestaurants

■PipeliningisusedinotherCSdisciplines:

□Networking

□Serversoftwarearchitecture

■Usefultoincreasethroughputinthepresenceoflonglatency

□Moreonthatlater...

7

ComputerArchitecture,Spring2008

InstructionexecutionreviewTsinghuaUniversity

■ExecutingaMIPSinstructioncantakeuptofivesteps.

StepNameDescription

InstructionFetchIFReadaninstructionfrommemory.

InstructionDecodeIDReadsourceregistersandgeneratecontrolsignals.

ExecuteEXComputeanR-typeresultorabranchoutcome.

MemoryMEMReadorwritethedatamemory.

WritebackWBStorearesultinthedestinationregister.

■However,aswesaw,notallinstructionsneedallfivesteps.

InstructionStepsrequired

beqIFIDEX

R-typeIFIDEXWB

swIFIDEXMEM

IwIFIDEXMEMWB

8

ComputerArchitecture,Spring2008

浦多又承

Single-cycledatapathdiagramTsinghuaUniversity

■Howlongdoesittaketoexecuteeachinstruction?

9

ComputerArchitecture,Spring2008

Example:InstructionFetch(IF)TsinghuaUniversity

■LefsquicklyreviewhowIwisexecutedinthesingle-cycledatapath.

■WeUIignorePCincrementingandbranchingfornow.

■IntheInstructionFetch(IF)step,wereadtheinstructionmemory.

10

ComputerArchitecture,Spring2008

InstructionDecode(ID)TsinghuaUniversity

■TheInstructionDecode(ID)stepreadsthesourceregisterfrom

theregisterfile.

11

ComputerArchitecture,Spring2008

浦多又承

Execute(EX)TsinghuaUniversity

■Thethirdstep,Execute(EX),computestheeffective

memoryaddressfromthesourceregisterandthe

instruction'sconstantfield.

RegWrite

12

ComputerArchitecture,Spring2008

浦多又承

Memory(MEM)TsinghuaUniversity

■TheMemory(MEM)stepinvolvesreadingthedata

memory,fromtheaddresscomputedbytheALU.

RegWrite

13

ComputerArchitecture,Spring2008

Writeback(WB)TsinghuaUniversity

■Finally,intheWriteback(WB)step,thememory

valueisstoredintothedestinationregister.

RegWrite

14

ComputerArchitecture,Spring2008

AbunchoflazyfunctionalunitsTsinghuaUniversity

■Noticethateachexecutionstepusesadifferentfunctionalunit.

■Inotherwords,themainunitsareidleformostofthe8nscycle!

□TheinstructionRAMisusedforjust2nsatthestartofthe

cycle.

□RegistersarereadonceinID(1ns),andwrittenonceinWB

(1ns).

□TheALUisusedfor2nsnearthemiddleofthecycle.

□Readingthedatamemoryonlytakes2nsaswell.

■Thafsalotofhardwaresittingarounddoingnothing.

15

ComputerArchitecture,Spring2008

PuttingthoseslackerstoworkTsinghuaUniversity

■Weshouldn'thavetowaitfortheentireinstructiontocompletebefore

wecanre-usethefunctionalunits.

■Forexample,theinstructionmemoryisfreeintheInstructionDecode

stepasshownbelow,so...

IdleInstructionDecode(ID)

________A_______

16

ComputerArchitecture,Spring2008

DecodingandfetchingtogetherTsinghuaUniversity

■Whydon'twegoaheadandfetchthenextinstructionwhilewe5re

decodingthefirstone?

Fetch2ndDecode1stinstruction

17

ComputerArchitecture,Spring2008

Executing,decodingandfetching

■Similarly,oncethefirstinstructionentersitsExecutestage,wecango

aheadanddecodethesecondinstruction.

■Butnowtheinstructionmemoryisfreeagain,sowecanfetchthethird

instruction!

Fetch3rdDecode2ndExecute1st

________A__________________________八_______________人_______________

18

ComputerArchitecture,Spring2008

MakingPipeliningWorkTsinghuaUniversity

■We'llmakeourpipeline5stageslong,tohandleeachofthefivesteps

inaloadinstructions(thelongestinstructionforthismachine)

□Stagesare:IF,ID,EX,MEM,andWB

■Wewanttosupportexecuting5instructionssimultaneously:onein

eachstage.

19

ComputerArchitecture,Spring2008

Breakdatapathinto5stagesTsinghuaUniversity

■Insertpipelineregisters

■Eachstagehasitsownfunctionalunits.

■Eachstagecanexecutein2ns

IFIDEXEMEMWB

20

ComputerArchitecture,Spring2008

800C6u-」ds-9」nlo①l-llo」<」2ndE0。

69

(dsAoe一寸⑤m

蕓

(ds*)9二ocls

L(dsAMLMls

LCCM

L蕓

QL(ds*)8

蕓

9MlASWxaQ-H=(ds*)寸318

09g寸

00-0^0

speo"|

PipeliningPerformanceTsinghuaUniversity

Clockcycle

123456789

Iw$t0,4($sp)IFIDEXMEMWB

Iw$t1,8($sp)IFIDEXMEMWB

Iw$t2,12($sp)IFIDEXMEMWB

Iw$t3,16($sp)IFIDEXMEMWB

J

Iw$t4,20($sp)IFIDEXMEMWB

filling

■Executiontimeonidealpipeline:

□timetofillthepipeline+onecycleperinstruction

□HowlongforNinstructions?

■Comparewithotherimplementations:

□SingleCycle:(8nsclockperiod)

■HowmuchfasterispipeliningforN=1000?

22

ComputerArchitecture,Spring2008

PipelineDatapath:ResourceRequirements

Clockcycle

123456789

lw$t0,4($sp)IFIDEXMEMWB

Iw$t1,8($sp)IFIDEXMEMWB

lw$t2,12($sp)IFIDEXMEMWB

Iw$t3,16($sp)IFIDEXMEMWB

Iw$t4,20($sp)IFIDEXMEMWB

■Weneedtoperformseveraloperationsinthesamecycle.

□IncrementthePCandaddregistersatthesametime.

□Fetchoneinstructionwhileanotheronereadsorwritesdata.

■Whatdoesthatmeanforourhardware?

23

ComputerArchitecture,Spring2008

Pipeliningotherinstructiontypes

■R-typeinstructionsonlyrequire4stages:IF,ID,EX,andWB

□Wedon5tneedtheMEMstage

■WhathappensifwetrytopipelineloadswithR-type

instructions?

Clockcycle

123456789

add$sp,$sp,-4IFIDEXWB

sub$v0,$a0,$a1IFIDEXWB

Iw$t0,4($sp)IFIDEXMEMWB

or$s0,$s1,$s2IFIDEXWB

Iw$t1,8($sp)IFIDEXMEMWB

24

ComputerArchitecture,Spring2008

浦多又承

ImportantObservationTsinghuaUniversity

■Eachfunctionalunitcanonlybeusedonceperinstruction

■Eachfunctionalunitmustbeusedatthesamestageforall

instructions:

LoadusesRegisterFile'sWritePortduringits5thstage

R-typeusesRegisterFile'sWritePortduringits4thstage

Clockcycle

123456789

add$sp,$sp,-4IFIDEXWB

sub$v0,$a0,$a1IFIDEXWB

Iw$t0,4($sp)IFIDEXMEMWB

or$s0,$s1,$s2IFIDEXWB

Iw$t1,8($sp)IFIDEXMEMWB

25

ComputerArchitecture,Spring2008

Asolution:InsertNOPstages

■Enforceuniformity

□Makeallinstructionstake5cycles.

□Makethemhavethesamestages,inthesameorder

■Somestagesw川donothingforsomeinstructions

Rtype|IF|ID|EX|NOP|WB

Clockcycle

123456789

add$sp,$sp,-4IFIDEXNOPWB

sub$v0,$a0,$a1IFIDEXNOPWB

Iw$t0,4($sp)IFIDEXMEMWB

or$s0,$s1,$s2IFIDEXNOPWB

Iw$t1,8($sp)IFIDEXMEMWB

■StoresandBrancheshaveNOPstages,too...

storeIFIDEXMEMNOP

branchIFIDEXNOPNOP|

26

ComputerArchitecture,Spring2008

浦多又承

SummaryTsinghuaUniversity

■Pipeliningattemptstomaximizeinstructionthroughputby

overlappingtheexecutionofmultipleinstructions.

■Pipeliningoffersamazingspeedup.

□Inthebestcase,oneinstructionfinishesoneverycycle,and

thespeedupisequaltothepipelinedepth.

■Thepipelinedatapathismuchlikethesingle-cycleone,but

withaddedpipelineregisters

Eachstageneedsisownfunctionalunits

■Nexttimewe'llseethedatapathandcontrol,andwalkthrough

anexampleexecution.

27

ComputerArchitecture,Spring2008

PipelineddatapathandcontrolTsinghuaUniversity

■Lasttimeweintroducedthemainideasofpipelining.

■Todaywellseeabasicimplementationofapipelinedprocessor.

□Thedatapathandcontrolunitsharesimilaritieswiththesingle-

cycleimplementationthatwealreadysaw.

□Anexampleexecutionhighlightsimportantpipeliningconcepts.

■Infuturelectures,we'lldiscussseveralcomplicationsofpipelining

thatwe'rehidingfromyoufornow.

28

ComputerArchitecture,Spring2008

ComputerArchitecture,Spring2008

TsinghuaUniversity

Pipelineddatapathand

control

PipeliningconceptsTsinghuaUniversity

■Apipelinedprocessorallowsmultipleinstructionstoexecuteatonce,

andeachinstructionusesadifferentfunctionalunitinthedatapath.

■Thisincreasesthroughput,soprogramscanrunfaster.

□Oneinstructioncanfinishexecutingoneveryclockcycle,and

simplerstagesalsoleadtoshortercycletimes.

Clockcycle

123456789

Iw$t0,4($sp)IFIDEXMEMWB

sub$v0,$a0,$a1IFIDEXMEMWB

and$t1,$t2,$t3IFIDEXMEMWB

or$s0,$s1,$s2IFIDEXMEMWB

add$t5,$t6,$0IFIDEXMEMWB

30

ComputerArchitecture,Spring2008

PipelinedDatapathTsinghuaUniversity

■Thewholepointofpipeliningistoallowmultipleinstructionstoexecuteatthe

sametime.

■Wemayneedtoperformseveraloperationsinthesamecycle.

□IncrementthePCandaddregistersatthesametime.

□Fetchoneinstructionwhileanotheronereadsorwritesdata.

Clockcycle

123456789

Iw$t0,4($sp)IFIDEXMEMWB

sub$v0,$a0,$a1IFIDEXMEMWB

and$t1,$t2,$t3IFIDEXMEMWB

or$s0,$s1,$s2IFIDEXMEMWB

add$t5,$t6,$0IFIDEXMEMWB

■Thus,likethesingle-cycledatapath,apipelinedprocessorwillneedto

duplicatehardwareelementsthatareneededseveraltimesinthesameclock

cycle.

□Whatabouttheregisterfile?

31

ComputerArchitecture,Spring2008

OneregisterfileisenoughTsinghuaUniversity

■WeneedonlyoneregisterfiletosupportboththeIDandWBstages.

ReadRead

register1data1

ReadRead

register2data2

Write

register

Registers

Write

data

■Readsandwritesgotoseparateportsontheregisterfile.

■Wealreadytookadvantageofthispropertyinoursingle-cycleCPU.

32

ComputerArchitecture,Spring2008

浦多又承

TsinghuaUniversity

Single-cycledatapath,slightlyrearranged

ComputerArchitecture,Spring200833

PipelineregistersTsinghuaUniversity

■Welladdintermediateregisterstoourpipelineddatapath.

■There'salotofinformationtosave,however.We'llsimplifyourdiagramsby

drawingjustonebigpipelineregisterbetweeneachstage.

■Theregistersarenamedforthestagestheyconnect.

IF/IDID/EXEX/MEMMEM/WB

NoregisterisneededaftertheWBstage,becauseafterWBtheinstructionis

done.

34

ComputerArchitecture,Spring2008

PipelineddatapathTsinghuaUniversity

u

I

PCSrc

EX/MEMMEM/WB

Shift

RegWriteleft2

ReadRead

register1data1MemWrite

Zero

ReadRead

register2data2Resultl—>Address

Write

Data

registerMemToReg

memory

RegistersALUOp

WriteY

dataALUSrcWriteRead

datadata

Instr[15-0]Sign

RegDst

extendMemRead

Instr[20-16]

Instr[15-11]

35

ComputerArchitecture,Spring2008

PropagatingvaluesforwardTsinghuaUniversity

■Anydatavaluesrequiredinlaterstagesmustbepropagatedthrough

thepipelineregisters.

■Themostextremeexampleisthedestinationregister.

□Therdfieldoftheinstructionword,retrievedinthefirststage(IF),

determinesthedestinationregister.Butthatregisterisn'tupdated

untilthefifthstage(WB).

□Thus,therdfieldmustbepassedthroughallofthepipeline

stages,asshowninredonthenextslide.

■Noticethatwecan'tkeepasingle^instructionregister,becausethe

pipelinedmachineneedstofetchanewinstructioneveryclockcycle.

36

ComputerArchitecture,Spring2008

ThedestinationregisterTsinghuaUniversity

u

I

PCSrc

EX/MEMMEM/WB

RegWriteleft2

ReadRead

register1data1MemWrite

ReadRead

register2data2Result—>■>Address

Write

Data

registerMemToReg

memory

RegistersALUOp

WriteY

dataALUSrcWriteRead

■>datadata

Instr[15-0]Sign

RegDst

extendMemRead

Instr[20-16]

Instr[15-11]

37

ComputerArchitecture,Spring2008

Whataboutcontrolsignals?TsinghuaUniversity

■Thecontrolsignalsaregeneratedinthesamewayasinthesingle-

cycleprocessor——afteraninstructionisfetched,theprocessor

decodesitandproducestheappropriatecontrolvalues.

■Butjustlikebefore,someofthecontrolsignalswillnotbeneeded

untilsomelaterstageandclockcycle.

■Thesesignalsmustbepropagatedthroughthepipelineuntilthey

reachtheappropriatestage.Wecanjustpasstheminthepipeline

registers,alongwiththeotherdata.

■Controlsignalscanbecategorizedbythepipelinestagethatuses

them.

38

ComputerArchitecture,Spring2008

PipelineddatapathandcontrolTsinghuaUniversity

1

0K-I

ID/EX

EX/MEM

PCSrc

Control