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

dc.contributor.advisorPatt, Yale N.
dc.contributor.committeeMemberErez, Mattan
dc.contributor.committeeMemberTiwari, Mohit
dc.contributor.committeeMemberRossbach, Christopher
dc.contributor.committeeMemberChappell, Rob S
dc.creatorPruett, Stephen M.
dc.date.accessioned2022-10-26T22:25:56Z
dc.date.available2022-10-26T22:25:56Z
dc.date.created2022-05
dc.date.issued2022-05-06
dc.date.submittedMay 2022
dc.date.updated2022-10-26T22:25:57Z
dc.description.abstractHigh 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.
dc.description.departmentElectrical and Computer Engineering
dc.format.mimetypeapplication/pdf
dc.identifier.urihttps://hdl.handle.net/2152/116384
dc.identifier.urihttp://dx.doi.org/10.26153/tsw/43279
dc.language.isoen
dc.subjectComputer architecture
dc.subjectMicroarchitecture
dc.subjectBranch prediction
dc.subjectPre-computation
dc.subjectControl independence
dc.subjectMerge point prediction
dc.subjectReconvergence
dc.titleMaintaining high performance in the presence of impossible-to-predict branches
dc.typeThesis
dc.type.materialtext
thesis.degree.departmentElectrical and Computer Engineering
thesis.degree.disciplineElectrical and Computer Engineering
thesis.degree.grantorThe University of Texas at Austin
thesis.degree.levelDoctoral
thesis.degree.nameDoctor of Philosophy

Access full-text files

Original bundle

Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
PRUETT-DISSERTATION-2022.pdf
Size:
1.15 MB
Format:
Adobe Portable Document Format

License bundle

Now showing 1 - 2 of 2
No Thumbnail Available
Name:
PROQUEST_LICENSE.txt
Size:
4.45 KB
Format:
Plain Text
Description:
No Thumbnail Available
Name:
LICENSE.txt
Size:
1.84 KB
Format:
Plain Text
Description: