FPGA Central

Hi all,

I'm using a Virtex-2 FPGA and I wonder how can I efficiently choose one
from many wires competing to hold a resource. When 2 wires request the
resource at the same time, only the one with higher priority should be
taken. I know how to do it attaching all the wires to multiple AND
gates. The problem is that those AND gates can be huge if 20+ wires
compete.

Any ideas?

Thanks.
Jose.

"JL" <[email protected]> wrote in message
news:[email protected] oups.com...
> Hi all,
>
> I'm using a Virtex-2 FPGA and I wonder how can I efficiently choose one
> from many wires competing to hold a resource. When 2 wires request the
> resource at the same time, only the one with higher priority should be
> taken. I know how to do it attaching all the wires to multiple AND
> gates. The problem is that those AND gates can be huge if 20+ wires
> compete.
>
> Any ideas?
>
> Thanks.
> Jose.
>

Hint: search Priority encoder

Jose, how fast do you need the answer? ns or perhaps even clock
cycles?
Peter Alfke

I need the answer within clock cycles. One clock cycle would be great,
although I can bear a few more. I didn't mention that the priority
encoder or whatever solution should be parametrizable in VHDL. Just as
background information, I'm developing a bus where all modules (DMA,
CCD cameras, etc) can request a long write to SDRAM at any moment.
Since the transfer is quite long, over 512 words, I don't care if the
arbiter takes a few cycles to resolve who will be granted the bus.

I'm trying this now:

signal requests : std_logic_vector(m-1 downto 0);
signal resolved : std_logic_vector(m-1 downto 0);

process(i_Clk, i_Rst, first_level)
variable found : std_logic;
begin
if (i_Rst = '1') then
resolved <= (others=>'0');
elsif (i_Clk'event and i_Clk = '1') then
found := '0';
for y in 0 to m-1 loop
if (requests(x) = '1' and found = '0') then
resolved <= ext(requests(y downto 0), m);
found := '1';
end if;
end loop;
end if;
end process;

It synthesizes well, although I don't know if that is good coding
practice. It seems to work at behavioral and post-place&route
simulations.

I'm just a bit worried about the efficiency of that construct. Do you
think it will become a headache if I don't express it in another way?
Do you think it could grow too big for something like 30 wires
requests?

Regards.
Jose.

Let me tell you what can be done in Virtex-4 (probably also in
Spartan3):

A priority "linear encoder" with 4 x N inputs and 4 x N outputs, each
output corresponding to a prioritized input.
Only one output is ever active, the one corresponding to the
highest-priority active input.
Total cost: 5N+1 (LUTs+flip-flops).
Such a 32-input linear priority encoder uses 41 LUTs = 21 slices (<6
CLBs), and runs at >250 MHz.
The design is fully modular (per 4 bits).
Peter Alfke

The VHDL code that I posted before is buggy. After the first signal
resolution, the resolved vector never becomes all '0'. The following
code solves it:

signal requests : std_logic_vector(m-1 downto 0);
signal resolved : std_logic_vector(m-1 downto 0);
signal some_request : std_logic;

process(i_Clk, i_Rst, first_level)
variable found : std_logic;
variable var_resolved : std_logic_vector(m-1 downto 0);
begin
if (i_Rst = '1') then
resolved <= (others=>'0');
var_resolved := (others=>'0');
some_request <= '0';
found := '0';
elsif (i_Clk'event and i_Clk = '1') then
found := '0';
var_resolved := (others=>'0');
for y in 0 to m-1 loop
if (requests(x) = '1' and found = '0') then
var_resolved <= ext(requests(y downto 0), m);
found := '1';
end if;
end loop;
some_request <= found;
resolved <= var_resolved;
end if;
end process;


It also adds a new wire, some_req, that is '1' when there is any wire
requesting the resource, and '0' when there isn't. That is useful when
you don't want to grant the resource inmediately, but controlled by a
state machine or any other decision-making procedure. It is tested and
it works after Place & Route in a Virtex-2 at 100 Mhz. The synthesizer
reports good operation over 200 Mhz, although I didn't try this.

Regards.
Jose.