CS 152 Computer Architecture and Engineering Lecture 12 Advanced Out of Order Superscalars Krste Asanovic Electrical Engineering and Computer Sciences University of California at Berkeley http www eecs berkeley edu krste http inst eecs berkeley edu cs152 March 9 2011 CS152 Spring 2011 Last time in Lecture 11 Register renaming removes WAR WAW hazards In order fetch decode out of order execute in order commit gives high performance and precise exceptions Dynamic branch predictors can be quite accurate 95 and avoid most control hazards Branch History Tables BHTs just predict direction later in pipeline Just need a few bits per entry 2 bits gives hysteresis Need to decode instruction bits to determine whether this is a branch and what the target address is Branch Target Buffers BTBs predict direction and target earlier in pipeline but bigger entries Return Address Stack predicts subroutine returns March 9 2011 CS152 Spring 2011 2 Branch Mispredict Recovery In order execution machines Assume no instruction issued after branch can write back before branch resolves Kill all instructions in pipeline behind mispredicted branch Out of order execution Multiple instructions following branch in program order can complete before branch resolves March 9 2011 CS152 Spring 2011 3 In Order Commit for Precise Exceptions In order Fetch Out of order Reorder Buffer Decode Kill In order Commit Kill Kill Execute Inject handler PC Exception Instructions fetched and decoded into instruction reorder buffer in order Execution is out of order out of order completion Commit write back to architectural state i e regfile memory is in order Temporary storage needed in ROB to hold results before commit March 9 2011 CS152 Spring 2011 4 Branch Misprediction in Pipeline Inject correct PC Branch Prediction Kill Kill PC Fetch Decode Branch Resolution Kill Reorder Buffer Commit Complete Execute Can have multiple unresolved branches in ROB Can resolve branches out of order by killing all the instructions in ROB that follow a mispredicted branch Must also kill instructions in flight in execution pipelines March 9 2011 CS152 Spring 2011 5 Recovering ROB Renaming Table Rename Table r1 t vv t t t vv Rename Snapshots Register File r2 Ptr2 next to commit Ins use exec op p1 src1 p2 src2 pd dest data rollback next available Ptr1 next available Reorder buffer Load Unit FU FU FU Store Unit t1 t2 tn Commit t result Take snapshot of register rename table at each predicted branch recover earlier snapshot if branch mispredicted March 9 2011 CS152 Spring 2011 6 Data in ROB Design HP PA8000 Intel Pentium Pro Core2 Duo Nehalem Register File holds only committed state Ins use exec op p1 src1 p2 src2 pd dest data Reorder buffer Load Unit FU FU FU Store Unit t1 t2 tn Commit t result On dispatch into ROB ready sources can be in regfile or in ROB dest copied into src1 src2 if ready before dispatch On completion write to dest field and broadcast to src fields On issue read from ROB src fields March 9 2011 CS152 Spring 2011 7 Data Movement in Data in ROB Design Architectural Register File Read operands during decode Write results at commit Write sources after decode Read results at commit Reorder Buffer Read operands at issue Write results at completion Functional Units March 9 2011 CS152 Spring 2011 8 Unified Physical Register File MIPS R10K Alpha 21264 Intel Pentium 4 Sandy Bridge Rename all architectural registers into a single physical register file during decode no register values read Functional units read and write from single unified register file holding committed and temporary registers in execute Commit only updates mapping of architectural register to physical register no data movement Decode Stage Register Mapping Commited Register Mapping Unified Physical Register File Read operands at issue Write results at completion Functional Units March 9 2011 CS152 Spring 2011 9 Pipeline Design with Physical Regfile kill Branch Prediction PC Fetch kill Branch Resolution kill Decode Rename kill Out of Order Reorder Buffer In Order Commit In Order Physical Reg File Branch ALU MEM Unit Store Buffer D Execute March 9 2011 CS152 Spring 2011 10 Lifetime of Physical Registers Physical regfile holds committed and speculative values Physical registers decoupled from ROB entries no data in ROB ld r1 r3 add r3 r1 4 sub r6 r7 r9 add r3 r3 r6 ld r6 r1 add r6 r6 r3 st r6 r1 ld r6 r11 Rename ld P1 Px add P2 P1 4 sub P3 Py Pz add P4 P2 P3 ld P5 P1 add P6 P5 P4 st P6 P1 ld P7 Pw When can we reuse a physical register When next write of same architectural register commits March 9 2011 CS152 Spring 2011 11 Physical Register Management R0 R1 R2 R3 R4 R5 R6 R7 Rename Table P8 P7 P5 P6 Physical Regs P0 P1 P2 P3 P4 P5 P6 P7 P8 Free List R6 R7 R3 R1 p p p p p2 Rd P0 P1 P3 P2 P4 ld r1 0 r3 add r3 r1 4 sub r6 r7 r6 add r3 r3 r6 ld r6 0 r1 Pn ROB use ex op March 9 2011 p1 PR1 PR2 LPRd CS152 Spring 2011 PRd LPRd requires third read port on Rename Table for each instruction 12 Physical Register Management R0 R1 R2 R3 R4 R5 R6 R7 Rename Table P8 P0 P7 P5 P6 Physical Regs P0 P1 P2 P3 P4 P5 P6 P7 P8 Free List R6 R7 R3 R1 p p p p p2 Rd r1 P0 P1 P3 P2 P4 ld r1 0 r3 add r3 r1 4 sub r6 r7 r6 add r3 r3 r6 ld r6 0 r1 Pn ROB use ex op x ld March 9 2011 p1 p PR1 P7 PR2 LPRd P8 CS152 Spring 2011 PRd P0 13 Physical Register Management R0 R1 R2 R3 R4 R5 R6 R7 Rename Table P8 P0 P7 P1 P5 P6 Physical Regs P0 P1 P2 P3 P4 P5 P6 P7 P8 Free List R6 R7 R3 R1 p p p p p2 Rd r1 r3 P0 P1 P3 P2 P4 ld r1 0 r3 add r3 r1 4 sub r6 r7 r6 add r3 r3 r6 ld r6 0 r1 Pn ROB use ex op p1 x ld p x add March 9 2011 PR1 P7 P0 PR2 LPRd P8 P7 CS152 Spring 2011 PRd P0 P1 14 Physical Register Management R0 R1 R2 R3 R4 R5 R6 R7 Rename Table P8 P0 P7 P1 P5 P3 P6 Physical Regs P0 P1 P2 P3 P4 P5 P6 P7 P8 Free List R6 R7 R3 R1 p p p p p2 PR2 p P5 Rd r1 r3 r6 P0 P1 P3 P2 P4 ld r1 0 r3 add r3 r1 4 sub r6 r7 r6 add r3 r3 r6 ld r6 0 r1 Pn ROB use ex x x x op p1 ld p add sub p March 9 2011 PR1 P7 P0 P6 LPRd P8 P7 P5 CS152 Spring 2011 PRd P0 P1 P3 15 Physical Register Management R0 R1 R2 R3 R4 R5 R6 R7 Physical Regs Rename Table P8 P0 P7 P1 P2 P5 P3 P6 P0 P1 P2 P3 P4 P5 P6 …
View Full Document
Unlocking...