Returns a one-hot grant bitmask selected from one of the raised request bits in a word, in round-robin order, going from least-significant bit (highest priority) to most-significant bit (lowest priority), and back around. A grant is held until the request is released.
Unset request bits are skipped, which avoids wasting time. Requests can be
raised or dropped before their turn comes, but this must be done
synchronously to the clock. Grants are calculated combinationally from the
requests, so pipeline as necessary. If the requests_mask bit
corresponding to a requests bit is zero, then that request cannot be
granted that cycle. The round-robin always continues from the last granted
request, even after an idle period of no requests, unless clear is
asserted.
A common use-case for an arbiter is to drive a one-hot
multiplexer to select one of multiple senders
requesting for one receiver, or one of multiple receivers requesting from
one sender. This arrangement requires that the requestors can raise and
hold a requests bit, wait until they receive the correspondig grant bit
to begin their transaction, and to drop their requests bit only once they
are done. This is very similar to a ready/valid handshake, except that the
transaction cannot be interrupted, else the granted access is lost.
Here, we 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.
A round-robin arbiter is commonly used to fairly divide a resource amongst multiple requestors, in proportion to each requestor's activity, since each requestor holds a grant until they lower their request. Idle requestors don't use up any of the arbitrated resource. A frequent requestor will not obstruct other requestors perpetually.
However, this round-robin arbiter does not deal with some subtleties 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.
To enable the creation of custom fairness adjustments, the requests_mask
input can be used to exclude one or more requests from being granted in the
current cycle, and must be updated synchronously to the clock. The
requests_mask is arbitrary, and if desired can be calculated from the
current requests, the grant_previous one-hot output which always holds
the last given grant even if the requests are currently all idle, and the
current one-hot grant output.
requests_mask is a valid option.requests_mask is applied combinationally to the requests input
and to the internal round_robin_mask, both of which have a combinational
path to grant, so pipeline as necessary. If unused, leave requests_mask set to all-ones, and the masking logic
will optimize away.
`default_nettype none
module Arbiter_Round_Robin
#(
parameter INPUT_COUNT = 0
)
(
input wire clock,
input wire clear,
input wire [INPUT_COUNT-1:0] requests,
input wire [INPUT_COUNT-1:0] requests_mask, // Set to all-ones if unused.
output wire [INPUT_COUNT-1:0] grant_previous,
output reg [INPUT_COUNT-1:0] grant
);
localparam ZERO = {INPUT_COUNT{1'b0}};
initial begin
grant = ZERO;
end
We need to detect if any requests are active: when all requests go idle, we want to remember the last granted request. Otherwise, that lost state means the round-robin restarts from the highest priority request rather than the next lower priority request after the last granted request.
Always granting the highest priority first after an idle period allows a pathological request pattern to cause starvation: all but the highest priority request would starve if they keep asserting and de-asserting in lock-step after an idle period.
reg any_requests_active = 1'b0;
always @(*) begin
any_requests_active = (requests != ZERO);
end
For the same reasons, we need to detect when we leave an idle request period so we can, for that cycle, refuse to grant again the last granted request, which would otherwise cause starvation of other requests happening in lock-step.
wire out_from_idle;
Pulse_Generator
requests_restart
(
.clock (clock),
.level_in (any_requests_active),
.pulse_posedge_out (out_from_idle),
// verilator lint_off PINCONNECTEMPTY
.pulse_negedge_out (),
.pulse_anyedge_out ()
// verilator lint_on PINCONNECTEMPTY
);
Grant a request in priority order (LSB has higest priority) after applying
requests_mask. This is the base case which starts the round-robin.
reg [INPUT_COUNT-1:0] requests_masked_priority = ZERO;
always @(*) begin
requests_masked_priority = requests & requests_mask;
end
wire [INPUT_COUNT-1:0] grant_priority;
Bitmask_Isolate_Rightmost_1_Bit
#(
.WORD_WIDTH (INPUT_COUNT)
)
priority_grants
(
.word_in (requests_masked_priority),
.word_out (grant_priority)
);
Mask-off all requests of equal and higher priority than the request
currently granted, from the previous cycle. This masking makes the
round-robin progress towards lower priority requests as the previously
granted higher priority requests are released. The thermometer_mask must
be inverted before use.
wire [INPUT_COUNT-1:0] thermometer_mask;
Bitmask_Thermometer_to_Rightmost_1_Bit
#(
.WORD_WIDTH (INPUT_COUNT)
)
grant_mask
(
.word_in (grant_previous),
.word_out (thermometer_mask)
);
reg [INPUT_COUNT-1:0] round_robin_mask = ZERO;
always @(*) begin
round_robin_mask = ~thermometer_mask;
end
The round_robin_mask excludes the currently granted request, which we
don't want to interrupt, so we OR the currently granted request bit into
the round_robin_mask so we only mask-off all higher priority requests,
leaving the currently granted request as highest priority.
EXCEPTION: If we are returning from an all-idle request phase, we
instead zero-out that granted request bit, so the round-robin can resume to
the next lower priority request based on the round_robin_mask, instead of
possibly re-granting the same request again.
The round_robin_mask is further masked, in the same manner, by the
requests_mask input, which may prevent the granting of some requests of
lower priority after the currently granted request is released.
reg [INPUT_COUNT-1:0] requests_masked_round_robin = ZERO;
reg [INPUT_COUNT-1:0] grant_previous_gated = ZERO;
always @(*) begin
grant_previous_gated = (out_from_idle == 1'b1) ? ZERO : grant_previous;
requests_masked_round_robin = requests & (round_robin_mask | grant_previous_gated) & (requests_mask | grant_previous_gated);
end
Grant a request in priority order, but from the round-robin masked
requests, which only contain requests of equal or lower priority to the
currently granted request, minus any requests further masked by the
requests_mask input.
wire [INPUT_COUNT-1:0] grant_round_robin;
Bitmask_Isolate_Rightmost_1_Bit
#(
.WORD_WIDTH (INPUT_COUNT)
)
round_robin_grants
(
.word_in (requests_masked_round_robin),
.word_out (grant_round_robin)
);
If no round-robin granted requests remain, then instead grant from the
priority requests, which starts over the round-robin at the highest
priority (LSB) request. This also resets round_robin_mask.
always @(*) begin
grant = (grant_round_robin == ZERO) ? grant_priority : grant_round_robin;
end
Remember the last granted request so we can compute round_robin_mask to
exclude higher priority requests than the last granted request. If all
requests go idle, don't update, so we can continue the round-robin from
where we left off when requests appear again, to avoid starvation of lower
priority requests.
Register
#(
.WORD_WIDTH (INPUT_COUNT),
.RESET_VALUE (ZERO)
)
previously_granted_request
(
.clock (clock),
.clock_enable (any_requests_active),
.clear (clear),
.data_in (grant),
.data_out (grant_previous)
);
endmodule