1Edgar GabrielCOSC 6385 Computer Architecture - Tomasulo’s Algorithm (II)Edgar GabrielFall 2009COSC 6385 – Computer ArchitectureEdgar GabrielDetailed steps• Lets look at the details for an operationOP rd, rs, rt(e.g. ADD.D F6, F2, F0)• Assume, that – Operation has been assigned to reservation station r– RS[r] is the data structure holding all the fields for reservation station r, as described in the last lecture– RegisterStat[rs] is the data structure holding the status of register rs (e.g. whether a reservation station will write the register)2COSC 6385 – Computer ArchitectureEdgar GabrielDetailed steps (II)Issue Station r emptyFP operationInstruction state Wait until Action / bookkeepingif ( RegisterStat[rs].Qi != 0 ){RS[r].Qj = RegisterStat[rs].Qi;}else {RS[r].Qj = 0;RS[r].Vj = Regs[rs];}if ( RegisterStat[rt].Qi != 0 ){RS[r].Qk = RegisterStat[rt].Qi;}else {RS[r].Qk = 0;RS[r].Vk = Regs[rt];}RS[r].Busy = yes;RegisterStat[rd].Qi = r;COSC 6385 – Computer ArchitectureEdgar GabrielDetailed steps (III)Execute RS[r].Qj==0 &&FP operation RS[r].Qk==0Write resultFP operation Execution complete and CDB availableInstruction state Wait until Action / bookkeeping/* compute result using Vj and Vk */: if ( RegisterStat[x].Qi == r) {Regs[x] = result;RegisterStat[x].Qi = 0;}: if ( RS[x].Qj == r ) {RS[x].Vj = result;RS[x].Qj = 0;}: if ( RS[x].Qk == r ) {RS[x].Vk = result;RS[x].Qk = 0;}RS[r].Busy = no;x∀x∀x∀3COSC 6385 – Computer ArchitectureEdgar GabrielDetailed steps (IV)Issue Buffer r emptyLoadInstruction state Wait until Action / bookkeepingif ( RegisterStat[rs].Qi != 0 ){RS[r].Qj = RegisterStat[rs].Qi;}else {RS[r].Qj = 0;RS[r].Vj = Regs[rs];}RS[r].A = imm;RS[r].Busy = yes;RegisterStat[rt].Qi = r;For a LOAD operation, e.g. LD rt, imm(rs)COSC 6385 – Computer ArchitectureEdgar GabrielDetailed steps (V)Execute RS[r].Qj==0 &&Load step1 r is head of load queueLoad step 2 Load step 1 completeWrite resultLoad Execution complete and CDB availableInstruction state Wait until Action / bookkeepingRS[r].A = RS[r].Vj + RS[r].ARead from Mem[RS[r].A]: if ( RegisterStat[x].Qi == r) {Regs[x] = result;RegisterStat[x].Qi = 0;}: if ( RS[x].Qj == r ) {RS[x].Vj = result;RS[x].Qj = 0;}: if ( RS[x].Qk == r ) {RS[x].Vk = result;RS[x].Qk = 0;}RS[r].Busy = no;x∀x∀x∀4COSC 6385 – Computer ArchitectureEdgar GabrielDynamic branch prediction (I)• In Tomasulo’s algorithm, no instruction is allowed to initiate execution until all branches preceding the instruction have completed• Up to now, we used four techniques to avoid branch hazards– Stall– Predict not taken– Predict taken– Delayed branch• All methods are static -> do not take the previous behavior of branches into accountCOSC 6385 – Computer ArchitectureEdgar GabrielDynamic branch prediction (II)• Seven techniques for dynamic branch prediction– 1bit branch prediction buffer– 2bit branch prediction buffer– Correlating Branch Prediction Buffer– Branch Target Buffer– (Integrated Instruction Fetch Units)– Return Address Predictors5COSC 6385 – Computer ArchitectureEdgar Gabriel1bit Branch prediction buffer (I)• Branch prediction buffer:– Small memory area indexed by the lower portion of the address of the branch instruction– Records whether the branch was taken the last time or not (1 bit is sufficient)• Please note:– Several branches might share the same address since we do not use the full branch instruction address for accessing the branch prediction bufferCOSC 6385 – Computer ArchitectureEdgar Gabriel1bit Branch Prediction Buffer (II)• Limitations– Even for a regular loop (embedded in another large loop) the 1bit Branch Prediction Buffer will mispredict at least the first and the last iteration• 1stiteration: the bit has been set by the last iteration of the same loop to ‘not-taken’, but the branch will be taken• Last iteration: the bit says ‘taken’, but the branch won’t be taken6COSC 6385 – Computer ArchitectureEdgar Gabriel2bit Branch Prediction Buffer• A prediction must miss twice before the prediction is changed– Can be extended to n-bitsPredict taken11Predict taken10Predict not taken01Predict not taken00TakenTakenNot takenTakenNot takenNot takenTakenCOSC 6385 – Computer ArchitectureEdgar GabrielCorrelated branches• For a (1,1) predictor: each branch has two different branch prediction buffers:• The content of the two branch prediction buffers are determined by the branch to which they belong• Which of the two branch prediction buffers are used is depending on the outcome of the previous branch in the applicationX / YPredictor used in case the previous branch in the application has not been takenPredictor used in case the previous branch in the application has been taken7COSC 6385 – Computer ArchitectureEdgar GabrielCorrelated branches - exampleif ( d==0 )d = 1;if ( d==1 ) …BNEZ R1, L1 !branch b1DADDIU R1, R0, #1L1: DADDIU R3, R1, #-1BNEZ R3, L2 !branch b2…L2: Initial value of dd==0? b1Value of dbefore b2d==1? b22 No Taken 2 No Taken0 Yes Not taken 1 Yes Not taken2 No Taken 2 No Taken0 Yes Not taken 1 Yes Not takenCOSC 6385 – Computer ArchitectureEdgar GabrielCorrelated branches - exampled=?BPB b1 b1 act. BPB b2 B2 act.2 NT/NT NT/NT• the branch prediction buffers for the branches b1 and b2 are assumed to hold the prediction ‘Not taken’ for both option (previous branch not taken/taken)8COSC 6385 – Computer ArchitectureEdgar GabrielCorrelated branches - exampled=?BPB b1 b1 act. BPB b2 B2 act.2 NT/NT NT/NT• assuming BPB for b1 uses the ‘Not Taken’ predictor because the previous branch in the application has not been taken→ BPB for b1 predicts that b1 will not be takenCOSC 6385 – Computer ArchitectureEdgar GabrielCorrelated branches - exampled=?BPB b1 b1 act. BPB b2 B2 act.2 NT/NT T NT/NT→ BPB for b1 predicts that b1 will not be taken→ b1 is taken (see table for d=2)Initial value of dd==0? b1Value of dbefore b2d==1? b22 No Taken 2 No Taken0 Yes Not taken 1 Yes Not taken9COSC 6385 – Computer ArchitectureEdgar GabrielCorrelated branches - exampled=?BPB b1 b1 act. BPB b2 B2 act.2 NT/NT T NT/NTT/NT→ updating the ‘Previous branch has not been taken’ part of BPB for b1 to Taken→ because b1 has been taken, the ‘last branch has been taken’ part of BPB b2 will be used→ BPB b2 predicts, that b2 will not be takenCOSC 6385 – Computer ArchitectureEdgar GabrielCorrelated branches - exampled=?BPB b1 b1 act. BPB