100-sources/requests Arbiter

[ivlsi]

Hi All,

One one of the interviews, I was asked to implement a 100-requests Round-Robin Arbiter.

It seems that an implementation of the Arbiter using FSM is not realistic. So, what are the options?

Thank you!

 

[vGoodtimes]

I'm assuming the concern was in how the FSM worked in terms of latency vs area/frequency. a 100 cycle approach should be favored until you are given a reason to avoid it -- it will not affect clock frequency, is lower area than most designs, and is simple to design and verify. Proposing this and the design rationale should be a first step. For interviews, you should always propose something that will clearly work first and then ask if other optimizations are needed.

Latency and area are the implied issues. A RRA can be done by in a single long cycle, but the cycle time will be large. Likewise, the RRA can be done with the 100 cycles of latency. The next obvious optimization would be divide and conquer based methods. The square-root complexity version would probably be expected. For example, have 11 arbiters with 10 inputs. 10 for the 100 inputs, then the 11th to choose between them. This is not a true round-robin arbiter as it can select one item 2+ times before another item is selected. Similar grouping ideas can be applied to a FSM version that doesn't have this issue. Likewise, logic can be added to check inputs in parallel -- eg, select from the next 4 possible inputs to reduce latency to 25 cycles.