Dynamic Branch Predictors essays

Dynamic Branch Predictors essays In pipelined processors, an instruction must be fetched at every clock cycle in order to sustain the pipeline. However, in modern processors, the decision of whether or not to take a branch is not made until the memory-access stage of the pipeline, and the pipeline must stall the fetching of the next instruction until the decision is made. Because on average 20% of instructions are fetches, this causes a significant penalty on the performance of pipelined processors. Since the processor must keep working during this delay, modern processors incorporate branch predictors to predict whether a branch will be taken or not, and load instructions from the more likely path to minimize the branch penalty. Dynamic branch predictors use information gathered about the program's branches at run-time to determine the most likely outcome of each branch. There are several different flavors of dynamic branch predictors in use, the most common of which are one-level branch predictors, two-level branch predictors, hybrid branch predictors, and multiple component hybrid branch predictors. In one-level branch predictors, each branch instruction is mapped to an entry in a one-dimensional table of n-bit counters, which are usually designated as saturated counters. A saturated counter works like this: If the branch is taken, the corresponding counter is incremented, and if the branch is not taken, the corresponding counter is decremented. The values are cropped to [0...2^n). If a branch's counter is below 2^n-1, the branch is predicted as not taken, and otherwise the branch is predicted as taken. In other words, the branch is predicted as taken if the first bit of the branch's counter is 1, and the branch is predicted as not taken if the first bit is 0. The simplest counters use 1 bit, which is not the most effective. For instance, if a branch is almost always taken, one not-taken will cause the ...