Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 27Slide 28Slide 29Slide 30Slide 31Slide 32Slide 33Slide 34Slide 35Slide 36Slide 37UC Regents Fall 2005 © UCBCS 152 L8: Pipelining II2005-9-22John Lazzaro (www.cs.berkeley.edu/~lazzaro)CS 152 Computer Architecture and EngineeringLecture 8 – Pipelining IIwww-inst.eecs.berkeley.edu/~cs152/TAs: David Marquardt and Udam SainiUC Regents Fall 2005 © UCBCS 152 L8: Pipelining IIFrom First Class: The Architect’s ContractTo the program, it appears that instructions execute in the correct order defined by the ISA.What the machine actually does is up to the hardware designers, as long as the contract is kept.As each instruction completes, themachine state (regs, mem) appears to the program to obey the ISA.The primary challenge of 152 CPU projects!UC Regents Fall 2005 © UCBCS 152 L8: Pipelining IILast Time: A 5-stage pipelined CPUIRIRBAMInstr Fetch“IF” Stage“ID/RF” StageDecode & Reg Fetch1 2“EX” StageExecutionIRYM3IRR“MEM” StageMemoryWE, MemToReg4WB5WriteBackMux,LogicUC Regents Fall 2005 © UCBCS 152 L8: Pipelining IIToday: HazardsVisualizing pipelines to evaluatehazard detection and resolution.A tool kit for hazard resolution.A taxonomy of pipeline hazards.Tuesday: We apply this knowledge to design a pipelined MIPS CPU that obeys the contract with the programmer.UC Regents Fall 2005 © UCBCS 152 L8: Pipelining IIThe lectures are a gentle introduction, to prepare you to read the book ...The book presentation of pipelined processors is sufficient to do Lab 3.These lectures are not.Reminder: Do the Reading!UC Regents Fall 2005 © UCBCS 152 L8: Pipelining IIVisualizing PipelinesUC Regents Fall 2005 © UCBCS 152 L8: Pipelining IIPipeline Representation #1: TimelineIRIRIF (Fetch) ID (Decode) EX (ALU)IRIRMEMWBADD R4,R3,R2OR R7,R6,R5SUB R1,R9,R8XOR R3,R2,R1AND R6,R5,R4I1:I2:I3:I4:I5:Sample ProgramIF IDIFEXIDIFMEMEXIDIFWBMEMEXIFIDWBMEMIDEXIFWBEXMEMIDMEMWBEXPipeline is “full”Good for visualizing pipeline fills.I1:I2:I3:I4:I5:t1 t2 t3 t4 t5 t6 t7 t8Time:InstI6:UC Regents Fall 2005 © UCBCS 152 L8: Pipelining IIPipeline is “full”Good for visualizing pipeline stalls.Representation #2: Resource UsageIRIR IRIRADD R4,R3,R2OR R7,R6,R5SUB R1,R9,R8XOR R3,R2,R1AND R6,R5,R4I1:I2:I3:I4:I5:Sample ProgramI1 I2I1I3I2I1I4I3I2I1I5I4I3I1I2IF:ID:EX:MEM:WB:t1 t2 t3 t4 t5 t6 t7 t8Time:StageIF (Fetch) ID (Decode) EX (ALU) MEMWBI5I4I2I3I6I5I3I4I6I7I4I5I6I7I8UC Regents Fall 2005 © UCBCS 152 L8: Pipelining IIHazard TaxonomyUC Regents Fall 2005 © UCBCS 152 L8: Pipelining IIStructural HazardsSeveral pipeline stages need to use the same hardware resource at the same time.Solution #1: Add extra copies ofthe resource (only works sometime).Solution #2: Change resource sothat it can handle concurrent use.Solution #3: Stages “take turns”by stalling parts of the pipeline.UC Regents Fall 2005 © UCBCS 152 L8: Pipelining IIStructural hazard solution: 2 memoriesIRIRBAMInstr Fetch“IF” Stage“ID/RF” StageDecode & Reg Fetch1 2“EX” StageExecutionIRYM3IRR“MEM” StageMemoryWE, MemToReg4WB5WriteBackMux,LogicWhat if we merged Data and Instr memories?UC Regents Fall 2005 © UCBCS 152 L8: Pipelining IIStructural hazard solution: concurrent useIRIRBAMInstr Fetch“IF” Stage“ID/RF” StageDecode & Reg Fetch1 2“EX” StageExecutionIRYM3IRR“MEM” StageMemoryWE, MemToReg4WB5WriteBackMux,LogicID and WB stages use register file in same clock cycleUC Regents Fall 2005 © UCBCS 152 L8: Pipelining IIData Hazards: 3 Types (RAW, WAR, WAW)Several pipeline stages read or write thesame data location in an incompatible way.Read After Write (RAW) hazards.Instruction I2 expects to read a datavalue written by an earlier instruction,but I2 executes “too early” and readsthe wrong copy of the data.Note “data value”, not “register”. Data hazards are possible for any architected state (such as main memory). In practice, main memory hazard avoidance is the job of the memory system.UC Regents Fall 2005 © UCBCS 152 L8: Pipelining IIRecall from last lecture: RAW exampleIRIRIRBAMInstr FetchStage #1 Stage #2Stage #3Decode & Reg FetchADD R4,R3,R2OR R5,R4,R2R4 not written yet ...... wrong value of R4 fetched from RegFile, contract with programmer broken! Oops!ADD R4,R3,R2OR R5,R4,R2Sample programThis is what we mean when we say Read After Write (RAW) HazardUC Regents Fall 2005 © UCBCS 152 L8: Pipelining IIData Hazards: 3 Types (RAW, WAR, WAW)Write After Read (WAR) hazards. Instruction I2 expects to write over a data value after an earlier instruction I1 reads it. But instead, I2 writes too early, and I1 sees the new value.Write After Write (WAW) hazards. Instruction I2 writes over data an earlier instruction I1 also writes. But instead, I1 writes after I2, and the final data value is incorrect.WAR and WAW not possible in our 5-stage pipeline. But are possible in other pipeline designs.UC Regents Fall 2005 © UCBCS 152 L8: Pipelining III1:I2:I3:I4:I5:t1 t2 t3 t4 t5 t6 t7 t8Time:InstI6:Control Hazards: A taken branch/jumpIRIRIF (Fetch) ID (Decode) EX (ALU)IRIRMEMWBBEQ R4,R3,25SUB R1,R9,R8AND R6,R5,R4I1:I2:I3:Sample Program(ISA w/o branch delay slot)IF IDIFEXIDIFMEM WBEX stage computes if branch is takenNote: with branch delay slot, I2 MUST complete, I3 MUST NOT complete.If branch is taken, these instructions MUST NOT complete!UC Regents Fall 2005 © UCBCS 152 L8: Pipelining IIHazards RecapStructural HazardsData Hazards (RAW, WAR, WAW)Control Hazards (taken branches and jumps)On each clock cycle, we must detect the presenceof all of these hazards, and resolve them before they break the “contract with the programmer”.UC Regents Fall 2005 © UCBCS 152 L8: Pipelining IIAdministrivia: Upcoming deadlines ...Thursday 9/29: At 11:59 PM via email:Lab 2 peer evaluations, and Lab 3 preliminary design document due.Monday 9/26: Lab 2 final report due via the submit program, 11:59 PM.Friday 9/23: “Xilinx Checkoff”, in section. For non-150 students, “150 Lab Lecture 4”, 2-3 PM, 125 Cory.Lab 3 now available on the web siteUC Regents Fall 2005 © UCBCS 152 L8: Pipelining IICrunch Week: Homework, Midterm, LabHW graded on effortMidterm two weeks from today, in evening, no class that day.Thursday review session.Will cover format, material, and ground rules for test.Lab 3 design doc, checkoffs, later in
View Full Document
Unlocking...