Advanced use of VHDL - Factorial example

Discussion in 'VHDL' started by Bert_Paris, Apr 27, 2009.

  1. Bert_Paris

    Bert_Paris Guest

    I have assembled an Application Note summarizing some
    VHDL Coding Techniques that can be useful in an number
    of situations.

    Covers : some RTL issues, dealing with large integers,
    recursivity, unconstrained vectors in ports, using
    operators as function calls...

    Anyone spotting error(s) is welcome to report ;-)

    http://www.alse-fr.com/archive/Factorial.pdf

    Bert Cuzeau
     
    Bert_Paris, Apr 27, 2009
    #1
    1. Advertising

  2. Matthew Hicks wrote:

    > I
    > also think your choice of using recursive functions is overly complex,
    > especially for anyone who is not a VHDL expert.


    Some non-vhdl guys know C or python.

    > The same effect could
    > be had by using loop and generate statements to explicitly build a
    > look-up table.


    Not the same effect.
    Fewer would learn something new.

    > P.S. - Can you provide an example where using unconstrained arrays for
    > port objects is better that using arrays constrained by generic values?


    Synthesis can't override the default generics on the top entity.
    However, I'm not sure that a wrapper is less trouble.

    I would like to thank Bert for taking the trouble
    to document and publish this example.
    While it's not exactly my style, it is working code,
    and I may even pull it out the next time someone
    complains about the verbosity of vhdl.

    -- Mike Treseler
     
    Mike Treseler, Apr 28, 2009
    #2
    1. Advertising

  3. Bert_Paris

    Bert_Paris Guest

    Hi Matthew,

    Matthew wrote :
    >> I have assembled an Application Note summarizing some VHDL Coding
    >> Techniques that can be useful in an number of situations.
    >>
    >> Covers : some RTL issues, dealing with large integers, recursivity,
    >> unconstrained vectors in ports, using operators as function calls...
    >>
    >> Anyone spotting error(s) is welcome to report ;-)
    >>
    >> http://www.alse-fr.com/archive/Factorial.pdf
    >>
    >> Bert Cuzeau
    >>

    >
    > I had many problems with the coding style... until I read the second part of
    > the paper. You should make sure to mention that all those type conversions
    > in the first part of the paper is a bad coding style.


    They definitely are *NOT* bad style at all !!!!
    To make a long story short :
    - ports are SLV
    - you need numbers internally
    So you have to juggle with conversions, but that's in no way difficult
    !
    Just looks a bit awkward for someone not knowing the language.
    With a very little bit of experience, you just write them without
    thinking.
    At times, you may come to hate VHDL for being so strongly typed,
    but when you use Verilog and spend hours finding out gross errors
    that wouldn't even compile in VHDL, you think it's a nice feature,
    after all :)

    > I also think your
    > choice of using recursive functions is overly complex, especially for anyone
    > who is not a VHDL expert.


    I don't think it takes a VHDL expert to understand
    fact(I) = I * fact(I-1).
    Doesn't sound more challenging that a loop.

    > The same effect could be had by using loop ...


    I think I mentioned this.
    But if you took this paper as an apology for recursive definition of
    functions, I must have been not explicit enough. I think I was clear
    that it was not the interest of the paper.

    > and generate statements

    Why would you need generate ? ? ?
    > to explicitly build a look-up table.


    > I also think that
    > this technique is better in that it does not rely as heavily on the synthesis
    > tool's ability to infer the best solution.


    Again, that's not correct. The final solution relies exclusively on the
    ability of the synthesis tool to reduce combinational logic !
    Not very advanced technology I would say.

    > Also, a very advanced technique,
    > using the knowledge that the predefined operators are just functions to slice
    > their output. I like it, but you should explain why you can do this in a
    > more in-depth manner.


    This paper is not intended to replace the Expert VHDL Training courses
    that we deliver ;-)
    But I don't think I revealed such a big secret either.
    It's meant to make sure you remember you saw the solution whenever you
    try to extract a slice from an operation result.

    > You could also overload the operator, creating a
    > result that you don’t have to slice (which requires more explanation).


    I am strongly against overloading standard operators, but that's
    another story. In that case, it would probably look bad.
    Can you share your solution ?

    > I also, liked, and never thought of, using unconstrained arrays as port
    > signal types and having the higher-level module constrain them. I still
    > prefer using generics for this, but I'll add it to my toolbox just in case.


    Using generics add more lines of code and is a potential source of more
    errors. (the code could use a generic incorrectly)

    > Overall, I would remove most of the first half of the paper and just present
    > the naive (bad) approach, then go into detail on better ways of doing things.


    Don't agree.
    The first part is certainly not "bad" !
    It's the recommended approach usually (when the function is correctly
    transformed by the synthesis tools).
    Imagine the Factorial function is an incrementer, do you think the look
    up table approach is better that saying out <= in + 1 ?
    With 32 bits inputs (and a 4 gigawords table) ?

    > P.S. - Can you provide an example where using unconstrained arrays for port
    > objects is better that using arrays constrained by generic values? One plus
    > for generics is that you don't need a wrapper to work with a single unit if
    > you use the defaults.


    Please, rewrite the example with generics, loops and generate, and
    compare. Again, nothing better than some coding to understand issues.

    btw : having generics at the top level also has issues.
    Some synthesis tools can over-ride them, or you can use the default
    values. Unconstrained vectors is a very elegant and reliable way of
    doing things.

    > P.P.S - Compiler writers hate you. :)


    I don't think I'm abusing the language !

    Bert
     
    Bert_Paris, Apr 28, 2009
    #3
  4. Bert_Paris

    Sean Durkin Guest

    Matthew Hicks wrote:

    > That doesn't answer my question, as generics are still a better choice
    > in this case, because you can't even synthesize (or simulate for that
    > matter) unconstrained arrays.


    Of course you can. The array becomes constrained as soon as you connect
    a constrained signal to it. I use this quite often, actually, simulates
    and synthesizes fine with every tool I've ever tried (ModelSim,
    ActiveHDL, XST, Precision, Synplify).

    Simple example:

    I often do image-processing blocks. The bidtwidth of the pixels can be 8
    in one case, 12 or 14 in another, the underlying operations remain the
    same. Now I can solve this using a GENERIC, but then I'd have to drag
    that GENERIC all through the hierarchy. Besides, the GENERIC clutters up
    my entity declarations:

    entity do_stuff is
    generic (
    BITWIDTH : positive := 8
    );
    port (
    clk : in std_logic;
    pix_in : in std_logic_vector(BITWIDTH-1 downto 0);
    pix_out : out std_logic_vector(BITWIDTH-1 downto 0);
    pix_mean : out std_logic_vector(BITWIDTH-1 downto 0);
    pix_min : out std_logic_vector(BITWIDTH-1 downto 0);
    pix_ax : out std_logic_vector(BITWIDTH-1 downto 0)
    );
    end entity do_stuff;

    Looks ugly IMHO, only gets worse if you e.g. have separate RGB-values
    and such. Now, I could instead use records or special types to make it
    look nicer, but then I couldn't use a GENERIC, but would have to use
    i.e. a constant defined in a package and the corresponding type
    declarations. Then it would look better, but I'd have to drag a package
    all through the hierarchy, and into every project I want to use that
    specific module in.

    So, what I do is use unconstrained arrays, and declare special types
    inside the architecture:

    entity do_stuff is
    port (
    clk : in std_logic;
    pix_in : in std_logic_vector;
    pix_out : out std_logic_vector;
    );
    end entity do_stuff;

    architecture bla of do_stuff is

    subtype t_pixdata is std_logic_vector(pix_in'length-1 downto 0);
    -- I think std_logic_vector(pix_in'range) might work, too

    signal pixel : t_pixdata;

    begin
    -- do stuff with pixels
    end architecture bla;

    This is "portable" (I can use it in every project without needing any
    additional files), doesn't need any special constants or packages,
    doesn't have a cluttered up port list and I don't have to drag a GENERIC
    all through the hierarchy, which I might forget to hook up somewhere
    along the line. I like to have only things configurable that need to be
    configured. In this case, the width of the vectors can unmistakably be
    deduced from the connected signals, so there's really no need to make it
    configurable. My experience is that things that can be configured,
    somebody will configure wrong, so it's better not to even give them the
    chance :)

    The only thing you have to take care of is that when you instantiate
    do_stuff, the signals you connect to the unconstrained ports must be
    constrained. But I think "constrainedness" even propagates down.

    So, for me this works well, but I guess it's more of a personal
    preference. BTW, I use GENERICs, too, but for other stuff, things that
    can't be deducted from something else.

    cu,
    Sean

    --
    Replace "MONTH" with the three-letter abbreviation of the current month
    (simple, eh?).
     
    Sean Durkin, Apr 28, 2009
    #4
  5. Bert_Paris

    Tricky Guest


    >
    > This is "portable" (I can use it in every project without needing any
    > additional files), doesn't need any special constants or packages,
    > doesn't have a cluttered up port list and I don't have to drag a GENERIC
    > all through the hierarchy, which I might forget to hook up somewhere
    > along the line. I like to have only things configurable that need to be
    > configured. In this case, the width of the vectors can unmistakably be
    > deduced from the connected signals, so there's really no need to make it
    > configurable. My experience is that things that can be configured,
    > somebody will configure wrong, so it's better not to even give them the
    > chance :)
    >


    But you can prevent incorrect configs, or at least throw up warnings
    as discussed in another thread. The following code throws a warning in
    most synthesisers, and actually halts Quartus:

    function check_setup return boolean is
    begin
    assert (ip'length = 8 or ip'length = 10 or ip'length = 12)
    report "Invalid Input Length detected" severity failure;
    return true;
    end check_setup;

    constant CONFIG_CHECKED : boolean := check_setup;

    This method can also be used to check for illegal generic
    combinations.
     
    Tricky, Apr 28, 2009
    #5
  6. Bert_Paris

    KJ Guest

    >
    > The only thing you have to take care of is that when you instantiate
    > do_stuff, the signals you connect to the unconstrained ports must be
    > constrained. But I think "constrainedness" even propagates down.
    >


    Also remember that unconstrained means that you don't even know which
    'direction' the bits go (i.e. 0 to 7 or 7 downto 0). It's quite easy to
    muck something up because in your mental model and your testbench you only
    considered the following form of port map

    signal xyz: std_logic_vector(7 downto 0);
    ....
    dut : entity work.widget port map(a => xyz);

    And haven't tested or considered if widget works correctly for this...

    signal xyz: std_logic_vector(0 to 7);
    ....
    dut : entity work.widget port map(a => xyz);

    For code that you intend to only reuse yourself, this likely won't be an
    issue since you'll probably always use it in the same manner. For code
    intended for the masses, that will not be the case.

    If nothing else, using unconstrained arrays rather than a generic does imply
    that some additional testing *should* be performed to make sure that it
    works with "x to y", "x downto 5" and null arrays

    Kevin Jennings
     
    KJ, Apr 28, 2009
    #6
  7. Bert_Paris

    Bert_Paris Guest

    KJ wrote :
    >>
    >> The only thing you have to take care of is that when you instantiate
    >> do_stuff, the signals you connect to the unconstrained ports must be
    >> constrained. But I think "constrainedness" even propagates down.

    >
    > Also remember that unconstrained means that you don't even know which
    > 'direction' the bits go (i.e. 0 to 7 or 7 downto 0). It's quite easy to muck
    > something up because in your mental model and your testbench you only
    > considered the following form of port map


    Hi Kevin,

    Interesting question.

    I assume the users of this module follow my VHDL Coding Style Guide
    that I published here in the past. In particular, I am adamant at
    enforcing "downto 0" ranges when vectors represent numbers !
    Exceptions are a pain (PPC) and I don't even imagine an output like (7
    to 47) for the Factorial output vector.
    And even... would this be really a problem ?
    What reliability do you gain by using "40 downto 0" ? This doesn't say
    the MSBit is 40, does it ?

    For an IP, I definitely agree that it is a good idea to add assertions
    that verify the ports are defined as expected.
    Note that not all synthesis tools accept passive processes, otherwise
    it's tempting to put these assertions in the entity itself.

    Thx for your feedback.

    Bert
     
    Bert_Paris, Apr 28, 2009
    #7
  8. Matthew Hicks wrote:

    > Well, my views comes from a person with degrees in Computer Science, so
    > I have written my fair share of software language programs, thus I'm
    > well versed in things like recursion. When I write hardware, I am not
    > writing software, I always think about what the synthesized hardware
    > will look like.


    The synthesized hardware looks like LUTs, flops and wires.

    > I guess that is why I prefer Verilog to VHDL. I try to
    > avoid coding styles that abstract the final HW implementation too much,
    > especially when dealing with novices.


    I'll stick with a bit of abstraction

    >>> The same effect could be had by using loop and generate statements to
    >>> explicitly build a look-up table.
    >>>

    >> Not the same effect.
    >> Fewer would learn something new.

    >
    > Agreed, but only for experts in VHDL. For those who aren't, this would
    > just confuse them and teach them a poor way to write code for actual
    > industrial use.


    I don't agree.
    Generated structures are very fussy around the edges.
    I'll stick with structured registers.
    Custom types and subtypes are vhdl's advantage.

    >>> P.S. - Can you provide an example where using unconstrained arrays
    >>> for port objects is better that using arrays constrained by generic
    >>> values?
    >>>

    >> Synthesis can't override the default generics on the top entity.
    >> However, I'm not sure that a wrapper is less trouble.

    >
    > That doesn't answer my question, as generics are still a better choice
    > in this case, because you can't even synthesize (or simulate for that
    > matter) unconstrained arrays.


    Like I said, I agree with that,
    but top generics are a synthesis annoyance nevertheless.

    -- Mike Treseler
     
    Mike Treseler, Apr 28, 2009
    #8
  9. Bert_Paris

    Andy Guest

    A couple of my own thoughts on this.

    First, I applaud the use of recursion! Yes we still design hardware,
    but at some point we have to move on from coding netlists of gates and
    flops, just like SW progressed from assembly code through higher and
    higher levels of abstraction. I usually code the simplest description
    of the behavior I can come up with, and then, only if the synthesis
    tool cannot meet timing/area/power/etc. will I try a harder-to-read/
    write/understand description that the synthesis tool may like better.

    Use of unconstrained std_logic_vector on ports: I like it, but...
    since the ports must be constrained by an upper level signal or port,
    then by definition, this is not a primary (device level port), and
    there is absolutely no need to hobble oneself with SLV ports when
    integer, unsigned or something else will work better. Non-SL/SLV
    primary ports are only a "bad thing" if you want/need to be able to
    simulate a post-synthesis or post-P&R netlist without a wrapper to
    convert the tool-generated SL/SLV ports back to whatever your test
    bench (written for the original RTL description/ports) expects. To my
    way of thinking, SLV should only be used when a uniform numerical
    interpretation of the contents is not appropriate. If I'll write

    When I do have to use SLV, I usually throw in a subtype definition:

    subtype slv is std_logic_vector; -- unconstrained subtype

    This way, "slv" can be used for signal/variable declarations and
    conversions instead of "std_logic_vector".

    Finally, the table array effectively constrains the input size to 31
    bits (maximum width of the table index) anyway.

    Andy
     
    Andy, Apr 28, 2009
    #9
  10. Andy wrote:

    > I usually code the simplest description
    > of the behavior I can come up with, and then, only if the synthesis
    > tool cannot meet timing/area/power/etc. will I try a harder-to-read/
    > write/understand description that the synthesis tool may like better.


    Yes. Why generate half adders,
    if c := a + b; works just as well.

    > Use of unconstrained std_logic_vector on ports: I like it, but...
    > since the ports must be constrained by an upper level signal or port,
    > then by definition, this is not a primary (device level port), and
    > there is absolutely no need to hobble oneself with SLV ports when
    > integer, unsigned or something else will work better.


    That's the main point.
    For registers inside the top wrapper,
    synthesis can keep track of the bit encoding.
    If want an enumerated array of signed counters, let it be.
    For device pins, explicit SLVs make sense for verilog compatibility.

    -- Mike Treseler
     
    Mike Treseler, Apr 28, 2009
    #10
  11. Bert_Paris

    Andy Guest

    More comments:

    The function call notation trick for the multiply is not a good idea,
    especially when numeric_std provides a resize() function that also
    warns when the numeric value is truncated:

    res := resize(d * fact(d-1), res'range);

    More readable & more functional.

    I'm not crazy about widespread use of one-liner flops, but in limited
    doses they work well.

    Andy
     
    Andy, Apr 29, 2009
    #11
  12. Bert_Paris

    Bert_Paris Guest

    Andy wrote :
    > The function call notation trick for the multiply is not a good idea,
    > especially when numeric_std provides a resize() function that also
    > warns when the numeric value is truncated:
    >
    > res := resize(d * fact(d-1), res'range);
    >
    > More readable & more functional.


    Thanks for the comments !

    In this specific case, you're absolutely right. I will mention
    this in a revised version.
    I always recommend using resize for the benefit of being warned
    during simulation, and I could have applied it here.
    I think the function notation trick is still useful to know (like
    for just extracting a slice "in the middle" of a vector, or for
    testing the carry only, etc).

    > I'm not crazy about widespread use of one-liner flops, but in limited
    > doses they work well.


    I use them essentially for resynch (especially when no reset).
    I don't think using a process in this case enhances the readability.

    Bert
     
    Bert_Paris, Apr 29, 2009
    #12
  13. > Andy wrote :
    >> I'm not crazy about widespread use of one-liner flops, but in limited
    >> doses they work well.


    Bert_Paris wrote:
    > I use them essentially for resynch (especially when no reset).
    > I don't think using a process in this case enhances the readability.


    Maybe not, but it might enhance maintainability
    when I add a feature or a reset.

    -- Mike Treseler
     
    Mike Treseler, Apr 29, 2009
    #13
  14. On 2009-04-28, Mike Treseler <> wrote:

    |-------------------------------------------------------------------------|
    |"Matthew Hicks wrote: |
    | |
    |[..] |
    | |
    |> The same effect could |
    |> be had by using loop and generate statements to explicitly build a |
    |> look-up table. |
    | |
    |Not the same effect. |
    |Fewer would learn something new. |
    | |
    |[..]" |
    |-------------------------------------------------------------------------|

    Mr. T.,

    I love you.

    Love,
    C. P. G.
     
    Nicholas Paul Collin Gloucester, May 6, 2009
    #14
    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. Silver
    Replies:
    9
    Views:
    683
    red floyd
    Dec 5, 2003
  2. Replies:
    2
    Views:
    472
    marbac
    May 8, 2005
  3. aNt17017

    Long(er) Factorial

    aNt17017, Apr 21, 2006, in forum: C Programming
    Replies:
    35
    Views:
    960
    Keith Thompson
    Apr 26, 2006
  4. afd
    Replies:
    1
    Views:
    8,360
    Colin Paul Gloster
    Mar 23, 2007
  5. Michele Simionato
    Replies:
    1
    Views:
    604
    Lacrima
    Mar 27, 2010
Loading...

Share This Page