# What is the most efficient method of storing statistics in an FPGA?

I'm trying to work out the most efficient way of storing statistics in an FPGA. Here is a point form summary of the situation:

• Many 32bit and 64bit values are calculated / stored.
• Any number of the values could update in any clock cycle.
• A number of the values will be updating in most clock cycles (byte counts, time counts).
• The frequency of change is something on the order of 200MHz, so running a separate clock faster to do multiple calculations per system clock is not really possible.
• The calculation of the values is generally pretty simple, it's the storage and updating of them that I am worried about.
• I am looking for efficiency of resource usage, as implementing all counters in FF's will not be possible with the available resources.
• If I put the stats registers in logic RAM (LUT's), then I can't access more than one at a time, so updates get really complicated.

Is there a good way of storing statistics in LUT's where it is possible to update more than one at a time, given that they may update in consecutive cycles?

• There's a lot of detail missing from the question that we'll need to know to give a good answer: When you say efficient, what do you mean? Minimum power, minimum fpga resources, minimum calculation latency? What statistics do you need to calculate (mean? standard deviation? more complex statistics?) How is the data presented -- one new value at a time, all at once at power-up, several values at a time? How often do you need to update the statistics -- every time you get new data, every N clock cycles, every time a user pushes a button? Commented Jan 31, 2012 at 4:49
• As you pointed out, there are tradeoffs when storing values in LUT RAMs, Block RAMs, or Flip-Flops. Also, the word "statistics" is a very generic term with little meaning in this context. For us to be able to give you a useful answer we are going to need MUCH more information. We need to know what you want to store, what calculations need to be done, how many "updates" are done and in what time period, how data flows into and out of this logic, etc. Without this detailed information the question you ask is like asking a cook, "How should I bake?"
– user3624
Commented Jan 31, 2012 at 4:51
• One immediate impression: If your application doesn't need the calculated values immediately available, as they would be if you had a separate register for each one, then a processor of some kind (microcontroller or DSP or something) will probably be a cleaner solution than an FPGA. Commented Jan 31, 2012 at 4:53
• Sorry for not being as complete as I should have been with the question. I guess the most important part of the problem is storing the stats. The part about how to store values in LUTs in a system where values can be updated every clock cycle is the real crux of the problem. Commented Feb 1, 2012 at 5:58

The following is the killer requirement:

There are a large number of statistics that the design will be calculating, and any number of them could be updating every clock cycle.

That alone means that you can't lump accumulators together into block RAM's or do any other special tricks to reduce logic requirements. If you want to make things more efficient then you have to figure out how to change this requirement.

Here are some ideas on how this could happen:

1. Run your "master clock" at a much higher frequency than your "counting clock". For example, if your "counting clock" was running at 10 MHz then run your master clock at 160 MHz-- or 16 times faster. In this way you can process 16 accumulators in a "time slice" fashion. You'd use some LUT based RAM to make a 16 word dual-port ram. On the first clock you would process "channel 0", the second clock you'd process "channel 1", etc. Since your data can only come in at 1/16th of your master clock rate you can process all data in the required time. This might not work if your master clock rate is too high for your chosen FPGA. I would estimate that the logic size with this approach is about 1/4th, when compared to just doing a lot of counters. If you need more than 16 accumulators then you need several of these modules.

2. If your "counting clock" is too high for approach #1, but the total number of "counts" in a certain time interval is small (even though they could come in all bunched up in time) then you could do something a little more strange. Start with a FIFO that is 32 or even 64 bits wide. Each data bit represents a signal for that channel's count to increment. If, during any one clock cycle, a data bit is set then that "word" is written to the FIFO. On the output side of the FIFO create some logic that will take a word and use the set bits to increment counters in RAM. You have to be a little smart here so that if, for example, 4 bits are set then it will take 4 clock cycles to increment those 4 counters. The counters (32 or 64 of them) are stored in RAM (LUT or Block, whichever makes sense). The depth of the FIFO will dictate just how bunched up the "count events" can be. I estimate that this logic will be approximately 1/4th the size, but there is a lot of variation here depending on the width and depth of the FIFO and what kind of RAM is used. On average you will be limited to incrementing one counter every clock cycle, but the FIFO will soak up any short-term peaks in your count rate.

3. If you need to count things really fast, but for a very short amount of time then you could simply use a variation on #2. Make the FIFO really large and don't worry too much about emptying the FIFO quickly. This assumes that all of your count events will fit in the FIFO. It's quick and simple, but you are limited to about a few thousand clock cycles for your measurement period.

One difficulty with approach #1 and #2 is that you need crazy logic to clear the counters. I recommend that you simply don't clear them. Instead, read the count values at the start and again at the end and then calculate the difference. I'm assuming that you have a CPU that you can do this in. This trick will save you lots of logic and some headache.

• Thanks very much for that answer, it was very useful. In my problem domain the clock freq is too fast for option 1, and there are too many counters that can possibly be counting most of the time to really scale out option 2. But I think I can break out option 2 to use multiple separate RAM's, and have all the counts that can be incrementing most of the time in different RAM's. This should allow me to use a number of parallel option 2's to solve the problem. Commented Feb 1, 2012 at 22:50

If you have 32 simple 16-bit counters, I would suggest that you use eleven 32-bit shift registers to handle the upper 11 bits (think of it as 32 11-bit latches that feed each other), and 32 6-bit counters, to handle the bottom six. Every cycle, you will hit all the shift registers to bring "to the front" the upper portion of the next count register. If the MSB of the corresponding 6-bit counter matches the LSB from the shift registers, feed the old value back into the shifters; otherwise increment the value and feed it back.

Such an approach would be straightforwardly adaptable to different numbers of counters and lengths. If desired, it could be implemented hierarchically (e.g. instead of using 32 6-bit counters, one could use eight groups of four dedicated 3-bit counters, with each of those groups having a four 3-bit shift registers and a four-bit incrementer). To handle extreme upper bits, one could use a single long shift register to store all of the upper bits from every counter, since there would be enough time to shift all the bits through the register every time any of them would increment.

Here's an implementation of a high-order-bits counter which demonstrates how one can use a minimal amount of circuitry to behave as many counters, provided the things to be counted don't change too quickly. Using something like Actel's "Versatiles", one can implement 'k' counters totalling 'N' bits, using N+k+1 latches and k+1 other tiles, provided that any input levels to be counted will be stable for N+k cycles (so if N+k=64, then one might need seven-bit dedicated counters). Note that a conventional synchronous-counter approach using Versatiles would need two tiles per counter bit, so one may end up with a substantial win using this approach. Unless the things to be counted are inherently slow, it's probably best to combine counters in pairs.

In the supplied schematic, the guts of the counter are at the right. If one wants to implement a single counter in a shift register N+1 bits long, then every N input clocks one should drive high the 'frameStart' signal and simultaneously supply the signal to be counted on the 'prevMSB' input. If one wants to store multiple counters, one should hit 'frameStart' when the LSB of each counter comes around in the shift register, and output the signal to be counted from the appropriate counter at that time. In the supplied schematic, N is eight, and depending upon the "split mode" input the counter can behave as either two four-bit counters or one eight-bit counter. The upper-left part of the schematic is a clock generator. Clicking "start" when "AUTO-STOP" is true will generate eight clock pulses. Clicking "start" when "AUTO-STOP" is false will generate clock pulses until "AUTO-START" is set true, and will then continue to generate pulses up to the next multiple of eight.

Note that the counter output shows the LSB at the top output-to-input wire, and the bottom bit of each counter is the last observed state of the input. The only time the very top shift register will output true simultaneous with a "frameStart" signal is when a counter has just generated a carry out (which it ignored).

• Not sure this approach will work for what I am doing. If I understand your suggestion correctly, it would not be able to handle the case where in two consecutive clock cycles multiple values need to be incremented/modified. Am I missing something here? Commented Feb 1, 2012 at 22:43
• The idea is that every counter has dedicated hardware for the lower-order bits. If one has a six-bit counter for each input, the upper bit will change at most once every 32 cycles. Depending upon the counters and their lengths, though, I may have a better approach. Commented Feb 1, 2012 at 22:53
• Ah yes, I get it now. I need to work out if this option or David's option 2 is more appropriate for my situation. Commented Feb 2, 2012 at 0:19
• @marcush: See example above added to answer. Maybe I'm not understanding David's approach properly, but I really don't see how it saves any logic compared with using a dedicated counter for the low-order bits. Commented Feb 2, 2012 at 0:20