Multiple variable cache replacement policy

• US 6,523,091 B2
• Filed: 08/16/2001
• Issued: 02/18/2003
• Est. Priority Date: 10/01/1999
• Status: Expired due to Term

• Current Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Tirumala, Anup S., Tremblay, Marc
• Primary Examiner(s): Kim, Matthew
• Assistant Examiner(s): ELMORE, STEPHEN C
• Application Number:
  US09/931,115
• Publication Number:
  US 20020010839A1
• Time in Patent Office: 551 Days
• Field of Search: 711/133, 711/134, 711/136, 711/143
• US Class Current: 711/133
• CPC Class Codes: G06F 12/0804 with main memory updating G06F12/0806 takes precedence
• CPC Class Codes: G06F 12/127 using additional replacement algorithms

Abstract

A method for selecting a candidate to mark as overwritable in the event of a cache miss while attempting to avoid a write back operation. The method includes associating a set of data with the cache access request, each datum of the set is associated with a way, then choosing an invalid way among the set. Where no invalid ways exist among the set, the next step is determining a way that is not most recently used among the set. Next, the method determines whether a shared resource is crowded. When the shared resource is not crowded, the not most recently used way is chosen as the candidate. Where the shared resource is crowded, the next step is to determine whether the not most recently used way differs from an associated source in the memory and where the not most recently used way is the same as an associated source in the memory, the not most recently used way is chosen as the candidate. Where the not most recently used way differs from an associated source in the memory, the candidate is chosen as the way among the set that does not differ from an associated source in the memory. Where all ways among the set differ from respective sources in the memory, the not most recently used way is chosen as the candidate and the not most recently used way is stored in the shared resource.

Claims

1. A circuit that selects a candidate to mark as overwritable in the event of a cache miss, comprising:

logic that receives a cache access request, wherein said cache access request is associated with a main memory address;

logic that determines whether the contents of said main memory address are present in a data cache;

logic that associates, when the contents of said main memory address are not present in said data cache, said main memory address with a set within said data cache, wherein said set includes a plurality of ways;

logic that determines whether any of said plurality of ways is an invalid way;

logic that selects, if said invalid way exists, said invalid way as the candidate;

cache replacement logic that selects, where no said invalid way exists among said set, a way among said set as a preliminary candidate, wherein said cache replacement logic is based on the state of at least one affected resource.

2. A computer system for selecting a candidate to mark as overwritable in the event of a cache miss comprising:

a main memory;

a data cache that is shared by a plurality of processing units;

means for receiving a main memory address in said main memory;

means for determining whether the contents of said main memory address are present in said data cache;

means for associating said main memory address with a set within said data cache when the contents of said main memory address are not present in said data cache, wherein said set includes a plurality of ways;

means for determining whether any of said plurality of ways is an invalid way and that selects said invalid way as the candidate;

means for applying, where no invalid ways exist among said set, a cache replacement policy to select a way among said set as a preliminary candidate, wherein said cache replacement policy is based on the state of at least one affected resource.

3. The computer system of claim 2 wherein said at least one affected resource comprises a cross bar switch.

4. The computer system of claim 2 wherein said at least one affected resource comprises a memory controller.

5. The computer system of claim 2 wherein said at least one affected resource comprises a memory controller buffer.

6. The computer system of claim 2 wherein said at least one affected resource comprises a write back buffer.

7. The computer system of claim 6 wherein said means for applying a cache replacement policy further comprises:

means for determining whether said write back buffer is crowded;

means for determining, when said write back buffer is crowded, whether said preliminary candidate is dirty;

means for selecting said preliminary candidate as the candidate when (said write back buffer is not crowded) OR (said write back buffer is crowded AND said preliminary candidate is not dirty); and

means for storing the contents of said preliminary candidate in said write back buffer and selects said preliminary candidate as the candidate, when said write back buffer is crowded and said preliminary candidate is dirty.

8. A circuit that selects a candidate to mark as overwritable in the event of a cache miss, comprising:

means for receiving a cache access request, wherein said cache access request is associated with a main memory address;

means for determining whether the contents of said main memory address are present in a data cache;

means for associating, when the contents of said main memory address are not present in said data cache, said main memory address with a set within said data cache, wherein said set includes a plurality of ways;

means for determining whether any of said plurality of ways is an invalid way;

means for selecting, if said invalid way exists, said invalid way as the candidate;

means for selecting, when no said invalid way exists among said set, a way among said set as a preliminary candidate, wherein said selecting a way is based on the state of at least one affected resource.

9. The circuit of claim 8 wherein said at least one affected resource comprises a cross bar switch.

10. The circuit of claim 8 wherein said at least one affected resource comprises a memory controller.

11. The circuit of claim 8 wherein said at least one affected resource comprises a memory controller buffer.

12. The circuit of claim 8 wherein said at least one affected resource comprises a write back buffer.

13. The circuit of claim 8 wherein said means for selecting a way comprises:

means for determining whether said write back buffer is crowded;

means for determining, when said write back buffer is crowded, whether said preliminary candidate is dirty;

means for selecting, where (said write back buffer is not crowded) OR (said write back buffer is crowded AND said preliminary candidate is not dirty), said preliminary candidate as the candidate; and

means for storing, where said write back buffer is crowded and said preliminary candidate is dirty, the contents of said preliminary candidate in said write back buffer and that selects said preliminary candidate as the candidate.