Round robin arbitration
Raji
Can anybody please tell me how to implement round-robin arbitration in
verilog?
Thanks,
Raji
levita...@yahoo.com
Understand these and you'll be godlike.
http://www.siliconlogic.com/pdf/Arbiters_MattWeber_SLE.pdf
http://tiny-tera.stanford.edu/~nickm/papers/HOTI_98.pdf
of course, if you're talking about async arbiters, that's another
story....:)
Raji
Thanks for the links, they were pretty helpfull in getting a good idea. My
interface is little more complicated though. I can have requestors which
need not have distinct priorities, i.e some may have equal priorities too.
So if I have 5 modules, the levels of priorities need not be 5, could be
3 where 2 sets of modules have same priority(then I need to arbiter them
equally). The priorities should be programmable too. The case where all
have equal priority, I will shift to round-robin arbitration.
Any suggestions to tackle this??, I am pretty much stuck right now.
Thanks,
Raji
Jonathan Bromley
>Thanks for the links, they were pretty helpfull in getting a good idea. My
>interface is little more complicated though. I can have requestors which
>need not have distinct priorities, i.e some may have equal priorities too.
> So if I have 5 modules, the levels of priorities need not be 5, could be
>3 where 2 sets of modules have same priority(then I need to arbiter them
>equally). The priorities should be programmable too. The case where all
>have equal priority, I will shift to round-robin arbitration.
It's all about specification, isn't it?
What does "priority" mean? My guess is that you mean that
a higher priority request will always win against a low priority
request, no matter how long the low priority request has been
waiting. But you want equal-priority requests to be resolved on
a round-robin basis. To make things more complicated, you are
saying that all priorities are programmable.
Suppose for a moment that you have only one priority level.
Then everything is round-robin. You need only three blocks
to implement this. Let's suppose that the requesters are
numbered from 0 to N-1.
You need:
(0) The array of N request inputs. This is free, of
course - it's just the request signals.
(1) A register that holds the number of the requester that
was most recently serviced.
(2) A barrel shifter that rotates the array of request inputs
by the value of register (1) - this implements the
round-robin behaviour.
(3) A priority encoder that determines which active request
is highest in the barrel-shifted array of requests.
The priority-encoded value (3) is the number of the requester
that should next be serviced. It also needs some sort of
output to indicate the possibility that there is NO active
request.
When you service a request, you get the request number from (3)
and then copy it into register (1) so that a different requester
has the highest round-robin priority next time. The direction
of rotation, and the organisation of the priority encoder,
are chosen so that the rotate operation puts the request
you've just serviced to the back of the queue.
To add multiple priorities to this scheme, simply
replicate the whole affair for each possible priority
level, so that you have a separate round-robin arbiter at
each priority level. Then, to service a request, you first
find the highest priority LEVEL that has an active request
(using fixed priority) and then service that request.
If you want programmable priorities as well, then the
round-robin arbiter at each priority level must have
enough slots for every possible requester - because it's
possible in principle for all requesters to have the
same priority. Then you arrange that if a requester
is programmed to have priority P, it activates a request
signal only on the round-robin arbiter for priority P -
that's just a simple decode function. The result is
that if you have M different priority levels, then
each requester has M request outputs - one for each
priority level - and when it makes a request, it
asserts only the request output corresponding to
its chosen priority level.
It is not at all obvious how this scheme will behave if
a requester's priority is reprogrammed on-the-fly - but
getting that right is a hard problem anyway. If priorities
are programmed once and for all at setup time, it works
just fine.
<rant>
Programmable priorities are a waste of time anyway.
Rate-monotonic scheduling works much better.
</rant>
--
Jonathan Bromley, Consultant
DOULOS - Developing Design Know-how
VHDL, Verilog, SystemC, Perl, Tcl/Tk, Verification, Project Services
Doulos Ltd. Church Hatch, 22 Market Place, Ringwood, BH24 1AW, UK
Tel: +44 (0)1425 471223 mail:jonathan...@doulos.com
Fax: +44 (0)1425 471573 Web: http://www.doulos.com
The contents of this message may contain personal views which
are not the views of Doulos Ltd., unless specifically stated.
Jonathan Bromley
<jonathan...@doulos.com> wrote:
[For a round-robin arbiter]
>You need:
>(0) The array of N request inputs. This is free, of
> course - it's just the request signals.
>(1) A register that holds the number of the requester that
> was most recently serviced.
>(2) A barrel shifter that rotates the array of request inputs
> by the value of register (1) - this implements the
> round-robin behaviour.
>(3) A priority encoder that determines which active request
> is highest in the barrel-shifted array of requests.
>
>The priority-encoded value (3) is the number of the requester
>that should next be serviced.
<embarrassed cough> not quite, it needs to be corrected
("un-rotated") to compensate for the shift introduced in
step 2.
The first paper mentioned by levitation30 is excellent!!!
levita...@yahoo.com
First you round-robin between all requests at the same priority level.
That gives a grant at that level (not the final grant). If any
request is asserted at this level, you assert a request to the next
level.
You only advance this level's round robin, if this req is finally granted
at the next level. The final grant for guys at this level, is this
arbiters grant, ANDed with whether this level is granted at the next
levels.
At the 2nd level, you round robin between all requests at the same level,
and the one OR of requests from the prior lower level. You do the same thing
basically as the level below you..and feed a single request up to the n
ext level.
You can see with N levels and N requests, you can basically construct a
progammable fixed priority arbiter, with any programmable priority order
amongst requests.
So for each request, have a CSR that says which "level" it should be
associated with. You typically don't need more than two pools of requests,
so two levels should be fine. Every request can then be associated with either
level.
A key thing is to feed the OR of requests up the levels, not the grants.
This means that your timing doesn't get crazy...i.e. it's not a path
thru N arbiters for your worst case timing...just the top level arbiter,
some OR gates, and some AND gates should be the worst case path.
-lev