Electrical computers and digital processing systems: memory – Storage accessing and control – Hierarchical memories
Reexamination Certificate
2003-04-14
2004-03-09
Kim, Matthew (Department: 2186)
Electrical computers and digital processing systems: memory
Storage accessing and control
Hierarchical memories
C711S147000
Reexamination Certificate
active
06704845
ABSTRACT:
FIELD OF THE INVENTION
The present invention pertains to snoop filters used in multi-processor systems. More particularly, the present invention relates to a technique for replacing cache line entries in a snoop filter so as to reduce back invalidates in a multi-node architecture.
BACKGROUND OF THE INVENTION
A snoop filter is a device used to reduce bus traffic in certain computer systems, particularly multiple-processor (“multi-processor”) systems. In a multi-processor system, the snoop filter generally forms part of an interface between two or more “nodes”. Each node contains one or more processors, a node controller, and memory, including one or more levels of cache memory associated with each processor. The snoop filter is essentially a specialized cache for tracking cache coherency state information relating to the cache memories of the processors. The snoop filter keeps track of the coherency state of each cache line of each of the processors. The state information is used by the snoop filter to decide which bus transactions received from the various nodes need to be passed on to other nodes in the system. The snoop filter filters unnecessary bus transactions by preventing them from reaching those nodes for which they are not needed. Hence, a snoop filter can have a dramatic positive impact on the overall system performance by reducing bus traffic.
FIG. 1
shows an example of a four-node, eight-processor system
1
. The four nodes
2
(“node#0”, “node#1”, “node#2”, and “node#3”) are coupled to each other through a multi-node interface
10
, which includes a snoop filter
5
and a switch
9
. The switch
9
controls the routing of communications traffic between nodes
2
. Each node
2
includes two processors
3
coupled on a local bus
8
. The two processors
3
of each node
2
are also coupled to a Random Access Memory (RAM)
4
of that node through a node controller
6
. The node controller
6
of each node
2
is coupled to the snoop filter
5
. In addition, associated with each processor
3
is a cache memory (or “cache”)
7
. The caches
7
may be located within their respective processors
3
, or they may be separate from but coupled to their respective processors
3
(e.g., off-chip or outside the processor but on the same chip).
Now consider a simple example of how the snoop filter
5
conserves bus bandwidth for the four-node system. Assume that a particular cache line, address A, is present only in one node of the system, node#0. If a processor
3
in node#3 wants to write to this cache line, the request first comes to the snoop filter
5
, and the snoop filter
5
will send an invalidation request only to node#0, since that cache line is only resident in node#0. The request is “filtered”, i.e., not forwarded to the two remaining nodes, node#1 or node#2, eliminating unnecessary transactions on the local buses
8
of node#1 and node#2.
Because the cache lines of each processor
3
have an entry in the snoop filter
5
, the snoop filter
5
will send a “back invalidate” when it is forced to replace a snoop filter entry that corresponds to a valid entry in some processor's cache
7
. A back invalidate is simply a signal to one or more nodes
2
to invalidate, in their caches
7
, the line that has been replaced in the snoop filter. Continuing the example above, if the entry corresponding to cache line address A is replaced, a back invalidate signal is sent to node#
3
before the snoop filter entry is allocated to a new cache line. When a node
2
receives a back invalidate signal, the node
2
marks that cache line as invalid. If another access is made to the cache line that was invalidated, a miss will occur and the accessing processor
3
will be forced to send a bus request to re-read the line.
In this way, back invalidates from a snoop filter increase bus traffic and can cause cache misses. Known snoop filter replacement methods do not address this problem adequately. A conventional method for choosing a replacement line in a snoop filter is to use a temporal-based replacement algorithm such as Least Recently Used (LRU). In LRU, the oldest entry is chosen for replacement based on the premise that if the line has not been accessed recently, it is unlikely to be accessed in the near future. Other temporal-based algorithms, such as Pseudo-LRU (PRLU) or First In First Out (FIFO), work in a similar manner but are less expensive to implement. However, known temporal-based algorithms suffer from the same limitation, i.e., the lack of temporal information available to the snoop filter. This lack of temporal information stems from the fact that the snoop filter is only updated on cache misses. The snoop filter is unaware of cache hits and thus receives only a fraction of the temporal information available in the cache. Perhaps more importantly, the temporal correlation between the access streams from different processors in a multi-node architecture is weak at best.
REFERENCES:
patent: 5713004 (1998-01-01), Kimmel et al.
patent: 5715427 (1998-02-01), Barrera et al.
patent: 5809528 (1998-09-01), Miller et al.
patent: 5819105 (1998-10-01), Moriarty et al.
patent: 5822765 (1998-10-01), Boatright et al.
patent: 5913226 (1999-06-01), Sato
patent: 5966729 (1999-10-01), Phelps
patent: 6023747 (2000-02-01), Dodson
patent: 6275909 (2001-08-01), Arimilli et al.
patent: 6304945 (2001-10-01), Koenen
patent: 6370622 (2002-04-01), Chiou et al.
patent: 6389517 (2002-05-01), Moudgal et al.
patent: 6598123 (2003-07-01), Anderson et al.
Anderson James R.
Jayasimha Doddaballapur N.
Kim Matthew
Li Zhuo H.
LandOfFree
Snoop filter line replacement for reduction of back... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Snoop filter line replacement for reduction of back..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Snoop filter line replacement for reduction of back... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3229574