Electrical computers and digital processing systems: memory – Address formation – Combining two or more values to create address
Reexamination Certificate
2001-07-25
2004-03-30
Padmanabhan, Mano (Department: 2188)
Electrical computers and digital processing systems: memory
Address formation
Combining two or more values to create address
C711S147000, C711S148000, C711S150000, C711S154000, C711S168000, C709S213000, C709S214000
Reexamination Certificate
active
06715059
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The invention relates generally to the field of multiprocessor parallel processing systems. More particularly, the invention relates to multiprocessor parallel processing systems configured with globally accessible shared memory apparatus.
2. Discussion of the Related Art
A shared memory unit is made up in two general areas as an atomic complex and a shared memory area.” The atomic complex is further subdivided into a lock complex, doorbell complex, and miscellaneous area.
The lock complex is merely an array of shared memory unit memory locations that provide a “test and set” like operation on a 32 bit object or memory word. When the shared memory unit receives a read request for one of these objects it returns the data to the requester. In addition, if the least significant bit (LSB) of the data is a binary 0 the shared memory unit sets the LSB to a 1 in its copy of the data. Thus any future reads of this object will return a 1 in the LSB of the data. If the LSB is already a 1 then the shared memory unit just returns the data and does nothing to its copy. When a requester sees that the data returned has the LSB cleared or 0 it can assume any future reads, by other hosts attached to the shared memory unit, will return a 1 in the LSB thus creating an element with “test and set” locking heuristics. The LSB stays set until the first reader, the one that read the element where the LSB was 0, writes a binary 0 back to the element thus clearing this test and set lock.
With this primitive the shared memory area of the shared memory unit can be broken up into many pieces that can each be accessed atomically by team members as long as they acquire a lock prior to accessing each area. For example, in shared memory there can be a doubly linked list of widget structures. Widget structures are added to the list by some team members and removed by others. Since each team member is running asynchronously with respect to each other and they all have access to this list the team must be very careful when changing the list. Only one team member may change the list at a time. This is accomplished by acquiring the lock above, modifying the list and releasing the lock when the list is updated. When one team member owns the lock all other team members that want the lock must wait. These waiting team members are usually in a state where they can do nothing else until it is their turn to update the list, thus wasting valuable CPU cycles. As the number of team members increase, the lock contention increases geometrically to a point where adding team members to the team no longer adds to the performance of the team.
The present invention overcomes the above limitation and others by describing methods and apparatus wherein a shared memory unit can be used to eliminate the above discussed problems in the prior art. In addition, methods for dynamically expanding the capabilities of a shared memory unit to deliver various functions are disclosed.
SUMMARY OF THE INVENTION
There is a need for the following embodiments. Of course, the invention is not limited to these embodiments.
According to an aspect of the invention, a method comprises: permitting a plurality of central processing units to simultaneously read data stored in a first shared memory address, the first shared memory address being accessed by a first central processing unit; receiving a request to read the first shared memory address from a second central processing unit; receiving a request to read the first shared memory address from a third central processing unit; determining a relationship between data stored in the first shared memory address and data stored in a second shared memory address; determining a relationship between data stored in the first shared memory address and data stored in a third shared memory address; transforming the data stored in the second shared memory address to a form equivalent to that of the data stored in the first shared memory address; transforming the data stored in the third shared memory address to a form equivalent to that of the data stored in the first shared memory address; permitting the second central processing unit to access data stored in the second shared memory address; and permitting the third central processing unit to access data stored in the third shared memory address. According to another aspect of the invention, a method, comprises: providing a queue of activity to a central processing unit, the queue of activity residing in the shared memory unit; receiving a request from a central processing unit via the queue of activity to move a block of shared memory, the block of shared memory residing in the shared memory unit; moving the block of shared memory as desired by the central processing unit; and notifying the central processing unit upon completion of the move of the block of shared memory. According to another aspect of the invention, a method, comprises: providing a queue of activity to a central processing unit, the queue of activity residing in the shared memory unit; receiving a request from a central processing unit via the queue of activity to update data stored in a shared memory address, the request including an old value and a new value; if the old value received from the central processing unit matches a data stored in the shared memory address, updating the data stored in the shared memory address to the new value; and then notifying the central processing unit of a successful update of the data stored in the shared memory address to the new value. According to another aspect of the invention, a method, comprises permitting a shared memory unit to control a plurality of central processing units attempting to traverse a data structure stored in the shared memory unit. According to another aspect of the invention, an apparatus comprises: a central processing unit; and a shared memory unit coupled to the central processing unit, the shared memory unit including a data structure and a queue of activity documenting shared memory accesses by the central processing unit of the shared memory unit.
These, and other, embodiments of the invention will be better appreciated and understood when considered in conjunction with the following description and the accompanying drawings. It should be understood, however, that the following description, while indicating various embodiments of the invention and numerous specific details thereof, is given by way of illustration and not of limitation. Many substitutions, modifications, additions and/or rearrangements may be made within the scope of the invention without departing from the spirit thereof, and the invention includes all such substitutions, modifications, additions and/or rearrangements.
REFERENCES:
patent: 4486834 (1984-12-01), Kobayashi et al.
patent: 5568609 (1996-10-01), Sugiyama et al.
patent: 5604882 (1997-02-01), Hoover et al.
patent: 5649092 (1997-07-01), Price et al.
patent: 5668943 (1997-09-01), Attanasio
patent: 5765157 (1998-06-01), Lindholm et al.
patent: 5983326 (1999-11-01), Hagersten et al.
patent: 6092166 (2000-07-01), Bobak et al.
patent: 6108757 (2000-08-01), Arshad
patent: 6173375 (2001-01-01), Arshad
patent: 6385658 (2002-05-01), Harter et al.
patent: 6427195 (2002-07-01), McGowen et al.
patent: 0 602 791 (1994-06-01), None
International Search Report for PCT/US02/23171 dated Mar. 3, 2003.
International Search Report dated Jul. 16, 2002.
International Search Report mailed Jun. 5, 2002.
Bershad, et al., “The Midway Distributed Shared Memory System” Compcon Digest of Papers, pp. 528-537, Feb. 22, 1993.
Wilson, et al. “Hardware Assist for Distributed Shared Memory” Proceedings of the International Conference on Distributed Computing Systems, pp. 246-255, May 25, 1993.
Songnian, et al. “Heterogeneous Distributed Shared Memory,” IEEE Transactions on Parallel and Distributed Systems, vol. 3, No. 5, pp. 540-554, Sep. 1, 1992.
Nitzberg, et al. “Distributed Shared Memory: A Survey of Issues and Algorithms,” IEEE Computer Society, pp. 52-60, Aug. 1, 1991.
Stumm,
Gray Cary Ware & Freidenrich LLP
Padmanabhan Mano
Song Jasmine
TAS Holdings, Inc.
LandOfFree
Methods and systems for a shared memory unit with extendable... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Methods and systems for a shared memory unit with extendable..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods and systems for a shared memory unit with extendable... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3214628