System, method and computer program product for executing a cache replacement algorithm

• US 7,711,904 B2
• Filed: 03/22/2007
• Issued: 05/04/2010
• Est. Priority Date: 03/22/2007
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Lynch, Daniel N., Puzak, Thomas R., Emma, Philip G.
• Primary Examiner(s): Nguyen; Hiep T
• Application Number:
  US11/689,592
• Publication Number:
  US 20080235453A1
• Time in Patent Office: 1,139 Days
• Field of Search: None
• US Class Current: 711/136
• CPC Class Codes: G06F 12/0862 with prefetch
• CPC Class Codes: G06F 12/0897 with two or more cache hierarchy levels with multilevel cache hierarchies G06F12/0811
• CPC Class Codes: G06F 12/127 using additional replacement algorithms

Abstract

A system, method and computer program product for executing a cache replacement algorithm. A system includes a computer processor having an instruction processor, a cache and one or more useful indicators. The instruction processor processes instructions in a running program. The cache includes two or more cache levels including a level one (L1) cache level and one or more higher cache levels. Each cache level includes one or more cache lines and has an associated directory having one or more directory entries. A useful indicator is located within one or more of the directory entries and is associated with a particular cache line. The useful indicator is set to provide an indication that the associated cache line contains one or more instructions that are required by the running program and cleared to provide lack of such an indication.

Claims

1. A computer processor comprising:

an instruction processor for processing instructions in a running program;

a cache comprising two or more cache levels including a level one (L1) cache level and one or more higher cache levels, each cache level comprising one or more cache lines and having an associated directory having one or more directory entries;

a useful indicator within one or more of said directory entries and associated with a particular cache line, each useful indicator being set to provide an indication that the associated cache line contains one or more instructions that are required by the running program and cleared to provide lack of such an indication; and

a cache line fetch mechanism which utilizes the useful indicators to suppress prefetches from the higher cache levels to the L1 cache.

2. The computer processor of claim 1 wherein one of or more of the useful indicators are modified upon full completion of an instruction.

3. The computer processor of claim 1 wherein one of the useful indicators is modified when placing a cache line into the L1 cache level.

4. The computer processor of claim 3 wherein the modification includes the setting of the useful indicator to a one for a demand fetch and to a zero for a speculative fetch.

5. The computer processor of claim 1 wherein the useful indicator comprises a single bit.

6. The computer processor of claim 1 wherein the directory entries include a plurality of useful indicators including the useful indicator.

7. The computer processor of claim 1 further comprising a least recently used (LRU) mechanism for ordering recency of use of cache lines.

8. The computer processor of claim 7 wherein the directory entries include a plurality of useful indicators including the useful indicator and the computer processor further comprises a cache line replacement mechanism which utilizes the useful indicators and the LRU mechanism to avoid replacing lines that have historically proven to be useful.

9. A method of executing a cache replacement algorithm, the method comprising:

determining placement of a selected cache line in a cache that comprises two or more cache levels including a L1 cache and one or more higher level cache levels, each cache level comprising a plurality of cache lines and having an associated directory having a plurality of directory entries corresponding to the cache lines, the directory entries including useful indicators and the determining responsive to a useful indicator associated with the selected cache line;

suppressing prefetches from the higher cache levels to the L1 cache when the useful indicator is set to zero indicating that the cache line is not useful;

placing prefetches from the higher cache levels to the L1 cache when the useful indicator is set to one indicating that the cache line is useful; and

updating one or more of the useful indicators in response to a system event.

10. The method of claim 9 wherein the useful indicator associated with the selected cache line indicates if the selected cache line has been accessed.

11. The method of claim 9 further comprising utilizing the useful indicators and an LRU mechanism to implement a cache line replacement algorithm.

12. The method of claim 9 wherein the system event is a full completion of an instruction that has accessed the selected cache line.

13. The method of claim 9 wherein each of the useful indicators comprise a single bit.

14. The method of claim 9 wherein the cache includes a L1 cache and a L2 cache and the determining includes:

receiving a L1 cache miss for a target cache line, the cache miss being a speculative miss or a demand miss;

if the L1 cache miss is a demand miss and the target cache line is located in the L2 cache, then installing the target cache line into the L1 cache and setting an associated useful indicator to one;

if the L1 cache miss is a demand miss and the target cache line is not located in the L2 cache, then installing the target cache line into the L2 cache and setting the associated useful indicator to one;

if the L1 cache miss is a speculative miss and the target cache line is not located in the L2 cache, then installing the target cache line into the L2 cache and setting the associated useful indicator to zero; and

if the L2 cache miss is a speculative miss and the target cache line is located in the L2 cache with the associated useful indicator equal to one, then installing the target cache line in the L1 cache and setting the associated useful indicator to zero.

15. A computer program product for executing a cache replacement algorithm, the computer program product comprising:

a storage medium readable by a processing circuit and storing instructions for execution by the processing circuit for facilitating a method comprising;

determining placement of a selected cache line in a cache that comprises two or more cache levels including a L1 cache and one or more higher level cache levels, each cache level comprising a plurality of cache lines and having an associated directory having a plurality of directory entries corresponding to the cache lines, the directory entries including useful indicators and the determining responsive to a useful indicator associated with the selected cache line;

suppressing prefetches from the higher cache levels to the L1 cache when the useful indicator is set to zero indicating that the cache line is not useful;

placing prefetches from the higher cache levels to the L1 cache when the useful indicator is set to one indicating that the cache line is useful; and

updating one or more of the useful indicators in response to a system event.

16. The computer program product of claim 15 wherein the useful indicator indicates if the selected cache line has been accessed.

17. The computer program product of claim 15 wherein the method further comprises utilizing the useful indicators and an LRU mechanism to implement a cache line replacement algorithm.

18. The computer program product of claim 15 wherein the system event is a full completion of an instruction that has accessed the selected cache line.

19. The computer program product of claim 15 wherein the useful indicator comprises a single bit.

20. The computer program product of claim 15 wherein the cache includes a L1 cache and a L2 cache and the determining includes:

receiving a L1 cache miss for a target cache line, the cache miss being a speculative miss or a demand miss;

if the L1 cache miss is a demand miss and the target cache line is located in the L2 cache, then installing the target cache line into the L1 cache and setting an associated useful indicator to one;

if the L1 cache miss is a demand miss and the target cache line is not located in the L2 cache, then installing the target cache line into the L2 cache and setting the associated useful indicator to one;

if the L1 cache miss is a speculative miss and the target cache line is not located in the L2 cache, then installing the target cache line into the L2 cache and setting the associated useful indicator to zero; and

if the L2 cache miss is a speculative miss and the target cache line is located in the L2 cache with the associated useful indicator equal to one, then installing the target cache line in the L1 cache and setting the associated useful indicator to zero.