Maintaining high performance in the presence of impossible-to-predict branches




Pruett, Stephen M.

Journal Title

Journal ISSN

Volume Title



High performance microprocessors have relied on accurate branch predictors to maintain high instruction supply for over 30 years. Unfortunately, as instruction windows and pipeline widths have continued to grow, misprediction penalties have gotten worse. Branch predictors have failed to improve at a fast enough rate to counteract these penalties. Impossible-to-predict branches, such as data-dependent branches, have become the worst offender since, so far, no viable predictor exists for these branches. I propose to identify such branches at runtime, and replace the inaccurate branch prediction with a more accurate merge point prediction. Doing so enables techniques that can either pre-compute the result of the branch, as is the case for Branch Runahead, or avoid the misprediction altogether by dynamically predicating instructions, or fetching instructions out-of-order; i.e., from the merge point until the branch direction has been determined. This dissertation presents a new merge point prediction algorithm that achieves a higher accuracy and coverage than prior work, and uses it to enable three mechanisms for dealing with impossible-to-predict branches: Branch Runahead, Dynamic Predication, and Delayed Fetch.


LCSH Subject Headings