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:

  1. If token[2:0] == 3’b001, then req[0] has highest priority while req[2] has the lowest priority;
  2. If token[2:0] == 3’b010, then req[1] has highest priority while req[0] has lowest priority;
  3. 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.

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:

  1. @cycle0 token[2:0] == 3’b001, then req[0] gets granted;
  2. @cycle1 token[2:0] == 3’b010, then req[2] gets granted;
  3. @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:

  1. If req[0] is granted, then mask[2:0] becomes 3’b110 and req[0] will be masked in next cycle;
  2. If req[1] is granted, then mask[2:0] becomes 3’b100 and req[1:0] will be masked in next cycle;
  3. 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.

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:

  1. If @cycle0 mask[2:0] = 3’b111, then req[0] is granted;
  2. @cycle1 mask[2:0] == 3’b110, and req[2] is granted;
  3. @cycle2 mask[2:0] == 3’b000, and req[0] is granted;
  4. @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:

  1. “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.
  2. Associate a counter for each request, to keep track of how many requests are granted for each source.
  3. 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.

6 Comments

  1. 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

    1. 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.

  2. 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;

    1. 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!

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.