4
\$\begingroup\$

I have a module that takes in a sample, puts it in a large buffer, and sums the buffer. When it synthesizes, Quartus says it requires too many combinational nodes. I tried many things to see what affects it, but it seems that nothing works.

I have tried:

  • a single sum in a for loop
  • pipelining the sum into 4 clock cycles
  • reducing the number of elements being summed does seem to allow the adder to work

Below is the pipelined sum (pipelined into 4 stages), requires 43862 combinational nodes, I have 22320 available.

always @ (posedge clk) begin
        
        // clock for input sample
        if (inDataCounter < 500) begin
            inDataCounter <= inDataCounter+1;
        end else if (inDataCounter == 500) begin
            inDataCounter <= 0;
            inDataClk<= ~inDataClk;
        end
        
        //First pipeline
        for (mm=0; mm<256; mm=mm+1) begin//should be 256
            sum1[mm] = 0;
        end
        for (kk=0; kk<256; kk=kk+1) begin //should be 256
            for (ll=0; ll<8; ll=ll+1) begin
                sum1[kk] = sum1[kk] + signalHist[ll + kk*8];
            end
        end
        
        //second pipeline
        for (nn=0; nn<32; nn=nn+1) begin
            sum2[nn] = 0;
        end
        for (oo=0; oo<32; oo=oo+1) begin
            for (pp=0; pp<8; pp=pp+1) begin
                sum2[oo] = sum2[oo] + sum1[pp + oo*8];
            end
        end
        
        //third pipeline
        for (qq=0; qq<4; qq=qq+1) begin
            sum3[qq] = 0;
        end
        for (rr=0; rr<4; rr=rr+1) begin
            for (ss=0; ss<8; ss=ss+1) begin
                sum3[rr] = sum3[rr] + sum2[ss + rr*8];
            end
        end
        
        //fourth pipeline (final with 8 per)
        totalSum = 0;
        for (tt=0; tt<4; tt=tt+1) begin
            totalSum = totalSum + sum3[tt];
        end
        
        //output data
        OUTDATA[15:0] <= totalSum[35:20];
    end
    
    
    //read the new sample into the buffer signalHist
    always @ (posedge inDataClk) begin
        for (jj=1; jj<2048; jj=jj+1) begin
            signalHist[jj] <= signalHist[jj-1];
        end
        signalHist[0] <= INDATA;
    end

Am I really hitting the limit of the FPGA here, or is there another method I could use to get such a summation to run on fewer logic elements?

\$\endgroup\$
12
  • \$\begingroup\$ Why do you need a buffer? Get the samples and sum them on the fly. \$\endgroup\$
    – Eugene Sh.
    May 18 at 15:32
  • 5
    \$\begingroup\$ Remember that for loops in Verilog generate logic, they don't execute sequential steps at run time. So your second for block generates 2048 adders. Is that what you want if you're trying to minimize combinatorial resources? \$\endgroup\$
    – The Photon
    May 18 at 16:18
  • 2
    \$\begingroup\$ Also, pipelines generally improve throughput by increasing "area" (logic resources) and latency. If your problem is the design takes too much area, then pipelining is probably not the way to solve it. \$\endgroup\$
    – The Photon
    May 18 at 16:19
  • 3
    \$\begingroup\$ The main thing (as TonyM and ThePhoton already wrote) is to understand that there is no 'for'/'while'/'until' loop in HDL. The 'for' statement in Verilog/VHDL does something completely different. \$\endgroup\$
    – asdfex
    May 18 at 17:19
  • 1
    \$\begingroup\$ The document entitled "Designing Filters for High Performance" from Intel has an interesting figure (number 3). If you write your HDL to look as the DSP block in FPGA, you will reach the best performance vs resources tradeoff \$\endgroup\$
    – gotchi85
    May 19 at 14:19

3 Answers 3

14
\$\begingroup\$

I'm afraid you're making a classic Verilog/VHDL mistake: trying to write a computer program in an HDL, instead of using it to design a digital logic circuit.

An FPGA has no CPU to run Verilog 'lines' and compiled instructions on. An HDL is closer to a glorified schematic netlist than anything else.

Instead, you need to design a logic circuit that will carry out your function. Then enter Verilog representing that logic circuit and simulate it to check it works. With experience, these two steps can become more of a single step.

The final circuit for what is your integration circuit may benefit from using internal block RAM to keep the samples history, if you have enough clock cycles to then read and add the RAM contents.

Following that, a more elaborate circuit would calculate an initial RAM contents total, then maintain it by subtracting the sample to be discarded and adding the incoming sample. That uses a couple of clocks, usually much less than to add the RAM contents every time a sample is added.

\$\endgroup\$
7
  • \$\begingroup\$ I guess this may fundamentally be my problem. My ultimate goal is to implement a large FIR filter, essentially a multiply accumulate but with many points (>=2048). It is an algorithm typically run on a DSP that I want to run in realtime, so I am trying to implement it on the fpga. Does this sort of algorithm just not fit well to an FPGA? Or are there better ways to implement them than I am? \$\endgroup\$ May 18 at 16:55
  • 3
    \$\begingroup\$ @user2704336, taking a step back, are you familiar with the actual logic structure of an FPGA and its programmable logic gates, and the gulf between that and a CPU found in a DSP or microcontroller/microprocessor? Please do elaborate on your understanding of FPGAs because we have to know where you are to suggest how to get somewhere further. \$\endgroup\$
    – TonyM
    May 18 at 17:09
  • \$\begingroup\$ I am very familiar with DSPs, and the fundamental differences between an FPGA and other processors. But my understanding of what is inside an FPGA (ie. what are inside a CLB) and how they connect to do something useful is fairly weak. \$\endgroup\$ May 18 at 17:19
  • 3
    \$\begingroup\$ @user2704336 I'm glad Tony managed to state this so well. I've been following your posts and it is clear how the concepts of software programming are affecting the way you interpret Hardware Description Languages. Don't think sequentially as you do in software. Your are describing to a specialized software how wires and components are connected (if I may put this so simply), and this is possible in many abstraction levels (from a logic gate to a multiplier, which is a big circuit). A for loop e a simple way to write less code, it is not sequential processing. \$\endgroup\$
    – devnull
    May 18 at 17:23
  • \$\begingroup\$ @user2704336, are you familiar with synchronous digital logic circuits made from AND/OR/XOR/NOT gates and D-type Flip-Flops (DFFs) ? Search for schematics of example digital logic circuits on the Internet and you'll see what you've got available to design with inside an FPGA. It's so far away from copying and pasting an algorithm into Verilog syntax. \$\endgroup\$
    – TonyM
    May 18 at 17:29
6
\$\begingroup\$

A running average can be implemented with just the buffer, one register, an adder and a subtractor. It doesn't need to take many resources.

enter image description here

Image credit - https://surf-vhdl.com/how-to-implement-moving-average-in-vhdl/

A running average is a variation of a FIR filter.

Implementing the Moving Average filter

A Generic Filter Implementation structure

\$\endgroup\$
5
  • \$\begingroup\$ This adder was actually a sub-component of my larger project, a large FIR filter, which required a huge amount of logic. I isolated the summation circuit to focus on that but ultimately I want the multiply+accumilates. Is it just impractical to assume this many multiply/accumilates can fit on an FPGA? Or are there higher end FPGAs that can fit them? \$\endgroup\$ May 18 at 17:05
  • 1
    \$\begingroup\$ @user2704336 - It depends how many multipliers you need. A full general FIR can take a lot of resources. Have you looked into the various ways of reducing resource usage. E.g using only zero and unity multipliers as in the running average or folding the FIR if the shape is symmetric (that can substitute an adder for half of the multiplies). Or do operations sequentially if the timing is appropriate. \$\endgroup\$ May 18 at 17:25
  • \$\begingroup\$ @user2704336 Extremely rough estimate, 1 LUT outputs 1 bit. So if you have 2500ish 16-bit adders that's a minimum of 40000 LUTs \$\endgroup\$
    – user253751
    May 19 at 9:02
  • 1
    \$\begingroup\$ There's a mistake in the second paragraph. A running average (moving average) is one where all FIR coefficients are equal (so can be chosen to be one). It is not correct that "All but the first and last (FIR) coefficients are set to zero". Your first paragraph is correct, the moving average can be realized by an IIR filter with only two non-zero coefficients, but this requires feedback and thus it has IIR structure. It's important to consider that the IIR structure will still yield a finite response if integer arithmetic is used, but in floating-point, errors can accumulate forever. \$\endgroup\$
    – Ben Voigt
    May 19 at 21:13
  • \$\begingroup\$ @BenVoigt - you're right, my error. I have added a diagram showing my intended block diagram. \$\endgroup\$ May 19 at 22:21
1
\$\begingroup\$

Your design is NOT pipelined. Because all of your "sum = ... " statements use "=" rather than "<=", they have to complete within the same cycle.

It is absolutely critical that you understand what "for" does within "always @" blocks. It does not iterate, like a loop with in a computer program. Instead, it forces the synthesis of lots of identical blocks.

You have to understand your design in both the "space" and "time" dimensions. Unfortunately, Verilog doesn't help with the latter at all.

\$\endgroup\$
2
  • \$\begingroup\$ Yes you are right, my design is not pipelined, I see that now. But I do in fact want all that hardware synthesized to run in parallel (ie. the @always / for loop). I want it to complete in 1 cycle, if possible. My goal is to do all this in parallel, but I've found out that may just be impractical on a low end FPGA. \$\endgroup\$ May 21 at 0:29
  • \$\begingroup\$ It is like communicating vessels. A monster coded for one clock cycle will meet a frequency 10 times smaller than a pipelined design. Unless you really want to save resources \$\endgroup\$
    – gotchi85
    May 22 at 11:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.