Electrical computers and digital processing systems: memory – Storage accessing and control – Hierarchical memories
Reexamination Certificate
2001-08-30
2004-06-29
Kim, Hong (Department: 2186)
Electrical computers and digital processing systems: memory
Storage accessing and control
Hierarchical memories
C711S141000, C711S158000, C711S151000, C711S144000, C709S225000
Reexamination Certificate
active
06757788
ABSTRACT:
BACKGROUND OF THE INVENTION
This invention relates to cache coherence control of a computer system, and more particularly to a cache coherence control system for ensuring coherency between caches of a plurality of CPU's, I/O devices and nodes of a parallel computer system constituted of a plurality of nodes interconnected by an interconnect network.
In a multi CPU system, a plurality of CPU's perform tasks by accessing a common main memory (shared memory). In such a system, as one CPU executes a main memory access, it becomes necessary to ensure cache coherency of all CPU's by checking, for example, the existence of modified data in caches of all other CPU's. This process is called cache coherence control.
In the reference document “SCALABLE SHARED-MEMORY MULTIPROCESSING”, Daniel E. Lenoski et al., published by Morgan Kaufmann Publishers, pp. 16-19, there is a description about a cache coherence control method for a system having a plurality of interconnected CPU's. With this method, a main memory access issued by one CPU is transferred to all other CPU's to ensure cache coherency by checking, for example, the existence of modified data in the caches of all CPU's.
In a multi CPU system according to conventional techniques, in order to ensure cache coherency, it is necessary to broadcast a main memory access of one CPU to all CPU's and perform a cache coherence control at all CPU's of the system.
With these conventional techniques, the number of cache coherence control requests received at each CPU increases in proportion to the number of CPU's.
As the number of CPU's of a multi CPU system increases, the number of cache coherence control requests received at each CPU increases so that a cache access by each CPU becomes difficult. As the number of cache coherence control requests at each CPU transferred to the network interconnecting all CPU's of the system increases, the network may be saturated.
As a result, even if the number of CPU's of the multi CPU system is increased more than a certain number, the system performance cannot be improved.
A parallel computer system has general characteristics that many areas of a memory to be accessed are independent from each process or each thread, and it is rare for the memory to be shared by processes or threads.
Based upon such characteristics, the following approach may be made. A memory area once accessed by a node is assumed to be a memory area which can be accessed exclusively by this node, and when another node accesses this memory area, this memory area is considered as a shared area. In this manner, many memory areas can be accessed exclusively by each node. An access to such memory areas can be executed without cache coherence control so that the number of cache coherence requests can be reduced.
To realize this approach, each memory area is related to each access right. If some node has an access right to a target memory area, this node accesses this memory area without cache coherence control, whereas if the node has no access right, the node accesses this memory area by performing usual cache coherence control.
If a node is to access a memory area whose access right is possessed by another node, the other node with the access right is deprived of the access right. Thereafter, for a memory access to the memory area, the other node executes the cache coherence control.
Generally, a memory is accessed in the unit of a cache block. It is therefore natural to relate an access right to each memory block.
However, with this method, even if some node accesses some block and the access right to this block is given to the node, the number of cache coherence controls cannot be reduced unless the node accesses again this block.
Most of business applications have a low accessibility to the same memory block. Therefore, the above method is associated with the problem that the effects of reducing cache coherence control requests are poor.
SUMMARY OF THE INVENTION
It is an object of the present invention to provide a cache coherence control system capable of reducing the number of cache coherence control requests even for a program having a low accessibility to the same memory block.
In order to achieve the above object, according to a representative aspect of the invention, there is provided a cache coherence control system for caches which store, in the unit of a predetermined block, data of a shared memory accessed by a CPU or an I/O device provided at each of a plurality of nodes interconnected by a mutual interconnection network, wherein: in the cache coherence control system, each node has an access right memory for registering an access right entry representative of that the node has an access right to an extended block corresponding to a plurality of blocks of the shared memory; if the node of the CPU or I/O device has an access right to the extended block including a target block for a shared memory access, the target block in the shared memory is accessed without cache coherence control for caches of other nodes; and if the node of the CPU or I/O device has no access right to the extended block including the target block for the shared memory access, cache coherence control for the caches of other nodes are performed and when necessary the shared memory block is accessed.
In the cache coherence control system: the access right memory uses a portion of an address of the extended block as an access right row address, and a portion other than the access right row address of the extended block address of the shared memory as an access right entry tag; and the access right entry tag and one or more of the access right entries for storing the access right status are stored in the access right memory at a same access right row address.
In the cache coherence control system: in accessing the access right memory, the access right memory is read by using the access right row address obtained from the address of the extended block including the target access block of the shared memory; and an access right status of an access right entry among a plurality of access right entries at the access row address, the access right entry having an access right entry tag coincident with the access right entry tag obtained from the extended block address, is used as the access right status of the node.
The access right status includes three statuses: a status with an access right; a status without an access right; and a status with an indefinite access right.
In this case: when the CPU or I/O device issues the shared memory access with cache coherence control; the node of the CPU or I/O device searches the access right memory of the node; if the access right entry corresponding to the extended block including the target access block for the shared memory access does not exist in the access right memory of the node, or if the access right entry corresponding to the extended block exists in the access right memory of the node and the access right status in the access right entry is the status with an indefinite access right; cache coherence control is performed for caches in all other nodes relative to the target access block; an extended block storing status check is performed to check whether one or more blocks in the extended block including the target access block are stored in the cache of each of the other nodes; if the access right entry corresponding to the extended block including the target access block of the shared memory exists and the access right status of the access right is the status without an access right, cache coherence control is performed for the cache of each of all other nodes relative to the target access block; and if the access right entry corresponding to the extended block including the target access block of the shared memory exists and the access right status of the access right is the status with an access right, cache coherence control is not performed for the cache of each of the other nodes.
Further: when a shared memory access with a cache coherence cont
Hamanaka Naoki
Higuchi Tatsuo
Kawamoto Shinichi
Maeda Hiromitsu
Antonelli Terry Stout & Kraus LLP
Hitachi , Ltd.
Kim Hong
LandOfFree
CACHE COHERENT CONTROL SYSTEM FOR NETWORK NODES ALLOWS CPU... 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 COHERENT CONTROL SYSTEM FOR NETWORK NODES ALLOWS CPU..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and CACHE COHERENT CONTROL SYSTEM FOR NETWORK NODES ALLOWS CPU... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3332099