Selectively performing lookups for cache lines
View Patent ↗Embodiments of the present invention provide a system that selectively performs lookups for cache lines. During operation, the system by maintains a lower-level cache and a higher-level cache in accordance with a set of rules that dictate conditions under which cache lines are held in the lower-level cache and the higher-level cache. The system next performs a lookup for cache line A in the lower level cache. The system then discovers that the lookup for cache line A missed in the lower-level cache, but that cache line B is present in the lower-level cache. Next, in accordance with the set of rules, the system determines, without performing a lookup for cache line A in the higher-level cache, that cache line A is guaranteed not to be present and valid in the higher-level cache because cache line B is present in the lower-level cache.
1. A method for selectively performing lookups for cache lines, comprising:
maintaining a lower-level cache and a higher-level cache in accordance with a set of rules that dictate conditions under which cache lines are held in the lower-level cache and the higher-level cache;
performing a lookup for cache line A in the lower level cache;
determining that the lookup for cache line A missed in the lower-level cache, but that cache line B is present in the lower-level cache; and
in accordance with the set of rules, determining, without performing a lookup for cache line A in the higher-level cache, that cache line A is guaranteed not to be present and valid in the higher-level cache because cache line B is present in the lower-level cache.
2. The method of claim 1 , wherein maintaining the lower-level cache and the higher-level cache in accordance with the set of rules involves ensuring that:
the higher-level cache is direct-mapped;
in the higher-level cache, two cache lines can map to a same location;
any two cache lines that map to a same location in the higher-level cache map to a same set in the lower-level cache;
any cache line in the lower-level cache which can be victimized from the lower-level cache is allocated in the higher-level cache; and
a set of cache lines exist in the lower-level cache for which it can be determined, without accessing the higher-level cache, that the cache line is also allocated in the higher-level cache.
3. The method of claim 2 , wherein placing a cache line into the lower-level cache involves logically allocating the cache line in the higher-level cache.
4. The method of claim 2 , wherein ensuring that the set of cache lines exist in the lower-level cache for which it can be determined, without accessing the higher-level cache, that the cache line is also allocated in the higher-level cache involves ensuring that:
all cache lines allocated in the lower-level cache are also allocated in the higher-level cache;
all cache lines allocated in the lower-level cache from a predefined range of physical addresses are also allocated in the higher-level cache; or
state information associated with each cache line in the lower-level cache indicates whether or not the cache line is allocated in the higher-level cache.
5. The method of claim 1 , wherein upon determining that cache line A is guaranteed not to be present and valid in the higher-level cache, the method further comprises:
victimizing cache line B from the higher-level cache and allocating the location in the higher-level cache for cache line A;
victimizing cache line B from the lower-level cache and allocating the location in the lower-level cache for cache line A; and
placing cache line A in the lower-level cache but not in the allocated location in the higher-level cache.
6. The method of claim 1 , wherein upon determining that cache line A is guaranteed not to be present and valid in the higher-level cache, the method further comprises:
victimizing cache line B from the higher-level cache and allocating the location in the higher-level cache for cache line A;
victimizing cache line B from the lower-level cache and allocating the location in the lower-level cache for cache line A; and
placing cache line A in the lower-level cache and in the higher-level cache.
7. The method of claim 1 , wherein upon determining that a copy of cache line A is guaranteed not to be present and valid in the higher-level cache, the method further comprises:
victimizing cache line B from the lower-level cache and allocating the location in the lower-level cache for cache line A;
placing cache line A in the lower-level cache; and
leaving cache line B in the higher-level cache.
8. The method of claim 1 , wherein the method further comprises:
receiving a lookup request for cache line A that is directed to a lower-level cache, wherein the lookup operation is performed in response to the request; and
returning a response to the lookup request that cache line A is not present and valid in either the lower-level cache or the higher-level cache.
9. An apparatus for selectively performing lookups for cache lines, comprising:
a lower-level cache;
a higher-level cache coupled to the lower-level cache;
wherein the apparatus is configured to:
maintain the lower-level cache and the higher-level cache in accordance with a set of rules that dictate conditions under which cache lines are held in the lower-level cache and the higher-level cache;
perform a lookup for cache line A in the lower level cache;
determine that the lookup for cache line A missed in the lower-level cache, but that cache line B is present in the lower-level cache; and
in accordance with the set of rules, determine, without performing a lookup for cache line A in the higher-level cache, that cache line A is guaranteed not to be present and valid in the higher-level cache because cache line B is present in the lower-level cache.
10. The apparatus of claim 9 , wherein when maintaining the lower-level cache and the higher-level cache in accordance with the set of rules, the apparatus is configured to ensure that:
the higher-level cache is direct-mapped;
in the higher-level cache, two cache lines can map to a same location;
any two cache lines that map to the same location in the higher-level cache map to a same set in the lower-level cache;
any cache line in the lower-level cache which can be victimized from the lower-level cache is allocated in the higher-level cache; and
a set of cache lines exist in the lower-level cache for which it can be determined, without accessing the higher-level cache, that the cache line is also allocated in the higher-level cache.
11. The apparatus of claim 10 , wherein when placing a cache line into the lower-level cache, the apparatus is configured to logically allocate the cache line in the higher-level cache.
12. The apparatus of claim 10 , wherein when ensuring that the set of cache lines exist in the lower-level cache for which it can be determined, without accessing the higher-level cache, that the cache line is also allocated in the higher-level cache, the apparatus is configured to ensure that:
all cache lines allocated in the lower-level cache are also allocated in the higher-level cache;
all cache lines allocated in the lower-level cache from a predefined range of physical addresses are also allocated in the higher-level cache; or
state information associated with each cache line in the lower-level cache indicates whether or not the cache line is allocated in the higher-level cache.
13. The apparatus of claim 9 , wherein upon determining that cache line A is guaranteed not to be present and valid in the higher-level cache, the apparatus is configured to:
victimize cache line B from the higher-level cache and allocate the location in the higher-level cache for cache line A;
victimize cache line B from the lower-level cache and allocate the location in the lower-level cache for cache line A; and
place cache line A in the lower-level cache but not in the allocated location in the higher-level cache.
14. The apparatus of claim 9 , wherein upon determining that cache line A is guaranteed not to be present and valid in the higher-level cache, the apparatus is configured to:
victimize cache line B from the higher-level cache and allocate the location in the higher-level cache for cache line A;
victimize cache line B from the lower-level cache and allocate the location in the lower-level cache for cache line A; and
place cache line A in the lower-level cache and in the higher-level cache.
15. The apparatus of claim 9 , wherein upon determining that a copy of cache line A is guaranteed not to be present and valid in the higher-level cache, the apparatus is configured to:
victimize cache line B from the lower-level cache and allocate the location in the lower-level cache for cache line A;
place cache line A in the lower-level cache; and
leave cache line B in the higher-level cache.
16. The apparatus of claim 9 , wherein the apparatus is further configured to:
receive a lookup request for cache line A that is directed to a lower-level cache, wherein the apparatus is configured to perform the lookup operation in response to the request; and
return a response to the lookup request that cache line A is not present and valid in either the lower-level cache or the higher-level cache.
17. A computer system for selectively performing lookups for cache lines, comprising:
a processor;
a lower-level cache and a higher-level cache coupled to the processor, wherein the lower-level cache and the higher-level cache store instructions and data for the processor;
wherein the computer system is configured to:
maintain the lower-level cache and the higher-level cache in accordance with a set of rules that dictate conditions under which cache lines are held in the lower-level cache and the higher-level cache;
perform a lookup for cache line A in the lower level cache;
determine that the lookup for cache line A missed in the lower-level cache, but that cache line B is present in the lower-level cache; and
in accordance with the set of rules, determine, without performing a lookup for cache line A in the higher-level cache, that cache line A is guaranteed not to be present and valid in the higher-level cache because cache line B is present in the lower-level cache.
18. The computer system of claim 17 , wherein when maintaining the lower-level cache and the higher-level cache in accordance with the set of rules, the computer system is configured to ensure that:
the higher-level cache is direct-mapped;
in the higher-level cache, two cache lines can map to a same location;
any two cache lines that map to the same location in the higher-level cache map to a same set in the lower-level cache;
any cache line in the lower-level cache which can be victimized from the lower-level cache is allocated in the higher-level cache; and
a set of cache lines exist in the lower-level cache for which it can be determined, without accessing the higher-level cache, that the cache line is also allocated in the higher-level cache.
19. The computer system of claim 18 , wherein when placing a cache line into the lower-level cache, the computer system is configured to logically allocate the cache line in the higher-level cache.
20. The computer system of claim 18 , wherein when ensuring that the set of cache lines exist in the lower-level cache for which it can be determined, without accessing the higher-level cache, that the cache line is also allocated in the higher-level cache, the computer system is configured to ensure that:
all cache lines allocated in the lower-level cache are also allocated in the higher-level cache;
all cache lines allocated in the lower-level cache from a predefined range of physical addresses are also allocated in the higher-level cache; or
state information associated with each cache line in the lower-level cache indicates whether or not the cache line is allocated in the higher-level cache.