Continue to Site

Welcome to EDAboard.com

Welcome to our site! EDAboard.com is an international Electronics Discussion Forum focused on EDA software, circuits, schematics, books, theory, papers, asic, pld, 8051, DSP, Network, RF, Analog Design, PCB, Service Manuals... and a whole lot more! To participate you need to register. Registration is free. Click here to register now.

Register Log in

Round Robin gate-level diagram

Status
Not open for further replies.
P

promach

Advanced Member level 4
Joined
Feb 22, 2016
Messages
1,199
Helped
2
Reputation
4
Reaction score
5
Trophy points
1,318
Activity points
11,636
May I know why 'priority' signal is fed back to AND gate input ?
What is the purpose of the AND gate in the picture below ?

From googling, I found this article , but I am not sure if the AND gate in the article serves the similar purpose.
The article implementation uses some mask vector which seems a bit strange and complicated in terms of hardware resources as well.

3b3QqGJ.png


- - - Updated - - -

I just got an answer from one of my friend:

priority' signal is fed back so that the given priority stays on for multiple cycles since the registers are not conditionally clocked

So, if priority 1 is high and all the grant inputs are low, it will stay high forever.

Well, better wording would be: it is looped back into the AND gate for the purpose of it staying on forever and the AND gate is there to cut it off in case a grant input becomes high
Click to expand...
 
Last edited:

I don't see that schematic in the link you have given. I somehow think this is an incomplete schematic, what ensures only one grant is given ?
 
Right, it's only the priority generation. The arbiter itself isn't shown.
 

fourtytwo said:
I don't see that schematic in the link you have given. I somehow think this is an incomplete schematic, what ensures only one grant is given ?
Click to expand...

See page 83 of On-Chip Networks, Second Edition Synthesis Lectures on Computer Architecture

You are probably right and pointed out an important point here.

I am reading on a documentation of an existing noc code on github : See section 3.6 Round-Robin Arbiter

The test fails whenever the granted signals are more than one or when the grant is assigned to an agent
that didn’t request the resource or when the granted agent is not the one with highest priority among
the requesting ones
Click to expand...

How would we circumvent the failure issue ?
By ensuring the grant vector is a one-hot vector ? Could we really do this in reality ?

- - - Updated - - -

Edit: I just found another priority generation logic using round-robin mechanism.

Is the large lookup table for grant signal really necessary at all ? Are there any alternatives ?

The priority of inputs is in descending order from in1 to in3. Thus, in1 has the highest priority, in2 has the next highest priority, and in3 has the lowest priority. The D flip-flop is used for avoiding glitch due to ANDing
Click to expand...

Priority logic

avBwMbN.png


Round-Robin Arbiter

XIYxGd8.png


LUT for grant signals

KEK17zT.png
 
Last edited:

Have a look at the following arbiter.v code :

Someone told me to think of rr_arbiter is that it's a simplified ripple-borrow circuit that wraps around.

'base' is a one hot signal indicating the first request that should be considered for a grant.
Click to expand...

huh ? Do you guys understand how to generate 'base' input signal ?

Notice the subtraction. The borrow logic causes it to search to find the next set bit.
Click to expand...

why ~(double_req-base) ?

Code Verilog - [expand]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

module arbiter (
    req, grant, base
);
 
parameter WIDTH = 16;
 
input [WIDTH-1:0] req;
output [WIDTH-1:0] grant;
input [WIDTH-1:0] base;
 
wire [2*WIDTH-1:0] double_req = {req,req};
wire [2*WIDTH-1:0] double_grant = double_req & ~(double_req-base);
assign grant = double_grant[WIDTH-1:0] | double_grant[2*WIDTH-1:WIDTH];
    
endmodule
 

addition/subtraction for many logical inference problems and priority problems.

x & -x = x & ~(x-1) will return a vector with 1 bit set, and this bit will be the rightmost 1 in x. (or 0 when x = 0)
for example x = 0xF6. (x-1) = 0xF5, ~(x-1) = 0x0A. Notice that the carry of 0xF6 - 1 goes only to the 2nd bit and then stops. As a result, bits 7:2 in the two terms will be opposite -- the carry doesn't propogate this far. Same goes for bit 0 -- the carry forced the lsb's to 0. only bit 1 will be set in both.

Now look at x = 0xF5 in x & ~(x-2) x-2 = 0xF3 and ~(x-2) = 0x0C. noticed that the carry can't even start in the lsb -- x-2 will preserve even/odd. So these bits will be 0 due to "1 and not 1 = 0". At this point, the problem is the same as above, just for bits 7:1 vs 7:0.

For this application, this same trick is applied to the double_req version in order to capture if this carry moves past the normal msb.

if "base" is not a power of two, you could get more than on bit set in the result.

- - - Updated - - -

Possibly better explanation:

Bits to the right of the single bit set in "base" will be unaffected by (double_req - base). (group-a)
The expression (double_req - base) will result in borrowing from this point.
This converts the right bits of double_req past base into 1's if they are 0's. (group-b)
(group-b might be empty, eg if rightmost bit of double_req is the bit set in base)
This borrowing chains until double_req has a 1. This 1 is set to 0. (bit-c)
Bits to the left of this rightmost 1 in double_req are unaffected. (group-d)

The negation means the bits in group-a and group-d (which were not affected by the subtraction) will be different from the values in double_req.
The bits in group-b (if present) will be converted to 0.
The bit in bit-c will be converted to a 1.
The result of the and is thus all 0's except the first in a bit location >= base's only set bit.

(group-a/group-d are zero as: value and not value = 0.)
(bits in group-b are zero as: value and 0 = 0.)
 

Status
Not open for further replies.

Similar threads

Part and Inventory Search

Welcome to EDABoard.com

Sponsor

Back
Top