Electrical computers and digital data processing systems: input/ – Access arbitrating – Access prioritizing
Reexamination Certificate
2001-10-12
2004-10-12
Lefkowitz, Sumati (Department: 2181)
Electrical computers and digital data processing systems: input/
Access arbitrating
Access prioritizing
C710S045000, C710S117000, C710S124000, C370S395210, C370S395410, C370S395420, C370S395430, C711S151000
Reexamination Certificate
active
06804738
ABSTRACT:
FIELD OF THE INVENTION
The field of the invention relates to a system where access to a resource is scheduled to provide a particular quality-of-service to two or more requestors competing for access to that resource.
BACKGROUND
In computer systems it is common that a given resource (such as a system bus, a memory bank, etc.) is shared between several competing requesting devices or processes (“requesters”) that would like to make use of the resource. Access to that resource therefore has to be arbitrated, in order to determine which requestor can access the resource when there are concurrent and conflicting requests to the resource. It is desirable to be able to specify different quality-of-service (QOS) guarantees for different requestors in order for the system to operate properly. Examples of QOS guarantees include data bandwidth and latency. For example, it may be desirable to allow a processor to have very high-priority and therefore low-latency access to a memory system. Another example is that one might want a video system to have a certain reserved bandwidth on a system bus so that the video screen can be updated as required at a fixed frame rate.
Existing arbitration schemes that aim to provide QOS guarantees include fixed-priority arbitration and time division multiplexing. In fixed-priority arbitration each requester is assigned a fixed priority and requesters are serviced in priority order. In time division multiplexing, each requestor is pre-allocated a certain set of fixed access periods during which it can access the resource. While these arbitration schemes have their value in certain systems, they fall short of providing QOS guarantees when there is a mix of requesters with different QOS requirements and perhaps unpredictable request arrival times. For example, it is not possible to give any kind of bandwidth guarantee to multiple different requesters if fixed-priority arbitration is used unless the exact request pattern of each initiator is known a priori. Time division multiplexing is inefficient when the arrival times of requests are not deterministic, or when the requests require differing amounts of service time from the resource depend on the type of request or the recent history of other requests.
What is desired is a resource scheduling scheme that can provide different QOS guarantees to different requestors and further can efficiently handle non-deterministic arrival and service times.
SUMMARY OF THE INVENTION
The present invention is directed to a method and apparatus for scheduling a resource to meet quality of service guarantees. In one embodiment of three levels of priority, if a channel of a first priority level is within its bandwidth allocation, then a request is issued from that channel. If there are no requests in channels at the first priority level that are within the allocation, requests from channels at the second priority level that are within their bandwidth allocation are chosen. If there are no requests of this type, requests from channels at the third priority level or requests from channels at the first and second levels that are outside of their bandwidth allocation are issued. The system may be implemented using rate-based scheduling.
REFERENCES:
patent: 5218456 (1993-06-01), Stegbauer et al.
patent: 5274769 (1993-12-01), Ishida
patent: 5287464 (1994-02-01), Kumar et al.
patent: 5363484 (1994-11-01), Desnoyers et al.
patent: 5469473 (1995-11-01), McClear et al.
patent: 5530901 (1996-06-01), Nitta
patent: 5557754 (1996-09-01), Sone et al.
patent: 5664153 (1997-09-01), Farrell
patent: 5748629 (1998-05-01), Caldara et al.
patent: 5809538 (1998-09-01), Pollmann et al.
patent: 5917804 (1999-06-01), Shah et al.
patent: 5926649 (1999-07-01), Ma et al.
patent: 5982780 (1999-11-01), Bohm et al.
patent: 5996037 (1999-11-01), Emnett
patent: 6023720 (2000-02-01), Aref et al.
patent: 6092137 (2000-07-01), Huang et al.
patent: 6104690 (2000-08-01), Feldman et al.
patent: 6122690 (2000-09-01), Nannetti et al.
patent: 6167445 (2000-12-01), Gai et al.
patent: 6253269 (2001-06-01), Cranston et al.
patent: 6330225 (2001-12-01), Weber et al.
patent: 6335932 (2002-01-01), Kadambi et al.
patent: 6363445 (2002-03-01), Jeddeloh
patent: 6628609 (2003-09-01), Chapman et al.
patent: 6636482 (2003-10-01), Cloonan et al.
patent: 2002/0174227 (2002-11-01), Hartsell et al.
patent: 2003/0079080 (2003-04-01), DeMoney
Lamport, Leslie; How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs, IEEE Transactions On Computers, vol. C-28, No. 9, Sep. 1979, pp. 690-691.
Rixner, Scott, et al., Memory Access Scheduling, To appear in ISCA-27 (2000), Computer Systems Laboratory, Stanford University, Stanford, CA 94305, pp. 1-11.
Search Report for PCT/US02/05438, mailed May 24, 2002, 1 page.
Search Report for PCT/US02/05288, mailed May 20, 2002, 1 page.
Search Report for PCT/US02/05439, mailed Jun. 26, 2002, 1 page.
Search Report for PCT/US02/05287, mailed Jul. 11, 2002, 2 pages.
Rixner et al., “A Bandwidth-Efficient Architecture for Media Processing”, Micro-31, 1998, pp. 1-11.
Blakely , Sokoloff, Taylor & Zafman LLP
Lefkowitz Sumati
Sonics, Inc.
LandOfFree
Method and apparatus for scheduling a resource to meet... 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 scheduling a resource to meet..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for scheduling a resource to meet... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3267958