Two-level branch prediction cache
AssigneeNexgen Microsystems
InventorsDavid R. Stiles, John G. Favor, Korbin S. Van Dyke
Life of this patent
Estimating the term…
Abstract
An improved branch prediction cache (BPC) scheme that utilizes a hybrid cache structure. The BPC provides two levels of branch information caching. The fully associative first level BPC is a shallow but wide structure (36 32-byte entries), which caches full prediction information for a limited number of branch instructions. The second direct mapped level BPC is a deep but narrow structure (256 2-byte entries), which caches only partial prediction information, but does so for a much larger number of branch instructions. As each branch instruction is fetched and decoded, its address is used to perform parallel look-ups in the two branch prediction caches.
Claims12
In a computer system that includes an instruction cache and decode logic responsive to fetched instructions, a branch prediction cache (BPC) structure comprising:
- a first level BPC, separate from the instruction cache, having a first number N1 of lines for storing prediction information on up to N1 previously encountered branch instructions, each line in said first level BPC being configured to store an entry providing prediction information at a first level of detail, said first level BPC being responsive to a first subset of address bits from an input program counter (PC) containing the address of an encountered instruction, and including first means for enabling a given first level BPC entry to be output in the event that said first subset of address bits and the given first level BPC entry satisfy a predetermined condition;
- and
- a second level BPC, separate from the instruction cache, having a second number N2 of lines, larger than said first number of lines, for storing prediction information on up to N2 previously encountered branch instructions, each line in said second level BPC being configured to store an entry providing prediction information at a second level of detail, lower than said first level of detail, said second level BPC being responsive to a second subset of address bits from the input PC, and including second means for enabling a second level BPC entry to be output for use in the event that said predetermined condition is not met.
In a computer system having decode logic responsive to fetched instructions and an instruction cache from which instructions, including branch instructions, are fetched for execution, the improvement comprising:
- means for generating an input program counter (PC) representative of the address of an encountered instruction;
- a first level branch prediction cache (BPC), separate from the instruction cache, having a first number N1 of lines for storing prediction information on up to N1 previously encountered branch instructions, each line being configured to store an entry providing prediction information at a first level of detail including the address of the branch instruction for which prediction information is stored, a target address for the branch instruction, target bytes corresponding to the instruction stream starting at the target address, and branch history information representing the direction taken during at least one previous execution of the branch instruction;
- means, associated with said first level BPC, for comparing the input PC with the address of the branch instruction in each of the first level BPC entries, and, in the event of a match between the input PC and the address of the branch instruction in the first level BPC entry, for enabling a first level BPC entry to be output and target bytes in the first level BPC entry to be communicated to the decode logic;
- and
- a second level BPC, separate from the instruction cache, having a second number N2 of lines, larger than said first number of lines, for storing prediction information on up to N2 previously encountered branch instructions each line being configured to store an entry providing prediction information at a second level of detail, lower than said first level of detail, including a portion of a target instruction address and branch history information representing the direction taken during at least one previous execution of the branch instruction for which prediction information is stored, said second level BPC being indexed by only a portion of the input PC so as to provide a second level BPC entry for use in the event that no match occurs between the input PC and the address of the branch instruction in any of the first level BPC entries.
In the operation of a computer system wherein instructions, including branch instructions, are fetched for execution, a method of predicting branch outcome, comprising the steps of:
- generating an input PC representative of the address of an encountered instruction;
- providing a first level BPC, separate from an instruction cache, having a first number of lines;
- storing in each of at least some of the lines of the first level BPC respective entries providing information corresponding to respective previously encountered branch instructions, each entry including the address of the respective branch instruction, a target address for the respective branch instruction, and branch history information representing the direction taken during at least one previous execution of the respective branch instruction;
- comparing the input PC with the address of the branch instruction in each of the first level BPC entries, and, in the event of a match between the PC and the address of the branch instruction for a particular first level BPC entry, enabling the particular first level BPC entry to be output;
- providing a second level BPC, separate from the instruction cache, having a second number, larger than said first number, of lines;
- storing in each of at least some of the lines of the second level BPC respective entries providing information corresponding to respective previously encountered branch instructions, each entry including a portion of a target instruction address and branch history information representing the direction taken during at least one previous execution of the branch instruction, the second level BPC being indexed by only a portion of the input PC;
- and
- enabling a second level BPC entry indexed by the portion of the input PC to be output for use in the event that no match exists in the first level BPC.
Dependencies are inferred from the claim text.