Self-healing coarse-grained snoop filter

1. A method for filtering snoops in a coherent multiprocessor system, comprising:

receiving a request to update a target memory location at a Level-2 (L2) cache shared among multiple local processing units that each have a Level-1 (L1) cache;

performing a lookup based on the target memory location in a snoop filter that tracks entries in each L1 cache associated with each of the multiple local processing units;

selecting a victim entry to evict from the snoop filter in response to the lookup missing the snoop filter and the snoop filter lacking available space to store a new entry that corresponds to the target memory location;

establishing the new entry in a temporary overflow area;

sending a request to invalidate every cache line that maps to the selected victim entry to at least one of the multiple processing units that has one or more cache lines that map to the selected victim entry in the L1 cache associated therewith;

receiving, from the at least one processing unit, an acknowledgement indicating that every cache line that maps to the selected victim entry has been invalidated in the L1 cache associated therewith; and

moving the new entry from the temporary overflow area into the snoop filter to replace the selected victim entry in the snoop filter with the new entry that corresponds to the target memory location upon receiving the acknowledgement.

2. The method recited in claim 1 , further comprising:

installing the new entry in the snoop filter in response to the lookup based on the target memory location missing the snoop filter and the snoop filter having the available space to store the new entry.

3. The method recited in claim 1 , further comprising:

receiving a remote snoop after establishing the new entry in the temporary overflow area and before receiving the acknowledgement, the remote snoop indicating that a remote master has requested permission to modify a memory location; and

forwarding the remote snoop to one or more of the multiple local processing units in response to the remote snoop hitting the selected victim entry or the new entry.

4. The method recited in claim 1 , further comprising:

temporarily disabling the snoop filter prior to receiving the acknowledgement;

receiving a remote snoop indicating that a remote master has requested permission to modify a memory location while the snoop filter is disabled; and

forwarding the remote snoop to the L1 cache at each local processing unit.

5. The method recited in claim 1 , further comprising:

identifying, among the multiple local processing units, at least one processing unit that has one or more cache lines that map to the target memory location in response to the lookup hitting the snoop filter;

forwarding a local snoop to the identified at least one processing unit; and

updating one or more metrics associated with the entries tracked in the snoop filter that are used to select the victim entry to be evicted upon the snoop filter lacking the available space to store the new entry.

6. The method recited in claim 1 , wherein the selected victim entry comprises a least-frequently accessed entry selected from among a plurality of entries in the snoop filter that were least-recently accessed.

7. The method recited in claim 1 , wherein the selected victim entry comprises one or more of an entry in the snoop filter that was least-recently accessed, an entry in the snoop filter that was least-recently established, or a random entry in the snoop filter.

8. The method recited in claim 1 , wherein the selected victim entry comprises one or more entries in the snoop filter that the multiple local processing units have not accessed for a given time period and that remote snoops are determined to frequently hit according a ratio between accesses to the one or more entries and overall recent accesses during the given time period.

9. The method recited in claim 1 , further comprising:

flushing the snoop filter and the L1 cache at each local processing unit in response to the lookup missing the snoop filter and the snoop filter lacking the available space to store the new entry that corresponds to the target memory location, whereby the selected victim entry to evict from the snoop filter comprises every entry in the snoop filter and the request sent to each L1 cache causes the entire L1 cache to be flushed.

10. The method recited in claim 1 , wherein the L2 cache is non-inclusive.

11. A coherent multiprocessor system, comprising:

multiple local processing units that each have a Level-1 (L1) cache;

a Level-2 (L2) cache shared among the multiple local processing units, wherein the L2 cache includes a snoop filter configured to track entries in each L1 cache associated with each of the multiple local processing units; and

a processor configured to:

receive a request to update a target memory location at the L2 cache;

perform a lookup in the snoop filter based on the target memory location;

select a victim entry to evict from the snoop filter in response to the lookup missing the snoop filter and the snoop filter lacking available space to store a new entry that corresponds to the target memory location;

establish the new entry in a temporary overflow area;

send a request to invalidate every cache line that maps to the selected victim entry to at least one of the multiple processing units that has one or more cache lines that map to the selected victim entry in the L1 cache associated therewith;

receive, from the at least one processing unit, an acknowledgement indicating that every cache line that maps to the selected victim entry has been invalidated in the L1 cache associated therewith; and

move the new entry from the temporary overflow area into the snoop filter to replace the selected victim entry in the snoop filter with the new entry that corresponds to the target memory location upon receiving the acknowledgement.

12. The coherent multiprocessor system recited in claim 11 , wherein the processor is further configured to install the new entry in the snoop filter in response to the lookup missing the snoop filter and the snoop filter having the available space to store the new entry.

13. The coherent multiprocessor system recited in claim 11 , wherein the processor is further configured to:

receive a remote snoop after the new entry has been established in the temporary overflow area and before the acknowledgement is received, the remote snoop indicating that a remote master has requested permission to modify a memory location; and

forward the remote snoop to one or more of the multiple local processing units in response to the remote snoop hitting the selected victim entry or the new entry.

14. The coherent multiprocessor system recited in claim 11 , wherein the processor is further configured to:

disable the snoop filter temporarily before the acknowledgement is received;

receive a remote snoop indicating that a remote master has requested permission to modify a memory location while the snoop filter is disabled; and

forward the remote snoop to the L1 cache at each local processing unit.

15. The coherent multiprocessor system recited in claim 11 , wherein the processor is further configured to:

identify, among the multiple local processing units, at least one processing unit that has one or more cache lines that map to the target memory location in response to the lookup hitting the snoop filter;

forward a local snoop to the identified at least one processing unit; and

update one or more metrics associated with the entries tracked in the snoop filter that are used to select the victim entry to be evicted upon the snoop filter lacking the available space to store the new entry.

16. The coherent multiprocessor system recited in claim 11 , wherein the selected victim entry comprises a least-frequently accessed entry selected from among a plurality of entries in the snoop filter that were least-recently accessed.

17. The coherent multiprocessor system recited in claim 11 , wherein the selected victim entry comprises one or more of an entry in the snoop filter that was least-recently accessed, an entry in the snoop filter that was least-recently established, or a random entry in the snoop filter.

18. The coherent multiprocessor system recited in claim 11 , wherein the selected victim entry comprises one or more entries in the snoop filter that the multiple local processing units have not accessed for a given time period and that remote snoops are determined to frequently hit according a ratio between accesses to the one or more entries and overall recent accesses during the given time period.

19. The coherent multiprocessor system recited in claim 11 , wherein the processor is further configured to:

flush the snoop filter and the L1 cache at each local processing unit in response to the lookup missing the snoop filter and the snoop filter lacking the available space to store the new entry that corresponds to the target memory location, whereby the selected victim entry to evict from the snoop filter comprises every entry in the snoop filter and the request sent to each L1 cache causes the entire L1 cache to be flushed.

20. The coherent multiprocessor system recited in claim 11 , wherein the L2 cache is non-inclusive.

21. An apparatus, comprising:

means for receiving a request to update a target memory location at a non-inclusive Level-2 (L2) cache shared among multiple local processing units that each have a Level-1 (L1) cache;

means for performing a lookup based on the target memory location in a snoop filter that tracks entries in each L1 cache associated with each of the multiple local processing units;

means for selecting a victim entry to evict from the snoop filter in response to the lookup missing the snoop filter and the snoop filter lacking available space to store a new entry that corresponds to the target memory location;

means for establishing the new entry in a temporary overflow area;

means for sending a request to invalidate every cache line that maps to the selected victim entry to at least one of the multiple processing units that has one or more cache lines that map to the selected victim entry in the L1 cache associated therewith;

means for receiving, from the at least one processing unit, an acknowledgement indicating that every cache line that maps to the selected victim entry has been invalidated in the L1 cache associated therewith; and

means for moving the new entry from the temporary overflow area into the snoop filter to replace the selected victim entry in the snoop filter with the new entry that corresponds to the target memory location upon receiving the acknowledgement.

22. The apparatus recited in claim 21 , further comprising:

means for installing the new entry in the snoop filter in response to the lookup based on the target memory location missing the snoop filter and the snoop filter having the available space to store the new entry.

23. The apparatus recited in claim 21 , further comprising:

means for receiving a remote snoop after establishing the new entry in the temporary overflow area and before receiving the acknowledgement, the remote snoop indicating that a remote master has requested permission to modify a memory location; and

means for forwarding the remote snoop to one or more of the multiple local processing units in response to the remote snoop hitting the selected victim entry or the new entry.

24. The apparatus recited in claim 21 , further comprising:

means for temporarily disabling the snoop filter prior to receiving the acknowledgement;

means for receiving a remote snoop indicating that a remote master has requested permission to modify a memory location while the snoop filter is disabled; and

means for forwarding the remote snoop to the L1 cache at each local processing unit.

25. The apparatus recited in claim 21 , further comprising:

means for identifying, among the multiple local processing units, at least one processing unit that has one or more cache lines that map to the target memory location in response to the lookup hitting the snoop filter;

means for forwarding a local snoop to the identified at least one processing unit; and

means for updating one or more metrics associated with the entries tracked in the snoop filter that are used to select the victim entry to be evicted upon the snoop filter lacking the available space to store the new entry.

26. The apparatus recited in claim 21 , further comprising:

means for flushing the snoop filter and the L1 cache at each local processing unit in response to the lookup missing the snoop filter and the snoop filter lacking the available space to store the new entry that corresponds to the target memory location, whereby the selected victim entry to evict from the snoop filter comprises every entry in the snoop filter and the request sent to each L1 cache causes the entire L1 cache to be flushed.

27. A non-transitory computer-readable medium storing computer-executable instructions, the stored computer-executable instructions configured to cause one or more processors to:

receive a request to update a target memory location at a non-inclusive Level-2 (L2) cache shared among multiple local processing units that each have a Level-1 (L1) cache;

perform a lookup based on the target memory location in a snoop filter that tracks entries in each L1 cache associated with each of the multiple local processing units;

select a victim entry to evict from the snoop filter in response to the lookup missing the snoop filter and the snoop filter lacking available space to store a new entry that corresponds to the target memory location;

establish the new entry in a temporary overflow area;

send a request to invalidate every cache line that maps to the selected victim entry to at least one of the multiple processing units that has one or more cache lines that map to the selected victim entry in the L1 cache associated therewith;

receive, from the at least one processing unit, an acknowledgement indicating that every cache line that maps to the selected victim entry has been invalidated in the L1 cache associated therewith; and

move the new entry from the temporary overflow area into the snoop filter to replace the selected victim entry in the snoop filter with the new entry that corresponds to the target memory location upon receiving the acknowledgement.

28. A method for filtering snoops in a coherent multiprocessor system, comprising:

receiving a request to update a target memory location at a Level-2 (L2) cache shared among multiple local processing units that each have a Level-1 (L1) cache;

performing a lookup based on the target memory location in a snoop filter that tracks entries in each L1 cache associated with each of the multiple local processing units;

selecting a victim entry to evict from the snoop filter in response to the lookup missing the snoop filter and the snoop filter lacking available space to store a new entry that corresponds to the target memory location;

sending a request to invalidate every cache line that maps to the selected victim entry to at least one of the multiple processing units that has one or more cache lines that map to the selected victim entry in the L1 cache associated therewith;

flushing the snoop filter and the L1 cache at each local processing unit in response to the lookup missing the snoop filter and the snoop filter lacking the available space to store the new entry that corresponds to the target memory location, whereby the selected victim entry to evict from the snoop filter comprises every entry in the snoop filter and the request sent to each L1 cache causes the entire L1 cache to be flushed; and

replacing the selected victim entry in the snoop filter with the new entry that corresponds to the target memory location.

29. The method recited in claim 28 , further comprising:

temporarily disabling the snoop filter prior to receiving an acknowledgement from the at least one processing unit indicating that every cache line that maps to the selected victim entry has been invalidated in the L1 cache associated therewith;

receiving a remote snoop indicating that a remote master has requested permission to modify a memory location while the snoop filter is disabled; and

forwarding the remote snoop to the L1 cache at each local processing unit.

30. The method recited in claim 28 , wherein the L2 cache is non-inclusive.

31. A coherent multiprocessor system, comprising:

multiple local processing units that each have a Level-1 (L1) cache;

a Level-2 (L2) cache shared among the multiple local processing units, wherein the L2 cache includes a snoop filter configured to track entries in each L1 cache associated with each of the multiple local processing units; and

a processor configured to:

receive a request to update a target memory location at the L2 cache;

perform a lookup in the snoop filter based on the target memory location;

select a victim entry to evict from the snoop filter in response to the lookup missing the snoop filter and the snoop filter lacking available space to store a new entry that corresponds to the target memory location;

send a request to invalidate every cache line that maps to the selected victim entry to at least one of the multiple processing units that has one or more cache lines that map to the selected victim entry in the L1 cache associated therewith;

flush the snoop filter and the L1 cache at each local processing unit in response to the lookup missing the snoop filter and the snoop filter lacking the available space to store the new entry that corresponds to the target memory location, whereby the selected victim entry to evict from the snoop filter comprises every entry in the snoop filter and the request sent to each L1 cache causes the entire L1 cache to be flushed; and

replace the selected victim entry in the snoop filter with the new entry that corresponds to the target memory location.

32. The coherent multiprocessor system recited in claim 31 , wherein the processor is further configured to:

disable the snoop filter temporarily until an acknowledgement is received from the at least one processing unit to indicate that every cache line that maps to the selected victim entry has been invalidated in the L1 cache associated therewith;

receive a remote snoop indicating that a remote master has requested permission to modify a memory location while the snoop filter is disabled; and

forward the remote snoop to the L1 cache at each local processing unit.

33. The coherent multiprocessor system recited in claim 31 , wherein the L2 cache is non-inclusive.