Back to results
US 7,069,426 B1Granted
Branch predictor with saturating counter and local branch history table with algorithm for updating replacement and history fields of matching table entries
AssigneeIntel Corporation
InventorVincent E. Hummel
Life of this patent
Estimating the term…
Abstract
An embodiment of the invention is directed to a dynamic branch prediction method in which a first taken/not-taken prediction is provided responsive to an address using a saturating counter branch predictor. A second taken/not-taken prediction responsive to the address resulting in a hit in a local branch history table is provided. In addition, a hit/miss indication for the address is provided. The second prediction is selected for the address if the indication is a hit, and the first prediction is selected if the indication is a miss.
Claims17
A method comprising:
- providing a first taken/not-taken prediction responsive to an address using a saturating counter branch predictor;
- providing (1) a second taken/not-taken prediction responsive to the address resulting in a hit in a local branch history table, and (2) a hit/miss indication for the address, wherein the second prediction is generated by a decision function that accepts, as an input, a history value from a matching entry of the local branch history table and produces, as an output, the second prediction, the decision function being implemented by combinational logic that has no memory so as to reduce on-chip area;
- selecting for the address one of (1) the second prediction if the indication is a hit, and (2) the first prediction if the indication is a miss;
- updating a replacement field for the matching entry in the local branch history table only if the first prediction was incorrect;
- and
- updating a history field for the matching entry in the local branch history table with the outcome of an executed branch instruction only if the first prediction was incorrect and the second prediction was correct.
3 more elements
A processor comprising:
- an instruction pointer (IP) generator capable of providing an address;
- saturating counter branch prediction (SCBP) logic having an input coupled to the IP generator and capable of providing a first taken/not-taken prediction at an output responsive to the address;
- local branch history prediction (LBHP) logic having an input coupled to the IP generator and capable of providing (1) a second taken/not-taken prediction at an output responsive to the address resulting in a hit, and (2) a hit/miss indication for the address, wherein the LBHP logic includes (1) at least one local branch history table to provide a taken/not-taken history from a matching entry in said table in response to said hit and (2) combinational logic that is predetermined at the time the processor is built to implement, without memory, a decision function whose output is the second prediction based on the taken/not-taken history;
- a multiplexer having an input coupled to the outputs of the SCBP and LBHP logic and a select input coupled to receive the hit/miss indication and in response provide (1) the second prediction if there is a hit and (2) the first prediction if there is a miss;
- and
- logic to update a replacement field for said matching entry only if the first prediction is incorrect and to update a history field for said matching entry with the outcome of an executed branch instruction only if the first prediction is incorrect and the second prediction is correct.
3 more elements
An apparatus comprising:
- means for providing an address of at least one instruction;
- means for providing a first taken/not-taken branch prediction based upon the current state of a state machine and responsive to the address;
- local branch history prediction (LBHP) logic having an input coupled to the address providing means and capable of providing (1) a second taken/not-taken prediction at an output responsive to the address resulting in a hit, and (2) a hit/miss indication for the address, wherein the LBHP logic includes at least one local branch history prediction table to provide a taken/not-taken history from a history field of a matching entry in said table in response to said hit and means for generating, without memory the second prediction based on the taken/not-taken history;
- and
- a multiplexer having an input coupled to the first prediction means and the output of the LBHP logic and a select input coupled to receive the hit/miss indication and in response provide (1) the second prediction if there is a hit and (2) the first prediction if there is a miss;
- means for updating said history field, with the outcome of an executed branch instruction that is pointed to by said address, only if the first prediction is incorrect and the second prediction is correct.
3 more elements
A method comprising:
- providing a first taken/not-taken prediction responsive to an address using a saturating counter branch predictor;
- providing a second taken/not-taken prediction responsive to the address resulting in a hit in a local branch history table, wherein the second prediction is generated using a decision function that is provided with a taken/not-taken history value from a history field of a matching entry of the local branch history table and produces, as output, the second prediction, the decision function being implemented by combinational logic that has no counter or state machine;
- selecting for the address one of the first prediction and the second prediction depending on whether or not the address resulted in said hit;
- updating a replacement field, for an existing entry in the local branch history table that includes a history field containing a plurality of taken/not-taken outcomes of one or more previously executed branch instructions associated with said address, only if the first prediction is incorrect;
- and
- updating said history field based on an outcome of an executed branch instruction that is pointed to by said address, only if the first prediction is incorrect and the second prediction is correct.
3 more elements
Dependencies are inferred from the claim text.