2
\$\begingroup\$

EDIT:

Unfortunately, the example below was poorly chosen. Several people correctly pointed out that x2 is just a bit shift and doesn't actually require a multiplication. I'm aware of this but I overlooked it when attempting to devise a sufficiently simple example.

A better example would be to replace that 2 by an \$m\$, where \$m\$ is some integer that is not, in general, a power of 2.


I'm implementing the following difference equation in digital logic on an FPGA: $$ a[n] = b[n] + c[n] + 2a[n-1], $$ where \$n\$ denotes the sample number, and \$b\$ and \$c\$ are inputs.

I'm attempting to pipeline it such that each combinational path between registers has at most one operation (addition or multiplication). I believe this task is impossible. Am I correct?

To justify this claim, let's start with the simpler difference equation: $$ a[n] = b[n] + c[n] + a[n-1], $$ The following block diagram implements this:

enter image description here

I can use SageMath to verify this (I've 0-initialized r1 and r2):

import numpy as np

n = np.arange(10)
b = list(var(f"b_{i}") for i in n)
c = list(var(f"c_{i}") for i in n)
x = var("x")


def maybe(a):
    if diff(a, x) != 0:
        return x
    return a


def r1(n):
    if n == 0:
        return 0
    return maybe(b[n - 1] + c[n - 1])


def r2(n):
    if n == 0:
        return 0
    return maybe(r1(n - 1) + r2(n - 1))


for i in n:
    print(f"{i}: {r2(i)}")

which yields,

0: 0
1: 0
2: b_0 + c_0
3: b_0 + b_1 + c_0 + c_1
4: b_0 + b_1 + b_2 + c_0 + c_1 + c_2
5: b_0 + b_1 + b_2 + b_3 + c_0 + c_1 + c_2 + c_3
6: b_0 + b_1 + b_2 + b_3 + b_4 + c_0 + c_1 + c_2 + c_3 + c_4
7: b_0 + b_1 + b_2 + b_3 + b_4 + b_5 + c_0 + c_1 + c_2 + c_3 + c_4 + c_5
8: b_0 + b_1 + b_2 + b_3 + b_4 + b_5 + b_6 + c_0 + c_1 + c_2 + c_3 + c_4 + c_5 + c_6
9: b_0 + b_1 + b_2 + b_3 + b_4 + b_5 + b_6 + b_7 + c_0 + c_1 + c_2 + c_3 + c_4 + c_5 + c_6 + c_7

Now, let's add back the x2. In order to meet the combinational path requirements, I have to add a register after this multiplication. A block diagram that incorrectly implements this is shown below.

enter image description here

This is incorrect because r3 time-misaligns \$c\$ and \$b\$ with the feedback data. However, the next block diagram shows why I believe it isn't possible to realign \$c\$ and \$b\$ in the correct way.

enter image description here

The right-most adder has two inputs. The sequential logic paths for these inputs are highlighted by the blue and red arrows. In the correct implementation (remove r3), the total delay of the red path is one sample period greater than that of the blue path. This makes sense, since we're adding the output one sample ago to the current inputs. r3 increases the red path delay by 1 sample period, invalidating the circuit. In order to rectify this we would need to add a delay to the blue path. But, that's not possible since any delay added to the blue path also adds the same delay to the red path.

Do I have any options here? Do I just have to accept that the feedback combinational path will have a multiplication and an addition? Anything else I can do?

Is there any mathematical or computer science theory that discusses/formalizes these notions? I spent a while skimming digital logic and FPGA textbooks and didn't find anything.

\$\endgroup\$
9
  • \$\begingroup\$ Why not multiply the sum of B and C by 0.5 then, after the final "a" output multiply by 2? \$\endgroup\$
    – Andy aka
    Jan 12, 2022 at 0:55
  • \$\begingroup\$ Why are you registering a lane change? (r2 --> r3) \$\endgroup\$
    – jonk
    Jan 12, 2022 at 1:11
  • \$\begingroup\$ @Andyaka yeah nicely done, that works. But, I'm not thrilled about the division. It's lossy unless I add a bit and increases complexity somewhat, especially if I use something other than 2. Granted I didn't mention any of these concerns (or that I was using fixed-point, etc.) in the original question and you did satisfy the constraints. \$\endgroup\$
    – MattHusz
    Jan 12, 2022 at 1:13
  • \$\begingroup\$ @jonk mind clarifying what that means? I'm adding a register between the multiplication and addition. I could remove r3 altogether and the result would be correct, but then I have a multiplication and addition in the combinational path, which violates the constraints I set. \$\endgroup\$
    – MattHusz
    Jan 12, 2022 at 1:15
  • \$\begingroup\$ Is that a multiplication by two? A shift. Simply a lane change of the prior result? I may be misreading, I admit. (I've definitely got some kind of illness, today, and have only been up a few minutes.) \$\endgroup\$
    – jonk
    Jan 12, 2022 at 1:19

2 Answers 2

1
\$\begingroup\$

Consider your first figure, and pretend the feedback contains a general variable coefficient multiplier. Per you clarification, you are processing at fs = fclk, and fclk is maximized for the target FPGA.

Retiming

Let's first look at the basics of retiming: moving delay elements without changing the input to output behaviour, except for changing latency.

You can move delay elements around:

  • through constant multipliers or constant adders
  • through nodes (e.g. 2-input adders and multipliers) by merging/doubling the delays along the path
  • add new delays at inputs (usually all) and at outputs (usually all) to add latency

Moving delay elements if often the trick to break up critical DSP paths. These are long paths of mathematical operations that need to complete in one sample processing cycle, i.e. they complete between z^-1 delay elements. Your adder-multiplier pair is a typical example, and other filter structures may have variations such as long strings of adders, or multiple adder-multiplier pairs etc...

So your r2 in your first figure can move to the right past the feedback tap off by doing the following:

  1. move r2 past the tap off, thus adding a delay to the output (optionally this one can be removed altogether if the overall delay does not matter)
  2. duplicate it (you get a r2') and move r2' down along the tap-off to the input of the multiplier

You now have an equivalent structure but with r2 duplicated.

Then move r2' through the multiplier so that it sits between the multiplier and the adder. The structures you get are input/output equivalent, spare perhaps a bulk delay, but internal sates will not be identical.

This moved the delay element, it broke up one critical path, but created a new one.

Theoretically (and for the sake of illustration) you can further move it through the adder to the adder's output, and you have to move r1 through the adder too. Then merge r2' with the moved r1. Look carefully and you then have the equivalent structure as in your first figure, but with the delay r1 sitting at the output.

In feedforward structures, this kind of by adding new delays and moving them through mathematical operations or deep logic operations will create pipeline stages and break-up critical flop-to-flop paths.

Unfolding

DSP structures with feedback can also be pipelined but are regrettably not treated as easily as retiming a feedforward structure.

An approach for pipelining feedback uses a technique called "unfolding": you can't pipeline the feedback IIR structure in a naive way by just moving delay elements around, but you can apply a 2D delay in the feedback in stead of 1D, and calculate y(n) = f( x((n) and y(n-2)).

Note, it's still a 1st order IIR but with y(n-2) in stead of the usual y(n-1). The difference equation is:

y(n) = y(n-2)K^2 + kx(n-1) + x(n)

This is called unfolding or "look-ahead", and comes at the expense of more hardware.

Since you are operating at the clock rate, sharing resources will not be possible -as I am sure you know- and you'll have to instantiate dedicated multipliers and adders for each multiplication and addition.

enter image description here

Cut-sets

Now split the 2D delay into two 1D delays and move one of them forward or back to reside between the addition and multiplication. You would likely also move the D at the input for similar reasons there.

So, if a back-to-back "unflopped" multiply and add in the feedback were problematic, this will solve it.

Deeper study

For more details you can look at IIR unfolding, retiming, cutsets and pipelining.

This was heavily studied in the late 80s in the area of VLSI, DSP and arithmetic structures, for instance in works by Parhi and Messerschmitt.

Image: https://www.site.uottawa.ca/~mbolic/elg6163/lee.pdf

\$\endgroup\$
6
  • \$\begingroup\$ I don't totally follow. To clarify, when you say "Then move r2 through the multiplier", this should be r2', right? If I follow your steps up through this point (assuming I've done so correctly) then I have a delay between the multiplier and the adder (r2') but I no longer have one between the adder and the multiplier, since r2 is now past the feedback tap-off. I could follow your next step to move r2' through the adder, but now I no longer have a delay between the multiplier and adder. Also, I don't understand why r1 also needs to be moved (we're back to basically the original structure). \$\endgroup\$
    – MattHusz
    Jan 12, 2022 at 18:14
  • \$\begingroup\$ @MattHusz Yes, r2', typo. Ok, from your comment it seems I misunderstood your question. First: is f_clk a given and can you process the sampled input at fs=f_clk/2 (or less)? If yes, I can show you how to retime the circuit so that adder and multiplier are separated by flops on both sides, even in feedback. Also, is this a theoretical question or do you have a practical synthesis timing closure problem? \$\endgroup\$
    – P2000
    Jan 12, 2022 at 20:28
  • \$\begingroup\$ It's a theoretical question, but it's the essence of the problem I'm facing in a real design. The constraints I've set are admittedly a bit superficial and possibly overly strict (I have not implemented this in HDL yet, and it's possible that it would meet timing as is). But, I asked it this way for a reason. The add->register->multiply->register->add maps efficiently to a single DSP slice on a Xilinx FPGA. So, while I might be able to get away with not doing it this way, I'd very much like to. It's also useful from a theoretical perspective: I'm trying to generalize my understanding of (1/2) \$\endgroup\$
    – MattHusz
    Jan 12, 2022 at 21:24
  • \$\begingroup\$ Similar examples from this example. By the way, the recommendation to search Parhi and Messerschmitt was great. I started reading "VLSI Digital Signal Processing Systems" by Parhi and it seems to be a tremendous resource. (2/2) \$\endgroup\$
    – MattHusz
    Jan 12, 2022 at 21:27
  • \$\begingroup\$ To directly answer your question: I do need to process at the full f_clk, and f_clk is quite fast. \$\endgroup\$
    – MattHusz
    Jan 12, 2022 at 21:27
1
\$\begingroup\$

I think my answer is essentially the same as P2000's answer, but maybe a different way of stating it will be helpful.

I'm going to assume that where you wrote \$2\$, you meant to write \$13\$ :)

If the recurrence relation

$$ a[n] = b[n] + c[n] + 13a[n-1] $$

holds, then the recurrence relation

$$ a[n] = b[n] + c[n] + 13 \big (b[n-1] + c[n-1] + 13a[n-2] \big) $$

also holds. This recurrence relation can be simplified to

$$ a[n] = \big (b[n] + c[n] + 13 b[n-1] + 13 c[n-1] \big) + 169 a[n-2]. $$

So, in order to implement this using only one operation in between one register and the next, you can build a pipeline that has two sections:

  • one section which computes \$\big (b[n] + c[n] + 13 b[n-1] + 13 c[n-1] \big)\$ every two cycles, and
  • one section which multiplies by \$169\$ in one cycle, and adds the result from the previous section in the next cycle.
\$\endgroup\$
3
  • \$\begingroup\$ Nicely explained. However, I don't think it's actually possible to compute \$b[n]+c[n]+13b[n-1]+13c[n-1]\$ in two cycles with only one 1- or 2-input operation between each register. I think that takes at least 3 cycles. \$\endgroup\$
    – MattHusz
    Jan 13, 2022 at 20:16
  • \$\begingroup\$ @MattHusz Yeah, I think you'll end up with a latency of 3 cycles. But if I understand the situation right, the throughput is what matters for that section of the pipeline, and you can definitely obtain a throughput of once every two cycles. \$\endgroup\$ Jan 13, 2022 at 22:10
  • \$\begingroup\$ Yep, you're right, just now arrived at the desired result with this method. Thanks! \$\endgroup\$
    – MattHusz
    Jan 13, 2022 at 22:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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