flags vs. comparator

Discussion in 'VHDL' started by Valentin Tihomirov, Nov 10, 2003.

  1. The task is to update N first bits of a M-bit wide register. I can accompany
    each input with a flag telling whether input should be updated or not.
    Alternatively, I can calculate validity of an input with a <N comparator at
    the input.
    This issue is very similar to coding scheme of FSM states. The first of the
    options corresponds to Gray style, the second is natural compact coding. Now
    I need to choose between them. Cosidering Performance vs. Area trade off, I
    think that solution with flags is faster because of much simpler
    combinatorial logic. For the same reason it should consume less area.
    Maximal value of N is 7.


    Question: Which one would you choose?




    Quantitative approach:

    Logic required for flags:
    - N flag registers.
    Logic required for comparators:
    log2(N)-bit wide register for for holding N;
    N comparators;
    complexity of comparator is proportional to log2(N), i.e. k*log2(N)
    ----------------
    total: N regs vs. log2(N) regs + N*k*Log2(N) gates
    This shows that Gray coding is good for large N as well. There should be a
    mistake in calculations.
    Valentin Tihomirov, Nov 10, 2003
    #1
    1. Advertising

  2. Valentin Tihomirov wrote:
    > The task is to update N first bits of a M-bit wide register.


    > The first of the
    > options corresponds to Gray style, the second is natural compact coding. Now
    > I need to choose between them.


    > Question: Which one would you choose?


    I would code it as a FOR loop inside
    a clocked process and let synthesis
    pack the gates.

    -- Mike Treseler
    Mike Treseler, Nov 11, 2003
    #2
    1. Advertising

  3. "Valentin Tihomirov" <> wrote in
    message news:bop0ra$1gufoo$-berlin.de...
    > The task is to update N first bits of a M-bit wide register.

    [...]
    > Quantitative approach:
    >
    > Logic required for flags:
    > - N flag registers.
    > Logic required for comparators:
    > log2(N)-bit wide register for for holding N;
    > N comparators;
    > complexity of comparator is proportional to log2(N), i.e. k*log2(N)
    > ----------------
    > total: N regs vs. log2(N) regs + N*k*Log2(N) gates


    Valentin,
    I see no mistake in your calculation, but surely there is a mistake
    in your assumptions. To create the N-bit thermometer code
    (I think that's the correct name for a code that has all bits
    set from bit 0 up to bit N) you will need some
    additional resources, unless the nature of the problem means
    that you already have the thermometer code available from some
    other part of the logic.

    For large N there may also be some routing implications,
    perhaps?

    If you are prepared to accept long combinational delays,
    you can create the thermometer code using a long ripple
    chain of OR gates (syntax not checked, but the idea is OK):

    ripple_thermometer_code_loop: for i from 0 to M-1 generate
    if i = 0 generate
    mask(i) <= '1' when N = i else '0';
    end;
    if i > 0 generate
    mask(i) <= '1' when N = i else mask(i-1);
    end;
    end generate;

    This makes much simpler logic than the parallel implementation
    you are considering:

    parallel_thermometer_code_loop: for i from 0 to M-1 generate
    mask(i) <= '1' when N >= i else '0';
    end generate;

    In most FPGAs you should be able to exploit the carry chain
    to make a ripple implementation go quickly.
    --

    Jonathan Bromley, Consultant

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

    Doulos Ltd. Church Hatch, 22 Market Place, Ringwood, Hampshire, BH24 1AW, UK
    Tel: +44 (0)1425 471223 mail:
    Fax: +44 (0)1425 471573 Web: http://www.doulos.com

    The contents of this message may contain personal views which
    are not the views of Doulos Ltd., unless specifically stated.
    Jonathan Bromley, Nov 11, 2003
    #3
  4. There should not be any routing implications when loading '1' into all cells
    because most prog logic devices incorporate built-in wiring for preset. I
    was misunderstood. The task is not to activate all inputs 0 to N-1. The task
    is to load the inputs with data. The reamaining inputs remain intact. And
    I'm looking for flagging mechanism. The flag controls a MUX2 with OLD_VALUE,
    NEW_VALUE inputs. The value is submitted to a buffer. In other words, the
    task is to activate (set to '1') selectr of a mux2.

    One option is to use a comparator, calculating mux2's selector basing on
    index of the input.
    for I in 0 to D_WIDTH loop
    -- here N isn't a const but is a registered value
    D(I) <= NEW_VALUE(I) when i < N else Q(I);
    end loop;

    Another option is to have a flag-FF accompanying each input
    for I in 0 to D_WIDTH loop
    D(I) <= NEW_VALUE(I) when FLAG(I) = '1' else Q(I);
    end loop;



    I will have thermometer-like carry-loading chain. There are twio phases in
    my system.
    1) Scale is rising one point each clock cycle (N := N + 1) until a
    condition is reached;
    2) N is used to load N first celss of a buffer.

    I'm asking what should I load during first phase on new point:
    - increment N counter; or
    - shift '1' into flag-FFs.


    Thanks.
    Valentin Tihomirov, Nov 11, 2003
    #4
  5. "Valentin Tihomirov" <> wrote in
    message news:boqr74$1h23uq$-berlin.de...
    > There should not be any routing implications when loading '1' into all

    cells
    > because most prog logic devices incorporate built-in wiring for preset. I
    > was misunderstood.


    No, you weren't; but I think I probably expressed my reply in
    an unnecessarily complicated way.

    > The task is not to activate all inputs 0 to N-1. The task
    > is to load the inputs with data. The reamaining inputs remain intact. And
    > I'm looking for flagging mechanism. The flag controls a MUX2 with

    OLD_VALUE,
    > NEW_VALUE inputs. The value is submitted to a buffer. In other words, the
    > task is to activate (set to '1') selectr of a mux2.


    I completely understood that. My examples indicated how you
    might obtain the mux-selector bits.

    > One option is to use a comparator, calculating mux2's selector basing on
    > index of the input.
    > for I in 0 to D_WIDTH loop
    > -- here N isn't a const but is a registered value
    > D(I) <= NEW_VALUE(I) when i < N else Q(I);
    > end loop;


    I gave you similar code that would create the
    selector bits. My version used "generate",
    so it was OK to use "when...else". You cannot use when...else
    in procedural code in VHDL.

    > Another option is to have a flag-FF accompanying each input
    > for I in 0 to D_WIDTH loop
    > D(I) <= NEW_VALUE(I) when FLAG(I) = '1' else Q(I);
    > end loop;


    Indeed. But you did not tell us how you might obtain that
    set of flag values. I assumed that you were asking how to
    obtain the flag values.

    > I will have thermometer-like carry-loading chain. There are twio phases in
    > my system.
    > 1) Scale is rising one point each clock cycle (N := N + 1) until a
    > condition is reached;
    > 2) N is used to load N first celss of a buffer.


    You didn't tell us that. If you had made this clear, we would
    probably have given different answers.

    > I'm asking what should I load during first phase on new point:
    > - increment N counter; or
    > - shift '1' into flag-FFs.


    If you are ABSOLUTELY SURE that N will always increment, and cannot
    change in any other way, then I suggest that an explicit thermometer
    code chain is appropriate. Flip-flops are cheap in an FPGA, and
    the thermometer code is easy to write.

    The "array of comparators" implementation is crazy in your situation,
    because you KNOW that every comparison result will be true if it
    has been true once before. At each step, every comparator except
    the Nth will re-calculate a result that is already known to be true.
    That would be a ridiculous waste of hardware.
    --

    Jonathan Bromley, Consultant

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

    Doulos Ltd. Church Hatch, 22 Market Place, Ringwood, Hampshire, BH24 1AW, UK
    Tel: +44 (0)1425 471223 mail:
    Fax: +44 (0)1425 471573 Web: http://www.doulos.com

    The contents of this message may contain personal views which
    are not the views of Doulos Ltd., unless specifically stated.
    Jonathan Bromley, Nov 11, 2003
    #5
  6. Amazing

    > The "array of comparators" implementation is crazy in your situation,
    > because you KNOW that every comparison result will be true if it
    > has been true once before. At each step, every comparator except
    > the Nth will re-calculate a result that is already known to be true.
    > That would be a ridiculous waste of hardware.


    How couldn't I realize this myself? Thank you very much for the idea.
    Valentin Tihomirov, Nov 11, 2003
    #6
    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. sunil
    Replies:
    4
    Views:
    768
    Ralf Hildebrandt
    Feb 22, 2004
  2. sk

    comparator problem

    sk, Nov 3, 2004, in forum: VHDL
    Replies:
    0
    Views:
    843
  3. john

    counter plus comparator

    john, Nov 8, 2004, in forum: VHDL
    Replies:
    4
    Views:
    762
    Raghavendra
    Nov 10, 2004
  4. Replies:
    6
    Views:
    502
  5. Steve Holden
    Replies:
    0
    Views:
    772
    Steve Holden
    Feb 8, 2009
Loading...

Share This Page