Work conserving round robin arbiter

 
 
Integrated

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 indicates 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. Using a parallel prefix computation (PPC) speeds up the next granted requestor calculation and improves the circuit timing. This Component contains the verified verilog RTL code for a work conserving round robin arbiter, meaning there are no cycles spent on requestors that are inactive.

Work Conserving Round Robin 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 indicates 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 term “work conserving” refers to the ability of a round robin arbiter to skip requestors that do not have any data to process and move directly to the next requestor who has valid data to process. This method of arbitration is more efficient as it does not “waste” time on idle requestors. 

Block Diagram

The below block diagram shows the basic PPC based work conserving round robin arbiter and the pipeline version.

 

Work conserving round robin arbiter block diagram

 

Features

  • Work conserving round robin arbitration with equal share of the number of grants per all requestors
  • No time slots wasted on inactive requestors
  • ack signal, for downstream stall of the arbiter, the grant vector will change only if ack is asserted. For a new grant every cycle; the ack signal can be kept asserted.
  •  Fast parallel computation using Parallel prefix computation.
  • Valid output indicating the arbiter grant is valid.
  • Wrap around functionality, when the round robin reaches the last requestor, it will return to the requestors at the beginning without losing cycles.
  • Parameterized number of requestors, enabling flexibility in using the arbiter in different applications.
  • Parameterized output stage, providing either one-hot, binary decoded or thermometer decoded output for usage in different applications.

Optional Features

Optional features are available through different downloadable files

  • Pipeline integration support.
  • synchronous and asynchronous reset.

Product Deliverables

  • verified RTL code
  • Access to detailed design documentation
  • 1 year support and customization service.

 

Round Robin 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 indicates 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 cyclic counter. Alternatively, the arbiter can be 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. This type of round robin arbiter is referred to as a weighted arbiter where each requestor is assigned a predefined weight.

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 potential use for a round robin arbiter.

Work Conserving Round Robin

The term “work conserving” refers to the ability of a round robin arbiter to skip requestors that do not have any data to process and move directly to the next requestor who has valid data to process. This method of arbitration is more efficient as it does not “waste” time on idle requestors.

The work conserving round robin (WCRRB) arbiter is required to constantly look ahead into the next available requestors and enable the next valid requestor to be granted immediately after the current requestor is complete, including the cases of wrap around where requestors at the beginning of the list are to be granted right after those at the end of the list.

The function of looking constantly into all requests in order to calculate the next valid grant, may be costly in logic, and as the number of requestors get bigger, faster computation methods must be applied in order to meet timing and limit the size of the logic. Using parallel prefix computation algorithms enables faster logic and reduces overall arbiter complexity.

Parallel Prefix Computation (PPC)

Parallel prefix computation is a type of parallel calculation serving to reduce the number of stages it PPC parallel prefix OR computationtakes to calculate a function on multiple inputs by using parallel computations where possible. The example below is for an OR computation. The main feature of the OR PPC is to transform any vector into a thermometer decoded vector where all bits, starting from the first bit set are set. Once the computation is complete a simple bit compare will reveal the first-bit-set.

The OR parallel prefix computation enables the arbitration logic to find quickly the first request which is asserted, resulting in the ability to find the next valid requestor with the minimal possible logic cones.

The function of an OR PPC is demonstrated in the following table:

Request vector

PPC output

0001

1111

0010

1110

1100

1100

0100

1100

1000

1000

0011

1111

1001

1111

1110

1110

PPC Round Conserving Round Robin Arbiter

The usage of the PPC computation for a work conserving round robin is utilizing a mask to block the currently granted requestor, thus enabling the next selection of the PPC to indicate the next active requestor in line.

To generate the requestor ID from the PPC output vector the vector is binary decoded, resulting with the binary index of the granted requestor.

The arbiter also handles the wrap-around of the requesting vector. At some point, one of the highest bits in the requestor’s vector is selected and the next selection would have to be at the lower requestors.  The wrap-around operation is performed without loss of cycles, making the arbiter a true work-conserving arbiter.

The simple form of the work conserving round robin arbiter is well suited for fair arbitration between equal priority and equal processing time requestors, ensuring that the same number of grants will go to each valid requestor.

Pipeline PPC Work Conserving Round Robin Arbiter

The integration of a PPC round robin arbiter into a pipeline design is useful in many applications and requires the ability to stall the arbiter if the downstream logic is unable to handle the resulting grant.

The arbiter outputs would also indicate that the current result is valid. This would enable downstream logic to ignore the arbiter output in the situation where no requests are asserted.

There is one cycle delay between the assertion of a request and the grant for it, so the arbiter can be integrated into a design as a single pipe stage.

Parameters Table

parameters available for the WCRRB core.

Parameter

Valid values

description

WIDTH

>7

Number of requestors

OUTPUT_TYPE

0,1,2

0 – ceil (log(WIDTH)) binary encoded index of the     granted requestor.

1 -  WIDTH one-hot encoding of the granted requestor

2 – WIDTH thermometer encoding of the granted requestor, all bits lower than the selected are 0.

 

Interface Table

Signal name

Direction/width

description

clk

Input

Clock signal

resetb

Input

Active low reset signal.

ack

input

Indication that the previous grant has been consumed by the downstream logic and the arbiter may grant the next requestor.

request

Input [WIDTH – 1:0]

Request input vector

 

 

 

valid

Output

 

Indication that the current grant is valid and is a result of a valid requestor.

grant

Output [WIDTH – 1:0]

Grant output, either binary decoded, one-hot or thermometer selectable through the OUTPUT_TYPE parameter.

In case of binary decoding the width of the grant would be log2(WIDTH) rounded up.

 

Valid Signal Function

The purpose of the Arbiter valid signal is to enable downstream logic to distinguish between the case where no requests are asserted and the case where request 0 is asserted in a binary decoded arbiter. Those two cases would result in a binary decoded output of 0 and the valid bit would indicate that request 0 is granted. For pipeline integration, this signal may be used to indicate the validity of the arbiter pipeline stage.

Acknowledge Signal Function

The ack signal serves for stalling the arbiter in the case where downstream logic is unable to process the grant. This function enables the integration of the arbiter into flow controlled pipeline implementation.

Once the ack signal is asserted, the arbiter would mask the last granted request and look to the next active requestor. While the ack is de-asserted, the grant vector may change as request vector changes and more requests are asserted. Eventually, the grant that was present at the time the ack is selected.

Output Type

The arbiter can have three types of output, depending on the requirement of the surrounding logic.

A one-hot output type outputs a vector where only the bit associated with the selected requestor is asserted in the grant vector. The grant vector in this case would have the width of the request vector.

A binary decoded output would have the index of selected requestor, decoded using the number of bits required to decode the highest requestor number. The lowest requestor index is 0. Therefore, the valid bit should be used to determine if the arbiter output is valid.

The Thermometer decoding option would output a thermometer decoder vector. This can be used by downstream logic for further calculation or serve other scheduling schemes using this round robin arbiter.

Output Type

Parameter setting

description

Binary decoded

0

ceil (log(WIDTH)) binary encoded index of the granted requestor

One-hot

1

WIDTH one-hot encoding of the granted requestor

Thermometer

2

WIDTH Thermometer encoding of the granted requestor

 

Pipeline Integration

The arbiter can be integrated into a pipeline and serve as a single pipe stage. For that purpose, a sampling stage is integrated into the arbiter, along with the handling of the valid and ack signals in those conditions.

Typically the downstream logic would only assert ack if the valid is asserted, but a case where ack is constantly asserted while pipe is not stalled, waiting for the next grant is also possible.

 

 

Usability

The Work conserving round robin arbiter is designed to be used in the context of pipelined decision blocks and within multiple queue or FIFO systems where its advantages are:

  1. Enable fair arbitration, granting all requestors the same number of times.
  2. The pipelined version can be easily integrated into flow controlled, pipeline decision blocks.
  3. Simple integration into FIFO systems. See application note below.
  4. Fast PPC selection logic.

Care must be taken in the following issues:

1.    When the request vector is fast changing and has bits that get de-asserted, overall fairness may be compromised.

Integrating with a FIFO system

The typical usage of a round robin arbiter for a FIFO system with multiple FIFOs and an arbiter to select which of them will be extracted is implemented through the following connections:

  1. Connect the request vector to the ~empty or each of the FIFOs so when the FIFO is not empty, a request to the arbiter will be asserted.
  2. Connect a one-hot grant vector to the extract of the FIFOs. This would be masked with the downstream flow control signaling.
  3. Connect the arbiter ack signal to the downstream flow control signal so each time there is no flow control, the ack would be asserted providing that the arbiter valid is asserted.

 

More details can be found in the queuing component type where such a component can be found.

 

Test Items

the below table summarizes the test items that were checked for the Work conserving arbiter

Item name

Description

Reset functionality

Check reset assertion during operation, see that the mask returns to 0 and pipeline stages are cleared.

Single request

Assert each request separately, check for valid grant on the same requestor each cycle.

Request change while ack de-asseted

Check the case where ack is de-asserted and the request vector changes by applying requests of higher priority and de-asserting the current request check the output changes accordingly.

Low rate request

Check round robin functionality under low rate requests where all requests are de-asserted for periods and then resumed, see that round robin order is kept.

Constantly asserted ack

Check behavior under constantly asserted ack

Wrap around

Check wrap around case where highest request and lowest request are both asserted.

Statistics check

Running constant requests on all request bits and checking that over a long time the number of grants per each requestor is identical.

additional test items for pipeline functionality

Item name

Description

Fast alternating ack

Issue ack signal with many alternating changes.

Ack with no valid

issue ack with no valid asserted, check no impact on the mask vector.