New Algorithm Improves Branch PredictionSimple Hardware Can Achieve 65%Dynamic Prediction Uses HistoryFigure 1. In the two-bit Smith algorithm …Figure 2. The two-level algorithm uses …Two-Level Algorithm Improves AccuracyPracticality Forces SimplificationTarget Addresses Must Also Be PredictedFigure 3. A branch history table …Figure 4. As processors use more complex algorithms …Alternative Designs Ease BranchingP6 Implementation Remains MysteriousTwo-Level Prediction Is Very AccurateYeh and Patt’s Taxonomyby Linley GwennapIntel’s P6 processor (see 090202.PDF) is the first touse a two-level branch-prediction algorithm to improveaccuracy. This algorithm, first published by Tse-Yu Yehand Yale Patt, has the potential to push accuracy wellbeyond the 90% level achieved by the best processorstoday. As future processors look to improve performanceby increasing the issue rate and/or extending thepipeline depth, the two-level algorithm is likely to be-come more common.Branch prediction has been a problem for CPU de-signers since the advent of pipelining. A pipelined pro-cessor must fetch the next instruction before the currentone has executed. If the current instruction is a condi-tional branch, the processor must decide whether to fetchfrom the target address, assuming the branch will betaken, or from the next sequential address, assuming thebranch will not be taken. An incorrect guess causes thepipeline to stall until it is refilled with valid instructions;this delay is called the mispredicted branch penalty.Processors with a simple five-stage pipeline typi-cally have a two-cycle branch penalty. For a four-waysuperscalar design, however, this could mean a loss ofeight instructions. If the pipeline is extended, the branchpenalty usually increases, resulting in the loss of evenmore instructions. Since programs typically encounterbranches every 4–6 instructions, inaccurate branch pre-diction causes a severe performance degradation inhighly superscalar or deeply pipelined designs.Initial efforts at branch prediction used simple al-gorithms based on the direction of the branch. Amongcommercial microprocessors, the MIPS R6000 pioneeredthe use of compiler “hints” to direct branch prediction.Digital’s 21064 was the first microprocessor to storebranch history information, with the P6 leading the wayto two-level prediction. This article reviews these earlieralgorithms before explaining the new two-level methodin more detail.Simple Hardware Can Achieve 65%For scalar processors with relatively short pipelines,branch prediction is less of a concern. In fact, for proces-sors with a branch delay slot, the branch penalty can beas little as one cycle. The default “prediction” method forsimple pipelined designs is to assume that branches arenot taken, always fetching sequential instructions. The486 and most embedded processors use this scheme be-cause of its simplicity and low cost.It turns out, however, that conditional branches aretaken more often than not. Most programs make heavyuse of loops, which repeatedly branch to the same ad-dress. Simulations show that conditional branches aretaken about 60% of the time in the SPECint89 suite andmore often in scientific code such as the SPECfp89benchmarks[1]. Thus, a simple optimization is to alwayspredict branches to be taken.A better algorithm takes into account the directionof the branch. Backward branches typically completeloop iterations and thus are taken as much as 80% of thetime or more. Forward branches are more difficult topredict but tend to be not taken more often than taken.Thus, by simply looking at the direction of the branch(usually available as the sign bit of the offset), a proces-sor can predict backward branches taken and forwardbranches not taken. This BTFN algorithm succeedsabout 65% of the time for SPECint89. MicroSparc-2 andmost PA-RISC processors use BTFN.With appropriate instruction-set hooks, the com-piler can improve branch-prediction accuracy. Because ithas access to the source code, a good compiler can recog-nize code sequences that are likely to branch, such asloops, and those that are unlikely to branch, such as ex-ception checking. Current MIPS and PowerPC chips,among others, implement special branch instructionsthat encode the compiler’s prediction in a single bit.Compilers can take further advantage of these pre-dicted branch instructions by using a technique calledprofiling or feedback-directed compilation. After the pro-gram is initially compiled, it is run using test data to de-termine the typical direction of each branch; the pro-gram is then recompiled to adjust the branch-predictionbits. According to IBM, its compilers achieve 75% accu-racy on SPECint92 using this technique.Dynamic Prediction Uses HistoryThe previous algorithms are classified as staticschemes, because any particular branch is always pre-dicted in the same way whenever it is encountered. Toachieve greater accuracy, dynamic algorithms take intoaccount run-time information. The processor learns fromits mistakes and changes its predictions to match the be-havior of each particular branch.A dynamic algorithm keeps a record of previousbranch behavior, allowing it to improve its predictionsover time. A simple scheme, published by James Smithin 1981[2], maintains a single history bit for each branch.When a branch is encountered, it is predicted to go theMICROPROCESSOR REPORTNew Algorithm Improves Branch Prediction Vol. 9, No. 4, March 27, 1995 © 1995 MicroDesign ResourcesNew Algorithm Improves Branch Prediction Better Accuracy Required for Highly Superscalar Designssame way it did the previous time, as indicated by thebit. This technique can push accuracy to 80%.As a practical matter, there are two ways to imple-ment this scheme. The history bits can be kept in the in-struction cache, for example, one per every four instruc-tions. When instructions are fetched from the cache, thehistory bit comes along. If the bit is set, that group of in-structions contains a predicted-taken branch, and thefetch stream is redirected. In this example, the storageoverhead would be less than 1% of the cache area.Although this method—used by Digital’s Alpha,AMD’s K5, and other processors—provides dynamic pre-diction with minimal cost, it has some drawbacks. Somegroups of instructions will not contain a branch, wastingthe history bit. Groups with multiple branches createinterference, as the history of one branch overwrites thatof another in the
View Full Document
Unlocking...