PipeliningPipeline performancePipeline applied to instruction executionPipeline parallelismPipeline implementation requirementsExamples of what to store in pipeline registersPipeline data path (highly abstracted)Pipeline data path (a little less abstracted)HazardsNotation (cf. Figure 6.18)Tracing one instruction through all 5 stages (St 1)Tracing one instruction through all 5 stages (St 2)Tracing one instruction through all 5 stages (St 3)Stage 3 (ct’d)Tracing one instruction through all 5 stages (St 4)Tracing one instruction through all 5 stages (St 5)Summary of requirements of ideal pipeline data path01/13/19 CSE378 Pipelining 1Pipelining•Basic concept of assembly line–Split a job A into n sequential subjobs (A1,A2,…,An) with each Ai taking approximately the same time–Each subjob is processed by a different substation (or resource) or, equivalently, passes through a series of stages–Subjobs of different jobs overlap their execution, i.e., when subjob A1 of job A is finished in stage 1, subjob A2 of job A will start executing in stage 2 while subjob B1 of job B will start executing in stage 101/13/19 CSE378 Pipelining 2Pipeline performance•Latency of a single job can be longer–because each stage takes as long as the longest one, say tmax–because all jobs have to go through all stages even if they don’t do anything in one of the stages•Throughput is enhanced–Ideally, in steady state, one job completes every tmax rather than after (t1 + t2 + ... tn ) •In the ideal case (all ti are the same) throughput is n times better if there are n stages. But :–Execution time of a job could take less than n stages–We assume that the pipeline can be kept full all the time01/13/19 CSE378 Pipelining 3Pipeline applied to instruction execution•Multiple cycle implementation•In pipeline modeIfetch Dec ALU Mem WbIfetch Dec ALU Mem WbInstr. iInstr. i+1Idle timeIfetch Dec ALU Mem WbIfetch Dec ALU Mem WbIfetch Dec ALU Mem WbInstr. iInstr. i+1Instr. i+201/13/19 CSE378 Pipelining 4Pipeline parallelism•Note that at any given time after the pipeline is full, we have 5 instructions in progress; however each individual instruction has a longer latencyIfetch Dec ALU Mem WbIfetch Dec ALU Mem WbIfetch Dec ALU Mem WbIfetch Dec ALU Mem WbIfetch Dec ALU Mem WbIfetch Dec ALU Mem Wb5 instructions in progress t t+1 t +2 t+3 t+4 t+5 t +6 t+7 t+8 t+9Instr. iInstr. i+1Instr. i+2Instr. i+3Instr. i+4Instr. i+501/13/19 CSE378 Pipelining 5Pipeline implementation requirements•5 stages are active on 5 different instructions•Thus all the resources needed for single cycle implementation will be required (at least)•All stages are independent and isolated from each other. This implies that all information gathered at stage i needed in stages i+1, i+2 etc…must be kept and passed from stage to stage.•For that purpose we will use “pipeline registers” (or flip-flops or latches) between each stage01/13/19 CSE378 Pipelining 6Examples of what to store in pipeline registers•The following is not an exhaustive list (just a sample)•The register number where the result will be stored–Known at stage 2; needed at stage 5•The register number of the data containing the contents of a “store” as well as the contents of that register–Known at stage 2; needed at stage 4•The immediate value–Known at stage 2; needed at stage 3•The updated PC (we’ll see why later)•etc ..01/13/19 CSE378 Pipelining 7Pipeline data path (highly abstracted)IF ID EX Mem WBIF/ID ID/EX EX/Mem Mem/WB01/13/19 CSE378 Pipelining 8Pipeline data path (a little less abstracted)•Let’s look back at Fig. 5.17 (Single cycle implementation) and see where the pipeline registers should be put and what additional resources, if any, are needed.01/13/19 CSE378 Pipelining 9Hazards•Hazards are what prevents the pipeline to be ideal•Three types of hazards:–Structural where two instructions at different stages want to use the same resource. Solved by using more resources (e.g., instruction and data memory; several ALU’s)–Data hazards when an instruction in the pipeline is dependent on another instruction still in the pipeline. Some of these hazards will be resolved by bypassing and some will result in the pipeline being stalled–Control hazards which happens on a successful branch (or procedure call/return). We’ll investigate several techniques to take care of these hazards.01/13/19 CSE378 Pipelining 10Notation (cf. Figure 6.18)•Pipeline registers keeping information between stages labeled by the names of the stages they connect (IF/ID, ID/EX, etc.)•Information flows from left to right except for–writing the result register (potential for data hazard)–modifying the PC (potential for control hazard)01/13/19 CSE378 Pipelining 11Tracing one instruction through all 5 stages (St 1)•Stage 1: Instruction fetch and increment PC (same for all instructions)–Instruction fetched from instruction memory. The instruction will be needed in subsequent stages. Hence stored in IF/ID•recall (i) the IR register in multiple cycle implementation, and (ii) that in single cycle implementation we had two “memories”, one for instruction and one for data–PC PC + 4•The incremented PC will be needed to fetch the next instruction at the next cycle but it will also be needed if we have to do branch target computation. Hence incremented PC saved in IF/ID–Resources needed: Instruction memory and ALU–IF/ID contains instruction and incremented PC01/13/19 CSE378 Pipelining 12Tracing one instruction through all 5 stages (St 2)•Stage 2: Instruction decode and register read (same for all instructions)–We save in ID/EX everything that can be needed in next stages:•The instruction and the incremented PC (from IF/ID) (e.g., function bits can be needed, the name of the register to be written etc.)•The contents of registers rs and rt (recall registers A and B)•The sign extended immediate field (for imm. Inst., load/store, branch)•Control lines et-ups. We’ll deal with control later•Note that we do not compute the branch target address here (why?). –Resources needed: register file, control unit–ID/EX
View Full Document
Unlocking...