N-input AND gate

T

TigerJade

Guest
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
 
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.
Click to expand...
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
 
TigerJade wrote:

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.
Click to expand...
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.
 
Thanks for the information.
It looks like the chain-shape AND and the tree-shape AND have the same
topology aftern synthesis.

TJ
 
But this type of implementation has propagation delay of N AND gates.
Click to expand...
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.
 
Hubble wrote:
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.
Click to expand...
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
 
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.
 
TigerJade wrote:

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.
Click to expand...
Thanks for posting your results.
I guess I would be surprised if any
of the top synthesis tools performed
any differently.

-- Mike Treseler
 
Mike Treseler wrote:
TigerJade wrote:

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
Click to expand...

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
 
You must log in or register to reply here.

Welcome to EDABoard.com

Sponsor

Back
Top