SECTORED CACHE REPLACEMENT ALGORITHM FOR REDUCING MEMORY WRITEBACKS

• US 20100325365A1
• Filed: 06/17/2009
• Published: 12/23/2010
• Est. Priority Date: 06/17/2009
• Status: Active Grant

• Current Assignee: Lenovo International Limited (Lenovo Group Ltd.)
• Original Assignee: International Business Machines Corporation
• Inventors: Colglazier, Daniel J.
• Granted Patent: US 8,745,334 B2
• Time in Patent Office: Days
• US Class Current: 711/136
• CPC Class Codes: G06F 12/0864 using pseudo-associative means, e.g. set-associative or hashing
• CPC Class Codes: G06F 12/0891 using clearing, invalidating or resetting means
• CPC Class Codes: G06F 12/127 using additional replacement algorithms
• CPC Class Codes: G06F 12/128 adapted to multidimensional cache systems, e.g. set-associative, multicache, multiset or multilevel

Abstract

An improved sectored cache replacement algorithm is implemented via a method and computer program product. The method and computer program product select a cache sector among a plurality of cache sectors for replacement in a computer system. The method may comprise selecting a cache sector to be replaced that is not the most recently used and that has the least amount of modified data. In the case in which there is a tie among cache sectors, the sector to be replaced may be the sector among such cache sectors with the least amount of valid data. In the case in which there is still a tie among cache sectors, the sector to be replaced may be randomly selected among such cache sectors. Unlike conventional sectored cache replacement algorithms, the improved algorithm implemented by the method and computer program product accounts for both hit rate and bus utilization.

Claims

1. A method for selecting a cache sector among a plurality of cache sectors for replacement in a computer system, said method comprising:

determining a first set of cache sectors among said plurality of cache sectors, wherein each of said first set of cache sectors has the least amount of modified data among said plurality of cache sectors and is not the most recently used cache sector; and

selecting a first single cache sector for replacement if said first set of cache sectors comprises one cache sector.

2. The method according to claim 1, further comprising:

determining a second set of cache sectors among said first set of cache sectors if said first set of cache sectors comprises multiple cache sectors, wherein each of said second set of cache sectors has the least amount of valid data among said first set of cache sectors; and

selecting a second single cache sector for replacement if said second set of cache sectors comprises one cache sector.

3. The method according to claim 2, further comprising selecting a random cache sector among said second set of cache sectors for replacement if said second set of cache sectors comprises multiple cache sectors.

4. The method according to claim 1, further comprising marking a most recently used cache sector among said plurality of cache sectors.

5. The method according to claim 4, wherein said marking step comprises storing in a directory entry an identifier corresponding to said most recently used cache sector.

6. A computer program product for selecting a cache sector among a plurality of cache sectors for replacement in a computer system, said computer program product comprising a computer-readable storage medium having computer-readable program code instructions stored therein comprising:

a first set of computer instructions for determining a first set of cache sectors among said plurality of cache sectors, wherein each of said first set of cache sectors has the least amount of modified data among said plurality of cache sectors and is not the most recently used cache sector; and

a second set of computer instructions for selecting a first single cache sector for replacement if said first set of cache sectors comprises one cache sector.

7. The computer program product according to claim 6, further comprising:

a third set of computer instructions for determining a second set of cache sectors among said first set of cache sectors if said first set of cache sectors comprises multiple cache sectors, wherein each of said second set of cache sectors has the least amount of valid data among said first set of cache sectors; and

a fourth set of computer instructions for selecting a second single cache sector for replacement if said second set of cache sectors comprises one cache sector.

8. The computer program product according to claim 7, further comprising a fifth set of computer instructions for selecting a random cache sector among said second set of cache sectors for replacement if said second set of cache sectors comprises multiple cache sectors.

9. The computer program product according to claim 6, further comprising a sixth set of computer instructions for marking a most recently used cache sector among said plurality of cache sectors.

10. The computer program product according to claim 9, wherein said sixth set of computer instructions comprises a seventh set of computer instructions for storing in a directory entry an identifier corresponding to said most recently used cache sector.