PERCEPTRON-BASED BRANCH PREDICTION MECHANISM FOR PREDICTING CONDITIONAL BRANCH INSTRUCTIONS ON A MULTITHREADED PROCESSOR

• US 20110087866A1
• Filed: 10/14/2009
• Published: 04/14/2011
• Est. Priority Date: 10/14/2009
• Status: Active Grant

• Current Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Barreh, Jama I., Grohoski, Gregory F., Shah, Manish K., Golla, Robert T.
• Granted Patent: US 8,904,156 B2
• Time in Patent Office: Days
• US Class Current: 712/239
• CPC Class Codes: G06F 9/383 Operand prefetching cache prefetching G06F12/0862
• CPC Class Codes: G06F 9/3836 Instruction issuing, e.g. dynamic instruction scheduling or out of order instruction execution
• CPC Class Codes: G06F 9/384 Register renaming
• CPC Class Codes: G06F 9/3848 using hybrid branch prediction, e.g. selection between prediction techniques
• CPC Class Codes: G06F 9/3851 from multiple instruction streams, e.g. multistreaming

Abstract

A multithreaded microprocessor includes an instruction fetch unit including a perceptron-based conditional branch prediction unit configured to provide, for each of one or more concurrently executing threads, a direction branch prediction. The conditional branch prediction unit includes a plurality of storages each including a plurality of entries. Each entry may be configured to store one or more prediction values. Each prediction value of a given storage may correspond to at least one conditional branch instruction in a cache line. The conditional branch prediction unit may generate a separate index value for accessing each storage by generating a first index value for accessing a first storage by combining one or more portions of a received instruction fetch address, and generating each other index value for accessing the other storages by combining the first index value with a different portion of direction branch history information.

Claims

1. A multithreaded microprocessor comprising:

an instruction fetch unit configured to fetch and maintain a plurality of instructions belonging to one or more threads; and

one or more execution units configured to concurrently execute the one or more threads;

wherein the instruction fetch unit includes a conditional branch prediction unit configured to provide, for each of the one or more threads, a direction branch prediction in response to receiving an instruction fetch address of a current conditional branch instruction, wherein the conditional branch prediction unit includes;

a plurality of storages each including a plurality of entries, wherein each entry is configured to store one or more prediction values, and each prediction value of a given storage corresponds to at least one conditional branch instruction in a cache line; and

a control unit coupled to the plurality of storages and configured to generate a separate index value for accessing each storage, wherein the control unit is configured to generate a first index value for accessing a first storage by combining one or more portions of the instruction fetch address, and to generate each other index value for accessing each other respective storage by combining the first index value with a different portion of direction branch history information for each storage.

2. The processor as recited in claim 1, wherein the branch prediction unit further includes a second plurality of storages each corresponding to a respective thread of the one or more threads for storing the direction branch history information, wherein each of the second plurality of storages is configured to store a plurality of direction results of previously executed conditional branch instructions for the corresponding thread.

3. The processor as recited in claim 1, wherein to provide each direction branch prediction, the control unit is configured to sum together the prediction values from each of the plurality of storages that correspond to a same conditional branch instruction.

4. The processor as recited in claim 1, wherein each prediction value represents a probability of a particular conditional branch instruction that is associated with a currently executing thread of the one or more threads being taken.

5. The processor as recited in claim 1, wherein a direction branch prediction corresponding to a zero or a positive number corresponds to a taken branch.

6. The processor as recited in claim 1, wherein in response to determining a given direction branch prediction for a particular conditional branch instruction is inaccurate, the control unit is configured to update each prediction value corresponding to the particular conditional branch prediction.

7. The processor as recited in claim 1, wherein in response to determining a given direction branch prediction for a particular conditional branch instruction is inaccurate, the control unit is configured to decrement each prediction value corresponding to the particular conditional branch prediction if the given direction branch prediction inaccurately predicted a taken branch, and to increment each prediction value corresponding to the particular conditional branch prediction if the given direction branch prediction inaccurately predicted a not taken branch.

8. The processor as recited in claim 1, wherein in response to determining a given direction branch prediction for a particular conditional branch instruction is below a minimum threshold value, the control unit is configured to update each prediction value corresponding to the particular conditional branch instruction.

9. The processor as recited in claim 1, wherein in response to determining a given direction branch prediction for a particular conditional branch instruction is below a minimum threshold value, the control unit is configured to decrement each prediction value corresponding to the particular conditional branch instruction if the given direction branch prediction is an accurately predicted not taken branch, and to increment each prediction value corresponding to the particular conditional branch instruction if the given direction branch prediction is an accurately predicted taken branch.

10. The processor as recited in claim 1, wherein each of the plurality of storages comprises a memory array having independently accessible banks, wherein two or more banks are concurrently accessible.

11. The processor as recited in claim 10, wherein each of the plurality of storages includes a decode unit configured to detect a collision in which a read operation and a write operation are directed to a same bank, and in response to detecting the collision, the decode unit is configured to allow the write operation to occur, and to force read data to be all zeroes.

12. The processor as recited in claim 11, wherein in response to detecting that the read operation and the write operation are directed to a same address, the decode unit is further configured to allow the write operation to occur and to provide write data as read data.

13. A method comprising:

an instruction fetch unit fetching a plurality of instructions belonging to one or more threads;

one or more execution units concurrently executing the instructions from the one or more threads;

a direction branch prediction unit providing for each of the one or more threads, a direction branch prediction for one or more conditional branch instructions in a cache line in response to receiving an instruction fetch address of a current conditional branch instruction;

a control unit storing within each entry of a plurality of storages, one or more prediction values, wherein each prediction value of a given storage corresponds to at least one conditional branch instruction in the cache line; and

the control unit generating a separate index value for accessing each storage, wherein the control unit further generating a first index value for accessing a first storage by combining one or more portions of the instruction fetch address, and generating each other index value for accessing each other respective storage by combining the first index value with a different portion of direction branch history information for each storage.

14. The method as recited in claim 13, further comprising the fetch unit storing the direction branch history information within a second plurality of storages, wherein each of the second plurality of storages corresponds to a respective thread of the one or more threads, wherein the direction branch history information comprises a plurality of direction results of previously executed conditional branch instructions for the corresponding thread.

15. The method as recited in claim 13, further comprising the control unit summing together the prediction values from each of the plurality of storages that correspond to a same conditional branch instruction to provide each direction branch prediction.

16. The method as recited in claim 13, further comprising the control unit concurrently accessing two or more of a plurality of independently accessible banks of each of the plurality of storages.

17. The method as recited in claim 13, further comprising in response to the control unit detecting a collision in which a read operation and a write operation are directed to a same bank, the decode unit allowing the write operation to occur, and forcing read data to be all zeroes.

18. A system comprising:

a multithreaded processor including a plurality of multithreaded processor cores, wherein each multithreaded processor core includes;

an instruction fetch unit configured to fetch and maintain a plurality of instructions belonging to one or more threads; and

one or more execution units configured to concurrently execute the one or more threads;

wherein the instruction fetch unit includes a conditional branch prediction unit configured to provide for each of the one or more threads, a direction branch prediction for one or more conditional branch instructions in a cache line in response to receiving an instruction fetch address of a current conditional branch instruction, wherein the conditional branch prediction unit includes;

a plurality of storages each including a plurality of entries, wherein each entry is configured to store one or more prediction values, and each prediction value of a given storage corresponds to at least one conditional branch instruction in the cache line; and

a control unit coupled to the plurality of storages and configured to generate a separate index value for accessing each storage, wherein the control unit is configured to generate a first index value for accessing a first storage by combining one or more portions of the instruction fetch address, and to generate each other index value for accessing each other respective storage by combining the first index value with a different portion of direction branch history information for each storage.

19. The system as recited in claim 18, wherein the branch prediction unit further includes a second plurality of storages each corresponding to a respective thread of the one or more threads for storing the direction branch history information, wherein each of the second plurality of storages is configured to store a plurality of direction results of previously executed conditional branch instructions for the corresponding thread.

20. The system as recited in claim 18, wherein to provide each direction branch prediction, the control unit is configured to sum together the prediction values from each of the plurality of storages that correspond to a same conditional branch instruction.