Arbiter algorithm

I am going to make an arbiter in vhdl which is fair. It is supposed to
arbit 128 different masters and give them access to the bus. If more
than one master requests the bus the arbiter is supposed to give the
master that have waited the longest since last transmit, and give that
one access first.

Do any you have a nice and smart way of doing this without using too
much time on it (too many clock periods)?

Anders
Norway

Rusty

Rusty wrote:
> I am going to make an arbiter in vhdl which is fair. It is supposed to
> arbit 128 different masters and give them access to the bus. If more
> than one master requests the bus the arbiter is supposed to give the
> master that have waited the longest since last transmit, and give that
> one access first.

When the shop is empty, I get immediate service.
When the shop is busy, I take the next number and wait
for it to be called.

-- Mike Treseler

Mike Treseler

But if number 14 and 28 both requests the bus, I have to check and see
which one of them have waited the longest. How would I do that fast.

Mike Treseler wrote:
> Rusty wrote:
>
>> I am going to make an arbiter in vhdl which is fair. It is supposed to
>> arbit 128 different masters and give them access to the bus. If more
>> than one master requests the bus the arbiter is supposed to give the
>> master that have waited the longest since last transmit, and give that
>> one access first.
>
>
> When the shop is empty, I get immediate service.
> When the shop is busy, I take the next number and wait
> for it to be called.
>
> -- Mike Treseler

Rusty

Rusty wrote:
> But if number 14 and 28 both requests the bus, I have to check and see
> which one of them have waited the longest. How would I do that fast.

The number is not my identifier.
The number is on a ticket
I rip from the wheel.

-- Mike Treseler

Mike Treseler

Rusty <> writes:

> Mike Treseler wrote:
>> Rusty wrote:
>>
>>> I am going to make an arbiter in vhdl which is fair. It is supposed
>>> to arbit 128 different masters and give them access to the bus. If
>>> more than one master requests the bus the arbiter is supposed to
>>> give the master that have waited the longest since last transmit,
>>> and give that one access first.
>> When the shop is empty, I get immediate service.
>> When the shop is busy, I take the next number and wait
>> for it to be called.

> But if number 14 and 28 both requests the bus, I have to check and see
> which one of them have waited the longest. How would I do that fast.

A FIFO will do exactly what Mike described above.

Then comes the question: what do you do when you get requests from
multiple sources per cycle. Rotating fair arbitration is the answer
here.


Kai
--
Kai Harrekilde-Petersen <khp(at)harrekilde(dot)dk>

Kai Harrekilde-Petersen

Kai Harrekilde-Petersen wrote:

> Then comes the question: what do you do when you get requests from
> multiple sources per cycle. Rotating fair arbitration is the answer
> here.

It might be fair enough for the
proprietor to award the
next ticket to the customer_id
closest to a pseudo-random count.

-- Mike Treseler


even homework is more
fun than testing software

Mike Treseler