Arbitration Schemes - Verilog Hardware Design

[forkconfig]

I'm working on a hobby project and I have run into a problem with arbitration.
Is there any online lectures/course notes or books you can suggest to help me?

Also if you don't mind helping me here is my problem.
I have 256 clients, clients can make requests at any time.
At first what I did is I had a shared bus where clients could make requests on. But how would I ensure multiple clients don't request at the same time?
So then I added dedicated request lines. But then the issue was, now I have to check ALL 256 lines in the one clock cycle, so if in the next clock cycle, people want to make a request I don't loose those, and I maintain first come first serve sequence.

I'd really appreciate any help.

Thanks

Oh I'm using Verilog by the way.

 

[achaleus]

you said first come first serve.. what if two requests comes at the same time(we have to consider this) .. yes you should give priority, make them in queue(like fifo) type logic in which the request will be stored and processed after initial operation..

find some nptel videos they may help

 

[forkconfig]

Well your jumping ahead - I've figured out the priority part and once it's in the queue I'm good.

For my design, priority is set by id number, since when looking at the dedicated request lines I will loop through the client lines. And yes I am using a queue to serve the requests. However, my questions starts before we even get to this stage.

Here I will break it down:
1) If I have a shared bus in which clients can req permission by putting their address on the line and setting the req bit high. How do I ensure multiple clients don't req at the same time? I could use a daisy chain, but I want to maintain fairness (first come first serve).

2) At this point I decided to use dedicated request lines. However the issue is, to handle the requests on one clock cycle I have to iterate through 'n' clients (in this case 256). I want to reduce that time. It would be great if rather than polling each of the 256 lines, I could have the hardware trigger when a line goes high so I don't have to loop through.
Kind of like this (PSEUDO CODE):
@(posedge of any of the 256 lines) begin
tell me which bit(s) went high
handle only those bits
end

3) If there is a better way to perform arbitration please make suggestions.

 

[amitjagtap]

1. In order to resuce the time of polling all 256 signal lines
a) you increase the sampling frequency to check high request on lines. ... if samp. freq > (present clk freq)* 256, then you can sample all signals in less than one clk cycle of your present clk. One more advantage of using higher clk for sampling is.... you can very closly resolve two signals requesting for sampling simultaniously.
b) Divide 256 lines in groups of 2 (128 each ) or group of 4 (64 each).... Compare each group for request on a line. then poll that perticular group......Bisection Method... This will reduce your time of polling as compared to polling all 256 signals....Do this at higher clk so that you will have good time margin.
Well we will discuss more if this is helpfull for your design....
It is difficult to get diesct code for your appln.
Best of luck

 

[forkconfig]

That was very helpful. Thanks!

a) I didn't know you could vary clock frequencies. I can do that with verilog code? How do I define this clock?
I've heard of CDC (Clock Domain Crossing) but I thought those were physical clocks. So when people discuss CDC are they referring to clocks defined using this method your suggesting?

b) So to impliment this Bisection Method, would I do something like:
assign regStatus0 = bus[0] | bus[1] | bus[2] | bus[3];
...until I get to bus[255]...

and then run through the comparison of those registers.
Or is there a better way of doing it?

If that way is correct then would it be a good idea to keep doing that even amongst those status registers?
Ex: regStatusPrime0 = regStatus0 | regStatus1 | regStatus2 | regStatus3

Thanks

 

[amitjagtap]

Lets assume you are dividing 256 lines in 32 each in this case you have to generate only one signal to represent 32 lines (if your request line is going high for request just OR all 32 lines). Like this for each group of 32 lines you will have 8 representing lies..Now you have to poll/sample these lines only....as shown in figure A,B,C,,,H are those lines. If any line is sampled as high...then you have to search for that perticular 32 lines only...
Hope this help you...
Well, you can use DCM Digital clock manages (for Xilinx FPGA) to increase you clock frequency...