Granted Patent B1

US 12,499,050 · App. 18/910,922 · Granted Dec 16, 2025

Inventors: John G. Favor (San Francisco, CA); Srivatsan Srinivasan (Cedar Park, TX); Robert Haskell Utley (Austin, TX)

Assignee: Ventana Micro Systems Inc.

G06F12/0864G06F3/0626G06F3/0659G06F3/0673G06F2212/6032

Abstract

Claims (89)

1 . A method, comprising:

in a cache memory subsystem comprising a first-level cache and an N-way set associative second-level cache that is inclusive of the first-level cache;

receiving a physical memory line address for allocation into the second-level cache;

using a set index portion of the physical memory line address to select a set of N ways of the second-level cache;

for each way of the selected set of N ways of the second-level cache, forming a physical address proxy (PAP) for the physical memory line address corresponding to the way, wherein each formed PAP includes the set index portion and the corresponding way that uniquely identifies a corresponding one of the selected set of N ways of second-level cache;

for each of the N formed PAPs, receiving a corresponding indicator of whether the formed PAP is resident in the first-level cache; and

selecting one way of the selected set of N ways of the second-level cache having a corresponding indicator indicating that the corresponding one of the N formed PAPs is not resident in the first-level cache.

2 . The method of claim 1 , wherein the first-level cache is configured to be accessed using virtual addresses, further comprising:

detecting, by the cache memory subsystem, that a virtual address misses in the first-level cache;

translating at least a portion of the virtual address into the physical memory line address for allocation into the selected one way of the selected set of N ways of the second-level cache; and

allocating the corresponding one of the N formed PAPs that is not resident in the first-level cache into an entry of the first-level cache.

3 . The method of claim 1 , wherein the cache memory subsystem further comprises a load/store unit, the method further comprising:

using, by the load/store unit, PAPs obtained from the first-level cache rather than corresponding physical memory line addresses to make store-to-load forwarding-related comparisons; and

said selecting comprising selecting one way of the selected set of N ways of the second-level cache to minimize a likelihood that the formed PAP corresponding to the selected way is already in use as a proxy for a physical memory line address different from the received physical memory line address.

4 . The method of claim 1 , wherein the cache memory subsystem further comprises a PAP directory having entries corresponding to the entries of the first-level cache, the method further comprising:

when a PAP for a physical memory line address is allocated into an entry of the first-level cache, allocating the PAP into a corresponding entry of the PAP directory; and

for each of the N formed PAPs, looking up the formed PAP in the PAP directory, wherein the PAP directory is configured to provide the corresponding indicator to indicate whether the formed PAP is resident in the first-level cache.

5 . The method of claim 4 , wherein said looking up the formed PAP in the PAP directory comprises concurrently looking up each of the N formed PAPs in the PAP directory and concurrently setting the corresponding one of N indicators to indicate whether the corresponding one of N formed PAPs is resident in the first-level cache.

6 . The method of claim 4 ,

wherein the first-level cache is configured to be accessed using virtual addresses, is logically arranged as S sets and W ways, and is configured to be indexed to select a set of the S sets using T translated bits and U untranslated bits of a virtual address such that a PAP may be allocated into 2{circumflex over ( )}T different sets of the first-level cache;

wherein the PAP directory is physically arranged as S/(2{circumflex over ( )}T) rows and W*(2{circumflex over ( )}T) columns; and

wherein the concurrently looking up each of the N formed PAPs in the PAP directory comprises using U untranslated bits within the set index portion of the physical memory line address to select a row of the PAP directory.

7 . The method of claim 6 ,

wherein to allocate a PAP into the entry of the PAP directory corresponding to an entry of the first-level cache:

the U untranslated bits of the virtual address are used to select a row of the PAP directory; and

the T translated bits of the virtual address are used to select W columns of the PAP directory from which to select one column of the selected W columns into which to write a diminutive PAP (dPAP); and

wherein the dPAP is remaining bits of the PAP other than bits of the set index portion of the physical memory line address that correspond to the U untranslated bits of the virtual address; and

wherein said concurrently looking up each of the N formed PAPs in the PAP directory comprises:

for each of the N formed PAPs, concurrently comparing a dPAP portion of the formed PAP with each of the W*(2{circumflex over ( )}T) dPAPs of the selected row of the PAP directory to detect whether the PAP is resident in the PAP directory.

8 . A cache memory subsystem, comprising:

a first-level cache; and

an N-way set associative second-level cache that is inclusive of the first-level cache, wherein the second-level cache is configured to:

receive a physical memory line address for allocation into the second-level cache;

use a set index portion of the physical memory line address to select a set of N ways of the second-level cache;

for each way of the selected set of N ways of the second-level cache, form a physical address proxy (PAP) for the physical memory line address corresponding to the way, wherein each formed PAP includes the set index portion and the corresponding way that uniquely identifies a corresponding one of the selected set of N ways of second-level cache;

for each of the N formed PAPs, receive a corresponding indicator of whether the formed PAP is resident in the first-level cache; and

select one way of the selected set of N ways of the second-level cache having a corresponding indicator indicating that the corresponding one of the N formed PAPs is not resident in the first-level cache.

9 . The cache memory subsystem of claim 8 , wherein the first-level cache is configured to be accessed using virtual addresses, and wherein the cache memory subsystem is further configured to:

translate at least a portion of a virtual address that misses in the first-level cache into the physical memory line address;

allocate the physical memory line address into the selected one way of the selected set of N ways of the second-level cache; and

allocate the corresponding one of the N formed PAPs that is not resident in the first-level cache into an entry of the first-level cache.

10 . The cache memory subsystem of claim 8 , further comprising:

a load/store unit that uses the PAPs obtained from the first-level cache rather than corresponding physical memory line addresses to make store-to-load forwarding-related comparisons; and

wherein the one way of the selected set of N ways of the second-level cache is selected to minimize a likelihood that the formed PAP corresponding to the selected way is already in use as a proxy for a physical memory line address different from the received physical memory line address.

11 . The cache memory subsystem of claim 8 , further comprising:

a PAP directory having entries corresponding to the entries of the first-level cache, so that when a PAP for a physical memory line address is allocated into an entry of the first-level cache, the PAP is also allocated into the corresponding entry of the PAP directory; and

wherein the cache memory subsystem is further configured to:

for each of the N formed PAPs, look up the formed PAP in the PAP directory, wherein the PAP directory is configured to provide the corresponding indicator to indicate whether the formed PAP is resident in the first-level cache.

12 . The cache memory subsystem of claim 11 , wherein the cache memory subsystem is configured to concurrently look up each of the N formed PAPs in the PAP directory and wherein the PAP directory is configured to concurrently provide the N corresponding indicators each indicating whether a corresponding one of the N formed PAPs is resident in the first-level cache.

13 . The cache memory subsystem of claim 12 ,

wherein the first-level cache is configured to be accessed using virtual addresses, and wherein the first-level cache is logically arranged as S sets and W ways and is configured to be indexed to select a set of the S sets using T translated bits and U untranslated bits of a virtual address such that a PAP may be allocated into 2{circumflex over ( )}T different sets of the first-level cache;

wherein the PAP directory is physically arranged as S/(2{circumflex over ( )}T) rows and W*(2{circumflex over ( )}T) columns; and

wherein to concurrently look up each of the N formed PAPs in the PAP directory, the cache memory subsystem is configured to use U untranslated bits within the set index portion of the physical memory line address to select a row of the PAP directory.

14 . The cache memory subsystem of claim 13 ,

wherein to allocate a PAP into the entry of the PAP directory corresponding to an entry of the first-level cache:

the U untranslated bits of the virtual address are used to select a row of the PAP directory; and

the T translated bits of the virtual address are used to select W columns of the PAP directory from which to select one column of the selected W columns into which to write a diminutive PAP (dPAP); and

wherein the dPAP is remaining bits of the PAP other than bits of the set index portion of the physical memory line address that correspond to the U untranslated bits of the virtual address; and

wherein to concurrently look up each of the N formed PAPs in the PAP directory, the cache memory subsystem is configured to:

for each of the N formed PAPs, concurrently compare a dPAP portion of the formed PAP with each of the W*(2{circumflex over ( )}T) dPAPs of the selected row of the PAP directory to detect whether the PAP is resident in the PAP directory.

15 . A non-transitory computer-readable medium having instructions stored thereon that are capable of causing or configuring a cache memory subsystem to perform operations comprising:

in a cache memory subsystem comprising a first-level cache and an N-way set associative second-level cache that is inclusive of the first-level cache;

receiving a physical memory line address for allocation into the second-level cache;

using a set index portion of the physical memory line address to select a set of N ways of the second-level cache;

for each way of the selected set of N ways of the second-level cache, forming a physical address proxy (PAP) for the physical memory line address corresponding to the way, wherein each formed PAP includes the set index portion and the corresponding way that uniquely identifies a corresponding one of the selected set of N ways of second-level cache;

for each of the N formed PAPs, receiving a corresponding indicator of whether the formed PAP is resident in the first-level cache; and

selecting one way of the selected set of N ways of the second-level cache having a corresponding indicator indicating that the corresponding one of the N formed PAPs is not resident in the first-level cache.

16 . The non-transitory computer-readable medium of claim 15 , wherein the first-level cache is configured to be accessed using virtual addresses, further comprising:

detecting, by the cache memory subsystem, that a virtual address misses in the first-level cache;

translating at least a portion of the virtual address into the physical memory line address for allocation into the selected one way of the selected set of N ways of the second-level cache; and

allocating the corresponding one of the N formed PAPs that is not resident in the first-level cache into an entry of the first-level cache.

17 . The non-transitory computer-readable medium of claim 15 , wherein the cache memory subsystem further comprises a load/store unit, the method further comprising:

using, by the load/store unit, PAPs obtained from the first-level cache rather than corresponding physical memory line addresses to make store-to-load forwarding-related comparisons; and

said selecting comprising selecting one way of the selected set of N ways of the second-level cache to minimize a likelihood that the formed PAP corresponding to the selected way is already in use as a proxy for a physical memory line address different from the received physical memory line address.

18 . The non-transitory computer-readable medium of claim 15 , wherein the cache memory subsystem further comprises a PAP directory having entries corresponding to the entries of the first-level cache, the method further comprising:

when a PAP for a physical memory line address is allocated into an entry of the first-level cache, allocating the PAP into a corresponding entry of the PAP directory; and

for each of the N formed PAPs, looking up the formed PAP in the PAP directory, wherein the PAP directory is configured to provide the corresponding indicator to indicate whether the formed PAP is resident in the first-level cache.

19 . The non-transitory computer-readable medium of claim 18 , wherein said looking up the formed PAP in the PAP directory comprises concurrently looking up each of the N formed PAPs in the PAP directory and concurrently setting the corresponding one of N indicators to indicate whether the corresponding one of N formed PAPs is resident in the first-level cache.

20 . The non-transitory computer-readable medium of claim 19 ,

wherein the first-level cache is configured to be accessed using virtual addresses, is logically arranged as S sets and W ways, and is configured to be indexed to select a set of the S sets using T translated bits and U untranslated bits of a virtual address such that a PAP may be allocated into 2{circumflex over ( )}T different sets of the first-level cache;

wherein the PAP directory is physically arranged as S/(2{circumflex over ( )}T) rows and W*(2{circumflex over ( )}T) columns; and

wherein said concurrently looking up each of the N formed PAPs in the PAP directory comprises using U untranslated bits within the set index portion of the physical memory line address to select a row of the PAP directory.

21 . The non-transitory computer-readable medium of claim 20 ,

wherein to allocate a PAP into the entry of the PAP directory corresponding to an entry of the first-level cache:

the U untranslated bits of the virtual address are used to select a row of the PAP directory; and

the T translated bits of the virtual address are used to select W columns of the PAP directory from which to select one column of the selected W columns into which to write a diminutive PAP (dPAP); and

wherein the dPAP is remaining bits of the PAP other than bits of the set index portion of the physical memory line address that correspond to the U untranslated bits of the virtual address; and

wherein said concurrently looking up each of the N formed PAPs in the PAP directory comprises:

for each of the N formed PAPs, concurrently comparing a dPAP portion of the formed PAP with each of the W*(2{circumflex over ( )}T) dPAPs of the selected row of the PAP directory to detect whether the PAP is resident in the PAP directory.

Assignments (1)

Continuity (20)

References Cited (48)