cols="6" colsep="0" rowsep="0">

TABLE 1

CPU-0 has
CPU-1 has
CPU-2 has
. . .
. . .
CPU-(R-1)

cacheline
cacheline
cacheline

has

cacheline

Hence, the data field of each ‘way’ of an entry in the snoop filter (10) tracks the ‘shared’ state of the cacheline in all CPUs.

An example to illustrate the dynamics between the snoop state machine (30) and the snoop filter (10) (256 entry, 4-way set associative, with a 32-entry conflict buffer) as shown in FIG. 5 to FIG. 13:

- 1) CPU-0 perform a read to address A (cacheline A). The snoop state machine (30) sends a query to the snoop filter (10).
- 2) Query address A[13:6]=5, and this entry 5 of the snoop filter (10). [31:14] is compared to all 4 tags. None matched. This resulted in a miss. The LRU chose set-0. These are passed to the snoop state machine (30).
- 3) At the same time, the conflict buffer (20) is looked up with the snoop ID=5. None of the entries in the conflict buffer (20) matched, and so a free entry into the conflict buffer (20) is assigned. Assume that entry-0 of the conflict buffer (20) is picked.
- 4) The conflict buffer (20) entry-0 is marked with ‘snoop ID’ set to 5 (A[13:6]==5), and out of the 4-bits ‘ip’ bits, bits[0] set to 1. This indicates that set-0 of snoop filter (10) entry-5 is now in progress.
- 5) The snoop state machine (30) gets a miss from snoop filter (10). Under the area-saving mode, snoop state machine (30) will send snoop requests to other 5 CPUs because it doesn't recognise if any CPU contains the cacheline A, which known as peer-cache snoop, i.e. snooping peer CPUs on the same address A.
- 6) While waiting for the snoop responses for the cacheline A. CPU-1 send a request to Cacheline B. B address [13:6] will be used reference into in the snoop filter (10).
- 7) For this example, it assume that B[13:6]==5, and thus it points to the same entry as the earlier A[13:6] (i.e. B[13:6]==A[13:6]==5). It also assume that B[31:14]!=A[31:14], so there is no hit among the tags of snoop filter (10) entry A[13:6].
- 8) Since it is a miss, LRU will select one of the way for this query. The snoop state machine (30) will be notified of the miss result and thus it will send snoop request to all other CPUs for cacheline B.
- 9) At the same time, B[13:6] is compared to all 32-entries of the conflict buffer. Since the value of B[13:6]==A[13:6]==5, entry-0 of conflict buffer (20) will indicate as a conflict hit. The current ‘in progress’ bits of conflict buffer (20) is 0001, indicating that set-0 is in use.
- 10) Hence LRU will not select set-0. It should select either set-1/2/3. Assume set-1 is selected by the LRU. So conflict buffer (20) entry-0, will set it's ‘in progress’ bits to 1100 (indicating set-0 and set are in progress). snoop state machine (30) will send peer-cache snoop requests to other 5 CPUs (CPU 0, 2, 3, 4, 5) because it doesn't know if any CPU contains the cacheline B.
- 11) Subsequently CPU-2 and CPU-3 send in requests to cacheline C and cacheline D respectively. Assume that coincidentally, C [13:6]==D [13:16]==B[13:16]==A[13:16]==5. Both C and D are mapped to entry 5 of the snoop filter (10).
- 12) Assuming C [31:14]!=D [31:14], both requests will result in a miss among the tags of entry 5 of the snoop filter (10). LRU will select set-2 for request C and set-3 for request. D. Since entry-5 of the snoop filter (10) is tracked by conflict buffer (20) entry-0, conflict buffer (20) entry-0's ‘ip’ bits are set to all ones, 1111, indicating that all 4 sets of entry-5 of the snoop filter (10) are currently snoop-in-progress.
- 13) The snoop state machine (30) will be notified of the miss result and thus it will send peer snoop request to all other CPUs for cacheline C and D.
- 14) Let's assume that, in the worst case that coincidentally CPU 4 send a request to cacheline E, and E[13:6]==5, and thus it corresponds again to entry-5 of the snoop filter (10). E[31:14] still result in a miss of the snoop filter (10). Entry-0 of conflict buffer (20) also indicates that ‘in progress’ is all ones, and thus LRU will not be able to allocate any entry to cacheline E. It indicates a ‘conflict’ to the snoop state machine (30).
- 15) Seeing the ‘conflict’ asserted, snoop state machine (30) will temporarily postpone on cacheline E's snoop query (to be retried later).
- 16) Snoop responses for cacheline A will eventually make their way to snoop state machine (30) and it will update entry-5 set-0 of the snoop filter (10) with information that CPU0 has the cacheline (cpu state or cs=100000) and the tag address (A[31:14]). The conflict buffer (20) entry-0, bits[0] is cleared, marking that set-0 of entry-5 of the snoop filter (10) is no longer in progress.
- 17) From this point onwards, the query request for cacheline address E can be retried.
- 18) Snoop responses for cacheline B, C, D will also eventually make their way back to the snoop state machine (30), and the snoop state machine (30) will update entry-5 of the Snoop filter (10), set-1 (for snoop responses corresponding to cacheline B), set-2 (for snoop responses corresponding to cacheline C), and set-3 (for snoop response corresponding to cacheline D). The entry-0 of conflict buffer, ‘in progress’ bits will eventually be cleared to all 0. When that happens, entry-0 of conflict buffer (20) is now freed up, since it no longer need to track entry-5 of the snoop filter (10), i.e. it can be freely re-assigned/recycled to track other entries of the snoop filter (10). The snoop state bits of each set in entry-5 of the snoop filter (10) is now updated with the information of which CPU has the cacheline.
- 19) Now if there is a new request from CPUx to cacheline A (or B, C, D) again, it will result in a hit in the snoop filter (10) entry 5. The data from entry 5 and the way with tag that matches address [31:14] will be used by the snoop filter (10) to determine which CPU to send the snoop request. In this example, the cpu state is 100000, this means CPU-0 has the cacheline and thus the snoop state machine (30) will only snoop CPU-0 for the cacheline A.
- 20) The previous request to cacheline E, which was postponed, can also now be retried. E[13:6] will map to entry-5 of snoop filter (10). The snoop ID of 5 is used to lookup the conflict buffer (20) but matches none. So assume entry-11 of the conflict buffer (20) is assigned. Assume the LRU chooses set-3, and thus the ‘in progress’ bits[3] of entry-11 of the conflict buffer (20) is set to 0001. The snoop state machine (30) will send out peer-cache snoop to CPU 0, 1, 2, 3, 5 for cacheline address E.
- 21) This also means previously set-3 tracks the cacheline D, but now it has been reassigned to track cacheline E.
- 22) If subsequently CPU sending a request to cacheline D, this will result in mapping to entry-5 again in the snoop filter (10). But this time it will result in a hit on set-3. However, entry-0 of conflict buffer (20) has the ‘in progress’ bits[3] set to 1, which means another earlier request is taking up set-3 and thus this request on Cacheline D has to be postponed and retried at a later time.
- 23) Once the snoop state machine (30) receives the earlier snoop responses corresponding to cacheline E, the snoop filter (10) is updated with entry-5, set 3's tag set to E, and the conflict buffer (20) entry-11 cleared.

The advantage of area-saving mode is that it will have much fewer conflict buffer (20) entries than the snoop filter (10). The snoop filter (10) can have 1 million entries, but there are only 32 entries in the conflict buffer. The conflict buffer (20) needs to be large enough to track pending or outstanding snoops. Snoop delays are not indefinite, so they do not need a very large conflict buffer. This is a big improvement over existing implementations that may have a 1:1 mapping with the snoop filter (10) for in-progress, in-use, or valid bits.

Apart from that, note that it can have a very small snoop filter (10) for this ‘area-saving’ mode. Any miss in the snoop filter (10) will just result in the snoop state machine (30) performing a peer snoop request to all CPUs and still being functionally correct. A worst-case 0-entry snoop filter (10) is analogous to the case of not enabling the snoop filter (10), where the snoop state machine (30) always sends peer snoop requests to all CPUs on every cacheline request.

Besides, the penalty of having a small snoop filter (10) in the ‘area-saving’ mode is an increase in snoop request and snoop response traffic. It does not limit the effective size of the CPU caches. i.e., CPU caches can still be made much bigger than the snoop filter (10).

The reduction in the number of peer snoop requests sent by the snoop state machine (30) is proportional to the size of the snoop filter (10). So if the area permits, the snoop filter (10) size can be increased significantly to reduce snoop traffic (both snoop requests and snoop responses).

(2) High Performance Mode.

The same structures (snoop filter (10) and conflict buffer) are used, with some differences.

Table 2 shows the difference is each set of the snoop filter (10) now tracks additional information.

TABLE 2

ID of the
CPU-0
CPU-1
CPU-2
. . .
. . .
CPU-(R-1)

CPU that
sharing
sharing
sharing

sharing

is
cacheline
cacheline
cacheline

cacheline

exclusive

ownership

Besides storing information about which CPUs could be sharing the same cacheline (having read-only permission), each entry of the snoop filter also stores the ID of the CPU that has exclusive access to the cacheline. This information is used by the snoop state machine (30) to perform different types of snoops depending on the request type and the CPU snoop state.

The second difference is that a miss on the snoop filter (10) means that none of the CPUs contains the cacheline, and thus the snoop state machine (30) does not need to send any snoop requests. Compare this to the area-saving mode, where a miss on the snoop filter (10) means the snoop state machine (30) needs to send snoop requests to all CPUs. Another way to see this is that the area-saving mode does not keep precise information about the cache states, so it can have much fewer entries, but the downside is that it causes the snoop state machine (30) to send more snoops. The high-performance mode needs to keep precise information of all CPU cache states, nothing more, nothing less, in order to send exactly the minimum number of snoops required, but in doing so, it needs more area to keep this information.

The third difference is that now, with the extra information (the ID of the CPU that is exclusive), the snoop state machine (30) can optimize the final snoop requests required depending on the type of cacheline request.

An example to illustrate how the high performance snoop filter (10) works.

- 1) CPU-0 performs a read to address A (cacheline A). The snoop state machine (30) sends a query to the snoop filter (10).
- 2) Request address A[13:6] is mapped to entry 5 (ie A[13:6] has a value of 5) in the snoop filter (10). A[31:14] is compared to all 4 tags. None matched. This resulted in a miss. The LRU chose way-0. These are passed to the snoop state machine (30). The snoop ID 5 is sent to conflict buffer (20) for lookup. Again, none matched and entry-0 of conflict buffer (20) is assigned.
- 3) The conflict buffer (20) entry-0 is marked with ‘snoop entry ID’ set to 5 (A[13:6]==5), and the 4-bits ‘in progress’ bits, ‘ip’ bits[0] set to 1. This indicates that way-0 of snoop filter (10) entry 5 is now in progress.
- 4) The snoop state machine (30) gets a miss from snoop filter (