Partially inclusive snoop filter

In some embodiments, the invention includes a snoop filter, wherein entries in the snoop filter are allocated in response to initial accesses of local cache lines by a remote node, but entries in the snoop filter are not allocated in response to accesses of the local cache lines by a local node. Other embodiments are described and claimed.

RELATED APPLICATION

BACKGROUND OF THE INVENTION

1. Technical Field of the Invention

The present invention relates to computer systems and, more particularly, to a multi-node computer system with a snoop filter.

2. Background Art

Large multi-processor computer systems are often organized in nodes in which at least some of the nodes include main memory, some number of processors and associated caches. Multiple processors can access and modify a cache line. An access is a read or write transaction (request) with respect to the cache line. A write request may be handled in directly such as through a read for ownership. A cache coherency protocol allows the processors to use the most recently updated version of the cache line. A popular cache coherency protocol is the MESI (modified, exclusive, shared, or invalid) protocol. There are various variants of the MESI protocol.

Snoop filters/directories have been designed to help maintain cache coherency between nodes. For example,FIG. 1illustrates a multi-node processor system including a node0and a node1. Multi-node systems may include more than two nodes. Node0includes a processor bus0(sometimes called a front side bus), four processors P0, P1, P2, and P3, a memory controller hub14, and main memory16. The processor bus has been a multi-drop bus, but using a point-to-point interconnect bus has been suggested. Node1includes a processor bus1, four processors P4, P5, P6, and P7, a memory controller hub24, and main memory26. Processors P0, P1, . . . P7have corresponding caches18-0,18-1, . . .18-7. For some processors, the caches are called L0, L1, and L2caches, but the names are not important and there may be more or less than three caches per processor. The L2caches may be on the same die as the processor or on a different die. A coherency controller switch30is coupled between memory controller hubs14and24as well as I/O hub38and I/O hub40. Memory controller hubs14and24are sometimes referred to as a North bridge. Memory controller hub14is the local (home) memory controller hub for node0and memory controller hub24is the local memory controller hub for node1. I/O hubs38and40are sometimes referred to as South bridges. I/O hubs38and40also have caches42and44respectively. The caches of the I/O hubs and the caches of the processors are called caching agents.

An individual node include circuitry to maintain cache coherency inside that node through a cache coherency protocol such as the MESI protocol or a variant of it. For example, the circuitry to maintain cache coherency in node0is distributed amongst interfaces for memory controller hub14and processors P0-P3.

Coherency controller switch30routes transactions between nodes, tracks requests, and broadcasts snoops. Cache controller switch30includes a snoop filter34. Snoop filter34tracks the state and location of cache lines held in the processor caches and I/O hub caches. A benefit of the snoop filter is to eliminate the need to broadcast unneeded snoop requests to all caching agents, thus reducing latency of coherent memory accesses, decreasing bandwidth utilization, and improving system performance. If an access is made that is a miss in snoop filter34, a memory read is issued to the local memory controller hub, and a location in snoop filter34is allocated to track the cache line. It is safe to fetch data from memory without snooping the processor bus.

Due to the finite number of entries, a miss in snoop filter34may indicate there are no available entries. In such a case, a victim entry will be selected for eviction/back invalidation. A drawback of snoop filter34is that it must be sized to match the cumulative size of all the caches in the system to be effective. If the snoop filter is not sized appropriately then the processor caches will receive an excessive number of back invalidates due to frequent replacements in the snoop filter. This will limit the cache utilization of the processors resulting in the system under performing.

Snoop filter34may include multiple snoop filters that are physically different. For example, one snoop filter could be for even cache lines and another could be for odd cache lines. The multiple snoop filters do not have to be in a centrally located snoop filter, but rather may be distributed (e.g., in memory controller hubs and/or in memory interfaces integrated with the processor). In a uniform memory access (UMA) system, all memory locations have an essentially equal access time for each processor.

In a non-uniform memory access (NUMA) system, memory locations (addresses of cache lines) are shared by the processors, but some memory locations are accessed more quickly by some processors than by others. For example, inFIG. 1, processors in node0can access locations in main memory16more quickly than processors in node0can access locations in main memory26. Further, a particular range of memory locations may be assigned to node0and another range may be assigned to node1. The programmer of the operating system (OS) or other programs may take advantage of this locality by having processors in node0tend to use the memory location in the range associated with node0and processors in node1tend to use the memory locations in the range associated with node1.

DETAILED DESCRIPTION

Referring toFIG. 2, a multi-node computer system50includes nodes0,1. . . N, and a coherency controller switch60coupled between the nodes. Coherency controller switch60routes transactions between nodes, tracks requests, and broadcasts snoops. Coherency controller switch60includes a snoop filter64. The invention is not limited to particular details for nodes0. . . N or to a particular number of nodes. System50may be a NUMA system.

FIG. 3illustrates details of some embodiments of nodes, but the invention is not limited to these details.FIG. 3illustrates only nodes0,1,2, and3, but there may be additional nodes. Further, system50may include other circuitry that is not illustrated inFIG. 3. Node0is a multi-processor node that includes memory controller hub14, main memory16, a processor bus0, processors P0, P1, P2, and P3with corresponding caches18-0,18-1,18-2, and18-3. Likewise, node1includes memory controller hub24, main memory26, a processor bus1, processors P4, P5, P6, and P7with corresponding caches18-4,18-5,18-6, and18-7. Caches18-0. . .18-7are not restricted to a particular type of cache or cache protocols. Node2includes I/O hub38and node3includes I/O hub40. Processor buses0and1may be multi-drop buses or point-to-point interconnect buses. Nodes2and3might also be considered to include additional I/O devices (not illustrated) that are coupled to I/O hubs38and40. It is not required that nodes0and1be identical or that nodes2and3be identical.

The nodes may include circuitry to maintain cache coherency through the MESI protocol or a variant of it within the node. For example, node0may include circuitry distributed in interfaces of memory controller hub14and interfaces of processors P0to P3to maintain cache coherency within node0.

Merely as an example and not a limitation,FIG. 4illustrates L0, L1, and L2caches (making up cache18-0) on the same die as processor P0.FIG. 5illustrates the L2cache as being on a different die than processor P0. The invention is not limited to systems that include L0, L1, and L2caches.

In some embodiments, each node has a particular address range of cache lines assigned to it. That is, each cache line is assigned to a particular node. The node to which a cache line is assigned is referred to as its local node (or home node). Other nodes are remote nodes with respect to the cache line.

Snoop filter64tracks the state and location of cache lines held in the processor caches and I/O hub caches. A benefit of the snoop filter is to eliminate the need to broadcast unneeded invalidates to all caching agents, thus reducing latency of writes, decreasing bandwidth utilization, and improving system performance.

The operation of coherency controller switch60and snoop filter64inFIGS. 2 and 3differs from that of prior art coherency controller switch30and snoop filter34inFIG. 1in the following ways. In the case of the prior art system inFIG. 1, when either a local node or a remote node makes an access to a cache line, snoop filter34is consulted. If there is not an entry in snoop filter34for the cache line (i.e., a miss), an entry is allocated for the cache line in snoop filter34. If there is already an entry for the cache line in snoop filter34(i.e., a hit), then appropriate snoops are made and communicated and the entry in snoop filter34is updated according to the MESI protocol or a variant of it. Accordingly, all accesses to a cache line whether by remote or local nodes are tracked by snoop filter34.

The following are three way in which the operation of coherency controller switch30and snoop filter34differs from that of coherency controller switch60and snoop filter64.

1. An entry in snoop filter64is not allocated in response to an access of a local cache line by a local node (home node). However, when a local node accesses a local cache line, snoop filter64is consulted to see if there is already an entry for the local cache line. If there is not already an entry in snoop filter64(a miss), a remote node has not accessed the cache line and the access by the local node will continue without allocating an entry in snoop filter64. A remote snoop is not needed. If there is already an entry in snoop filter64(a hit), it is because a remote node (non-home node) has already accessed the local cache line and the access by the local node is tracked in snoop filter64by an appropriate updating of the entry according to the MESI protocol or a variant of it. Appropriate snoops of remote nodes are made according to the MESI protocol or a variant of it and snoop responses are collected. Accordingly, not all accesses of a cache line are tracked by snoop filter64, but only those accesses of the cache line that are made by a remote node or that are made by a local node when there is already an entry in snoop filter64because of previous access by a remote node.

For example, assume cache line X is assigned to node0and an entry is not allocated in snoop filter64for cache line X. Accordingly, cache line X is local with respect to node0, node0is the local node, and nodes1,2, and3are remote nodes. If node0accesses cache line X, an entry is not allocated in snoop filter64for cache line X and the allocation continues. Now assume cache line X is assigned to node0and an entry has already been allocated in snoop filter64for cache line X because node1has accessed it. In that case, future accesses of cache line X by node0are tracked by snoop filter64with appropriate snoops, collection of snoop responses, and updating of the entry.

2. If a remote node accesses a local cache line where it misses in snoop filter64, a cacheable access (read with snoop) is issued by coherency controller switch60to the local node. In the cacheable access, there is a snoop of the local processor bus and a memory read to the memory of that node. The snoop of the local processor bus is made because the cache line may be modified in a cache of one of the processors of the local node. Any modification to the cache line by the local node would not be reflected in snoop filter64because an entry was not previously allocated for that cache line. By contrast, in the prior art system ofFIG. 1, if the local cache line had been previously been accessed by the local node that would have been tracked in the snoop filter and main memory16could be accessed directly without checking the processor bus.

For example, assume cache line X is assigned to node0. If node1accesses cache line X and there is a miss in snoop filter64(i.e., there is no entry for cache line X in snoop filter64), then an entry is created for cache line X in snoop filter64and a cacheable access is issued to processor bus0and main memory16instead of merely a direct read to main memory16. In response to the cacheable access, processor bus0checks the caches of node0(e.g., caches18-0,18-1,18-2, and18-3) to determine which, if any, of them have or have modified cache line X. Further, memory controller hub14checks main memory16. The check to main memory16may be performed speculatively at the same time as the check to the caches of bus0or it may be performed after the check of the caches is unsuccessful. Processor bus0performs cache coherency according to the MESI protocol or some variant of it. At the completion of the request of cache line X by node1, an appropriate update to snoop filter64is made to reflect what has occurred. In some embodiments, if the request from node1is a write back of cache line X, the operation may be completed by writing into the home memory location in node0without a snoop to processor bus0, where the MESI protocol guarantees only one unique modified owner in the system at a time.

3. A third difference concerns the case in which a local node makes a read for ownership access (a type of write) to a local cache line. If there is a miss in snoop filter64, the read for ownership continues. If there is a hit in snoop filter64(because there is an entry for the cache line), a snoop invalidate request (such as a snoop invalidate own line (PSILO)) is issued to any remote owner(s).

A cache line may be de-allocated so that the entry for the cache line is removed from snoop filter64. Even though there has previously been an entry for the cache line in the snoop filter, for purposes of the operations described herein, when the cache line is again accessed it will be treated as if it were the first time it was accessed. If the cache line is next accessed by its local node, an entry will not be allocated and the access will not be tracked by snoop filter64. However, accesses by the local node will again be tracked after the cache line is again accessed by a remote node.

The invention can allow a snoop filter of a given size to effectively cover a larger cache than in the prior art example. As an example, in a system with two nodes where memory accesses are equally distributed (i.e., 50% local and 50% remote), this protocol change would approximately double the coverage of the snoop filter. As NUMA optimizations are made to the operating systems by having a node tend to use cache lines assigned to it so that the ratio of local to remote access increases a fixed snoop filter size increases its ability to effectively cover larger and larger caches.

When there is an eviction of one of the cache lines in the snoop filter, there are at least two approaches regarding back invalidating. Under a first approach, that cache line is back invalidated for all nodes. Under a second approach, that cache line is back invalidated for all nodes except the node that is the local node for that cache line.

The nodes include circuitry to maintain cache coherency within the node. That circuitry may be distributed amongst interfaces for the node's memory controller hub and processors.

FIG. 6illustrates that coherency controller switch60may represent more than one snoop filter and corresponding coherency controller switch. For example, inFIG. 6, coherency controller switch60includes a sub-snoop filter64A for even cache lines and a sub-snoop filter64B for odd cache lines with corresponding coherency controller switches60A and60B. Cache lines may be divided in some way other than even/odd in sub-snoop filters64A and64B. A sub-coherency controller switch60A may be on the same die or on a different die than sub-coherency controller switch60B. If sub-coherency controller switches60A and60B are on the same die, coherency controller switch60may have some additional circuitry shared by both switches60A and60B. There may be more than two sub-snoop filters.FIG. 9shows sub-snoop filters64A . . .64N, wherein N may be the number of nodes, twice the number of nodes or some other number. The sub-snoop filters do not have to be divided according to even and odd cache lines. The snoop filters may be in the memory controller hubs and/or in another place in a node such as a processor die and I/O hub die. Some functions of coherency controller switch60may be performed in a central location, while other functions of it are performed elsewhere such as near snoop filters in the nodes.

The snoop filter may be implemented in a variety of ways and the invention is not restricted to particular details for the snoop filter. The snoop filter will include a field or fields to indicate the cache line address, the state of the cache line, and where the node or nodes, if any, in which the cache line is cached. As an example, various features of snoop filter64are illustrated inFIGS. 7,8,9, and10, although the invention is not limited to these details. Referring toFIG. 10, snoop filter64includes multiple lists64-0,64-1,64-3. . .64-X of coherency information about cache lines. Merely as an example, snoop filter64might be 12-way set associative in which case there could be twelve coherency lists64-0,64-1, . . .64-11.

FIG. 10illustrates coherency list64-0of snoop filter64. In this particular embodiment, an address is divided into a tag (which is an upper part of the address) and an index (which is a lower part of the address). The index is “built-in” to the rows of coherency list64-0. There are many more rows than are shown inFIGS. 7 and 10. A cache line is stored in one of the coherency lists64-0. . .64-X that has a row with the same index as the cache line. The tag of the cache line is put in the “cache line address tag” field of the row. If all lists are occupied with that index, various algorithms such as least recently used (LRU) algorithms can be used in deciding in which list the cache line will be held. In some embodiments, particular coherency lists are dedicated to cache lines for a particular node or nodes, but it may be more efficient to allow any cache line to be in any coherency list.

The coherency lists of snoop filter64also include other fields under the heading “State and where cached” inFIG. 7. One example of the “State and where cached” fields are fields70shown inFIG. 8, which include an E/M (exclusive/modified) bit and a presence vector74. In the example ofFIG. 8, there are 6 bits in the presence vector74, one corresponding to each node in the system. InFIG. 3, only four nodes, but there may be six nodes (four processor nodes and two I/O hub nodes). If there are more or less nodes in the system, there would be a corresponding number of bits in the presence vector. InFIG. 8, the bits in presence vector74are labeled N0, N1. . . N5to represent nodes0,1, . . .5in the system ofFIG. 3. Nodes0-N are sometimes referred to as ports from the perspective of coherency controller switch60. Accordingly, the bits in the presence vector might be labeled ports0,1, . . .5to represent nodes0-5. InFIG. 3, only nodes0,1,2, and3are shown. Nodes4and5might be processor nodes like nodes0and1. Alternatively, the I/O hubs could be nodes4and5and nodes2and3could be reassigned to processor nodes.

A first logical value for the E/M bit indicates the cache line is the non-exclusive/ non-modified state and a second logical value in the E/M bit indicates the cache line is in the exclusive/modified state. In the following examples, the first logical value for the E/M bit is 0 (low) and the second logical value is 1 (high), although the opposite could be used. A first logical value for a bit of presence vector74indicates the corresponding node has not cached the cache line of interest. Accordingly, if all six bits of presence vector74have the first logical value, it A second logical value indicates the corresponding node has cached the cache line. In the following examples, the first value is 0 (low) and the second value is 1 (high), although the opposite could have been used.

A first logical value in the node bits of presence vector74indicates the corresponding node has not cached the cache line of interest. A second logical value indicates the corresponding node has cached the cache line. In the following examples, the first value is 0 (low) and the second value is 1 (high), although the opposite could have been used.

The following are some examples as to operation of snoop filter64according to some embodiments of the invention. However, the invention is not limited to these details. The following examples assume bits N0, N1, N2, and N3in presence vector74represent nodes0,1,2, and3inFIG. 3, respectively, and there are two additional nodes N4and N5that are not illustrated inFIG. 3.

In a first example, there is a data read transaction requested by node0of a cache line X which is not cached in any of the node's caches. Cache line X is in the range assigned to node1, so that node1is the local node. Node0issues a read request to coherency controller switch60. Snoop filter64performs a lookup operation to determine if cache line X has been cached at any of the nodes0-5. In some embodiments, while the snoop filter64is performing the lookup operation, coherency controller switch60issues a speculative memory read to node1. Coherency controller switch60may include memory decode circuitry to allow it to determine which node is being addressed by the read request. In this example, snoop filter64indicates that cache line X is not cached in any of the system's caches. Accordingly, a 0 is included in N0-N5in presence vector74or an entry for cache line X is not in snoop filter64. Coherency controller switch60delivers a snoop response to node0and may also send a memory read confirmation to node1. In response to the memory read confirmation, node1delivers the requested data to coherency controller switch60. Coherency controller switch60then delivers the requested data to node1. Because node1is the only node that has cached the subject cache line, snoop filter64marks the E/M bit accordingly and the NO bit to 1 to indicate that node0has a copy of the cache line.

In a second example, a memory read for ownership (processor write) transaction involves a cache line Y shared between nodes0and1. In this example, cache line Y is in the range of node0so node0is the local node. Node0is also the requesting node. In other words, node0is writing a cache line to its own memory16. Node0begins by issuing an invalidate cycle to coherency controller switch60. Snoop filter64then performs a lookup operation to determine which nodes have copies of cache line Y and also to determine in which state cache line Y is cached. The lookup operation in this example indicates that cache line Y is “shared” and that nodes1and2have copies. Accordingly, the N1and N2bits have a 1 while the N0and N3-N5bits have a 0. Switch60then issues invalidate cycles to nodes1and2. Nodes1and2respond with snoop response signals and coherency controller switch60delivers a snoop response to node0to complete the transaction. Snoop filter64now shows that node0has the only copy of the cache line and that the line is in the “exclusive/modified” state. Accordingly, the E/M bit has a 1 and the N0bit has a 1 while the N1-N5bits have a 0. In some embodiments, the snoop filter entry can be de-allocated at the end of the read for ownership transaction where the local node is the sole owner of the cache line.

A third example involves a read cycle to a “modified” cache line Z which is in the memory range of node1, so node1is the local node. Node0is the requesting node and node2is the node that has modified its copy of cache line Z. Node0begins the transaction by issuing a read request to coherency controller switch60. Snoop filter64performs a lookup operation while the coherency controller switch60issues a speculative memory read to node1. The result of the snoop filter lookup indicates that node2has a modified copy of cache line Z. Coherency controller switch60sends a snoop request to node2and node2responds with a snoop response along with the modified data. Coherency controller switch60delivers the snoop response and the data to node0and at the same time delivers the data to node1so that the system memory can be updated. Node1then signals a completion to coherency controller switch60and the completion is forwarded from switch60to node0to complete the transaction.

Presence vector70and74has been described the E/M bits and presence vector bits N0-N5as being single bit with 0 or 1 logical values. Alternatively, the state information could be encoded in cells that allowed more than two logical values (e.g., voltages).

In some embodiments, the above-described new techniques for dealing with accesses of local cache lines by local and remote nodes apply to all cache lines and all nodes. In other embodiments, the new techniques might apply to only some of the cache lines and/or only some of the nodes, wherein for others of the cache lines and/or others of the nodes, other techniques such as allocating entries for all initial accesses may apply. In some embodiments, some of the new techniques apply while others of them do not. As an example of alternative embodiments, for some or all nodes, an entry would be allocated for initial accesses of some local caches lines by the local node, but for other cache lines, one or more of the new techniques would apply. As another example, accesses by some nodes would be treated in the new way, but accesses by others of the nodes would be treated in the prior art way. Various combinations of new and old techniques may be used.

When comparingFIG. 3andFIG. 1, only the coherency controller switch and snoop filter have different reference numbers. That illustrates that the other components in the figures can be constructed and operated the same in the prior art system and in the system ofFIG. 3. However, other components (e.g., memory controller hubs14and24) could be different inFIGS. 1 and 3.

The interconnects between components shown in drawings or described herein (e.g., between switch60and the nodes) may be made through electrical, optical, or wireless techniques, or through some other technique of communication.

The invention is not restricted to the particular details listed herein. Indeed, those skilled in the art having the benefit of this disclosure will appreciate that many other variations from the foregoing description and drawings may be made within the scope of the present invention. Accordingly, it is the following claims including any amendments thereto that define the scope of the invention.