DOC PREVIEW
UT CS 352H - MIPS Pipelined Implementation

This preview shows page 1-2-17-18-19-36-37 out of 37 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 37 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 37 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 37 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 37 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 37 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 37 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 37 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 37 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

CS352H: Computer Systems ArchitectureMIPS PipelinePipeline PerformanceSlide 4Pipeline SpeedupPipelining and ISA DesignHazardsStructure HazardsData HazardsForwarding (aka Bypassing)Load-Use Data HazardCode Scheduling to Avoid StallsControl HazardsStall on BranchBranch PredictionMIPS with Predict Not TakenMore-Realistic Branch PredictionPipeline SummaryMIPS Pipelined DatapathPipeline registersPipeline OperationIF for Load, Store, …ID for Load, Store, …EX for LoadMEM for LoadWB for LoadCorrected Datapath for LoadEX for StoreMEM for StoreWB for StoreMulti-Cycle Pipeline DiagramSlide 32Single-Cycle Pipeline DiagramPipelined Control (Simplified)Pipelined ControlSlide 36Concluding RemarksUniversity of Texas at Austin CS352H - Computer Systems Architecture Fall 2009 Don FussellCS352H: Computer Systems ArchitectureTopic 8: MIPS Pipelined ImplementationSeptember 29, 2009University of Texas at Austin CS352H - Computer Systems Architecture Fall 2009 Don Fussell 2MIPS PipelineFive stages, one step per stageIF: Instruction fetch from memoryID: Instruction decode & register readEX: Execute operation or calculate addressMEM: Access memory operandWB: Write result back to registerUniversity of Texas at Austin CS352H - Computer Systems Architecture Fall 2009 Don Fussell 3Pipeline PerformanceAssume time for stages is100ps for register read or write200ps for other stagesCompare pipelined datapath with single-cycle datapathInstr Instr fetch Register readALU op Memory accessRegister writeTotal timelw 200ps 100 ps 200ps 200ps 100 ps 800pssw 200ps 100 ps 200ps 200ps 700psR-format 200ps 100 ps 200ps 100 ps 600psbeq 200ps 100 ps 200ps 500psj 200ps 200psUniversity of Texas at Austin CS352H - Computer Systems Architecture Fall 2009 Don Fussell 4Pipeline PerformanceSingle-cycle (Tc= 800ps)Pipelined (Tc= 200ps)University of Texas at Austin CS352H - Computer Systems Architecture Fall 2009 Don Fussell 5Pipeline SpeedupIf all stages are balancedi.e., all take the same timeTime between instructionspipelined = Time between instructionsnonpipelinedNumber of stagesIf not balanced, speedup is lessSpeedup due to increased throughputLatency (time for each instruction) does not decreaseUniversity of Texas at Austin CS352H - Computer Systems Architecture Fall 2009 Don Fussell 6Pipelining and ISA DesignMIPS ISA designed for pipeliningAll instructions are 32-bitsEasier to fetch and decode in one cyclec.f. x86: 1- to 17-byte instructionsFew and regular instruction formatsCan decode and read registers in one stepLoad/store addressingCan calculate address in 3rd stage, access memory in 4th stageAlignment of memory operandsMemory access takes only one cycleUniversity of Texas at Austin CS352H - Computer Systems Architecture Fall 2009 Don Fussell 7HazardsSituations that prevent starting the next instruction in the next cycleStructure hazardsA required resource is busyData hazardNeed to wait for previous instruction to complete its data read/writeControl hazardDeciding on control action depends on previous instructionUniversity of Texas at Austin CS352H - Computer Systems Architecture Fall 2009 Don Fussell 8Structure HazardsConflict for use of a resourceIn MIPS pipeline with a single memoryLoad/store requires data accessInstruction fetch would have to sta ll for that cycleWould cause a pipeline “bubble”Hence, pipelined datapaths require separate instruction/data memoriesOr separate instruction/data cachesUniversity of Texas at Austin CS352H - Computer Systems Architecture Fall 2009 Don Fussell 9Data HazardsAn instruction depends on completion of data access by a previous instructionadd $s0, $t0, $t1sub $t2, $s0, $t3University of Texas at Austin CS352H - Computer Systems Architecture Fall 2009 Don Fussell 10Forwarding (aka Bypassing)Use result when it is computedDon’t wait for it to be stored in a registerRequires extra connections in the datapathUniversity of Texas at Austin CS352H - Computer Systems Architecture Fall 2009 Don Fussell 11Load-Use Data HazardCan’t always avoid stalls by forwardingIf value not computed when neededCan’t forward backward in time!University of Texas at Austin CS352H - Computer Systems Architecture Fall 2009 Don Fussell 12Code Scheduling to Avoid StallsReorder code to avoid use of load result in the next instructionC code for A = B + E; C = B + F;lw $t1, 0($t0)lw $t2, 4($t0)add $t3, $t1, $t2sw $t3, 12($t0)lw $t4, 8($t0)add $t5, $t1, $t4sw $t5, 16($t0)stallstalllw $t1, 0($t0)lw $t2, 4($t0)lw $t4, 8($t0)add $t3, $t1, $t2sw $t3, 12($t0)add $t5, $t1, $t4sw $t5, 16($t0)11 cycles13 cyclesUniversity of Texas at Austin CS352H - Computer Systems Architecture Fall 2009 Don Fussell 13Control HazardsBranch determines flow of controlFetching next instruction depends on branch outcomePipeline can’t always fetch correct instructionStill working on ID stage of branchIn MIPS pipelineNeed to compare registers and compute target early in the pipelineAdd hardware to do it in ID stageUniversity of Texas at Austin CS352H - Computer Systems Architecture Fall 2009 Don Fussell 14Stall on BranchWait until branch outcome determined before fetching next instructionUniversity of Texas at Austin CS352H - Computer Systems Architecture Fall 2009 Don Fussell 15Branch PredictionLonger pipelines can’t readily determine branch outcome earlyStall penalty becomes unacceptablePredict outcome of branchOnly stall if prediction is wrongIn MIPS pipelineCan predict branches not takenFetch instruction after branch, with no delayUniversity of Texas at Austin CS352H - Computer Systems Architecture Fall 2009 Don Fussell 16MIPS with Predict Not TakenPrediction correctPrediction incorrectUniversity of Texas at Austin CS352H - Computer Systems Architecture Fall 2009 Don Fussell 17More-Realistic Branch PredictionStatic branch predictionBased on typical branch behaviorExample: loop and if-statement branchesPredict backward branches takenPredict forward branches not takenDynamic branch predictionHardware measures actual branch behaviore.g., record recent history of each branchAssume future behavior will continue the trendWhen wrong, stall while re-fetching, and update historyUniversity of Texas at Austin CS352H - Computer Systems Architecture Fall


View Full Document
Download MIPS Pipelined Implementation
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view MIPS Pipelined Implementation and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view MIPS Pipelined Implementation 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?