Weighted round robin multi fifo queuing

 
 
Verified

A queuing structure is based on a set of FIFOs, storing data from different sources and an arbitration mechanism selecting the most suitable requestor according to a predefined algorithm. This component implements a queuing system based on FIFOs and a weighted round robin arbitration scheme. The typical usage of this queuing structure is to buffer data from multiple sources, select the highest priority and drive it to a shared resource such as a communication link or processing unit. This component contains the verified RTL Verilog code of the FIFO structure and a round robin arbiter.

block diagram

queuing block diagram

 

Features

·         Weighted Work conserving Round robin arbitration based on parallel prefix computation (PPC).

·         Parameterized number of FIFOs

·         Valid indication for output validity, usable for pipeline integration.

·         Parameterized FIFO width and depth.

·         Acknowledge signal for flow control, enables downstream logic to stall the arbitration.

·         Generic registers based FIFOs

Optional Features

Optional features are available through different downloadable files

·         Synchronous and asynchronous reset

Deliverables

·         verified RTL code

·         Access to detailed design documentation

·         1 year support and customization service.

parameters table

Parameter

Valid values

description

FIFOCNT(NOQ)

>7

Number of FIFOs in the queuing system

WIDTH

any

FIFO width

DEPTH

any

FIFO depth

WEIGHT_S

any

the width of the weight vectors for the arbitration

Interface table

Signal name

Direction/width

description

clk

Input

Clock signal for main domain A, free running clock, needs to toggle for proper functionality

Datain[NOQ – 1:0]

Input [WIDTH -1:0]

input data bus for FIFOs, built as a concatenation of the input vectors per FIFO.

resetb

Input

Active low reset signal, when asserted, mask would be set 0.

ack

input

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

valid

Output

 

Indication that the current output is valid and is a result of a valid non-empty FIFO.

fifoload

Input [NOQ – 1:0]

Request input vector, width of the vector is the number of queues.

Fifofull

Output [NOQ – 1:0]

Fifo full indication for upstream flow control

Weight[NOQ – 1:0]

Input [WEIGHT_S – 1:0]

The number of weight vectors is equal to the number of requests excluding all 0. A requestor with priority 0 would be ignored. The WEIGHT_S parameter is the width of the individual weight input vectors where the Weight vector is a concatenation of the per FIFO weight.

Dataout

Output [WIDTH -1:0]

Output data bus, according to the arbiter selection.

Functionality

The queuing system contains multiple FIFOs and an arbitration module enabling weighted work conserving round robin arbitration. Each FIFO will get his share of the output according to his relative weight. Empty FIFO will inevitably create discrepancies to this fairness rule. Weight example:

Weight

Number of transactions

1

105

3

315

4

420

Several flows of data from different sources can share a common resource according to a predefined weight, allowing priority among them according to their relative weight.

generic FIFO

A “generic FIFO” is a reference name to the simple type of synchronous FIFOs, where the memory array is based of flip-flops and the pointers and status (full, empty, almost full etc.) are generated using counters or pointers logic.

The load and extract operations of the FIFO impact the FIFO pointers.

When the load signal is asserted, the data on the FIFO datain is loaded into the position pointed by the write pointer and the pointer is then incremented by 1 to point to the next FIFO entry.

If the FIFO full indication is asserted, and the extract signal is not asserted, the load operation would be ignored and the pointer would not be incremented. More details about the generic FIFO can be found here

Valid signal

The purpose of the valid signal is to enable downstream logic to identify the case where no FIFO contains data, so pipeline integration can be achieved.

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 in flow controlled pipeline implementation the arbiter would stall on its latest granted FIFO while ack is de-asserted and continue once it is asserted again.

Weight logic

The weight of each FIFO is actually the maximal number of grants the FIFO will receive in the current round. If the request signal is de-asserted, the arbiter would skip to the next FIFO with valid entries.

A weight of 0 serves to mask off the FIFO, indicating to the arbiter that this FIFO is to be ignored.

The weight of multiple requestors may be identical and not all weight options must be used.

The minimal weight used, is a weight of 1 so each valid requestor would have at least one grant before it is blocked by the weight logic.

The weight can be changed during the arbitration and the change will take effect in the next time the FIFO is selected by the arbiter.

PPC Work conserving round robin arbiter

Using the PPC computation for a work conserving round robin uses a mask to block the currently granted requestor, enabling the next selection of the PPC to indicate the next requestor in line.

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.

More details about the weighted round robin arbiter can be found here

Reset

The control logic for the FIFO and arbitration is logic is either asynchronous or synchronous depending on the reset policy of the instantiating device.

Test Items

the below table summarizes the test items that were checked  for the different decoders

Item name

Description

Check resulting arbiter distribution

Run many requests where all FIFOs have constant valid entries. See that the relative number of grants fit the weight  definition

Use same weight for all

Check for equal distribution

Slow FIFO

aFIFO gets empty, de-asserting a request so it cannot fill its allocated weight, see no effect on rest of requestors

Use weight 0

See that the FIFO is ignored

Use constantly asserted ack

Check distribution is according to weight

FIFO full

Check FIFO drops new entry when loaded and full

 

 

 

Usability

A queuing multi-FIFO structure can be used for applications such as networking, memory subsystem access, table query access and more.