Branch prediction within a multithreaded processor

• US 20070288735A1
• Filed: 06/09/2006
• Published: 12/13/2007
• Est. Priority Date: 06/09/2006
• Status: Active Grant

• Current Assignee: Arm Ltd. (United Kingdom) (SoftBank Group Corp.)
• Original Assignee: Arm Ltd. (United Kingdom) (SoftBank Group Corp.)
• Inventors: Vasekin, Vladimir, Biles, Stuart David, Levdik, Yuri, Kapustin, Andrei
• Granted Patent: US 7,877,587 B2
• Time in Patent Office: Days
• US Class Current: 712/239
• CPC Class Codes: G06F 9/30101 Special purpose registers
• 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
• CPC Class Codes: G06F 9/3851 from multiple instruction streams, e.g. multistreaming

Abstract

A branch prediction mechanism 16, 18 within a multithreaded processor having hardware scheduling logic 6, 8, 10, 12 uses a shared global history table 18 which is indexed by respective branch history registers 20, 22 for each program thread. Different mappings are used between preceding branch behaviour and the prediction value stored within respective branch history registers 20, 22. These different mappings may be provided by inverters placed into the shift in paths for the branch history registers 20, 22 or by adders 40, 42 or in some other way. The different mappings help to equalise the probability of use of the particular storage locations within the global history table 18 such that the plurality of program threads are not competing excessively for the same storage locations corresponding to the more commonly occurring patterns of preceding branch behaviour.

Claims

1. Apparatus for processing data, said apparatus comprising:

a multithreaded processor having a hardware scheduling mechanism for interleaving execution of program instructions from a plurality of program threads; and

a branch prediction mechanism having;

(i) a plurality of branch history registers each storing a prediction index that is a representation of preceding branch behaviour for a respective program thread of said plurality of program threads;

(ii) a global history table shared between said plurality of program threads and having a plurality of storage locations storing predictions of branch behaviour, said plurality of storage locations being indexed in dependence upon a prediction index for a currently active program thread; and

(iii) mapping logic providing different mappings for different program threads between storage locations of predictions within said plurality of storage locations and preceding branch behaviour represented by respective prediction indices.

2. Apparatus as claimed in claim 1, wherein said mapping performed by said mapping logic is such that a probability of use to store a prediction of each of said plurality of storage locations, when summed for all of said plurality of program threads, is substantially uniform between said plurality of storage locations.

3. Apparatus as claimed in claim 1, wherein said mapping logic provides a one-to-one mapping between preceding branch behaviour and prediction index for each of said plurality of program threads.

4. Apparatus as claimed in claim 1, wherein said mapping logic maps preceding branch behaviour into a different prediction index for each different program thread.

5. Apparatus as claimed in claim 4, wherein said mapping logic maps a given preceding branch behaviour into respective different prediction indices such that each prediction index has an individual pattern of bit inversions with respect to all other of said prediction indices.

6. Apparatus as claimed in claim 4, wherein said mapping logic adds a different offset to each prediction index stored in a respective one of said plurality of branch history registers.

7. A method of processing data, said method comprising the steps of:

interleaving execution of program instructions from a plurality of program threads using a hardware scheduling mechanism controlling a multithreaded processor; and

predicting branch behaviour by;

(i) storing a prediction index that is a representation of preceding branch behaviour for a respective program thread of said plurality of program threads within a respective one of a plurality of branch history registers;

(ii) storing predictions of branch behaviour within a global history table shared between said plurality of program threads and having a plurality of storage locations, said plurality of storage locations being indexed in dependence upon a prediction index for a currently active program thread; and

(iii) performing different mappings for different program threads between storage locations of predictions within said plurality of storage locations and preceding branch behaviour represented by respective prediction indices.

8. A method as claimed in claim 7, wherein said mapping performed is such that a probability of use to store a prediction of each of said plurality of storage locations, when summed for all of said plurality of program threads, is substantially uniform between said plurality of storage locations.

9. A method as claimed in claim 7, wherein said mapping provides a one-to-one mapping between preceding branch behaviour and prediction index for each of said plurality of program threads.

10. A method as claimed in claim 7, wherein said mapping maps preceding branch behaviour into a different prediction index for each different program thread.

11. A method as claimed in claim 10, wherein said mapping maps a given preceding branch behaviour into respective different prediction indices such that each prediction index has an individual pattern of bit inversions with respect to all other of said prediction indices.

12. A method as claimed in claim 10, wherein said mapping adds a different offset to each prediction index stored in a respective one of said plurality of branch history registers.

13. Apparatus for processing data, said apparatus comprising:

multithreaded processor means having hardware scheduling means for interleaving execution of program instructions from a plurality of program threads; and

branch prediction means having;

(i) a plurality of branch history register means each for storing a prediction index that is a representation of preceding branch behaviour for a respective program thread of said plurality of program threads;

(ii) a global history table means shared between said plurality of program threads and having a plurality of storage locations for storing predictions of branch behaviour, said plurality of storage locations being indexed in dependence upon a prediction index for a currently active program thread; and

(iii) mapping means for providing different mappings for different program threads between storage locations of predictions within said plurality of storage locations and preceding branch behaviour represented by respective prediction indices.