FPGARelated.com
Forums
   Forums    More Forums    comp.arch.fpga  

Using carry chain of counters for term count detect

Started by rickman ●August 14, 2009
Summary The discussion focuses on how to implement VHDL down counters that efficiently utilize hardware carry chains for terminal count (zero) detection.

The discussion focuses on how to implement VHDL down counters that efficiently utilize hardware carry chains for terminal count (zero) detection. The participants compare methods using integers versus unsigned vectors and explore how different synthesis tools, like Synplify and Lattice, optimize these structures.

The consensus suggests that while operand padding can force carry chain usage, modern synthesis tools often optimize these paths effectively regardless of the specific VHDL type used, provided the behavior is clearly defined.

  • Using an extra bit (operand padding) in unsigned subtraction allows the MSB to act as a carry out for zero detection.
  • Jim Lewis provided a vector-based algorithm that uses a single carry cell to implement zero detection more predictably than integer-based methods.
  • Synthesis tools like Synplify may deviate from traditional carry chains in technology mapping if they find a faster or smaller logic implementation.
  • The 'count - 1 < 0' logic trick works natively with integer types but requires manual resizing or sign-bit handling when using unsigned vectors.
VHDLFPGA SynthesisDigital Logic Design
I typically use down counters that are loaded with an initial value
and output a flag when reaching zero.  Sometimes the tools use the
carry chain and other times they don't.  I seem to recall that this
was discussed here a few months ago and someone posted a function or
other VHDL code that would produce a carry chain every time.  I
typically use a MOD operator for the counter, but the code I saw used
an integer for the count and subtracted one in the conditional of an
IF, then used the same expression in the counter assignment if the
result was not less than zero.  It appears that this was optimized to
share the same logic for both expressions.

I can't find this thread.  Anyone remember it and some keywords that
would let me find it?  There may be something wrong with Google
groups.  I search on "counter carry chain" and it finds *NO*
results.

Rick
Reply by KJ ●August 14, 20092009-08-14
On Aug 14, 6:36=A0pm, rickman <gnu...@gmail.com> wrote:

> I typically use down counters that are loaded with an initial value
> and output a flag when reaching zero. =A0



>
> I can't find this thread. =A0Anyone remember it and some keywords that
> would let me find it? =A0There may be something wrong with Google
> groups. =A0I search on "counter carry chain" and it finds *NO*


I think this is the link you're looking for.  Andy's post from June 19
is the 8th one in the thread.

http://groups.google.com/group/comp.lang.vhdl/browse_frm/thread/36d7833968f=
3e102/452a230826d347aa?q=3Ddown+counter+%22Andy%22+group:comp.lang.vhdl

Kevin Jennings
Reply by rickman ●August 16, 20092009-08-16
On Aug 14, 9:17 pm, KJ <kkjenni...@sbcglobal.net> wrote:

> On Aug 14, 6:36 pm, rickman <gnu...@gmail.com> wrote:
>
> > I typically use down counters that are loaded with an initial value
> > and output a flag when reaching zero.
>
> > I can't find this thread.  Anyone remember it and some keywords that
> > would let me find it?  There may be something wrong with Google
> > groups.  I search on "counter carry chain" and it finds *NO*
>
> I think this is the link you're looking for.  Andy's post from June 19
> is the 8th one in the thread.
>
> http://groups.google.com/group/comp.lang.vhdl/browse_frm/thread/36d78...
>
> Kevin Jennings


I guess that is the one.  I don't see where they brought out the carry
flag to use elsewhere though and when I implement this, I get two
adders and the one generating the term count uses extra logic just to
get the carry out of the chain.  This is using the Lattice tools in
their XP parts.

I seem to recall making this work by adding an extra bit to the input
value and separating the msb of the output as the carry.  I'll give
that a try.

Rick
Reply by Brian Davis ●August 16, 20092009-08-16
On Aug 15, 10:13 pm, rickman <gnu...@gmail.com> wrote:

>
> I seem to recall making this work by adding an extra bit to the input
> value and separating the msb of the output as the carry.  I'll give
> that a try.
>

 Not specific to your down counter problem, but I posted a
snippet a few years back that showed operand padding to
pull out the carry/overflow:

http://www.fpga-faq.com/archives/99500.html#99517

I'd first seen that in another post years ago,
that I can't locate anymore...

 I've also noticed troubles with the google archive search,
I've been using the archive search on fpga-faq.com instead

http://www.fpga-faq.com/archives/index.html

Brian
Reply by Andy ●August 16, 20092009-08-16
On Aug 14, 8:17=A0pm, KJ <kkjenni...@sbcglobal.net> wrote:

> On Aug 14, 6:36=A0pm, rickman <gnu...@gmail.com> wrote:
>
> > I typically use down counters that are loaded with an initial value
> > and output a flag when reaching zero. =A0
>
> > I can't find this thread. =A0Anyone remember it and some keywords that
> > would let me find it? =A0There may be something wrong with Google
> > groups. =A0I search on "counter carry chain" and it finds *NO*
>
> I think this is the link you're looking for. =A0Andy's post from June 19
> is the 8th one in the thread.
>
> http://groups.google.com/group/comp.lang.vhdl/browse_frm/thread/36d78...
>
> Kevin Jennings


Wow, what's old is new again...

I should note that since then, I have noticed that while the RTL view
from Synplify indicates using the next bit (carry), the technology
view sometimes comes up with something better, not necessarily using
the carry chain the way one would expect.

That said, I have never seen it do worse than a "count =3D 0"
comparison.

Also be aware that the "count - 1 < 0" (or "count + 1 > 2**n-1") trick
only works with integer types, not with unsigned vector types.

Andy
Reply by JimLewis ●August 17, 20092009-08-17
Hi Rick,
Integers and such are great for sim run time, however, if you are not
getting the hardware you want, here is an array based algorithm that
only uses one carry cell to implement the zero detect.  It has a few
extras that you may want to remove.  BaseReg is the loadable base
register.  CntReg keeps the current count value.  IntReg is a
registered version of the zero detect.

Best,
Jim
SynthWorks VHDL training


TimerProc : process (Clk, nReset)
  variable Dec : unsigned(CntReg'Length downto 0) ;
begin
  if (nReset = '0') then
    BaseReg <= (others => '0') ;
    CntReg  <= (others => '0') ;
    IntReg  <= '0' ;
  elsif rising_edge(Clk) then
    if (TimerSel = '1' and Read = '0') then
      BaseReg <= unsigned(DataIn) ;
    end if ;
    Dec  := ('0' & CntReg) - 1 ;
    if (Dec(Dec'Left) = '1') then
      CntReg  <= BaseReg ;
    else
      CntReg  <= Dec(CntReg'Range);
    end if ;
    IntReg    <= Dec(Dec'Left) ;
  end if ;
end process ;
Reply by Andy ●August 17, 20092009-08-17
That's about the cleanest example using vectors I've seen.

I'm not sure it wouldn't be subject to the same final optimizations
from Synplify (et al?), since those optimizations were related more to
the entire carry chain than to just the end of it. Although outputting
the carry bit in the IntReg register would likely give it a strong
nudge towards preserving the carry bit intact (if not the entire
chain). I've not checked any results from integer-coded
implementations that also registered (count - 1 < 0) as a boolean
output.

Be careful if CntReg'Range is not "n downto 0".

Andy
Reply by rickman ●August 17, 20092009-08-17
On Aug 17, 12:15 pm, JimLewis <J...@SynthWorks.com> wrote:

> Hi Rick,
> Integers and such are great for sim run time, however, if you are not
> getting the hardware you want, here is an array based algorithm that
> only uses one carry cell to implement the zero detect.  It has a few
> extras that you may want to remove.  BaseReg is the loadable base
> register.  CntReg keeps the current count value.  IntReg is a
> registered version of the zero detect.
>
> Best,
> Jim
> SynthWorks VHDL training
>
> TimerProc : process (Clk, nReset)
>   variable Dec : unsigned(CntReg'Length downto 0) ;
> begin
>   if (nReset = '0') then
>     BaseReg <= (others => '0') ;
>     CntReg  <= (others => '0') ;
>     IntReg  <= '0' ;
>   elsif rising_edge(Clk) then
>     if (TimerSel = '1' and Read = '0') then
>       BaseReg <= unsigned(DataIn) ;
>     end if ;
>     Dec  := ('0' & CntReg) - 1 ;
>     if (Dec(Dec'Left) = '1') then
>       CntReg  <= BaseReg ;
>     else
>       CntReg  <= Dec(CntReg'Range);
>     end if ;
>     IntReg    <= Dec(Dec'Left) ;
>   end if ;
> end process ;


I don't have any problem getting the basic counter to use the carry
chain, but I can not get the carry out for other purposes.  The result
seems to depend on size and how the tool is invoked.  If I use the
Lattice tool, an 8 bit counter uses 3 LUTs to detect the terminal
count.  At 16 bits it duplicates the adder chain and pulls off the
carry out.  Using Synplify directly the technology view shows two
adders while the RTL view shows one adder with 24 bits.  The carry
comes out of the top and the lower N bits are used for the counter.
Go figure...

Rick
Reply by JimLewis ●August 21, 20092009-08-21
Hi Rick,
This is what I like about vectors.  You can generally force an
implementation with the code and reduce the quirks that a given
synthesis tool subjects you to.

Cheers,
Jim
Reply by Andy ●August 21, 20092009-08-21
On Aug 20, 11:02=A0pm, JimLewis <J...@SynthWorks.com> wrote:

> This is what I like about vectors. =A0You can generally force an
> implementation with the code and reduce the quirks that a given
> synthesis tool subjects you to.


Only if you are willing to constrain the code to keep certain terms
from being optimized away. The same synthesis tool, on the same
target, generally applies the same sets of "back end" (technology
mapping) optimizations regardless of what data type was used in the
RTL, since by the time those optimizations are applied, everything is
a vector of bits. The operations, defined by the data types, give
certain hints & constraints based on behavior, but the back end is
still free to accept those hints or offer something it thinks is
better (so long as it implements the prescribed behavior, at the
boundaries of interest). And in my observations, when Synplify has
abandoned the explicit, traditional carry implied by the RTL, the
circuit it came up with was faster and/or smaller. I learned to quit
wasting my time second guessing the synthesis tool's chosen
implementation, as long as it met performance and resource
constraints. I still use the subtract and compare condition only
because it is easy enough to write and understand, and consistently
gives equal or better results than a simple pre-subtraction compare to
zero.

I actually prefer some of the attributes of integer arithmetic that
have flowed into the IEEE fixed point vector types (e.g. length
expansion to cover the potential range of the results). Unfortunately,
the subtraction of unsigned operands still returns an unsigned result.
Arithmetically, that is not always the case. Like integer operations,
you specify the arithmetic operation with the fixed point expression,
and control the data path width by assigning it to objects of a
specific type/subtype with whatever "resizing" operation is required.
You could probably code this whole exercise in fixed point more easily
than in unsigned.

Andy