Understanding Linear implementation of a round-robin arbiter

[promach]

For Efficient microarchitecture for network-on-chip routers , do anyone know how this round-robin arbiter actually works ?


Note: The corresponding verilog codes seem to be located at c_rr_arbiter_base.v and c_rr_arbiter.v

[hamster_nz]

The top box offers priority to the the next input after the last one granted.

The the rest of the boxes are in a ring, and the first being request locks out the rest of the ring, until it gets back to the one being offered priority where the ring is broken.

Quite nifty.

[hamster_nz]

Reset needs to be though through to ensure that one and only one bit is set in the 'who to offer to first' register, preventing the whole thing from latching up.

[BrianHG]

Damn that would have been useful a decade ago.  I did it the hard way...
I made a state machine.  And I also required a 2 tier override priority for 2 specific sources.

[RoGeorge]

do anyone know how this round-robin arbiter actually works ?

You can visualize it as a round table with a moderator, where only one person is allowed to talk, and only for a certain amount of time.  Then, the next person is allowed to talk, and so on.  The moderator allows them to speak one by one, in circles around the table.

What exactly was your question about?  The idea, the schematic, or the HDL implementation?

Later edit
Note:  Using the words "Verilog code" is very misleading, better think about it as a Verilog circuit, or schematic diagram.

[promach]

1) What is the purpose of the OR and AND gates in the second box ?

2) How is the above gate-level schematics different from https://github.com/promach/noc/blob/master/arbiter.v ?


By the way, See waveform of my verilog code implementation

Code: [Select]

// Credit : [url]https://www.reddit.com/r/FPGA/comments/dbr1xs/understanding_linear_implementation_of_a/[/url]

module arbiter2 #(parameter WIDTH = 4) (clk, reset, req, grant);

input clk, reset;
input [WIDTH-1:0] req;
output [WIDTH-1:0] grant;

// 'grant' is one-hot vector, which means only one client request is granted/given green light to proceed
// note that 'base' is one-hot vector,
// 'base' signal helps round-robin arbiter to decide which 'req' to start servicing
reg [WIDTH-1:0] base;

always @(posedge clk)
begin
if(reset) base <= 1;

else base <= (base[WIDTH-1]) ? 1 : (grant == 0) ? 1 : (grant << 1);
end

wire [WIDTH-1:0] priority_in;
reg [WIDTH-1:0] priority_out;

genvar index;
generate
for(index = 0; index < WIDTH; index = index + 1)
begin
if(index > 0) assign priority_in[index] = base[index] | priority_out[index-1];

else assign priority_in[index] = base[index] | priority_out[WIDTH-1];
end
endgenerate

assign grant = (reset) ? 1 : req & priority_in;

always @(posedge clk) priority_out <= (~req) & priority_in;

`ifdef FORMAL
initial assume(reset);

reg first_clock_had_passed;
initial first_clock_had_passed = 0;

always @(posedge clk) first_clock_had_passed <= 1;
always @(posedge clk) if(first_clock_had_passed && $past(first_clock_had_passed) && $past(first_clock_had_passed, 2) && $past(first_clock_had_passed, 3)) assume(req[WIDTH-1]); // ALL requests ON

// covers the ability to handle requests properly even with ALL requests ON
always @(posedge clk) cover(first_clock_had_passed);
`endif

endmodule

[promach]

What is wrong with my updated verilog code that resulted in wrong waveform result ?

Code: [Select]

// Credit : [url]https://www.reddit.com/r/FPGA/comments/dbr1xs/understanding_linear_implementation_of_a/[/url]

module arbiter2 #(parameter WIDTH = 4) (clk, reset, req, grant);

input clk, reset;
input [WIDTH-1:0] req;
output [WIDTH-1:0] grant;

// 'grant' is one-hot vector, which means only one client request is granted/given green light to proceed
// note that 'base' is one-hot vector,
// 'base' signal helps round-robin arbiter to decide which 'req' to start servicing
reg [WIDTH-1:0] base;

always @(posedge clk)
begin
if(reset) base <= 1;

else base <= (base[WIDTH-1]) ? 1 : (grant == 0) ? 1 : (grant << 1);
end

wire [WIDTH-1:0] priority_in;
reg [WIDTH-1:0] priority_out;

genvar index;
generate
for(index = 0; index < WIDTH; index = index + 1)
begin
if(index > 0) assign priority_in[index] = base[index] | priority_out[index-1];

else assign priority_in[index] = base[index] | priority_out[WIDTH-1];
end
endgenerate

assign grant = (reset) ? 1 : req & priority_in;

always @(posedge clk) priority_out <= (~req) & priority_in;

`ifdef FORMAL
initial assume(reset);

reg first_clock_had_passed;
initial first_clock_had_passed = 0;

always @(posedge clk) first_clock_had_passed <= 1;
always @(posedge clk) if(first_clock_had_passed && $past(first_clock_had_passed) && $past(first_clock_had_passed, 2) && $past(first_clock_had_passed, 3)) assume(&req); // ALL requests ON

// covers the ability to handle requests properly even with ALL requests ON
always @(posedge clk) cover(first_clock_had_passed);
`endif

endmodule

[hamster_nz]

The way I read the orignal diagram, this bit feels wrong:

Code: [Select]

always @(posedge clk)
begin
if(reset) base <= 1;

else base <= (base[WIDTH-1]) ? 1 : (grant == 0) ? 1 : (grant << 1);
end

Specifically:

(grant == 0) ? 1 : (grant << 1)

That should be more like

(grant == 0) ? base : { grant[WIDTH-2:0] , base[WIDTH-1] }

Or how ever you do a rotate in Verilog.

[hamster_nz]

Warning: I don't do Verilog, so this code might be very poorly written.

So this is that module in the picture, literally turned directly into Verilog:

Code: [Select]

`timescale 1ns / 1ps
// Please credit Mike Field / hamster@snap.net.nz

module arbit(
    input clk,
    input reset,
    input [7:0] request,
    output [7:0] grant
    );

reg [7:0] granting = 8'b0;
reg [7:0] first_offer = 8'b0;
reg [7:0] available = 8'b0;
reg [7:0] request_loop_in = 8'b0;
reg [7:0] request_loop_out = 8'b0;

assign grant = granting;

always @(posedge clk)
  begin
    if(reset) begin
      first_offer  = 1;
    end else begin
      if(granting != 0) begin
        first_offer = { granting[6:0], granting[7]};
      end
    end
  end

// This is yeachy async logic, that contains a loop, bit due to first_offer being
// one-hot the the loop is always broken.
always @(*) request_loop_in   = { request_loop_out[6:0], request_loop_out[7]};
always @(*) available         = request_loop_in | first_offer;
always @(*) granting          = available & request;
always @(*) request_loop_out  = available & ~request;

endmodule

And attached is the simulation that confirms to me that it is working as I expect and understand it should.  It may not be working as you expect it will.

If multiple requests are asserted at the same time it grants to the next highest, and wrapping back to zero.

As I expected, the reset condition is particularly dodgy - should you have an 'X' it will propagate around the loop in the logic and turn the whole thing to custard.

[promach]

verilator -Wall --lint-only arbit.v
%Warning-UNOPTFLAT: arbit.v:15: Signal unoptimizable: Feedback to clock or circular logic: 'arbit.request_loop_out'
reg [7:0] request_loop_out = 8'b0;
          ^~~~~~~~~~~~~~~~
                    ... Use "/* verilator lint_off UNOPTFLAT */" and lint_on around source to disable this message.
                    arbit.v:15:      Example path: arbit.request_loop_out
                    arbit.v:36:      Example path: ALWAYS
                    arbit.v:14:      Example path: arbit.request_loop_in
                    arbit.v:37:      Example path: ALWAYS
                    arbit.v:13:      Example path: arbit.available
                    arbit.v:39:      Example path: ALWAYS
                    arbit.v:15:      Example path: arbit.request_loop_out
%Error: Exiting due to 1 warning(s)
%Error: Command Failed /usr/bin/verilator_bin -Wall --lint-only arbit.v

There is circular loop logic in your code...

Besides, can I say that first_offer is equivalent to p[] ?

[hamster_nz]

There is circular loop logic in your code...

That is the whole point. As there is a logic loop in the diagram, so there is a logic loop in the code.

Besides, can I say that first_offer is equivalent to p[] ?

Sure.

[promach]

Sorry but yosys synthesis tool just does not allow synthesis for code that contains circular loop ...

[hamster_nz]

Sorry but yosys synthesis tool just does not allow synthesis for code that contains circular loop ...

Don't be sorry for that.

From the diagram I could see that it is an interesting, useful piece of logic, that in practice actually works, but it was also apparent that due to the logic loop you would have difficulty to build it using standard FPGA/ASIC tools.

You should have taken the time to read the very next block of text after figure 2.2. in the document you linked to:


Commercially available timing analysis tools are typically unable to properly analyze circuits that contain combinational loops like the one generated by wrapping around the priority signals. This is particularly problematic when using a standard cell design flow, as it prevents synthesis from performing proper gate sizing.


Which is exactly the problem you are facing.

[promach]

due to the logic loop you would have difficulty to build it using standard FPGA/ASIC tools.

Do you have any practical workaround to get around this issue for synthesis tool ?

[hamster_nz]

due to the logic loop you would have difficulty to build it using standard FPGA/ASIC tools.

Do you have any practical workaround to get around this issue for synthesis tool ?

Reading the next sentence after the one quoted on Page 16 might be a very good place to start:

We can avoid the combinational loop by severing the wraparound priority signal and connecting it to a chain of fixed-priority cells F as shown in Figure 2.32

You don't seem very interested in the topic if you can't be bothered reading the relevant parts of the paper you linked to in your original post.

[promach]

We can avoid the combinational loop by severing the wraparound priority signal and connecting it to a chain of fixed-priority cells F as shown in Figure 2.3

What is actually the purpose of the chain of fixed-priority cells F ?

How does this chain actually help to eliminate the circular loop ?



Update: I have just finished implementing figure 2.3 in verilog code below :

Code: [Select]

// Credit : [url]https://www.reddit.com/r/FPGA/comments/dbr1xs/understanding_linear_implementation_of_a/[/url]

module arbiter2 #(parameter WIDTH = 4) (clk, reset, req, grant);

input clk, reset;
input [WIDTH-1:0] req;
output [WIDTH-1:0] grant;

// 'grant' is one-hot vector, which means only one client request is granted/given green light to proceed
// note that 'base' is one-hot vector,
// 'base' signal helps round-robin arbiter to decide which 'req' to start servicing
reg [WIDTH-1:0] base;

always @(posedge clk)
begin
if(reset) base <= 1;

else base <= (base[WIDTH-1]) ? 1 : (grant == 0) ? base : { grant[WIDTH-2:0] , base[WIDTH-1] };
end

wire [WIDTH-1:0] priority_in;
wire [(WIDTH << 1)-1:0] priority_out; // the two leftmost significant bit are left unused

wire [WIDTH-1:0] granting = req & priority_in;
wire [WIDTH-1:0] approval; // the most significant bit is left unused, we only have (N-1) block F

genvar index;
generate
for(index = 0; index < WIDTH; index = index + 1)
begin
if(index == WIDTH-1) assign grant[index] = granting[index];

else assign grant[index] = granting[index] | approval[index];


if(index > 0)
begin
assign priority_in[index] = base[index] | priority_out[index-1];
assign approval[index] = approval[index-1] & req[index];
end

else begin
assign priority_in[index] = base[index];
assign approval[index] = priority_out[WIDTH-1] & req[index];
end
end
endgenerate


genvar priority_index;
generate
for(priority_index = 0; priority_index < (WIDTH << 1); priority_index = priority_index + 1)
begin : out_priority

if(priority_index < (WIDTH))
assign priority_out[priority_index] = (~req[priority_index]) & priority_in[priority_index];

else assign priority_out[priority_index] = (~req[priority_index >> 1]) & priority_out[priority_index-1];
end
endgenerate

`ifdef FORMAL
initial assume(reset);

reg first_clock_had_passed;
initial first_clock_had_passed = 0;

always @(posedge clk) first_clock_had_passed <= 1;
always @(posedge clk) if(first_clock_had_passed && $past(first_clock_had_passed) && $past(first_clock_had_passed, 2) && $past(first_clock_had_passed, 3)) assume(&req); // ALL requests ON

// covers the ability to handle requests properly even with ALL requests ON
always @(posedge clk) cover(first_clock_had_passed);
`endif

endmodule

[hamster_nz]

Taking it really slow...

We have four 'things' trying to get granted access to a shared resource - CPUs accessing memory, people accessing a shower, whatever
Call them 'A', 'B', 'C', and 'D'. We want to give them all fair access.

So the following 'round robin' system is chosen:

If 'A' last had access then the priorities will be 'B','C','D' and lowest will be 'A'
If 'B' last had access then the priorities will be 'C','D','A' and lowest will be 'B'
If 'C' last had access then the priorities will be 'D','A','B' and lowest will be 'C'
If 'D' last had access then the priorities will be 'A','B','C' and lowest will be 'D'

To make life simpler, rather than remembering who had the resource last, we will remember who has the highest priority.

That is what figure 2.2 implements - the register in the top block holds who has priority to the resource, and the logic works out the new priorities.

You end up with these patterns - when there are competing requests you take the first in the list, and set the highest priority to be
the next one after the one taken:

Highest priority => complete list of priority, from highest to lowest.
A => ABCD
B => BCDA
C => CDAB
D => DABC

Hopefully you follow me this far.

The problem with the logic was the combinatorial loop caused by the priorities being reshuffled - the one that Verilator can't handle.

Here's how that is solved.

A N+(N-1) stage (7 stages where N = 4), fixed order arbiter is created, with the first N-1 being repeated.
For our four resources the priority will be a never-changing "ABCDABC". What does change is that the first three stages can be disabled depending on who is the priority to the resource:

A => ABCDABC
B => -BCDABC
C => --CDABC
D => ---DABC

You end up with the same effective priority as the round robin, but you have fixed, unchanging priorities in the logic, and no loop.

To make it clearer, the second repetition of a request has been removed (as the first one will always be granted as it has higher priority):

A => ABCD---
B => -BCDA--
C => --CDAB-
D => ---DABC

That is why in figure 2.3 the "request" lines for first N-1 inputs feed two blocks, and there are N-1 OR gates to merge the grant outputs.

[promach]

I need some time to digest your previous post just above.

Could you comment on various ways of delay minimization for the gate schematics of Figure 2.3 ?

Note: The PhD thesis author also pointed out another (besides figure 2.3) novel implementation of Fast Arbiters for On-Chip Network Switches

[hamster_nz]

Could you comment on various ways of delay minimization for the gate schematics of Figure 2.3 ?

The opimization seems to be:

Split the N+(N-1) arbiter in (almost) half, so our for a four input arbiter ABCDABC becomes ABCD  and ABC,

Calculate both halves independently - the second half is very simple to calculate as  it doesn't have any dependency on the register that holds what signal was last granted:

    g[4] = A
    g[5] = ~A & B
    g[6] = ~A & ~B & C

And rather than using OR gates to combine g[2:0] with g[6:4], you must then use a 2:1 mux, selecting g[6:4] if the first four blocks of the arbiter haven't asserted an output.

For an 4-input arbiter implemented as shown the critical path from the path though 7 blocks (maybe 14 gates) and an OR gate

For this enhanced version the delay is 4 blocks (maybe 8 gates) and a 2:1 mux.

At least that is the gist of it - something like figure 3 in https://www.researchgate.net/publication/224371772_Fast_arbiters_for_on-chip_network_switches

[hamster_nz]

Literally a rainy day here so did some more experimentation, that will most likely only be of interest to me.... 

When implemented in a Spartan6 FPGA, and implemented as per the acyclic diagram, a 4-input round-robin arbiter uses 14 LUTs and 4 flipflops.

Implemented as below uses under half the logic resources (6 LUTs and 2 flipflops) - and is significantly faster too.

Code: [Select]

module arb2(
    input clk,
    input reset,
    input [3:0] request,
    output [3:0] grant
    );


   reg [5:0] lut_result;
   reg [1:0] hi_pri;
   
   assign grant = lut_result[3:0];
   
always @(posedge clk)
   begin
      if(reset) begin
         hi_pri = 2'b0;
      end else begin
         hi_pri = lut_result[5:4];
      end
   end

always @(*)
   begin
     
 case ( { hi_pri, request } )
      // Verify this table yourself - it was manually generated!
      // request[0] priority
      6'b000000: lut_result = 6'b000000;
      6'b000001: lut_result = 6'b010001;
      6'b000010: lut_result = 6'b100010;
      6'b000011: lut_result = 6'b010001;
      6'b000100: lut_result = 6'b110100;
      6'b000101: lut_result = 6'b010001;
      6'b000110: lut_result = 6'b100010;
      6'b000111: lut_result = 6'b010001;
      6'b001000: lut_result = 6'b001000;
      6'b001001: lut_result = 6'b010001;
      6'b001010: lut_result = 6'b100010;
      6'b001011: lut_result = 6'b010001;
      6'b001100: lut_result = 6'b110100;
      6'b001101: lut_result = 6'b010001;
      6'b001110: lut_result = 6'b110100;
      6'b001111: lut_result = 6'b010001;

      // request[1] has priority
      6'b010000: lut_result = 6'b010000;
      6'b010001: lut_result = 6'b100001;
      6'b010010: lut_result = 6'b100010;
      6'b010011: lut_result = 6'b100010;
      6'b010100: lut_result = 6'b110100;
      6'b010101: lut_result = 6'b110100;
      6'b010110: lut_result = 6'b100010;
      6'b010111: lut_result = 6'b100010;
      6'b011000: lut_result = 6'b001000;
      6'b011001: lut_result = 6'b001000;
      6'b011010: lut_result = 6'b100010;
      6'b011011: lut_result = 6'b100010;
      6'b011100: lut_result = 6'b110100;
      6'b011101: lut_result = 6'b110100;
      6'b011110: lut_result = 6'b100010;
      6'b011111: lut_result = 6'b100010;

      // request[2] has priority
      6'b100000: lut_result = 6'b100000;
      6'b100001: lut_result = 6'b010001;
      6'b100010: lut_result = 6'b100010;
      6'b100011: lut_result = 6'b010001;
      6'b100100: lut_result = 6'b110100;
      6'b100101: lut_result = 6'b110100;
      6'b100110: lut_result = 6'b110100;
      6'b100111: lut_result = 6'b110100;
      6'b101000: lut_result = 6'b001000;
      6'b101001: lut_result = 6'b001000;
      6'b101010: lut_result = 6'b001000;
      6'b101011: lut_result = 6'b001000;
      6'b101100: lut_result = 6'b110100;
      6'b101101: lut_result = 6'b110100;
      6'b101110: lut_result = 6'b110100;
      6'b101111: lut_result = 6'b110100;

      // request[3] has priority
      6'b110000: lut_result = 6'b110000;
      6'b110001: lut_result = 6'b010001;
      6'b110010: lut_result = 6'b100010;
      6'b110011: lut_result = 6'b010001;
      6'b110100: lut_result = 6'b110100;
      6'b110101: lut_result = 6'b010001;
      6'b110110: lut_result = 6'b100010;
      6'b110111: lut_result = 6'b010001;
      6'b111000: lut_result = 6'b001000;
      6'b111001: lut_result = 6'b001000;
      6'b111010: lut_result = 6'b001000;
      6'b111011: lut_result = 6'b001000;
      6'b111100: lut_result = 6'b001000;
      6'b111101: lut_result = 6'b001000;
      6'b111110: lut_result = 6'b001000;
      6'b111111: lut_result = 6'b001000;

      default  : lut_result = 6'b000000;
   endcase
                 
   end
endmodule

Of course it doesn't scale well to wider arbiters, but is a perfect match for a LUT6 FPGA

[promach]

I really need some more time to understand your explanation on how the round-robin arbiter in the PhD thesis works.

By the way, you were implementing it in pure lookup table which also resulted in the same resource usage as my code in post above.

5. Printing statistics.

=== arbiter2 ===

   Number of wires:                 17
   Number of wire bits:             32
   Number of public wires:           7
   Number of public wire bits:      22
   Number of memories:               0
   Number of memory bits:            0
   Number of processes:              0
   Number of cells:                 18
     SB_DFFESR                       2
     SB_DFFESS                       1
     SB_DFFSR                        1
     SB_LUT4                        14

[promach]

A N+(N-1) stage (7 stages where N = 4), fixed order arbiter is created, with the first N-1 being repeated.
For our four resources the priority will be a never-changing "ABCDABC". What does change is that the first three stages can be disabled depending on who is the priority to the resource:

A => ABCDABC
B => -BCDABC
C => --CDABC
D => ---DABC

You end up with the same effective priority as the round robin, but you have fixed, unchanging priorities in the logic, and no loop.

To make it clearer, the second repetition of a request has been removed (as the first one will always be granted as it has higher priority):

A => ABCD---
B => -BCDA--
C => --CDAB-
D => ---DABC

I do not understand why disabling the first three stages ?

[hamster_nz]

A N+(N-1) stage (7 stages where N = 4), fixed order arbiter is created, with the first N-1 being repeated.
For our four resources the priority will be a never-changing "ABCDABC". What does change is that the first three stages can be disabled depending on who is the priority to the resource:

A => ABCDABC
B => -BCDABC
C => --CDABC
D => ---DABC

You end up with the same effective priority as the round robin, but you have fixed, unchanging priorities in the logic, and no loop.

To make it clearer, the second repetition of a request has been removed (as the first one will always be granted as it has higher priority):

A => ABCD---
B => -BCDA--
C => --CDAB-
D => ---DABC

I do not understand why disabling the first three stages ?

If it has just granted a request to A, you now want 'B" to have the highest effective priority, so you disable the first stage, giving B the highest priority.

If it has granted a request to B, you now want 'C" to have the highest effective priority, so you disable the first two stages, giving C the highest priority.

If it has granted a request to C, you now want 'D" to have the highest effective priority, so you disable the first three stages, giving D the highest priority.

If it has granted a request to D, you now want 'A" to have the highest effective priority, so you don't disable any, giving A the highest priority.

[promach]

That is why in figure 2.3 the "request" lines for first N-1 inputs feed two blocks, and there are N-1 OR gates to merge the grant outputs.

And how does such disabling helps to eliminate the circular loop in figure 2.2 ?

Calculate both halves independently - the second half is very simple to calculate as  it doesn't have any dependency on the register that holds what signal was last granted:

    g[4] = A
    g[5] = ~A & B
    g[6] = ~A & ~B & C

No, note that the first block F requires C_n output from the Nth block R. Did you see that ?

[hamster_nz]

FIgure 2.2 has circular loops making it hard for tools to implement.

That is why the scheme in figure 2.3 is used - to get rid of the loops.

So how do you get rid of the loops in figure 2.2? You implement the functionally equivilent design that is in shown in figure 2.3!

(have I been secretly become trapped into a piece of performance art? Some avant garde trolling?)