Two-level branch prediction cache
AssigneeNexGen, Inc.
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.
Claims31
In a computer system that includes decode logic responsive to encountered instructions having addresses, a branch prediction device comprising:
- a first level branch prediction cache (BPC) 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 set of address bits 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 set of address bits and the given first level BPC entry satisfy a predetermined condition;
- and
- a second level BPC 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 set of address bits of the encountered instruction 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 that includes decode logic responsive to encountered instructions having addresses, a branch prediction device comprising:
- a first level branch prediction cache (BPC) 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 set of address bits of an encountered instruction, and including a first associative memory, said first associative memory enabling a given first level BPC entry to be output in the event that said first set of address bits results in a match associated with said given first level BPC entry;
- and
- a second level BPC 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 set of address bits of the encountered instruction, and including a second memory, said second memory enabling a second level BPC entry to be output for use in the event that said first set of address bits does not result in a match associated with any first level BPC entry.
A branch prediction method comprising:
- providing a first branch prediction cache (BPC);
- providing a second BPC;
- presenting a first set of address bits of an encountered instruction to said first BPC;
- presenting a second set of address bits of the encountered instruction to said second BPC;
- reading a first set of information from said first BPC, if there is a match on said first set of address bits in said first BPC;
- enabling the output of said second BPC, at least if said match in said first BPC does not occur;
- and
- reading a second set of information from said second BPC, at least if said match in said first BPC does not occur.
A branch prediction method comprising:
- providing a first branch prediction cache (BPC);
- providing a second BPC;
- presenting a first set of address bits to said first BPC, said first set of address bits including a first subset of address bits from an input program counter (PC) containing the address of an encountered instruction;
- presenting a second set of address bits to said second BPC, said second set of address bits including a second subset of address bits from the input PC;
- if there is a match on said first set of address bits presented to said first BPC, reading a first set of information from said first BPC, said first set of information including an address of a previously encountered branch instruction, a full target address to which said previously encountered branch instruction last branched, branch history information representing the direction taken during at least one previous execution of said previously encountered branch instruction, and three groups of eight target instruction bytes, said instruction bytes starting at said target address;
- enabling an output of said second BPC;
- and
- if said match does not occur, reading a second set of information from said second BPC.
Dependencies are inferred from the claim text.