Microprocessor having a cache memory system using multi-level cache set prediction

• US 5,918,245 A
• Filed: 03/13/1996
• Issued: 06/29/1999
• Est. Priority Date: 03/13/1996
• Status: Expired due to Term

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Yung, Robert
• Primary Examiner(s): Gossage, Glenn
• Application Number:
  US08/615,662
• Time in Patent Office: 1,203 Days
• Field of Search: 395/449, 395/455, 395/464, 395/414, 395/421.03, 711/122, 711/128, 711/137, 711/204, 711/213
• US Class Current: 711/122
• CPC Class Codes: G06F 12/0862 with prefetch
• CPC Class Codes: G06F 12/0864 using pseudo-associative means, e.g. set-associative or hashing
• CPC Class Codes: G06F 12/0897 with two or more cache hierarchy levels with multilevel cache hierarchies G06F12/0811
• CPC Class Codes: G06F 12/1054 the data cache being concurrently physically addressed
• CPC Class Codes: G06F 2212/6082 Way prediction in set-associative cache

Abstract

A cache structure for a microprocessor which provides set-prediction information for a separate, second-level cache, and a method for improving cache accessing, are provided. In the event of a first-level cache miss, the second-level set-prediction information is used to select the set in an N-way off-chip set-associative cache. This allows a set-associative structure to be used in a second-level cache (on or off chip) without requiring a large number of traces and/or pins. Since set-prediction is used, the subsequent access time for a comparison to determine that the correct set was predicted is not in the critical timing path unless there is a mis-prediction or a miss in the second-level cache. Also, a cache memory can be partitioned into M sets, with M being chosen so that the set size is less than or equal to the page size, allowing a cache access before a TLB translation is done, further speeding the access.

Claims

1. A cache memory system comprising:

a plurality of entries;

a plurality of tags, each tag corresponding to one of said entries; and

a plurality of first set predictors each first set predictor corresponding to one of said entries each first set predictor identifying a set in a first cache memory where a predicted next entry to be accessed is predicted to be located; and

a plurality of second set predictors, each second set predictor corresponding to one of said entries, each second set predictor identifying a set in a second cache memory where a predicted next entry to be accessed is predicted to be located;

wherein each set in said second cache memory has a size less than or equal to the size of a page of memory.

2. The memory system of claim 1 wherein a plurality of said entries are data.

3. The memory system of claim 1 wherein a plurality of said entries are instructions.

4. The memory system of claim 1 wherein a plurality of said entries include a plurality of data words.

5. The memory system of claim 1 wherein a plurality of said entries include a plurality of instructions.

6. The memory system of claim 1 wherein said second cache memory is a level two cache.

7. The memory system of claim 1 wherein said second cache memory is an Nth level cache.

8. The memory system of claim 1 wherein each logical set in said second cache memory has a size less than or equal to the size of a page.

9. The memory system of claim 1 further comprising:

a cache latch for storing one of said second set predictors corresponding to a last accessed entry.

10. The memory system of claim 1 further comprising:

a previous address latch for storing a last address accessed, for use in updating a set predictor for a current address.

11. The cache memory system of claim 1 wherein said tags are physical addresses, and further comprising:

a translation look-aside buffer configured to translate an input virtual address in parallel with a use of said input virtual address to access said first cache memory.

12. The memory system of claim 1 wherein said first cache memory is a first level cache in a microprocessor.

13. The memory system of claim 12 wherein said second cache memory is an Nth level cache external to said microprocessor.

14. The memory system of claim 13, further comprising an Nth level cache tag memory on said microprocessor for storing tags for said external Nth level cache.

15. A computer system comprising:

a system memory;

a microprocessor including a level one cache memory;

a level two cache memory coupled to said microprocessor;

said level one cache memory including

a plurality of entries,

a plurality of tags, each tag corresponding to one of said entries,

a plurality of first set predictors each first set predictor corresponding to one of said entries each first set predictor identifying a set in said level one cache memory where a predicted next entry to be accessed is predicted to be located; and

a plurality of second set predictors, each second set predictor corresponding to one of said entries, each second set predictor identifying a set in said level two cache memory where a predicted next entry to be accessed is predicted to be located.

16. A method for improving the accessing of a cache memory system comprising the steps of:

storing a plurality of entries in a first cache memory;

storing a plurality of tags, each tag corresponding to one of said entries in said first cache memory;

storing a plurality of first set predictors in said first cache memory, each first set predictor corresponding to one of said entries each first set predictor identifying a set in said first cache memory where a predicted next entry to be accessed is predicted to be located; and

storing a plurality of second set predictors in said first cache memory, each second set predictor corresponding to one of said entries, each second set predictor identifying a set in a second cache memory where a predicted next entry to be accessed is predicted to be located.