Reduced logic level operation folding of context history in a history register in a prediction system for a processor-based system

Patent metadata

Field	Value
Publication number	US-10437592-B2
Application number	US-201715685519-A
Country	US
Kind code	B2
Filing date	Aug 24, 2017
Priority date	Aug 24, 2017
Publication date	Oct 8, 2019
Grant date	Oct 8, 2019

Abstract

Reduced logic level operation folding of context history in a history register in a prediction system for a processor-based system is disclosed. The prediction system includes a prediction circuit employing reduced operation folding of the history register for indexing a prediction table containing prediction values used to process a consumer instruction when value has not yet been resolved. To avoid the requirement to perform successive logic folding operations to produce a folded context history of a resultant reduced bit width, reduced logic level folding operation of the resultant reduced bit width is employed. Reduced logic level folding operation of the resultant reduced bit width involves using current folded context history from previous contents of a history register as basis for determining a new folded context history. In this manner, logic folding of the history register is faster and operates with reduced power consumption as a result of fewer logic operations.

First claim

What is claimed is:

1. A method of folding a context history used to provide a predicted value for an instruction to be executed in an instruction processing system, comprising:
bit field swapping N most significant bits (MSBs) of a current folded context history in a current folded context history register comprising F folded bits of a current context history in a history register having a B bit length, with N least significant bits (LSBs) of the current folded context history to provide a swapped current folded context history;
performing a logic operation on the swapped current folded context history with a logic word comprising N bits of a new context history and N bits of the current context history to generate a new folded context history of F bits;
generating an index based on the new folded context history;
indexing a prediction entry among a plurality of prediction entries in a prediction table circuit corresponding to the index, each of the plurality of prediction entries comprising a predicted value field configured to store a predicted value; and
providing the predicted value from the indexed prediction entry in the prediction table circuit to be used for processing the instruction.

2. The method of claim 1 , comprising performing the logic operation as a single logic operation on the swapped current folded context history with the logic word comprising N LSBs of the new context history and N bits of the current context history to generate the new folded context history of F bits.

3. The method of claim 2 , comprising performing the logic operation on the swapped current folded context history with the logic word comprising N LSBs of the new context history and N MSBs of the current context history starting at bit F−1 of the current context history to generate the new folded context history of F bits.

4. The method of claim 1 , comprising performing the logic operation as a single logic level operation on the swapped current folded context history with the logic word comprising N bits of the new context history and N bits of the current context history to generate the new folded context history of F bits.

5. The method of claim 1 , further comprising not performing successive logic operations on the current context history to generate the new folded context history.

6. The method of claim 1 , comprising performing an exclusive OR (XOR)-based logic operation on the swapped current folded context history with a logic word comprising N LSBs of the new context history and N bits of the current context history to generate the new folded context history of F bits.

7. The method of claim 1 , wherein the new folded context history comprises
g [ F −1:0]= n [ N −1:0]{circumflex over ( )}{ f [ F−N −1:0], f [ F −1: F−N ]}{circumflex over ( )}{ b [ B −1: B−N ], R′b 0},

where:
‘b’ is a First-In-First-Out (FIFO) bitstring;
‘B is a length of b in bits;
‘n’ is a new set of bits to be added to b;
‘N’ is a length of n in bits;
‘f’ is a current folded context history of b;
‘F’ is a length of fin bits;
‘g’ is a new folded context history of b;
‘F’ is also a length of g in bits; and
‘R’ is a fixed number=B % F.

8. The method of claim 1 , further comprising hashing the new folded context history with a current program counter (PC) of the instruction into the index.

9. The method of claim 8 , wherein:
each of the plurality of prediction entries further comprise a tag field configured to store a tag;
further comprising:
hashing the new folded context history with the current PC of the instruction into a search tag; and
determining if the search tag matches the tag in the prediction entry among the plurality of prediction entries corresponding to the index on the index input; and

comprising:
responsive to the search tag matching the tag in the prediction entry among the plurality of prediction entries corresponding to the index on the index input, providing the predicted value from the prediction entry among the plurality of prediction entries corresponding to the index on the index input.

10. The method of claim 1 , wherein:
each of the plurality of prediction entries further comprise a tag field configured to store a tag;
further comprising:
hashing the new folded context history with a current PC of the instruction into a search tag; and
determining if the search tag matches the tag in the prediction entry among the plurality of prediction entries corresponding to the index on the index input; and

comprising:
responsive to the search tag matching the tag in the prediction entry among the plurality of prediction entries corresponding to the index on the index input, providing the predicted value from the prediction entry among the plurality of prediction entries corresponding to the index on the index input.

11. The method of claim 1 , further comprising storing the new folded context history in the current folded context history register.

12. A non-transitory computer-readable medium having stored thereon computer executable instructions which, when executed by a processor, cause the processor to:
bit field swap N most significant bits (MSBs) of a current folded context history in a current folded context history register comprising F folded bits of a current context history in a history register having a B bit length, with N least significant bits (LSBs) of the current folded context history to provide a swapped current folded context history; and
perform a logic operation on the swapped current folded context history with a logic word comprising N bits of a new context history and N bits of the current context history to generate a new folded context history of F bits;
generate an index based on the new folded context history;
index a prediction entry among a plurality of prediction entries in a prediction table circuit corresponding to the index, each of the plurality of prediction entries comprising a predicted value field configured to store a predicted value; and
provide the predicted value from the indexed prediction entry in the prediction table circuit to be used for processing an instruction.

13. The non-transitory computer-readable medium of claim 12 having stored thereon computer executable instructions which, when executed by the processor, cause the processor to perform the logic operation as a single logic operation on the swapped current folded context history with the logic word comprising N bits of the new context history and N bits of the current context history to generate the new folded context history of F bits.

14. The non-transitory computer-readable medium of claim 12 , having stored thereon computer executable instructions which, when executed by the processor, cause the processor to perform the logic operation as a single logic level operation on the swapped current folded context history with the logic word comprising N bits of the new context history and N bits of the current context history to generate the new folded context history of F bits.

15. The non-transitory computer-readable medium of claim 12 , having stored thereon computer executable instructions which, when executed by the processor, further cause the processor to not perform successive logic operations of the current context history to generate the new folded context history.

16. The non-transitory computer-readable medium of claim 12 , having stored thereon computer executable instructions which, when executed by the processor, further cause the processor to hash the new folded context history with a current program counter (PC) of the instruction into the index.

Assignees

• Qualcomm Inc

Inventors

• Krishna Anil
• Yi Yongseok
• Kothinti Naresh Vignyan Reddy

Classifications

• G06F9/3806

  using address prediction, e.g. return stack, branch history buffer · CPC title

• G06F9/3848

  using hybrid branch prediction, e.g. selection between prediction techniques · CPC title

• G06F9/30149

  of variable length instructions · CPC title

• G06F9/3861

  Recovery, e.g. branch miss-prediction, exception handling (error detection or correction G06F11/00) · CPC title

• G06F9/3844 Primary

  using dynamic branch prediction, e.g. using branch history tables · CPC title