Electrical computers and digital processing systems: memory – Storage accessing and control – Hierarchical memories
Reexamination Certificate
1999-02-26
2001-08-21
Yoo, Do Hyun (Department: 2187)
Electrical computers and digital processing systems: memory
Storage accessing and control
Hierarchical memories
C711S141000, C711S142000, C711S145000, C711S148000, C711S168000, C710S200000
Reexamination Certificate
active
06279085
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 writebacks 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 located at a remote node, which contains a modified copy of a cache line, attempts to cast the cache line out of its cache memory by issuing a writeback request to a home node at the same time a processor located at the home node is attempting to access the same cache line, a livelock situation can occur. Consequently, it would be desirable to provide a method for avoiding the above-mentioned livelock situation caused by colliding writebacks 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 processing nodes coupled to an interconnect. Each of the two processing nodes includes a local system memory. In response to an attempt by a processor located at a node other than a owning node to access a cache line modified at the owning node via a memory request at substantially the same time when a processor located at said owning node attempts to writeback the modified cache line to the home node, the writeback is allowed to complete at the home node without retry only if the writeback is from what a coherency directory within the home node considered as the owning node of the modified cache line. The owning node is the node with the most recent copy of the cache line exist. The memory request is then allowed to retry and completed at the home node.
All objects, features, and advantages of the present invention will become apparent in the following detailed written description.
REFERENCES:
patent: 5829032 (1998-10-01), Komuro et al.
patent: 5950228 (1999-09-01), Scales et al.
patent: 6078981 (2000-06-01), Hill et al.
patent: 6085295 (2000-07-01), Ekanadham et al.
Carpenter Gary Dale
Glasco David Brian
Bracewell & Patterson L.L.P.
International Business Machines - Corporation
Pham Vu A.
Salys Casimer K.
Yoo Do Hyun
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-2442823