Performance of a cache by detecting cache lines that have been reused

• US 20060224830A1
• Filed: 03/30/2005
• Published: 10/05/2006
• Est. Priority Date: 03/30/2005
• Status: Active Grant

• Current Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Original Assignee: International Business Machines Corporation
• Inventors: Tast, Hans-Werner, Davis, Gordon T., Leon, Santiago A.
• Granted Patent: US 7,380,065 B2
• Time in Patent Office: Days
• US Class Current: 711/136
• CPC Class Codes: G06F 12/127 using additional replacement algorithms

Abstract

A method and system for improving the performance of a cache. The cache may include an array of tag entries where each tag entry includes an additional bit (“reused bit”) used to indicate whether its associated cache line has been reused, i.e., has been requested or referenced by the processor. By tracking whether a cache line has been reused, data (cache line) that may not be reused may be replaced with the new incoming cache line prior to replacing data (cache line) that may be reused. By replacing data in the cache memory that might not be reused prior to replacing data that might be reused, the cache hit may be improved thereby improving performance.

Claims

1. A method for improving the performance of a cache comprising the steps of:

receiving a request of an address of data;

determining if said requested data is located in said cache;

setting a bit in a tag associated with a cache line to a second state if said requested data is located within said cache line of said cache, wherein said bit indicates whether said cache line has been reused;

wherein said cache line is grouped with other cache lines in a congruence class, wherein each cache line in said congruence class is associated with a tag containing a bit indicating whether its associated cache line has been reused; and

resetting said bit for one of said cache lines in said congruence class if a number of cache lines in said congruence class identified as being reused exceeds a threshold.

2. The method as recited in claim 1 further comprising the step of:

modifying a field of said tag associated with said cache line to indicate said cache line is most recently used, wherein said field is configured to track a least recently used status of said cache line.

3. The method as recited in claim 2 further comprising the step of:

adjusting least recently used statuses of said other cache lines in said congruence class.

4. The method as recited in claim 1 further comprising the step of:

leaving said bit in said tag associated with said cache line to remain in a first state if said request is a write request.

5. The method as recited in claim 1 further comprising the step of:

hashing said address to select said congruence class.

6. The method as recited in claim 5 further comprising the steps of:

selecting a least recently used cache line in said congruence class with said bit in said tag associated with said least recently used cache line indicating said least recently used cache line has not been reused;

invaliding current contents of said selected least recently used cache line; and

loading new data in said selected least recently used cache line.

7. The method as recited in claim 6 further comprising the step of:

clearing said bit in said tag associated with said selected least recently used cache line.

8. The method as recited in claim 5 further comprising the step of:

selecting a least recently used cache line in said congruence class with said bit in said tag associated with said least recently used cache line indicating said least recently used cache line has been reused if there are no cache lines in said congruence class that has not been reused.

9. A system, comprising:

a processor, wherein said processor has a cache associated with it;

a system memory for storing data of said processor;

a bus system coupling said processor to said system memory;

wherein said cache comprises;

a data array comprising a plurality of congruence classes, wherein each of said congruence classes groups a plurality of cache lines;

a tag array comprising a plurality of tags, wherein each of said plurality of tags is associated with one of said plurality of cache lines, wherein each of said plurality tags comprises a bit used to indicate whether its associated cache line has been reused;

logic for receiving a request of an address of data;

logic determining if said requested data is located in said cache;

logic for setting said bit in said tag associated with a cache line in a congruence class to a second state if said requested data is located within said cache line of said cache; and

logic for resetting said bit for one of said plurality of cache lines in said congruence class if a number of cache lines in said congruence class identified as being reused exceeds a threshold.

10. The system as recited in claim 9, wherein each of said plurality of tags comprises a field used to indicate a least recently used status of its associated cache line, wherein said cache further comprises:

logic for modifying said field of said tag associated with said cache line to indicate said cache line is most recently used.

11. The system as recited in claim 10, wherein said cache further comprises:

logic for adjusting least recently used statuses of other cache lines in said congruence class.

12. The system as recited in claim 9, wherein said cache further comprises:

logic for leaving said bit in said tag associated with said cache line to remain in a first state if said request is a write request.

13. The system as recited in claim 9, wherein said cache further comprises:

logic for hashing said address to select said congruence class.

14. The system as recited in claim 13, wherein said cache further comprises:

logic for selecting a least recently used cache line in said congruence class with said bit in said tag associated with said least recently used cache line indicating said least recently used cache line has not been reused;

logic for invaliding current contents of said selected least recently used cache line; and

logic for loading new data in said selected least recently used cache line.

15. The system as recited in claim 14, wherein said cache further comprises:

logic for clearing said bit in said tag associated with said selected least recently used cache line.

16. The system as recited in claim 13, wherein said cache further comprises:

logic for selecting a least recently used cache line in said congruence class with said bit in said tag associated with said least recently used cache line indicating said least recently used cache line has been reused if there are no cache lines in said congruence class that has not been reused.