Electrical computers and digital processing systems: memory – Storage accessing and control – Shared memory area
Reexamination Certificate
1999-02-26
2001-05-01
Nguyen, Hiep T. (Department: 2187)
Electrical computers and digital processing systems: memory
Storage accessing and control
Shared memory area
C711S121000, C711S143000, C711S144000, C711S145000, C711S150000, C711S168000, C711S169000
Reexamination Certificate
active
06226718
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Technical Field
The present invention relates to a method and system for data processing in general, and in particular to a method and system for avoiding livelocks within a computer system. Still more particularly, the present invention relates to a method and system for avoiding protocol livelocks due to stale exclusive/modified directory entries within a non-uniform memory access computer system.
2. Description of the Prior Art
It is well-known in the computer arts that greater computer system performance can be achieved by combining the processing power of several individual processors to form a multiprocessor (MP) computer system. MP computer systems can be designed with a number of different topologies, depending on the performance requirements of a particular application. A symmetric multiprocessor (SMP) configuration, for example, is one of the simpler MP computer system topologies that are commonly used, in which resources such as a system memory are shared by multiple processors. The topology name “symmetric” stems from the fact that all processors within an SMP computer system have symmetric access to all resources within the system.
Although the SMP topology permits the use of relatively simple inter-processor communication and data sharing protocols, the SMP topology overall has a limited scalability and bandwidth, especially at the system memory level as the system scale increases. As a result, another MP computer system topology known as non-uniform memory access (NUMA) has emerged as an alternative design that addresses many of the limitations of the SMP topology, at the expense of some additional complexity.
A typical NUMA computer system includes a number of interconnected nodes. Each node includes at least one processor and a local “system” memory. The NUMA topology name stems from the fact that a processor has lower access latency with respect to data stored in the system memory at its local node than with respect to data stored in the system memory at a remote node. NUMA computer systems can be further classified as either non-cache coherent or cache coherent, depending on whether or not data coherency is maintained among caches in different nodes. The NUMA topology addresses the scalability limitations of the conventional SMP topology by implementing each node within a NUMA computer system as a smaller SMP system. Thus, the shared components within each node can be optimized for use by only a few processors, while the overall system benefits from the availability of larger scale parallelism with relatively low latency.
Despite all the various advantages, a NUMA system also has its fair share of problems, one of them being livelocks. For example, if a reading processor did not modify a cache line that was exclusive to the reading processor and instead cast out the cache line without informing a cache coherency directory, the cache coherency directory would still indicate that the reading processor has the cache line exclusively. Subsequent accesses to the cache line will be forwarded to the reading processor, which will indicate that the reading processor no longer has the cache line. A livelock can occur if a processor from a node different from the node that previously owned the cache line attempts to access the cache line at the same time the reading processor attempts to access the same cache line again. Consequently, it would be desirable to provide a method for avoiding protocol livelocks due to stale exclusive/modified directory entries within a NUMA computer system.
SUMMARY OF THE INVENTION
In accordance with the method and system of the present invention, a NUMA computer system includes at least two nodes coupled to an interconnect. Each of the two nodes includes a local system memory. In response to an attempt by a processor of a first node to read a cache line at substantially the same time as a processor of a second node attempts to access the same cache line, wherein the cache line has been silently cast out from a cache memory within the second node even though a coherency directory within the home node still indicates the cache line is held exclusively in the second node. The receipt of the request from the second node, the owning node, allows the node controller to infer that second node no longer has a modified copy of the line, and the node controller can update the directory with this new information. The owning node is the node with the most recent copy of the cache line exist. Subsequent requests will find the data in the system memory at the home node.
All objects, features, and advantages of the present invention will become apparent in the following detailed written description.
REFERENCES:
patent: 6078981 (2000-06-01), Hill et al.
patent: 6108752 (2000-08-01), VanDoren et al.
Carpenter Gary Dale
Dean Mark Edward
Glasco David Brian
Felsman Bradley Vaden Gunter & Dillon, LLP
International Business Machines - Corporation
Nguyen Hiep T.
Salys Casimer K.
LandOfFree
Method and system for avoiding livelocks due to stale... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and system for avoiding livelocks due to stale..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for avoiding livelocks due to stale... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2455269