Efficient allocation of cache memory space in a computer system

• US 5,893,150 A
• Filed: 07/01/1996
• Issued: 04/06/1999
• Est. Priority Date: 07/01/1996
• Status: Expired due to Term

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Hill, Mark D., Hagersten, Erik E.
• Primary Examiner(s): Chan, Eddie P.
• Assistant Examiner(s): Ellis, Kevin L.
• Application Number:
  US08/675,306
• Time in Patent Office: 1,009 Days
• Field of Search: 395/460, 395/461, 395/462, 395/463, 395/465, 395/466, 395/472, 711/133, 711/134, 711/135, 711/136, 711/138, 711/139, 711/145
• US Class Current: 711/139
• CPC Class Codes: G06F 12/0813 with a network or matrix configuration
• CPC Class Codes: G06F 12/0888 using selective caching, e.g. bypass

Abstract

An efficient cache allocation scheme is provided for both uniprocessor and multiprocessor computer systems having at least one cache. In one embodiment, upon the detection of a cache miss, a determination of whether the cache miss is "avoidable" is made. In other words, would the present cache miss have occurred if the data had been cached previously and if the data had remained in the cache. One example of an avoidable cache miss in a multiprocessor system having a distributed memory architecture is an excess cache miss. An excess cache miss is either a capacity miss or a conflict miss. A capacity miss is caused by the insufficient size of the cache. A conflict miss is caused by insufficient depth in the associativity of the cache. The determination of the excess cache miss involves tracking read and write requests for data by the various processors and storing some record of the read/write request history in a table or linked list. Data is cached only after an avoidable cache miss has occurred. By caching only after at least one avoidable cache miss instead of upon every (initial) access, cache space can be allocated in a highly efficient manner thereby minimizing the number of data fetches caused by cache misses.

Claims

1. A method for selecting data to be cached in a computer system having a cache and a main memory, the method comprising the steps of:

searching for said data in said cache;

detecting a cache miss when said data cannot be found in said cache; and

if said cache miss is detected, then;

fetching said data from said main memory;

determining if said cache miss is an avoidable cache miss; and

if said cache miss is determined to be said avoidable cache miss, then caching said data in said cache.

2. The method of claim 1 further comprising the step of writing back any older data displaced from said cache to said main memory as a result of caching said data.

3. The method of claim 1 wherein said avoidable cache miss is an excess cache miss.

4. The method of claim 3 wherein said excess cache miss is a capacity miss of said data.

5. The method of claim 3 wherein said excess cache miss is a conflict miss of said data.

6. The method of claim 5 wherein a count of said avoidable cache miss(es) of said data and a count of cache hit(s) of older data are maintained, and wherein said data is cached and said older data is written back only if said count of said avoidable cache miss(es) exceeds said count of said cache hit(s).

7. A method for selecting data to be cached in a computer system including at least a first subsystem and a second subsystem, each said subsystem including a cache, said second subsystem is a home subsystem of the data, the method comprising the steps of:

searching for said data in said cache of said first subsystem;

detecting a cache miss when said data cannot be found in said cache of said first subsystem; and

if said cache miss is detected, then;

fetching said data from said second subsystem to said first subsystem;

determining if said cache miss is an avoidable cache miss; and

if said cache miss is determined to be said avoidable cache miss, then caching said data in said cache of said first subsystem.

8. The method of claim 7 further comprising the step of writing back any older data displaced from said first subsystem to said second subsystem as a result of caching said data.

9. The method of claim 8 wherein a count of said avoidable cache miss(es) of said data and a count of cache hit(s) of older data are maintained, and wherein said data is cached and said older data is written back only if said count of said avoidable cache miss(es) exceeds said count of said cache hit(s).

10. The method of claim 7 wherein said avoidable cache miss is an excess cache miss.

11. The method of claim 10 wherein said excess cache miss is a capacity miss of said data.

12. The method of claim 11 wherein said excess cache miss is a conflict miss of said data.

13. The method of claim 10 wherein said home subsystem maintains a list of said subsystem(s) which has a shared copy of said data and an identity of a last writer of said data, and wherein said access cache miss is detected when said fetching step includes sending a read-to-share request for said data to said second subsystem, and said list indicates that said first subsystem had previously fetched a shared copy of said data.

14. The method of claim 10 wherein said home subsystem maintains a list of said subsystem(s) which have a shared copy of said data and an identity of a last writer of said data, and wherein said access cache miss is detected when said fetching step includes sending a read-to-own request for said data to said second subsystem, and said first subsystem was said last writer of said data.

15. The method of claim 14 wherein said home subsystem also maintains an identity of said last owner of said data, and an indicator indicating whether said last owner has copied said data back to said home subsystem, and wherein said last writer is determined by examining the identity of said last owner and said indicator.

16. A computer system comprising:

a cache;

a main memory coupled to said cache; and

a fetcher coupled between said cache and said main memory, said fetcher configured to fetch data from said main memory to said cache when an avoidable cache miss of said data occurs in said cache.

17. The computer system of claim 16 wherein said avoidable cache miss is an excess cache miss.

18. The computer system of claim 17 wherein said excess cache miss is a capacity miss of said data.

19. The computer system of claim 17 wherein said excess cache miss is a conflict miss of said data.

20. The computer system of claim 17 wherein said fetcher is further configured to write back any older data displaced from said cache to said main memory.

21. A caching system for a computer system comprising:

a first cache associated with a first subsystem of said computer system;

a second cache associated with a second subsystem of said computer system, said second subsystem is a home subsystem of data;

a fetcher coupled between said first cache and said second cache, said fetcher configured to fetch said data from said second cache to said first cache when an avoidable cache miss of said data occurs in said first cache.

22. The caching system of claim 21 wherein said avoidable cache miss is an excess cache miss.

23. The caching system of claim 22 wherein said excess cache miss is a capacity miss of said data.

24. The caching system of claim 22 wherein said excess cache miss is a conflict miss of said data.

25. The caching system of claim 22 wherein said fetcher is further configured to write back any displaced data from said first cache to a home subsystem of said displaced data.

26. The caching system of claim 22 wherein said home subsystem includes a list of subsystem(s) of said computer system which has a shared copy of said data and an identity of a last writer of said data, and wherein said access cache miss is detected when said first subsystem sends a read-to-share request for said data to said second subsystem, and said list indicates that said first subsystem had previously fetched a shared copy of said data.

27. The caching system of claim 22 wherein said home subsystem includes a list of subsystem(s) of said computer system which has a shared copy of said data and an identity of a last writer of said data, and wherein said access cache miss is detected when said first subsystem sends a read-to-own request for said data to said second subsystem, and said first subsystem was said last writer of said data.

28. The caching system of claim 27 wherein said home subsystem includes an identifier of said last owner of said data, and an indicator indicating whether said last owner has copied said data back to said home subsystem, and wherein said last writer is determined by examining the identifier of said last owner and said indicator.