Arbitration scheme for optimal performance

Details Arbitration scheme for optimal performance Arbitration scheme for optimal performance

1999-10-05

2003-02-11

Dharia, Rupal (Department: 2781)

Electrical computers and digital data processing systems: input/

Intrasystem connection

Bus access regulation

C710S243000, C710S309000

Reexamination Certificate

active

06519666

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates in general to data communication systems, and in particular to high performance data communication systems having an optimized multi-master shared bus arbitration scheme.
2. Description of Related Art
Digital communication over a communication channel is well known in the art. Modern data communication systems often have multiple high performance data processors and generally include a plurality of external devices interconnected by one or more various buses. For example, modern computer systems typically include a host processor coupled through a high bandwidth local expansion bus, such as the peripheral component interconnect (PCI) bus or the VESA (Video Electronics Standard Association) VL bus, to an external shared memory, peripheral devices, and other processors. Examples of devices which can be coupled to local expansion buses include SCSI adapters, network interface cards, video adapters, etc.
High performance bus architectures, such as the PCI bus architecture, provide a hardware mechanism for transferring large sequential groups of data between a peripheral controller's local memory and a host processor's shared memory via burst cycles. In many bus architectures, the maximum burst length is typically not defined.
Systems in which many devices share a common resource typically utilize arrangements for allocating access to the resource under conditions during which a plurality of associated devices may concurrently request access. High performance systems have the potential to generate multiple independent requests for access to one or more external components, often via a single shared bus interface unit (BIU). Since multiple independent input/output (I/O) requests may appear at the BIU at any given time, the data communication system requires a shared bus arbitration scheme to determine the priority of the I/O requests for accessing the shared bus. In multi-master systems, where one or more data processors have the capability of becoming a bus master, the bus arbitration protocol determines which data processor becomes the bus master first. Typically, these multi-master systems employ an arbiter, external to the data processors, to control the shared bus arbitration, and each data processor requests access to an external shared memory or another external device from the arbiter.
Elaborate fairness algorithms have been devised that relieve the symptoms of hogging of the shared bus. Generally, multi-master systems depend on some sort of fairness arbitration protocol to prevent any one bus master from monopolizing the shared bus. A common arbitration scheme is least-recently-used (LRU) master scheme. A typical fairness protocol would limit each bus master to only one bus transaction, when the arbiter receives requests from multiple potential bus masters. Essentially, the arbiter would allow each master a turn in round-robin fashion. Automatic rotation of priorities when the interrupting devices are of equal priority is usually accomplished by rotating (circular shifting) the assigned priorities so that the most recently served device is assigned the lowest priority. In this way, accessibility to the shared resource tends to be statistically leveled for each of the competing devices.
Historically, arbitration devices have allocated access using a variety of predetermined hierarchies of priority. For example, some arbiters utilize a system in which access is a direct function of the order in which the requests are received from the external devices. Other systems incorporate priority levels for access, and each external device is assigned a particular priority value. Generally, existing arbitration schemes attempt to achieve a level of fairness appropriate to the particular system architecture, which insures that no one external device may dominate the resource, such as a shared bus, and thereby starve other external devices having lower priority levels.
For systems having lower performance objectives, a conventional priority scheme, such as round-robin scheme, might provide sufficient performance. However, high performance multi-master data communication systems, where various shared bus masters transfer long continuous burst transfers, as well as short burst messages, and perform register access transactions, require optimized performance, and need an improved arbiter priority algorithm. Usually, in such systems, the short message traffic on the bus should not be excessively delayed due to the long burst transfer activity.
Therefore, there is a need for an improved priority algorithm, in high performance multi-master data communication systems with multiple shared external devices, to insure that the system cannot lock the shared bus resource, and that the short burst messages and register access transactions on the shared bus are effectively processed between the long burst transfers.
SUMMARY OF THE INVENTION
The foregoing and other objects, features, and advantages of the present invention will be apparent from the following detailed description of the preferred embodiments which makes reference to several drawing figures.
One preferred embodiment of the present invention includes a shared bus master arbitration circuitry, utilized in a data communication system, for allocating access to a shared bus connected to a plurality of data processing devices and resources, where the shared bus is located between a higher-priority system resource, a lower-priority system resource, and a peripheral device. The system utilizes a shared bus arbiter for dynamically determining the highest priority request between a number of shared bus requests and granting control of the shared bus to the highest priority request.
Another preferred embodiment of the present invention includes a shared bus arbitration scheme for a data communication system, where a shared bus is connected to a plurality of bus masters and resources, some resources having higher priority than the others and including a peripheral device. Each master may request control of the shared bus and is adapted to perform short transfers and long burst transfers on the shared bus between a resource and the master. A shared bus arbiter is utilized for dynamically determining the highest priority request between a number of shared bus requests, and granting control of the shared bus to the highest priority requesting bus master.
In all the embodiments of the present invention the arbiter utilizes a three-level priority hierarchy arbitration scheme where the highest priority level is given to short message transfer requests on the higher-priority system resources, the intermediate priority level is given to short message transfer requests on the lower-priority system resources, if there are no outstanding higher priority level requests, and the lowest priority level is given for long burst transfers, if there are no outstanding short message transfer requests. The short message transfers include short burst transfers and register access transactions. If there are simultaneously several requests with the same priority level, the same-priority level requests are serviced in the next arbitration cycle in round robin fashion.
The bus arbiter postpones the lower level requests for a pre-determined delay period, for allowing all higher level operations queued by the same requester to execute before the shared bus control is given to any lower priority requester, and for preventing a lower priority level transaction from intervening between consecutive higher priority level transactions from the same requester. The pre-determined delay period is about one clock cycle greater than the maximum time required for the same requester to re-assert its shared bus request for the next short message transfer. The higher-priority system resource includes at least one component from a processor-shared memory subsystem connected to the shared bus via an external or internal bus, and the lower-priority system resource is selected from a plurality of interfaced s

Affiliated with

Also associated with

Rating

Arbitration scheme for optimal performance does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Arbitration scheme for optimal performance, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Arbitration scheme for optimal performance will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3169115