Arbiter algorithm

[Rusty]

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

 

[Mike Treseler]

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]

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

 

[Mike Treseler]

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

 

[Kai Harrekilde-Petersen]

Rusty <andersru@stud.ntnu.no> 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>

 

[Mike Treseler]

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