by Although it is simple, fixed priority arbiters may cause starvation across different requests. To guarantee fairness, designers usually use round-robin arbiter. We will start from a wrong design, in order to enhance your understanding of round-robin; then we will cover the right design, that can guarantee fairness under all conditions.
The Wrong Round-Robin Arbiter Design
Assume the design takes 3 requests, i.e., req[2:0].
Internally, this design keeps a 3-bit history array, i.e., token[2:0]. Token[2:0] is a one-hot array initialized to 3’b001, and it circular left shifts 1 bit every time there are valid requests. The way the design works:
- If token[2:0] == 3’b001, then req[0] has highest priority while req[2] has the lowest priority;
- If token[2:0] == 3’b010, then req[1] has highest priority while req[0] has lowest priority;
- If token[2:0] == 3’b100, then req[2] has highest priority while req[1] has the lowest priority
The Verilog code is shown below.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
module rrb_arb_wrong ( input clk, input rst_n, input [2:0] req, output logic [2:0] grant ); logic [2:0] token; // token update logic always_ff @(posedge clk or negedge rst_n) if (~rst_n) token <= 3'b001; else if (|req) if (token == 3'b100) token <= 3'b001; else token <= (token << 1'b1); // grant generation always_comb begin grant = '0; case (token) 3'b001: begin if (req[0]) grant = 3'b001; else if (req[1])grant = 3'b010; else if (req[2])grant = 3'b100; end 3'b010: begin if (req[1]) grant = 3'b010; else if (req[2])grant = 3'b100; else if (req[0])grant = 3'b001; end 3'b100: begin if (req[2]) grant = 3'b100; else if (req[0])grant = 3'b001; else if (req[1])grant = 3'b010; end endcase end endmodule: rrb_arb_wrong |
If every cycle, all 3 requests are asserted, then this design guarantees fairness across all 3 requests. If, however, only req[2] and req[0] are asserted every cycle, then fairness across req[2] and req[0] breaks:
- @cycle0 token[2:0] == 3’b001, then req[0] gets granted;
- @cycle1 token[2:0] == 3’b010, then req[2] gets granted;
- @cycle2 token[2:0] == 3’b100, then req[2] gets granted again.
Req[0] gets granted once but req[2] gets granted twice for every 3 cycles.
The Right Round-Robin Arbiter Design
Again we assume the round robin arbiter design takes 3 requests, i.e., req[2:0].
Internally, it keeps a 3-bit mask array, i.e., mask[2:0], and it is initialized to 3’b111. The way that the mask gets updated is:
- If req[0] is granted, then mask[2:0] becomes 3’b110 and req[0] will be masked in next cycle;
- If req[1] is granted, then mask[2:0] becomes 3’b100 and req[1:0] will be masked in next cycle;
- If req[2] is granted, then mask[2:0] becomes 3’b000 and all requests are masked in next cycle.
If not all requests are masked out in current cycle, i.e., mask[2:0] != 3’b000, then we use fixed priority arbiter to grant the masked requests; If all requests are masked in current cycle, i.e., mask[2:0] == 3’b000, then we use a simple fixed priority arbiter to grant the raw requests.
The Verilog code is shown below.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
module rrb_arb ( input clk, input rst_n, input [2:0] req, output logic [2:0] grant ); logic [2:0] mask; logic [2:0] mask_req; logic [2:0] raw_grant; logic [2:0] mask_grant; // mask update logic always_ff @(posedge clk or negedge rst_n) if (~rst_n) mask <= 3'b111; else if (grant[0]) mask <= 3'b110; else if (grant[1]) mask <= 3'b100; else if (grant[2]) mask <= 3'b000; // masked requests assign mask_req = req & mask; // grant for raw requests in case mask == 3'b000 fixed_prio_arb u_arb_raw (.req(req), .grant(raw_grant)); // grant for masked requests in case mask != 3'b000 fixed_prio_arb u_arb_mask (.req(mask_req), .grant(mask_grant)); // final grant assign grant = (mask_req == 3'b000) ? raw_grant : mask_grant; endmodule: rrb_arb |
It is obvious that this design can guarantee fairness even when not all requests are asserted. For example, only req[2] and req[0] are asserted:
- If @cycle0 mask[2:0] = 3’b111, then req[0] is granted;
- @cycle1 mask[2:0] == 3’b110, and req[2] is granted;
- @cycle2 mask[2:0] == 3’b000, and req[0] is granted;
- @cycle3 mask[2:0] == 3’b110, and req[2] is granted.
Req[0] and req[2] always get granted 50% of the time, respectively.
How to verify the fairness of a round-robin arbiter
A commonly interview question is, how to verify the fairness of a round-robin arbiter. Here we show 3 approaches:
- “Coloring” the data pattern for each request, so that testbench can identify which source the data comes from. At the end of the test, count how many requests are granted for each source.
- Associate a counter for each request, to keep track of how many requests are granted for each source.
- Associate a timing counter for each request, to track how long since the last time the request gets granted. If certain timing counter exceeds a threshold, we can conclude the fairness is broken
Conclusion
Round robin is a simple but effect arbitration scheme, and it established the baseline for weighted round robin arbiter, which we will cover in next post.
In following example, request 0 gets starvation even if we use the right round robin:
req = 100 & mask= 111 => grant = 100
req = 010 & mask= 000 => grant = 010
req = 111 & mask= 100 => grant = 100, while grant should be given to request 1 (grant=001). So, request 1 gets starvation
Hi David, you asked a very interesting question. Round-robin guarantees fairness over long period of time, instead of momentarily. In your case, req 1 will be granted in the next cycle, so there is no actual starvation.
I think you might be confused about the difference between round-robin and least recently granted. To grant request 1 as soon as it shows up, you’ll need least recently granted arbiter, instead of round-robin arbiter.
Thanks for the post!
Question on a specific case.
mask = 3’b110; (or even 3’b100)
req = 3’b001;
mask_req = 3’b000;
Since the mask is non-zero but the mask_req is zero, the arbiter will not grant req[0] until the mask changes to 3’b000, which will not happen unless req[2] is granted. Is my understanding correct?
I’m wondering if the the final grant should sample mask_req to decide on the grant signal to pick.
// final grant
assign grant = (mask*_req* == 3’b000) ? raw_grant : mask_grant;
Hi Adithya,
You’re right. The final grant should sample the “mask_req” instead of “mask”. I’ll update the code. Thanks for pointing this out!