Electrical computers and digital processing systems: memory – Storage accessing and control – Hierarchical memories
Reexamination Certificate
2000-09-21
2004-01-13
McLean-Mayo, Kimberly (Department: 2187)
Electrical computers and digital processing systems: memory
Storage accessing and control
Hierarchical memories
C711S141000
Reexamination Certificate
active
06678800
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
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 increasing access performance by controlling various statuses or states of cache data.
2. Description of the Related Arts
In association with a recent demand for a high processing speed of a computer system, in a multiprocessor system, each CPU (processor) has a cache apparatus. Data in a cache provided for each CPU is managed on the cache memory every block in accordance with a rule called a cache coherence protocol to maintain matching of the data among the caches in order to maintain correctness of the data, namely, sharing and consistency of data among the caches.
As a conventional general cache protocol, an MESI cache protocol for managing four statuses or states of MESI has been known.
FIGS. 1A and 1B
are status transition diagrams of the conventional MESI cache protocol.
FIG. 1A
is a fetching protocol in case of a fetching request (reading request).
FIG. 1B
is a storing protocol in case of a storing request (writing request). Symbols of the status transition denote the following contents.
M: Modified. Valid data is held only in one of a plurality of caches. Data has been modified. It is not guaranteed that a value of the data is the same as that in a main storage.
E: Exclusive. Valid data is held only in one of a plurality of caches.
S: Shared. The same data is held in a plurality of caches.
I: Invalid. Data in the cache is invalid.
In the cache control using the conventional MESI cache protocol as mentioned above, if a certain CPU issues a fetching request by which a CPU of the other system refers to a data block stored in a cache apparatus, it is necessary to write the data block into the main storage MS. It requires an amount of access time corresponding to the time for such a writing operation.
FIGS. 2A
to
2
E show a multiprocessor system comprising CPUs
100
-
1
to
100
-
3
and cache apparatuses
102
-
1
to
102
-
3
and relate to a case where the CPU
100
-
2
issues a fetching request and a storing request to the same data block.
FIGS. 2A and 2B
first show a fetching process of the CPU
100
-
2
. First in
FIG. 2A
, the CPU
100
-
2
issues the fetching request to the cache apparatus
102
-
2
of the self system. However, since the status of the data block denotes Invalid I, the CPU
100
-
2
issues the fetching request through a bus to the cache apparatus
102
-
1
in which the data block has been held in the status of Modified M. In
FIG. 2B
, the data block is obtained and, in response to the CPU
100
-
2
, the status of the data block in the cache apparatus
102
-
2
is changed from Invalid I to Shared S. The status of the data block in the cache apparatus
102
-
1
on the data fetching destination side is switched from Modified M to Shared S. Further, the data block which received the fetching request is written into the main storage MS.
FIGS. 2C
to
2
E show a case where the CPU
100
-
2
subsequently issues the storing request to the same data block. As shown in
FIG. 2C
, when the CPU
100
-
2
issues the storing request to the self system cache apparatus, a block changing request is issued to the cache apparatus
102
-
1
of the other system holding the same data block in the status of Shared S. As shown in
FIG. 2D
, the status of the data block is switched from Shared S to Invalid I. The CPU
100
-
2
performs a storing process to store new data into a data block in the cache apparatus. When the storing process is finished, as shown in
FIG. 2E
, the completion of the storage is notified from the cache apparatus
102
-
2
to the CPU
100
-
2
. The process is finished.
FIGS. 3A
to
3
D show a case where the CPUs
100
-
2
and
100
-
3
successively issue the fetching request to the same data block. First, the fetching process of the CPU
100
-
2
in
FIGS. 3A and 3B
is the same as that in
FIGS. 2A and 2B
. It is necessary to write the data block into the main storage MS in response to the fetching request to the cache apparatus
102
-
1
.
FIGS. 3C and 3D
show the fetching process of the CPU
100
-
3
. The data block is obtained by the fetching request to the cache apparatus
102
-
2
of the other system. In
FIG. 3D
, the completion of the fetch is notified to the CPU
100
-
3
.
In such a conventional MESI cache protocol, however, as shown in
FIGS. 2B and 3B
, when the data block is obtained by issuing the fetching request to the cache apparatus of the other system, the writing operation into the main storage MS is performed in the cache apparatus
102
-
1
of the other system. As shown in
FIG. 2C
, when the CPU
100
-
2
allows the data block held in the status of Shared S to be stored in the cache apparatuses
102
-
1
and
102
-
2
of the self and other systems, it is necessary to switch the status of the data block from Shared S to Invalid I by issuing the block changing request (status changing request) to the cache apparatus
100
-
1
of the other system.
FIG. 4A
is another status or state transition diagram of the fetching protocol in the conventional MESI cache protocol. Also in this case, when the data block in the status of Modified M is switched to Invalid I in response to the fetching request from the other system, the writing operation into the main storage MS is performed.
FIG. 4B
shows another status or state transition diagram of the fetching protocol in the conventional SEMI cache protocol. In this case, when the data block in the status of Modified M is switched to Invalid I in response to the fetching request from the other system, it is not switched to Shared S even if the fetching request is issued after that, thereby making the writing operation into the main storage MS unnecessary even if the data block is switched from Modified M to Invalid I in response to the fetching request of the other system.
To make the writing operation into the main storage MS which is performed at the time of the fetching process of the MESI cache protocol in
FIG. 2A
or
3
A unnecessary, in JP-A-6-124240 (Japanese Patent Application No. 4-275825), as shown in
FIGS. 5A and 5B
, the protocol is constructed so as to show five statuses obtained by adding Shared Modified O to the MESI cache protocol, thereby making the writing operation into the main storage MS at the time of the fetching process unnecessary. Reference symbol O of Shared Modified denotes Owner.
FIGS. 6A
to
6
E show the multiprocessor system comprising the CPUs
100
-
1
to
100
-
3
and cache apparatuses
102
-
1
to
102
-
3
and relate to the case where the CPU
100
-
2
issues the fetching request and the storing request to the same data block. First,
FIGS. 6A and 6B
show the fetching process of the CPU
100
-
2
.
In
FIG. 6A
, the CPU
100
-
2
issues the fetching request to the self system cache apparatus
102
-
2
. Since the data block is in the status of Invalid I, the fetching request is issued via the bus to the cache apparatus
102
-
1
holding the data block in the status of Modified M. In
FIG. 6B
, the data block is obtained, a response is made to the CPU
100
-
2
, and the status of the data block of the cache apparatus
102
-
2
is changed from Invalid I to Shared S. In this instance, the status of the data block of the cache apparatus
102
-
1
on the data fetching destination side is switched from Modified M to Shared Modified O. In this case, since it is not switched to Shared S, the writing operation into the main storage MS of the data block which received the fetching request is unnecessary.
FIGS. 6C
to
6
E show the case where the CPU
100
-
2
issues the storing request to the same data block. As shown in
FIG. 6C
, when the CPU
100
-
2
issues the storing request to the self system cache apparatus
102
-
2
, the block changing request (status changing request) is issued to the other system cache apparatus
100
-
1
holding the same data block in the status of Shared Modified O. As shown
Kurihara Akihiro
Mori Tsuyoshi
Fujitsu Limited
McLean-Mayo Kimberly
Staas & Halsey , LLP
LandOfFree
Cache apparatus and control method having writable 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 Cache apparatus and control method having writable modified..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Cache apparatus and control method having writable modified... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3237781