Electrical computers and digital processing systems: memory – Storage accessing and control – Hierarchical memories
Reexamination Certificate
1999-02-01
2002-06-18
Kim, Matthew (Department: 2186)
Electrical computers and digital processing systems: memory
Storage accessing and control
Hierarchical memories
C711S120000
Reexamination Certificate
active
06408365
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a loosely coupled multiprocessor system, and more particularly to the maintenance of coherency between the data stored in main and cache memories in such a multiprocessor system.
2. Description of the Related Art
One technology for maintaining coherency between the data stored in main and cache memories in a conventional loosely coupled multiprocessor system is disclosed in “The Directory-Based Cache Coherence Protocol for the DASH Multiprocessor” by Daniel Lenoski, James Laudon, Kourosh Gharachorloo, Anoop Gupta and John Hennessy, In Proceedings of 17th International Symposium on Computer Architecture, pages 148-159, 1990.
FIG. 1
of the accompanying drawings shows in block form an arrangement of such a conventional loosely coupled multiprocessor system.
As shown in
FIG. 1
, the conventional loosely coupled multiprocessor system comprises a plurality of nodes Pe
0
-Pe
n−1
and two interconnection networks
10
1
,
10
2
that interconnect the nodes.
Each of the nodes, denoted by Pe
i
in
FIG. 1
, comprises a processor
50
for performing processing and memory access, a main memory
51
, a cache memory
52
that can be accessed at a higher speed than the main memory
51
, and a coherency maintenance controller
53
for maintaining coherency between the data stored in the main memory
51
and the cache memory
52
(and those of the other nodes). The processor
50
temporarily stores data in the main memory
51
.
The coherency maintenance controller
53
holds the state of data stored in the main memory
51
and information of nodes which hold a copy of data in the cache memory
52
(hereinafter referred to as “holding node information”). There are two states of data, i.e., states C and M. The state C is a state in which a copy of data is present in the cache memories
52
of a plurality of nodes. In this case, the value of the copy of data present in the cache memory
52
and the value of data stored in the main memory
51
are the same with each other. The state M is a state in which only the cache memory
52
of one node holds a copy of data. In this case, the value of the copy of data present in the cache memory
52
and the value of data stored in the main memory
51
are different from each other, and the value of the copy of data present in the cache memory
52
is the latest value.
The coherency maintenance controller
53
also holds the state of data stored in the cache memory
52
and a tag address of the data. There are three states of data, i.e., states I, S, and D. The state I is a state in which there is no effective copy of data with maintained coherency. The state S is a state in which there is a possibility that there is an effective copy of data and there is also an effective copy of data in the cache memory
52
of another node. The state D is a state in which there is an effective copy of data, there is no effective copy of data in the cache memory
52
of another node, and the value of the data is different from the value of the data stored in the main memory
51
. The tag address indicates at which address the data stored in the cache memory
52
is located.
The interconnection network
10
1
distributes request messages exchanged between the nodes, and the interconnection network
10
2
distributes reply messages exchanged between the nodes. The interconnection network for distributing request messages and the interconnection network for distributing reply messages, which are separate from each other, are effective to avoid deadlock in maintaining coherency between the data stored in the main memory
51
and cache memory
52
.
A process for maintaining coherency between the data stored in the main memory
51
and cache memory
52
in the multiprocessor system when the processor
50
performs a load or store access to data at a given address will be described below.
First, it is assumed that the processor
50
at the node Pe
1
performs a load access.
The coherency maintenance controller
53
checks if an effective copy of the data at the corresponding address is present in the cache memory
52
or not. If an effective copy of the data is present in the cache memory
52
, i.e., if the data is in the state S or D, then the coherency maintenance controller
53
replies to the processor
50
by transferring the data read from the cache memory
52
to the processor
50
, after which the process comes to an end.
If an effective copy of the data is not present in the cache memory
52
, i.e., if the data is in the state I, then the coherency maintenance controller
53
at the node Pe
1
transmits a request message to read the data to a node which holds the data at the corresponding address, e.g., the node Pe
h
, through the interconnection network
10
1
.
In response to the reading request message, the coherency maintenance controller
53
at the node Pe
h
checks if the latest value of the data at the corresponding address is present in the main memory
51
at the node Pe
h
. If the latest value of the data at the corresponding address is present in the main memory
51
, i.e., if the data is in the state C, then the coherency maintenance controller
53
at the node Pe
h
transmits the data stored in the main memory
51
to the node Pe
1
through the interconnection network
10
2
, and adds the node Pe
1
to the holding node information.
Upon reception of the data from the node Pe
h
, the coherency maintenance controller
53
at the node Pe
1
transfers the received data to the processor
50
, and copies the data to the cache memory
52
. The coherency maintenance controller
53
at the node Pe
1
sets the state of the data to the state S.
At the node Pe
h
which has received the reading request message, if the latest value of the data at the corresponding address is not present in the main memory
51
, i.e., if the data is in the state M, then the coherency maintenance controller
53
at the node Pe
h
refers to the holding node information, and transmits the reading request message to a node which holds the latest data, e.g., the node Pe
r
, through the interconnection network
10
1
.
At the node Pe
r
which has received the reading request message, the coherency maintenance controller
53
checks if the data in the state D is present in the cache memory
52
or not. If the data in the state D is present in the cache memory
52
, then the coherency maintenance controller
53
at the node Pe
r
transmits the data stored in the cache memory
52
to the node Pe
1
through the interconnection network
10
2
, and also transmits a writing request message with the data stored in the cache memory
52
being added thereto to the node Pe
h
through the interconnection network
10
1
. The coherency maintenance controller
53
at the node Pe
r
updates the state of the data present in the cache memory
52
to the state S.
In response to the writing request message, the coherency maintenance controller
53
at the node Pe
h
updates the data in the main memory
51
to the data added to the writing request message. The coherency maintenance controller
53
also updates the state of the data to the state C and adds the node Pe
1
to the holding node information.
At the node Pe
r
which has received the reading request message, if the data in the state D is not present in the cache memory
52
, then the coherency maintenance controller
53
at the node Pe
r
transmits a Nak (negative acknowledge) message to the node Pe
1
through interconnection network
10
2
.
In response to the Nak message, the coherency maintenance controller
53
at the node Pe
1
transmits the reading request message again to the node Pe
h
. Subsequently, the same process is repeated until data is transmitted to the node Pe
1
and transferred to the processor
50
at the node Pe
1
.
Now, it is assumed that the processor
50
at the node Pe
1
performs a store access.
The coherency maintenance controller
53
checks if a copy of the data at the corresponding address, which is only one copy in the system, is presen
Anderson Matthew D.
Kim Matthew
NEC Corporation
Sughrue & Mion, PLLC
LandOfFree
Multiprocessor system having means for arbitrating between... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Multiprocessor system having means for arbitrating between..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multiprocessor system having means for arbitrating between... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2925913