Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1999-02-26
2002-03-19
Choules, Jack (Department: 2177)
Data processing: database and file management or data structures
Database design
Data structure types
C709S241000
Reexamination Certificate
active
06360231
ABSTRACT:
TECHNICAL FIELD
The present invention relates generally to multi-processor computer systems and more particularly to system control units.
BACKGROUND ART
High performance, multi-processor computer systems with a large number of microprocessors are built by interconnecting a number of node structures, each node containing a subset of the processors and memory in the system. While the memory in the system is distributed, several of these systems support a shared memory abstraction where all the memory in the system appears as a large memory common to all processors in the system. To support high-performance, these systems typically allow processors to maintain copies of memory data in their local caches. Since multiple processors can cache the same data, these systems must incorporate a cache coherence mechanism to keep the copies coherent.
In some cache-coherent systems, each memory block (typically a portion of memory tens of bytes in size) is assigned a “home node”, which maintains all necessary global information for that memory block, manages the sharing of that memory block, and guarantees its coherence. The home node maintains a directory, which identifies the nodes that possess a copy of the memory block. When a node requires a copy of the memory block, it requests the memory block from its local, private cache. If the data is found, the memory access is resolved locally. Otherwise, a remote memory access is performed to the home node. The home node supplies the data from memory if its memory has the latest data. If another node has the latest copy of the data, the home node directs this node to forward the data to the requesting node. The data is then stored in the local cache of the requesting node.
In cache-coherent systems, multiple copies of the same memory block can exist in different nodes. These copies must be read-only and identical to the home memory copy. They are called “clean” copies in a “shared” state.
When a processor updates its local cache copy, it must ensure that all other copies are invalidated. Consequently, the processor has an ‘exclusive” and “modified” data copy, which hold the most recent value of the data. The other copies of the memory block are “stale”. The updating processor then becomes the “owner” of the memory block.
The home node employs a coherence protocol to ensure that when a node writes a new value to the memory block, all other nodes see this latest value. Coherence controllers implement this coherence functionality. First, they implement a coherence controller for each memory unit, which maintains coherence of all memory blocks in that memory unit. Second, the functionality of the coherence controller is integrated with the functionality of the System Control Unit (SCU) of the associated memory unit.
The SCU provides the control and the path for data movement for the following sources and destinations within the node: the processors within the node; the local (node) portion of the memory system; the network connecting all of the nodes of the multi-processor computer system; and the input/output (I/O) system of the local node.
However, the state-of-art cache-coherent shared-memory multiprocessor system designs do not have good support for data integrity. Consider that a process executes the following code:
LOCK
update global data A;
update global data B;
update global data C;
UNLOCK
The above code can be simply considered as a “transaction”. Execution of the transaction causes that the local cache of the executing processor has the most recent data values of locations A, B, and C. the home memory of locations A, B, and C have stale data copies. Unfortunately, if the local node fails, it means that the most recent values of locations A, B, and C are lost. In the worst case, the new value of location A is reflected back to its home memory, and the new changes for B and C are lost. As a result, the global data structure is corrupted or partially updated with incomplete information.
Note that this problem of data integrity is not caused by the failure of resources, in this case the home memory which exports locations A, B, and C. Instead, the problem is due to the failure of nodes/processes which use the resources.
Under many situations, the software may demand the semantics of “transactional memory”. In brief, a transaction performed on global data structures consists of a “request” phase, an “execution” phase and finally a “commit” phase. The new changes are considered globally complete and visible only after the transaction is committed. If any failure occurs before the transaction commits, the system state is rolled back to the state right before the transaction begins.
For the exemplified transaction, it is clear that the LOCK operation defines where the original system state is and where the request phase begins. The UNLOCK operation indicates where the update operations must commit. Specifically, before the LOCK is released, the home memory of A, B, and C is either completely updated with the new values, or is unchanged. Given this “All-or-None” semantics, all processes will observe either the original state before the LOCK, or the new state defined by the execution of the transaction.
Thus, a system has been long sought and long eluded those skilled in the art, which would provide an efficient implementation of transactional memory.
DISCLOSURE OF THE INVENTION
The present invention provides a cache coherent distributed shared memory multi-processor computer system which supports transactional memory semantics.
The present invention also provides a cache coherent distributed shared memory multi-processor computer system which supports transactional memory semantics with a cache flushing engine.
The present invention further provides a cache coherent distributed shared memory multi-processor computer system which allows programmers to selective force write-backs of dirty cache lines to the home memory.
The above and additional advantages of the present invention will become apparent to those skilled in the art from a reading of the following detailed description when taken in conjunction with the accompanying drawings.
REFERENCES:
patent: 5201044 (1993-04-01), Frey, Jr. et al.
patent: 5329626 (1994-07-01), Klein et al.
patent: 5335343 (1994-08-01), Lampson et al.
patent: 6049889 (2000-04-01), Steely, Jr. et al.
patent: 6055605 (2000-04-01), Sharma et al.
Data Concurrency Control in Distributed Data Networks. Dec. 1981, IBM Technical Disclosure Bul letin, vol. 24 No. 7A, pp. 3137-3139.
Nguyen Tung
Pong Fong
Russell Lance
LandOfFree
Transactional memory for distributed shared memory... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Transactional memory for distributed shared memory..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Transactional memory for distributed shared memory... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2850098