CS 152 Computer Architecture and Engineering Lecture 10 Complex Pipelines Out of Order Issue Register Renaming Krste Asanovic Electrical Engineering and Computer Sciences University of California at Berkeley http www eecs berkeley edu krste http inst eecs berkeley edu cs152 February 28 2011 CS152 Spring 2011 Last time in Lecture 9 Modern page based virtual memory systems provide Translation Protection Virtual memory Translation and protection information stored in page tables held in main memory Translation and protection information cached in translation lookaside buffer TLB to provide single cycle translation protection check in common case Virtual memory interacts with cache design Physical cache tags require address translation before tag lookup or use untranslated offset bits to index cache Virtual tags do not require translation before cache hit miss determination but need to be flushed or with ASIDCS152 to cope with February 28 extended 2011 Spring 2011context swaps Also 2 Complex Pipelining Motivation Pipelining becomes complex when we want high performance in the presence of Long latency or partially pipelined floatingpoint units Memory systems with variable access time Multiple arithmetic and memory units February 28 2011 CS152 Spring 2011 3 Floating Point Unit FPU Much more hardware than an integer unit Single cycle FPU is a bad idea why it is common to have several FPU s it is common to have different types of FPU s Fadd Fmul Fdiv an FPU may be pipelined partially pipelined or not pipelined To operate several FPU s concurrently the FP register file needs to have more read and write ports February 28 2011 CS152 Spring 2011 4 Functional Unit Characteristics fully pipelined partially pipelined 1cyc1cyc1cyc 2 cyc 2 cyc Functional units have internal pipeline registers operands are latched when an instruction enters a functional unit following instructions are able to write register file during a long latency operation February 28 2011 CS152 Spring 2011 5 Floating Point ISA Interaction between the floating point datapath and the integer datapath is determined largely by the ISA MIPS ISA separate register files for FP and Integer instructions the only interaction is via a set of move instructions some ISA s don t even permit this separate load store for FPR s and GPR s but both use GPR s for address calculation separate conditions for branches FP branches are defined in terms of condition codes February 28 2011 CS152 Spring 2011 6 Realistic Memory Systems Common approaches to improving memory performance caches single cycle except in case of a miss stall interleaved memory multiple memory accesses bank conflicts split phase memory operations separate memory request from response out of order responses Latency of access to the main memory is usually much greater than one cycle and often unpredictable Solving this problem is a central issue in computer architecture February 28 2011 CS152 Spring 2011 7 Issues in Complex Pipeline Control Structural conflicts at the execution stage if some FPU or memory unit is not pipelined and takes more than one cycle Structural conflicts at the write back stage due to variable latencies of different functional units Out of order write hazards due to variable latencies of different functional units How to handle exceptions ALU IF ID Issue GPRs FPRs Mem WB Fadd Fmul Fdiv February 28 2011 CS152 Spring 2011 8 Complex In Order Pipeline Inst PC Mem D Decode Delay writeback so all operations have same latency to W stage GPRs FPRs X1 X1 Write ports never oversubscribed one inst in one inst out every cycle Stall pipeline on long latency operations e g divides cache misses Handle exceptions in order at How to prevent commit point increased writeback latency from slowing down single cycle integer operations Bypassing February 28 2011 Data X2 Mem X3 W X2 FAdd X3 W X2 FMul X3 Unpipelined divider FDiv X2 CS152 Spring 2011 Commit Point X3 9 In Order Superscalar Pipeline Inst 2 PC D Mem Dual Decode GPRs Fetch two instructions per cycle issue both simultaneously if one is integer memory and other is floating point Inexpensive way of increasing throughput examples include Alpha 21064 1992 MIPS R5000 series 1996 Same idea can be extended to wider issue by duplicating functional units e g 4 issue UltraSPARC Alpha 21164 but regfile ports and bypassing costs grow quickly February 28 2011 FPRs X1 X1 Data X2 Mem X3 W X2 FAdd X3 W X2 FMul X3 Unpipelined FDiv X2 divider X3 CS152 Spring 2011 Commit Point 10 Types of Data Hazards Consider executing a sequence of rk ri op rj type of instructions Data dependence r3 r1 op r2 r5 r3 op r4 Read after Write RAW hazard Anti dependence r3 r1 op r2 r1 r4 op r5 Write after Read WAR hazard Output dependence r3 r1 op r2 r3 r6 op r7 February 28 2011 Write after Write WAW hazard CS152 Spring 2011 11 Register vs Memory Dependence Data hazards due to register operands can be determined at the decode stage but data hazards due to memory operands can be determined only after computing the effective address store load M r1 disp1 r2 r3 M r4 disp2 Does r1 disp1 r4 disp2 February 28 2011 CS152 Spring 2011 12 Data Hazards An Example I1 DIVD f6 f6 f4 I2 LD I3 MULTD f0 f2 f4 I4 DIVD f8 f6 f2 I5 SUBD f10 I6 ADDD f6 f8 f2 f2 45 r3 f0 f6 RAW Hazards WAR Hazards WAW Hazards February 28 2011 CS152 Spring 2011 13 Instruction Scheduling I1 DIVD I2 LD I3 MULTD f0 f2 f4 I4 DIVD f8 f6 f2 I5 SUBD f10 f0 f6 I6 ADDD f6 f8 f2 Valid orderings in order I1 I2 out of order out of order February 28 2011 I3 f6 f6 f4 I1 f2 45 r3 I4 I2 I3 I4 I5 I5 I6 I2 I1 I3 I4 I5 I6 I1 I2 I3 I5 I4 I6 CS152 Spring 2011 I6 14 Out of order Completion In order Issue in order comp I1 DIVD I2 LD I3 MULTD f0 f2 f4 3 I4 DIVD f8 f6 f2 4 I5 SUBD f10 f0 f6 1 I6 ADDD f6 f8 f2 1 1 2 out of order comp 1 2 February 28 2011 f6 f6 f4 Latency 4 f2 45 r3 1 2 3 4 1 3 5 4 6 5 6 2 3 1 4 3 5 5 4 6 6 CS152 Spring 2011 15 Complex Pipeline ALU IF ID Issue GPR s FPR s Mem WB Fadd Fmul Can we solve write hazards without equalizing all pipeline depths and without bypassing February 28 2011 Fdiv CS152 Spring 2011 16 When is it Safe to Issue an Instruction Suppose a data structure keeps track of all the instructions in all the functional units The following checks need to be made before the Issue stage can dispatch an instruction Is the required function unit available Is the input data available RAW Is it safe to write the destination WAR WAW Is there a structural conflict at the WB stage February 28 2011
View Full Document
Unlocking...