Performance Improvement by Prioritizing the Issue of the Instructions in Unconfident Branch Slices

摘要

Single-thread performance has hardly improved for more than a decade. One of the largest problems for performance improvements is branch misprediction. There are two approaches to reduce the penalty caused by this. One is to reduce the frequency of misprediction, and the other is to reduce the cycles consumed because of misprediction. Improving branch predictors is the former approach, and many studies on this topic have been done for several decades. However, the latter approach has been rarely studied. The present paper hence explores the latter approach. The cycles consumed because of misprediction are divided into the following two parts. The first part is the state recovery penalty, which consists of cycles consumed for rolling back the processor state. The second part is the misspeculation penalty, which are cycles consumed during useless speculative execution from the fetch of a mispredicted branch until the completion of the branch execution. We focus on reducing the misspeculation penalty. For this, we propose a scheme called PUBS, which allows the instructions in unconfident branch slices to be issued with highest priority from the issue queue (IQ). Here, a branch slice is a set consisting of a branch and the instructions this branch directly or indirectly depends on, and we call the branch slice unconfident if the associated branch prediction cannot be sufficiently trusted. By issuing instructions in unconfident branch slices as early as possible, the wait cycles of these instructions in the IQ are minimized and thus the misspeculation penalty is minimized. Our evaluation results using SPEC2006 benchmark programs show that the PUBS scheme improves the performance of the programs with difficult branch prediction by 7.8% on average (a maximum of 19.2%) using only 4.0KB hardware cost.