Dependency Chain Prioritization to Speed Up Branch With Low-Confidence Prediction
Publication Date: 2016-Aug-18
The IP.com Prior Art Database
Described is dependency chain prioritization to speed up branch with low-confidence prediction.
Page 01 of 4
Dependency Chain Prioritization to Speed Up Branch With Low - Prediction
Branch prediction is a common technique in microprocessors used to speed up the information flow through the pipeline. This technique predicts which way a branch will evaluate, taken or not taken, before fetching, loading, and executing further instructions based on this prediction. If the branch prediction is correct, then the pipeline would already be loaded with the instructions following the branch, allowing for a faster information flow through the pipeline. However, if the branch prediction is incorrect, then all of the information that was loaded based on the branch prediction must be flushed, causing a significant drop in performance.
A pattern of instructions that occurs frequently in programs is a sequence of a Load (LD) or Add (ADD), Compare (CMP), and then Branch (BR). Often times, a BR is dependent on a CMP instruction, which may be ready to issue but must wait behind older instructions before it can be issued. In the meantime, in the case of an incorrectly predicted branch, new, incorrect instructions are being fetched and dispatched every cycle, filling the Issue Queue (ISQ), the Mappers, and the Completion Table, and all of the BR-related instructions will need to be flushed once the BR executes. Additionally, during Branch prediction, the various Branch prediction algorithms work to assign a value to a Branch prediction: strongly taken, weakly taken, strongly not taken, or weakly not taken. These values indicate the level of confidence the algorithm has in the prediction. Since weakly predicted values are less likely to be right than strongly predicted branches, these branches are more prone to cause flushing and performance loss. If these weaker branches are given a higher priority, performance could be enhanced by executing and evaluating these mispredicted branches more quickly. By taking the branch prediction confidence into account when determining which instructions to issue and resolving BR instructions faster, more incorrectly predicted and fetched instructions can be flushed while correctly fetched instructions from other threads are kept and executed, effectively minimizing the Branch mispredict penalty.
In current implementations, CMP-dependent BR instructions are not given any priority and, therefore, BR instructions are not evaluated quickly. BR instructions currently read from the CR Mapper, which tracks the Condition Register set by CMP instructions. In turn, the Compare instruction reads from the GPR Mapper, which tracks the general, logical registers used during instruction processing. The BR instruction then waits in the Branch Issue Queue for the CMP instruction it's dependent on to be issued before it can be issued. This new mechanism will track the confidence of Branch predictions, starting from the Branch prediction unit in the IFU in the point of issue in the ISU, giving more priority to resolving weakly predicted Bran...