Apparatus and method for providing round-robin arbitration

The present invention relates to an apparatus and a method for providing round-robin arbitration between requests for access to a shared resource such as a data bus, shared by a plurality of hardware modules, as mentioned in the preamble of claims 1 and 11, respectively.

Arbitration systems of this kind are normally configured in a so-called master-slave configuration, in which a module seeking access to the shared resource sends a request to the master module and the master module controls the arbitration by polling, sending grant signals to the requesting modules in a round-robin scheme. Communication is only possible between the master and a slave, not between slaves.

From U.S. Pat. No. 5,072,363 a system providing round-robin arbitration between requests for access to a shared resource such as a data bus, shared by a plurality of hardware modules is known, said system comprising a central counter cyclically driven between multiple count states by a clock, each count state being associated with a request for access to the shared resource by one of the plurality of hardware modules. In this system, the arbiter receives each individual request for access to the shared resource on separate request lines connected between the arbiter and the modules. Correspondingly, the arbiter grants access to the shared resource via separate grant lines connected between the arbiter and the modules. This involves at least two lines between the arbiter and each of the hardware modules. Furthermore, the arbitration is performed using a programmable array logic and a bus arbitration module and programming of the programmable array logic and the setup of input/output lines have to be individually adapted in accordance with the number of modules involved in each individual case, thereby reducing the flexibility of the system.

EP-0,286,235 describes arbitration in which the bus controller issues a “send” command and an “address” on the bus to be shared by the processors and the addressed processor responds by using the bus or by sending a NACK-signal on the bus. The processor has only access to the bus for a predetermined limited time period. Thus, this arbitration system is totally unsuited for controlling the access to e.g. a serial HDLC-bus, in which the time needed for sending an HDLC-frame can be considered stochastic.

It is the object of the present invention to provide an apparatus and a method of the above kind, which is of simple construction. This object is achieved with an apparatus as stated in claim 1 and a method as stated In claim 11. Hereby it is achieved that the arbitration can be implemented using a simple construction, including a simple counter, simple comparators and simple gates. Preferred embodiments of the invention are revealed in the sub-ordinate claims.

In the following detailed part of the description, the Invention will be explained in more detail with reference to the exemplary embodiments of an apparatus and a method in accordance with the invention shown in the drawings, in which

FIG. 1 shows an arbitration system for shared access to a HDLC data bus, and

FIG. 2 shows a typical sequence of signals in the system shown in FIG. 1 .

The arbitration apparatus shown in FIG. 1 comprises a N-bit counter 1 cyclically driven between multiple count states by a clock supplied to the counter via a gate 2 , which will be described in more detail in the following. The N-bit output from the counter 1 is supplied to an arbitration bus with N-lines connected in parallel to all of the hardware modules sharing the shared resource which in the example is a HDLC-bus. Each of the modules comprises a comparator 4 for comparing the address set on the arbitration bus with its own address and the output from the comparator 4 is used to enable an internal grant signal G i and an external request signal R, respectively, whenever an internal request signal R i is set in the module in order to get access to the shared resource, i.e. the HDLC bus. The enabling of the grant and request signals, respectively, can be implemented using simple gates and the external request signal R is sent back to the gate for controlling the clock to the counter via an external request line connected in parallel to all of the modules. The gate 2 for controlling the clock for the counter 1 enables the externally supplied clock for counting as long as the external request signal is not activated by any of the modules. As soon as one of the modules, upon receipt of its own address on the arbitration address bus, activates the external request signal R, the clock to the counter is disabled and kept disabled until the module de-activates the external request signal R, by deactivating the internal request signal R i , upon completion of its access to the shared resource.

In the embodiment shown, the shared resource is a serial HDLC communication bus and the receiving module is able to return handshake signals to the transmitting module via separate lines for acknowledge ACK, negative acknowledge NACK and not ready to receive NR. These signals are returned to the transmitting module to inform the transmitter about the success of the transmission of data on the HDLC bus. The access to the HDLC bus is not completed until these handshake signals are received back from the receiving module and accordingly, the transmitting module does not deactivate its request signal until such handshake signals are received. The protocol for access to the bus is preferably such that the transmitting module deactivates the request signal no matter what type of handshake signal is received and accordingly wait a certain period of time before trying to retransmit data which have not been properly received by the receiver.

FIG. 2 shows a typical sequence of signals in the system shown in FIG. 1 . From top to bottom the signals are as follows:

a) clock signal,

b) count state on bus 3 from counter 1 ,

c) external request signal R activated by any of the modules and disabling the clock C to the counter 1 by means of the gate 2 ,

d) internal request signal R i in the module with the own address 9 ,

e) symbolic representation of the data signal on the HDLC bus 7 ,

f) symbolic representation of any of the signals ACK, NACK and NR,

g) internal request signal R i from the module with the internal address 10 .

In the situation sketched in FIG. 2, modules nos. 9 and 10 have data ready for transmission on the HDLC data bus and accordingly, these modules have set their internal request signals R i active. Starting from the left, the counter 1 is in the count state corresponding to the address 7 and counts on to addresses 8 and reaches 9 , at which point of time the gate 6 in the module with the address 9 is enabled when the comparator 4 detects the address 9 on the counter state bus 3 from the counter. This enables the external request signal R which via the gate 2 disables the clock signal C to the counter 1 . At the same time the gate 5 gets an internal grant signal G i to the module no. 9 whereby the module no. 9 starts sending data via the HDLC bus 7 . When the module 9 has finished its data transmission on the HDLC bus 7 , the HDLC controllers in the receiving module generate end of message interrupt and the receiver unit activates one of the lines ACK, NACK or NR to indicate the success or failure of receiving the data. The module no. 9 detects the activation of one of these handshake signals and following deactivates its internal request R i , thereby deactivating the external request signal R, whereby the counter 1 resumes its counting and counts onwards to the address 10 . The internal request signal R i is active in the module no. 10 and accordingly, this module sets the external request signal active when receiving the address 10 on the count state bus 3 from the counter. After this, the module no. 10 sends data on the HDLC bus 7 as just described for module no. 9 .

As can be seen, the system in accordance with this embodiment provides equal access to the HDLC bus for each of the modules and a standard HDLC controller can be used to control the access to this HDLC bus with very simple external logic circuits.

Although the above system has been described with separate lines for the handshake signals, it is possible to use a software protocol for sending these handshake signals in separate frames on the HDLC bus, but this will naturally reduce the available bandwidth on the bus. Correspondingly, the external request signal may be sent back to the counter system using the HDLC bus, but this will increase the number of clocks necessary for polling each unit and consequently, also reduce the available bandwidth on the bus.

The invention has mainly been developed in order to provide a round-robin arbitration between loosely coupled hardware modules in a computer or digital telephone exchange, but a man skilled in the art will be able to make the necessary modifications in order to use the invention in many other situations where several hardware modules share a common resource.

The own address for each of the modules may naturally be allocated in accordance with the slot number in which an insert is inserted in a system, but may also be set in any other way, e.g. manually by means of dip-switches in each module.