Saturating counters

[SiliconWizard]

Small puzzle.

How would you implement a saturating counter (let's say here for an unsigned counter - so saturating downwards to 0, and upwards to max value it can hold, so all 1's) without adding a logic level (for testing for saturation)?

In other words, do you know of any means of doing this with a structure that has no added delay compared to a simple adder?

Any ideas welcome.

[mrflibble]

Mmmh, interesting. As a first stab at it ... For example for an unsigned saturating 4-bit adder on xilinx, something like this:
1 - add two 4-bit numbers using a CARRY4
2 - the 4 result bits go straight to the relevant 4 FFs in same CLB
3 - take the MSB CARRY OUT signal on the CARRY4, and use it as a synchronous reset for the above 4 FFs.
4 - those 4 FFs should all reset to 1 (HIGH)

Note that this is an adder, so more general solution. For upcount, use a=+1 and b=prev_value., where prev_value is the previous value on the FFs.

[BrianHG]

Maybe something like (Verilog):

Code: [Select]

module limit_cnt (
input  wire       clk,
input  wire       increment,
input  wire       decrement,

output reg  [3:0] counter
  ) ;

always @ (posedge clk) begin
        if  ((counter != 4'hF ) && (increment )) counter <= counter +1;
else if  ((counter != 4'h0 ) && (decrement )) counter <= counter -1;
end

endmodule

This should work way in the multi hundreds of megahertz to GHz, all the way up to 32 bit counters as the ' != ' is a simple xor equality compare function.  No addition math there.  And the +/-1 would be optimized by the compiler as a simple 1 bit add/subtract.  Adding a reset, or set/load inputs will also not decrease the performance.

[OwO]

The fastest way involves a dumb counter with enable (note that doIncrement should be driven by a FF):

cnt <= cnt+1 when doIncrement='1' and rising_edge(clk);

Then predicting ahead of time when the counter will reach saturation value:

cntWillSaturate <= '1' when cnt = unsigned(cnt'range=>'1') - 2 else '0';
cntWillSaturate1 <= cntWillSaturate when rising_edge(clk);
doIncrement <= not cntWillSaturate1 when rising_edge(clk);

You will need to make changes to support control inputs but the basic idea is the same. Since you can't predict control inputs ahead of time the next best you can do is speculate-and-fix: let the counter overflow for a few clock cycles until it notices it should saturate, but follow this up with pipelined logic to fix the output value.

[OwO]

But actually in an FPGA testing for saturation doesn't actually add a logic level if it ends up using the CE input of the flipflops - the MUX before a flipflop is always present in hardware, and if the CE path is no longer than the D path (e.g. the comparison is as fast as the addition) it doesn't affect timing. The synthesizer should be able to infer the use of CE as long as you didn't do something stupid (like a global clock enable) or hide the MUXing in long spaghetti behavioral code.

Now this code:

if  (counter != 8h'FF ) && (increment ) counter <= counter +1;
else if  (counter != 8h'00 ) && (decrement ) counter <= counter -1;

Is likely to not synthesize optimally because in my experience the tools won't see that it can be simplified to a adder/subtractor and a CE flipflop. It'll see a 3-input MUX and conclude it can't fit the CE flipflop template and end up using a LUT MUX.

I would separate the add/subtract part from the CE part:

addSubSel <= increment;
counterNext <= counter+1 when addSubSel='1' else counter-1;

counterCE <= '1' when (increment='1' and counter != X"FF") or (decrement='1' and counter != X"00") else '0';
counter <= counterNext when counterCE='1' and rising_edge(clk);

[OwO]

I tried synthesizing the above behavioral code and compared it to my dataflow version.
The results are just as I guessed - the behavioral version synthesizes into crap logic that only runs at 228MHz (compared to 315MHz for the dataflow version).



(leftmost red column is WNS, followed by TNS. The clock was constrained to 2.4ns)

Looking at the failing timing path of the behavioral version:

There is a bunch of LUTs before the adder (an adder by itself should show only one LUT before the CARRY chain).

I looked closely at the logic to figure out why the behavioral version has such a complex data path, and it turns out the answer lies in the corner case, which is increment='1' and decrement='1' at the same time. For optimization purposes we don't care about what happens to the counter under this condition.

It turns out the behavioral code does something baroque - if increment and decrement are both high, it will prefer to increment, but if the counter is saturated high it will fall through to the else branch, which decrements. In other words, the type of arithmetic taken (add or subtract) depends on the value of the counter!

What does this mean? It means better tools and smarter synthesis will not solve the problem; the logic itself has to be changed.
This enforces my belief that behavioral code should be avoided at all costs; writing a dataflow description forces you to think what the datapath and clock enable path really looks like. The behavioral version hides that from you, and you end up with suboptimal logic in very non-obvious ways.

Behavioral code:

Code: [Select]

library IEEE;
use IEEE.STD_LOGIC_1164.ALL;
use IEEE.NUMERIC_STD.ALL;

entity counterTestBehav is
    port(clk: in std_logic;
    increment, decrement: in std_logic;
    dout: out unsigned(31 downto 0));
end counterTestBehav;

architecture a of counterTestBehav is
signal count, count1: unsigned(31 downto 0);
begin
process(clk) is
begin
if rising_edge(clk) then
if increment='1' and count /= X"FFFFFFFF" then
count <= count+1;
elsif decrement='1' and count /= X"00000000" then
count <= count-1;
end if;
end if;
end process;

count1 <= count when rising_edge(clk);
dout <= count1 when rising_edge(clk);
end a;

Dataflow code:

Code: [Select]

library IEEE;
use IEEE.STD_LOGIC_1164.ALL;
use IEEE.NUMERIC_STD.ALL;

entity counterTestDataflow is
    port(clk: in std_logic;
    increment, decrement: in std_logic;
    dout: out unsigned(31 downto 0));
end counterTestDataflow;

architecture a of counterTestDataflow is
signal countCE: std_logic;
signal count, countNext, count1: unsigned(31 downto 0);
begin
countNext <= count+1 when increment='1' else count-1;

countCE <= '1' when (increment='1' and count /= X"FFFFFFFF")
or (decrement='1' and count /= X"00000000")
else '0';
count <= countNext when countCE='1' and rising_edge(clk);

count1 <= count when rising_edge(clk);
dout <= count1 when rising_edge(clk);
end a;


[BrianHG]

I tried synthesizing the above behavioral code and compared it to my dataflow version.
The results are just as I guessed - the behavioral version synthesizes into crap logic that only runs at 228MHz (compared to 315MHz for the dataflow version).

Design methodology aside, it is a sad state of affairs that a 4 bit limit counter of either design here con only reach 228Mhz.  Why does Quartus give a FMAX of 333MHz on their oldest obsolete cheapest FPGA with my behavioral version using only 4 registers, 9 combinational elements total?

[SiliconWizard]

Thanks OwO for the detailed analysis - that's interesting. My experience with just plain behavioral code for this was consistent with what you got, hence my question to find better ways of implementing this.

One thing to note (that I already pointed out a while ago in another thread) is how "dumb" synthesis tools can be sometimes when dealing with "if" constructs. This can be pretty surprising even to seasoned engineers, as those tools are otherwise pretty good at optimizing logic for a whole range of structures. A common pitfall with "if" is that it will often be translated as a priority encoder of some sort, even when it's completely obvious from behavior only that there is no priority needed.

@OwO: isn't your proposed counter a pipelined one? Not that it's necessarily an issue, it can be adequate for a number of applications, but in some cases the added latency may not be what we want.

[OwO]

The two versions I compared above behave identically except in the case of increment='1' and decrement='1'. I added two pipeline registers at the end so that the tools are free to place logic whereever rather than close to the IOs; there is no pipeline delay otherwise.

But yes both of the above versions aren't pipelined and so aren't the fastest I can do; I'll probably design a pipelined and speculative version later and see if I can get above 400MHz (slowest Artix-100T).

The counters I compared are 32 bits; I'm sure you can do much faster with less bits.

[SiliconWizard]

The two versions I compared above behave identically except in the case of increment='1' and decrement='1'. I added two pipeline registers at the end so that the tools are free to place logic whereever rather than close to the IOs; there is no pipeline delay otherwise.

OK, I see the rationale.

But yes both of the above versions aren't pipelined and so aren't the fastest I can do; I'll probably design a pipelined and speculative version later and see if I can get above 400MHz (slowest Artix-100T).

Yes, I thought of a pipelined approach in which for instance, the first stage would just count (and let the counter roll over), and the second stage would select the right output depending on previous state, something like this.

But I was ultimately really curious about finding out if there was a modified counter structure that would saturate by itself while being structurally as simple as a basic counter that rolls over.

[BrianHG]

Yes there is, but unfortunately, it would run slower on FPGA.  In a full blown ASIC cell, it would not.

You may be thinking something like:

up_counter <= up_counter + ~(up_counter == 4'hF);

Gate wise, this literally does what you are asking for...  Make an adder whose addition input is 1 when the output bits are not equal to 1111.

This unfortunately makes adder whose 1 bit 0 or 1 input directly dependent on the state of the adder's outputs.
Advanced preparation of such a 'up_counter' total and a similar 'down_counter' total, then select which result you want depending on up/down inputs would be the pipeline method.

[Bassman59]

Small puzzle.

How would you implement a saturating counter (let's say here for an unsigned counter - so saturating downwards to 0, and upwards to max value it can hold, so all 1's) without adding a logic level (for testing for saturation)?

In other words, do you know of any means of doing this with a structure that has no added delay compared to a simple adder?

I would write it simply:

Code: [Select]

    signal reset : std_logic;
    signal operation : std_logic_vector(1 downto 0);
    alias inc : std_logic is operation(0);
    alias dec : std_logic is operation(1);
    signal counter : natural range 0 to CNTMAX; -- define CNTMAX as whatever

SaturatingCounter : process (clk) is
begin
    if rising_edge(clk) then
        if reset = '1' then
            counter <= 0;
        else
            OpDecode : case operation is
                when "01" => -- increment
                     if counter < CNTMAX then
                         counter <= counter + 1;
                     end if;
                 when "10" => -- decrement
                     if count > 0 then
                        counter <= counter - 1;
                     end if;
                 when others =>
                      -- do nothing if both inc and dec are asserted, or if nothing.
                     null;
            end case OpDecode;
        end if;
    end if;
end process SaturatingCounter;
If this meets my timing constraints, I'm done, as further optimization isn't necessary. If it doesn't, I look to see why.

[aheid]

Dumb question, why use separate inc/dec flags. Why not single? Inc=1, dec=0.

[BrianHG]

Dumb question, why use separate inc/dec flags. Why not single? Inc=1, dec=0.

You may want the counter to remain stationary.
Like a volume control know with a min and max, you may want it to turn up, or down, or stay still.

[ralphrmartin]

Then the correct way to encode your inputs is, in my opinion,
one variable for which 0 means  Increment, 1 means Decrement
one variable for which 0 means do nothing, 1 means do something (increment or decrement as specified)

That way you avoid the issue of what to do if Increment = 1 and Decrement = 1 at the same time.

I think the problem here is not behavioural logic per se, but proper specification of what the behaviour should be.

[aheid]

Dumb question, why use separate inc/dec flags. Why not single? Inc=1, dec=0.

You may want the counter to remain stationary.
Like a volume control know with a min and max, you may want it to turn up, or down, or stay still.

Sure, but as a programmer my natural reaction would be to have a single inc/dec flag and then a counter/clock enable flag. So why two seemingly clearly ambiguous flags instead? Again, I'm a FPGA n00b so just trying to understand.

[Someone]

Then the correct way to encode your inputs is, in my opinion,
one variable for which 0 means  Increment, 1 means Decrement
one variable for which 0 means do nothing, 1 means do something (increment or decrement as specified)

That way you avoid the issue of what to do if Increment = 1 and Decrement = 1 at the same time.

I think the problem here is not behavioural logic per se, but proper specification of what the behaviour should be.

It is not always the "correct" encoding, a FIFO controller is a common example of a counter that has separate increment and decrement inputs. No change for inc == dec is entirely correct there.

[BrianHG]

Dumb question, why use separate inc/dec flags. Why not single? Inc=1, dec=0.

You may want the counter to remain stationary.
Like a volume control know with a min and max, you may want it to turn up, or down, or stay still.

Sure, but as a programmer my natural reaction would be to have a single inc/dec flag and then a counter/clock enable flag. So why two seemingly clearly ambiguous flags instead? Again, I'm a FPGA n00b so just trying to understand.

What if you want an up and down button connected to 2 inputs in the FPGA.  Press 1 to increment, or the other to decrement.

Arguing about the 2 controls for this counter is meaningless.  It can be anything your project requires, including 3 inputs or even more.  The whole issue here was about methods to implement the 'Saturation' itself.

[aheid]

Arguing about the 2 controls for this counter is meaningless.  It can be anything your project requires, including 3 inputs or even more.  The whole issue here was about methods to implement the 'Saturation' itself.

It just seemed the two separate flags was prone to poor synthesis, so I wanted to see if there was a reason to chose that way that I was missing.

[hamster_nz]

For smaller, performance-critical saturation counters this pattern might be of use, as it doesn't use the carry chain and only has a single level of logic:

Code: [Select]

library IEEE;
use IEEE.STD_LOGIC_1164.ALL;
use IEEE.NUMERIC_STD.ALL;

entity sat_counter is
    Port ( clk : in STD_LOGIC;
           inc : in STD_LOGIC;
           dec : in STD_LOGIC;
           count : out STD_LOGIC_VECTOR (3 downto 0));
end sat_counter;

architecture Behavioral of sat_counter is
  type a_mem is array(0 to 63) of std_logic_vector(3 downto 0);
  signal mem : a_mem := (x"0",x"1",x"2",x"3",x"4",x"5",x"6",x"7",x"8",x"9",x"A",x"B",x"C",x"D",x"E",x"F",  -- Nnee
                         x"1",x"2",x"3",x"4",x"5",x"6",x"7",x"8",x"9",x"A",x"B",x"C",x"D",x"E",x"F",x"F",  -- Inc
                         x"0",x"0",x"1",x"2",x"3",x"4",x"5",x"6",x"7",x"8",x"9",x"A",x"B",x"C",x"D",x"E",  -- Dec
                         x"0",x"1",x"2",x"3",x"4",x"5",x"6",x"7",x"8",x"9",x"A",x"B",x"C",x"D",x"E",x"F"); -- inc & dec
  signal index : std_logic_vector(5 downto 0);
  signal state : std_logic_vector(3 downto 0) := (others => '0');

begin

   count <= std_logic_vector(state);
   index <= dec & inc & state;

process(clk)
   begin
      if rising_edge(clk) then
         state <= mem(to_integer(unsigned(index)));
      end if;
   end process;

end Behavioral;


For example, this four bit counter needs four 6-input LUTs and 4FFs.

BRAM blocks can also be used for counters of moderate widths (8 or so bits).

You can sometimes add add an "enable" and reset input at no extra cost (see second schematic):

Code: [Select]

library IEEE;
use IEEE.STD_LOGIC_1164.ALL;
use IEEE.NUMERIC_STD.ALL;

entity sat_counter is
    Port ( clk : in STD_LOGIC;
           inc : in STD_LOGIC;
           dec : in STD_LOGIC;
           enable : in STD_LOGIC;
           reset : in STD_LOGIC;
           count : out STD_LOGIC_VECTOR (3 downto 0));
end sat_counter;

architecture Behavioral of sat_counter is
  type a_mem is array(0 to 63) of std_logic_vector(3 downto 0);
  signal mem : a_mem := (x"0",x"1",x"2",x"3",x"4",x"5",x"6",x"7",x"8",x"9",x"A",x"B",x"C",x"D",x"E",x"F",  -- Nnee
                         x"1",x"2",x"3",x"4",x"5",x"6",x"7",x"8",x"9",x"A",x"B",x"C",x"D",x"E",x"F",x"F",  -- Inc
                         x"0",x"0",x"1",x"2",x"3",x"4",x"5",x"6",x"7",x"8",x"9",x"A",x"B",x"C",x"D",x"E",  -- Dec
                         x"0",x"1",x"2",x"3",x"4",x"5",x"6",x"7",x"8",x"9",x"A",x"B",x"C",x"D",x"E",x"F"); -- inc & dec
  signal index : std_logic_vector(5 downto 0);
  signal state : std_logic_vector(3 downto 0) := (others => '0');

begin

   count <= std_logic_vector(state);
   index <= dec & inc & state;

process(clk)
   begin
      if rising_edge(clk) then
         if reset = '1' then
            state <= (others => '0');
         elsif enable = '1' then
            state <= mem(to_integer(unsigned(index)));
         end if;
      end if;
   end process;

end Behavioral;

You can push the ROM+state register into a Block RAM, making longer fast counters possible, and with Dual-port RAMs you can implement two counters using the same memory block.

[hamster_nz]

Oh, and if you push the ROM into Block RAM with at least this on Xilinx parts:

Code: [Select]

  attribute rom_style : string; 
  attribute rom_style of mem : signal is "block";

here's what the implemented design looks like.

If you have an 'enable' and a 'reset' then a LUT2 is needed to control the BRAM's clock enable, possibly slowing timing. You can sometimes merge the reset into the block RAM.

[SiliconWizard]

Using memory blocks to implement this is a creative approach. Of course, it's a waste of area, but on FPGAs, that doesn't really matter as long as the counter is small enough.

I'd be curious to see a comparison of Fmax between your proposed memory-based approach, and a purely behavioral/naive approach, for say a 4-bit counter.

[NorthGuy]

32-bit counter will use 8 CARRY4 elements on Xilinx, which is very slow already. I'm not sure it can run at 400 MHz.

Calculating the "will saturate up" and "will saturate down" conditions parallel to the carry chain is not difficult. Then these can be used by one extra logic level in front of the carry chain, which would get "will saturated up", "will saturate down", "increment" and "decrement" signals and figure out the inputs to the carry chain. This is probably better than adding muxes to the results. Such method will be a touch slower than the counter itself.

If you want faster, you need to pipeline the counter first. Since the free running counter is fully predictable, you can pipeline it as much as you can. This is not hard and maximum clock speed most likely can be achieved.

It's much harder with the saturating counter where the stream of "increment" or "decrement" pulses is unpredictable. But you still can maintain current values of "timer -2", "timer-1","timer+1","timer+2" and then get the result by muxing the correct values depending on the incoming "increment" and "decrement" values. But that's a lot of writing and a lot of logic. But anyway, you may be able to get to one logic level, so high speed certainly can be achieved. But there's no way the tools may do this for you automatically.

[BrianHG]

I'd be curious to see a comparison of Fmax between your proposed memory-based approach, and a purely behavioral/naive approach, for say a 4-bit counter.

We all provided you with source code examples.  All the top FPGA vendors offer free versions of their compilers which can compile all of our provided codes.  It is trivial to read the final FMAX product after a test compile.

In the case of these 4 bit counters, only 1 issue you might get is 2 different FMAX as in Quartus,  you will see 1 higher speed, the maximum error free operational clock frequency of the counter, and a 'restricted FMAX' which may be a slower limited frequency due to the counter being fed by or it feeding IO pins where this lower FMAX may be the speed limit of the IO pins with their set IO voltage standard, like LVTTL for example.  Only using the counter buried internally will allow the higher listed FMAX and there are no coding tricks which would allow you to go above that restricted FMAX if the counter being used is directly reliant on the IOs with their selected IO standard.  In other words, if you are trying to exceed this 'restricted' FMAX with simple coding tricks, I sorry to say that you are wasting time and you should upgrading your FPGA speed rating unless you don't care about the tight synchronous clocked inputs and allow for a sliping-async style inputs driving the direction of your counter.  Though, the clock still needs to be clean.

[hamster_nz]

Artix-7 speed grade 1.

4-bit saturating counter implemented using Block RAM = 4.001ns = ~250 MHz (constrained to 4ns clock, with -0.001 WNS)
4-bit saturating counter implemented using LUT6+FFs =  2.2ns = 454 MHz (constrained to 2.2ns with 0.687ns  slack).

When I constrained the later case to 2.0ns, it fails timing on "Total Pulse Width Negative Slack" .

I'm somewhat surprised by how slow the Block RAM version was. I was expecting it to go to the speed of the Block RAM - 450MHz. That external LUT2 (to combine the reset and enable signals) slows things down a bit