Chirag's Blog: Inter Processor Arbitration in Multiprocessor

Inter Processor Arbitration

The processor, main memory and I/O devices can be interconnected by means of a common bus. A bus is set of lines (wires) defined to transfer all bits of a word from a specified source to a specified destination. Thus, bus provides a communication path for the transfer of data.

The bus includes data lines, address lines and control lines. Such a bus known as system bus. Different types of arbitration: Serial (Daisy Chain) arbitration, Parallel arbitration, Dynamic arbitration

Serial (Daisy Chain) arbitration

In this type of arbitration, processors can access bus based on priority. In serial arbitration, bus access priority resolving based on the serial connection of the processors. This technique is obtained from daisy chain (serial) connection of processors. The serial priority resolving technique is obtained from daisy-chain connection similar to the daisy chain priority interrupt logic. The processors connected to the system bus are assigned priority according to their position along the priority control line.

Figure : Serial (Daisy Chain) Arbitration

When multiple devices concurrently request the use of the bus, the device with the highest priority is granted access to it. Each processor has its own bus arbiter logic with priority-in and priority-out lines. The priority out (PO) of each arbiter is connected to the priority in (PI) of the next-lower-priority arbiter. The PI of the highest-priority unit is maintained at a logic value 1. The highest-priority unit in the system will always receive access to the system bus when it requests it. The processor whose arbiter has a PI = 1 and PO = 0. That processor accesses the system bus.

Advantages

Simple and cheaper method

Least number of lines.

Disadvantages

Higher delay

Priority of the processor is fixed

Not reliable

Parallel Arbitration

In this technique uses an external priority encoder and decoder as shown in figure below. Each bus arbiter in the parallel scheme has a bus request output line and a bus acknowledge input line. When processor wants to access system bus at that time arbiter of that processor enables request line. The processor takes control of the bus if it acknowledges input line is enabled.

Figure : Parallel Arbitration

Figure shows the request lines from four arbiters going into a 4 x 2 priority encoder. The output of the encoder generates a 2-bit code, which represents the highest-priority unit among those requesting the bus. The 2-bit code from the encoder output drives a 2×4 decoder which enables the proper acknowledge line to grant bus access to the highest-priority unit. It works on priority encoder truth table.

Advantage

Separate pair of bus request and bus grant signals, so it is faster.

Disadvantage

Require more bus request and grant signal.

Dynamic Arbitration

Discussed two bus arbitration procedures use a static priority algorithm. The priority of each device is fixed by the way it is connected to the bus. In contrast, a dynamic priority algorithm gives the system the capability for changing the priority of the devices while the system is in operation. Few dynamic arbitration procedures that use dynamic priority algorithms: Time Slice, Polling, LRU, FIFO

Time Slice: In this algorithm allocates a fixed-length time slice of bus time that is offered to each processor in sequentially manner, in round-robin fashion. The service provide to each processor with this scheme is independent of its location along the bus. No preference is given to any particular device since each is allotted the same amount of time to communicate with the bus.

Polling: In a bus system that uses polling, the bus-grant signal is replaced by a set of lines called poll lines, which are connected to all units. Poll lines are used by the bus controller to define an address for each device connected to the bus. The bus controller, arrange address in a sequence through prescribed manner. When a processor that recognizes its address, it activates the bus busy-line and then accesses the bus. After a number of bus cycles, the polling process continues by choosing a different processor. The polling sequence is normally programmable, and as a result, the selection priority can be randomly under program control.

LRU: The LRU (least recently used) algorithm gives the highest priority to the requesting device that has not used the bus for the longest interval. The priorities are adjusted after a number of bus cycles according to the LRU algorithm. With this procedure, no processor is favoured over any other since the priorities are dynamically changed to give every device an opportunity to access the bus.

FIFO: In the first-come, first-serve scheme, requests are served in the order received. To implement this algorithm, the bus controller establishes a queue arranged according to the time that the bus requests arrive. Each processor must wait for its turn to use the bus on a first-in, first-out (FIFO) basis.

Advantages

The priority can be changed by altering the sequence stored in controller.

More reliable.

To learn more about Inter Processor Arbitration, watch below video