Improving hit rate of code translation redirection table with replacement strategy based on usage history table of evicted entries

Patent metadata

Field	Value
Publication number	US-9880846-B2
Application number	US-201213444673-A
Country	US
Kind code	B2
Filing date	Apr 11, 2012
Priority date	Apr 11, 2012
Publication date	Jan 30, 2018
Grant date	Jan 30, 2018

Abstract

In one embodiment, a micro-processing system includes a hardware structure disposed on a processor core. The hardware structure includes a plurality of entries, each of which are associated with portion of code and a translation of that code which can be executed to achieve substantially equivalent functionality. The hardware structure includes a redirection array that enables, when referenced, execution to be redirected from a portion of code to its counterpart translation. The entries enabling such redirection are maintained within or evicted from the hardware structure based on usage information for the entries.

First claim

The invention claimed is:

1. A micro-processing system including a microprocessor and associated memory system, comprising:
a hardware structure on a core of the microprocessor;
a plurality of entries in the hardware structure, each entry being associated with a translation of a corresponding code portion, the translation being executable by the microprocessor in lieu of the corresponding code portion to achieve substantially equivalent functionality;
a redirection array in the hardware structure that includes, for each entry, redirection information usable to cause execution to be redirected from the corresponding code portion to the translation for that corresponding code portion;
a history data structure that tracks a history of a value of an access bit, wherein the history data structure has more entries than the hardware redirector and is analyzed to increase hit rate of the redirection array; and
an access array in the hardware structure that includes usage information that varies in response to the entries being used to redirect execution, where specific entries are maintained within or evicted from the hardware structure based on the usage information for those entries.

2. The micro-processing system of claim 1 , further comprising management software that repeatedly samples values in the access array and controls whether specific entries are maintained within or evicted from the hardware structure based on how frequently those entries were used to redirect execution to translations.

3. The micro-processing system of claim 1 , further comprising management software that repeatedly samples values in the access array and controls whether specific entries are maintained within or evicted from the hardware structure based on how recently those entries were used to redirect execution to translations.

4. The micro-processing system of claim 1 , further comprising management software that repeatedly samples values in the access array and controls whether specific entries are maintained within or evicted from the hardware structure based on how frequently and how recently those entries were used to redirect execution to translations.

5. The micro-processing system of claim 1 , further comprising a hardware decoder on the core of the microprocessor, where if a selected code portion does not have an entry in the hardware structure, that selected code portion is executed by the microprocessor using the hardware decoder, and where if the selected code portion does have an entry in the hardware structure, its corresponding translation is executed by the microprocessor without using the hardware decoder.

6. The micro-processing system of claim 1 , where the usage information in the access array includes, for each entry, an access bit which is a binary indication of whether or not the entry has been used to redirect execution to a translation.

7. The micro-processing system of claim 6 , where the micro-processing system is operative to (1) set the access bits in the access array when their corresponding entries are used to redirect execution to translations; and (2) clear the access bits between times when they have been set.

8. The micro-processing system of claim 7 , further comprising management software that repeatedly samples and clears the access bits to generate a history of access bit values over time, the management software being further operative to control whether a selected entry is maintained within or evicted from the hardware structure based on the history of the access bit associated with that entry.

9. The micro-processing system of claim 8 , where the management software is operative to control whether the selected entry is maintained within or evicted from the hardware structure based on one or more of how recently and how frequently the entry is used to redirect execution to the associated translation, as reflected in the history of the access bit.

10. The micro-processing system of claim 1 , where the usage information in the access array includes, for each entry, a count of how many times the entry has been used to redirect execution to a translation.

11. The micro-processing system of claim 1 , where the usage information in the access array includes, for each entry, a time when the entry was used to redirect execution to a translation.

12. In a processing pipeline having a hardware decoder disposed on a core of a microprocessor, a method of alternatively processing in a translation mode that omits use of the hardware decoder, or in a hardware decoder mode that makes use of the hardware decoder, the method comprising:
generating a plurality of translations, each translation being executable in the translation mode in lieu of executing a corresponding code portion in the hardware decoder mode, to achieve substantially equivalent functionality;
inserting, into a hardware structure on the core of the microprocessor, a plurality of entries, where each entry (1) is associated with one of the translations and its corresponding code portion, (2) includes redirection information usable during a fetch operation to cause execution to be redirected to the associated translation from its corresponding code portion;
inserting usage information into the hardware structure, where the usage information varies in response to the entries being used to redirect execution;
inserting history information regarding a value of an access bit, wherein the history information has more entries than the usage information and is analyzed to increase hit rate of a redirection array; and
maintaining or evicting specific entries from the hardware structure based on analysis of the usage information.

13. The method of claim 12 , where maintaining or evicting specific entries from the hardware structure is performed based on how frequently those entries were used to redirect execution, as determined by the analysis of the usage information.

14. The method of claim 12 , where maintaining or evicting specific entries from the hardware structure is performed based on how recently those entries were used to redirect execution, as determined by the analysis of the usage information.

15. The method of claim 12 , where maintaining or evicting specific entries from the hardware structure is performed based on how frequently and how recently those entries were used to redirect execution, as determined by the analysis of the usage information.

16. The method of claim 12 , where the usage information includes, for each entry in the hardware structure, an access bit which is a binary indication of whether the entry has been used to redirect execution.

17. The method of claim 16 , further comprising repeatedly sampling and clearing the access bits to generate a history of access bit values over time for each entry, where maintaining or evicting specific entries from the hardware structure is based on analysis of the history of access bit values over time for those entries.

18. The method of claim 17 , where the history of access bit values for each entry includes at least one of (1) how frequently the entry was used to redirect execution; (2) how recently the entry was used to redirect execution; (3) a count of how many times the entry was used to redirect execution; and (4) a time when the entry was used to redirect execution.

19. A micro-processing system including a microprocessor and associated memory system, comprising:
a hardware structure on a core of the microprocessor;
a plurality of entries in the hardware structure, each entry being associated with a translatio

Assignees

• Tuck Nathan
• Segelken Ross
• Nvidia Corp

Inventors

• Tuck Nathan
• Segelken Ross

Classifications

• G06F9/3017

  Runtime instruction translation, e.g. macros · CPC title

• G06F9/30174

  for non-native instruction set, e.g. Javabyte, legacy code · CPC title

• G06F9/4552

  Involving translation to a different instruction set architecture, e.g. just-in-time translation in a JVM · CPC title

• G06F9/3808 Primary

  for instruction reuse, e.g. trace cache, branch target cache · CPC title