Note: Descriptions are shown in the official language in which they were submitted.
WO91/10957 PCT/US91/003~3
-- 1 --
20~0821
ARBIT~ATION AMONG MULTIPLE U~RS OF
~59~
Backaround o~ ~h~Invention
The present invention relates in general to
arbitration among users of a shared resource, such as a
digital data bus, for access to the resource.
Users that share a data bus, such as PC boards
connected by a common backplane within a system, typically
compete for use of the data bus by participating in some
form of arbitration. In one known arbitration scheme, each
user having data to send on the shared data bus applies an
arbitration signal to a wired-OR arbitration bus, and
subsequently checks the resultant signal on the arbitration
bus. If the resultant signal corresponds to that expected
by the user, then that user wins the use of the shared data
bus and is permitted to tra~sfer a data message over it.
Some arbitration schemes include a series of signal
matching cycles, where the ultimate winner of the data bus
is the user for which the resultant signal on the
arbitration bus matches the expected signal in each of the
cycles.
Such arbitration procedures generally require some
form of synchronization between the users. Typically,
synchronization is provided by having the users time the
arbitration based on a system clock that simultaneously
drives all users. Another alternative is to select one
user to serve as a "master" during arbitration and have
that user supply arbitration timing for all users. A third
alternative is to synchronize the clocks by, for example,
phase locking the individual user clocks. Propagation and
other delays among a large number of users complicates
clock synchronization among the users, and limits the
maximum usable clock frequency,~and thus the speed of the
arbitration cycles and subsequent data bus transfers.
WO 91/10957 PCT/US91/00323
,
~ 2 -
It is also known to award priority to users in the
arbitration based on whether the users have previously been
denied access, to promote fair allocation of the shared ,
resource among the users.
~
~u-mmary of the Inven~ion
A general aspect of the invention is arbitrating among
a plurality of users for access to a shared resource in a
system of the mind in which the users arbitrate by placing
arbitration signals on a line and subsequently comparing
their arbitration signals with a signal appearing on the
line, by providing the users with independently operating
clocks, and controlling the progression of the arbitration
based on timing provided by the clock of at least one of
the users.
Preferred embodiments include the following features.
At least one user is allowed to cause itself and other
users to place the arbitration signals on the line and
perform the comparison at times governed by the clock of
the at least one user. Each user that arbitrates for the
resource is capable of transmitting a first control signal
at a time governed by the clock of that user to inform
other users that it will place its arbitration signal on
the line, and an arbitrating user refrains from
transmitting the first control signal if it has already
received the first control signal from another arbitratinq
user. An arbitrating user places its arbitration signal on~
the line when it either generates or receives the first
control signal.
Due to, for example, propagation delays, an
arbitrating user may successively receive multiple first
control signals, but the arbitrating user is permitted to
respond only-to the first such control signal that the user
receives. Each user that transmits the first control
signal does so by asserting a pulse on a first cohtrol line
(e.g., a wired-OR line connected between the users), and
.......... ~ . .... .... . . .
WO 91/10957 P~T/US91/Q0323
. . _ 3 _ 2070821
the arbitrating users respond to a single edge (such as the
undriven to driven edge) of the pulse.
Each user that arbitrates for the resource is also
capable of transmitting a second control signal to cause
itself and other users to perform the comparison, and an
arbitrating user refrains from transmitting the second
control signal if it has already received the second
control signal from another arbitrating user. A user
performs the comparison when it either generates or
receives the second control signal. An arbitrating user
may successively receive multiple second control signals
from multiple users (because of propagation delays between
the users), but the user is permitted to respond only to
the first such control signal that the user receives. The
second control signal is a pulse asserted on a second
control line, such as a wired-OR line connected between the
users, and the arbitrating users respond to a single edge
(e.g., the undriven to driven edge) of the pulse.
The arbitrating users count a predetermined number of
clock pulses generated by their clocks after they receive
or generate the first control signal; after reaching the
predetermined number, a user transmits the second control
signal if that user has not yet received the second control
signal from another user. To prevent the time interval
between the first and second control signals from
decreasing for successive arbitrations, the predetermined
number is different ~e.g;, one clock pulse less) for users
that generate the first control signal than for users that
receive the first control signal. An arbitrating user
performs the comparison when it either generates or
receives the.second control signal and.determines the
result of the arbitration based on results of this
~ comparison. The.user that wins the arbitration for.the
. . .shared resource (e.g., a data.bus) is permitted access to
the resource to, for example, transmit data over the bus.
WO 91/10957 ~ PCT/US91/00323
~ 4 -
Preferably, the arbitration includes a predetermined
number of cycles in each of which at least one arbitrating
user places its arbitration signal on the line and
subsequently compares its arbitration signal with a signal
appearing on the line to determine the result of the
arbitration, and the progression'of the arbitration within
each cycle and from a first cycle to a subsequent cycle is
controlled based on timing provided by the clock of at
least one of the users. Each arbitrating user determines
whether to proceed from one cycle to a second cycle based
on results of the comparison made in the first cycle, and
only one arbitrating user makes a determination to proceed
in the final one of the cycles; such user is granted access
to the shared resource. The clock that provides such
timing may be that of different users in different cycles.
Each user that arbitrates for the resource is capable
of transmitting a first control signal in each cycle at a
time governed by the clock of that user to inform other
users that it will place its arbitration signal on the
line; a user refrains from transmitting the first control
signal if it has received a first control signal from
another user, and an arbitrating user places its
arbitration signal on the line when it either generates or
receives the first control signal. Each user that
arbitrates for the resource is capable of transmitting a
second control signal in each cycle to cause itself and
other users to perform the comparison; an arbitrating user
refrains from transmitting the second control signal if it
has received a second control signal from another user; an
arbitrating user performs the comparison when it either
generates or receives the second control signal.
~ Each arbitrating user counts in each arbitration cycle
a predetermined number of clock cycles generated by^its
clock after it receives or generates the first control
signaL and, after the predetermined number is reached, the
user transmits the second control signal if it has not yet
.. . .. .. . . . . . . ..
WO91/10957 PCT/US91/00323
~ 5 ~ 2070821
received the second control signal from another user. The
.
- - transmission of the second control signal serves to start a
- second cycle of the arbitration and cause each user that
has determined to proceed in the arbitration to place its
arbitration signal on the line. Each arbitrating user that
receives or generates.the second control signal then counts
a predetermined number of its clock cycles and, after the
predetermined number is reached, transmits a third control
signal if the user has not received the third control
signal from another user. The arbitrating users each
perform the comparison when they either generate or receive
the third control signal, and determine a result of the
second cycle of the arbitration based on this comparison.
The transmission of the third control signal also
serves to start a third cycle in the arbitration and cause
each user that has determined to proceed in the arbitration
to place an arbitration signal on the line. Each
arbitrating user that receives or generates the third
control signal counts a predetermined number of cycles of
its clock and, after reaching the predetermined number,
transmits a fourth control signal if the user has not
received the fourth control signal from another user. The
arbitrating users each perform the comparison when they
either generate or receive the fourth control signal and
determine a result of the third cycle of the arbitration
based on the comparison.
There may be any number of arbitration cycles. In one
embodiment, there are three cycles and the fourth control
signal serves to start a subsequent arbitration. In
another embodiment, there are more than three cycles and
the fourth control signal serves to start the fourth cycle
in the arbitration.
. - Preferably, the arbitration process includes multiple
.arbitrations, successively performed, and the:progression
of each arbitration and progression from one arbitration to
a second arbitration is controlled based on timing provided
WO 91/10957 PCT/US91/00323
~ 6 -
by the clock of at least one of the plurality of users.
The clock that provides the timing may be that of different
users for different arbitrations. Each user checks the
arbitration line at the conclusion of an arbitration and
does not proceed to the next arbitration if the line is
idle. At least one user in each arbitration determines
itself the winner of the arbitration based on the
comparisons that are made, and that user is allowed access
to the resource. The winning user signals other users if
it detects that another arbitration is occurring while the
winning user is using the resource, and the winning user
releases this signal when it has finished using the
resource. The users to suspend arbitration while the
signal from the winning user is pending and resume
arbitration when the signal is released.
Where the shared resource is a data path, the path
preferably comprises a bus that includes multiple data
lines; the winning user transmits a strobe and data to at
least one destination user over a portion of the data lines
using a common driver, and the destination users receive
the strobe and data over that portion of said data lines
via a common receiver, whereby skew between the data and
said strobe i~ reduced.
Each destination user sends a first signal to the
winning user at a first predetermined time after the
destination user begins to receive the data, and the
destination user sends a second signal after a second
predetermined time interval (both of which times are
determined by counting a predetermined number of cycles of
its clock) if the destination user determines that correct
data was received. The winning user monitors the signal
from the destination user (or users) and determines that an
error has occurred if the winning user does not observe the
second signal within a predetermined time (also determined
by counting a predetermined number of cycles of its clock).
The first and second signals are sent over a wired-OR line
WO 91/10957 PCT/US91/00323
- 7 - 2070821
having an undriven state interconnected between ~he users;
the first signal comprises asserting this line to a driven
state, and the second signal comprises releasing said line
to the undriven state.
The progression of the arbitration does not depend
upon a single master clock, or upon synchronizing the
individual user clocks. The users perform the arbitration
using their independent clocks, which should be (but need
not be) at approximately the same frequency. The
arbitration technique is thus extremely fault tolerant--a
malfunction of one user's clock affects only that user,
while the remaining users are free to proceed with the
arbitration using their independent clocks--compared with
prior schemes in which arbitration timing was furnished by
a system clock or by the clock of one "master" user. Also,
because no one user serves as the "master" during
arbitration, there is no need to initially determine which
user will function as the master and thus, at least
initially, supply arbitration timing for the other users.
Nor must failures of such a master user be dealt with
(e.g., by choosing another user to serve as the master).
Another general aspect of the invention is arbitrating
among a plurality of users for access to a shared resource
in a system of the kind in which each user arbitrates for
access by placing an arbitration signal on a path
interconnecting the users and subsequently comparing its
arbitration signal with a signal appearing on the path to
determine if the user has won the arbitration, by assigning
a first priority to each user that requests access in the
arbitration based at least on an access priority
preassigned to the request for access and on whether the
user is a member of a current group of users-that is formed
at a time during the arbitration-when another group of
users is empty, the current group including users that have
been denied access as of that time; at least a portion of
each user's arbitration signal is arranged as a multibit
,. . ,. ..... ,.. ,...... i
WO 91/109~7 PCT/US91/00323
~,~ Q~ ~S~ ~ - 8 - '~
word having a value that represents the first priority, and
each user that arbitrates for access places its multibit
word in parallel on the path and determines whether it has
won the arbitration by subsequently comparing its multibit
word value with the value of a multibit word that appears
on the path.
Preferred embodiments include the following features.
Each user's multibit word is arranged to have a value
such that users belonging to the current group will have a
higher first priority in the arbitration than users that
have the same preassigned priori,ty but that are not members
of the current group. This assures (within a subset of
users whose access requests have the same preassigned
priority) that users previously denied access will be
served before later-requesting users.
The arbitration comprises a predetermined number of
cycles, with each user that arbitrates in a first one of
the cycles determining whether to proceed to arbitrate in
the next cycle based on results of the comparison made in
the first cycle; each user that proceeds to arbitrate in
the next cycIe places a second multibit word in parallel on
the path and repeats the comparing and determining steps.
Each user's second multibit word may be different from the
multibit word produced by that user during the first cycle.
In one embodiment, during at least one of the cycles, each
user places on the path a multibit word that represents an
identification of the user in the system and has a value
that represents a second preassigned access priority
related to the identification. These multibit words are
preferably binary words arranged to have marching ones
values according to the respective identification of the
users; ,-In,one embodiment, each user's multibit word that
represents,identification has a value based at -least in , -
' , part on whether'the user is a member-of the current group'.
The invention provides a fast and effective means'of
controlling the allocation of the shared resource among the
..... .. ..... I
WO 91/10957 PCT/US91tO0323
- 9 20708Zl; `
users. This allows a large number of users, aSynChrOnOus
to one another, to use the resource.
Other features and advantages of the invention may
become apparent from the following detailed description and
from the claims.
pescri~tion o~ the Preferred Embodiments
A brief description of the drawings is as follows.
Fig. 1 i9 a block diagram of a digital system in which
multiple users arbitrate for use of a common data bus.
Fig. 2 is a timing diagram showing sequences of
arbitration, data transfer, and ratification in the system
of Fig. 1.
Fig. 3a, 3b, 3c and 3d are flow charts showing the
sequence of events during arbitration among users for the
data bus of Fig. 1.
Fig. 4 is a timing diagram showing a 3-cycle
arbitration tournament among users of Fig. 1.
Fig. 5 is a timing diagram showing how arbitration
timing may change, from one tournament to the next.
Fig. 6 is a timing diagram showing idle time between
the arbitration tournaments of Fig. 4~
Fig. 7 is a timing diagram showing the suspension of
successive arbitration tournaments of Fig. 4.
Fig. 8 shows an assignment of arbitration code bits
corresponding to a 3-cycle, 5-wire, 2-priority arbitration
tournament of Fig. 4.
Fig. 9 shows the first cycle of each of seven
tournaments of the 3-cycle, 5-wire, 2-priority tournament
of Fig. 8.
Fig. 10 illustrates an arbitration address code
assignment among the users of Fig. 1 for the 3-cycle, 5-
wire, 2-priority tournament of Fig. 4.
: Fig. 11 is a timing diagram showing the sequence of
events for a data transfer over the data bus of Fig. 1.
WO 91/10957 PCT/US91/00323
Fig. 12 is a timing diagram showing the passing of
data bus control among sequential users of the data bus of
.
Fig. 1.
Figs. 13 and 14 are timing diagrams showing the data
ratify protocol used with data transfers over the data bus
of Fig. 1.
Fig. 15 is a timing diagram showing the ratify
protocol timing of Figs. 13 and 14 between sequential users
of the data bus of Fig. 1.
Fig. 16 is a chart showing a possible assignment of
arbitration code bits corresponding to a 4-cycle, 3-wire,
2-priority arbi~ration tournament.
Fig. 17 depicts an arbitration address code assignment
among the users of Fig. 1 for the 4-cycle, 3-wire, 2-
priority arbitration tournament of Fig. 16.
Fig. 18 is a timing diagram of the 4-cycle arbitration
tournament of Fig. 16.
Fig. 19 is a timing diagram illustrating the
suspension of successive arbitration tournaments of Fig.
18.
S~us~ and OperatiQn
Referring to Fig. 1, a digital system 10 includes
multiple users 12a - 12n, which, for example, are PC
(printed circuit) boards disposed in a cardcage 11 and
which communicate via a backplane 13. Digital system 10
employs arbitration and synchronization ~discussed in
detail below) among its users for access to a shared data
bus 14 in the backplane. Data bus 14 is a multi-line bus
comprising data lines (D0 - D7), data strobes lines (STROBE
A, STROBE B), a data ratify line (RATIFY), and a data frame
line (FRAME). Digital data is transferred between users
12a - 12n over the data bus 14 in the form of data packets,
as discussed below. ~
Data is sent by an individual user 12 a - 12n ovër
data bus 14 after that user has gained access to the data
WO91/10~57 PCT/US91/00323
- 11 -2070821
bus by means of arbitration with the other users 12 a -
12n. Arbitration takes place in a "tournament" which
comprises a series of arbitration cycles. Only a single
user 12a - 12n will survive all the arbitration cycles in a
given tournament to become the "winner" of that tournament,
and thereby becomes the next user in line to access the
data bus 14 and send its data packet.
Arbitration bus 16 is a multi-line digital bus running
between all users 12a - 12n. Each line of the arbitration
bus 16 (ARBDATA0 through ARBDATA4) is driven by the users
12a - 12n as a wire-ORed data bit, allowing each
arbitrating user to assert an individual multi-bit
- arbitration code ~ARB CODE) on the bus, as described below.
Thus, a single resultant multi-bit arbitration (ARBDATA)
code appears on the arbitration bus 16 dependent on the
bit-wise wired-OR relationship of all asserted user
arbitration codes.
Sync bus 19 is a multi-line digital synchronization
control bus carrying arbitration synchronization
information between all users 12a - 12n. Each line of sync
bus 19 ~ARBSYNC1, ARBSYNC2 and ARBSYNC3) is driven by the
users as a wired-OR control signal, allowing more than one
user to simultaneously assert the same sync bus line. Each
sync bus line carries an arbitration synchronization signal
used to synchronize and control the users' assertion and
readback o~ arbitration codes on arbitration bus 16, as
described below.
Each user 12a - 12n contains its own internal user
clock 18. The user clocks 18 are independent and
plesiosynchronous--they are very close to a predetermined
frequency but are not synchronized with each other or with
a system clock over a bus between the clocks. Each user
12a - 12n bases its arbitration cycle timing on its own
internal clock 18, with synchronization between users
occurring only by means of the sync bus l9 signals.
Similarly, data transfer timing is synchronized between
'"''' '''.
WO 91/10957 PCT/US91/00323
~ ~ ~ 12 -
users by means of the data strobe signal lines (i.e.,
STROBE A and ST~OBE B) of data bus I4.
Each user has a pair of send buffer circuits 20 and 21
that receive data from the users' functional circuit 24,
which, for instance, may be a microprocessor, signal
processor, or other electronic circuit. Send buffer
circuits 20 and 21 each constructs data packets comprising
the data to be transferred from the user's functional
circuit 24 to a destination user and the address of the
destination user. Additionally, each send buffer 20, 21
assigns its priority to each packet as determined by the
functional circuit's decision to route the data to that
particular send buffer. Send buffer 20 assigns each packet
a high priority "P1" status, while send buffer 21 assigns
each packet a low priority "P2" status. Once packet
construction is completed, send buffer 20 or 21 signals its
arbitration controller 17 to begin arbitrating for the data
bus 14. In response, arbitration controller 17 enters
arbitration for the data bus 14 with the other users 12a -
12n that also have data packets ready to send. Arbitrationproceeds as described below until each user 12a - 12n with
data to send has accessed data bus 14 and sent its data.
~ ach user 12a - 12n continually monitors data bus 14
and responds to recognition of its own address in a
transmitted data paclcet on the data bus by accepting thé
packet and asserting the data bus 14 data ratify line, as
discussed below. The receiving target user routes the
accepted data packet to either of its receive buffers 22 or
23 as determined by the packet's P1 or P2 priority status.
Receive buffer 22 accepts Pl priority packets, while
receive buffer 23 accepts P2 priority packets. The :`
received data is used by the user's functional circuit 24
as required. :
Referring to Fig. 2,~a sequence of overlapping events
(arbitration, data transfer and ratification) is shown for
five data packet transfers between users 12a - 12n. In
WO 91/10957 PCT/US91/00323
- 13 - 20708-~1
general, a data packet transfer over data bus 14 involves
three phases: arbitration, data transfer, and
ratification. The arbitration phase (called a
"tournament") of a given data transfer cycle includes a
series of arbitration cycles (e.g., three cycles or four
cycles) conducted among the users who have data ready to
send on data ~us 14. The arbitrating user that wins, e.g.,
tournament 1 is permitted to send the next data packet over
data bus 14. Data transfer 1 begins immediately following
tournament 1 because (in this example) no users are
c~urrently using data bus 14. The user 12a - 12n that wins
tournament 1 sends its data packet over data bus 14 to the
user addressed to receive it. Data transfer 1 lasts until
the entire data packet has been transferred over the-data
bus. Ratification 1 begins during data transfer 1 with the
receiving user acknowledging erroneous or errorless receipt
of the packet to the sending user by asserting the data bus
14 ratify line as described below. Ratification 1 ends
some time after data transfer 1 because the receiving user
must have captured the entire data packet before signalling
the sending user of the erroneous or errorless receipt of
the data.
For some packets, the data transfer phase is longer
than the time needed to arbitrate for the next sender. For
example, data trans~er 1 continues until after the
conclusion of tournament 2. It is necessary to avoid the
possibility of two tournaments occurring during the same
data transfer, because this would lead to two winners
waiting for cessation of activity on data bus 14 to begin
what would be conflicting data transfers. Consequently,
the users 12a - 12n are allowed to start only one
tournament- during a given data transfer. This is - -
accomplished using the FRAME line in data bus 14, as-~
discussed below. Thereforej while tournament 2 is allowed
t~ commence immediately following tournament 1, the users
12a - 12n must wait t:o start tournament 3 until data
... ~ . ... . . . .. .. . . .... . . . . .
WO 91/10957 PCT/US91/00323
~ 0~ 14 -
transfer 1 ends. Also, the user I2a - 12n that wins
- tournament 2 must wait for data transfer 1 to be completed
before beginning data transfer 2. Hence, the winner of
tournament 2 monitors data bus 14 for cessation of activity
and then begins data transfer 2. Ratification 2 follows
data transfer 2 in the same manner described above for
ratification 1. The timing of ratification is such that no
adjacent ratifications will ove~lap (although they may
overlap adjacent data transfers).
Typically, a tournament is shorter in duration than
the data transfer cycle during which it occurs. This is so
because a tournament comprises only a few arbitration
cycles, each only a few clock pulses in duration, while a
data transfer typically involves the transmission of a
large number of data words over a corresponding number of
clock cycles. However, sometimes relatively small data
packets containing only a few bytes of data (e.g:, the
packet sent in data transfer 2) are transmitted. As a
result, the next tournament, e.g., tournament 3, exceeds
the prevlous data transfer 2 in duration. This leads to
some degree of idleness for data bus 14 between data
transfers 2 and 3 because data transfer 3 cannot begin
until tournament 3 has been completed (because no winner
has yet been assigned to access the data bus for data
transfer 3).
A tournament may begin at any time as long as there is
no possibility of conflict between two tournament winners
waiting for data bus 14. For example, tournament 4 begins
during data transfer 3 as soon as there is at least one
user (other than the user currently sending data) requiring
access to data bus 14. Accordingly, the winner of
tournament 4 waits for data transfer 3 to conclude before
beginning data transfer 4. - - -
Another cause of data bus 14 idleness is the start of
a tournament shortly before the current data transfer is
complete. For example, tournament 5 begins just prior to
WO9l/10957 PCT/US91/~0323
' - 15 ~ 20i082~`
the end of data transfer 4, causing data bus 14 to remain
idle after data transfer 4 ends until the winner of
tournament 5 can be determined and that user begins data
transfer 5.
Arbitration ~iminq
Referring to Figs. 3a and 4, individual users 12a -
12n running on individual non-synchronous user clocks 18,
coordinate the application and readback of arbitration
codes (ARBDATA) on arbitration bus 16 for a three-cycle
tournament in the following manner. The three wired-OR
lines of sync bus 19 and the rising edges of their
respective signals, ARBSYNC1, ARBSYNC2, and ARBSYNC3, are
used to coordinate the'tournament. So-called `'wired-OR"
lines have a quiescent or undriven state when no user is
driving'the line, and a driven or asserted state when one
or more users drive the line. ~he undriven-to-driven edges
of these signals are used for arbitration because
applicants have found that the other edges ~i.e., driven-
to-undriven) of the signals produce more reflections on the
wired-OR lines which interfere with efficient arbitration.
Thus a single edge of the ARBSYNC signals is used. In the
examples shown in the figures, the lines are quiescently at
a logic low and are driven to a logic high; thus, the
rislng edge is used. But normally high lines, driven to a
logic low, could also be employed, in which case, the
falling edges would be used.
In the example illustrated by Figs. 3a and 4, it is
assumed that initially no users 12a - 12n are attempting to
arbitrate. When a user (e.g., user 12a) determines from
its send buffer 20 or 21 that it has a data packet to send
on data bus 14, it asserts a pulse on ARBSYNC3 ~100) at a
-~ rising edge of its internal user clock 18 ~time A).- The
rising edge of this pulse indicates t'o all users that'this
is the beginning of arbitration cycle l. The ARBSYNC3
pulse is one clock period long, and thus is terminated when
. .
. -
WO91/10957 PCT/US91/00323
0`~ ~ 16 -
a counter in user 12a (initialize'd ~102) at 0) counts one
'cycle ~104)' of the user clocK 18 of user 12a. Each user
12a - 12n includes a watchdog timer which forces the user
to release an ARBSYNC signal (i.e., allow the signal to
become a logic 0) if the user holds the ARBSYNC signal high
for a predetermined time. This prevents a malfunctioning
user clock 18 from d:isrupting arbitration.
Upon receiving the rising edge of the pulse on
ARBSYNC3, all other users 12a - 12n are prevented from
generating their own ARBSYNC3 pulses. If two or more users
12a - 12n become ready to arbitrate at about the same time,
- it is possible that these users will each assert a pulse on
ARBSYNC3 before having a chance to observe the rising edge
from the other. The appearances of multiple pulses on the
ARBSYNC3 line is of no conse~uence because each user 12a -
12n responds only to the first detected rising edge of the
pulse ARBSYNC3.
Logic delays and transmission line effects may cause
the ARBSYNC3 pulses to appear as one pulse or as a sequence
of pulses on the ARBSYNC3 line (during the period shown as
time B). The exact shape of the ARBSYNC3 signal is not
important, because each user responds only to the rising
edge of the first ARBSYNC3 pulse it sees. Upon receiving
this edge, every user 12a - 12n that has a data packet
ready to send applies its cycle 1 ARBDATA code (ARB CODE 1)
(106), discussed below, on arbitration bus 16. Only users
12a - 12n that have a data packet ready when they observe
the rising edge of ARBSYNC3 may participate in this
tournament (tournament 1). Note that each user 12a - 12n
drives the arbitration bus 16 with its cycle 1 ARBDATA code
in response to the ARBSYNC3 rising edge, which need not be
(and often is not) synchronous with its own internal user
clock 18. The cycle l ARBDATA code is driven by each user
during-time period C. Non-participating users 12a - 12n
continue to monitor the synC bus 19 signals to keep track' '
of arbitration cycles and detect the beginning of the next
..... , . ................................... .. .. ... , ., . .,. , . ~ ......
', ' :
WO 91/1Og57 PCT/US91/00323
. . , ~
-- 17 --
2070821
tournament (tourn,ament 3), but they may not participate in
the current tournament by driving either the arbitration
bus 16 or sync bus 19 signals.
Once a positive edge has been generated on ARBSYNC3,
all users 12a - 12n wait for arbitration bus 16 to
stabilize before attempting to read ARBDATA (106). A
latency period (time A to time D) is built into each user
as a delay between the rising edge of ARBSYNC3 ~100), as
seen by the user, and generation of the next ARBSYNC pulse
(ARBSYNC1), which will cause reading of ARBDATA. In the
worst case, this delay compensates for ARBSYNC3 to
propagate down sync bus 19 to a far-end user, and for that
far-end user to apply its ARBDATA to arbitration bus 16 in
response. Delay is also required for the far-end user
ARBDATA to propagate back across the arbitration bus 16 to
all users. A standard user clock delay is programmed into
a register (ARB DELAY) in each arbitration controller 17
(Fig. 1) to compensate for this worse case logic and
transmission line delay. The delay is 5 clock cycles in
the examples shown in Figs. 4, 5, and 6. Each user that
asserts ARBSYNC3 beglns to count (102) positive edges of
its own user clock 18 immediately after asserting the
~RBSYNC3 pulse (100), which is equivalent to starting the
count with a value of 0 (102) (i.e., the first rising edge
of the user clock 18 after asserting ARBSYNC3 produces a
count of 1). Every other arbitrating user, upon receiving
the initial positive edge of ARBSYNC3, waits for the next
rising edge of its own user clock 18 before it begins
counting, which for such users is the equivalent of
starting the count with a value of -1 (i.e., the first
rising:edge of the user clock after receiving ARBSYNC3
produces a count of 0).
- Each user captures the ARBDATA value on arbitration
bùs 16 on the rising edge of the first ARBSYNCl:pulse it
observes (time D). The state of the ARBSYNCl line when a
user 12a - 12n reaches its ARB_DELAY count determines
.. . ... ., . . . ., . . . , . . . . ~ ., .. . .. ,, . ., ~ .. ,,.. _.. ... .
' .
WO 91/t~957 PCT/US91/00323
~ 0~ 0~ 18 -
:
whether or not that user asserts a pulse on ARBSYNC1. One
and one-half clock counts before the user clock count
reaches the ARB_DELAY value (i.e., on the negative edge of
the internal user clock 18 after the count reaches
ARB_DELAY-2, which is 3 cycles in this example) ~108), the
user begins observing (112) the ARBSYNC1 line (110). If
the user's clock count then reaches the terminal ARB_DELAY
value and ARBSYNC1 remains low (114), then the user asserts
a pulse on ARBSYNC1 for one clock cycle at time D (116,
10 132, 133). If, on the other hand, a high level on ARBSYNC1
arrives while the user is observing the ARBSYNC1 line
(118), then the user refrains from asserting a pulse on the
ARBSYNC1 line.
The leading edge of the pulse on ARBSYNC1 triggers
each user to capture (120) the ARBDATA code on the
arbitration bus 16 (time D). ARBSYNC1, like ARBSYNC3, may
appear as a single pulse or as a sequence of pulses from
various leading users (time F), but only the leading edge
of the first appearing ARBSYNC1 pulse is used by the
participating users ~time D). Each participating user then
compares ~122) the captured code with the code it was
expecting as ARBDATA. If the codes match ~124), the user
is a "winner" ~possibly one of a number of winners) of that
cycle and remains a contender in the tournament. If, for a
given user, the codes do not match ~126), that user has
lost in this tournament but may continue to produce sync
bus 19 pulses where appropriate for the remainder of the
tournament. However, losing users no longer drive ARBDATA
~128) on the arbitration bus 16 in the remaining ~i.e., the
second and third) arbitration cycles in this tournament.
Referring also to Fig. 3b, the second arbitration
cycle is similar to the first, except that it is triggered
by the rising edge of ARBSYNC1 (time D). Each user 12a -
12n remaining in contention in the tournament places its -
second arbitration code ARBDATA on the arbitration buslines (130) immediately after receiving the rising edge of
~0 91/lOg57 PCT/US91/00323
-- 19 -- ..
2070821
ARBSYNC1 ~time E) generated during cycle 1. Each
- participating user 12a - 12n (contender or loser) who
asserted an ARBSYNC1 pulse begins counting positive edges
of its own user clock immediately after asserting ARBSYNC1
(132, Fig. 3a). Other participating users (i.e., those
users that did not assert ARBSYNC1) wait until the next
rising edge of their internal clock 18 following the rising
edge of ARBSYNC1 before beginning to count (134, Fig. 3a).
On the next negative transition of the internal clock 18
10 (138) after the count reaches ARB_DELAY-2 (136) (same value
as cycle 1 above), each participating user begins observing
(140) the ARBSYNC2 bus line. The first participating user
to reach a count of ARB_DELAY (142), without observing a
rising edge on the ARBSYNC2 bus line, places a single pulse
(144), one user clock pulse in length (146, 148), on
ARBSYNC2 at time G. This pulse causes each user 12a - 12n
remaining in contention in the tournament to again sample
(150) ARBDATA on arbitration bus 16 and compare it (152) at
time E to the second arbitration code (ARB CODE 2) ~hat it
placed on arbitration bus 16. Once again, if for a given
user, the codes do not match (154), that user becomes a
loser in tournament 1 and no longer drives ARBDATA (156);
buk the user continues to monitor and supply, if required,
sync bus 19 signals for the remainder of the tournament.
Referring also to Fig. 3c, this process is repeated in
the third cycle of the tournament. The third cycle is
triggered by the rising edge of ARBSYNC2 (144, Fig. 3b) at
time G. Users that remain in contention in the tournament
place (158) their third and last arbitration code (ARB CODE
30 3) ARBDATA on arbitration bus 16. Each participating user .
~contender or;loser) who asserted an ARBSYNC2 pulse begins
.. counting.(146,: Fig. 3b) positive edges of its own user
- clock immediately after asserting ARBSYNC2. -.Other
.. participating users wait until the.next rising edge of
their internal clocks. 18 following observation of the
rising edge of ARBSYNC2 before beginning to count (147,
WO 91/lOg57 ~ ~ ~ PCT/US91/00323
. ,. . : ~ ';;
,, . .. ~
Fig. 3B). On the next negative transition of their
internal' clocks 18 (162) after the count reaches ARB DELAY-
2 ~160), all participating users begin observing (164) the
ARBSYNC3 line. Every participatinq user that reaches ~166)
a count of ARB_DELAY, without observing a rising edge on
the ARBSYNC3 line, places (168) à single pulse, one user
clock pulse in length (170, 172), on ARBSYNC3 at time I.
This pulse causes each user that remains in contention in
the tournament to again sample (174) ARBDATA on arbitration
bus 16 and compare (176) it to the third arbitration code
(ARB CODE 3) that it placed on bus 16 at time G. When all
remaining contenders sample ARBDATA, only one will find a
code that matches the code expected by the user (178).
This user is the tournament winner (180) and will be the
next user allowed access to data bus 14 to transmit the
data packet in its send buffer 20 or 21 (Fig. 1).
The rising edge of ARBSYNC3 (168) used to capture
(174) the third cycle ARBDATA concludes the current
tournament (i.e., tournament 1), and also serves to begin
the next tournament (i.e., tournament 2). Each user, other
than the winner of tournament 1, that has a packet ready to
send when ARBSYNC3 rises at time H, becomes a contender in
the new tournament (177). The user that won the previous
tournament iS not a contender in the new tournament,
because that user has been granted access to data bus 14
and need not compete until it requires access again, but
that user participates in the next ARBSYNC pulse generation
to start the next tournament, as described below.
' Referring also to Fig. 3d, tournament 2 begins
immediately following tournament 1 as long as there are
- still users that require arbitration. Each user that will
contend for access to data bus 14`in tournament'2 responds
to the rising edge'of ARBSYNC3 (168, Fig.' 3c) at time I of
.
tournament 1, by'placing (200) its ARBDATA code for cycle 1
of tournament 2 on arbitration bus 16. The user or users'
of tournament 1 that asserted ARBSYNC3 at time I (cycle 3,
' ' ' '' " ' ' ' " '' : ', '
., ;
.. : .
,
WO9t/109S7 PCT/US91/00323
' - 21 ~0708`21
tournament 1) begins counting ~170, Fig. 3c) internal user
clocks immediately after it asserts ARBSYNC3. All other
participating users begin counting their internal user
clocks on the next rising clock edge after they detect the
S ARBSYNC3 pulse (171, Fig. 3c). On the next negative
transition of their internal clock ~204) after the count
reaches ARB_DELAY-2 (202), all participating users begin
observing ~206) the ARBSYNCl line. The first participating
users to reach a count of ARB_DELAY, without observing
~208) a rising edge of the ARBSYNC1 line (with the FRAME
line remaining low (210), as discussed below) places (212)
a single pulse, one user clock pulse in length (214, 216),
on ARBSYNC1 at time J. The winner of tournament 1 then
stops participating in the tournament. The ARBSYNC1 pulse
causes all tournament 2 contenders to sample ~218) ARBDATA
on arbitration bus 16 to complete cycle 1 of tournament 2.
As long as there are some contenders in tournament 2,
ARBDATA will have a non-zero value ~220) ~the zero value
case is discussed below) and the tournament will continue
in cycles 2 and 3 ~121, Fig. 3a) in the same manner as
discussed above for tournament 1.
The ARBSYNC pulse that terminates an arbitration cycle
is always generated by the user or users that first reaches
the ARB DELAY count of internal user clock cycles. Such
users are called "leading users". Since all user clocks
are at about the same frequency, the leading user of one
cycle is also likely to be the leading user for the next
cycle. It is possible, however, for a faster clock to
gradually drift ahead of a slower one, so that the user
with the faster cl'ock takes over the role of leading user.
Also, if~a user drops out of-the arbitration (e.g., because
it has-won a tournament), the role of leading user shifts
to another user. ;
Referri'ng to Fig. 5, there is shown an example'of the
role of leading user shifting from one tournament to'the
next. During tournament 1, user A is the leading user in
..... ..
WO 91/10957 PCT/US9l/00323
~ 22 - ~
each arbitration cycle, so the user A clock is effectively
timing the rlsing edges of the ARBSYNC pulses. All users
that participated in tournament 1, including the winner,
plus any new users that wish to send a packet, all count
clock cycles in the first arbitration cycle of tournament
2. In this example, user A is again the first to reach
ARB_DELAY so it generates ARBSYNC1 (at time B).
Now assume that user A was the winner of tournament 1,
so A stops participating in tournament 2. ARBSYNC2 must
now be generated by some other user, whichever one is the
first to reach a count of ARB-DELAY. In the example, the
first turns out to be user B (at time C). User B then
continues to be the leading user in tournament 2 (see time
D).
Referring to Fig. 6, as discussed below, it is
possible to have some idle time between two tournaments.
The left side of the figure shows the end of the tournament
(e.g., tournament 1) in which only a single user is
contending for access to data bus 14. When the single
contender obtains access, there are no more users 12a - 12n
requesting use of the data bus 14, so all arbitration bus
16 lines remain low (i.e., ARBDATA = 0). As always, the
winning user of tournament 1 continues counting clock
cycles after tournament 1 concludes, and ultimately
supplies the ARBSYNC1 pulse (time C). Upon receiving the
positive edge of this pulse, all users 12a - 12n capture
the idle state of the arbitration bus. Thus, a source for
the ARBSYNC1 pulse is assured, even in the absence of any
new contenders or tournament 1 losers to supply this pulse.
Upon capturing the idle condition of the arbitration bus
- lines, all users cease arbitration activity and wait for
their send buffers 20 or 21 (Fig. 1) to obtain a new data
packet. During the arbitration idle state, any user may
-start a new tournament by asserting the ARBSYNC3 pulse
(time D) as described above.
' .
WO91/10957 PCT/US91/00323
- 23 -207~82~
Referring to Figs. 3d and 7, arbitration is suspended
.
when necessary by use of the data bus 14 FRAME control Iine
(Fig. 1). Because packet data transmission on data bus 14
usually takes longer than a tournament (Fig. 2), it is
often necessary to suspend the start of a second tournament
until a current data packet transfer on the data bus is
completed. This prevents two or more tournaments from
taking place during the same data transfer, which would
result in more than one tournament winner concurrently
waiting to access data bus 14. Only a single tournament
may occur during a given data packet transfer period to
assure that only one user is designated to access the data
bus when the current data bus access is complete.
When the user accessing data bus 1~ detects the
presence of a tournament, signified by the rising edge of
ARBSYNC2, that user asserts the FRAME control line of data
bus 14 (time A in Fig. 7). Each user participating in the
next tournament samples (209, Fig. 3d) the FRAME control
line on positive edges of its own internal user clock. If
FRAME is high ~211) when a participating user is about to
generate an ARBSYNC1 pulse ~time B), that user enters a
hold state, suspending arbitration. Therefore, while FRAME
is high, no users are allowed to complete cycle 1 of the
second tournament. Upon completing its current data
transfer on data bus 14, the sending user allows the FRAME
control line to go low ~time C). Upon detecting (210) the
low state of the FRAME control line, all arbitrating users
resume the tournament operation (time D).
In the examples discussed thus far, the arbitration
tournament was three arbitration cycles in length, and
- three synchronizing lines were used in the sequence:
ARBSYNCl, ARBSYNC2, ARBSYNC3. Fig. 18, discussed below,
shows-an example with only two synchronizing lines, which
are pulsed in alternating sequence: ARBSYNC1, ARBSYNC2,
ARBSYNC1, ARBSYNC2. More than one synchronizing line is
used so that the latest pulses from one arbitration cycle
.
WO91/lOg57 PCT/US91/00323
~ 24 - ~
wili not be confused with the earliest pulses from the next
arbitration cycle. For the scheme to work, there must be a
sampling period near the end of each arbitration cycle
during which each user can watch for a sync pulse from some
other user, while counting toward ARB_DELAY. (In the
example described above, this period begins on the negative
edge of the user's clock after it reaches a count of
ARB_DELAY-2). All pulses from previous cycles must be over
with before this sampling period can begin.
It is possible to perform arbitration with only one
synchronizing line, but a longer arbitration cycle time is
required. The minimum cycle time must include the times
given above (i.e., enough time for a signal to travel the
length of the backplane, for a user at the far end to
respond, and for the signal to travel back and be
recognized), plus the length of the sync pulse itself and
the length of the ARBDATA sample time at the end of each
cycle.
~_cl~C~ L_~510~QL
The individual lines of arbitration bus 16 (ARBDATA0
through ARBDATA4) are configured as wired-OR lines so that
any participating user asserting one of the arbitration bus
lines ~i.e., by placing a logic "l" on the line) will cause
each of the other users to detect that assertion.
Therefore, an arbitration bus line is low if no
participating user asserts it high, but is high if any
participating user asserts it high.
Arbitration codes are assigned to users so that after
a predetermined number of cycles (e.g., 3 or 4) of applying
arbitration codes to arbitration bus:lines 16, only one
user will remain. This user is the "winner" of the
tournament and is permitted to send its data packet on data
.
bus 14 during the next data transfer cycle, as discussed
above.
, . .
WO 91/10957 PCT/US9i/00323
- 25 -
2070821
Referring to Figs. 8 and lO, there is shown a three-
cycle tournament using a five-wire arbitration bus 16.
Arbitration data lines ARBDATA0 - ARBDATA4 (Fig. l) are the
data lines of arbitration bus 16, representing a five bit
ARBDATA code word (ARB CODE). Line ARBDATA4 is the most
significant bit tMSB) and line ARBDATA0 is the least
significant bit (LSB). Fig. 8 is divided into three
arbitration cycles and shows the meaning assigned to each
arbitration line (bit) for each arbitration cycle. During
cycle l, arbitration data lines ARBDATA0 - ARBDATA4 are
defined to represent user priorities (i.e., Pl and P2) and
groups (Gl and G2), discussed below. During cycles 2 and
3, the arbitration lines are defined to represent pre-
assigned arbitration address code bits A9-A5 (i.e., the
most significant portion of an arbitration code of Fig. lO)
and A4-A0 (i.e., the least significant portion of an
arbitration code of Fig. lO) respectively.
Arbitration cycle l separates the participating users
by priority of the message, Pl or P2. Message priority is
determined by each user's send buffers 20 and 21 (Fig. l)
and is dependent on message content and related urgency.
There are two message priorities available in this system,
a high priority Pl and a lower priority P2. Priority for
arbitration is based on two factors: (l) the priority as
indicated by message priority signals Pl and P2 and (2)
group membership. Group membership is gained by a user
when it fails to win a tournament in which no contender was
a group member with the same message priority. Group
membership is indicated by group priority signals Gl (for
Pl messages) and G2 (for P2 messages). During cycle l, a
user with a Pl packet asserts (i.e., places a logic "l")
arbitration data lines ARBDATA0, ARBDATAl, and ARBDATA2
(Olll) (Fig. ~), Similarly, a user with a priority P2
packet asserts onIy line ARBDATAO ~OOOl). - -
Group Gl users set ARBDATA 3 high (llll) and group G2
users set ARBDATAl high (OOll) in addition to their
WO91/10957 ~ 26 - PC~/US91/00323
;, ~
respective P1 and P2 codes. Thereafter in subsequent
tournaments, users asserting a G1 signal have priority over
those asserting a P1, G2 or P2 signal. Thus, users
belonging to group G1 will have priority over all new
entrants with the same P1 mes`sage priority (i.e., users
that are not members of G1 ? a~d all users with P2 message
priority. Similarly, those users asserting a G2 signal
have priority over those asserting only a P2 message
priority (i.e., users that are not members of G2) signal,
yet G2 users still yield to all users asserting either P1
or G1 priority signals. New G1 or G2 groups may be formed
after all the current G1 or G2 respective group users have
been serviced, thus assuring access to those belonging to a
group before granting access to new participating users
with the same message priority. In this way, all users
with the same priority who enter a given tournament
together are assured of being serviced before a new user,
with the same priority, who attempts to start arbitration
after this tournament.
Referring to Fig. 9a, there is shown an example of the
arbitration codes asserted by seven users competing for
access to data bus 14 during cycle 1 (ARB CODE 1) of each
of seven tournaments. The far left column indicates the
user number and its corresponding priority. For instance,
user 1 has a P1 priority, and user 4 has a P2 priority.
During cycle 1 of tournament 1, users 1, 2 and 3 assert
their P1 priority code of 0111 (Fig. 3), and users 9 and 5
assert their priority P2 code of 0001. Users 6 and 7 have
not yet requested access to data bus 14 and thus do not
participate in tournament 1.
Assume that user 3 wins tournament 1 (e.g., it has the
highest user number (A9 - A0) among Pl users and therefore
gets selected first-as per the suggested arbitration
assignments descri~ed below), thus user 3 does not
participate in tournament 2. Users 1 and 2 continue to
assert their priority P1 signals. Because they lost
WO91/10957 PCT/US91/00323
- 27 - 2~70821
,
.
tournament l, and no user:had its group bit set in
tournament l, they form a Gl group and assert their Gl code
of llll during cycle l of tournament 2. Similarly, users 4
and 5, the priority 2 losers of tournament l, form a G2
group and assert their G2 code of 00ll during cycle l of
tournament 2. Users 6 and 7 vie for access in tournament 2
and thus assert their corresponding priority Pl code ~0lll)
and P2 code (000l) respectively. Because user 6 entered
the arbitration contest in a later tournament than users l
and 2 (same Pl priority), user 6 will always have a lower
priority with respect to that of users l and 2 (i.e., users
l and 2 will always get access before 6). The same is true
for user 7 with respect to users 4 and 5 (same P2
priority); that is, users 4 and 5 will always get access
before user 7.
Assume that user 2 wins tournament 2 and thus does not
participate in the next tournament. In tournament 3, user
l continues to assert its Gl code, users 4 and 5 assert
their G2 codes, user 6 asserts its Pl code, and user 7
asserts its P2 code. Once a Gl group is formed, all of its
members must be serviced before another Gl group is formed.
Thus user 6 cannot be a member of a Gl group unless all
members of the Gl group at the time user 6 started
arbltration ~i.e., users l and 2) have been serviced. As
with a Gl group, once a G2 group is formed, all of its
members must be served before another G2 group is formed.
Thus user 7 cannot be a member of a G2 group until all
members of the current G2 group are serviced (i.e., users 4
and 5). Therefore user 6 may only assert a Pl code and
user 7 may only assert a P2 code at this time.
Assume that usex l is the winner of tournament 3.
-Thus, it is apparent that both users l and 2, forming group
Gl were serviced before the priority Pl user 6.
User 6 wins tournament 4 even though it began
arbitrating after the G2 group of packets 4 and 5 was -
formed. This is apparent from the order of priority ~i.e.,
.. ..... .. .... . .. .. .... . . . . ...
WO 91/109~7 PCT/US91/00323
_.
~ 28 -
Gl, Pl, G2, P2) of Fig. 9. The remaining tournaments 6 and -
' 7 illustrate thàt the two priority P2 packets, 4 and 5,
forming group G2 are serviced before priority P2 packet 7.
Referring to Fig. 9b, there is shown another example
of the arbitration codes asserted during cycle l of each of
six tournaments. Here, five users with Pl message priority
packets compete for c~ccess to data bus 14. The far left
column indicates the user number and its corresponding
priority. In particular, this example illustrates how a
new group forms after one group finishes (i.e., all users
in the group gain access to data bus 14). Group Gl is used
here, but the scheme also holds for other groups such as
G2.
During cycle l of tournament l, users l, 3 and 4, all
lS having Pl priority, participate in the tournament. Each
asserts its Pl message priority code 0lll. users 2 and 5
have not yet begun to participate.
Assume that user 9 wins tournament l (i.e., has
highest user number A9 - A0 among Pl participants) and does
not participate in tournament 2. Users l and 3 continue to
assert their Pl priority code during tournament 2.
Additionally, because they lost tournament l, and no user
had its Gl group bit set in tournament, users l and 3 form
a Gl group and as9ert their Gl code of llll during cycle l
of tournament 2. New tournament 2 participant user 2 also
has a Pl message priority packet, but may not join users l
and 3 in group Gl since it did not participate in
tournament l (i.e., the'losing participants of which formed
group Gl). Therefore, user 2 asserts a Pl code of 0lll
during tournament 2, and continues to do so until both
users l and.3 have won a tournament.
Assume that user 3 wins tournament 2, and thus need
not participate in tournament 3. During tournament 3, user
l competes with user 2 and new user 5'j also having Pl
priority. Once again, user l asserts an arbitration code"
of llll, indicating Gl membership. Users 2 and 5 both
.
WO 9l/10957 PCT/US91/00323
,
2070821 - ' .
assert codes of 0111, since neither one is a member of
group G1.
User 1 wins tournament 3, thus need not participate in
tournament 4. Users 2 and 5 participate in tournament 4,
S along with new user 4. All users have P1 priority packets
and each asserts a code of 0111. Since tournament 4 is the
first tournament after the tournament in which the last
member of the original Gl group won ~i.e., user 1 won
tournament 3), the losers of tournament 4 will form a new
G1 group for tournament 5. That is, the current tournament
has no participants asserting G1 membership, and therefore
a new G1 group may form for the next tournament.
Therefore, although users 2, 4 and 5 began arbitration at
different times ~i.e., user 2 in tournament 2, user 5 in
tournament 3 and user 4 in tournament 4), they all assert
the same 0111 Pl message priority code during tournament 4,
and the losers form the same Gl group for tournament 5.
Assume user 5 wins tournament 4, and thus need not
participate in tournament 5. Users 2 and 4 form the same
20 G1 group and each continues to assert a code of 1111 until
lt is serviced ~i.e., user 4 wins tournament 5 and user 2
wins tournament 6).
There are additional arbitration cycles in each
tournament because, as can be appreciated from the above
discussion, multiple users typically "win" during cycle 1.
Cycles 2 and 3 are used to "weed out" all but one
tournament winner. A series of unique arbitration codes
are pre-assigned among users (e.g., based on cardcage slot
position) and are applied by the user to the arbitration
bus during cycles 2 and 3 to produce a tournament winner.
Referring to Fig.:10, there is shown a table of
tournament cycle 2 and 3 codes and their distribution among
36 users. The column labeled A9-A5 correspond to
.
arbitration bits A9-A5 of Fig. 8 (ARB-CODE 2). SimiIarly,
the column labeled Ar-A0 correspond to arbitration bits A4-
A0 of Fig. 8 ~ARB CODE 3). The arbitration codes in these
~.
WO 91/1~9S7 ~ PCT/US9l/00323
- 30 -
two columns form a "marching ones'l pattern in each column.
Every code is either the same, a subset, or a superset of
every other code in its column. Therefore, during a given
arbitration cycle, if two or more codes are simultaneously
applied ~o the wired-OR lines of arbitration bus 16, the
resulting pattern will always match at least one of the
codes applied. There are groups of users with the same A9-
A5 (ARB CODE 2) code, but these users have different A4-A0
(ARB CODE 3) codes. Although the arbitration code
assignment suggested by Fig. 10 need not be followed
exactly, the codes should be related by an identity-subset-
superset property so that each arbitration cycle will
always have at least one winner.
Also apparent from Fig. 10 is that a priority exists
among codes, with user 0 having the lowest priority code
and user 35 having the highest priority code. Thus, within
a given group, user 35 will always defeat any other users
in cycles 2 and 3. The converse is true for user 0. For
example, during cycle 2, users 30 - 35 tllll) will always
Z0 be victorious over other remaining users. Conversely in
cycle 2, users 0 - 5 ~0000) will always lose to any other
users. In cycle 3, users 5, 11, 17, 23, 29 or 35 (1111)
will be victorious over any other remaining users because
they are the highest priority users of their cycle 2 group
(but the presence of any one of these users in cycle 3
mutually excludes the presence of the others).
Hence, if a group of users all desire to arbitrate at
the same time and with the same message priority, higher
numbered users will win first. Users who begin arbitrating
with the same message priority a little later, however,
will have to wait for all members of the first group to
- finish. - --
;
, , ' . ' `: ' '
, . .. .. . . ., ~ . ., . , , ,, , .,, ~ . . .
WO91/10957 PCT/US91/00323
- 31 -
2070821
Data T~ansfer Pro~ocol
Referring to Fig. ll, the data bus lines (Fig. l) are
grouped into two segments (corresponding to data buffer A
and data buffer B of Fig. l), each of which includes its
own data strobe signal (STROBE A and STROBE B,
respectively). The timing for only a single data bus
segment and associated strobe is shown in Fig. ll. All the
lines of a given segment are attached to the same bus
driver device in the sending user and the same bus receiver
device in the receiving user in order to limit the skew
between the various data bits of a segment and its
corresponding data strobe signal caused by variable
propagation delays associated with multiple drivers and
receivers. Eliminating the skew between the data bus
segment and its corresponding data strobe leads to a high
data rate capability. In this example, one data bus
segment (Data Buffer B) contains seven data bits ~Dl - D7),
while the other data bus segment (Data Buffer A) contains
the remaining data bit, D0 (to make a total of eight data
bits), the FRAME line, the RATIFY line, and the PARITY
line.
Transitions on the data strobe line occur midway
through the time period in which data being transmitted on
data bus 14 is valid (time A). Thus, the strobe
transitions are used by the receiving user to capture that
data. The data strobe makes only a single transition per
data cycle, and both rising (time A) and falling (time B)
transitions are used to strobe data into the receiving
buffer. The data strobe line is always returned to its low
resting state at the end of a packet. If the-data packet
contains an odd number of bytes, an extra cycle time is
added to the end of the packet to allow the data strobe
line to-return to its low resting state (time X). Both
cases are shown in Fig. ll.
As discussed above, the FRAME line is used to suspend
tournaments once a next sender has been selected. The
.. . . .... . . . . .. . ... .. ...... ......... ..
WO 91/109S7 ~,~ PCT/US91/00323
~ ~ - 32 -
, . . ,~ .
current sender raises the FRAME control line if it detects
the start of a second cycle of a tournament (i.e., the
rising edge of ARBSYNC2, Fig. 7) which may occur at any
time during its data packet transfer (time C). The sender
S lowers the FRAME control line when it sends the last byte
of its packet over the data bus 14 (time E). Another
function of the FRAME line is to flag the end of each
packet for the receiving user and any tournament winner
waiting for data bus 14. Therefore, the sender always
raises the FRAME control signal during the next to last
byte of a packet (time D) even if it doesn't detect another
arbitration and lowers the FRAME signal on the last byte
(time E) to provide a high to low transition on the FRAME
control signal at the end of every data packet. A winning
user of subsequent arbitration monitors the FRAME control
signal and begins its data transfer only after it detects
the high to low transition on the FRAME control signal.
The sending user calculates an error detecting parity
bit from the data bus data bits and frame control signal
bits, and transmits the parity bit along with the data on
the PARITY line of data bus 14 ~Fig. 1). The parity
alternates between odd and even parity, beginning with odd
parity, on a data byte by data byte basis. Alternating
parity makes clock glitches or out of sync clock edges
detectable as parity errors. Also, no collection of stuck
data bus lines can satisfy the parity check over the entire
data packet.
Referring to Fig. 12, there is shown a timing diagram
of sequential data transfers (Fig. 2) over the data bus 14,
and the relationship of user clocks among subsequent users
of data bus:lq. While user A transfers data on data bus
14, subsequent arbitration winner, e.g., user B, samples
the FRAME control iine on data strobe edges (time A?, and
looks for a high to low transition on FRAME (time B)
indicating the end of the current data transfer on data bus
14. User B then samples data strobe on the rising edge of
... . . . . .. .. . .. .. . . . ... .. .. . . .. . ...
WO 9l/10957 ; PCT/US91/00323
~~ ~ 33 ~ 2 ~ 7 08 2 1
its own internal user clock (time C) until a low value is
obtained, thus assuring user B of control of the data
strobe. On the following negative edge of the user B clock
(timer D), user B begins sending the first byte of its
packet on data bus 14.
In order for two users 12a - 12n to transfer data
packets using this data transfer protocol, their user
clocks 18 must be maintained close in frequency. In
particular, the user clocks 18 must be close enough in
frequency so that, over the course of a maximum-sized
packet (e.g., 64 bytes), the skew accumulated between the
slowest and fastest user clock 18 is less than 1/2 the
interconnect bit time (i.e., the time taken for a bit to
propagate between the two most distant users).
Ratify Protocol
The ratify protocol provides verification t:o the
sender that the packet arrived at the receiver intact. The
first byte ~word) of each data packet sent over the data
bus contains a destination user address. Each user 12a -
12n captures the first word of every packet and examines
the address to determine if it is the destination for the
packet. Each user is configured to recognize its own
unique address, and all users recognize a global broadcast
address (as well as multicast addresses). If a user does
not recognize the packet address as its own ~or as a global
address), the user simply ignores the rest of the packet.
If the address is a global address or matches the-address
of a receiving user, the user examines the priority bit
~i.e., P1 or P2), which is also in the first byte of the
packet, and accordingly directs the packet to the proper
receive buffer, 22 or 23 ~Fig. 1) corresponding to the
packet priority. Receive buffer 22 accepts priority P1
packets while receive buffer 23 accepts priority P2
packets.
W09l/10~57 PCT/US91/00323
34 -
Referring to Figs. 13 and 14, when a user recognizes
- its own addrèss (or the global or multicast addresses) and
begins to receive the packet, it responds by raising the
data bus 14 RATIFY line (Fig. 1) at time A. As a packet
transfer continues, the receiving user captures each byte
of the packet and checks `for parity errors. At the end of
the packet, if the use~r detects no parity errors, the user
lowers the RATIFY line ~time C). Conversely, if the
receiving user detects a parity error, it holds the RATIFY
line for a predetermined period, as discussed below (e.g.,
from time C to time E), after the end of the packet
transmission, before lowering the RATIFY line.
The sending user checks that some user is receiving
the packet by looking for a high level on the RATIFY line
during packet transfer. This indicates that at least one
user has recognized this address as its own and has
responded by raising the RATIFY line. If no user responds
by raising the RATIFY line, the sender recognizes an error
condition and terminates packet transmission.
After the last data byte is sent over data bus 14, the
sending user waits a predetermined length of time,
programmed in the RATIFY_DELAY register o~ arbitration
controller 17 (Fig. 1), to allow the farthest and slowest
user to respond, and samples the RATIFY line again. A low
level indicates a successful transfer. If the packet was a
broadcast packet to all users (i.e., a global address which
all users recognize as their own), their RATIFY line
responses appear together (because the RATIFY line is also
wired-OR) so that any user can prevent the RATIFY line from
30 . going low at the end of the packet if that user received
erroneous data.~
- :Timing-diagrams Figs. 13 and--14 show the ratify---
protocol signals for "long" (Fig. 13) and "short"~(Fig. 14)
packets from the standpoints of the sending user and the
receiving user. The time delays in the ratify protocol are
governed by the preprogrammed RATIFY_DELAY control register
. .... .......... ... . , . . . , ,.,. , ......................... ,~.
. ' ~ .
-
~, .
WO91/10957 PCT/US91/00323
~ 35 ~ 2070~21
(Fig. 1) in each arbitration controller 17, which specifiesa delay`in the range from one to seven user clock cycles.
In Figs. 13 and 1~, RATIFY_DELAY is assumed to be preset to
6. Fig. 13 shows the "long" packet case where the data
packet sent contains at least twice the RATIFY_DELAY
(programmed value) number of bytes (e.g., 13 bytes). Fig.
1~ shows the "short" packet case where the number of bytes
in the data packet sent (e.g., g bytes) is less than twice
the RATIFY_DELAY number of bytes. Figs. 13 and 14 each
show the signals twice, once as they appear at the sending
user and again as they appear at the receiving user, to
show the delay that can exist between them.
Referring to Fig. 13, the RATIFY control line is
raised by the receiving user after a number of bytes equal
to the value in its RATIFY_DELAY control register (time A)
is received, i.e., six bytes. If the entire packet is
received without error, the receiving user lower:s the
RATIFY control line after it receives the last byte of the
packet, i.e., the thirteenth cycle (time C). If any errors
occurred, the receiving user continues to assert the RATIFY
control line for another predetermined number of clocks
equal to the value programmed in RATIFY_DELAY (until time
E). The sending user checks the level of the RATIFY
control line at the time that it sends the byte number
equal to twice its RATIFY DELAY, i.e., the twelfth byte
~time B~. If it is high, the sending user again checks the
level of the RATIFY control line after waiting a number of
clocks equal to the RATIFY DELAY value after the last byte
of the packet ~time D). A low on the RATIFY line indicates
receipt of a packet without error. The:sender detects a
- receiving user-error if the RATIFY line is still high at
this time ~time D). .
Fig. 14 shows the ratify protocol for a "short" packet
~l.e., packet length less than twice;the RATIFY_DELAY
value). The times at which the receiving user raises the
RATIFY control line ~time A) and the sending user checks
W~91~10957 PCT/US91/00323
~ 36 -
the RATIFY control line for a high value (time B) are the
same as in Fig. 13. The falling edge of the RATIFY control
line, however, is triggered by a particular internal clock
cycle count ~i.e., twice the RATIFY_DELAY value) rather
than being triggered by the end of the packet being
received ~time C). Likewise, the time that the sender
samples the final RATIFY control line value is at a
particular clock cycle count after checking the RATIFY line
(i.e., the value of RATIFY_DELAY) (time D).
Fig. 15 gives a more general view of the RATIFY
control line timing from the viewpoint of a sending user.
The RATIFY control line signal from one packet can overlap
into the beginning of the next packet being sent on the
data bus 14 (time B), but does not disturb the values of
the RATIFY control line sampled by the sending user (times
A and C).
If short packets are too closely spaced, their RATIFY
control line signals could interfere with one another. For
instance, a receiving user might raise its RATIFY control
line before the sending user of the previous packet has a
chance to sample its final RATIFY control line value (Fig.
14, time D). This case is prevented by guaranteeing that
packet starts cannot be too closely spaced. The
arbitration protocol always spaces packet starts by at
least one tournament time ~Fig. 2). As long as any
tournament time is guaranteed to be longer than the time
needed to exec~te the ratify protocol, there is no problem
of overlapping-ratifications. Therefore, arbitration
controller 17 control registers ARB_DELAY and RATIFY_DELAY
(Fig. l) are programmed.such that the number of arbitration
~cycles multiplied by the length of an arbitration cycle is
greater than the length of the ratify protocol.
- The importance of this ratify protocol is that the
: sender knows whether or not-a packet transfer is
successful. I~ unsuccessful, the sender has several
., .. . . . . . . . ... .. . . ... .. .. ... ... . . . . - . . . .
.
WO91/10957 PCT/US91/00323
2070821
options such as trying to send the packet again over the
same path, or trying a different path.
ALternative ~mbod~m~nts
Other embodiments are within the scope of the
following claims.
The ratify protocol could alternatively be arranged so
that a user asserts the ratify line (after reception) if it
receives correct data. In this way, the sending user can
determine if any user received a transmission correctly.
With the ratify protocol depicted in the drawings, the
sending user determines if any user received incorrect
data.
As is readily apparent from the above discussion, any
number of priorities, address schemes, and arbitration code
word sizes may be accommodated by adjusting the number of
arbitration signals and cycles making up a tournament. For
instance, a single arbitration line (l-bit code word) could
accommodate 2n users in n arbitration cycles. Similarly,
2m priority levels can be accommodated in m cycles. A
single group bit may also be added to track group
formation. Such a cycle sequence may be as follows: Pm_l,
..., Pl, Po~ G, An-lt ..., Al, Ao, where Pm_l-Po represent
priority bits, G represents group membership, and An_l-Ao
~epresent address code bits (i.e., priority is determined
first, then group membership, then address).
To reduce the number of arbitration cycles needed, the
number of arbitration signal lines can be increased. For
example, four priority levels can be handled in one cycle
by three lines:(using codes 000, 00l, 0ll, lll), instead of
one line and two cycles.
~ When multiple signal lines are used,:the arbitration
codes can become more complicated.--The arbitration: -
: sequence involves three types of information: priority,
group, and address, in that order. If a given cycle
involves more than one type of information (e.g., priority
W~ 91/10957 ~ PCT/US91/00323
~Q~3 - 38 - `
and group, ox group and address), then it becomes necessary
to provide codes for all possible combinations of the
.
items. In the first cycle of the scheme in Fig. 8, for
example, arbitration of two priorities is combined with
"group" arbitration. This requires four codes--one for
each priority with the group bit on, and one for each
priority with the group bit off.
At the opposite extreme from serial arbitration would
be completely parallel arbitration. This could be
performed with 2 x P lines for P priorities with group bit
on and off, and with 2 x P x A lines for A addresses with
all combinations o~ group and priority.
Referring to Figs. 16 - 19, there is shown another
embodiment featuring, for example, a four-cycle, two-
priority tournament using a three-wire arbitration bus.
All packet priority P1 and P2 decisions are made during
arbitration cycle 1 (Fig. 16). In the four-cycle
tournament, the same G1 and G2 groups are formed as
discussed above, but only a single group bit G need be
asserted on the arbitration bus during cycle 2 by users
belonging to either G1 or G2. Only one group bit is needed
in arbitration cycle 2 because priority gets resolved in
arbitration cycle 1. Only those users with the winning
priority level in cycle 1 drive G with the associated group
bit in cycle 2. This results in the identical G1, P1, G2,
P2 priority order among packets for either the 3-cycle or
4-cycle tournament.
As shown in Fig. 1?, seven bits of arbitration code,
A9, A7-A5, A2-A0, are used overall in a "marching one"
configuration, allowing for 32 users. The A9 MSB code bit
is combined with the G bit and asserted during cycle-2
~Fig.-16).~ Because group and address arbitration are being
combined in the same cycle, codes are provided for:all
possible combinations. The MSB of the code word represents
the logical AND of the A9 and G bits, while the-LSB
represents the logical OR of the A9 and G bits. Therefore,
, ,, ,, ,, ,, , , , . . .................. .. .. .... ,... ,.. ~
'
WO9t/10957 PCT/US91/00323
.. ~,
- 39 -
2~70821
users with A9 = 0 and group bit off assert a code of 000.
Users with A9 - 1 and group bit off-assert 011. Those with
A9 = 0 and group bit on assert lll, and those with A9 = l
and group bit on assert lll. Code bits A7-A5 and A2-A0 are
used during cycles 3 and 4 respectively. Because the four-
cycle tournament requires fewer code bits than the 3-cycle
tournament, bits A8, A4 and A3 (used in the 3-cycle
tournament) can be eliminated.
Fig. 18 shows the four-cycle tournament timing
diagram. ~rbitration timing is shown for an ARB_DELAY
value of 3, which leads to a 3 clock per arbitration cycle
timing. The timing is identical to the three-cycle case,
except only the ARBSYNC1 and ARBSYNC2 bus lines are used.
Arbitration begins where a user that is ready to send a
data packet asserts ARBSYNC2 high (time A). All users wait
ARB DELAY (3 internal clock pulses in this case) clocks and
-
assert ARBSYNC1 high ~if it is still low) to capture the
ARBDATA code on arbitration bus 16 (time B). Sync bus
assertions subsequently alternate between ARBSYNC2 and
ARBSYNC1 as shown in Fig. 18 (times C, D, E and F).
Fig. 19 shows tournament suspension of a four-cycle
tournament using the FRAME control signal. As with the
three-cycle case, completion of arbitration cycle 2 in
tournament 2, as indicated by a rising ARBSYNC2 line (time
A), during a current data packet transfer causes the
sending user to assert FRAME high (time B). The asserted
FRAME control line causes tournament 3 to be suspended
(time C) until completion of the current data packet
transfer (tlme D).
Tradeoffs between the number of arbitration signals
and the number of arbitration cycles can be seen from the
3-cycle and 9-cycle examples discussed above. If a four-
cycle tournament is chosen, fewer arbitration lines need be
dedicated to arbitration bus 16 an~ sync bus i9 functions.
Howevèr, a four-cycle tournament may prove to be too long
if the traffic load contains many packets that are shorter
WO 91/10957 ~ PCT/US91/00323
s ~ ' ~
than the 4-cycle arbitration time. For short packets, 3-
cycle arbitration would result in less delay between packet
transfers (i.e., less idle time on the data bus) due to
frequency waits for tournaments to complete.
If a mixture of long and short packets is present,
idle time can be reduced by modifying the arbitration
protocol to do more "look-ahead". Instead of selecting
only one "next sender" during a packet, tournaments could
be allowed to continue to select the next two or more
senders (at the expense of additional control lines). In
this way, extra arbitration time during long packets can
make up for insufficient arbitration time during short
packets.
Further, the fault tolerant nature of system 10 may be
increased by providing a redundant arbitration subsystem.
This would involve adding duplicate ARBSYNC lines,
arbitration bus lines, data bus lines, and user clocks.
. . .. .
., .. . ~ , ,
~ , . , ~ , .. . .
.
