Welcome to EDAboard.com

Welcome to our site! EDAboard.com is an international Electronic 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

100-sources/requests Arbiter

Status
Not open for further replies.

ivlsi

Advanced Member level 3
Joined
Feb 17, 2012
Messages
879
Helped
17
Reputation
32
Reaction score
16
Trophy points
1,298
Activity points
6,806
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

Advanced Member level 4
Joined
Feb 16, 2015
Messages
1,087
Helped
306
Reputation
612
Reaction score
302
Trophy points
83
Activity points
8,692
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.
 

Status
Not open for further replies.
Toggle Sidebar

Part and Inventory Search

Welcome to EDABoard.com

Sponsor

Top