Enhanced bus arbiter utilizing variable priority and fairness

Details Enhanced bus arbiter utilizing variable priority and fairness Enhanced bus arbiter utilizing variable priority and fairness

1999-07-29

2004-04-06

Lefkowitz, Sumati (Department: 2833)

Electrical computers and digital data processing systems: input/

Intrasystem connection

Bus interface architecture

C710S240000, C710S244000

Reexamination Certificate

active

06718422

ABSTRACT:

TECHNICAL FIELD
The present invention relates in general to a method and system for data processing in general and, in particular, to a method and system for bus arbitration based on variable priority and fairness protocols.
BACKGROUND INFORMATION
A computer system typically includes several types of buses, such as system bus, local buses, and peripheral buses. Various electronic circuit devices and components are connected with each other via these buses such that intercommunication may be possible among all of these devices and components.
In general, a central processing unit (CPU) is attached to a system bus, over which the CPU communicates directly with a system memory that is also attached to the system bus. A local bus is intended for connecting certain highly integrated peripheral components on the same bus as the CPU. One such local bus is known as the Peripheral Component Interconnect (PCI) bus. Under the PCI local bus standard, peripheral components can directly connect to a PCI local bus without the need for glue logic. Thus, PCI provides a bus standard on which high-performance peripheral devices, such as graphics devices and hard disk drives, can be coupled to the CPU, thereby permitting these high-performance peripheral devices to avoid the general access latency and the bandwidth constraints that are associated with a peripheral bus. A peripheral bus such as an Industry Standard Architecture (ISA) bus, is for connecting various peripheral devices to the computer system. These peripheral devices typically include input/output (I/O) devices such as a keyboard, floppy drives, and printers.
Generally, each system bus, local bus, and peripheral bus utilizes an independent set of protocols (or rules) to conduct data transfers between various devices attached to it. Each of these protocols is designed into a bus directly and is commonly referred to as the “architecture” of the bus. In a data transfer between different bus architectures, data being transferred from the first bus architecture may not be in a form that is usable or intelligible by the receiving second bus architecture. Accordingly, a mechanism is developed for “translating” data that are required to be transferred from one bus architecture to another. This translation mechanism is normally contained in a hardware device in the form of a bus-to-bus bridge (or interface) through which the two different types of buses are connected.
Incidentally, various bus-to-bus bridges have been designed to match the communication protocol of one bus with that of another in order to permit system-wide communications between devices on different buses. For example, a bus-to-bus bridge connecting between a system bus and a PCI local bus is called a PCI host bridge. The PCI host bridge contains all the logic and hardware for translating data communications between the system bus and the PCI local bus, and ensures that data is transferred between these two buses intelligibly.
If multiple devices connected to the different buses gained access to the CPU or even a local bus at the same time, chaos would result. Chaos is avoided by introducing one or more bus masters into the system. A bus master controls access to the bus. In other words, it initiates and controls all bus requests.
Deciding which device or bus master to use the bus next is called bus arbitration. In a bus arbitration scheme, a device (or the processor) wanting to use the bus signals a bus request. In response, at a later point in time the arbiter sends a grant signal to the device. After the grant is received, the device can use the bus. The device later signals to the arbiter that the bus is no longer required. The arbiter can then grant the bus to another device.
Arbitration schemes usually try to balance two factors in choosing which device to grant the bus. First, each device has a bus priority, and the highest-priority devices should be serviced first. Second, to assure that no device, even with low priority, is never completely locked out, most I/O buses such as PCI also require that the arbiter implement some kind of fairness protocol. The intent of a fairness protocol is to assure that all devices receive a turn on the bus. For instance, one conventional fairness protocol is a round robin scheme. Under a round robin fairness protocol, a device which has just completed a bus operation is not granted access to the bus for a second operation until all the requesting devices have first been granted access to the bus.
Even though a bus may provide a fairness protocol in the arbiter(s) that control access to the bus, acceptable access to the bus can be effectively denied to a device or devices by other high performance devices. This is an unexpected problem that fairness protocols were intended to avoid. The problem is that of “beat” frequencies that interfere with a device's access to the bus. The concept of this “beat” frequency will be described below.
Some buses such as PCI provide a performance feature usually referred to as “backoff” capability that allows a device to disconnect from the bus if it is not able to handle the request at that time. This capability in PCI is referred to as Retry. If a PCI device is not able to handle a request when it occurs the target of the request can issue a “Retry” which indicates to the master that issued the request on the bus to try again later.
For PCI, the typical platform provides a PCI host bridge to provide bus synchronization between the system bus and the PCI bus. The platform may also provide a number of PCI-to-PCI bus bridges to provide additional PCI bus segments. Usually each PCI bus segment will have its own arbiter (with fairness protocol). Each bridge usually has posting buffers for temporary buffering of bus transactions as these transactions flow through the bridge in both directions (primary side to secondary side, and secondary side to primary of a bridge).
The way a beat frequency can deny a device effective access to the bus involves interaction between the set of buffers in a bridge, the bridge arbiter, and the bus traffic by devices on the bus. For example, assume a bus under a PCI host bridge or PCI-to-PCI bridge has a round-robin fairness protocol to four devices under the bridge (Device A, Device B, Device C, and Device D). Also assume the bridge is assigned the highest priority (priority 0), Device A is assigned the next highest priority (priority 1), Device B is assigned the next highest priority (priority 2), Device C is assigned the next highest priority (priority 3), and Device D is assigned the next highest priority (priority 4). If all devices ask for the bus at the same time, the fairness protocol will assure that each devices get a chance to try to utilize the bus. The arbitration priority, in this example, simply determines the order in which the devices get a turn to try to utilize the bus. In this example when all devices request use of the bus, the bridge is granted first access, then Devices A to D in sequence. Under this scheme, both Device A and B could get a turn on the bus and fill up the bridge's buffers such that when Device C gets on the bus, Device C gets a Retry because the bridge's buffers are full. Eventually, the bridge empties out some of the buffers as transactions on the other side of the bridge. Then Devices D, A and B get turns on the bus, again filling the buffers. When Device C gets its rotating turn on the bus again, it again receives a Retry because the bridge's buffers are full again. A beat frequency can occur such that each time a specific device gets a turn on the bus it is turned away with a Retry (or equivalent, depending on the bus type) because other devices keep filling up the bridge buffers. When the number of Retries are relatively high, the device can overrun or underrun resulting in significant performance losses from software detecting the overrun or underrun and repeating the operation.
Simply adding more buffers to the bridge only changes the amount of data that Devices A, B, and D need to transfer to produce the “beat”

Affiliated with

Also associated with

Rating

Enhanced bus arbiter utilizing variable priority and fairness does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Enhanced bus arbiter utilizing variable priority and fairness, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Enhanced bus arbiter utilizing variable priority and fairness will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3211560