N-input AND gate

T

TigerJade

Hi,
I'm thinking about to write a N-input AND gate like this:
signal A : std_logic_vector(N-1 downto 0)
process (A)
variable result: std_logic;
begin
result := '1';
for i in N-1 downto 0 loop
result := result and A(i);
end loop;
Y <= result;
end process;
But this type of implementation has propagation delay of N AND gates. I
believe a tree type of AND gates will have only propagation delay of
log2(N), which is a significant reduction if N is large, although the
number of AND gates is the same.

Is it possible using some loop or generate statements to produce a
tree-type N-input AND gate, which is suitable for for all values of N,
or even just N = any power of 2.

Regards,
TJ
 
M

Mike Treseler

TigerJade wrote:

Is it possible using some loop or generate statements to produce a
tree-type N-input AND gate, which is suitable for for all values of N,
or even just N = any power of 2.

Synthesis does a pretty good job with AND gates.
Consider describing your design at a higher level
and see if this is really a problem that
needs a solution.

-- Mike Treseler
 
D

David Bishop

TigerJade said:
Hi,
I'm thinking about to write a N-input AND gate like this:
signal A : std_logic_vector(N-1 downto 0)
process (A)
variable result: std_logic;
begin
result := '1';
for i in N-1 downto 0 loop
result := result and A(i);
end loop;
Y <= result;
end process;
But this type of implementation has propagation delay of N AND gates. I
believe a tree type of AND gates will have only propagation delay of
log2(N), which is a significant reduction if N is large, although the
number of AND gates is the same.

The function you are looking for is called "and_reduce", and you will
find a copy in:

http://www.eda.org/vhdl-200x/vhdl-200x-ft/packages/std_logic_1164_additions.vhd

It uses recursion, but I've tested it in several synthesis tools.

In the final version of vhdl-2005 it should be an overload for the "and"
function.
 
T

TigerJade

Thanks for the information.
It looks like the chain-shape AND and the tree-shape AND have the same
topology aftern synthesis.

TJ
 
H

Hubble

But this type of implementation has propagation delay of N AND gates.

Really? This is not a structure using and gates as components but
already an algorithmic destription of the problem inside a process.
The Y driver will happily deliver the result after one delta. Or did I
miss somehting here?

Hubble.
 
M

Mike Treseler

Hubble said:
Really? This is not a structure using and gates as components but
already an algorithmic destription of the problem inside a process.
The Y driver will happily deliver the result after one delta.

I think the OP is trying to compare synthesis results
for different AND algorithms. I agree that in theory
the algorithm shouldn't make any difference, but I
don't doubt that real synthesis has some sensitivity
to it.

I prefer to spend time describing and simulating
logical entities and leave the gate level details
alone. I guess it all depends on what you're doing.

-- Mike Treseler
 
T

TigerJade

Well. What I did is to write two VHDL architectures with the two
algorithms and synthesize them separately with Leonardo Spectrum and
its ADP package for ASIC techniques. After the synthesis, I compared
the circuits generated by it and the area, timing reports and found no
difference at all. I guess, it might heavily rely on the synthesis tool
used.
 
M

Mike Treseler

TigerJade said:
After the synthesis, I compared
the circuits generated by it and the area, timing reports and found no
difference at all. I guess, it might heavily rely on the synthesis tool
used.

Thanks for posting your results.
I guess I would be surprised if any
of the top synthesis tools performed
any differently.

-- Mike Treseler
 
J

Jos De Laender

Mike said:
Thanks for posting your results.
I guess I would be surprised if any
of the top synthesis tools performed
any differently.

-- Mike Treseler


It used to be one of my favourites ;-)

The most optimum solution is to write it recursively.
It synthesizes then always to a tree solution.

If you do the check on the *isolated* circuit the results will probably
be the same for the loop as for the recursive solution.

If you do the check on the construction buried in a bunch of other
functionality , it does make a difference.

My understanding is that a chain (for loop description) is initially
synthesized as a chain but can be optimized to a tree again , provided
that 'not too much logic' is around it.

The tree (recursive) is initially synthesized as a tree and stays like
that , independent of surrounding logic.

Or did synthesis tools improve that much since I left the field ?

Jos
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top