METHOD TO IMPROVE BRANCH PREDICTION LATENCY

• US 20100037036A1
• Filed: 08/06/2008
• Published: 02/11/2010
• Est. Priority Date: 08/06/2008
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Gao, Hongliang, Hum, Herbert
• Granted Patent: US 8,151,096 B2
• Time in Patent Office: Days
• US Class Current: 712/205
• CPC Class Codes: G06F 9/3844 using dynamic branch prediction, e.g. using branch history tables

Abstract

An apparatus to generate a branch prediction of an instruction based at least in part on the address of the previous branch instruction, wherein the previous instruction is prior to the instruction in a program order. The prediction can also based on a branch history value with respect to the previous branch instruction and one or more previous branch predictions.

Claims

1. A processor comprising

a fetch unit to fetch instructions from a memory;

a first buffer to store one or more branch predictions correspond to one or more branch instructions including a first instruction;

a second buffer to store at least a part of an address of the first instruction; and

a branch prediction logic to generate a branch prediction of a second instruction based at least in part on the address of the first instruction, wherein the first instruction is prior to the second instruction in a program order.

2. The processor defined in claim 1, wherein the branch prediction of the second instruction is further based on the one or more branch predictions and a branch history value with respect to the first instruction.

3. The processor defined in claim 1, wherein the branch prediction logic comprises a prediction table to store a first plurality of prediction entries, wherein the prediction table is accessed using a branch history value with respect to the first instruction and at least the part of the address of the first instruction without using a part of an address of the second instruction.

4. The processor defined in claim 3, wherein the branch prediction logic is operable to update an actual direction of the second instruction to the prediction table.

5. The processor defined in claim 1, wherein a prediction process of a second instruction begins before a decoding process of the second instruction begins.

6. The processor defined in claim 1, wherein the branch prediction of the second instruction is available by the end of a second clock cycle of a decoding process of the second instruction.

7. The processor defined in claim 1, wherein the branch prediction logic will restore at least the part of the address of the first instruction to the second buffer if the first instruction is mispredicted, wherein the branch prediction logic will replace a branch prediction corresponds to the first instruction in the first buffer with an actual direction of the first instruction.

8. The processor defined in claim 1, wherein a prediction process of the second instruction is N clock cycles in length, the first instruction is a (N−

1)th branch instruction prior to the second instruction in the program order, wherein N is an integer larger than 1.

9. The processor defined in claim 8, wherein the branch prediction logic stores at least the part of the address of the first instruction to the second buffer at least (N−

2) clock cycles before a decoding process of the second instruction begins.

10. The processor defined in claim 8, wherein the first buffer can store at least (N−

1) branch predictions correspond to the one or more plurality of instructions.

11. The processor defined in claim 8, wherein at least 2^N-1 entries from a prediction table are accessed, based at least in part on the address of the first instruction and a branch history value with respect to the first instruction, before a decoding process of a second instruction begins.

12. A method to perform branch prediction comprising:

reading a first plurality of entries from a first prediction table based at least in part on an address of a first branch instruction and a branch history value with respect to the first branch instruction;

selecting a first entry from the first plurality of entries based at least on a branch prediction of the first branch instruction; and

generating a branch prediction of a second branch instruction based at least on the first entry, wherein the first branch instruction is prior to the second branch instruction in a program order.

13. The method defined in claim 12, further comprising:

storing one or more branch predictions that correspond to one or more branch instructions including the first branch instruction to a first buffer; and

storing at least a part of the address of the first branch instruction to a second buffer.

14. the method defined in claim 12, further comprising:

updating the first prediction table if an actual direction of the second branch instruction is available.

15. The method defined in claim 12, wherein the reading and the selecting are performed without using a part of an address of the second branch instruction.

16. The method defined in claim 12, further comprising:

decoding the second branch instruction over multiple clock cycles, wherein the branch prediction of the second branch instruction is available before the end of a second clock cycle of the multiple clock cycles.

17. The method defined in claim 12, further comprising:

reading a second plurality of entries from a second prediction table based at least in part on the address of the first branch instruction and the branch history value with respect to the first branch instruction; and

selecting a second entry from the second plurality of entries based at least on the branch prediction of the first branch instruction, wherein the branch prediction of the second branch instruction is generated based at least on the first entry and the second entry.

18. The method defined in claim 13, further comprising:

restoring at least the part of the address of the first branch instruction to the second buffer if the first branch instruction is mispredicted; and

replacing the branch prediction of the first branch instruction in the first buffer with an actual direction of the first branch instruction if the first branch instruction is mispredicted.

19. The method defined in claim 13, wherein the reading, the selecting and the generating operations altogether is N clock cycles in length, wherein the first branch instruction is a (N−

1)th branch instruction prior to the second branch instruction in the program order, wherein N is an integer larger than 1.

20. The method defined in claim 19, further comprising:

decoding the second branch instruction, wherein the storing at least the part of the address of the first branch instruction to the second buffer is performed at least (N−

2) clock cycles before the decoding of the second branch instruction begins.

21. The method defined in claim 19, wherein the first buffer can store at least (N−

1) branch predictions.

22. The method defined in claim 19, wherein at least 2^N-1 entries from the prediction table are accessed.

23. A system for branch prediction comprising:

an instruction fetch unit to receive instructions from a memory;

an instruction decoding unit to decode the instruction;

a first register to store one or more branch predictions correspond to one or more branch instructions including a first branch instruction;

a second register to store at least a part of an address of the first branch instruction; and

a branch prediction unit to generate a branch prediction of a second instruction based at least in part on the address of the first branch instruction, wherein the first branch instruction is prior to the second instruction in a program order.

24. The system defined in claim 23, wherein the branch prediction of the second instruction is further based on the one or more branch predictions and a branch history value with respect to the first branch instruction.

25. The system defined in claim 23, wherein the branch prediction unit comprises a prediction table to store a plurality of prediction entries, wherein the prediction table is accessed using a branch history value with respect to the first branch instruction and at least the part of the address of the first branch instruction without using a part of an address of the second instruction.