System for passing an index value with each prediction in forward direction to enable truth predictor to associate truth value with particular branch instruction

• US 6,081,887 A
• Filed: 11/12/1998
• Issued: 06/27/2000
• Est. Priority Date: 05/13/1998
• Status: Expired due to Fees

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Compaq Computer Corporation (HP Inc.)
• Inventors: Steely, Simon C. Jr., McLellan, Edward J., Emer, Joel S.
• Primary Examiner(s): An, Meng-Ai T.
• Assistant Examiner(s): PATEL, GAUTAM
• Application Number:
  US09/191,869
• Time in Patent Office: 593 Days
• Field of Search: 712/234, 712/233, 712/236, 712/239, 712/240, 712/235, 712/237, 712/238
• US Class Current: 712/239
• CPC Class Codes: G06F 9/3844 using dynamic branch prediction, e.g. using branch history tables

Abstract

A technique for predicting the result of a conditional branch instruction for use with a processor having instruction pipeline. A stored predictor is connected to the front end of the pipeline and is trained from a truth based predictor connected to the back end of the pipeline. The stored predictor is accessible in one instruction cycle, and therefore provides minimum predictor latency. Update latency is minimized by storing multiple predictions in the front end stored predictor which are indexed by an index counter. The multiple predictions, as provided by the back end, are indexed by the index counter to select a particular one as current prediction on a given instruction pipeline cycle. The front end stored predictor also passes along to the back end predictor, such as through the instruction pipeline, a position value used to generate the predictions. This further structure accommodates ghost branch instructions that turn out to be flushed out of the pipeline when it must be backed up. As a result, the front end always provides an accurate prediction with minimum update latency.

Claims

1. A branch predictor for use with a data processor which includes an instruction pipeline wherein multiple conditional branch instructions are pending at the same time in various stages, the branch predictor apparatus comprising:

(a) a stored predictor, connected to a fetch stage of the instruction pipeline, the stored predictor accepting a stored predictor input value, and providing as an output a stored prediction value to enable the instruction pipeline to continue processing of a particular conditional branch instruction, the stored predictor further comprising;

(ii) an index counter associated with each one of a plurality of fetch program counter values of the particular conditional branch instruction, each index counter containing an index counter value indicating one of several candidate predictions to use for a next serial instance of the same conditional branch instruction; and

(iii) a storage array containing a number of addressable locations corresponding to the number of index counters, wherein each location in the storage array stores the multiple candidate predictions;

(b) a truth based predictor, connected to a retire stage of the instruction pipeline, the retire stage occurring after the fetch stage, the truth based predictor accepting a truth based predictor input value and a truth value indicating the actual result of the particular conditional branch instruction, and providing a truth based prediction value of the next execution instance of the particular conditional branch instruction as an output, and

the index counters being connected to the instruction pipeline so that the stored predictor passes to the truth based predictor, through the instruction pipeline, in a forward direction from the fetch stage towards the retire stage an index counter value used with each prediction, to enable the truth based predictor to associate the truth value with a particular conditional branch instruction.

2. An apparatus as in claim 1 wherein the stored predictor input value is a program counter location of the particular conditional branch instruction in the fetch stage.

3. An apparatus as in claim 1 wherein the truth based predictor input value is a retire stage program counter value.

4. An apparatus as in claim 1 wherein the stored predictor provides the stored prediction value within a time frame associated with one cycle time of the instruction pipeline.

5. An apparatus as in claim 1 wherein the multiple predictions are stored in each location and represent predictions for multiple serial instances of the particular conditional branch instruction.

6. An apparatus as in claim 1 wherein the index counter value indicates which prediction to use for the next serial instance of the particular conditional branch instruction.

7. An apparatus as in claim 1 wherein the truth based predictor makes multiple predictions and the stored predictor uses them serially.

8. An apparatus as in claim 1 wherein the multiple conditional branch instructions may be processed by the retire stage of the instruction pipeline in an order which is different from the order in which they are processed by the fetch stage of the instruction pipeline.

9. A branch predictor for use with a data processor which includes an instruction pipeline wherein multiple conditional branch instructions are pending at the same time in various stages, the branch predictor apparatus comprising:

(a) a stored predictor, connected to a fetch stare of the instruction pipeline, the stored predictor accepting a stored predictor input value, and providing as an output a stored prediction value to enable the instruction pipeline to continue processing of a particular conditional branch instruction, the stored predictor further comprising;

(ii) an index counter associated with each one of a plurality of fetch program counter values of the particular conditional branch instruction, each index counter containing an index counter value indicating one of several candidate predictions to use for a next serial instance of the same conditional branch instruction; and

(iii) a storage array containing a number of addressable locations corresponding to the number of index counters, wherein each location in the storage array stores the multiple candidate predictions;

(b) a truth based predictor, connected to a retire stage of the instruction pipeline, the retire stage occurring after the fetch stage, the truth based predictor accepting a truth based predictor input value and a truth value indicating the actual result of the particular conditional branch instruction, and providing a truth-based prediction value of the next execution instance of the particular conditional branch instruction as an output; and

such that the index counters are connected to the instruction pipeline so that a given index counter value is passed through the instruction pipeline in a forward direction from the stored predictor to the truth based predictor, to enable the truth-based predictor to associate the truth value with a particular conditional branch instruction, and so that the index counter value is available to be used to order the multiple prediction values provided from the truth based predictor to the stored predictor.

10. A method for branch prediction for use within a data processor that uses an instruction pipeline wherein multiple instructions are pending at the same time in various stages the method of branch prediction comprising the steps of:

(a) providing a stored prediction value, from the fetch stage of the instruction pipeline, the stored prediction value enabling the instruction pipeline to continue processing of a particular conditional branch instruction, the step of providing a stored prediction value further comprising the steps of;

(i) providing an index counter value associated with each one of the plurality of possible fetch program counter values of the particular conditional branch instruction, each index counter value indicating one of several candidate predictions to use for a next serial instance of the same conditional branch instruction;

(ii) storing in a number of addressable locations in a storage array the multiple candidate predictions;

(b) determining a truth-based prediction value of the next execution instance of the conditional branch instruction, the determining step made from the contents of a retire stage of the instruction pipeline, and the retire stage occuring after the fetch stage, and the truth-based prediction value depending upon a truth value indicating an actual result of the conditional branch instruction,

(c) passing an index counter value used with each prediction through the instruction pipeline to the step of determining a truth-based prediction value, the index counter values passing through the instruction pipeline in a forward direction from the fetch stage towards the retire stage, to enable the step of determining a truth-based prediction value to associate the truth value with a particular conditional branch instruction.

11. A method as in claim 10 wherein the stored predictor value is determined from a program counter value of the particular conditional branch instruction located in a fetch stage in the instruction pipeline.

12. A method as in claim 10 wherein the truth based predictor value also depends upon a retire program counter value provided by a fetch stage of the instruction pipeline.

13. A method as in claim 10 wherein the step of providing a stored prediction value determines the prediction value within a time frame associated with one cycle time of the instruction pipeline.

14. A method as in claim 10 wherein the multiple predictions represent predictions for multiple serial instances of the same conditional branch instruction.

15. A method as in claim 10 wherein the index counter value indicates which prediction to use for the next serial instance of the particular conditional branch instruction.

16. A method as in claim 10 wherein the truth based predictor makes multiple predictions and the stored predictor uses them serially.

17. A method as in claim 10 wherein the multiple conditional branch instructions may be processed by the retire stage of the instruction pipeline in an order which is different from the order in which they are processed by the fetch stage of the instruction pipeline.

18. A method for branch prediction for use within a data processor that uses an instruction pipeline wherein multiple instructions are pending at the same time in various stages, the method of branch prediction comprising the steps of:

(a) providing a stored prediction value, from the fetch stage of the instruction pipeline, the stored prediction value enabling the instruction pipeline to continue processing of a particular conditional branch instruction, the step of providing a stored prediction value further comprising the steps of;

(i) providing an index counter value associated with each one of the plurality of possible fetch program counter values of the particular conditional branch instruction, each index counter value indicating one of several candidate predictions to use for a next serial instance of the same conditional branch instruction;

(ii) storing, in a number of addressable locations in a storage array, the multiple candidate predictions;

(b) determining a truth-based prediction value of the next execution instance of the conditional branch instruction, the determining step made from the contents of a retire stage of the instruction pipeline, and the retire stage occuring after the fetch stage, and the truth-based prediction value depending upon a truth value indicating an actual result of the conditional branch instruction;

(c) passing the index counter value through the instruction pipeline such that a given index counter value is passed through the instruction pipeline in a forward direction from the stored predictor to the truth based predictor, to enable the truth-based predictor to associate the truth value with a particular conditional branch instruction; and

(d) ordering the the multiple prediction values provided from the truth-based predictor to the stored predictor according to the index counter value.