Multiple variable cache replacement policy

• US 20020010839A1
• Filed: 08/16/2001
• Published: 01/24/2002
• Est. Priority Date: 10/01/1999
• Status: Active Grant

• Current Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Tremblay, Marc, Tirumala, Anup S.
• Granted Patent: US 6,523,091 B2
• Time in Patent Office: Days
• 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 method for selecting a candidate to mark as overwritable in the event of a cache miss, comprising:

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

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

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;

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

choosing, when said invalid way exists, said invalid way as the candidate;

where no said invalid way exists among said set, applying 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.

2. The method of claim 1 wherein said at least one affected resource comprises a cross bar switch.

3. The method of claim 1 wherein said at least one affected resource comprises a memory controller.

4. The method of claim 1 wherein said at least one affected resource comprises a memory controller buffer.

5. The method of claim 1 wherein said at least one affected resource comprises a write back buffer.

6. The method of claim 5 wherein said cache replacement policy comprises:

determining whether said write back buffer is crowded;

where said write back buffer is crowded, determining whether said preliminary candidate is dirty;

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

where said write back buffer is crowded and said preliminary candidate is dirty, storing the contents of said preliminary candidate in said write back buffer and choosing said preliminary candidate as the candidate.

7. 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;

an address input for receiving a main memory address in said main memory;

a hit/miss circuit that determines whether the contents of said main memory address are present in said data cache;

a cache control circuit that associates 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;

an invalidity circuit that determines whether any of said plurality of ways is an invalid way and that selects said invalid way as the candidate;

a cache replacement circuit that, where no invalid ways exist among said set, applies 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.

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

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

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

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

12. The computer system of claim 11 wherein said cache replacement circuit comprises:

logic that determines whether said write back buffer is crowded;

logic that determines, where said write back buffer is crowded, whether said preliminary candidate is dirty;

logic that selects 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

logic that stores 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.

13. 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;

where no said invalid way exists among said set, performing a cache replacement logic to select 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.

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

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

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

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

18. The circuit of claim 17 wherein said cache replacement logic comprises:

logic that determines whether said write back buffer is crowded;

logic that determines, when said write back buffer is crowded, whether said preliminary candidate is dirty;

logic that selects, 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

logic that stores, 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.