1Intelligent wrong path issue: a means of improving performanceByChidiogo MadubikeMeghana SardesaiNmita Sarna2IntroductionSpeculation of instructions is crucial for modern superscalarsBranch predictors provide accuracies of up to 96% and are key to effective speculationHowever we cannot rely solely on prediction because the latency of misprediction has a negative impact on performanceTo solve this problem, computer architects came up with the ideaof wrong path issue3To issue or not to issue?Wrong path issue reduces the misprediction penaltyOn the other hand, useless wrong path instructions waste processor resources and must invariably be flushed from the pipeline– Have to have enough resources to issue and execute 2 paths knowing that one of them will be invalidatedTo find a better solution, we look at the behavior of branch instructions:4Branch behaviorProgram trace- branch instructions1 0 1 1 1 1 1 1 1 0 0 1 1 0 1 1 0 0 1 0 1 1 0 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1BLEZ instruction.…………0110111011111111111111111111111………..5IdeaImprove performance by introducing an algorithm which only selectively issues from the wrong path by observing the behavior of individual branches within a programAttempts to:– Reduce number of useless instructions being executed thus increasing useful instruction throughput– Reduce complexity involved in always issuing and executing of wrong path instructions – Prevent flushing of these instructions whenever the prediction is correct and therefore improving usage of resources and performance6Resource Usage# of functional units, dispatch queues, IFQs, reservation stations, etc.– For programs without enough ILP to make full use of processor resources, this might not be a problem– However if we have any programs that can make sufficient use of the processor resources then something needs to be doneAttempt to improve resource usage using a new algorithm7Implementation details Branch address sent to predictorPredictor entry for each branch includes– Threshold value of particular branchPredictor includes confidence values which contain–Incrementvalue for each correct prediction– System threshold value – (have to determine optimum value)– Max value of branch threshold– Prediction penalty for wrong predictions8Architecturebaddr btarget Br. thresholdbaddr>Sys. thresholdFetch andIssue wrong path?BTB entriesop9Program trace:Our program traces indicate that we attempt to capture those areas of the program in which the branch behavior is predicted to be highly accurate:op = 6 ; 0 br thr= 21 path dec= 1op = 2 ; 1 br thr= 27 path dec= 1op = 3 ; 1 br thr= 28 path dec= 1op = 6 ; 0 br thr= 17 path dec= 1op = 2 ; 1 br thr= 28 path dec= 1op = 3 ; 1 br thr= 29 path dec= 0op = 6 ; 0 br thr= 25 path dec= 1op = 6 ; 0 br thr= 13 path dec= 1op = 6 ; 1 br thr= 14 path dec= 1:10SimulationsWe performed our simulations on spec2000 reduced benchmarks using two different #’s of execution resourcesOur benchmarks : equake (FP), mcf (INT), parser (INT)– Equake: Simulation of seismic wave propagation in large basins– Mcf: Combinatorial optimization / Single-depot vehicle scheduling– Parser: Word ProcessingThe programs we simulated didn’t have much parallelism but we were able to obtain data that proved our hypothesis to some degree11Simulations cont’d…2ndset of data– 3 FPU adders– 3 integer ALUs – 1 integer MULT/DIV unit– 1 FPU MULT/DIV unit1stset of data– 4 FPU adders– 4 integer ALUs – 1 integer MULT/DIV unit– 1 FPU MULT/DIV unitBaseline Architecture – Always issues and executes the wrong path Our program – Selectively issues and executes the wrong path depending on information from the branch predictor12Results for FU = 4BaselineOur Dynamic ProgramEquake = 0.11% degradation (IPC)Mcf = 0.24% degradation (IPC)Parser= 2.29% improvement (IPC)1.53201.39380.7175Equake0.76720.70421.4201Mcf0.6121CPI1.6338IPC1.9959ParserExec_BWBenchm.1.43031.39270.7181Equake0.74660.70181.4250Mcf0.6036CPI1.6567IPC1.7259ParserExec_BWBenchm.13Results for FU = 3Baseline Our Dynamic programEquake = 0.11% degradation (IPC)Mcf = 0.48% degradation (IPC)Parser= 2.15% improvement (IPC)1.52561.38400.7225Equake0.77000.70551.4174Mcf0.6228CPI1.6057IPC1.9657ParserExec_BWBenchm.1.42041.38290.7231Equake0.74500.70071.4271Mcf0.6146CPI1.6272IPC1.6877ParserExec_BWBenchm.14ConclusionsReduction of useless resource usage Effect of ILPEffect of more or less execution resourcesEffect on longer pipelinesValidity of Hypothesis15ReferencesSwanson, McDowell, Swift, Eggers, Levy. “An evaluation of Speculative Instruction Execution on Simultaneous Multithreaded processors”, submitted for publication.Johnny K.F. Lee, Alan Jay Smith, “Branch Prediction Strategies and Branch Target Buffer Design”, Computer, January 1984.Joel Emer, Nikolas Gloy. “A Language for Describing Predictors and its Application to Automatic Synthesis”, Proceedings of the 24thInternational Symposium on Computer Architecture, June 1997Eric Rotenberg, Steve Bennet, James E. Smith, “Trace Cache: a Low Latency Approach to High Bandwidth Instruction Fetching”, Proceedings of the 29thInternational Symposium onMicroarchitecture, December 1996.Daniel Holmes Friendly, Sanjay Jeram Patel, Yale N. Patt, “Alternative Fetch and Issue Policies for the Trace Cache Fetch Mechanism”, Proceedings of the 30thInternational Symposium onMicroarchitecture, November