Multi-level round robin arbitration system

Arbitration means for arbitrating between computer devices A to F which compete for access to a common bus. The system provides cascaded round-robin units. Unit RR1 has ports A, B, C, and X in sequence, with port X coupled to round-robin unit RR2, which has ports D, E, F in sequence. On each cycling of unit RR1 past C to A, unit RR2 is checked and the next one of devices D to F (in the sequence determined by unit RR2) has the opportunity of bus access. A gating circuit 13 can further restrict bus accessing by unit RR2's devices, by timing or counter control. A third round-robin unit can be added coupled to unit RR1 (which would have ports A, B, C, X,Y) or to unit RR2 (which would have ports D, E, F, Y). The assignment of devices to ports can be controllable by a matrix switch and device assignment memory.

The present invention relates to the determination of priority (using the 
word in a broad sense) or arbitration between competing devices in 
computer systems. 
It is commonplace for a computer system to have several devices which may 
potentially compete for access to some common or shared resource. A 
typical example is a system including a system bus over which information 
(data words and addresses) flows, and which has attached to it a 
processor, various peripheral devices, and a main memory. The peripheral 
devices may also be termed DMA (direct memory access) devices, and may for 
example be communications devices. In this system, the processor and DMA 
devices will compete for access to the system bus, primarily in order to 
access the main memory. (The main memory itself will be passive, 
responding to access requests on the system bus but not initiating any 
activity itself.) The different DMA (communication) devices may have 
differing characteristics. 
There are various techniques for resolving the possible conflicting demands 
of the various devices for use of the shared resource. 
In some situations, eg in LANs (local area networks), the common resource 
is the communications channel, and each device monitors the channel so 
that the device does not interrupt another device which is already using 
the channel. (If two devices attempt to use the channel simultaneously, 
both cease their attempted communication and try again later after 
randomised delays.) 
Often, however, there is some arbitration means independent of the resource 
itself. All the devices are coupled to the arbitration means, and send 
signals to it when they want to use the resource. The arbitration means 
then determines how access to the recourse is to be allocated, and returns 
control signals to the devices accordingly. 
There are two main principles which may be used for arbitration: 
round-robin and graded priority (using the word `priority` now in a 
narrower sense). With the round-robin principle, the devices are 
notionally arranged in a cyclic sequence or loop, and if two or more 
devices all want to use the resource, access is granted to the first one 
round the loop from the last device to use the resource. With the graded 
priority principle, each device is given a different priority, and if two 
or more devices want to use the resource, access is granted to the device 
with the highest priority. 
The round-robin technique gives equal opportunities to all devices, so that 
every device has a right of access in turn. Once any device has terminated 
an access, however, if it wants another access it has to await its turn 
until all the other devices have had their accesses. The graded priority 
technique gives priority to some devices over others, so that the devices 
with higher priorities can hog the resource and devices with lower 
priorities may have to wait indefinitely long for access. 
The choice of which technique to use therefore depends on the nature of the 
system. For example, different devices may have different latencies; a 
device with a high latency can wait for a long time for access to the 
resource without ill effects, while a device with low latency must gain 
access to the resource quickly or some malfunction, such as the loss of 
information, will occur. 
Obviously, there is scope for variation in the details of the ways that the 
round-robin and graded priority schemes are implemented. There are also 
other schemes which are useful in appropriate situations, such as a 
queuing or first-come-first-served scheme, in which requests from the 
devices for the resource are stored in the order of their occurrence, and 
the resource is allocated to the devices in the sequence in which their 
requests occurred. (This scheme is broadly similar to the round robin 
scheme.) 
Despite that, the choice has broadly to be made between the two basic types 
of priority scheme, the round-robin scheme and the graded priority scheme. 
In many instances, neither choice is ideal. 
For example, take a communication system in which there are a processor and 
several communication devices (DMA devices) using a common bus and main 
memory. The processor should give way to DMA device demands, and this can 
be achieved by using the graded priority scheme. However, this requires 
the DMA devices to be ordered as well, and those at the low end of the 
priority sequence (near the processor) may then be starved of access to 
the bus. If the round-robin scheme is adopted, the processor has to be 
included in the round-robin sequence. The processor will acquire access to 
the bus frequently, and will therefore tend to reset the round-robin 
sequence to itself, so that the priority assignments for the DMA devices 
will effectively be biassed towards the graded priority scheme. 
Similarly, if the communication system has different types of communication 
devices which require different types of servicing, this can be satisfied 
only by adopting a graded priority scheme, with the devices requiring less 
servicing being given the lower priorities. But this system runs the 
danger of the lower priority devices being starved of bus access. 
The general object of the present invention is to provide a priority scheme 
which is more flexible than the standard existing schemes. 
Accordingly the invention provides arbitration circuitry for a computer 
system, comprising a first round-robin unit to which a first set of 
devices are attached, and a second round-robin unit to which a second set 
of devices are attached, the second round-robin unit being coupled to and 
treated as a device by the first round-robin unit. 
This allows high and low latency devices to share the bus, with the low 
latency devices having better access to the bus than high latency devices 
but the high latency devices getting a guaranteed amount of access to the 
bus. It may be desirable for the devices to have their burst sizes 
programmed or `tuned` for good interaction between the devices. 
Suppose that the first set of devices consists of 3 devices, A, B, and C, 
and the second set of devices consists of 3 devices D, E, and F. The first 
round-robin unit will then select in the cyclic sequence A, B, C, X, where 
X indicates the second round-robin unit, and the second round-robin unit 
will select in the cyclic sequence D, E, F. The resulting combined cyclic 
sequence selected by the two units together will thus be: 
EQU ABC-D-ABC-E-ABC-F- 
where the hyphens are used merely to clarify the structure of the sequence. 
It will of course be realised that the sequence just given is the sequence 
in which the devices will be served if all devices are requesting service. 
This sequence is in effect the order in which the devices are offered 
service; if a device which is offered service is not requesting service, 
the sequence skips past that device and goes on to offer service to the 
next device in the sequence. 
The actual sequence in which the devices are given service may thus, for 
example, be: 
EQU ABC-D-ABC-F-ABC-D-ABC-E-ABC-F- . . . 
where it is assumed that devices A, B, and C are continuously requesting 
service, while the sequence of service requests from devices D, E, and F 
is 
EQU D-F-DEF- . . . . 
Because the devices A, B, and C are all continuously requesting service, 
they receive service in cyclic sequence, with that sequence being 
interrupted at the appropriate intervals by service to the devices D, E, 
and F. Looking at these latter devices, device D is the first to request 
service and the first to receive service. The next of these devices to 
request service is device F, and this device receives service immediately 
(ie in the first available gap in the ABC sequence) after device D; this 
is because device F is the next requesting device in the cyclic sequence 
DEF following the device D currently being given access. 
The devices D, F, and E now request access is rapid succession. Because 
their requests all appear more or less together, the precise sequence in 
which they appear is irrelevant; the requests are answered in the order 
determined by the cyclic sequence D, E, F. These devices are therefore 
answered in the order D (which follows the current device closest in the 
cyclic sequence), E (following the previous device D), and F (following 
the previous device E). 
Given the same two sets of devices, an alternative way of achieving a 
similar result would be this. Take a single round-robin unit with 12 
ports, labelled (in sequence) A-B-C-D-A'-B'-C'-E-A"-B"-C"-F-, and couple 
device A to ports A, A', and A" (and similarly for devices B and C). 
This alternative has, however, certain disadvantages compared to the 
present system. One is that the complexity of round-robin units rises 
rapidly as the number of ports increases; a 12-port unit is considerably 
more complicated than a 4-port unit and a 3-port unit. The second is that 
the service offered to devices D, E, and F is reduced, compared to the 
present system. Thus while the present system can allow service to F to 
follow service to D with only a single ABC sequence intervening, as in the 
sequence 
EQU ABC-D-ABC-F-ABC-D-ABC-E-ABC-F- . . . 
discussed above, that sequence would become 
EQU ABC-D-ABC-ABC-F-ABC-D-ABC-E-ABC-F- . . . 
with a single round-robin unit with devices A, B, and C each being coupled 
to three of its ports. 
The present system can be developed (enhanced or elaborated) in various 
ways. 
One development is that more than one second-stage round-robin unit can be 
coupled to the first-stage unit. The first-stage unit may thus have a 
sequence of, say, AB-X-C-Y-, where the X sequence cycles through D, E, and 
F and the Y sequence cycles through say G, H, and I. 
Another development is that there can be more than two stages of units. 
Thus there may be a first-stage unit with a sequence of, say, ABC-X-, a 
second-stage unit with a sequence of say DEF-Y-, and a third-stage unit 
with a sequence of GHI. 
A further development is that the coupling between the units (the two 
units, in the simple form of the system) may be `gated`. This gating may 
be controlled by a counter which allows the second unit to operate only on 
say every 3rd cycle of the first unit, so that the sequence becomes 
EQU ABC-ABC-ABC-X-. 
The gating may alternatively be controlled by a timer, which allows the 
second unit to operate only during certain periods. The timer may be 
free-running, or may be reset each time the second unit operates. 
A further preferred feature of the present system is that a device priority 
assignment circuit can be included which can adjust the assignment of the 
various devices to the various round-robin units and positions thereon.

Referring to FIG. 1, the system comprises six devices DEVA to DEVF coupled 
to a common system bus SYS BUS. These devices may compete for access to 
the bus. The devices produce respective request signals RA to RF when they 
want bus access. These request signals are fed to an arbitration unit ARB, 
which returns corresponding acknowledgement (grant) signals GA to GF to 
the devices. The arbitration unit sets exactly one of the grant signals 
true, granting access to the bus to exactly one device at a time. 
FIG. 1 is a general diagram for any sort of arbitration unit. If the unit 
is a round-robin unit, then it will grant access in the cyclic sequence 
ABCDEF, or whatever modification of that sequence results from omitting 
devices which are not requesting bus access. For the moment, the block 
DEV-ASS should be ignored and it should be assumed that each device is 
coupled directly to the corresponding port of the arbitration unit ARB. 
FIG. 2 shows the details of the arbitration unit ARB for this system 
embodying the present system. The unit consists of two round-robin units 
RR1 and RR2. Unit RR1 has three ports A to C with the devices DEVA to DEVC 
coupled to them in the conventional way, and also has a fourth port X; 
unit RR2 has three ports D to F. 
For each of the ports D to F, the output from the round-robin unit passes 
through a respective one of a set of AND gates 10 to generate the grant 
signal for the respective device; the gates 10 are enabled by the output 
of the port X of unit RR1. The request signals to the ports D to F of unit 
RR2 are ANDed with the outputs from those ports by a set of three AND 
gates 11, the outputs of which are combined in an OR gate 12 to generate 
the input to port X of unit RR1. 
Unit RR2 receives its request signals RD to RF in the usual way, and 
produces a pre-grant output signal from the appropriate port in accordance 
with its cyclic sequence. Assume that at least one of the devices DEVD to 
DEVF is requesting bus access. The request signal from the currently 
chosen device is therefore ANDed with the pre-grant signal to that device 
to generate a true signal from one of the AND gates 11. This true signal 
passes through gate 12 to the request input of port X of unit RR1. (Block 
13 in the connection from gate 12 to the X port of unit RR1 should be 
ignored for the moment.) 
Unit RR1 cycles through the sequence ABCX. Since we are assuming that at 
least one of devices DEVD to DEVF is requesting bus access, signal RX will 
be true, and unit RR1 will therefore return signal GX as true in due 
course. This signal enables the AND gates 10, and therefore allows the 
pre-grant signal from unit RR2 to pass through and become the grant signal 
to the appropriate device. 
In due course, that device (one of DEVD to DEVF) will end its bus access, 
and its request signal will therefore go false. This will result in the 
request signal RX going false. Unit RR1 will therefore continue round its 
cycle, to devices A, B, and C. Unit RR2, in the meantime, will proceed 
round its cycle, to whichever of its requesting devices is next in cycle 
to be served, and issue the appropriate pre-grant signal. That will be 
combined with the corresponding request signal by the gates 11 and 12 to 
restore the request signal RX to unit RR1. However, unit RR1 will have 
moved on in its cycle, so unit RR2 will then remain quiescent until unit 
RR1 reaches port X again in its cycling. 
Obviously, if at any stage none of the devices DEVD to DEVF are requesting 
bus access, then signal RX will remain low, unit RR1 will skip past port X 
in its cycling, and unit RR2 will remain quiescent (remembering which of 
its devices it has reached in its cycling) until one of its devices 
requests bus access. 
The system thus grants bus access to the devices DEVA to DEVC in cyclic 
sequence, offering the opportunity of bus access to the devices DEVD to 
DEVF in cyclic sequence each time the ABC sequence cycles past C. Since 
the two round-robin units operate largely in parallel, the system can 
respond to requests within a single clock cycle, even when the sequence is 
changing from one of devices DEVA to DEVC to one of devices DEVD to DEVF 
(or back again). The bus is therefore fully utilised (unless all the 
devices happen to be idle, ie not requesting bus access). 
The effect of block 13 can now be considered. This block is shown as 
comprising a counter 14, fed from gate 12, which enables a gate 15, 
included between gate 12 and the input to port X of unit RR1. The counter 
14 is a cyclic counter, and gate 15 is enabled each time the counter 
cycles. Thus the rate at which requests from devices DEVD to DEVF are 
responded to is reduced by the count size of the counter. 
Block 13 may be modified by driving the counter by a signal (not shown) 
from unit RR1 instead of the signal from gate 12, so that the counter 
steps on each time unit RR1 cycles past gate X. This results in the 
response rate to devices DEVD to DEVF being controlled more by the 
activity of devices DEVA to DEVC than by the activity of devices DEVD to 
DEVF themselves. 
Block 13 may instead be modified by replacing the counter by a timer. The 
timer may be free-running, enabling and disabling gate 15 regularly. 
Alternatively, the timer may be reset eg each time the output signal GX 
goes true; it may either be free-running (to disable and then enable gate 
15 regularly after resetting) or one-shot (to hold gate 15 disabled for a 
given time after resetting). 
Turning now to the device assignment block DEV-ASS of FIG. 1, this is shown 
in more detail in FIG. 3. The request and grant lines RA, GA, etc of the 
devices DEVA, etc are converted by this block into modified request and 
grant lines MRA, MGA, etc of the ports of the arbitration unit ARB. The 
pairs of lines RA-GA, etc of the devices and the pair of modified lines 
MRA, MGA etc of the arbitrator ports are arranged in a matrix, with switch 
pairs SW at the intersections of the rows and columns. A device assignment 
memory ASS M controls the switch pairs SW, closing one switch pair in each 
row and column of the matrix. 
The device assignment memory is set to couple the devices to the ports of 
the two round-robin units in accordance with the characteristics of the 
various devices. Thus, if the ideal logical arrangement of the devices is 
as shown but their physical sequence is different, the device assignment 
memory would be set to achieve a logical re-arrangement of the devices. In 
particular, the device assignment unit permits the devices to be assigned 
to each of the two round-robin units in dependence on their 
characteristics; in the extreme, it allows all devices to be assigned to 
the same round-robin unit if they all have similar characteristics. 
The setting of the device assignment memory may be changeable, and may be 
driven on the identities of the devices (as indicated eg by their burnt-in 
electronic identifiers). Thus the numbers of devices attached to the two 
round-robin units can be changed, and a device can be moved from one 
round-robin unit to the other if the characteristics of the device are 
changed. 
The system has been shown as a pair of round-robin units, a device 
assignment unit, and some peripheral logic. It will be realised, however, 
that in practice the internal circuitry of the two round-robin units and 
the peripheral logic can in general be combined into a unitary logic 
system, which performs the same overall functions as the circuitry shown. 
The two round-robin units, in particular, can be regarded as state 
machines, with the interactions between the round-robin sequences included 
in the state machines. (A state machine is circuitry comprising a set of 
flip-flops and some combinative logic circuitry. The flip-flops implement 
a set of system `states`, and the combinative logic circuitry implements a 
set of transitions between those states under the control of external 
conditions (input signals).) In principle, the entire arbitration unit may 
be regarded as a single state machine, but it will generally be easier to 
divide it into two state machines corresponding generally to the two 
round-robin units.