(Answered): Branch Prediction, see following pics Question 3 Branch Prediction In this example, assume that each ...

Question 3 Branch Prediction In this example, assume that each loop uses a single branch instruction to decide where to go next. Consider the following loop nest: Branch 1: while( true) Branch 2: for(int i = 0; i < 2; i++) Branch 3: for( int j = 0; j< 1; j++) <do something> // PC: 0000 // PC: 0100 // PC: 1000 a) [5 points ] Starting with “Branch 1”, write the first 16 branch outcomes for the above code below. Hint: The first three are given! Complete the sequence. Number 1 2 3 Branch Branch 1 Branch 2 Branch 3 Branch 3 Outcome Taken Taken Taken 4 5 6 7 8 9 10 11 12 13 14 15 16 b) [5 points ] Assume we run the above code on a machine implementing Smith's predictor. The predictor uses the two PC MSBs to index the Pattern History Table (PHT). Note that in this case the addresses are only 4b long, so it's skipping the 2 LSBs. You should assume the PHT entries are 2b saturating counters all initialized to Weakly Taken (WT). How many entries does the PHT have and what is the predictors accuracy? Guess Result Branch Address 00 Current State WT WT WT T T Next State ST ST ST 01 T T 10 T T c) [20 points ] The CTO of Intel is calling you. They can't figure out how to design a branch predictor for the above branch pattern and can only afford to build an 8 entry PHT with 2b counters. They are convinced that the best option is to implement a static policy that guesses "Always Taken” and simply save the area the PHT would otherwise take up. You don't believe this is true because you recently took ECE 6913 A at NYU and are a branch prediction expert. You have just enough time to evaluate two designs before the CPU microarchitecture is frozen and sent off for fabrication, which one do you choose? 1) BP1: A two-level branch predictor that uses a 2-bit Global History Register (GSR) and the 3rd (from the right) bit of the branch PC address to index an 8 entry PHT. (E.g., if a branch address is 0100 the address bit used would be 1.) Assume the PHT using 2b saturating counters that are initialized to Weakly Taken (WT). 2) BP2: A two-level branch predictor that uses a 3-bit GHR to directly index the PHT. In this scenario, the PC address is not used to index the PHT. To evaluate the best design, simulate the 16 branch outcomes from part a) on both designs. To receive full credit, explain why each predictor is unable to do better by analyzing why mispredictions happen. BP1: GHR Guess Result 00 Branch PC Address 00 01 10 PHT Index 000 011 110 Current State WT WT WT T T Next State ST ST ST 01 11 T T T T BP2: GHR Guess Result PHT Index 000 000 Current State WT WT WT T T Next State ST ST ST T 001 011 001 011 T T T