Round robin arbitration

queuing FIFO and arbitration

Round robin arbitration is a scheduling scheme which gives to each requestor its share of using a common resource for a limited time or data elements. The basic algorithm implies that once a requestor has been serves he would “go around” to the end of the line and be the last to be served again. The simplest form of round robin arbiter is based on assignment of a fixed time slot per requestor; this can be implemented using a circular counter. Alternatively, the weighted round robin arbiter is defined to allow a specific number X of data elements per each requestor, in which case X data elements from each requestor would be processed before moving to the next one. Round robin arbiters are typically used for arbitration for shared resources, load balancing, queuing systems, and resource allocation. Any application requiring a minimal fairness where none of the requestors is suffering from starvation is a valid application for a round robin arbiter.

What is a round robin arbiter?

queueing FIFO and arbiterAn arbiter is a logical element serving to select the order of access to a shared resource. An arbiter would typically employ a scheduling algorithm to decide which one on several requestors would be serviced. The round robin arbitration, in its basic form, is a simple time slice scheduling, allowing each requestor an equal share of the time in accessing a memory or a limited processing resource in a circular order. For more complicated applications of round robin arbitration, such as packet switching, using a fixed time slice for each requestor is inefficient as the processing time of each data element, impacts the fairness of the arbitration. Therefore, there are several flavors of round robin arbitration, each suited for a different application.

Work conserving round robin arbitration

There are few widely used round robin algorithm variations that improve the fairness of arbitration or employ a defined priority scheme. The main limitation of the simple time slot allocation based round robin is the wasted time slots for requestors with no valid requests. The “work conserving” round robin scheme overcomes this limitation by skipping the inactive requests and only selecting in each round, between the active requestors. The work conserving round robin arbiter lets every active data flow that has data in the queue ready for sending to take turns in using a shared channel or processing unit in a circular order. The scheduling is work-conserving, meaning that if one flow is out of data to send, the next data flow will take its place, preventing shared resource down time. The challenge of work conserving arbiter logic design lies in the identification of the next active requestor and skipping inactive requestors with minimal logic and timing implications.

RTLery offers an efficient logic design implementation of a work conserving round robin arbiter RTL Verilog code which can be used as a reference design or for direct integration.

Weighted round robin arbiter

The weighted round robin (WRR) arbiter employs a mechanism for prioritizing the allocation of a shared resource, based on a relative “weight” given to each requestor. The option to assign weight for each of the requestors to the arbiter creates a priority between the requestors so that the ratio of processed data items from each requestor would be relative to its weight. For example a weight = 7 requestor will have 7 times more time slots than a weight = 1 requestor. This mechanism allows the prioritization of some data flows over others. The weighted round robin arbiter would allow X data items to be processed from each requestor, before moving to the next active one. Naturally, the “work conserving” functionality has to be kept, so inactive requestors would not be granted time slots.  

RTLery library offers a work conserving weighted round robin arbiter logic design and Verilog source code, verified and ready for integration.

 

Check out RTLery collection of verified RTL codes for arbiters

 

Subscribe to RTLery articles feed:

Leave a comment

Leave a comment