Electrical computers and digital data processing systems: input/ – Intrasystem connection – Bus interface architecture
Reexamination Certificate
2000-03-28
2004-02-24
Ray, Gopal C. (Department: 2181)
Electrical computers and digital data processing systems: input/
Intrasystem connection
Bus interface architecture
C710S310000, C710S306000, C710S106000, C710S107000, C710S113000, C710S240000, C710S241000, C709S235000, C370S229000
Reexamination Certificate
active
06697904
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The invention pertains generally to computers. In particular, it pertains to arbitrating data transfers on a computer bus.
2. Description of the Related Art
Modern computer systems may use a variety of buses to transfer data from one device to another. As seen in
FIG. 1
, a computer system
1
may include a local bus
5
to transfer data to/from a central processing unit (CPU)
2
, a memory bus
6
to transfer data to/from a main memory
4
, and a Peripheral Computer Interconnect (PCI) bus
7
to transfer data to/from any of multiple adapters
11
-
16
. The system may also include a bridge
3
to permit transferring data between devices on two different buses.
PCI bus systems are a well-known, industry-standardized approach for transferring data within a computer system. As with many bus systems, a device wishing to initiate a transfer between itself and another device must request and be granted the exclusive use of the bus for a period of time. Since more than one device may request the bus at the same time, an arbiter is necessary to determine which requester will be granted immediate use of the bus and which requestors must wait.
FIG. 2
illustrates one such system, in which the various adapters
11
-
16
of
FIG. 1
are shown generically as PCI agents
21
-
26
. Any agent wishing to use the PCI bus places a request signal on its respective REQ line to arbiter
27
. If two or more agents are requesting the bus at the same time, arbiter
27
will choose one of those requesters by placing a grant signal on the GNT line to that requester. When the granted device has finished with the bus, another arbitration determines which of multiple requesters will be granted access next. When a requester is given control of the bus its target device (the device with which the requester wishes to communicate data) may not be able to accept a data transfer. If not, the requestor will receive a retry indication from the target and must relinquish the bus. The requestor retries by sending another request signal to arbiter
27
.
Various techniques have been developed to perform this arbitration in arbiter
27
, such as first-come first-serve, hierarchical, and round robin, all of which are well known.
FIG. 3
illustrates the round robin, or rotating, method of arbitration in a system with six PCI agents that can potentially request the PCI bus at any time. The arbiter scans the request lines from PCI agents PA
0
-PA
5
by continuously examining the request lines in circular order, looking for a request signal on each line. When it detects a request signal, it stops scanning, grants bus access to the associated device by issuing a grant signal to that device, and subsequently resumes scanning. This technique gives equal priority to all requesters, since every device is given a chance to request the bus in every scan cycle.
The conventional location for arbiter
27
is in bridge
3
, which also includes a first-in first-out buffer (FIFO) to buffer the data as it is transferred between a device on the PCI bus and a device on one of the other buses, typically the memory bus. Any PCI device making a write transfer to a target device on another bus can transfer the data to this FIFO, and the data is then transferred from the FIFO to the target device. Depending on the volume of data being transferred and the size of the FIFO, the FIFO may become full, so that any further data transfer would overrun the FIFO and cause corruption of the data. To prevent this, when the FIFO becomes full, any further data transmission into the FIFO is halted until more data has been removed from the FIFO by the receiving device. In a typical system, if the FIFO becomes full in mid-transfer, the FIFO will send a STOP indication to the transmitting device. The transmitting device will then stop the transfer, relinquish the bus, and subsequently make another bus request to resume the transfer when it is again granted the bus. By the same token, if a requesting device is granted access to the bus but the FIFO is already full, the requestor will receive a STOP indication from the FIFO before any data is transferred. As before, it must drop the request, relinquish the bus and retry later. In a conventional round robin arbiter, these conditions can create a situation called starvation, in which one requestor is repeatedly denied access while another requester is repeatedly granted access. For example, if device A requests and is granted the bus, it can transfer enough data to fill up the FIFO before terminating the transfer. If device B is then granted the bus while the FIFO is still full, it will receive a retry response and must drop the request. As the next requesting device in the rotation, device A may request and be granted the bus again. The FIFO has by then had time to free up some space, which device A proceeds to fill up again. Device B will then get another chance to request access, and will again receive a retry, since the buffer is by now full again. In this manner, device A will be granted access every time it makes a bus request, while device B will never be granted access until device A has completed all transfers. This defeats the purpose of rotating priority, which is to give every device equal access to the bus.
SUMMARY OF THE INVENTION
An embodiment of the invention includes arbitration logic to repetitively scan first and second bus request lines. The arbitration logic has a first input coupled to the first request line to receive a first request signal, a first output to provide a first grant signal in response to receiving the first request signal, a second input coupled to the second request line to receive a second request signal, a second output to provide a second grant signal in response to receiving the second request signal, and a third input to receive a buffer full signal. The arbitration logic also includes control logic coupled to the first, second, and third inputs to pause the scan in response to receiving the buffer full signal.
REFERENCES:
patent: 4298954 (1981-11-01), Bigelow et al.
patent: 4933840 (1990-06-01), Sera et al.
patent: 4953081 (1990-08-01), Feal et al.
patent: 5276681 (1994-01-01), Tobagi et al.
patent: 5291459 (1994-03-01), Andersen
patent: 5305446 (1994-04-01), Leach et al.
patent: 5365552 (1994-11-01), Astle
patent: 5410652 (1995-04-01), Leach et al.
patent: 5440691 (1995-08-01), Carrafiello et al.
patent: 5448701 (1995-09-01), Metz et al.
patent: 5535341 (1996-07-01), Shah et al.
patent: 5546543 (1996-08-01), Yang et al.
patent: 5956489 (1999-09-01), San Andres et al.
patent: 6073132 (2000-06-01), Gehman
M. Morris Mano, Computer System Architecture, 1982, Prentice-Hall, Inc., 2nd edition, pp. 26-35.
Intel Corporation
King Justin
Ray Gopal C.
Travis John F.
LandOfFree
Preventing starvation of agents on a bus bridge does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Preventing starvation of agents on a bus bridge, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Preventing starvation of agents on a bus bridge will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3289878