CS 152 Computer Architecture and Engineering Lecture 13 Out of Order Issue Register Renaming Branch Prediction Krste Asanovic Electrical Engineering and Computer Sciences University of California at Berkeley http www eecs berkeley edu krste http inst eecs berkeley edu cs152 Last time in Lecture 12 Pipelining is complicated by multiple and or variable latency functional units Out of order and or pipelined execution requires tracking of dependencies RAW WAR WAW Dynamic issue logic can support out of order execution to improve performance Last time looked at simple scoreboard to track out of order completion Hardware register renaming can further improve performance by removing hazards 3 12 2009 CS152 Spring 09 2 Out of Order Issue ALU IF ID Issue Mem WB Fadd Fmul Issue stage buffer holds multiple instructions waiting to issue Decode adds next instruction to buffer if there is space and the instruction does not cause a WAR or WAW hazard Note WAR possible again because issue is out of order WAR not possible with in order issue and latching of input operands at functional unit Any instruction in buffer whose RAW hazards are satisfied can be issued for now at most one dispatch per cycle On a write back WB new instructions may get enabled 3 12 2009 CS152 Spring 09 3 Overcoming the Lack of Register Names Floating Point pipelines often cannot be kept filled with small number of registers IBM 360 had only 4 floating point registers Can a microarchitecture use more registers than specified by the ISA without loss of ISA compatibility Robert Tomasulo of IBM suggested an ingenious solution in 1967 using on the fly register renaming 3 12 2009 CS152 Spring 09 4 Instruction level Parallelism via Renaming 1 LD F2 34 R2 latency 1 2 LD F4 45 R3 long 3 MULTD F6 F4 F2 3 4 SUBD F8 F2 F2 1 5 DIVD F4 F2 F8 4 6 ADDD F10 F6 F4 1 In order Out of order 1 2 4 3 X 5 6 1 2 1 2 3 4 4 3 5 5 6 6 1 2 1 4 4 5 2 3 5 3 6 6 Any antidependence can be eliminated by renaming renaming additional storage Can it be done in hardware 3 12 2009 5 CS152 Spring 09 Register Renaming ALU IF ID Mem Issue WB Fadd Fmul Decode does register renaming and adds instructions to the issue stage reorder buffer ROB renaming makes WAR or WAW hazards impossible Any instruction in ROB whose RAW hazards have been satisfied can be dispatched Out of order or dataflow execution 3 12 2009 CS152 Spring 09 6 Dataflow execution Ins use exec op p1 src1 p2 src2 t1 t2 ptr2 next to deallocate prt1 next available tn Reorder buffer Instruction slot is candidate for execution when It holds a valid instruction use bit is set It has not already started execution exec bit is clear Both operands are available p1 and p2 are set 3 12 2009 7 CS152 Spring 09 Renaming Out of order Issue An example Renaming table v1 F1 F2 F3 F4 F5 F6 F7 F8 p data v1 t1 t5 t2 Reorder buffer Ins use exec op p1 0 1 1 0 LD LD 3 0 1 10 1 0 MUL 4 5 10 1 1 0 0 SUB DIV 1 22 src1 p2 src2 10 v2 t2 11 v1 v1 1 1 v1 v1 1 0 1 v1 t4 v4 t3 t1 t2 t3 t4 t5 v4 t4 data ti 1 2 3 4 5 6 LD LD MULTD SUBD DIVD ADDD 3 12 2009 F2 F4 F6 F8 F4 F10 34 R2 45 R3 F4 F2 F2 F6 F2 F2 F8 F4 When are tags in sources replaced by data When can a name be reused CS152 Spring 09 8 Data Driven Execution Renaming table reg file Ins use exec op p1 src1 p2 t1 t2 tn src2 Reorder buffer Replacing the tag by its value is an expensive operation Load Unit FU Store Unit FU t result Instruction template i e tag t is allocated by the Decode stage which also associates tag with register in regfile When an instruction completes its tag is deallocated 3 12 2009 9 CS152 Spring 09 Simplifying Allocation Deallocation Ins use exec op p1 src1 p2 t1 t2 ptr2 next to deallocate prt1 next available src2 Reorder buffer tn Instruction buffer is managed circularly exec bit is set when instruction begins execution When an instruction completes its use bit is marked free ptr2 is incremented only if the use bit is marked free 3 12 2009 CS152 Spring 09 10 IBM 360 91 Floating Point Unit R M Tomasulo 1967 1 2 3 4 5 6 distribute instruction templates by functional units p p p p p p tag data tag data tag data tag data tag data tag data load buffers from memory instructions 1 2 3 4 p p p p tag data tag data tag data tag data Floating Point Reg 1 p tag data p tag data 2 p tag data p tag data 1 p tag data p tag data 3 p tag data p tag data 2 p tag data p tag data Adder Mult tag result p tag data store buffers p tag data to memory p tag data Common bus ensures that data is made available immediately to all the instructions waiting for it Match tag if equal copy value set presence p 3 12 2009 CS152 Spring 09 11 Effectiveness Renaming and Out of order execution was first implemented in 1969 in IBM 360 91 but did not show up in the subsequent models until midNineties Why Reasons 1 Effective on a very small class of programs 2 Memory latency a much bigger problem 3 Exceptions not precise One more problem needed to be solved 3 12 2009 CS152 Spring 09 12 Precise Interrupts It must appear as if an interrupt is taken between two instructions say Ii and Ii 1 the effect of all instructions up to and including Ii is totally complete no effect of any instruction after Ii has taken place The interrupt handler either aborts the program or restarts it at Ii 1 3 12 2009 13 CS152 Spring 09 Effect on Interrupts Out of order Completion I1 I2 I3 I4 I5 I6 out of order comp DIVD LD MULTD DIVD SUBD ADDD 1 2 f6 f2 f0 f8 f10 f6 2 3 f6 45 r3 f2 f6 f0 f8 1 4 3 5 restore f2 f4 f4 f2 f6 f2 5 4 6 6 restore f10 Consider interrupts Precise interrupts are difficult to implement at high speed want to start execution of later instructions before exception checks finished on earlier instructions 3 12 2009 CS152 Spring 09 14 Exception Handling Commit Point In Order Five Stage Pipeline Inst Mem PC Select Handler PC PC Address Exceptions Kill F Stage D Decode E Illegal Opcode Exc D PC D Data Addr Except Overflow Exc E Kill D Stage Data Mem M PC E W Kill Writeback Exc M Kill E Stage PC M Cause EPC Asynchronous Interrupts Hold exception flags in pipeline …
View Full Document
Unlocking...