Enhancing branch prediction via on-line statistical analysis

To attain peak efficiency, high performance processors must anticipate changes in the flow of control before they actually occur. Branch prediction is the method of determining the most likely path to be taken at branch decision points in the pro gram. Many branch prediction mechanisms have been proposed. The most effective of these use a single tabular data structure in hardware to hold historical information regarding the behaviors of branches. The table is a limited resource, and is managed in a manner that can result in multiple branches attempting to share locations in the table in a conflicting manner. These conflicts are a major factor in the degradation of the accuracy of branch predictions. Such conflicts are called aliasing and much work has been done to reduce its occurrence. In this work, we present a novel method of analyzing the effectiveness of the various prediction methods relative to aliasing. The technique is based on a concept we introduce, branch entropy. With this concept, we develop an algorithm that efficiently determines combinations of predictor components that improve overall accuracy by adjusting the aggressiveness of the predictor to manage the degree of aliasing within the table, and thus optimize overall prediction accuracy. One result of this work is that identifying branches that are highly biased towards being taken (or not taken) and separately predicting them with a simple designation for their preferred direction, so that they are prevented from accessing the predictor table is the single most effective method for reducing aliasing and improving accuracy. From this result, we develop a design that automatically controls this process via a novel on-line profiling technique. Based on a robust statistical framework, our on-line profiling technique performs as well as off-line profiling that uses perfect feedback information. We show that this statistics-based method can also be applied to other, similar tasks by performing on-line profiling of objects in Java garbage collection for pretenuring into a mature object space