# US 2014/0208038 A1 · Sectored cache replacement algorithm for reducing memory writebacks > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 2014/0208038 A1 - Document ID: US20140208038A1 - Status: Published application - Kind: A1 - Application number: 14/226,778 - Filed: 2014-03-26 - Published: 2014-07-24 - Earliest claimed: 2009-06-17 - Assignees: International Business Machines Corporation - Applicants: International Business Machines Corporation - Inventors: DANIEL J. COLGLAZIER - Web page: https://patentgrep.com/patent/US20140208038A1 ## CPC - G06F 12/0891: using clearing, invalidating or resetting means - G06F 12/127: using additional replacement algorithms - G06F 12/128: adapted to multidimensional cache systems, e.g. set-associative, multicache, multiset or multilevel - G06F 12/0864: using pseudo-associative means, e.g. set-associative or hashing - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract A 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 algorithm implemented by the method and computer program product accounts for both hit rate and bus utilization. ## Claims ### Claim 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 excluding a most recently used cache sector, wherein each of said first set of cache sectors has the least amount of modified data among said plurality of cache sectors excluding said most recently used cache sector; and upon determining that said first set of cache sectors comprises one cache sector, selecting a first single cache sector for replacement. ### Claim 2 (depends on 1) The method according to claim 1, further comprising: upon determining that said first set of cache sectors comprises multiple cache sectors, determining a second set of cache sectors among said first set of 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 upon determining that said second set of cache sectors comprises one cache sector, selecting a second single cache sector for replacement. ### Claim 3 (depends on 2) The method according to claim 2, further comprising, upon determining that said second set of cache sectors comprises multiple cache sectors, selecting a random cache sector among said second set of cache sectors for replacement. ### Claim 4 (depends on 1) The method according to claim 1, further comprising marking said most recently used cache sector among said plurality of cache sectors. ### Claim 5 (depends on 4) 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. ### Claim 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: instructions for determining a first set of cache sectors among said plurality of cache sectors excluding a most recently used cache sector, wherein each of said first set of cache sectors has the least amount of modified data among said plurality of cache sectors excluding said most recently used cache sector; and instructions for, upon determining that said first set of cache sectors comprises one cache sector, selecting a first single cache sector for replacement. ### Claim 7 (depends on 6) The computer program product according to claim 6, further comprising: instructions for, upon determining that said first set of cache sectors comprises multiple cache sectors, determining a second set of cache sectors among said first set of 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 instructions for, upon determining that said second set of cache sectors comprises one cache sector, selecting a second single cache sector for replacement. ### Claim 8 (depends on 7) The computer program product according to claim 7, further comprising instructions for, upon determining that said second set of cache sectors comprises multiple cache sectors, selecting a random cache sector among said second set of cache sectors for replacement. ### Claim 9 (depends on 6) The computer program product according to claim 6, further comprising instructions for marking said most recently used cache sector among said plurality of cache sectors. ### Claim 10 (depends on 9) The computer program product according to claim 9, wherein said instructions for marking said most recently used cache sector comprise instructions for storing in a directory entry an identifier corresponding to said most recently used cache sector. ### Claim 11 A system comprising: a processor; and one or more memory elements storing a program, which, when executed on said processor, performs an operation of selecting a cache sector among a plurality of cache sectors for replacement in a computer system, said operation comprising: determining a first set of cache sectors among said plurality of cache sectors excluding a most recently used cache sector, wherein each of said first set of cache sectors has the least amount of modified data among said plurality of cache sectors excluding said most recently used cache sector; and upon determining that said first set of cache sectors comprises one cache sector, selecting a first single cache sector for replacement. ### Claim 12 (depends on 11) The system according to claim 11, wherein said operation further comprises: upon determining that said first set of cache sectors comprises multiple cache sectors, determining a second set of cache sectors among said first set of 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 upon determining that said second set of cache sectors comprises one cache sector, selecting a second single cache sector for replacement. ### Claim 13 (depends on 12) The system according to claim 12, wherein said operation further comprises, upon determining that said second set of cache sectors comprises multiple cache sectors, selecting a random cache sector among said second set of cache sectors for replacement. ### Claim 14 (depends on 11) The system according to claim 11, wherein said operation further comprises marking said most recently used cache sector among said plurality of cache sectors. ### Claim 15 (depends on 14) The system according to claim 14, wherein said marking step comprises storing in a directory entry an identifier corresponding to said most recently used cache sector. ### Claim 16 (depends on 5) The method according to claim 5, wherein said identifier is a numerical identifier based on a physical location of said most recently used cache sector. ### Claim 17 (depends on 10) The computer program product according to claim 10, wherein said identifier is a numerical identifier based on a physical location of said most recently used cache sector. ### Claim 18 (depends on 15) The system according to claim 15, wherein said identifier is a numerical identifier based on a physical location of said most recently used cache sector.