Query about optimization

Discussion in 'VHDL' started by Vinay Deshpande, May 22, 2007.

  1. 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
     
    Vinay Deshpande, May 22, 2007
    #1
    1. Advertising

  2. 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
     
    Colin Paul Gloster, May 22, 2007
    #2
    1. Advertising

  3. On May 22, 12:15 pm, Colin Paul Gloster <>
    wrote:
    > 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;?
     
    Vinay Deshpande, May 22, 2007
    #3
  4. Vinay Deshpande

    Eric Smith Guest

    Vinay Deshpande <> writes:
    > 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.
     
    Eric Smith, May 22, 2007
    #4
  5. On May 22, 1:03 pm, Eric Smith <> wrote:
    > Vinay Deshpande <> writes:
    > > 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.


    Thank you very much.
    Vinay
     
    Vinay Deshpande, May 22, 2007
    #5
  6. Vinay Deshpande

    Andy Guest

    On May 22, 3:51 am, Vinay Deshpande <> wrote:
    > On May 22, 1:03 pm, Eric Smith <> wrote:
    >
    > > Vinay Deshpande <> writes:
    > > > 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.

    >
    > 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
     
    Andy, May 22, 2007
    #6
  7. On May 22, 5:44 pm, Andy <> wrote:
    > On May 22, 3:51 am, Vinay Deshpande <> wrote:
    >
    > > On May 22, 1:03 pm, Eric Smith <> wrote:

    >
    > > > Vinay Deshpande <> writes:
    > > > > 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.

    >
    > > 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


    Thanks Andy,
     
    Vinay Deshpande, May 22, 2007
    #7
  8. On May 22, 5:44 pm, Andy <> wrote:
    > On May 22, 3:51 am, Vinay Deshpande <> wrote:
    >
    > > On May 22, 1:03 pm, Eric Smith <> wrote:

    >
    > > > Vinay Deshpande <> writes:
    > > > > 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.

    >
    > > 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


    Thanks Andy
     
    Vinay Deshpande, May 22, 2007
    #8
  9. On May 22, 5:44 pm, Andy <> wrote:
    > On May 22, 3:51 am, Vinay Deshpande <> wrote:
    >
    > > On May 22, 1:03 pm, Eric Smith <> wrote:

    >
    > > > Vinay Deshpande <> writes:
    > > > > 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.

    >
    > > 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


    Thanks Andy
     
    Vinay Deshpande, May 22, 2007
    #9
  10. Vinay Deshpande

    Frank Buss Guest

    Vinay Deshpande wrote:

    > 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 :)

    --
    Frank Buss,
    http://www.frank-buss.de, http://www.it4-systems.de
     
    Frank Buss, May 23, 2007
    #10
  11. Vinay Deshpande

    KJ Guest

    > 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
     
    KJ, May 23, 2007
    #11
  12. On May 23, 4:54 am, "KJ" <> wrote:
    > > 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


    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.
     
    Vinay Deshpande, May 23, 2007
    #12
  13. Vinay Deshpande

    KJ Guest

    "Vinay Deshpande" <> wrote in message
    news:...
    > On May 23, 4:54 am, "KJ" <> wrote:
    >> > 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

    >
    > 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
     
    KJ, May 23, 2007
    #13
  14. On Tue, 22 May 2007 19:54:59 -0400, "KJ" <>
    wrote:

    >> 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


    does "keep_hierarchy=true" count?

    :)

    - Brian
     
    Brian Drummond, May 23, 2007
    #14
  15. Vinay Deshpande

    Andy Guest

    On May 22, 6:54 pm, "KJ" <> wrote:
    > > 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


    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
     
    Andy, May 23, 2007
    #15
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Learner
    Replies:
    1
    Views:
    1,004
    Marina Levit [MVP]
    Jan 30, 2006
  2. Anonymous
    Replies:
    0
    Views:
    1,515
    Anonymous
    Oct 13, 2005
  3. Andy
    Replies:
    0
    Views:
    761
  4. Andy
    Replies:
    1
    Views:
    789
  5. Ravikiran

    Zero Optimization and Sign Optimization???

    Ravikiran, Nov 17, 2008, in forum: C Programming
    Replies:
    22
    Views:
    891
    Thad Smith
    Nov 24, 2008
Loading...

Share This Page