Electrical computers and digital processing systems: memory – Storage accessing and control – Hierarchical memories
Reexamination Certificate
2000-09-21
2003-02-25
Yoo, Do Hyun (Department: 2187)
Electrical computers and digital processing systems: memory
Storage accessing and control
Hierarchical memories
C711S141000
Reexamination Certificate
active
06526480
ABSTRACT:
TECHNICAL FIELD
The present invention relates to a cache apparatus and a control method for managing a cache memory by a multiprocessor system and, more particularly, to a cache apparatus and a control method for enabling a cache memory to hold data whose validity is uncertain and allowing a processor to speculatively process the data.
BACKGROUND ART
Generally, an access time to a main storage of a computer system is extremely slower as compared with an operating speed of a processor. When an access to the main storage occurs, therefore, the processor waits for data which is transmitted from the main storage. A cache apparatus is a memory which operates at a high speed although a capacity is smaller than that of the main storage, is arranged between the processor and the main storage, and reduces an apparent access time to the main storage, thereby reducing a data waiting time of the processor.
FIG. 1
shows a table structure of a cache memory provided for a cache apparatus. A cache line
122
serving as a unit of storage comprises a tag
124
and data
130
. The tag
124
includes a status tag
126
and an address tag
128
. When a reading request is received from a processor, the cache memory searches the cache line having the address tag
128
whose address value coincides with that of a request address. When the cache line having the coincident address value does not exist, it results in a cache miss. Even if there is a cache line having the coincident address value, it results in a cache miss so long as the data held in the cache line is invalid on the basis of the status tag
126
. In case of the cache miss, it is necessary to access the main storage or another cache memory. When the cache line in which the address value of the address tag
128
coincides exists and the data held in the cache line is valid on the basis of the status tag
126
, it results in a cache hit. In case of the cache hit, since it is unnecessary to access to the main storage or another cache, a data waiting time of the processor is short. As mentioned above, in the cache memory apparatus, when the cache line whose address value coincides with that of the request address exists, whether it is necessary to access to the main storage or another cache memory or not and whether the data waiting time of the processor is short or not are determined in accordance with whether the data held in the cache line is valid or invalid.
On the other hand, in a multiprocessor system, in many cases, each processor has a cache apparatus. As for the data in the cache memory provided for each processor, it is necessary to keep correctness of the data, namely, consistency of the data among the cache memories. To keep the consistency of data, each cache memory is managed in accordance with a rule called a cache coherence protocol to keep matching performance of the data among the cache memories. Consequently, it is possible access the data in the cache memory. A state where the consistency of the data is maintained among the cache memories in the multiprocessor system will now be explained with respect to a cache apparatus using an MESI protocol known as an invalidation type cache coherence protocol as an example.
FIG. 2A
shows a status transition for a reading request of the MESI protocol.
FIG. 2B
shows a status transition for a writing request of the MESI protocol. Symbols of the status transition denote the following contents.
M: Modified. Valid data has been held only in one of a plurality of caches and the data has been modified. It is not guaranteed that a value of the data is the same as that in the main storage.
E: Exclusive. Valid data has been held only in one of a plurality of caches.
S: Shared. The same data has been held in a plurality of caches.
I: Invalid. The data in the cache is invalid.
self: Case where a request from a self processor has been processed.
other: Case where a request from another cache apparatus has been processed.
self-if copy: Case where the cache is in the invalid status for a reading request and the other caches hold the data.
self-if no copy: Case where the cache is in the invalid status for a reading request and no cache holds the data.
In this case, since the state where no data exists in the cache is equivalent to a case where data has been held in the cache in a status of Invalid I in a practical sense, for convenience, the Invalid I status denotes both the following cases.
I. Case where the data has been held in the Invalid I status into the cache.
II. Case where no data exists in the cache
Similarly, such an expression that no data exists in the cache denotes both the following cases.
I. Case where no data really exists in the cache.
II. Case where the data has been held in the Invalid I status into the cache.
FIG. 3A
shows cache apparatuses of the multiprocessor system. Cache apparatuses
100
-
1
and
100
-
2
are provided for processors
102
-
1
and
102
-
2
, respectively, and they are connected to a main storage
106
in common through a bus
104
. As shown in
FIG. 3A
, it is assumed that data has been held in the Shared S status into a certain cache line in the cache memories of the cache apparatuses
100
-
1
and
100
-
2
. As shown in
FIG. 3B
, when a writing request for the data of the cache apparatus
100
-
1
is issued from the processor
102
-
1
, the data in the cache apparatus
100
-
1
is modified and the Shared S status is changed to the Modified M status. However, the consistency of the data between the cache apparatuses
100
-
1
and
100
-
2
cannot be maintained if the data in the cache apparatus
100
-
1
is merely modified. Therefore, after the invalidating operation to modify the Shared S status of the cache apparatus
100
-
2
to the Invalid I status is performed, the operation to modify the data in the cache memory
100
-
1
is needed. After that, as shown in
FIG. 3C
, when the processor
102
-
2
issues a reading request for the modified data, since the data in the cache apparatus
100
-
2
has been invalidated to the Invalid I status by the writing request from the processor
102
-
1
in
FIG. 3B
, the reading request from the processor
102
-
2
issued after that causes a cache miss.
Ordinarily, a block size of the cache line is larger than a size of data that is handled by the processor. It is now assumed that the cache block size is equal to the size of two words and the size of the data which is processed by the processor is equal to the size of one word, namely, the half size. As shown in
FIG. 4A
, it is assumed that the cache apparatuses
100
-
1
and
100
-
2
hold the same data existing in cache lines
122
-
1
and
122
-
2
, for example, data having a 2-word length in which the data in the head 1-word portion is set to “12” and the data in the latter 1-word portion is set to “34”. In such a state, as shown in
FIG. 4B
, it is assumed that the processor
102
-
1
generates the writing request for the data in the head 1-word portion of the cache line
122
-
1
and the value is rewritten from “12” to “56”. At this time, since the status of the cache memory of each of the cache apparatuses
100
-
1
and
100
-
2
is managed on the unit basis of each of the cache lines
122
-
1
and
122
-
2
, all of the data in the cache line
122
-
2
of the cache apparatus
100
-
2
is invalidated by the status transition to Invalid I. Subsequently, as shown in
FIG. 4C
, it is assumed that the reading request of the cache line
122
-
2
in the cache apparatus
100
-
2
from the processor
102
-
1
is a reading request for the data in the latter 1-word portion. In this case, in spite of the fact that the values of the data held in the latter 1-word portions of the cache lines
122
-
1
and
122
-
2
of the cache apparatuses
100
-
1
and
100
-
2
are the same as “34”, since the status of the cache line
122
-
2
is Invalid I, it results in a cache miss. The access operation to the main storage or another cache occurs and the processor
102
-
2
enters a data waiting state. It is the cache miss due to a so-called false sharing. The invalidating operat
Kumon Kouichi
Naruse Akira
Sato Mitsuru
McLean-Mayo Kimberly N.
Staas & Halsely LLP
Yoo Do Hyun
LandOfFree
Cache apparatus and control method allowing speculative... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Cache apparatus and control method allowing speculative..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Cache apparatus and control method allowing speculative... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3148850