Entry replacement within a data store

• US 20080183986A1
• Filed: 01/18/2008
• Published: 07/31/2008
• Est. Priority Date: 01/26/2007
• Status: Active Grant

• Current Assignee: Arm Limited (SoftBank Group Corp.)
• Original Assignee: Arm Limited (SoftBank Group Corp.)
• Inventors: Kleanthous, Marios, Yehia, Sami
• Granted Patent: US 8,271,750 B2
• Time in Patent Office: Days
• US Class Current: 711/159
• CPC Class Codes: G06F 12/121 using replacement algorithms
• CPC Class Codes: G06F 12/126 with special data handling, e.g. priority of data or instructions, handling errors or pinning

Abstract

A data processing system 2 includes a data store 14 having storage locations storing entries which can be used for a variety of purposes, such as operand value prediction, branch prediction, etc. An entry profile store 16 stores profile data in respect of more candidate entries than there are storage locations within the data store 14. The profile data is used to determine replacement policy for entries within the data store 14. The profile data 16 can include hash values used to determine whether or not predictions associated with candidate entries were or were not correct without having to store the full predictions within the profile data.

Claims

1. Apparatus for processing data comprising:

a data store having a plurality of storage locations;

an entry profile store of profile data in respect of candidate entries to be stored in storage locations of said data store, said entry profile store serving to store profile data in respect of more candidate entries than there are storage locations within said data store; and

an entry replacer responsive to said profile data stored in said entry profile store in respect of at least a candidate entry and an existing entry to control whether said candidate entry replaces said existing entry within a storage location of said data store;

wherein

said profile data includes performance gain data indicative of performance gains associated with use of respective candidate entries stored within said data store and said entry replacer preferentially stores candidate entries with a high associated performance gain when stored within said data store;

further comprising

a profile data updater to update said performance gain data in dependence upon cycle counts associated with actual use of a candidate entry when not stored within said data store, and to update updates said performance gain data in dependence upon cycle counts associated with actual use of a candidate entry when stored within said data store.

2. Apparatus as claimed in claim 1;

wherein said data store is a translation lookaside buffer indexed with data addresses and said entries are address mapping data.

3. Apparatus as claimed in claim 1, wherein said data store is indexed with program instruction addresses to provide access to entries stored therein.

4. Apparatus as claimed in claim 2, wherein said data store is part of a branch target instruction cache and said storage locations store branch target instructions associated with branch instructions at respective instruction addresses.

5. Apparatus as claimed in claim 2, wherein said data store is part of a branch target buffer and said storage locations store next addresses of instructions following branch instructions at respective instruction addresses.

6. Apparatus as claimed in claim 1, wherein said data store is a prediction memory and said storage locations store prediction data.

7. Apparatus as claimed in claim 6, wherein said prediction memory is part of an operand value predictor and said storage locations store predictions of operand values associated with program instructions at respective instruction addresses.

8. Apparatus as claimed in claim 7, wherein said operand value predictor is a stride value predictor and said storage locations store respective predictions of stride values by which associated operand values change upon each use.

9. Apparatus as claimed in claim 1, wherein said profile data includes frequency data indicative of how frequently respective candidate entries are used and said entry replacer preferentially stores candidate entries with a high frequency of use within said data store.

10. Apparatus as claimed in claim 9, wherein profile data updater updates said frequency data in dependence upon actual use of a candidate entry.

11. Apparatus as claimed in claim 1, wherein said profile data includes confidence data indicative of probabilities of predictions made in dependence upon storing respective candidate entries within said data store being correct and said entry replacer preferentially stores candidate entries with a high probability of resulting in a correct prediction when stored within said data store.

12. Apparatus as claimed in claim 11, wherein said profile data includes predicted hash functions indicative of predicted outcomes that would result from storing respective candidate entries within said data store.

13. Apparatus as claimed in claim 12, wherein a profile data updater compares a predicted hash function stored within said profile data for a candidate entry with a corresponding actual hash function generated in dependence upon processing associated with said candidate entry to generate a result indicate of whether or not a prediction associated with said candidate entry being stored in said data store was correct.

14. Apparatus as claimed in claim 13, wherein said apparatus includes an instruction processing pipeline having a writeback stage and said actual hash value is generated in said writeback stage.

15. Apparatus as claimed in claim 1, wherein said profile data includes program context data indicative of respective contexts in which candidate entries were last used and profile data updating circuitry changes a context value being associated with profile data being updated when an invalid profile data entry or a profile data entry with a different context value is to be updated.

16. Apparatus as claimed in claim 15, wherein said entry replacer preferentially replaces entries within said data store having profile data having a context value different to a current context value.

17. Apparatus as claimed in claim 1, wherein said data store is fully associative such that a candidate entry may be stored within any of said storage locations.

18. Apparatus as claimed in claim 1, wherein said entry profile store is directly mapped such that profile data for a candidate entry may only be stored in one location.

19. A method of processing data comprising the steps of:

storing entries within a data store having a plurality of storage locations;

within an entry profile store, storing profile data in respect of candidate entries to be stored in storage locations of said data store, said entry profile store serving to store profile data in respect of more candidate entries than there are storage locations within said data store; and

in response to said profile data stored in said entry profile store in respect of at least a candidate entry and an existing entry, controlling whether said candidate entry replaces said existing entry within a storage location of said data store;

wherein

said profile data includes performance gain data indicative of performance gains associated with use of respective candidate entries stored within said data store and said controlling preferentially stores candidate entries with a high associated performance gain when stored within said data store; and

further comprising

updating said performance gain data in dependence upon cycle counts associated with actual use of a candidate entry when not stored within said data store; and

updating said performance gain data in dependence upon cycle counts associated with actual use of a candidate entry when stored within said data store.

20. Apparatus for processing data comprising:

data store means having a plurality of storage location means;

entry profile store means for storing profile data in respect of candidate entries to be stored in storage location means of said data store means, said entry profile store means serving to store profile data in respect of more candidate entries than there are storage location means within said data store means; and

entry replacer means responsive to said profile data stored in said entry profile store in respect of at least a candidate entry and an existing entry for controlling whether said candidate entry replaces said existing entry within a storage location means of said data store means;

wherein

said profile data includes performance gain data indicative of performance gains associated with use of respective candidate entries stored within said data store and said controlling preferentially stores candidate entries with a high associated performance gain when stored within said data store;

further comprising

a profile updating means for updating said performance gain data in dependence upon cycle counts associated with actual use of a candidate entry when not stored within said data store; and

for updating said performance gain data in dependence upon cycle counts associated with actual use of a candidate entry when stored within said data store.