Pipelining digital logic with feedback

Question

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:

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.

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.

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.

Answer 1

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.

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

Answer 2

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.