Inferred Priority Encoder In VHDL

Consider something like:

result <= a when sig1 = '1' else
b when sig2 = '1' else
c when sig3 = '1' else
'0';

The XST synthesis tool infers a priority encoder. That's probably ok
when there are only 3 or 4 choices but it gets completely out of hand
when there are 16 choices. The number of logic levels becomes excessive.

The result here is 4 levels of logic, 2 2-input OR gates, 3 2-input
AND gates (one with an inverter on 1 input) and a 3-input AND gate
(with an inverter on 1 input) and the maximum delay is 9.393 nS, 7.376
nS for logic.

Now, XST doesn't know that sig1, sig2 and sig3 are mutually exclusive.
They are decoded op codes like 'add', 'sub', etc and decoded
elsewhere. This from the POP11 project where I have taken the
generated Verilog and tried to change it to VHDL.

The Verilog might look like:

assign result = (sig1 ? a : 1'b0) |
(sig2 ? b : 1'b0) |
(sig3 ? c : 1'b0);

This results in 3 2-input AND gates and a 3 input OR gate. Oddly
enough, it is slower at 10.648 nS and the Systhesis Report still lists
4 levels of logic. 7.567 nS attributed to logic versus 7.376 for the
VHDL example. But, as more conditions are added, the delay won't
increase. The OR gate will get wider and, I suppose there will be
issues when it gets too wide but that's a lot better than the 23
levels of logic I have for my naive VHDL interpretation of the ALU.

Is there a way to code this Verilog construct in VHDL that doesn't
result in a priority encoder? I would much prefer a MUX but I don't
have a vector to use to select inputs.

Or should I use this as a learning opportunity and use Verilog?

Thanks!
Richard

To post a message, send it to: f...
To unsubscribe, send a blank message to: f... Start a New Thread

You could do worse than check out
http://www.cs.tut.fi/soc/Metzgen04.pdf
Even though it's an Altera perspective, the general
principles holds true for Xilinx as well.

> Is there a way to code this Verilog construct in
> VHDL that doesn't
> result in a priority encoder? I would much prefer a
> MUX but I don't
> have a vector to use to select inputs.

If you can (especially if you know the selects ahead
of the data and can use a pipeline stage for that),
you're likely better off translating your bit-line
selects into an index and using that to drive the mux,
especially if the mux is wide. Fx (in Verilog,
untested)

wire [7:0] select;
reg [2:0] index;
always @(*)
casex (select)
8'b1xxxxxxx: index = 0;
8'bx1xxxxxx: index = 1;
...
8'bxxxxxxx1: index = 7;
default: index = 'hX;
endcase

wire [31:0] sig0, sig1, ..., sig7;
reg [31:0] res;
always @(*)
casex (index)
0: res = sig0;
....
7: res = sig7;
default: res = 'hX;
endcase
> Or should I use this as a learning opportunity and
> use Verilog?

Never a bad idea IMO.

Tommy

____________________________________________________________________________________
Be a better pen pal.
Text or chat with friends inside Yahoo! Mail. See how. http://overview.mail.yahoo.com/
To post a message, send it to: f...
To unsubscribe, send a blank message to: f... Start a New Thread

> If you want and & or gates, why not just say so, ie:
>
> result <= ( a and sig1 ) or ( b and sig2) or ( c and sig3);

In many cases 'a' is actually a vector...

>
> If you want to make something that more exactly matches the verilog
> code, you could write a function to do the multiplexing or generate the
> three intermediate signals and or them. The logic difference is coming
> from your cascaded when...else statements, which is creating a
> dependency between sig1/sig2/sig3 that doesn't exist in the verilog
version.
>
> Intermediate products:
> amx <= a when sig1='1' else '0';
> bmx <= b when sig2='1' else '0';
> cmx <= c when sig3='1' else '0';
> result <= amx or bmx or cmx;

This will work nicely even with vectors. I wonder if it is worth
messing around with tri-state to eliminate the 'or'?

>
> Pretty-fied function version:
> function my_mux (sig, x : in std_logic) return std_logic is
> begin
> if sig='1' then
> return x;
> else
> return '0';
> end if;
> end;
>
> ...
>
> result <= my_mux(sig1,a) or my_mux(sig2,b) or my_mux(sig3,c);
>
> All three should compile into the same physical gates...
>

Neat...

Thanks!
Richard

To post a message, send it to: f...
To unsubscribe, send a blank message to: f... Start a New Thread

> You could do worse than check out
> http://www.cs.tut.fi/soc/Metzgen04.pdf
> Even though it's an Altera perspective, the general
> principles holds true for Xilinx as well.

This one is even more explicitly on the mux issue:
Multiplexer Restructuring for FPGA Implementation Cost
Reduction
(http://www.soccentral.com/goto.asp?EntryID999)

Tommy

____________________________________________________________________________________
Get easy, one-click access to your favorites.
Make Yahoo! your homepage.
http://www.yahoo.com/r/hs
To post a message, send it to: f...
To unsubscribe, send a blank message to: f... Start a New Thread

--- In f..., "Eric Smith" wrote:
>
> > Is there a way to code this Verilog construct in VHDL that doesn't
> > result in a priority encoder? I would much prefer a MUX but I don't
> > have a vector to use to select inputs.
>
> Sure, just use "or" like you did in the Verilog ("|") instead of a
> the "when" constructs.
>
> Eric
>

I should have mentioned that in many cases, the code is dealing with
vectors rather than individual signals.

I recoded the ALU in cleaned-up Verilog and compared it to VHDL. In
the end, there is one level difference. It's either 28 levels
(Verilog) or 29 levels (VHDL) for the PDP-11/40 ALU and the delays
(ignoring IBUF and OBUF) are on the order of 40 nS for a Spartan IIE
speed grade 6.

Given that the prototype only runs at 20 MHz, I still have a little
margin.

Another approach might be to break up the ALU into separate units:
adder, shifter, bit operations, etc. Then MUX the results. I have
seen some RISC designs that use that approach.

Richard

To post a message, send it to: f...
To unsubscribe, send a blank message to: f... Start a New Thread

> I should have mentioned that in many cases, the code is dealing with
> vectors rather than individual signals.

And that would be a problem because... ?

To post a message, send it to: f...
To unsubscribe, send a blank message to: f... Start a New Thread

> Another approach might be to break up the ALU into
> separate units:
> adder, shifter, bit operations, etc. Then MUX the
> results. I have
> seen some RISC designs that use that approach.

Actually, that *is* the classic approach, but
sometimes you can do better by merging operations or
being very clever with the implementation. See fx. "A
High Performance 32-bit ALU for Programmable Logic" in
FPGA'04. In my experience, those tricks doesn't really
help on "modern" FPGAs though, so as long as you keep
the muxes under control you'll be fine.

Quartus II will give you a ton of information about
the muxes it found and how many resources they take.
ISE might have something similar.

Tommy

____________________________________________________________________________________
Never miss a thing. Make Yahoo your home page.
http://www.yahoo.com/r/hs
To post a message, send it to: f...
To unsubscribe, send a blank message to: f... Start a New Thread

--- In f..., "Eric Smith" wrote:
>
> > I should have mentioned that in many cases, the code is dealing with
> > vectors rather than individual signals.
>
> And that would be a problem because... ?
>

I guess I don't know how to do a vector assignment based on a logic
operation like:

some_vector <= (some_other_vector AND a_std_signal ) OR
(another_vector AND some_other_std_signal);

in an attempt to get rid of the WHEN - ELSE construct.

It would certainly work when everything is a std_signal.

Richard

To post a message, send it to: f...
To unsubscribe, send a blank message to: f... Start a New Thread

> I guess I don't know how to do a vector assignment based on a logic
> operation like:
>
> some_vector <= (some_other_vector AND a_std_signal ) OR
> (another_vector AND some_other_std_signal);

The logical operators are defined on std_logic_vector. The problem is
that they aren't defined between a std_logic_vector and a std_logic.
The easiest way to do this "inline" is to use an aggregate to expand
the std_logic signal into a vector:

some_vector < (some_other_vector and (some_other_vector'range => a_std_signal)) or
(another_vector and (another_vector'range => some_other_std_signal));

That's cumbersome to type, so a better approach may be to write your
own function to overload "and":

function "and" (a: std_logic_vector;
b: std_logic) return std_logic_vector is
begin
return a and (a'range => b);
end;

You can define that in your architecture (before the "begin", with your
types, signals, etc.), or you can put it in a separate package and "use"
it from multiple source files. Either way, you can then write:

some_vector <= (some_other_vector and a_std_signal) or
(another_vector and some_other_std_signal);

Of course, you don't have to overload the "and" operator. You could
define a function with a normal name such as andvs, and use that:

some_vector <= andvs (some_other_vector, a_std_signal) or
andvs (another_vector, some_other_std_signal);

I prefer the overloading as I think the result is more readable, but
some people don't seem to like overloading.

Eric

To post a message, send it to: f...
To unsubscribe, send a blank message to: f... Start a New Thread

> Is there a way to code this Verilog construct in VHDL that doesn't
> result in a priority encoder? I would much prefer a MUX but I don't
> have a vector to use to select inputs.

Sure, just use "or" like you did in the Verilog ("|") instead of a
the "when" constructs.

Eric

To post a message, send it to: f...
To unsubscribe, send a blank message to: f... Start a New Thread