Electrical computers and digital processing systems: multicomput – Computer conferencing – Priority based messaging
Reexamination Certificate
1998-12-22
2001-09-25
Etienne, Ario (Department: 2155)
Electrical computers and digital processing systems: multicomput
Computer conferencing
Priority based messaging
C710S040000, C710S111000, C710S244000, C710S264000
Reexamination Certificate
active
06295553
ABSTRACT:
FIELD OF THE INVENTION
This invention relates generally to transfer request priority management in multiprocessing systems, and more particularly to a system and method for prioritizing the delivery of information transfer requests using a least-recently-serviced rotational priority technique.
BACKGROUND OF THE INVENTION
Large-scale data processing systems typically utilize a tremendous amount of memory. This is particularly true in multiprocessing systems where multiple processing units are implemented. There are several memory methodologies known in the art that provide for efficient use of memory in such multiprocessing environments. One such memory methodology is a distributed memory where each processor has access to its own dedicated memory, and access to another processor's memory involves sending messages via an inter-processor network. While distributed memory structures avoid problems of contention for memory and can be implemented relatively inexpensively, it is usually slower than other memory methodologies, such as shared memory systems.
Shared memory is used in a parallel system, or multiprocessing system, and can be accessed by more than one processor. The shared memory is connected to the multiple processing units—typically accomplished using a shared bus or network. Large-scale shared memories may be designed to cooperate with local cache memories associated with each processor in the system. Cache consistency, or coherency, protocols ensure that one processor's cached copy of a shared memory location is invalidated when another processor writes to that location.
It may be the case that the main system memory assumes the responsibility for maintaining cache coherency. Data modifications applied to a particular cache must be properly regulated and controlled to eliminate the risk of any other requesting device accessing invalid data. Control circuitry and cache directory structures may be used within the main system memory to perform these regulation and control functions. In such a case, there is no direct connectivity between the independent caches because the control circuitry must be involved in order to maintain cache coherency. Furthermore, input/output (I/O) processors must also be able to bidirectionally communicate with system processors, and cache memories operating in connection with I/O processors is also therefore regulated by the directory structures, control circuitry, and other coherency-related circuitry.
Requests for data transfers may occur at a faster rate than the memory and associated cache coherency logic can sustain. A buffering technique is typically used to queue such requests until they can be processed. However, the queuing function can sometimes result in inefficient and discriminatory request servicing. In some cases, one processor's requests may be repeatedly processed, while another's arc left relatively unattended. In other cases, a processor having relatively few requests may needlessly tie up system resources by receiving unnecessary request service polls. These situations can reduce available request bandpass, and increase the probability of request stalling or request lockout.
It is desirable for data transfer requests to be managed as efficiently as possible. One method known in the art that attempts to alleviate these problems is known as a “fixed” request priority scheme. Each requester is assigned a fixed priority value, and requests are handled according to this associated priority value. Those requests having a high fixed priority value are always handled prior to those having relatively low priority values. Such a scheme leaves the lowest priority requester completely unattended unless, and until, no other requests are pending. This type of arrangement can cause request “stalls” or “lockouts”, since a high priority requester might always have a request available, blocking out lower priority requesters. While this is acceptable from the high priority requester's point of view, this results in serious performance degradation for lower priority requesters.
Another request priority scheme is referred to as “snap-fixed”, where input request activity is continually or periodically polled. This results in a captured “snapshot” of the request activity at a given time. All of the captured requests are processed in a fixed order until all requests in the snapshot have been processed, at which time a new snapshot is taken. While this approach is arguably better than the fixed approach, it too has its drawbacks. The snap-fixed approach can reduce or eliminate lockouts, but at a cost. A lower priority request always has to wait for all higher requests in the snapshot. This may be acceptable for a system where the high volume requesters are mixed with low volume requesters, and the low volume requesters are assigned a high priority level to compensate for the volume discrepancy. This would have very little adverse affect on the higher volume requesters since they would only occasionally be delayed. However, where the volume of all requesters is similar, this method clearly favors the requesters having higher priority assignments, and the other requesters will continually experience longer delays.
A “simple rotational” priority scheme involves changing the requester priority on a periodic basis. For example, the requester priority may be changed whenever a request is granted priority. Requester (N−1) moves to priority level (N), requester (N) moves to (N+1), and so forth. A disadvantage of a simple rotational scheme is that a requester may pass through its high priority assignment when it has no request ready, and may end up at the low end of the priority assignments when it does have a request available.
It would therefore be desirable to provide an efficient request priority arrangement and method that assigns priority based on the relative activity of each of the requesters as compared to other requesters in the system, thereby minimizing request stalling yet providing request priority where it is needed most. The present invention provides a request priority arrangement and method based on a unique, least-recently-serviced, rotational priority. Furthermore, the present invention is modular to provide for increased requester capacity, and is designed to be inherently adjustable to account for specific requester priority level assignments. The present invention offers these and other advantages over the prior art, and provides a solution to the aforementioned and other shortcomings of the prior art.
SUMMARY OF THE INVENTION
The present invention relates to a system and method for prioritizing the delivery of information transfer requests using a least-recently-serviced rotational priority technique. The invention implements a least-recently-serviced rotational priority scheme to allow inactive requesters assigned to higher priorities than a granted requester to maintain their current relative priority rank, while allowing all requesters assigned to lower priorities than the granted requester to collectively increment in priority ranking.
In accordance with one embodiment of the invention, a method is provided for prioritizing the delivery of information transfer requests in a system having one or more requesters to supply the information transfer requests. Active requesters have currently pending information transfer requests, and non-active requesters have no currently pending information transfer requests. The method includes granting transfer authorization to the information transfer request associated with the active requester that is currently assigned to the highest priority level in a range of priority levels. Each of the active and non-active requesters that have a priority level less than the priority level of the active requester that was granted the transfer have their priority levels incremented, while the non-active requesters having a priority level greater than the priority level of the active requester that was granted the transfer is maintained at its current priority level. Th
DePenning James L.
Gilbertson Roger Lee
Etienne Ario
Johnson Charles A.
Nawrocki, Rooney & Sivertson P.A.
Starr Mark T.
Unisys Corporation
LandOfFree
Method and apparatus for prioritizing delivery of data... 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 apparatus for prioritizing delivery of data..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for prioritizing delivery of data... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2514858