Methods and apparatus for data bus arbitration

Details Methods and apparatus for data bus arbitration Methods and apparatus for data bus arbitration

1999-01-06

2002-05-21

Etienne, Ario (Department: 2155)

Electrical computers and digital data processing systems: input/

Intrasystem connection

Bus access regulation

C710S040000, C710S113000, C710S240000, C710S241000, C710S244000

Reexamination Certificate

active

06393505

ABSTRACT:

CROSS REFERENCE TO RELATED APPLICATIONS
This application is related to co-pending U.S. patent application Ser. No. 09/226,776 entitled Methods And Apparatus For Variable Length SDRAM Transfers filed on the same day, which is incorporated herein by reference.
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates generally to arbitration for access to a digital device and more particularly, to techniques for arbitrating multiple data transfer requests to optimize the operation of a computer system.
2. Description of the Related Art
Dynamic random access memory (DRAM) is used to provide a number of different functions in computers including: “scratch pad” memory and video frame buffers. Synchronous dynamic random access memory (SDRAM) is a type of DRAM designed to deliver bursts of data at very high speed using automatic addressing, multiple page interleaving, and a synchronous (or clocked) interface. The SDRAM is typically monitored and managed by a SDRAM controller.
The SDRAM controller receives data transfer requests for memory access to the SDRAM. To establish the priority of the data transfer requestors, the SDRAM controller generally includes an arbiter. The arbiter receives information from the requestors to determine the type of data transfer requested, and then uses an arbitration scheme to assign a priority to each of the requesters. The SDRAM controller then grants memory access to the SDRAM based on the priority established by the arbiter.
Perhaps the simplest type of arbitration scheme is fixed priority, where each type of request in a system is assigned a fixed priority. When an arbiter receives multiple requests, the request with the highest priority always receives access to the data bus. For example, if there is a request A of high priority and request B of medium priority, then request B will receive memory access only if request A is not present.
A major problem with fixed priority arbitration schemes is that they can handle only a limited number of requesters because of the risk that devices with a low priority will not be timely serviced, if at all. For example, in a fixed priority scheme, if there is a request A of high priority, request B of medium priority, and request C of low priority, and the arbiter is constantly bombarded with requests A and B, then request C will “starve” and never be serviced. The risk of starvation rises with the number of devices that request service. In fact, if a fixed priority scheme includes ten devices with ten levels of priority, starvation is virtually guaranteed.
Another type of arbitration scheme used in the prior art is a round robin scheme. The standard round robin scheme deals with all the requests in a fixed order. For example, if request A is of high priority, request B of medium priority, and request C of low priority, the round robin scheme will grant request A first, then grant request B, and then grant request C. However, if request A is not present, then request B becomes of high priority, request C of medium priority and request A of low priority. Therefore, the round robin scheme continually shifts priority between all of the devices it services.
As with the fixed priority scheme, round robin schemes also run into starvation problems when handling a large number of requesters. Take the example of a round robin scheme that looks for and grants requests A-Z in alphabetical order, where request A has not been asserted at the time it is sought. If request A is asserted at the time that request B is being sought, then it is possible that request A will not be granted until requests B-Z have been serviced.
Another type of arbitration scheme used in the prior art is a dynamic priority scheme, which utilizes a set of rules that determine the priority of the requestors established by the arbiter. For example, the rules may give a higher priority to requesters that require the most bandwidth of memory access from a SDRAM or give higher priority to requestors that have most recently been serviced.
Dynamic priority schemes allow for in theory, an unlimited number of ways for an arbiter to establish the priority of multiple requestors. However, the more complicated the rules are, the more process overhead will be required to maintain the dynamic priority scheme. This is particularly true in cases where the dynamic priority scheme must arbitrate between real time devices.
There are several other arbitration schemes in the prior art such as a window based scheme that gives each requestors a certain slice of time where memory access will be granted. The advantage of the window based scheme is that it can guarantee bandwidth for its requesters. However, as with the dynamic priority scheme, the windows based scheme involving multiple requestors would be very complicated and require a great deal of logic. Furthermore, a window based scheme would have difficulty maintaining efficient data bus utilization because a slice in time may be set aside for a device when there is no request resulting in idle tine where the bus does nothing.
In view of the foregoing, it is desirable to have methods and an apparatus that is able to establish priority between multiple devices with real time requirements, while at the same time maintaining efficient utilization of the data bus.
SUMMARY OF THE INVENTION
The present invention fills these needs by providing methods and an apparatus for arbitrating between and servicing requestors having real time requirements while maintaining efficient utilization of the data bus. It should be appreciated that the present invention can be implemented in numerous ways, including as a process, an apparatus, a system, a device or a method. Several inventive embodiments of the present invention are described below.
In one embodiment of the present invention, a data bus arbitration system is disclosed. The data bus arbitration system includes a bus status monitor which is coupled to a data bus and generates a bus status signal for use by an arbiter. The arbiter is coupled to number of requesters, each of which belong to a distinct class of requesters. The arbiter arbitrates between multiple requests using heuristics dependent upon the classes of the requesters. The arbiter grants access to one of the requestors to the data bus while maintaining an efficiency of at least 80% of a total data bandwidth of the data bus for all requesters. One of the distinct classes of requesters is preferably a real time class. The data bus arbitration system preferably includes a timer that provides an indication of when access to the data bus must be granted for a real time request.
In another embodiment of the present invention, a method for data bus arbitration is disclosed. The method includes monitoring a status of a data bus. A data bus request from a requestor belonging to a first class of requesters is first processed by a first heuristic method. The method then proceeds with second processing a data bus request from a requestor belonging to a second class of requestors by a second heuristic method. Access to the data bus is granted to a requestor based upon the status of the data bus, the first processing and the second processing, understanding that the first class of requestors is of a generally higher priority than the second class of requestors. The method preferably includes third processing a data bus request from a requester belonging to a third class of requesters by a third heuristic method, understanding that the second class of requesters is of a generally higher priority than the third class of requestors.
In yet another embodiment of the present invention, a method for data bus arbitration is disclosed. The method includes means for monitoring a status of a data bus. A data bus request from a requester belonging to a first class of requesters is processed by a first processing means using a first heuristic method. The method then proceeds with processing a data bus request using a second processing means from a requester belonging to a second class of requesters by a second heuristi

Affiliated with

Also associated with

Rating

Methods and apparatus for data bus arbitration 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 apparatus for data bus arbitration, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods and apparatus for data bus arbitration will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2878143