Granted Patent B2

US 12,730,755 · App. 18/364,041 · Granted Sep 8, 2026

Inventors: Patrick J. Shyvers (Ft. Collins, CO); William L Walker (Ft. Collins, CO)

Assignee: ADVANCED MICRO DEVICES, INC.

G06F12/0871G06F12/0864G06F2212/1021

Abstract

Claims (54)

1 . A method for operating a cache memory in a computing system, the method comprising:

receiving a request for a first data item from the cache memory of the computing system, the first data item having an associated tag value;

performing a lookup in a Bloom filter for the tag value associated with the first data item;

performing a lookup in the cache memory for the requested first data item based on the lookup in the Bloom filter; and

updating the Bloom filter based on results of the lookup in the cache memory for the requested first data item, wherein updating the Bloom filter comprises sending multiple tag values from a plurality of cache ways in a set index accessed during the lookup to the Bloom filter.

2 . The method of claim 1 , wherein performing the lookup in the Bloom filter for the tag value associated with the first data item comprises:

computing indices for the Bloom filter based on the tag value associated with the first data item.

3 . The method of claim 2 , wherein computing one or more indices for the Bloom filter based on the tag value associated with the first data item comprises:

performing one or more hash functions on the tag value associated with the first data item.

4 . The method of claim 1 , wherein the cache memory comprises a set associative structure with the plurality of cache ways and a plurality of sets, each set comprises a cache block from each way.

5 . The method of claim 4 , wherein performing the lookup in the cache memory for the requested first data item based on the lookup in the Bloom filter comprises:

retrieving tag values associated with cache blocks in the set index of the plurality of sets for the requested first data item; and

comparing the retrieved tag values with the tag value associated with the first data item.

6 . The method of claim 5 , wherein updating the Bloom filter based on results of the lookup in the cache memory for the requested first data item comprises:

computing indices for the Bloom filter for each retrieved tag value in the set index of the cache memory; and

setting each of the computed indices of the Bloom filter to a value of one.

7 . The method of claim 4 , further comprising:

removing a cache block from a first set index in the cache memory; and

computing indices for the Bloom filter for tag values of each remaining cache block in the first set index of the cache memory; and

setting each of the computed indices of the Bloom filter to a value of one.

8 . The method of claim 1 , wherein performing the lookup in the cache memory for the requested first data item based on the lookup in the Bloom filter further comprises:

canceling the lookup in the cache memory for the requested first data item when the lookup in the Bloom filter for the tag value associated with the first data item results in a miss.

9 . The method of claim 8 , wherein after canceling the lookup in the cache memory for the requested first data item, performing a lookup in a different level of the cache memory for the requested first data item.

10 . An apparatus for operating a cache memory, the apparatus comprising:

a cache controller in the cache memory, the cache memory comprising a set associative structure with a plurality of cache ways and a plurality of sets, each set comprises a cache block from each way;

a hit prediction table in the cache memory, the hit prediction table comprising a Bloom filter, the hit prediction table being configured to:

perform a lookup in the Bloom filter for a tag value associated with a first data item requested from the cache memory; and

update the Bloom filter with results of a lookup in the cache memory for the requested first data item, wherein updating the Bloom filter comprises, during the lookup in the cache memory for the requested first data item, sending tag values from all the cache ways in a set index for the requested first data item to the Bloom filter.

11 . The apparatus of claim 10 , wherein to perform the lookup in the Bloom filter for the tag value associated with the first data item, the hit prediction table is further configured to:

compute indices for the Bloom filter based on the tag value associated with the first data item.

12 . The apparatus of claim 10 , wherein the cache controller is configured to:

perform the lookup in the cache memory for the requested first data item based on the lookup in the hit prediction table.

13 . The apparatus of claim 12 , wherein the cache controller is configured to:

cancel the lookup in the cache memory for the requested first data item when the lookup in the hit prediction table for the tag value associated with the first data item results in a miss.

14 . The apparatus of claim 12 , wherein the cache controller is further configured to:

retrieve tag values associated with cache blocks in the set index of the plurality of sets for the requested first data item;

compare the retrieved tag values with the tag value associated with the first data item;

computing indices for the Bloom filter for results of the lookup in the cache memory; and

setting each of the computed indices of the Bloom filter to a value of one.

15 . The apparatus of claim 14 , wherein the Bloom filter has a different number of indexes than the cache memory.

16 . A non-transitory computer-readable storage device storing instructions that, when executed by a computing system, cause the computing system to perform a method for operating a cache memory, the method comprising:

receiving a request for a first data item from the cache memory of the computing system, the first data item having an associated tag value;

performing a lookup in a Bloom filter for the tag value associated with the first data item;

performing a lookup in the cache memory for the requested first data item based on the lookup in the Bloom filter; and

updating the Bloom filter based on results of the lookup in the cache memory for the requested first data item, wherein updating the Bloom filter comprises, during the lookup in the cache memory for the requested first data item, sending tag values from all cache ways in a set index for the requested first data item to the Bloom filter.

17 . The non-transitory computer-readable storage device of claim 16 , further comprising instructions that cause the computing system to perform the method for operating the cache memory, the method further comprising:

computing indices for the Bloom filter based on the tag value associated with the first data item.

18 . The non-transitory computer-readable storage device of claim 16 , wherein the cache memory comprises a set associative structure with a plurality of cache ways and a plurality of sets, each set comprises a cache block from each way.

19 . The non-transitory computer-readable storage device of claim 18 , further comprising instructions that cause the computing system to perform the method for operating the cache memory, the method further comprising:

retrieving tag values associated with cache blocks in the set index of the plurality of sets for the requested first data item; and

comparing the retrieved tag values with the tag value associated with the first data item.

20 . The non-transitory computer-readable storage device of claim 19 , wherein when the lookup in the cache memory results in removal of a cache line from the cache memory, updating the Bloom filter comprises:

sending tag values of remaining cache blocks in the set index to the Bloom filter; and

computing indices for the Bloom filter for the tag values of the remaining cache blocks.

Assignments (1)

Continuity (1)

References Cited (10)