Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Positional Bus Arbitration Scheme

IP.com Disclosure Number: IPCOM000107508D
Original Publication Date: 1992-Mar-01
Included in the Prior Art Database: 2005-Mar-21
Document File: 5 page(s) / 194K

Publishing Venue

IBM

Related People

Elkins, GV: AUTHOR [+3]

Abstract

For a system with adapters connected by a common bus, a decision process is required to choose the next adapter that will use the bus. The requirements for the decision process are as follows: - Arbitration decision must be made fast, preferably within one clock cycle. - Working hardware must be available within one year. - Must be implemented with a redundancy scheme for providing some fault tolerance. - Worst case delay for bus ownership must be no more than one full cycle of all eight participants. This article describes an arbitration scheme that combines positional hierarchy with a masking scheme to meet all of the stated requirements.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 37% of the total text.

Positional Bus Arbitration Scheme

       For a system with adapters connected by a common bus, a
decision process is required to choose the next adapter that will use
the bus.  The requirements for the decision process are as follows:
-    Arbitration decision must be made fast, preferably within one
clock cycle.
-    Working hardware must be available within one year.
-    Must be implemented with a redundancy scheme for providing some
fault tolerance.
-    Worst case delay for bus ownership must be no more than one full
cycle of all eight participants.
This article describes an arbitration scheme that combines positional
hierarchy with a masking scheme to meet all of the stated
requirements.

      As shown in Fig. 1, any system that has multiple adapters
sharing a common data bus requires an arbiter.  The arbiter's primary
responsibility is to choose the next adapter that will transmit data
onto the shared bus.  The decision to choose the next adapter must be
fair (giving all adapters an opportunity to use the bus) and quick
(any bus cycles consumed by the arbitration decision process are
wasted).

      A new method was invented that combines positional priority
with a masking method.  Positional encoder logic yields a single
"true" output to the most (or least) significant "true" valued input.
Once a turn is taken by an adapter, that adapter is blocked from
taking another turn until all other adapters have had an opportunity
to use the bus.  The blocking is accomplished by setting a mask bit
to 'O' in the mask register.  When an 'O' occurs for position "X",
the "Xth" input to the positional encoder logic is forced "false".
When there are no valid inputs to the encoder logic, the mask
register is reset to all '1s' (i.e., every adapter with a valid
request has had a turn to use the bus).

      The maximum delay time from adapter request to bus ownership is
controlled by limiting each adapter's turn on the bus to a transfer
of one bundle of data.  The maximum amount of data that can be
transferred is 4,096 bytes, or 512 cycles on an 8 byte bus.  Thus,
the maximum delay from request to ownership is approximately 512
cycles times n-1 (excluding clock cycles consumed during the
arbitration process).  For an eight adapter system, the maximum delay
is about 512 cycles times 7, or near 3600 clock cycles.

      As shown in Fig. 2, this method employs five basic elements.
Requests from the adapters are captured off the shared bus (see Fig.
1) into the request block.  These requests are compared to a mask,
which is initialized such that all requests are unmasked.  The
compare block then presents unmasked requests to the priority
encoder.  The encoder logic sets priority based on pin definition
with input 7 having the highest priority and input 0 the lowest.  The
encoder logic then selects the highest priority input, which becomes
a positional grant on the shared bus.  The encoder output also goes
to...