Method and apparatus for reducing cache pollution

• US 6,516,388 B1
• Filed: 09/15/2000
• Issued: 02/04/2003
• Est. Priority Date: 09/15/2000
• Status: Expired due to Term

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Company (HP Inc.)
• Inventors: McCormick, James E. Jr., Undy, Stephen R.
• Primary Examiner(s): Nguyen, Hiep T.
• Application Number:
  US09/662,295
• Time in Patent Office: 872 Days
• Field of Search: 711/122, 711/134, 711/136, 711/128
• US Class Current: 711/136
• CPC Class Codes: G06F 12/0862 with prefetch
• CPC Class Codes: G06F 12/123 with age lists, e.g. queue, most recently used [MRU] list or least recently used [LRU] list

Abstract

In a cache which writes new data over less recently used data, methods and apparatus which dispense with the convention of marking new cache data as most recently used. Instead, non-referenced data is marked as less recently used when it is written into a cache, and referenced data is marked as more recently used when it is written into a cache. Referenced data may correspond to fetch data, and non-referenced data may correspond to prefetch data. Upon fetch of a data value from the cache, its use status may be updated to more recently used. The methods and apparatus have the affect of preserving (n−1)/n of a cache'"'"'s entries for the storage of fetch data, while limiting the storage of prefetch data to 1/n of a cache'"'"'s entries. Pollution which results from unneeded prefetch data is therefore limited to 1/n of the cache. In reality, however, pollution from unneeded prefetch data will be significantly less, as many prefetch data values will ultimately be fetched prior to their overwrite with new data, and upon their fetch, their use status can be upgraded to most recently used, thus ensuring their continued maintenance in the cache.

Claims

1. A method for reducing cache pollution, comprising:

a) marking non-referenced data as less recently used when it is written into a cache;

b) marking referenced data as more recently used when it is written into the cache;

c) upon fetch of a data value from the cache, updating its use status to more recently used; and

d) when new data is written into the cache, writing new data over data which is marked as less recently used.

2. A method as in claim 1, wherein the non-referenced data is marked as least recently used when it is written into the cache, and the referenced data is marked as most recently used when it is written into the cache.

3. A method as in claim 1, wherein the new data is written over data marked as least recently used.

4. A method as in claim 1, further comprising:

a) storing prefetch data in a buffer;

b) initially marking prefetch data stored in the buffer as non-referenced;

c) upon fetch of data from the buffer, marking the fetched data as referenced; and

d) periodically writing data stored in the buffer into the cache.

5. A method as in claim 4, further comprising:

a) storing fetch data in the buffer; and

b) initially marking fetch data stored in the buffer as referenced.

6. A method as in claim 1, wherein the status of a data value which is fetched from the cache is updated to most recently used.

7. A method as in claim 6, wherein:

a) the non-referenced data is marked as least recently used when it is written into the cache;

b) the referenced data is marked as most recently used when it is written into the cache; and

c) the new data is written over data marked as least recently used;

the method further comprising;

d) storing fetch and prefetch data in a buffer;

e) initially marking fetch data stored in the buffer as referenced;

f) initially marking prefetch data stored in the buffer as non-referenced;

g) upon fetch of data from the buffer, marking the fetched data as referenced; and

h) periodically writing data stored in the buffer into the cache.

8. A pollution reducing cache structure, comprising:

a) a cache comprising data entries and temporal use entries;

b) means for updating at least one temporal use entry upon a write of data into a data entry, wherein the at least one temporal use entry is updated to;

i) mark non-referenced data as less recently used; and

ii) mark referenced data as more recently used; and

c) means for reading a number of temporal use entries from the cache during a write operation, for identifying a data entry which is marked as less recently used by said number of temporal use entries, and for causing new data to be written into said identified data entry.

9. A pollution reducing cache structure as in claim 8, wherein:

a) the cache is an n-way, set-associative cache; and

b) one temporal use entry corresponds to each set of n data entries in the cache, wherein each temporal use entry specifies a pattern of more/less recently used statuses for a particular set of n data entries.

10. A pollution reducing cache structure as in claim 8, wherein:

a) the cache is an n-way, set-associative cache; and

b) one temporal use entry corresponds to each set of n data entries in the cache, wherein each bit of a particular temporal use entry specifies a temporal use relationship between two data values stored in a different two of the cache'"'"'s n ways.

11. A pollution reducing cache structure as in claim 8, further comprising:

a) a buffer;

b) means for initially marking prefetch data stored in the buffer as non-referenced;

c) means for marking data fetched from the buffer as referenced; and

d) a bus for transferring data values and their corresponding reference statuses from the buffer to the cache.

12. A pollution reducing cache structure as in claim 11, further comprising means for initially marking fetch data stored in the buffer as referenced.

13. A pollution reducing cache, comprising:

a) a plurality of data arrays and a data status array, wherein bit patterns stored in the data status array indicate a temporal use order of corresponding data values stored in the plurality of data arrays;

b) logic which, upon a write of new data into the cache, addresses a bit pattern and its corresponding data values; and

c) logic for updating said addressed bit pattern, said logic comprising;

i) an input for receiving a reference status of said new data;

ii) an input for receiving an indication as to which data value of said addressed data values said new data is to overwrite; and

iii) an output which provides an updated bit pattern in response to the logic'"'"'s inputs, wherein said updated bit pattern;

A) marks said new data as being more recently used if said reference status is “

referenced”

; and

B) marks said new data as being less recently used if said reference status is “

non-referenced”

.

14. A pollution reducing cache as in claim 13, wherein:

a) the cache is an n-way, set-associative cache; and

b) each bit pattern corresponds to a set of n data entries in the cache.

15. A pollution reducing cache as in claim 14, wherein each bit in a particular bit pattern specifies a temporal use relationship between two data values stored in a different two of the cache'"'"'s n-ways.

16. A pollution reducing cache as in claim 13, further comprising a number of enable lines coupled between the logic for updataing the addressed bit pattern and the data status array, wherein said logic for updating the addressed bit pattern asserts ones of the number of enable lines to update particular bits of said addressed bit pattern in a write-only fashion.

17. A pollution reducing cache as in claim 13, wherein the logic for updating the addressed bit pattern further comprises an input for receiving said addressed bit pattern.

18. A pollution reducing cache as in claim 13, wherein the cache is an instruction cache, and wherein each data value stored in the cache comprises one or more instructions.

19. A pollution reducing cache as in claim 13, wherein the output of the logic for updating the addressed bit pattern marks said new data as being most recently used if said reference status is “

referenced”

, and marks said new data as being least recently used if said reference status is “

non-referenced”

.

20. A pollution reducing cache as in claim 19, wherein:

a) the cache is an n-way, set-associative cache;

b) each bit pattern corresponds to a set of n data entries in the cache;

c) each bit in a particular bit pattern specifies a temporal use relationship between two data values stored in a different two of the cache'"'"'s n-ways; and

d) the cache further comprises a number of enable lines coupled between the logic for updating the addressed bit pattern and the data status array, wherein said logic for updating the addressed bit pattern asserts ones of the number of enable lines to update particular bits of said addressed bit pattern in a write-only fashion.