flags vs. comparator

[Valentin Tihomirov]

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.

 

[Mike Treseler]

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

 

[Jonathan Bromley]

"Valentin Tihomirov" <valentin@abelectron.com> wrote in
message news:bop0ra$1gufoo$1@ID-212430.news.uni-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: jonathan.bromley@doulos.com
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.

 

[Valentin Tihomirov]

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.

 

[Jonathan Bromley]

"Valentin Tihomirov" <valentin@abelectron.com> wrote in
message news:boqr74$1h23uq$1@ID-212430.news.uni-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: jonathan.bromley@doulos.com
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.

 

[Valentin Tihomirov]

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.