Pipelining Basic 5 Stage PipelineBasic 5 Stage Pipeline

1 EE 357 Unit 18EE 357 Unit 18 Basic Pipelining Techniques Mark Redekopp, All rights reservedSingle & Multi-Cycle PerformanceSingle & MultiCycle PerformanceSingleCycle CPUM ultiCycle CPUS ingle-Cycle CPU Each piece of the datapath requires only a small period of thll i ttiMulti-Cycle CPU Sharing resources allows for compact logic design but in ddiffdthe overall instruction execution (clock cycle) time yielding low utilization of the HW s actual capabilitiesmodern design we can afford replicated structures if needed Each instruction still requires lltltHW s actual capabilities several cycles to complete+Read Reg. 1 #Sh. Lef t + Reg. 2 #WriteReg. #Write DataRead data 1 Read data 0155 Mark Redekopp, All rights reservedRegister FileaaSign Extend1D-CacheeadDataWrite Data11632 PipeliningPipelining Combines elements of both designsg Datapath of _____ CPU w/ separate resources Datapath broken into _____ with temporary registers between stagesstages _____ clock cycle A single instruction requires CPI = nS stem can achie e CPI System can achieve CPI = _____ Overlapping Multiple Instructions (separate instruction in each Stage at once)Inst.

2 1 Inst. 1It1 Inst. 2It2It3 FDExClock 1 Clock 2 Clk 3 MemWB Mark Redekopp, All rights reservedInst. 1 Inst. 2 Inst. 2 Inst. 3 Inst. 3 Inst. 3 Inst. 4 Inst. 4 Inst. 5 Clock 3 Clock 4 Clock 5 Inst. 1 Inst. 1 Inst. 2 Basic 5 Stage PipelineBasic 5 Stage Pipeline Same structure as single cycle but now broken into 5 stages Pipeline Stage registersact as temp registers storing intermediate Pipeline Stage registers act as temp. registers storing intermediate results and thus allowing previous Stage to be reused for another instruction Also,act as a barrier from signals from different stages intermixingAlso, act as a barrier from signals from different stages +Read Sh+A40C+ 1 #Read Reg. 2 #WriteReg #Read data 1ge RegisterAZeroSh. Left 2ge Registerge Register FileReg. #Write DataRead data 2 Pipeline DataWrite DtPipeline Stag1 Mark Redekopp, All rights reservedSign ExtendD-CacheData1632 Issues with PipeliningIssues with Pipelining _____ of HW/logic resources between stages _____ggbecause of full utilization Can t have a single cache (both I & D) because each is needed to fetch one instruction while another accesses data] Prevent signals in one Stage (instruc.)

3 From _____ another Stage (instruc.) and becoming convoluted Balancing Stage delayBalancing Stage delay Clock period = _____ In example below, clock period = _____ means _____ delay for onlyof logic delayonly _____ of logic delaySample Stage Delay10ns10ns50ns Mark Redekopp, All rights reservedFetch LogicDecode LogicExecute LogicResolution of Pipelining IssuesResolution of Pipelining Issues No sharing of HW/logic resources between stagesggg For full performance, no feedback ( Stage i feeding back to Stage i-k) If two stages need a HW resource, _____ the resource in both stages ( an I- AND D-cache) Prevent signals from one Stage (instruc.) from flowing into another Stage (instruc.) and becoming convoluted Stage Registersact asto signals until next edgeStage Registers act as _____ to signals until next edge Balancing Stage delay [Important!!!] Balance or divide long stages (See next slides)ReReRe Mark Redekopp, All rights reservedFetch LogicDecode LogicExec.

4 1 LogicegisteregisterExec. 2 LogicegisterBalancing Pipeline StagesBalancing Pipeline Stages Clock period must equal the 5 ns15 nspqLONGEST delay from register to registerIn Example 1 clock period wouldEx. 1: Unbalanced Stage delayClock Period = 15ns In Example 1, clock period would have to be set to ____ [ 66 MHz], meaning total time through Pipeline =30ns for onlyns of logic10 ns10 nsClock Period = 15ns 30ns for only ____ ns of logic Could try to balance delay in each stageEx. 2: Balanced Stage delayClock Period = 10ns (150% speedup) Example 2: Clock period = __ns [100 MHz], while total time through Pipeline is still = 20ns Mark Redekopp, All rights reservedPipelining Effects on Clock PeriodPipelining Effects on Clock Period5 ns15 ns Rather than just try to balance jydelay we could consider making more stagesDivide long Stage into multipleEx. 1: Unbalanced Stage delayClock Period = 15ns10 ns10 ns Divide long Stage into multiple stages In Example 3, clock period could be 5ns [MHz]Clock Period = 15ns5ns [_____ MHz] Time through the Pipeline (latency) is still 20 ns, but we ve increased our(1 result every 5Ex.)

5 2: Balanced Stage delayClock Period = 10ns (150% speedup)5 ns5 ns5 ns5 nsour _____ (1 result every 5 ns rather than every 10 or 15 ns) Note: There is a small time overhead to adding a Pipeline Mark Redekopp, All rights reservedEx. 3: Break long Stage into multiple stagesClock period = 5 ns (_____ speedup)overhead to adding a Pipeline register/ Stage ( can t go crazy adding stages)Feed-Forward IssuesFeedForward Issues CISC instructions often perform several ALU and memory pyoperations per instructions (A0)+,$8(A0,D1) [M68000/Coldfire ISA] 3 Adds (post-increment, disp., index)() 3 Memory operations (I-Fetch + 1 read + 1 write) This makes Pipelining hard because of multiple uses of ALU and memory Redesign the Instruction Set Architecture to better support Pipelining (MIPS was designed with Pipelining in mind)A401PC+ Reg. 1 #Read Reg. 2 #WriteReg. #WriteRead data 1 Read Lef t 2+ Mark Redekopp, All rights reservedI-CacheRegister FileWrite Datadata 2 Sign Extend01D-CacheRead DataWrite Data11632 Sample 5- Stage PipelineSample 5 Stage Pipeline Examine the Basic operations that need to be performed by ppyour instruction classes LW: I-Fetch, Decode/Reg.

6 Fetch, Address Calc., Read Mem., Write to RegisterWrite to Register SW: I-Fetch, Decode/Reg. Fetch, Address Calc., Write Mem. ALUop: I-Fetch, Decode/Reg. Fetch, ALUop, Write to d/RFthC(Sbt t)Udt PC Bxx: I-Fetch, Decode/Reg. Fetch, Compare (Subtract), Update PC These suggest a 5- Stage Pipeline : II--Fetch, Fetch, ,, Decode/Reg. Fetch, Decode/Reg. Fetch, ALU (Exec.), ALU (Exec.), MemoryMemory Mark Redekopp, All rights reserved Memory, Memory, Reg. Reg. WritebackWritebackBasic 5 Stage PipelineBasic 5 Stage Pipeline All control signals needed for an instruction in the following stages are tdi th d d tdgenerated in the decode Stage and _____ Since writeback doesn t occur until final Stage , write register # is shipped with the instruction through the Pipeline and then used at the end Register File can read out the current data being written if read reg #=write reg #Register File can read out the current data being written if read reg # write reg # +Read Sh+A40C+ 1 #Read Reg.

7 2 #WriteReg #Read data 1ge RegisterAZeroSh. Left 2ge Registerge Register FileReg. #Write DataRead data 2 Pipeline DataWrite DtPipeline Stag1 Mark Redekopp, All rights reservedSign ExtendD-CacheData1632 Sample InstructionsSample InstructionsInstructionLW $t1,4($s0)ADD $t4 $t5 $t6 ADD $t4,$t5,$t6 BEQ $a0,$a1,LOOPFor now let s assume we just execute one at a time For now let s assume we just execute one at a time though that s not how a Pipeline works (multiple though that s not how a Pipeline works (multiple instructions are executed at one time).instructions are executed at one time). Mark Redekopp, All rights reservedst uct o s a e e ecuted at o e t e)st uct o s a e e ecuted at o e t e)LW $t1 4($s0)LW $t1,4($s0) +Read Reg. 1 #Sh. Left+AB45de$s0 #0 valueRead Reg. 1 # RegisterRead Reg. 2 #WriteReg. #Read data 1 Rdtage RegisterALResZeroLeft 2tage RegisterAddrtage RegisterB055) machine cod00000004 / $s0 ResAddressAddrALResZeroRead Reg.

8 2 #WriteReg. #Read data 1 Rdad from memo0I-Cache1 PInstructioRegister FileWrite DataRead data 2 SignPipeline DataWrite DataPipeline St1LW $t1,4($s0# / Offset=0x0 Res.$t1 # / DataWrite FileWrite DataRead data 2$t1 # / Data rea1 Sign ExtendD-Cache1632$t1 #$t1 D-Cache$ Mark Redekopp, All rights reservedFetch LW and increment PCAdd offset 4 to $s0 valueDecode instruction and fetch operandsWrite word to $t1 Read word from memoryADD $t4 $t5 $t6 ADD $t4,$t5,$ +Read Reg. 1 #Sh. Left+AB45odeRead Reg. 1 #$t5 # RegisterRead Reg. 2 #WriteReg. #Read data 1 Rdtage RegisterALResZeroLeft 2tage RegisterAddrtage RegisterB055t6 machine coRead Reg. 2 #WriteReg. #Read data 1Rd$t6 #alue / $t5 valueALResZerom of $t5 + $t6m of $t5 + $t60I-Cache1 PInstructioRegister FileWrite DataRead data 2 SignPipeline DataWrite DataPipeline St1 ADD $t4,$t5,$tRegister FileWrite DataRead data 2 Sign$t4 # / $t6 $t4 # / Sum$t4 # / Sum1 Sign ExtendD-Cache1632 ASign Extend$t4 # Mark Redekopp, All rights reservedFetch ADD and increment PCDecode instruction and fetch operandsAdd $t5 + $t6 Just pass sum throughWrite sum to $t4 BEQ $a0 $a1 LOOPBEQ $a0,$a1, +Read Reg.)

9 1 #Sh. Left+AB45$a0 #code$a0 Left+ RegisterRead Reg. 2 #WriteReg. #Read data 1 Rdtage RegisterALResZeroLeft 2tage RegisterAddrtage RegisterB055 Read Reg. 2 #WriteReg. #Read data 1Rd$a1 #OOP machine cent / $a1 val. / ALResZeroLeft 2arget PCritebackI-Cache1 PInstructioRegister FileWrite DataRead data 2 SignPipeline DataWrite DataPipeline St1 Register FileWrite DataRead data 2 SignEQ $a0,$a1,LOch TaNo wrSign ExtendD-Cache1632 Sign ExtendBEBranc$$ Mark Redekopp, All rights reservedFetch BEQ, increment PC, pass on PC+4 Decode instruction and fetch operands, pass on PC+4Do $a0-$a1 and check if result = 0 Calculate branch target addressUpdate PC,No Mem. AccessDo NothingPipeliningPipelining Now let s see how all three can be run inNow let s see how all three can be run in the Pipeline Mark Redekopp, All rights reserved5- Stage Pipeline5 Stage Mark Redekopp, All rights (LW) Mark Redekopp, All rights reservedFetch (ADD)(LW)PCLW $t1, ($s0)File Mark Redekopp, All rights reservedDecode instruction and fetch operandsFetch $t1 (BEQ)(ADD)(LW)PCreg.

10 # / $ $t4,0 data / 0x0 File$t5,$t604 Mark Redekopp, All rights reservedAdd displacement 0x04 to $s0 Fetch BEQD ecode instruction and fetch $(i+1)(BEQ)(ADD)(LW)PC$t4 BEQ$t1 reg #. # / $t5 Q / $a0,$a1 / / $s0 + 4 Fileand $t6 datadisplacemenant Mark Redekopp, All rights reservedRead word from memoryAdd $t5 + $t6 Decode instruction and pass displacementFetch next instruc i+ (LW)PCBEQ(i+2)(i+1)(BEQ)(ADD)$t1 reg # $t4 reg #Q / $a0,$a1instruc# / DataFile# / Sum1 vals / dispc. i+1p. Mark Redekopp, All rights reservedWrite word to $t1 Just pass data to next stageCheck if condition is trueDecode operands of instruc. i+1 Fetch next instruc i+ (ADD)(i+3)(i+2)(i+1)(BEQ) / DisR4 reg #File. i+1c. i+2placemen / Sumt Mark Redekopp, All rights reservedExecute i+1 Decode i+2 Fetch i+3If condition is true add displacement to PCWrite word to $ (BEQ)(target)(i+3)(i+2)(i+1) DoFile nothing Mark Redekopp, All rights reservedDelete i+2 Delete i+3 Delete i+1Do nothingFetch instruc at branch Pipeline5 Stage ns10 ns10 ns10 ns10 Mark Redekopp, All rights reservedWithout Pipelining (separate execution), each instruction would take _____With Pipelining , each instruction still takes _____ but 1 finishes every _____Non-Pipelined TimingNonPipelined Timing Execute n instructions a k Stage datapath Multicycle CPU w/ k steps or single cycle CPU10ns10ns10ns10ns10nsC1 ADDC2 ADDC3 ADDsteps or single cycle CPU w/ clock cycle k times slower w/o Pipelining :C3 ADDC4 ADDC5 ADD w/o Pipelining .