Branch Prediction - Coursework Example

Branch Prediction Introduction Branch prediction is a technique utilized by instruction pre-fetch processors in predicting whether a conditional branch is taken or not taken (Harris 446).Branch prediction remains an important area of research in ways of improving parallelism in computing. It is central factor to parallelism for it has influence on the performance of processors (both pipelined and superscalar). Changes in branches have an effect upon the processor performance due to the fact that there is lots of processor cycles as more effort is required in error rectification. Branch prediction is basically an optimization issue where the emphasis is on attaining minimum miss rate, minimum power consumption and little complexity with the least possible resources. The normal way of fetching and execution of instructions can be interrupted by branches that alter the usual flow of control in programs. Current Branch prediction research centers on bettering the performance of pipelined and superscalar microprocessors by correctly predicting whether a change in control flow will occur or not. Background The necessity for branch prediction develops from the utilization of pipelining technique in modern microarchitectures. The aim of pipelining is to make the most use of all hardware resources of a processor at once. Therefore it becomes necessary to make it certain that each phase of the pipeline hold an instruction. If there is no alterations in program control flow, instructions are fetched, decoded and executed quickly, nevertheless branches can occur breaking the sequence of events (Null and Lobur 17-18). The designers of microprocessors try to predict the direction which a branch takes in the effort of reducing wasted cycles as a result of flushing where many cycles of execution time are wasted. If prediction produces false results (misprediction), then the pipeline requires flushing and the right instruction is fetched into the pipeline. It is important for one to distinguish Dynamic Branch Prediction, from Static Branch Prediction. Static Branch Prediction is a branch prediction that utilizes information collected prior to the execution of a program. The predictors serve the purpose of predicting whether the branch is always taken or not taken. Also the branch direction can be predicted by running the program with a profiler that uses hint bit in the branch opcode as the indicator (Stokes 86). It is not difficult to predict static branches as the compilers covers for such branches. On the other hand, compilers find it hard to predict the outcome for dynamic branches. As a result it becomes necessary to adopt a prediction mechanism for these dynamic branches. Branch prediction schemes. Branch prediction techniques are applied in order to overcome limitations to fetch instructions. There are various techniques that have been presented for predicting the path taken by an instruction after a branch. Simple prediction techniques are usually power efficiency and very fast but, they have a high rate of not predicting whereas complex branch predictions such as neural based and two-level branch prediction give more accurate prediction at the expense of consumption of more power and increased level of complexity. Also complex prediction techniques require more time for prediction that is almost equivalent to the branch execution time (Zhang 156). The following are some widely known branch prediction schemes. Bi-Model Branch Predictors A bimodal branch predictor scheme has a table of n- bit entries that are indexed with the least significant bits of the branch addresses. In contrast to the caches, bimodal predictor entries generally are devoid of tags, and therefore a specific entry can be mapped to distinct separate branch instructions a process known as branch aliasing or branch interference. In such a case it is probably less accurate. For instance the hit rate of a bimodal branch predictors for entries with capacity of 4KB is over 80%. Local Branch Predictors Bimodal branch predictors have the disadvantage of not predicting accurately the exit of each loop. Conditional statements like For Loop have the tendency of having exactly the same number of loop counts due to their repetitive behavior, this gives a room for improvement. Local branch predictors has two tables namely; local branch history table and pattern history table. The local branch history table takes the records for history taken or not taken for the most current executions of the branch. This table is indexed by least significant bits of the respective addresses of branch instructions. The pattern history table indexes are created from the first table branch history and holds bimodal counters. A bimodal counter is used to predict a branch after branch history is ascertained. The hit rate for local branch predictors is fairly high than in bimodal predictors. Global Branch Predictors These type of predictors take the advantage of the strong correlation that exists between the branch behavior and the history of previously taken branches. A specific shift register that holds the history of all executed branches is kept. This stored value is used to index into bimodal counter tables. This technique is ideal for large table sizes as compared to bimodal scheme. Combining Branch Predictors Different branch prediction techniques are combined in parallel orientation. Such predictors may include; bimodal, gshare or bimodal-like predictor that chooses which of the former two predictors (bimodal or gshare) is used on the branches. The bimodal-like predictor is a choice predictor which is a 2bit counter for choosing which prediction scheme to use. The counter is clocked accordingly every time there is difference between the two predictions (bimodal and gshare). This technique equals the accuracy and speed of local prediction and global prediction respectively. Agree Branch Prediction This technique aims to cut down the level of interference in the history tables. An example of a predictor for this category is gskew predictor. The predictor predicts agree/disagree branch condition as opposed to taken/not-taken condition. In such scenarios the branches that are biased in a particular direction to a greater extent will absolutely have more agree entries. As a result probability of two interfere ring branches to have different values is reduced. Much emphasis is put on reducing the level of negative aliasing to either positive or neutral. This type of predictors go along very well with the combined predictors as bimodal predictor is used to form the basis for agree predictor. Agree predictors are suitable in environments where the branches are not biased in a specific direction. Current innovations/research on Commercial Branch Predictors There are several current branch predictors that are a fully integrated into the available commercial designs. POWER4 Branch Prediction in IBM System Microarchitecture. POWER4 prediction unit is very similar to combined predictor. It comprises of three branch history tables namely; Local predictor, Global predictor and Selector predictor. The local predictor also known as Branch history table holds 16 K entries each of which is 1 bit wide. The global predictor contains an 11-bit register for holding the history. The Selector predictor also called selector table is a 16K entry predictor of 1 bit width and monitors the most efficient predictors among the two. POWER4 gives dynamic branch prediction that can be driven by a software, if such a need arises. It also allows redirection of fetch instruction on the basis of the outcome. The predictor tables are modified accordingly depending on the outcome. Alpha 21264 Branch Predictors Alpha 21264 Branch Predictors are an example of Combined Branch Predictors. These predictors resemble POWER4 predictors. They comprise of three closely related units; the Choice predictor, Local predictor and Global predictor. The Local predictor keeps the history of the branches in a 2-bit counter totaling IK entries whereas the Global predictor utilizes 12 most current branches in predicting the expected results of a branch. Global predictor holds a total of 4K entries that are each 2-bit wide. The Choice predictor on the other hand keeps track on the history of both local and global predictors and selects the best among the two predictors. It holds also 4K entries that are each 2-bit wide. Neural Branch Prediction (Machine Learning Approach) This is a conditional branch prediction also referred to as Machine learning approach where machine (computer) acquires knowledge to be able to tell in advance the result of conditional branches. Artificial neural network attempts to model the brain cells neural networks. By so doing, it becomes very effective in learning pattern recognition and classification. Meanwhile Branch predictor emulates artificial neural network and classifies related branches together by utilizing the classification of branches. Neural Branch Prediction has some benefits in that it can be integrated into future microprocessors. Neural Branch Prediction gives a precise prediction implying that the accuracy is very high. However complexity remains a big challenge. The neural predictor is able to exploit complex history and require linear resource growth. On the other hand classical predictors have a requirement for exponential resource growth. The perceptron predictor has one main limitation; its high latency. Despite its high speed, the computation latency is comparatively high in comparison to the clock periods. This disadvantage even characterizes modern Microarchitectures. Conclusion There are two facets to branch predictions; one being determining the results of a given branch that can either be taken or not taken and other being the target address knowledge in case of taken outcome. A static branch prediction approach uses information that is integrated prior to runtime while on the contrary the dynamic branch prediction strategy logic retrieves the information and show in advance the branch behavior at runtime of programs. Nearly all of the dynamic predictors utilize information in two folds. For a better implementation of branch prediction logic both the history of previous branches and their particular behavior is considered. In respect to efficiency dynamic branch prediction comes out better than static due to the fact that the kind of data appearing in run time is quite unalike from the data used for profiling. On a concluding note the best technique to implement in hardware requirements constrained scenario is Bimodal or Gshare predictor. Nevertheless, a Two Level Dynamic Branch Prediction can also be implemented as it has high accuracy branch prediction outcomes. Work cited [1] D. Harris and S. Harris, Digital design and computer architecture, 1st ed. Waltham, MA: Morgan Kaufmann, 2013. [2] J. Stokes, Inside the machine, 1st ed. San Francisco: No Starch Press, 2007. [3] W. Zhang, High performance computing and applications, 1st ed. Berlin: Springer, 2010. [4] M. Hill, N. Jouppi and G. Sohi, Readings in computer architecture, 1st ed. San Francisco: Morgan Kaufmann, 2000. [5] L. Null and J. Lobur, Essentials of computer organization and architecture, 1st ed. Sudbury, Mass.: Jones & Bartlett Learning, 2012. Read More