Enhancing branch prediction via on-line statistical analysis

2002 2002

Other formats: Order a copy

Abstract (summary)

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.

Indexing (details)

Computer science;
0984: Computer science
0463: Statistics
Identifier / keyword
Applied sciences; Pure sciences; Aliasing; Branch prediction; Online; Phase detection; Statistical analysis
Enhancing branch prediction via on-line statistical analysis
Dropsho, Steven George
Number of pages
Publication year
Degree date
School code
DAI-B 63/01, Dissertation Abstracts International
Place of publication
Ann Arbor
Country of publication
United States
9780493525716, 0493525718
Weems, Charles C.
University of Massachusetts Amherst
University location
United States -- Massachusetts
Source type
Dissertations & Theses
Document type
Dissertation/thesis number
ProQuest document ID
Database copyright ProQuest LLC; ProQuest does not claim copyright in the individual underlying works.
Document URL
Access the complete full text

You can get the full text of this document if it is part of your institution's ProQuest subscription.

Try one of the following:

  • Connect to ProQuest through your library network and search for the document from there.
  • Request the document from your library.
  • Go to the ProQuest login page and enter a ProQuest or My Research username / password.