Electrical computers and digital processing systems: memory – Storage accessing and control – Shared memory area
Reexamination Certificate
1998-03-26
2001-10-02
Yoo, Do Hyun (Department: 2185)
Electrical computers and digital processing systems: memory
Storage accessing and control
Shared memory area
C711S148000, C711S150000, C711S156000, C711S159000
Reexamination Certificate
active
06298419
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Technical Field of the Invention
The present invention relates to shared memory network architectures, and more particularly, to a method for memory scaling when encountering memory shortages within a node of a software coherent network.
2. Description of Related Art
Distributed shared memory provides an important; compromise between the low cost of distributed memory machines and the convenient paradigm afforded by shared memory multiprocessors. Software shared memory has received much attention for both clusters of uniprocessors and clusters of multiprocessors. Existing designs of coherent shared memories and implementations of software shared memories treat local memory of a node as a third level cache and migrate and replicate shared data in that space. This approach, however, while simplifying the implementation of the coherence protocol results in the unfortunate side effect of preventing the total amount of shared memory available to the application from scaling with the size of the cluster. Adding additional nodes to the cluster increases the computational power of the overall cluster but does not increase the amount of shared memory which is available to the application. A significant number of applications require very large shared memories and while these applications may scale well under software coherence they cannot take full advantage of clustered environments due to memory limitations.
The primary reason behind the lack of memory scaling is that software distributed shared memories have not beer. designed to handle evictions of shared data. This results in the total amount of shared memory available being limited by the amount of memory which can be cached. The amount of memory which can be cached in turn is limited by the amount of memory available on the individual nodes within the cluster.
Race conditions between requests for data and data evictions complicate the coherence protocol. Furthermore, evicting data may completely eliminate it from the system and, therefore, steps must be taken when evicting data to ensure that a copy of the data remains in the system. Finally, evicting data from a node requires the updating of metadata which indicates to other nodes where the application data reside. Such updates need to be extremely efficient in order that they not degrade system performance.
OBJECTS OF THE INVENTION
Accordingly, it is an object of the present invention to provide a protocol which implements the efficient eviction of data from a coherent shared memory system in a multiprocessor architecture.
It is also an object of the present invention that such a protocol provide efficient notification to all nodes in the multinode architecture when data is being evicted or migrated.
It is still further an object of the present invention to provide further advantages and features, which will become apparent to those skilled in the art from the disclosure, including the preferred embodiment, which shall be described below.
SUMMARY OF THE INVENTION
The present invention overcomes the foregoing and other problems with a method and apparatus for providing additional memory storage within a local node that is a part of a shared memory system. A communications network enables communications to be carried on between each node of the system. The shared memory system includes a local memory associated with each node of the system. The local memory stores a plurality of groups of data referred to as pages. A directory associated with each node includes status information for each page of data stored within the shared memory system. The status information includes a variety of data concerning the state of a particular page. A Read-only bit indicates whether a copy of a page has only read-only privileges. Read-write bits indicate whether a copy of a page has read or write privileges. A difference bit indicates whether a node is writing differences of a particular page to the home node. A fetch bit indicates whether a node is attempting to fetch a page from its home node location, and eviction and migration bits indicate whether a home node of the page is being evicted or moved for other reasons.
At least one processor associated with each node of the network is configured to provide additional storage space within a local node by the eviction or movement of pages presently stored in local memory in the following manner.
Upon generation of a request for a fetch operation by the processor of a copy of a first group of data (page) from a home node location within the shared memory system, a determination is made as to whether sufficient local memory exists for receiving a copy of the first group of data. If sufficient memory does not exist, a second group of data within the local memory is selected for removal. The second group of data is selected such that removal of the second group of data does not cause the loss of any of the removed data from the shared memory system. If the local memory includes an only existing read-only copy of a group of data for which the local node is not a home node, this data is selected f or removal. If no read-only copy exists, the processor next searches for and selects a modified copy of a group of data within the local memory for which the local node is not a home node. If this too may not be found, a random group of data is selected for removal. This order of search is the preferred order, but other orders are possible. The mechanisms described herein can deal with any order and any type of page selected for eviction.
After a second group of data has been selected for removal, a determination is made whether the local node is the home node for the selected group of data. If the local node is not the home node, any modifications which have been made to the second group of data are determined and written back to the home node of the second group of data prior to removal. If the local node is the home node for the second group of data, the status information for the second group of data is updated to indicate that the home node location for the data is about to be changed. A waiting period may be implemented until all active operations involving the second group of data are completed. Once the active operations involving the second group of data are completed, the second group of data is written to a new home node location and directory information relating to the second group of data is updated to indicate the new home node location of the data. Once the second group of data has been removed, the first group of data may be fetched to local memory using the space vacated by the second group of data.
REFERENCES:
patent: 5269013 (1993-12-01), Abramson et al.
patent: 5274789 (1993-12-01), Costa et al.
patent: 5535116 (1996-07-01), Gupta et al.
patent: 5692149 (1997-11-01), Lee
patent: 5727150 (1998-03-01), Laudon et al.
patent: 5734922 (1998-03-01), Hagersten et al.
patent: 5918249 (1999-06-01), Cox et al.
patent: 5987506 (1999-11-01), Carter et al.
patent: 90/00283 (1990-01-01), None
Dubois et al., IEEE Transactions on Computers, vol. 38, No. 8, “Dynamic Page Migration in Multiprocessors with Distributed Global Memory”, Aug. 1989.
Kontothanassis Leonidas
Nikhil Rishiyur
Compaq Computer Corporation
McLean Kimberly
Oppenheimer Wolff & Donnelly LLP
Sherry Leah
Yoo Do Hyun
LandOfFree
Protocol for software distributed shared memory with 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 Protocol for software distributed shared memory with memory..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Protocol for software distributed shared memory with memory... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2607319