Generalized History for Branch Prediction
Original Publication Date: 1982-Jun-01
Included in the Prior Art Database: 2005-Feb-09
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.