A Round-Robin Arbiter

by GateForge Consulting Ltd.

We can use a round-robin arbiter to manage access to a shared resource, providing maximum access when there is only one active requestor, and equal shared access when there are multiple active requestors, without having to check each requestor in turn for activity, which would waste cycles better given to active requestors. For example:

Requests     Grants
--------     ------
01101    --> 00001
01100    --> 00100
01001    --> 01000
00001    --> 00001

Here, we will implement a "mask method" round-robin arbiter, as described in Section 4.2.4, Figure 12 of Matt Weber's Arbiters: Design Ideas and Coding Styles. Our implementation makes use of our previously created priority arbiter and priority thermometer mask modules.

Internally, this round-robin arbiter uses a priority arbiter, but also generates a mask that blocks request of lower priority than the currently granted request, forcing the requests to be granted from right-to-left. As in the example above, if a higher-priority request shows up later, it will not take priority over the currently granted request. Once the masked set of requests becomes empty, we reinitialize the process by looking at the raw requests instead. The raw requests are processed in parallel by a second priority arbiter.

// Returns a single bit set from all set request bits, in a round-robin order
// going from LSB to MSB and back around. Requests can be added or dropped
// on-the-fly, but synchronously to the clock.

module Round_Robin_Arbiter
#(
    parameter WORD_WIDTH                = 0
)
(
    input   wire                        clock,
    input   wire    [WORD_WIDTH-1:0]    requests,
    output  reg     [WORD_WIDTH-1:0]    grant
);

    initial begin
        grant = 0;
    end

    localparam zero = {WORD_WIDTH{1'b0}};

// --------------------------------------------------------------------

    // Grant a request in priority order (LSB has higest priority)

    wire [WORD_WIDTH-1:0] grant_raw;

    Priority_Arbiter
    #(
        .WORD_WIDTH (WORD_WIDTH)
    )
    Raw
    (
        .requests   (requests),
        .grant      (grant_raw)
    );

// --------------------------------------------------------------------

    // Mask-off all requests of higher priority 
    // than the request granted in the previous cycle.

    wire [WORD_WIDTH-1:0] mask;

    Thermometer_Mask
    #(
        .WORD_WIDTH (WORD_WIDTH)
    )
    Grant
    (
        .bitvector  (grant),
        .mask       (mask)
    );

    reg [WORD_WIDTH-1:0] requests_masked;

    always @(*) begin
        requests_masked = requests & mask;
    end

// --------------------------------------------------------------------

    // Grant a request in priority order, but from the masked requests
    // (equal or lower priority to the request granted last cycle)

    wire [WORD_WIDTH-1:0] grant_masked

    Priority_Arbiter
    #(
        .WORD_WIDTH (WORD_WIDTH)
    )
    Masked
    (
        .requests   (requests_masked),
        .grant      (grant_masked)
    );

// --------------------------------------------------------------------

    // If no granted requests remain after masking, then grant from the
    // unmasked requests, which starts over granting from the highest (LSB)
    // priority. This also resets the mask. And the process begins again.

    always @(posedge clock) begin
        grant <= (grant_masked == zero) ? grant_raw : grant_masked; 
    end

endmodule

However, this round-robin arbiter does not deal with the more complex issue of fairness. For example, it's possible that under normal operation, one requestor ends up placing a request always just before the previous requestor finishes. Thus, that new request waits less than the others. One solution periodically takes a snapshot of the current pending requests, and services all of these requests before refreshing the snapshot.


fpgacpu.ca