Using cuckoo movement for improved cache coherency

Patent metadata

Field	Value
Publication number	US-9535848-B2
Application number	US-201414308370-A
Country	US
Kind code	B2
Filing date	Jun 18, 2014
Priority date	Jun 18, 2014
Publication date	Jan 3, 2017
Grant date	Jan 3, 2017

Abstract

Example implementations of the present disclosure are directed to handling the eviction of a conflicting cuckoo entry while reducing performance degradation resulting. In example implementations, when an address is replacing another address, the evicted address does not necessarily map to the same places as the new address. Example implementations attempt to conduct a run through of the cache coherent directory with the new entry such that the evicted address can find an empty entry in the directory and fill the empty entry.

First claim

What is claimed is:

1. A method, comprising:
managing a coherency directory for a cache coherent system, the coherency directory comprising a plurality of entries arranged in a cuckoo hash;
for a new entry for the coherency directory causing a replacement of one of the plurality of entries in the coherency directory:
placing the replaced one of the plurality of entries into an eviction buffer; and
attempting to reinsert the replaced one of the plurality of entries into a different position within the coherency directory;

wherein the attempting to reinsert the replaced one of the plurality of entries comprises:
invoking a clean invalid operation to the coherency directory;
for the clean invalid operation finding an empty location in the coherency directory for the replaced one of the plurality of entries, canceling the clean invalid operation and moving the replaced one of the plurality of entries into the empty location;
for the clean invalid operation not finding an empty location in the coherency directory for the replaced one of the plurality of entries, removing one or more of the plurality of entries through a snoop operation triggered by the clean invalid operation.

2. The method of claim 1 , wherein the coherency directory is larger than a total cache capacity of the cache coherent system.

3. The method of claim 1 , wherein the attempting to reinsert the replaced one of the plurality of entries comprises:
performing a lookup on the replaced one of the plurality of entries;
for the lookup having a response of another one of the plurality of entries that is not the new entry; replacing the another one of the plurality of entries with the replaced one of the plurality of entries and placing the another one of the plurality of entries into the eviction buffer.

4. The method of claim 3 , wherein the performing the lookup is done once during a spare cycle during management of the cache coherent system.

5. The method of claim 3 , wherein the performing the lookup is forced based on an algorithm.

6. The method of claim 1 , wherein a lookup is performed on an entry in the eviction buffer for a multiple number of times until an empty entry is found or the eviction buffer being empty, the number of times subject to a limit;
for the empty entry being found, placing the entry in the eviction buffer into the empty entry;
for the empty entry not being found and the number of times not exceeding the limit; replacing an entry corresponding to the lookup with the entry in the eviction buffer, and placing the entry corresponding to the lookup into the eviction buffer; and
for the eviction buffer not being empty and the number of times exceeding the limit, triggering a snoop operation on entries in the eviction buffer.

7. The method of claim 6 , wherein the limit is a fixed limit.

8. The method of claim 6 , wherein the limit is set proportionally to a capacity of the eviction buffer.

9. The method of claim 1 , wherein the attempting to reinsert the replaced one of the plurality of entries comprises:
performing a single lookup on the replaced one of the plurality of entries;
for the lookup having a response of another one of the plurality of entries that is an empty location; placing the replaced one of the plurality of entries into the another one of the plurality of entries.

10. A controller of a cache coherent system configured to:
manage a coherency directory for the cache coherent system, the coherency directory comprising a plurality of entries arranged in a cuckoo hash;
for a new entry for the coherency directory causing a replacement to one of the plurality of entries in the coherency directory:
place the replaced one of the plurality of entries into an eviction buffer; and
attempt to reinsert the replaced one of the plurality of entries into a different position within the coherency directory;

wherein the controller is configured to attempt to reinsert the replaced one of the plurality of entries by:
invoking a clean invalid operation to the coherency directory;
for the clean invalid operation finding an empty location in the coherency directory for the replaced one of the plurality of entries, canceling the clean invalid operation and moving the replaced one of the plurality of entries into the empty location;
for the clean invalid operation not finding an empty location in the coherency directory for the replaced one of the plurality of entries, removing one or more of the plurality of entries through a snoop operation triggered by the clean invalid operation.

11. The controller of claim 10 , wherein the coherency directory is larger than a total cache capacity of the cache coherent system.

12. The controller of claim 10 , wherein the controller is configured to attempt to reinsert the replaced one of the plurality of entries by:
performing a lookup on the replaced one of the plurality of entries;
for the lookup having a response of another one of the plurality of entries that is not the new entry; replacing the another one of the plurality of entries with the replaced one of the plurality of entries and placing the another one of the plurality of entries into the eviction buffer.

13. The controller of claim 12 , wherein the controller is configured to perform the lookup by conducting the lookup once during a spare cycle during management of the cache coherent system.

14. The controller of claim 12 , wherein the controller is configured to perform the lookup based on an algorithm.

15. The controller of claim 10 , wherein the controller is configured to perform a lookup an entry in the eviction buffer for a multiple number of times until an empty entry is found or the eviction buffer being empty, the number of times subject to a limit;
for the empty entry being found, placing the entry in the eviction buffer into the empty entry;
for the empty entry not being found and the number of times not exceeding the limit; replacing an entry corresponding to the lookup with the entry in the eviction buffer, and placing the entry corresponding to the lookup into the eviction buffer; and
for the eviction buffer not being empty and the number of times exceeding the limit, triggering a snoop operation on entries in the eviction buffer.

16. The controller of claim 15 , wherein the limit is a fixed limit.

17. The controller of claim 15 , wherein the limit is set proportionally to a capacity of the eviction buffer.

18. The controller of claim 10 , wherein the controller is configured to attempt to reinsert the replaced one of the plurality of entries by:
performing a single lookup on the replaced one of the plurality of entries;

for the lookup having a response of another one of the plurality of entries that is an empty location; placing the replaced one of the plurality of entries into the another one of the plurality of entries.

Assignees

• Netspeed Systems

Inventors

• Rowlands Joe
• Kumar Sailesh

Classifications

• G06F12/0891 Primary

  using clearing, invalidating or resetting means · CPC title

• G06F2212/69

  Physics · mapped topic

• G06F17/3033

  Physics · mapped topic

• G06F2212/1041

  Resource optimization · CPC title

• G06F12/0817

  using directory methods · CPC title