Method and system for detecting and resolving virtual address synonyms in a two-level cache hierarchy

• US 6,751,720 B2
• Filed: 01/07/2002
• Issued: 06/15/2004
• Est. Priority Date: 06/10/2000
• Status: Expired due to Fees

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Barroso, Luiz André, Ravishankar, Mosur Kumaraswamy, Stets, Robert J. Jr., Nowatzyk, Andreas, Gharachorloo, Kourosh
• Primary Examiner(s): Sparks, Donald
• Assistant Examiner(s): CHACE, CHRISTIAN
• Application Number:
  US10/042,054
• Publication Number:
  US 20030023814A1
• Time in Patent Office: 890 Days
• Field of Search: 365/230.01, 711/117, 711/203, 711/210
• US Class Current: 711/210
• CPC Class Codes: G06F 12/0826 Limited pointers directories; State-only directories without pointers
• CPC Class Codes: G06F 12/0828 with concurrent directory accessing, i.e. handling multiple concurrent coherency transactions
• CPC Class Codes: G06F 2212/621 Coherency control relating to peripheral accessing, e.g. from DMA or I/O device

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.

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.

2. The method of claim 1 wherein the first searching includes translating the requested virtual memory address into the corresponding targeted physical memory address tag, retrieving a cache tag at a cache index corresponding to the requested virtual memory address, and comparing the targeted physical memory address tag with the retrieved cache tag.

3. The method of claim 2 wherein the translating of the requested virtual memory address, into the corresponding targeted physical memory address tag, and the retrieving of the cache tag occur during overlapping time periods.

4. The method of claim 1 wherein the second searching comprises searching a plurality of the Dtags simultaneously.

5. The method of claim 1 wherein the second-level cache comprises a plurality of second-level cache lines each configured to store a physical memory address tag, the method further comprising searching the second-level cache lines for a physical memory address tag that corresponds to the requested virtual memory address tag concurrently with the second searching.

6. The method of claim 1 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 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.

9. 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 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.

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.

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.