Electrical computers and digital processing systems: memory – Storage accessing and control – Shared memory area
Reexamination Certificate
1999-02-26
2001-07-31
Robertson, David L. (Department: 2187)
Electrical computers and digital processing systems: memory
Storage accessing and control
Shared memory area
C710S240000, C711S141000
Reexamination Certificate
active
06269428
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 livelocks due to colliding invalidating transactions 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, one particular concern with a NUMA system is the potential livelock problem that arises from the cache coherence protocol. For example, when a processor at a remote node is attempting to invalidate a cache line within its cache memory at the same time when a processor at a home node is also attempting to invalidate the same cache line, a livelock situation can occur. Consequently, it would be desirable to provide a method for avoiding livelocks due to colliding invalidating transactions 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 a request by a processor of a first node to invalidate a remote copy of a cache line also stored within its cache memory at substantially the same time when a processor of a second node is also requesting to invalidate said cache line, one of the two requests is allowed to complete. The allowed request is the first request to complete without retry at the point of coherency, typically the home node. Subsequently, the other one of the two requests is permitted to complete.
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.
Carpenter Gary Dale
Dean Mark Edward
Glasco David Brian
Bracewell & Patterson L.L.P.
International Business Machines - Corporation
Robertson David L.
Salys Casimer K.
LandOfFree
Method and system for avoiding livelocks due to colliding... 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 colliding..., 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 colliding... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2527955