Branch target address cache

• US 7,783,870 B2
• Filed: 08/13/2007
• Issued: 08/24/2010
• Est. Priority Date: 08/13/2007
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Zhang, Lixin, Levitan, David S., Speight, William E.
• Primary Examiner(s): Li; Aimee J
• Application Number:
  US11/837,893
• Publication Number:
  US 20090049286A1
• Time in Patent Office: 1,107 Days
• Field of Search: 712/234, 712/237, 712/238, 712/239
• US Class Current: 712/238
• CPC Class Codes: G06F 9/3804 for branches, e.g. hedging, branch folding
• CPC Class Codes: G06F 9/3806 using address prediction, e.g. return stack, branch history buffer
• CPC Class Codes: G06F 9/3844 using dynamic branch prediction, e.g. using branch history tables
• CPC Class Codes: G06F 9/3848 using hybrid branch prediction, e.g. selection between prediction techniques

Abstract

A processor includes an execution unit and instruction sequencing logic that fetches instructions from a memory system for execution. The instruction sequencing logic includes branch logic that outputs predicted branch target addresses for use as instruction fetch addresses. The branch logic includes a level one branch target address cache (BTAC) and a level two BTAC each having a respective plurality of entries each associating at least a tag with a predicted branch target address. The branch logic accesses the level one and level two BTACs in parallel with a tag portion of a first instruction fetch address to obtain a first predicted branch target address from the level one BTAC for use as a second instruction fetch address in a first processor clock cycle and a second predicted branch target address from the level two BTAC for use as a third instruction fetch address in a later second processor clock cycle.

Claims

1. A processor, comprising:

at least one execution unit that executes instructions; and

instruction sequencing logic, coupled to the at least one execution unit, that fetches instructions from a memory system for execution by the at least one execution unit, said instruction sequencing logic including a branch logic that outputs predicted branch target addresses for use as instruction fetch addresses, said branch logic including a level one branch target address cache (BTAC) and a level two BTAC each having a respective plurality of entries each associating at least a tag with a predicted branch target address;

wherein said branch logic accesses the level one BTAC and the level two BTAC in parallel with at least a tag portion of a first instruction fetch address to obtain a first predicted branch target address from the level one BTAC and a second predicted branch target address from the level two BTAC;

wherein the instruction sequencing logic fetches instructions from the memory system utilizing the first predicted branch target address as a second instruction fetch address in a first processor clock cycle and fetches instructions from the memory system utilizing the second predicted branch target address as a third instruction fetch address in a second processor clock cycle subsequent to the first processor clock cycle.

2. The processor of claim 1, wherein:

the level one BTAC has a single cycle access latency.

3. The processor of claim 1, wherein:

said branch logic includes N levels of BTAC, wherein N is an integer greater than or equal to two; and

each of the N levels of BTAC has a respective access latency different from that of each other level of BTAC.

4. The processor of claim 3, wherein the branch logic, if the N levels of BTAC output multiple different predicted branch target addresses identifying multiple different instruction fetch blocks in a same processor clock cycle, selects a predicted branch target address output by a highest level of BTAC to be presented as an instruction fetch address.

5. The processor of claim 3, wherein:

the at least one execution unit includes a branch execution unit that executes branch instructions;

the branch execution unit reports outcomes of executed branch instructions to the branch logic; and

the branch logic inserts a new branch target address prediction into a selected level among the N levels of BTAC based upon the reported outcome of an executed branch instruction.

6. The processor of claim 5, wherein:

the branch logic includes a buffer that holds at least one previous instruction fetch address; and

the branch logic selects the selected level based upon availability in the buffer of a particular previous instruction fetch address corresponding to the new branch target address prediction.

7. The processor of claim 1, wherein:

the branch logic includes branch direction prediction logic; and

the branch logic invalidates a branch target address prediction residing in a selected level among the N levels of BTAC based upon a branch direction prediction of the branch direction prediction logic.

8. The processor of claim 1, wherein:

the memory system includes a cache memory within the processor; and

the instruction sequencing logic accesses the level one BTAC, the level two BTAC, and the cache memory concurrently with the first instruction fetch address.

9. A data processing system, comprising:

the processor of claim 1;

an interconnect coupled to the processor; and

the memory system coupled to the interconnect.

10. A method of data processing in a processor including at least one execution unit and an instruction sequencing logic containing branch logic, the branch logic including a level one branch target address cache (BTAC) and a level two BTAC, said method comprising:

fetching a first instruction from a memory system for execution by at least one execution unit of the processor utilizing a first instruction fetch address;

the branch logic accessing the level one BTAC and the level two BTAC in parallel with at least a tag portion of the first instruction fetch address;

in response to said accessing;

outputting a first predicted branch target address from the level one BTAC;

outputting a second predicted branch target address from the level two BTAC; and

fetching a second instruction from the memory system utilizing the first predicted branch target address as a second instruction fetch address in a first processor clock cycle and fetching a third instruction from the memory system utilizing the second predicted branch target address as a third instruction fetch address in a second processor clock cycle subsequent to the first processor clock cycle.

11. The method of claim 10, wherein said first processor clock cycle immediately follows a previous clock cycle in which the branch logic accesses the level one BTAC.

12. The method of claim 10, wherein:

said branch logic includes N levels of BTAC, wherein N is an integer greater than or equal to two; and

each of the N levels of BTAC has a respective access latency different from that of each other level of BTAC.

13. The method of claim 12, and further comprising:

said level two BTAC outputting a third predicted branch target address in the first processor clock cycle; and

the branch logic selecting the first predicted branch target address output by the level one BTAC rather than said third predicted branch target address as said second instruction fetch address, wherein the first and third predicted branch target addresses identify different instruction fetch blocks.

14. The method of claim 12, wherein the at least one execution unit includes a branch execution unit that executes branch instructions, said method comprising:

the branch execution unit reporting outcomes of executed branch instructions to the branch logic; and

the branch logic inserting a new branch target address prediction into a selected level among the N levels of BTAC based upon the reported outcome of an executed branch instruction.

15. The method of claim 14, wherein the branch logic includes a buffer that holds at least one previous instruction fetch address, said method comprising:

the branch logic selecting the selected level based upon availability in the buffer of a particular previous instruction fetch address corresponding to the new branch target address prediction.

16. The method of claim 10, wherein the branch logic includes branch direction prediction logic, said method further comprising:

the branch logic invalidating a branch target address prediction residing in a selected level among the N levels of BTAC based upon a branch direction prediction of the branch direction prediction logic.

17. The method of claim 10, wherein the memory system includes a cache memory within the processor, said accessing further comprising:

accessing the level one BTAC, the level two BTAC, and the cache memory concurrently with the first instruction fetch address.