Browse Prior Art Database

Generalized History for Branch Prediction

IP.com Disclosure Number: IPCOM000049476D
Original Publication Date: 1982-Jun-01
Included in the Prior Art Database: 2005-Feb-09
Document File: 3 page(s) / 46K

Publishing Venue

IBM

Related People

Losq, JJ: AUTHOR

Abstract

In pipeline computer, branch instructions cause delays. One method to reduce these delays is by the use of a Branch History Table (BHT). A BHT stores the last n taken branches. Instruction addresses are used to access the BHT, at the time instructions are prefetched. A hit in the BHT means that the last time that instruction was executed, it was a taken branch. When there is a BHT hit, the table produces the target address. This address (the target of the branch for the last execution) is used to redirect instruction fetching. The reason is that it is hoped that if the last time that branch was executed it was taken, it will also be taken and have the same target address the next time it is executed. The success rate of this prediction strategy ("do as last time") is good on the average, but not for every branch.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 54% of the total text.

Page 1 of 3

Generalized History for Branch Prediction

In pipeline computer, branch instructions cause delays. One method to reduce these delays is by the use of a Branch History Table (BHT). A BHT stores the last n taken branches. Instruction addresses are used to access the BHT, at the time instructions are prefetched. A hit in the BHT means that the last time that instruction was executed, it was a taken branch. When there is a BHT hit, the table produces the target address. This address (the target of the branch for the last execution) is used to redirect instruction fetching. The reason is that it is hoped that if the last time that branch was executed it was taken, it will also be taken and have the same target address the next time it is executed. The success rate of this prediction strategy ("do as last time") is good on the average, but not for every branch. For example, some branches alternate between being taken and falling through. For those, the prediction will always be wrong.

It is possible to achieve a much higher prediction success rate when one knows more than only the last outcome (Taken/Not Taken). For example, the knowledge of the last two outcomes of a branch allows a far better guess as to the next outcome. Also, knowing which type of branch it is helps the prediction (i.e., being able to differentiate between a BCTR (Branch on Count Register Instruction) and a BC (Branch Conditional) - or a BC of mask 1 and one with mask 7). The BHT does not provide any information as to what type of branch its entries are. Also, it has been observed that by knowing whether the last n predictions for a given branch were successful or not, one can increase the chances for a correct prediction. The idea set forth is for all the information that allow for a highly accurate prediction of branches to be kept in a table. The table is, as the BHT, accessed by an instruction address at instruction prefetch time.

By contrast to the BHT, if ther...