Electrical computers and digital processing systems: memory – Storage accessing and control – Hierarchical memories
Reexamination Certificate
1999-04-19
2001-09-04
Yoo, Do Hyun (Department: 2185)
Electrical computers and digital processing systems: memory
Storage accessing and control
Hierarchical memories
C711S144000, C711S152000, C710S039000
Reexamination Certificate
active
06286082
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to a cache controller for a non-blocking, set associative cache. In particular, the present invention relates to a hazard control circuit for a cache controller that avoids overwriting modified cache data prior to write back.
BACKGROUND OF THE INVENTION
FIG. 1
illustrates, in block diagram form, a typical prior art multi-processor system
30
. System
30
includes a number of processors,
32
a
,
32
b
,
32
c
, coupled via a shared bus
35
to memory
36
. Processors
32
execute program instructions out-of-order (OOO). Each processor
32
has its own non-blocking cache
34
.
Each cache
34
is N-way set associative. In other words, each cache index defines a set of N cache entries, also referred to as N ways. Each cache index way includes data and a tag to identify the memory address with which the data is associated. Additionally, MOSI bits are associated with each item of data in a cache to maintain cache coherency by indicating the MOSI state of the data entry. According to the MOSI protocol, each cache data entry can be in one of four states: M, O, S, or I. The I state indicates invalid data. The owned state, O, indicates that the data associated with a cache index is valid, has been modified from the version in memory, is owned by a particular cache and that another cache may have a shared copy of the data. The processor with a requested line in the O state responds with data upon request from other processors. The shared state, S, indicates that the data associated with a cache index is valid, and one or more other processors share a copy of the data. The modified state, M, indicates valid data that has been modified since it was read into cache and that no other processor has a copy of the data.
MOSI states help determine whether a cache access request is a miss or a hit. A cache hit occurs when one of the ways of a cache index includes a tag matching that of the requested address and the MOSI state for that way is not I. A cache miss occurs when none of the tags of an index set matches that of the requested address or when the way with a matching tag contains invalid data. Within system
30
, at the time a miss is detected a determination is made whether a write-back is required. This determination is based upon MOSI state. A write back is necessary when a request misses in the cache and the index way assigned for the cache fill contains modified data; i.e., is in the M or O state.
FIG. 2
illustrates how MOSI states transition in response to various types of misses. In system
30
, at the time the need for a write back is recognized, the line is invalidated by changing the way's MOSI bits to the I state. The MOSI state of the way will again be changed from I to another state upon completion of the fill that precipitated the write back.
This policy of changing MOSI bits to I at the time of write back determination can lead to data loss when more than N outstanding store misses are permitted in a non-blocking, N-way set associative cache, as is the case in system
30
. Table I of
FIG. 3
illustrates how these two factors can lead to data loss by overwriting modified data without first writing it back. Table I illustrates how the MOSI bits and data of one index change in response to a series of store misses for that index. At time &tgr;
0
, all four ways of index A store modified data. At time &tgr;
1
when the first store, St
1
A, misses Way
0
is assigned for the required fill. The MOSI state of Way
0
indicates a write back is necessary. In anticipation of the yet-to-be-completed write back, the MOSI state of Way
0
is changed from M to I. Similar events occur at &tgr;
2
for way
1
, &tgr;
3
for Way
2
, and at &tgr;
4
for Way
3
. When the N+1th store misses occurs at &tgr;
5
way
0
is again assigned for the necessary fill. Because the fill associated with St
1
A has not yet completed, the MOSI state of Way
0
is still I, indicating that a write back of the data in Way
0
is not necessary. Subsequently, at &tgr;
6
the fill associated with St
1
A is completed, writing data item D
1
into Way
0
and changing its MOSI state to M. At &tgr;
7
the fill associated with St
5
A is completed writing data item D
5
over D
1
. Data item D
1
has been overwritten without the write back, even though its MOSI state is M. This data loss occurred because the determination of whether a write back was made while a previous fill for the same way was still pending.
One possible solution to avoiding overwriting modified data without a write back is to stall selection of store requests when there are N outstanding store misses. This eliminates the possibility that two fills can be pending at the same time for a single way. To illustrate the effect of this stall policy, consider the situation immediately after start-up when the tag bits for each cache entry represent the I state. In this situation the first N store requests will result in N outstanding cache misses. System
30
will respond to the Nth cache access request by stalling, without regard to the cache index associated with each cache access request. If all N store requests are to the same index then the stall was necessary to prevent data loss. However, if just one of the N pending cache accesses is for a different cache index then the stall is unnecessary because there was no danger of data loss. As used herein, a stall is unnecessary in a non-blocking, N-way set associative cache when there are fewer than N outstanding misses for any one cache index. While the performance penalty per unnecessary stall is small, it is incurred so frequently that the overall cost of unnecessary stalls is undesirable.
Thus, a need exists for a cache controller for a non-blocking, N-way set associative cache using a write-invalidate cache-coherency protocol that avoids overwriting cache data in the M or O states without first performing a write back.
A need also exists for a cache controller that reduces unnecessary cache stalls while preventing data loss possible when write back decisions are made at the time of miss detection.
A need exists for a cache controller that accounts for the cache indices associated with outstanding cache misses when determining whether to stall selection of cache access requests so that only necessary stalls are initiated.
A further need exists for a cache controller that reduces the duration of necessary stalls.
SUMMARY OF THE INVENTION
The hazard control circuit of the present invention prevents overwriting of modified cache data without write back in a non-blocking, N-way set associative cache that uses a write-invalidate cache-coherency protocol. The hazard control circuit does so by deferring assignment of a way for a miss until after completion of a pending fill for that way. The hazard control circuit of the prevent invention also avoids unnecessarily stalling selection of cache access requests and minimizes the length of necessary stalls.
The hazard control circuit of the present invention includes a transit hazard buffer, a stall assertion circuit and a way assignment circuit. The transit hazard buffer tracks pending cache access requests via a number of index entries. Each index entry includes an index identifier, an index counter and a set of index lock bits. The index identifier identifies a cache index for which there is at least one pending cache access. The index counter indicates the number of pending cache accesses to the identified index. The value of the index counter is modified as store requests are selected and as they are completed. The index lock bits indicate for a cache index which of its ways are available for a fill. A way is locked upon its assignment for a fill and is unlocked upon fill completion. The stall assertion circuit uses the index counters to determine when to initiate and terminate selection of store requests. The stall assertion circuit initiates a stall only when there are N outstanding cache access requests for a single cache index. The stall assertion circuit ends the stall as soon as safely possible
Kuttanna Belliappa M.
Moudgal Anuradha N.
Encarnacion Yamir
Pennie & Edmonds LLP
Sun Mocrosystems, Inc.
Yoo Do Hyun
LandOfFree
Apparatus and method to prevent overwriting of modified... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Apparatus and method to prevent overwriting of modified..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus and method to prevent overwriting of modified... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2549281