Slide 1Last time in Lecture 4Control HazardsOpcode Decoding Bubble (assuming no branch delay slots for now)Speculate next address is PC+4Pipelining JumpsJump Pipeline DiagramsPipelining Conditional BranchesPipelining Conditional BranchesPipelining Conditional BranchesNew Stall SignalControl Equations for PC and IR MuxesBranch Pipeline Diagrams (resolved in execute stage)Reducing Branch Penalty (resolve in decode stage)Branch Delay Slots (expose control hazard to software)Branch Pipeline Diagrams (branch delay slot)Why an Instruction may not be dispatched every cycle (CPI>1)Iron Law with Software-Visible NOPsCS152 AdministriviaExceptions: altering the normal flow of controlCauses of ExceptionsHistory of Exception HandlingDYSEAC, first mobile computer!Asynchronous Interrupts: invoking the interrupt handlerMIPS Interrupt Handler CodeSynchronous ExceptionException Handling 5-Stage PipelineException Handling 5-Stage PipelineException Handling 5-Stage PipelineSpeculating on ExceptionsException Pipeline DiagramAcknowledgementsFebruary 2, 2011 CS152, Spring 2011CS 152 Computer Architecture and Engineering Lecture 5 - Pipelining IIKrste AsanovicElectrical Engineering and Computer SciencesUniversity of California at Berkeleyhttp://www.eecs.berkeley.edu/~krstehttp://inst.eecs.berkeley.edu/~cs152February 2, 2011 CS152, Spring 20112Last time in Lecture 4•Pipelining increases clock frequency, while growing CPI more slowly, hence giving greater performance Time = Instructions Cycles Time Program Program * Instruction * CycleReduces because fewer logic gates on critical paths between flip-flopsIncreases because of pipeline bubbles•Pipelining of instructions is complicated by HAZARDS:–Structural hazards (two instructions want same hardware resource)–Data hazards (earlier instruction produces value needed by later instruction)–Control hazards (instruction changes control flow, e.g., branches or exceptions)•Techniques to handle hazards:–Interlock (hold newer instruction until older instructions drain out of pipeline and write back results)–Bypass (transfer value from older instruction to newer instruction as soon as available somewhere in machine)–Speculate (guess effect of earlier instruction)February 2, 2011 CS152, Spring 20113Control Hazards•What do we need to calculate next PC?–For Jumps» Opcode, offset and PC–For Jump Register»Opcode and Register value–For Conditional Branches»Opcode, PC, Register (for condition), and offset–For all other instructions»Opcode and PC•have to know it’s not one of above!February 2, 2011 CS152, Spring 20114timet0 t1 t2 t3 t4 t5 t6 t7 . . . .(I1) r1 (r0) + 10 IF1ID1EX1MA1WB1(I2) r3 (r2) + 17 IF2IF2ID2EX2MA2WB2(I3) IF3IF3ID3EX3MA3WB3(I4) IF4IF4ID4EX4MA4WB4timet0 t1 t2 t3 t4 t5 t6 t7 . . . .IF I1nop I2nop I3nop I4ID I1nop I2nop I3nop I4EX I1nop I2nop I3nop I4MA I1nop I2nop I3nop I4WB I1nop I2nop I3nop I4Opcode Decoding Bubble(assuming no branch delay slots for now)Resource Usagenop pipeline bubbleFebruary 2, 2011 CS152, Spring 20115Speculate next address is PC+4I1096ADD I2100J 304I3104ADDI4304ADDkillA jump instruction kills (not stalls)the following instructionstallHow?I2I1104IRIRPCaddrinstInstMemory0x4AddnopIREMAddJump?PCSrc (pc+4 / jabs / rind/ br)February 2, 2011 CS152, Spring 20116Pipelining JumpsI1096ADD I2100J 304I3104ADDI4304ADDkillI2I1104stallIRIRPCaddrinstInstMemory0x4AddnopIREMAddJump?PCSrc (pc+4 / jabs / rind/ br)IRSrcD = Case opcodeDJ, JAL nop... IMTo kill a fetched instruction -- Insert a mux before IRAny interaction between stall and jump?nopIRSrcDI2I1304nopFebruary 2, 2011 CS152, Spring 20117timet0 t1 t2 t3 t4 t5 t6 t7 . . . .IF I1I2I3I4I5ID I1I2nop I4I5EX I1I2nop I4I5MA I1I2nop I4I5WB I1I2nop I4I5Jump Pipeline Diagramstimet0 t1 t2 t3 t4 t5 t6 t7 . . . .(I1) 096: ADD IF1ID1EX1MA1WB1(I2) 100: J 304 IF2ID2EX2MA2WB2(I3) 104: ADD IF3nop nop nop nop(I4) 304: ADD IF4ID4EX4MA4WB4Resource Usagenop pipeline bubbleFebruary 2, 2011 CS152, Spring 20118Pipelining Conditional BranchesI1096ADD I2100BEQZ r1 +200I3104ADD108 …I4304ADDBEQZ?I2I1104stallIRIRPCaddrinstInstMemory0x4AddnopIREMAddPCSrc (pc+4 / jabs / rind / br)nopIRSrcDBranch condition is not known until the execute stage what action should be taken in thedecode stage ?AYALUzero?February 2, 2011 CS152, Spring 20119Pipelining Conditional BranchesI1096ADD I2100BEQZ r1 +200I3104ADD108 …I4304ADDstallIRIRPCaddrinstInstMemory0x4AddnopIREMAddPCSrc (pc+4 / jabs / rind / br)nopIRSrcDAYALUzero?If the branch is taken- kill the two following instructions- the instruction at the decode stage is not valid stall signal is not validI2I1108I3BEQZ??February 2, 2011 CS152, Spring 201110Pipelining Conditional BranchesI1096ADD I2100BEQZ r1 +200I3104ADD108 …I4304ADDstallIRIRPCaddrinstInstMemory0x4AddnopIREMPCSrc (pc+4/jabs/rind/br)nopAYALUzero?I2I1108I3BEQZ?Jump?IRSrcDIRSrcEIf the branch is taken- kill the two following instructions- the instruction at the decode stage is not valid stall signal is not validAddPCFebruary 2, 2011 CS152, Spring 201111New Stall Signalstall = ( ((rsD =wsE).weE + (rsD =wsM).weM + (rsD =wsW).weW).re1D + ((rtD =wsE).weE + (rtD =wsM).weM + (rtD =wsW).weW).re2D ) . !((opcodeE=BEQZ).z + (opcodeE=BNEZ).!z)Don’t stall if the branch is taken. Why?Instruction at the decode stage is invalidFebruary 2, 2011 CS152, Spring 201112Control Equations for PC and IR MuxesPCSrc = Case opcodeEBEQZ.z, BNEZ.!z br... Case opcodeD J, JAL jabs JR, JALR rind ... pc+4IRSrcD = Case opcodeEBEQZ.z, BNEZ.!z nop... Case opcodeD J, JAL, JR, JALR nop ... IMGive priority to the older instruction,i.e., execute-stage instructionover decode-stage instructionIRSrcE = Case opcodeEBEQZ.z, BNEZ.!z nop... stall.nop + !stall.IRDFebruary 2, 2011 CS152, Spring 201113timet0 t1 t2 t3 t4 t5 t6 t7 . . . .IF I1I2I3I4I5ID I1I2I3 nop I5EX I1I2nop nop I5MA I1I2nop nop I5WB I1I2nop nop I5Branch Pipeline Diagrams(resolved in execute stage)timet0 t1 t2 t3 t4 t5 t6 t7 . . . .(I1) 096: ADD IF1ID1EX1MA1WB1(I2) 100: BEQZ +200 IF2ID2EX2MA2WB2(I3) 104: ADD IF3ID3 nop nop nop(I4) 108: IF4nop nop nop nop(I5) 304: ADD IF5ID5EX5MA5WB5Resource Usagenop pipeline bubbleFebruary 2, 2011 CS152, Spring 201114•One pipeline bubble can be removed if an extra
View Full Document
Unlocking...