CS 152 Computer Architecture and Engineering Lecture 8 Pipelining II 2005 9 22 John Lazzaro www cs berkeley edu lazzaro TAs David Marquardt and Udam Saini www inst eecs berkeley edu cs152 CS 152 L8 Pipelining II UC Regents Fall 2005 UCB From First Class The Architect s Contract To the program it appears that instructions execute in the correct order defined by the ISA As each instruction completes the machine state regs mem appears to the program to obey the ISA What the machine actually does is up to the hardware designers as long as the contract is kept The primary challenge of 152 CPU CS 152 L8 Pipelining II UC Regents Fall 2005 UCB Last Time A 5 stage pipelined CPU 1 2 IF Stage Instr ID RF Stage Decode Reg Fetch Fetch IR 3 5 4 EX Stage Executio n IR IR A Y M M MEM WB Write Stage Memory Back WE MemToReg IR Mux Logic R B CS 152 L8 Pipelining II UC Regents Fall 2005 UCB Today Hazards Visualizing pipelines to evaluate hazard detection and resolution A taxonomy of pipeline hazards A tool kit for hazard resolution Tuesday We apply this knowledge to design a pipelined MIPS CPU that obeys the contract with the programmer CS 152 L8 Pipelining II UC Regents Fall 2005 UCB Reminder Do the Reading The book presentation of pipelined processors is sufficient to do Lab 3 These lectures are not The lectures are a gentle introduction to prepare you to read the book CS 152 L8 Pipelining II UC Regents Fall 2005 UCB Visualizing Pipelines CS 152 L8 Pipelining II UC Regents Fall 2005 UCB Pipeline Representation 1 Timeline IF Fetch ID Decode IR EX ALU IR MEM WB IR IR Good for visualizing pipeline fills Sample Program Time t1 t2 t3 Inst ADD R4 R3 R2 I1 IF ID EX I1 I2 AND R6 R5 R4 I2 IF ID SUB R1 R9 R8 I3 IF I3 XOR R3 R2 R1 I4 I4 OR R7 R6 R5 I5 I5 Pipeline I6 is full CS 152 L8 Pipelining II t4 t5 MEM EX ID IF WB MEM EX ID IF t6 t7 t8 WB MEM EX ID IF WB MEM EX ID WB MEM EX UC Regents Fall 2005 UCB Representation 2 Resource Usage IF Fetch ID Decode IR EX ALU IR MEM WB IR IR Good for visualizing pipeline stalls Sample Program Time t1 Stage ADD R4 R3 R2 I1 I1 IF I2 AND R6 R5 R4 ID SUB R1 R9 R8 I3 EX XOR R3 R2 R1 I4 MEM OR R7 R6 R5 I5 WB CS 152 L8 Pipelining II t2 t3 t4 t5 t6 t7 t8 I2 I1 I3 I2 I1 I4 I3 I2 I1 I5 I4 I3 I2 I1 I6 I5 I4 I3 I2 I7 I6 I5 I4 I3 I8 I7 I6 I5 I4 Pipeline is full UC Regents Fall 2005 UCB Hazard Taxonomy CS 152 L8 Pipelining II UC Regents Fall 2005 UCB Structural Hazards Several pipeline stages need to use the same hardware resource at the same time Solution 1 Add extra copies of the resource only works sometime Solution 2 Change resource so that it can handle concurrent use Solution 3 Stages take turns by stalling parts of the pipeline CS 152 L8 Pipelining II UC Regents Fall 2005 UCB Structural hazard solution 2 memories 1 2 IF Stage Instr ID RF Stage Decode Reg Fetch Fetch IR 3 5 4 EX Stage Executio n IR IR A Y M M MEM WB Write Stage Memory Back WE MemToReg IR Mux Logic B CS 152 L8 Pipelining II R What if we merged Data and Instr memories UC Regents Fall 2005 UCB Structural hazard solution concurrent use 1 2 IF Stage Instr ID RF Stage Decode Reg Fetch Fetch IR 3 5 4 EX Stage Executio n IR IR A Y M M MEM WB Write Stage Memory Back WE MemToReg IR Mux Logic B CS 152 L8 Pipelining II R ID and WB stages use register file in same clock cycle UC Regents Fall 2005 UCB Data Hazards 3 Types RAW WAR WAW Several pipeline stages read or write the same data location in an incompatible way Read After Write RAW hazards Instruction I2 expects to read a data value written by an earlier instruction but I2 executes too early and reads the 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 CS 152 L8 Pipelining II UC Regents Fall 2005 UCB Recall from last lecture RAW example Stage 1 Instr Fetch Sample program ADD R4 R3 R2 OR R5 R4 R2 Stage 3 Stage 2 IR Decode Reg Fetch OR R5 R4 R2 wrong value of R4 fetched from RegFile contract with programmer broken Oops IR IR R4 not written yet A M B CS 152 L8 Pipelining II ADD R4 R3 R2 This is what we mean when we say Read After Write RAW UC Regents Fall 2005 UCB Data 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 5stage pipeline But are possible in other pipeline designs CS 152 L8 Pipelining II UC Regents Fall 2005 UCB Control Hazards A taken branch jump IF Fetch ID Decode IR Sample Program ISA w o branch delay slot I1 BEQ R4 R3 25 I2 AND R6 R5 R4 I3 SUB R1 R9 R8 CS 152 L8 Pipelining II EX ALU IR MEM IR WB IR Note with branch delay slot I2 MUST complete I3 MUST NOT complete Time t1 t2 t3 t4 t5 t6 t7 t8 Inst EX stage IF ID EX MEM WB I1 compute I2 IF ID s if IF I3 branch I4 is taken If branch is taken I5 these instructions I6 MUST NOT UC Regents Fall 2005 UCB Hazards Recap Structural Hazards Data Hazards RAW WAR WAW Control Hazards taken branches and jumps On each clock cycle we must detect the presence of all of these hazards and resolve them before they break the contract with the programmer CS 152 L8 Pipelining II UC Regents Fall 2005 UCB Administrivia Upcoming deadlines Friday 9 23 Xilinx Checkoff in section For non 150 students 150 Lab Lecture 4 2 3 PM 125 Cory Monday 9 26 Lab 2 final report due via the submit program 11 59 PM Lab 3 now available on the web site Thursday 9 29 At 11 59 PM via email Lab 2 peer evaluations and Lab 3 preliminary design document due CS 152 L8 Pipelining II UC Regents Fall 2005 UCB Crunch Week Homework Midterm Lab HW graded on effort Thursday review Will cover format session material and ground rules for test Midterm two weeks from today in evening no class …
View Full Document
Unlocking...