Method and apparatus for adaptively bypassing one or more levels of a cache hierarchy

• US 20020099913A1
• Filed: 01/25/2001
• Published: 07/25/2002
• Est. Priority Date: 01/25/2001
• Status: Active Grant

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Steely, Simon C. Jr.
• Granted Patent: US 6,647,466 B2
• Time in Patent Office: Days
• US Class Current: 711/122
• CPC Class Codes: G06F 12/0811 with multilevel cache hierarchies
• CPC Class Codes: G06F 12/0888 using selective caching, e.g. bypass
• CPC Class Codes: G06F 12/0891 using clearing, invalidating or resetting means
• CPC Class Codes: G06F 12/0897 with two or more cache hierarchy levels with multilevel cache hierarchies G06F12/0811

Abstract

A system for adaptively bypassing one or more higher cache levels following a miss in a lower level of a cache hierarchy is described. Each cache level preferably includes a tag store containing address and state information for each cache line resident in the respective cache. When an invalidate request is received at a given cache hierarchy, each cache level is searched for the address specified by the invalidate request. When an address match is detected, the state of the respective cache line is changed to the invalid state, although the address of the cache line is left in the tag store. Thereafter, if the processor or entity associated with this cache hierarchy issues its own request for this same cache line, the cache hierarchy begins searching the tag store of each level starting with the lowest cache level. Since the address of the invalidated cache line was left in the respective tag store, a match will be detected at one of the cache levels, although the corresponding state of this cache line is invalid. This condition is specifically detected and is considered to be an “inval_miss” occurrence. In response, to an inval miss, the cache hierarchy calls off searching any higher levels, and instead, issues a memory reference request for the desired cache line. In a further embodiment, the entity that sourced an invalidate request is stored, and a subsequent memory reference request for the same cache line is sent directly to the source entity.

Claims

1. A method for use in a cache hierarchy including at least two cache levels organized as a lower cache level and a higher cache level, each cache level configured to store one or more cache lines, the method comprising the steps of:

providing a tag store at each cache level, the tag store containing tag values associated with the cache lines stored at the respective cache level, the tag values being settable between a valid state and a invalid state;

comparing at least a portion of the tag store of the lower cache level with a given tag value;

if the given tag value matches a tag value of the tag store, determining whether the matching tag value is in the valid state or the invalid state; and

if the matching tag value is in the invalid state, bypassing the higher level cache.

2. The method of claim 1 wherein the tag store includes one or more valid bits associated with the tag values for use in setting the state of the tag values.

3. The method of claim 2 wherein the step of determining comprising the step of examining the one or more valid bits from the matching tag value of the tag store to determine the state of the matching tag value.

4. The method of claim 1 wherein the cache hierarchy is disposed in a computer system having a main memory, the method further comprising the step of issuing a request to the main memory in response to determining that the matching tag value is in the invalid state.

5. The method of claim 3 wherein

the cache hierarchy is disposed in a computer system having a main memory,

each cache line is associated with a corresponding system address that identifies a main memory location, and

the given tag value is derived from a specified system address.

6. The method of claim 5 wherein the given tag value represents a portion of a system address for a cache line.

7. The method of claim 6 wherein

the computer system has one or more processors, and

the cache hierarchy is associated with a given processor.

8. The method of claim 7 further comprising the step of setting a particular tag value to the invalid state in response to receiving an invalidate request message specifying the particular tag value.

9. The method of claim 8 wherein the invalidate request message is initiated by a source processor having a corresponding identifier, the method further comprising the step of storing the source processor identifier from the invalidate request message at the cache line associated with the particular tag value specified by the invalidate request message.

10. The method of claim 9 further comprising the steps of:

in response to determining that the matching tag value is in the invalid state, retrieving the source processor identifier from the cache line associated with the matching tag value;

issuing a request to the source processor for the cache line represented by the matching tag value that is in the invalid state.

11. The method of claim 10 wherein the cache hierarchy is disposed in a computer system having a main memory, the method further comprising the step of issuing a request to the main memory for the cache line represented by the matching tag value that is in the invalid state.

13. The method of claim 12 wherein

the computer system has one or more processors, and

the cache hierarchy is associated with a given processor.

14. The method of claim 13 further comprising the steps of:

receiving a request for a cache line initiated by the given processor that is associated with the cache hierarchy, the request specifying a tag value;

comparing at least a portion of the tag store with the received tag value;

if the received tag value matches a tag value of the tag store, determining whether the matching tag value is in the valid state or the invalid state;

if the matching tag value is in the invalid state, retrieving the source processor identifier from the cache line associated with the matching tag value; and

issuing a request to the source processor for the cache line represented by the matching tag value that is in the invalid state.

15. The method of claim 14 wherein the cache hierarchy is disposed in a computer system having a main memory, the method further comprising the step of issuing a request to the main memory for the cache line represented by the matching tag value that is in the invalid state.

16. The method of claim 15 further comprising the step of, if the source processor has the cache line represented by the tag value specified in the request and the cache line is in the valid state, returning the cache line.

17. The method of claim 16 wherein the cache hierarchy includes at least two cache levels organized as a lower cache level and a higher cache level, each cache level having a tag store and configured to store one or more cache lines, the method further comprising the steps of:

if the tag value received from the given processor that is associated with the cache hierarchy does not match a tag value from the tag store of the first cache level, passing the tag value to the second cache level;

comparing at least a portion of the tag store of the second cache level with the received tag value;

if the received tag value matches a tag value of the second level tag store, determining whether the matching tag value is in the valid state or the invalid state;

if the matching tag value is in the invalid state, retrieving the source processor identifier from the cache line associated with the matching tag value and stored at the second level; and

issuing a request to the source processor for the cache line represented by the matching tag value that is in the invalid state.

12. A method for use in a cache hierarchy including at least one cache level, the at least one cache level configured to store one or more cache lines, the method comprising the steps of:

providing a tag store at the at least one cache level, the tag store containing tag values associated with the cache lines stored at the cache level, the tag values being settable between a valid state and a invalid state;

receiving an invalidate request message specifying a given tag value and a source processor identifier;

comparing at least a portion of the tag store with the given tag value;

if the given tag value matches a tag value of the tag store, setting the matching tag value to the invalid state; and

storing the source processor identifier from the invalidate request message at the cache line associated with the particular tag value specified by the invalidate request message.