Question? Leave a message!




Complex Pipelining

Complex Pipelining
1 Complex Pipelining Arvind Computer Science and Artificial Intelligence Laboratory M.I.T. Based on the material prepared by Arvind and Krste Asanovic 6.823 L11-2 Arvind Complex Pipelining: Motivation Pipelining becomes complex when we want high performance in the presence of • Long latency or partially pipelined floating-point units • Multiple function and memory units • Memory systems with variable access time October 19, 2005 6.823 L11-3 Arvind 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 October 19, 2005 6.823 L11-4 Arvind Floating Point Unit Much more hardware than an integer unit Single-cycle floating point unit is a bad idea - why? • it is common to have several floating point units • 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 register file needs to have more read and write ports October 19, 2005 6.823 L11-5 Arvind Function Unit Characteristics fully pipelined 1cyc 1cyc1cyc busy accept partially pipelined 2 cyc 2 cyc accept busy Function units have internal pipeline registers ⇒ operands are latched when an instruction enters a function unit ⇒ inputs to a function unit (e.g., register file) can change during a long latency operation October 19, 2005 6.823 L11-6 Arvind Realistic Memory Systems 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 Common approaches to improving memory performance • separate instruction and data memory ports ⇒ no self-modifying code •caches single cycle except in case of a miss ⇒ stall • interleaved memory multiple memory accesses ⇒ bank conflicts • split-phase memory operations ⇒ out-of-order responses October 19, 2005 6.823 L11-7 Arvind Complex Pipeline Structure ALU Mem IF ID Issue WB Fadd GPR’s FPR’s Fmul Fdiv October 19, 2005 6.823 L11-8 Arvind Complex Pipeline Control Issues • Structural conflicts at the write-back stage due to variable latencies of different function units • Structural conflicts at the execution stage if some FPU or memory unit is not pipelined and takes more than one cycle • Out-of-order write hazards due to variable latencies of different function units • How to handle exceptions? October 19, 2005 6.823 L11-9 Arvind Complex In-Order Pipeline Data Inst. Decode GPRs PC D X1 X2 X3 W + Mem Mem • Delay writeback so all operations have same FPRs X1 X2 X3 W Fadd latency to W stage – Write ports never oversubscribed (one inst. Commit in & one inst. out every cycle) Point X2 X3 Fmul How to prevent increased writeback latency from Unpipelined slowing down single cycle divider integer operations? FDiv X2 X3 Bypassing October 19, 2005 6.823 L11-10 Arvind Complex In-Order Pipeline Data Inst. Decode GPRs PC D X1 X2 X3 W + Mem Mem How should we handle FPRs X1 X2 X3 W Fadd data hazards for very long latency operations? Commit • Stall pipeline on long Point X2 X3 Fmul latency operations, e.g., divides, cache misses • Exceptions handled in program order at commit Unpipelined point divider FDiv X2 X3 October 19, 20056.823 L11-11 Arvind Superscalar In-Order Pipeline Data Inst. 2 Dual GPRs PC D X1 X2 X3 W + Mem Decode Mem • Fetch two instructions per cycle; issue both simultaneously if one is FPRs X1 X2 X3 W Fadd integer/memory and other is floating-point • Inexpensive way of increasing throughput, Commit examples include Alpha Point X2 X3 21064 (1992) & MIPS Fmul R5000 series (1996) • Same idea can be extended to wider issue by Unpipelined duplicating functional units divider (e.g. 4-issue UltraSPARC) FDiv X2 X3 but register file ports and bypassing costs grow quickly October 19, 200512 Dependence Analysis 6.823 L11-13 Arvind Types of Data Hazards Consider executing a sequence of r ← (r ) op (r ) k i j type of instructions Data-dependence r ← (r ) op (r) Read-after-Write 3 1 2 r ← (r ) op (r ) (RAW) hazard 5 3 4 Anti-dependence r ← (r ) op (r) Write-after-Read 3 1 2 r ← (r ) op (r ) (WAR) hazard 1 4 5 Output-dependence r ← (r ) op (r ) Write-after-Write 3 1 2 r ← (r ) op (r ) (WAW) hazard 3 6 7 October 19, 2005 6.823 L11-14 Arvind Detecting Data Hazards Range and Domain of instruction i R(i) = Registers (or other storage) modified by instruction i D(i) = Registers (or other storage) read by instruction i Suppose instruction j follows instruction i in the program order. Executing instruction j before the effect of instruction i has taken place can cause a RAW hazard if R(i) ∩ D(j) ≠ ∅ WAR hazard if D(i) ∩ R(j) ≠ ∅ WAW hazard if R(i) ∩ R(j) ≠ ∅ October 19, 2005 6.823 L11-15 Arvind Register vs. Memory Data 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 M(r ) + disp1 ← (r ) 1 2 load r ← M(r ) + disp2 3 4 Does (r + disp1) = (r + disp2) ? 1 4 October 19, 2005 6.823 L11-16 Arvind Data Hazards: An Example I DIVD f6, f6, f4 1 I LD f2, 45(r3) 2 I MULTD f0, f2, f4 3 I DIVD f8, f6, f2 4 I SUBD f10, f0, f6 5 I ADDD f6, f8, f2 6 RAW Hazards WAR Hazards WAW Hazards October 19, 2005 6.823 L11-17 Arvind Instruction Scheduling I DIVD f6, f6, f4 1 I 1 I LD f2, 45(r3) 2 I MULTD f0, f2, f4 I 3 2 I DIVD f8, f6, f2 4 I 3 I SUBD f10, f0, f6 5 I ADDD f6, f8, f2 I 6 4 Valid orderings: I 5 in-order I I I I I I 1 2 3 4 5 6 out-of-order I I I I I I 2 1 3 4 5 6 I 6 out-of-order I I I I I I 1 2 3 5 4 6 October 19, 2005 6.823 L11-18 Arvind Out-of-order Completion In-order Issue Latency I DIVD f6, f6, f4 4 1 I LD f2, 45(r3) 1 2 I MULTD f0, f2, f4 3 3 I DIVD f8, f6, f2 4 4 I SUBD f10, f0, f6 1 5 I ADDD f6, f8, f2 1 6 in-order comp 1 2 1 2 3 4 3 5 4 6 5 6 out-of-order comp 1 2 2 3 1 4 3 5 5 4 6 6 October 19, 2005 19 Five-minute break to stretch your legs 20 Scoreboard: A Hardware Data Structure to Detect Hazards Dynamically 6.823 L11-21 Arvind CDC 6600 Seymour Cray, 1963 • A fast pipelined machine with 60-bit words – 128 Kword main memory capacity, 32 banks • Ten functional units (parallel, unpipelined) – Floating Point: adder, 2 multipliers, divider Image removed due to – Integer: adder, 2 incrementers, ... copyright restrictions. • Hardwired control (no microcoding) • Dynamic scheduling of instructions using a scoreboard • Ten Peripheral Processors for Input/Output – a fast multi-threaded 12-bit integer ALU • Very fast clock, 10 MHz (FP add in 4 clocks) • 400,000 transistors, 750 sq. ft., 5 tons, Image removed due to 150 kW, novel freon-based technology for copyright restrictions. cooling • Fastest machine in world for 5 years (until 7600) – over 100 sold (7-10M each) October 19, 2005 6.823 L11-22 Arvind IBM Memo on CDC6600 Thomas Watson Jr., IBM CEO, August 1963: “Last week, Control Data ... announced the 6600 system. I understand that in the laboratory developing the system there are only 34 people including the janitor. Of these, 14 are engineers and 4 are programmers... Contrasting this modest effort with our vast development activities, I fail to understand why we have lost our industry leadership position by letting someone else offer the world's most powerful computer.” To which Cray replied: “It seems like Mr. Watson has answered his own question.” October 19, 2005 6.823 L11-23 Arvind Complex Pipeline ALU Mem IF ID Issue WB Fadd GPR’s FPR’s Fmul Can we solve write hazards without equalizing all pipeline depths and without Fdiv bypassing? October 19, 2005 6.823 L11-24 Arvind 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? October 19, 2005 6.823 L11-25 Arvind A Data Structure for Correct Issues Keeps track of the status of Functional Units Name Busy Op Dest Src1 Src2 Int Mem Add1 Add2 Add3 Mult1 Mult2 Div The instruction i at the Issue stage consults this table FU available? check the busy column RAW? search the dest column for i’s sources WAR? search the source columns for i’s destination WAW? search the dest column for i’s destination An entry is added to the table if no hazard is detected; An entry is removed from the table after Write-Back October 19, 2005 6.823 L11-26 Arvind Simplifying the Data Structure Assuming In-order Issue Suppose the instruction is not dispatched by the Issue stage if a RAW hazard exists or the required FU is busy, and that operands are latched by functional unit on issue: Can the dispatched instruction cause a WAR hazard ? NO: Operands read at issue WAW hazard ? YES: Out-of-order completion October 19, 2005 6.823 L11-27 Arvind Simplifying the Data Structure ... No WAR hazard ⇒ no need to keep src1 and src2 The Issue stage does not dispatch an instruction in case of a WAW hazard ⇒ a register name can occur at most once in the dest column WPreg : a bit-vector to record the registers for which writes are pending These bits are set to true by the Issue stage and set to false by the WB stage ⇒ Each pipeline stage in the FU's must carry the dest field and a flag to indicate if it is valid “the (we, ws) pair” October 19, 2005 6.823 L11-28 Arvind Scoreboard for In-order Issues BusyFU : a bit-vector to indicate FU’s availability. (FU = Int, Add, Mult, Div) These bits are hardwired to FU's. WPreg : a bit-vector to record the registers for which writes are pending. These bits are set to true by the Issue stage and set to false by the WB stage Issue checks the instruction (opcode dest src1 src2) against the scoreboard (Busy & WP) to dispatch FU available? BusyFU RAW? WPsrc1 or WPsrc2 WAR? cannot arise WAW? WPdest October 19, 2005 6.823 L11-29 Arvind Scoreboard Dynamics Functional Unit Status Registers Reserved Int(1) Add(1) Mult(3) Div(4) WB for Writes t0 I f6 f6 1 t1 I f2 f6 f6, f2 2 t2 f6 f2 f6, f2 I 2 t3 I f0 f6 f6, f0 3 t4 f0 f6 f6, f0 I 1 t5 I f0 f8 f0, f8 4 t6 f8 f0 f0, f8 I 3 t7 I f10 f8 f8, f10 5 t8 f8 f10 f8, f10 I 5 t9 f8 f8 I 4 t10 I f6 f6 6 t11 f6 f6 I 6 I DIVD f6, f6, f4 1 I LD f2, 45(r3) 2 I MULTD f0, f2, f4 3 I DIVD f8, f6, f2 4 I SUBD f10, f0, f6 5 I ADDD f6, f8, f2 6 October 19, 2005 30 Thank you
Website URL
Comment