Query about optimization

[Vinay Deshpande]

Hi all,
I am a newbie to VHDL. My query is about the optimization.
I created two versions of a N-bit adder. One with just C <= A + B;
and compiled it. It took 8 LEs. In second design I wrote a
hierarchical code for same. Like starting from a full adder, then
instantiating it to higher one. On compilation I got 20 LEs? Now my
question is, both circuits are essentially doing same job, no more no
less. Then why there is huge difference in LEs? Same thing I observed
with multiplier also. Do compilers have optimal implementations for
these operators (+, *)?
Waiting for reply.
Vinay

 

[Colin Paul Gloster]

Vinay Deshpande posted:

" I am a newbie to VHDL. My query is about the optimization.
I created two versions of a N-bit adder. One with just C <= A + B;
and compiled it. It took 8 LEs. In second design I wrote a
hierarchical code for same. Like starting from a full adder, then
instantiating it to higher one. On compilation I got 20 LEs? Now my
question is, both circuits are essentially doing same job, no more no
less. Then why there is huge difference in LEs? Same thing I observed
with multiplier also. Do compilers have optimal implementations for
these operators (+, *)?"

Hello,

The term "optimization" is very commonly misused, and not just in the
HDL communities. To run a synthesizer (or for something which is
not a HDL, a compiler) which will definitely always provide the best
solution (i.e. which will definitely always perform true optimization)
is an intractable problem (it would run for months for a design which
a practical, suboptimal compromise would take merely hours to produce
a netlist for).

Regards,
Colin Paul Gloster

 

[Vinay Deshpande]

Vinay Deshpande posted:

" I am a newbie to VHDL. My query is about the optimization.
I created two versions of a N-bit adder. One with just C <= A + B;
and compiled it. It took 8 LEs. In second design I wrote a
hierarchical code for same. Like starting from a full adder, then
instantiating it to higher one. On compilation I got 20 LEs? Now my
question is, both circuits are essentially doing same job, no more no
less. Then why there is huge difference in LEs? Same thing I observed
with multiplier also. Do compilers have optimal implementations for
these operators (+, *)?"

Hello,

The term "optimization" is very commonly misused, and not just in the
HDL communities. To run a synthesizer (or for something which is
not a HDL, a compiler) which will definitely always provide the best
solution (i.e. which will definitely always perform true optimization)
is an intractable problem (it would run for months for a design which
a practical, suboptimal compromise would take merely hours to produce
a netlist for).

Regards,
Colin Paul Gloster

But then why it takes less space in RTL design choice, i.e. C <= A +
B;?

 

[Eric Smith]

Do compilers have optimal implementations for
these operators (+, *)?

Yes. For instance, with your structual implementation out of
full adders, the synthesizer may not be able to figure out that
it can use the dedicated carry chain.

 

[Vinay Deshpande]

Yes. For instance, with your structual implementation out of
full adders, the synthesizer may not be able to figure out that
it can use the dedicated carry chain.

Thank you very much.
Vinay

 

[Andy]

Thank you very much.
Vinay

There are two areas where your hierarchical design would give most
synthesizers a harder problem. First, as noted above, synthesizers
have very good implementations of commonly used canned functions, like
"+", but often do not recognize a logical description as equivalent to
a canned function (the assumption is that if the designer wanted an
adder, they would have used "+"). Second, most synthesizers have only
limited optimization across entity boundaries, so a description that
spreads a combinatorial function across many entities is less likely
to result in a nearly optimal implementation.

Andy

 

[Vinay Deshpande]

There are two areas where your hierarchical design would give most
synthesizers a harder problem. First, as noted above, synthesizers
have very good implementations of commonly used canned functions, like
"+", but often do not recognize a logical description as equivalent to
a canned function (the assumption is that if the designer wanted an
adder, they would have used "+"). Second, most synthesizers have only
limited optimization across entity boundaries, so a description that
spreads a combinatorial function across many entities is less likely
to result in a nearly optimal implementation.

Andy

Thanks Andy,

 

[Vinay Deshpande]

There are two areas where your hierarchical design would give most
synthesizers a harder problem. First, as noted above, synthesizers
have very good implementations of commonly used canned functions, like
"+", but often do not recognize a logical description as equivalent to
a canned function (the assumption is that if the designer wanted an
adder, they would have used "+"). Second, most synthesizers have only
limited optimization across entity boundaries, so a description that
spreads a combinatorial function across many entities is less likely
to result in a nearly optimal implementation.

Andy

Thanks Andy

 

[Vinay Deshpande]

There are two areas where your hierarchical design would give most
synthesizers a harder problem. First, as noted above, synthesizers
have very good implementations of commonly used canned functions, like
"+", but often do not recognize a logical description as equivalent to
a canned function (the assumption is that if the designer wanted an
adder, they would have used "+"). Second, most synthesizers have only
limited optimization across entity boundaries, so a description that
spreads a combinatorial function across many entities is less likely
to result in a nearly optimal implementation.

Andy

Thanks Andy

 

[Frank Buss]

Same thing I observed
with multiplier also. Do compilers have optimal implementations for
these operators (+, *)?

Yes, there are FPGAs with some some hardware multipliers (e.g. 18 x 18 bit
multipliers on some Spartan FPGAs). Then a "*" would be optimized to zero
LEs and one multiplier

 

[KJ]

Second, most synthesizers have only

limited optimization across entity boundaries, so a description that
spreads a combinatorial function across many entities is less likely
to result in a nearly optimal implementation.

Do you have any code that actually demonstrates this lack of optomization?

KJ

 

[Vinay Deshpande]

Do you have any code that actually demonstrates this lack of optomization?

KJ

You can try the example which I quoted above. Create two
implementations of N-bit full adder, one with simple statement like C
<= A + B; and other using hierarchical design starting from a simple
full adder. You can see difference in logic elements consumed by both
implementations.

 

[KJ]

You can try the example which I quoted above. Create two
implementations of N-bit full adder, one with simple statement like C
<= A + B; and other using hierarchical design starting from a simple
full adder. You can see difference in logic elements consumed by both
implementations.

That's not what I was asking about. The comment that Andy made that I
questioned was directed at logic that spans multiple entities. What he said
was that the entity presented some sort of boundary that made it difficult
to optomize logic across. I've yet to see any evidence of such a barrier
and asked him for an example to back up his claim (and one would also need
to know which synthesis tool has this problem since that is the tool that
has the problem). What I've seen is that the logic gets flattened into a
netlist right at the outset, the entity 'boundaries' at that point no longer
exist and they have no such effect as claimed. It could be though that
older tools, or crappy tools, for whatever reason, did (or do) have this
limitation (maybe they optomized entities but not globally with a flattened
netlist). Hence the question.

As for your example, there are multiple n-bit adder algorithms and I suspect
that C<=A+B is implemented with a different base algorithm than the
cascading of smaller adders. Your view is that both produce the sum of two
numbers and are functionally identical but optomizers are not so smart as to
discern better algorithms from logic but what they are good at is inferring
from the top level code what the best algorithm to implement is....and then
optomize the logic for that. A crude example would be if you were to code a
discrete Fourier transform algorithm that produces frequency responses from
a set of input numbers and expect that an optomizer would be able to figure
out that an FFT would be better algorithm to use. Both would give you the
same overall function but different implementations one of which would be
'better'. Having said that, though I'll admit that I don't know just which
base algorithm your tool happened to choose and how (or if) it differed from
your hand coded version and whether the observed differences were because of
a different algorithm choice at the outset or because of an entity boundary
barrier effect. But you can't assume that just because you got different
results from different source code that it is an example of an entity
boundary barrier limitation.

KJ

 

[Brian Drummond]

Do you have any code that actually demonstrates this lack of optomization?

KJ

does "keep_hierarchy=true" count?



- Brian

 

[Andy]

Do you have any code that actually demonstrates this lack of optomization?

KJ

Not recently, no. Symplify usually does a pretty good job, but I don't
generally cross hierarchical boundaries with combinatorial logic (like
a recursive, hierarchical adder, etc.)

Andy