Multiple inputs adder

Discussion in 'VHDL' started by MariuszK, Jul 17, 2006.

  1. MariuszK

    MariuszK Guest

    Hello,

    I am looking for effective vhdl multiple input adders.
    Inputs count could be up to 1024 inputs!
    Requirements:
    - adder should be full parameterized (inputs count, adder words width,
    etc.)
    - adder should be optimized from viewpoint of time (frequency) and
    resources
    - adder should be pipelined

    Currently, I want build next tree structure.
    a0+a1+a2+a3+a4+a5+a6+a7+......a1023 =

    a0+a1 a2+a3 a4+a5 a6 +a7
    a01+a23 a45+a67
    a0123+a4567
    a01234567 + ...
    .........................................................
    a0123....1023

    This architecture for 1024 input adder will be included
    - 1023 two inputs adder
    - log2(1024)=10 pipeline stages


    Thank you for any answer.

    Best Regards
    Mariusz
    MariuszK, Jul 17, 2006
    #1
    1. Advertising

  2. MariuszK

    Andy Guest

    It would help to know how you get the input data (all at once, in order
    one operand per clock, random order one operand per clock, etc.)

    If you can only get one input per clock anyway, a simple accumulator
    (sum = sum + input) will be as high performance as you can get (the sum
    pops out 1 clock after the last input).

    The only time you'd need a binary tree type of implementation is if you
    have all inputs available at once (doubtful for 1024 inputs).

    Most synthesis tools are pretty good at turning a straight sum into a
    tree anyway:

    a+b+c+d => (a+b)+(c+d)

    But there are certainly limits as to how far they can go (1024
    inputs?).

    Andy


    MariuszK wrote:
    > Hello,
    >
    > I am looking for effective vhdl multiple input adders.
    > Inputs count could be up to 1024 inputs!
    > Requirements:
    > - adder should be full parameterized (inputs count, adder words width,
    > etc.)
    > - adder should be optimized from viewpoint of time (frequency) and
    > resources
    > - adder should be pipelined
    >
    > Currently, I want build next tree structure.
    > a0+a1+a2+a3+a4+a5+a6+a7+......a1023 =
    >
    > a0+a1 a2+a3 a4+a5 a6 +a7
    > a01+a23 a45+a67
    > a0123+a4567
    > a01234567 + ...
    > ........................................................
    > a0123....1023
    >
    > This architecture for 1024 input adder will be included
    > - 1023 two inputs adder
    > - log2(1024)=10 pipeline stages
    >
    >
    > Thank you for any answer.
    >
    > Best Regards
    > Mariusz
    Andy, Jul 17, 2006
    #2
    1. Advertising

  3. MariuszK

    MariuszK Guest

    Andy napisal(a):
    > It would help to know how you get the input data (all at once, in order
    > one operand per clock, random order one operand per clock, etc.)
    >
    > If you can only get one input per clock anyway, a simple accumulator
    > (sum = sum + input) will be as high performance as you can get (the sum
    > pops out 1 clock after the last input).
    >
    > The only time you'd need a binary tree type of implementation is if you
    > have all inputs available at once (doubtful for 1024 inputs).
    >
    > Most synthesis tools are pretty good at turning a straight sum into a
    > tree anyway:
    >
    > a+b+c+d => (a+b)+(c+d)
    >
    > But there are certainly limits as to how far they can go (1024
    > inputs?).
    >
    > Andy


    I will have all input data per clock - all at once. I want calculate
    this sum as fast as possible and with pipeline "possibility".

    By the way. How can I force synthesis tools to change straight sum into
    a tree calculation.
    Is that conversion made automatically? = a+b+c+d => (a+b)+(c+d)
    Additionally that "tree calculation" in my opinion should be made
    in few clocks tact to calculate i.e. 1024 inputs.
    Is pipeline architecture will made automatically by synthesis tools??


    Mariusz
    MariuszK, Jul 17, 2006
    #3
  4. On 17 Jul 2006 12:50:30 -0700, MariuszK
    <> wrote:

    >I will have all input data per clock - all at once. I want calculate
    >this sum as fast as possible and with pipeline "possibility".
    >
    >By the way. How can I force synthesis tools to change straight sum into
    >a tree calculation.


    Consider a recursive function or a recursive generate.

    Basically, to calculate sum(array):
    if array has one element ->
    result = that element,
    else ->
    result = sum(left half of array) + sum(right half of array)

    Some care is required to get everything exactly right if the
    array size is not an exact power of 2. Extreme care is
    required to get the bit widths of the sums right.

    >Is that conversion made automatically? = a+b+c+d => (a+b)+(c+d)


    Yes, for small calculations; probably not, for huge ones.

    >Additionally that "tree calculation" in my opinion should be made
    >in few clocks tact to calculate i.e. 1024 inputs.


    If you use a straightforward tree it will have 1023 adders over
    10 levels. So it would be very easy to pipeline it over 10 clocks,
    or perhaps over 5 clocks if you can squeeze two adds into
    one clock cycle.

    Depending on your target technology, other structures
    such as a Wallace tree may be more efficient than a
    simple tree of adders. It's harder to parameterise, though.

    >Is pipeline architecture will made automatically by synthesis tools??


    Not usually, although the better tools can do some pipelining if
    you give them appropriate hints. Note also that, unless you
    have a behavioural synth tool, you must describe the delays that
    will be introduced by the pipelining - not necessarily in the
    right place (the tool will move the delay registers into the
    pipeline where they will do the most good) but you must
    get the right number of cycles of delay.
    --
    Jonathan Bromley, Consultant

    DOULOS - Developing Design Know-how
    VHDL * Verilog * SystemC * e * Perl * Tcl/Tk * Project Services

    Doulos Ltd., 22 Market Place, Ringwood, BH24 1AW, UK

    http://www.MYCOMPANY.com

    The contents of this message may contain personal views which
    are not the views of Doulos Ltd., unless specifically stated.
    Jonathan Bromley, Jul 18, 2006
    #4
  5. MariuszK

    MariuszK Guest

    Hello,

    > Depending on your target technology, other structures
    > such as a Wallace tree may be more efficient than a
    > simple tree of adders. It's harder to parameterise, though.


    My target platform is Xilinx.

    Wallace tree structure could be used for multiple input adder???
    I use Wallace tree for multiplication, only.
    Could you send me any information (links, sample) how can I built
    wallace tree structure for multiple input adder? What others structure
    (except simple tree adder) could be used to build multiple input adder?

    Thanks
    Mariusz
    MariuszK, Jul 18, 2006
    #5
    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. Adrian Spilca

    Multiple input Adder

    Adrian Spilca, Jul 19, 2005, in forum: VHDL
    Replies:
    4
    Views:
    2,633
    Adrian Spilca
    Jul 19, 2005
  2. Martin Gustavsson

    IPostBackDataHandler with multiple rendered inputs.

    Martin Gustavsson, Mar 7, 2006, in forum: ASP .Net
    Replies:
    0
    Views:
    429
    Martin Gustavsson
    Mar 7, 2006
  3. Adi
    Replies:
    2
    Views:
    2,578
    Jens Thoms Toerring
    Nov 3, 2006
  4. Analog_Guy

    Multiple Reset Inputs

    Analog_Guy, Nov 20, 2010, in forum: VHDL
    Replies:
    3
    Views:
    1,013
  5. Sam
    Replies:
    2
    Views:
    123
Loading...

Share This Page