Method and system for detecting and resolving virtual address synonyms in a two-level cache hierarchy
First Claim
1. A method for detecting and resolving virtual memory address synonyms in a multi-level cache hierarchy, the multi-level cache hierarchy comprising a first-level cache and a second-level cache wherein the first-level cache comprises a plurality of virtually indexed first-level cache lines each configured to store a physical memory address tag and state information, the method comprising:
- maintaining a plurality of Dtags in the second-level cache, wherein each first-level cache line has an associated Dtag, and each Dtag includes state information for the first-level cache line and a copy of the physical memory address tag for the first-level cache line;
first searching the first-level cache for a targeted physical memory address tag at an original first-level cache line, wherein the targeted physical memory address tag and original first-level cache line correspond to a requested virtual memory address;
upon the first searching resulting in a miss, second searching the Dtags in the second-level cache to locate a synonym first-level cache line corresponding to the requested virtual memory address; and
upon the second searching resulting in a hit, copying contents of the synonym first-level cache line to the original first-level cache line;
invalidating the synonym first-level cache line; and
updating the Dtags associated with the synonym first-level cache line and the original first-level cache line to reflect the copying and the invalidating.
3 Assignments
0 Petitions
Accused Products
Abstract
L1 cache synonyms in a two-level cache system are detected and resolved by logic in the L2 cache. Duplicate copies of the L1 cache tags and state (“Dtags”) are maintained in the L2 cache. After a miss occurs in the L1 cache, the Dtags in the second-level cache that correspond to all possible synonym locations in the L1 cache are searched for synonyms. If a synonym is found, the L2 cache notifies the L1 cache where the requested cache line can be found in the L1 cache. The L1 cache then copies the cache line from the location where the synonym was found to the location where the miss occurred, and it invalidates the cache line at the original location. The Dtags in the second-level cache are updated to reflect the changes made in the L1 cache.
-
Citations
15 Claims
-
1. A method for detecting and resolving virtual memory address synonyms in a multi-level cache hierarchy, the multi-level cache hierarchy comprising a first-level cache and a second-level cache wherein the first-level cache comprises a plurality of virtually indexed first-level cache lines each configured to store a physical memory address tag and state information, the method comprising:
-
maintaining a plurality of Dtags in the second-level cache, wherein each first-level cache line has an associated Dtag, and each Dtag includes state information for the first-level cache line and a copy of the physical memory address tag for the first-level cache line;
first searching the first-level cache for a targeted physical memory address tag at an original first-level cache line, wherein the targeted physical memory address tag and original first-level cache line correspond to a requested virtual memory address;
upon the first searching resulting in a miss, second searching the Dtags in the second-level cache to locate a synonym first-level cache line corresponding to the requested virtual memory address; and
upon the second searching resulting in a hit, copying contents of the synonym first-level cache line to the original first-level cache line;
invalidating the synonym first-level cache line; and
updating the Dtags associated with the synonym first-level cache line and the original first-level cache line to reflect the copying and the invalidating. - View Dependent Claims (2, 3, 4, 5, 6, 7)
the requested virtual memory address includes a first set of address bits representing a virtual page number and a second set of address bits representing a virtual cache index, the first and second sets of address bits overlapping at a set of vpn bits; - and
the second searching, when resulting in a hit, generates a set of VPN bits that, when used to replace the vpn bits of the virtual cache index, produces a synonym cache index that identifies a location in the first-level cache of the synonym first-level cache line.
-
-
7. The method of claim 1, wherein the multi-level cache hierarchy further comprises a plurality of first-level caches that share a single second-level cache, the method further comprising maintaining a plurality of Dtags in the second-level cache for each of the plurality of the first-level caches.
-
8. A multi-level cache system comprising:
-
a first-level cache comprising a plurality of virtually indexed first-level cache lines each configured to store a physical memory address tag and state information;
a second-level cache comprising a plurality of second-level cache lines and a plurality of Dtags, wherein each first-level cache line of the plurality of virtually indexed first-level cache lines has an associated Dtag among the plurality of Dtags, and each Dtag includes state information for the first-level cache line and a copy of the physical memory address tag for the first-level cache line;
a first-level comparator located in the first-level cache and configured to compare a targeted physical memory address, translated from a requested virtual memory address, with the physical memory address tag stored at an original first-level cache line corresponding to the requested virtual memory address, the first-level comparator configured to generate a miss indicator when the targeted physical memory address and the physical memory address tag stored at the original first-level cache line do not match;
Dtag logic located in the second-level cache, responsive to a message conveying the miss indicator, and configured to search the Dtags in the second-level cache to locate a synonym first-level cache line corresponding to the requested virtual memory address;
a first-level controller in the first-level cache configured to;
copy contents of the synonym first-level cache line to the original first-level cache line; and
invalidate the synonym first-level cache line;
a second-level controller in the second-level cache configured to update the Dtags associated with the synonym first-level cache line and the original first-level cache line to reflect the copying of the synonym first-level cache line to the original first-level cache line and invalidation of the synonym first-level cache line. - View Dependent Claims (9, 10, 11, 12, 13, 14, 15)
the original first-level cache line corresponds to an original cache index derived from the requested virtual memory address; the Dtag logic includes;
a Dtag comparator configured to compare the targeted physical memory address with an additional physical memory address tag stored in the Dtag corresponding to a synonym cache index, the synonym cache index comprising a cache index corresponding to the targeted physical address and distinct from the original cache index; and
logic configured to generate a result signal representing at least a portion of the synonym cache index when the second-level comparator determines that the targeted physical memory address matches the additional physical memory address tag stored at in the Dtag corresponding to a synonym cache index.
-
-
10. The multi-level cache system of claim 8 wherein
the original first-level cache line corresponds to an original cache index derived from the requested virtual memory address; -
the Dtag logic includes;
a Dtag comparator configured to compare the targeted physical memory address with a plurality of additional physical memory address tags stored in the Dtags corresponding to a plurality of synonym cache indices, each of the synonym cache indices comprising a cache index corresponding to the targeted physical address and distinct from the original cache index; and
logic configured to generate a result signal representing at least a portion of an identified synonym cache index, identified by the second-level comparator from among the plurality of synonym cache indices when the second-level comparator determines that the targeted physical memory address matches the additional physical memory address tag stored at in the Dtag corresponding to the identified synonym cache index.
-
-
11. The multi-level cache system of claim 8, wherein the second-level cache includes
a plurality of second-level cache lines each configured to store a physical memory address tag and a cache line of data; - and
a second comparator configured to compare the targeted physical memory address to a second-level physical memory address tag at a specified second-level cache line, wherein the specified second-level cache line corresponds to the targeted physical memory address.
- and
-
12. The multi-level cache system of claim 11 wherein the second comparator and the Dtag logic are configured to compare the targeted physical memory address with physical memory address tags in the second-level cache lines and in the Dtags during overlapping time periods.
-
13. The multi-level cache system of claim 11 wherein the second comparator and the Dtag logic are configured to simultaneously compare the targeted physical memory address with physical memory address tags in the second-level cache lines and in the Dtags.
-
14. The multi-level cache system of claim 8 wherein
the requested virtual memory address includes a first set of address bits representing a virtual page number and a second set of address bits representing a virtual cache index, the first and second sets of address bits overlapping at a set of vpn bits; - and
the Dtag logic includes circuitry that generates a set of VPN bits that, when used to replace the vpn bits of the virtual cache index, produces a synonym cache index that identifies a location in the first-level cache of the synonym first-level cache line.
- and
-
15. The multi-level cache system of claim 8 comprising a plurality of first-level caches that share a single second-level cache wherein the second-level cache includes Dtags for a plurality of the first-level caches.
Specification