Electrical computers and digital data processing systems: input/ – Intrasystem connection – Bus access regulation
Reexamination Certificate
1999-04-15
2002-07-23
Lefkowitz, Sumati (Department: 2181)
Electrical computers and digital data processing systems: input/
Intrasystem connection
Bus access regulation
C710S116000, C710S118000
Reexamination Certificate
active
06425032
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to a bus controller or arbiter for controlling access to the bus of a computer system.
2. Description of the Related Art
Computers are becoming a more integral part of everyone's lives with each passing day. There is an ever-present demand for more efficient and faster-operating computers. The speed at which a computer operates is partially dependent on the rate at which data can be accessed by the different devices (e.g., disk drives, modems, etc.) attached to the computer.
Every computer includes a bus which serves as a conduit for the transfer of information between the central processing unit (CPU) of the computer and the various peripherals. Typically, the computer also includes a bus controller (often called an arbiter) for controlling which devices may access the bus, and in what order. A typical arbiter assigns priority values to each device depending on the requirements of the device. For instance, an interactive graphics adapter which is receiving video images over a modem or a network will have high priority because it must have access to the bus at all times, or valuable data will be lost. If the graphics adapter must wait to gain access to the CPU, the data which is transmitted during the waiting period may be lost. Such access interruptions can cause the video image being transmitted to appear jerky and unclear. A device such as a disk drive, however, is a relatively low priority device, since the data is stored in a tangible medium and can be re-accessed at any time.
FIG. 1
shows an exemplary prior art computer system
15
including a conventional arbiter
40
. It should be noted that the computer system
15
is merely one conventional way to implement a computer system with an arbiter, various other system configurations are known to those skilled in the art. A bus
10
having address, data and control information connects a CPU
20
with a memory
30
and the arbiter
40
. The bus
10
is also connected to various peripherals
50
,
60
(e.g., disk drives, CD-ROM drives, modems, etc.) which are used in conjunction with the computer system
15
. In the computer system
15
shown in
FIG. 1
, there are two peripherals
50
,
60
designated as “Device
1
” and “Device
2
”, respectively. Each peripheral
50
,
60
includes bus request lines R
1
, R
2
, bus grant lines G
1
, G
2
, and input/output (I/O) lines connected to the bus
10
destined for the arbiter
40
. When a peripheral (e.g.,
50
) requires access to the bus
10
, it sends out a signal on its bus request line (R
1
) to the arbiter
40
(via the bus
10
). The arbiter
40
includes circuitry (not shown) which decides if the request will be granted, and at what time. When the request is granted, the arbiter
40
sends out a “grant” signal, via the bus
10
, on the grant line (G
1
), letting the device (
50
) known that the bus
10
is ready to transfer or receive its information. The device (
50
) then transmits or receives the information over its associated I/O line. When transmitting information, the data travels from the device to the bus
10
, and then to the information receiver (e.g., CPU
20
). When receiving information, the data travels from the transmitter (e.g., CPU
20
), over the bus
10
and over the I/O line to the peripheral (in some cases, the CPU
20
itself may act as a peripheral). As stated above, most conventional arbiters assign priorities to each peripheral device based on the arbitration scheme and the general importance of the peripheral. For instance, if “Device
1
” (
FIG. 2
) were a audio sampling device such as a microphone, and “Device
2
” were a floppy disk drive, “Device
1
” would have a high priority because there is a higher likelihood of data loss. However, most conventional arbiters do not assign different arbitration schemes to periodic requests as opposed to aperiodic (i.e., one time) requests.
Some devices, such as CD-ROM drives, require periodic accessing of the bus. In other words, they need to access the bus many times (e.g., three times) over a specified time period (e.g., 10 &mgr;s). These devices are often referred to as periodic devices. Other examples of periodic devices include: modems and real-time video and audio samplers. The problem encountered with periodic devices is that in the time period between accesses, the bus controller may grant control of the bus to another device because it believes that the periodic device has completed its use of the bus. Therefore, each time the periodic device needs access to the bus it must make another request. Sometimes, if another device has already begun use of the bus, the periodic request may be den i ed by the arbiter, thereby slowing down the accessing process for the periodic device or causing the data transmitted to or from the periodic device to be delayed, queued or lost. The conventional process used for allowing periodic devices access to the computer bus is inefficient because the bus grant/request procedure may need to be repeated numerous times in a short period for the same periodic device.
Kelley et al., in U.S. Pat. No. 5,758,105, describe a method and apparatus for arbitrating periodic and aperiodic requests. The '105 patent describes an arbiter which contains two arbitration algorithms, one for periodic requests and one for aperiodic requests. The arbiter decides whether the device making the bus request is an aperiodic or a periodic device, and executes the proper algorithm accordingly. As can be seen from
FIG. 3
of the '105 patent, the arbiter assigns each device connected to the arbiter a certain amount of time on the bus depending upon the requirements of the device. The '105 patent does not describe the periodic bus allocation algorithm, nor does it discuss the effect of arbitrary device rates on the operation of the bus. When rates are arbitrary, no synchronous scheme can guarantee conflict free access to the bus for all devices for an indefinite period of time. Requests of two devices with arbitrary rates (not multiple of each other) will conflict at some time leading to queuing at one or both devices. The queuing of information introduces data delays into the system. The arbiter of the '105 patent does not take into account the queue length of each device trying to gain access to the bus and thus, is sub-optimal.
Accordingly, there is currently a need for bus controller that operates at very high speeds and that dynamically allocates space on a bus between both periodic and aperiodic devices, recognizes periodic devices and grants these devices control of the bus in a manner that minimizes data delays everywhere in the system by estimating queue lengths of the devices (or other performance metrics of interest).
SUMMARY OF THE INVENTION
The present invention is an arbiter which efficiently achieves controlled delays for all devices on the bus, whether periodic or aperiodic. The arbiter divides devices into two categories, periodic and aperiodic. When a request is made the information is relayed to a processor which decides whether to grant or deny the request. A service log located within the arbiter keeps track of important information relating to the requests, such as rate (for periodic requests), data transfer size, device queue length, etc. A time line memory located within the arbiter contains fixed sized entries of bus access service durations for the devices. The arbiter uses the queue length information to determine when a device should be granted access to the bus and uses the time line memory to allocate and grant bus service time to the device. For aperiodic requests, the arbiter consults the time line memory to locate an empty slot to service the request. For periodic requests, the arbiter uses information from the log in conjunction with the time line memory to allocate as many timeslots as it can until it detects a potential conflict (or other criteria are met). The arbiter uses these allocations to issue anticipatory grants to the requesting device. Thus, the arbiter
Dickstein Shaprio Morin & Oshinsky LLP
Lefkowitz Sumati
Lucent Technologies - Inc.
LandOfFree
Bus controller handling a dynamically changing mix of... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Bus controller handling a dynamically changing mix of..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Bus controller handling a dynamically changing mix of... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2899330