Inter processor Arbitration

1. Computer systems contain a number of buses at various levels to facilitate the transfer of information between components. 
2. The CPU contains a number of internal buses for transferring information between processor registers and ALU. 
3. A memory bus consists of lines for transferring data, address, and read/write information. 
4. An I/O bus is used to transfer information to and from input and output devices. 
5. A bus that connects major components in a multi-processor system, such as CPUs, lOPs, and memory, is called a system bus. 
6. The processors in a shared memory multiprocessor system request access to common memory or other common resources through the system bus. 
7. If n other processor is currently utilizing the bus, the requesting processor may be granted access immediately. 
8. However, the requesting processor must wait if another processor is currently utilizing the system bus. Furthermore, other processors may request the system bus at the same time. 
9. Arbitration must then be performed to resolve this multiple contention for the shared resources.
   The arbitration logic would be part of the system bus controller placed between the local bus and the system bus as shown in figure below.

System Bus

A typical system bus consists of approximately 100 signal lines. These lines are divided into three functional groups: data, address, and control. In addition, there are power distribution lines that supply power to the components. For example, the IEEE standard 796 multibus system has 16 data lines, 24 address lines, 26 control lines, and 20 power lines, for a total of 86 lines.

Data transfers over the system bus may be synchronous or asynchronous.

In a synchronous bus, each data item is transferred during a time slice known in advance to both source and destination units; synchronization is achieved by driving both units from a common clock source. An alternative procedure is to have separate clocks of approximately the same frequency in each unit. Synchronization signals are transmitted periodically in order to keep all clocks asynchronous bus in the system in step with each other.

In an asynchronous bus, each data item being transferred is accompanied by handshaking control signals to indicate when the data are transferred from the source and received by the destination.

Serial Arbitration Procedure

Arbitration procedures service all processor requests on the basis of established priorities. A hardware bus priority resolving technique can be established by means of a serial or parallel connection of the units requesting control the system bus. The serial priority resolving technique is obtained from daisy-chain connection of bus arbitration circuits similar to the priority interrupt logic.

The processors connected to the system bus are assigned priority according to their position along the priority control line. The device closest to the priority line is assigned the highest priority. When multiple devices concurrently request the use of the bus, the device with the highest priority is granted access to it.

It is assumed that 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 PO output for a particular arbiter is equal to 1 if its PI input is equal to 1 and the processor associated with the arbiter logic is not requesting control of the bus.

This is the way that priority is passed to the next unit in the chain. If the processor requests control of the bus and the corresponding arbiter finds its PI input equal to 1, it sets its PO output to 0. Lower-priority arbiters receive a 0 in PI and generate a 0 in PO. Thus the processor whose arbiter has a PI = 1 and PO = 0 is the one that is given control of the system bus.

A processor may be in the middle of a bus operation when a higher priority processor requests the bus.
The lower-priority processor must complete its bus operation before it relinquishes control of the bus. 

The bus busy line shown in Fig. below provides a mechanism for an orderly transfer of control. The busy line comes from open-collector circuits in each unit and provides a wired-OR logic connection. When an arbiter receives control of the bus (because its PI = 1 and PO = 0) it examines the busy line.

 If the line is inactive, it means that no other processor is using the bus. The arbiter activates the busy line and its processor takes control of the bus. However, if the arbiter finds the busy line active, it means that another processor is currently using the bus. 

The arbiter keeps examining the busy line while the lower-priority processor that lost control of the bus completes its operation. When the bus busy line returns to its inactive state, the higher-priority arbiter enables the busy line, and its corresponding processor can then conduct the required bus transfers.

Advantages

1. Simple and cheaper method
2. Least number of lines.
   

Disadvantages

1. Higher delay
2. Priority of the processor is fixed
3. Not reliable

 Parallel Arbitration Logic

The parallel bus arbitration 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. Each arbiter enables the request line when its processor is requesting access to the system bus. The processor takes control of the bus if its acknowledge input line is enabled. The bus busy line provides an orderly transfer of control, as in the daisy-chaining case.

Figure above 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.

Advantage

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

Disadvantage

1. 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

1. The priority can be changed by altering the sequence stored in controller.
2. More reliable.