INVALIDATION OF INDEX ITEMS FOR A TEMPORARY DATA STORE

• US 20150169452A1
• Filed: 12/02/2014
• Published: 06/18/2015
• Est. Priority Date: 12/16/2013
• Status: Active Grant

• Current Assignee: Arm Limited (SoftBank Group Corp.)
• Original Assignee: Arm Limited (SoftBank Group Corp.)
• Inventors: PERSSON, Erik, HUGOSSON, Ola
• Granted Patent: US 9,471,493 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 12/0808 with cache invalidating means G06F12/0815 takes precedence
• CPC Class Codes: G06F 12/0895 of parts of caches, e.g. directory or tag array

Abstract

A data processing apparatus and corresponding method of data processing are provided. The data processing apparatus comprises a temporary data store configured to store data items retrieved from a memory, wherein the temporary data store selects one of its plural data storage locations in which to store a newly retrieved data item according to a predetermined circular sequence. An index data store is configured to store index items corresponding to the data items stored in the temporary data store, wherein presence of a valid index item in the index data store is indicative of a corresponding data item in the temporary data store. Invalidation control circuitry performs a rolling invalidation process with respect to the index items stored in the index data store, comprising sequentially processing the index items stored in the index data store and selectively marking the index items as invalid according to a predetermined criterion.

Claims

1. A data processing apparatus comprising:

a temporary data store configured to store data items retrieved from a memory, wherein the temporary data store has plural data storage locations configured to store the data items and the temporary data store is configured to select a storage location of the plural data storage locations in which to store a newly retrieved data item according to a predetermined circular sequence of the plural data storage locations;

an index data store configured to store index items corresponding to the data items stored in the temporary data store, wherein presence of a valid index item in the index data store is indicative of a corresponding data item in the temporary data store; and

invalidation control circuitry configured to perform a rolling invalidation process with respect to the index items stored in the index data store, wherein the rolling invalidation process comprises sequentially processing the index items stored in the index data store and selectively marking the index items as invalid according to a predetermined criterion.

2. The data processing apparatus as claimed in claim 1, wherein the invalidation control circuitry is configured, when performing the rolling invalidation process, such that the predetermined criterion is fulfilled if a duration for which a selected index item has been stored in the index data store exceeds a predetermined period.

3. The data processing apparatus as claimed in claim 2, wherein the invalidation control circuitry is configured to determine the duration for which the selected index item has been stored in the index data store with reference to a count of a number of index items which have been stored in the index data store since the selected index item was stored in the index data store.

4. The data processing apparatus as claimed in claim 2, wherein the rolling invalidation process comprises two steps, wherein at a first step of the two steps the selected index item is read from the index data store and at a second step of the two steps the selected index item is marked as invalid if a duration for which the selected index item has been stored in the index data store exceeds a predetermined period.

5. The data processing apparatus as claimed in claim 4, wherein a single step of the two steps is performed each time a new index item is stored in the index data store.

6. The data processing apparatus as claimed in claim 1, wherein the invalidation control circuitry is configured to sequentially perform the rolling invalidation process with respect to a further predetermined circular sequence of storage locations of the index items stored in the index data store.

7. The data processing apparatus as claimed in claim 1, wherein the index data store is configured to store a sequence number in association with each of the index items, wherein the sequence number is incremented for each new index item stored in the index data store.

8. The data processing apparatus as claimed in claim 7, wherein the invalidation control circuitry is configured, when performing the rolling invalidation process, such that the predetermined criterion is fulfilled if a duration for which a selected index item has been stored in the index data store exceeds a predetermined period, and wherein the data processing apparatus is configured to determine the duration for which a selected index item has been stored in the index data store with reference to the sequence number stored in association with the selected data item.

9. The data processing apparatus as claimed in claim 7, wherein the data processing apparatus is configured, when access to a selected data item in the memory is required, to determine with reference to the index items in the index data store if the selected data item is stored in the temporary data store, and, if it is determined that the selected data item is stored in the temporary data store, to determine a storage location of the selected data item in the temporary data store with reference to the sequence number.

10. The data processing apparatus as claimed in claim 9, wherein the data processing apparatus is configured to determine the storage location of the selected data item in the temporary data store using a calculation dependent on the sequence number and a modulo of a number of the plural data storage locations in the temporary data store.

11. The data processing apparatus as claimed in claim 10, wherein the data processing apparatus further comprises a counter configured to wrap around at the number of the plural data storage locations in the temporary data store, wherein the counter is incremented for each new index item stored in the index data store, and wherein the storage location of the selected data item in the temporary data store is calculated as a current value of the counter minus a duration for which the selected index item has been stored in the index data store modulo the number of the plural data storage locations in the temporary data store.

12. The data processing apparatus as claimed in claim 1 wherein the data processing apparatus is configured, when access to a selected data item in the memory is required, to determine with reference to the index items in the index data store if the selected data item is stored in the temporary data store, and, if it is determined that the selected data item is stored in the temporary data store, to determine if a duration for which the selected index item has been stored in the index data store exceeds a predetermined period, and, if the duration for which the selected index item has been stored in the index data store exceeds the predetermined period, to cause the selected data item to be retrieved from the memory.

13. The data processing apparatus as claimed in claim 1, wherein the data processing apparatus is configured, when access to a selected data item in the memory is required, to determine with reference to the index items in the index data store if the selected data item is stored in the temporary data store, and if a selected index item corresponding to the selected data item is marked as invalid, to cause the selected data item to be retrieved from the memory.

14. The data processing apparatus as claimed in claim 2, wherein a number of the plural data storage locations in the temporary data store is greater than a number of index items corresponding to the predetermined period.

15. The data processing apparatus as claimed in claim 2, wherein the data processing apparatus is configured, when it is determined that the newly retrieved data item must be retrieved from the memory to the temporary data store, to delay the retrieval until a previous data item stored in the storage location has been stored in the temporary data store for longer than the predetermined period.

16. The data processing apparatus as claimed in claim 1, wherein the data items are portions of a reference frame of video data.

17. The data processing apparatus as claimed in claim 16, wherein each index item is stored in the index data store at a location given by a hash of at least one identifier associated with the corresponding portion of the reference frame.

18. The data processing apparatus as claimed in claim 17, wherein the at least one identifier comprises at least one of:

coordinate value information, a reference frame identifier, and information regarding a storage location in the memory.

19. A data processing apparatus comprising:

means for storing data items retrieved from a memory, wherein the means for storing data items has plural data storage locations configured to store the data items;

means for selecting a storage location of the plural data storage locations in which to store a newly retrieved data item according to a predetermined circular sequence of the plural data storage locations;

means for storing index items corresponding to the data items stored in the means for storing data items, wherein presence of a valid index item in the means for storing index items is indicative of a corresponding data item in the means for storing data items; and

means for performing a rolling invalidation process with respect to the index items stored in the means for storing index items, wherein the rolling invalidation process comprises sequentially processing the index items stored in the means for storing index items and selectively marking the index items as invalid according to a predetermined criterion.

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

storing data items retrieved from a memory in plural data storage locations configured to store the data items;

selecting a storage location of the plural data storage locations in which to store a newly retrieved data item according to a predetermined circular sequence of the plural data storage locations;

storing index items corresponding to the data items stored in the plural data storage locations, wherein presence of a valid stored index item is indicative of a corresponding data item in the plural data storage locations; and

performing a rolling invalidation process with respect to the stored index items, wherein the rolling invalidation process comprises sequentially processing the stored index items and selectively marking the index items as invalid according to a predetermined criterion.