FPGA-based acceleration: Worked examples — Hardware deep dive

Before we compute anything, let us name the symbols so nobody is lost. Every one of these will appear on the diagrams too.

Definition The symbols we use everywhere

$S$ = number of pipeline stages. Picture a factory conveyor with $S$ work-benches in a row; an item must visit all $S$ before it is finished.
$M$ = number of data items we push through (samples, matrix rows, pixels).
$T$ = clock period, the time for one tick of the conveyor. If the clock is $f$ hertz then $T = 1/ f$ . (A "hertz" is one tick per second.)
$t_{ma x}$ = time the slowest single bench needs. The whole conveyor can only tick as fast as its slowest bench, so $T = t_{ma x}$ .
$B$ = memory bandwidth (bytes we can fetch per second) and $I$ = arithmetic intensity (compute operations we do per byte fetched). Their product $B \cdot I$ is the fastest rate memory can feed.
$P_{p e ak}$ = the chip's peak compute rate (operations per second) if fed with infinite data — the hard ceiling set by how many multiply/add units the silicon holds.

The one formula the whole page revolves around, restated so we own it:

The scenario matrix

Every FPGA-timing question is one of these cells. The worked examples below each carry a tag [C#] telling you which cell they cover.

#	Case class	What is extreme about it	Example
C1	Large $M$ (streaming limit)	$M \to \infty$ , speedup $\to S$	Ex 1
C2	Tiny $M$ ( $M = 1$ , single item)	Fill cost dominates, no speedup	Ex 2
C3	Degenerate pipeline ( $S = 1$ )	Nothing to pipeline — sanity floor	Ex 3
C4	Balanced vs unbalanced stages	One slow stage sets $T$	Ex 4
C5	Compute-bound side of roofline	$P_{p e ak} < B \cdot I$	Ex 5
C6	Memory-bound side of roofline	$B \cdot I < P_{p e ak}$ ; more logic useless	Ex 6
C7	Real-world word problem	Choose device from latency budget	Ex 7
C8	Exam twist	Clock unit trap + efficiency $\to S$	Ex 8

Related vault topics you should keep open while reading: Pipelining and Throughput, Roofline Model & Arithmetic Intensity, Configurable Logic Blocks (LUTs & Flip-Flops), GPU vs FPGA vs ASIC trade-offs, High-Level Synthesis (HLS), Dataflow architectures.

Look at the conveyor above: the first item (amber) must crawl across all $S$ benches — that crawl is the fill. After it exits, cyan items follow one per tick. That single picture is why every case below behaves the way it does.

C1 — The streaming limit (large $M$ )

Compute pipelined cycles. $cycles = S + (M - 1) = 8 + 99, 999 = 100, 007$ . Why this step? The conveyor picture: the very first item needs all $S = 8$ ticks to crawl the whole pipe (the fill), and the remaining $M - 1 = 99, 999$ items each add exactly one more tick as they pop out behind it. $8 + 99, 999 = 100, 007$ .
Compute speedup. $\frac{M S}{S + M - 1} = \frac{100 , 000 \times 8}{100 , 007} = \frac{800 , 000}{100 , 007} \approx 7.9994$ . Why this step? Comparing to the serial CPU that spends $M \cdot S$ ticks.
Interpret. We are within $0.008%$ of the ceiling $S = 8$ . Why this step? Confirms the limit $\frac{M S}{S + M - 1} \to S$ as $M \to \infty$ .

Recall Verify

As $M \to \infty$ , divide top and bottom by $M$ : $\frac{S}{1 + ( S - 1 ) / M} \to S$ . With $M = 100, 000$ and $S = 8$ , we sit at $7.9994$ — essentially $8$ . Units: dimensionless (a ratio of times). ✓

C2 — One lonely item ( $M = 1$ )

Cycles for the pipeline. $S + (M - 1) = 8 + 0 = 8$ ticks. Why this step? With $M = 1$ there is nothing behind the item to overlap with; it just crawls the full length.
Cycles for the serial CPU. $M \cdot S = 1 \times 8 = 8$ ticks. Why this step? One item, eight serial operations.
Speedup. $\frac{1 \times 8}{8 + 1 - 1} = \frac{8}{8} = 1$ . Why this step? Both machines take the same time — the pipeline gave zero benefit.

Recall Verify

$\frac{M S}{S + M - 1}$ at $M = 1$ gives $\frac{S}{S} = 1$ for any $S$ . Speedup is exactly $1$ . ✓

C3 — The degenerate pipeline ( $S = 1$ )

Plug in. $\frac{M S}{S + M - 1} = \frac{5000 \times 1}{1 + 5000 - 1} = \frac{5000}{5000} = 1$ . Why this step? One stage means each item occupies the whole datapath alone — no room to overlap a second item.
Interpret the ceiling. The limit as $M \to \infty$ is $S = 1$ . Why this step? You can never beat $1 \times$ if there is only one stage. The ceiling is the stage count.

Recall Verify

$S = 1 \Rightarrow \frac{M}{M} = 1$ for all $M$ . The degenerate case correctly reports "no speedup". ✓

C4 — Unbalanced stages set the clock

Find the bottleneck (a). The clock can tick no faster than the slowest bench: $T = t_{ma x} = 9 ns$ . Why this step? Every stage shares one clock; if it ticked faster than $9 ns$ , the slow stage would not be finished when the tick arrives → wrong data (a timing-closure violation, see parent note).
Total time before the split (b). $(S + M - 1) T = (4 + 999) \times 9 = 1003 \times 9 = 9027 ns$ . Why this step? Direct use of the pipeline-time formula.
After splitting (c). Now $S = 6$ , $T = 3 ns$ : $(6 + 999) \times 3 = 1005 \times 3 = 3015 ns$ . Why this step? Two more stages cost two extra fill ticks, but each tick is three times shorter — a huge net win.
Speedup from re-balancing. $9027/3015 \approx 2.994 \times$ faster. Why this step? Confirms the intuition: the slowest stage was throttling everyone; slicing it lets the clock breathe.

Recall Verify

Before: $9027 ns$ . After: $3015 ns$ . Ratio $\approx 2.994$ . Units all in ns → ratio dimensionless. ✓

C5 — Compute-bound (roofline, right side)

Compute the memory ceiling. $B \cdot I = 20 GB/s \times 40 ops/byte = 800 GOP/s$ . Why this step? This is the fastest memory can feed you.
Take the min. $min (500, 800) = 500 GOP/s$ . Why this step? Memory could feed $800$ , but the silicon can only chew $500$ — compute is the wall.
Verdict: compute-bound. Adding more BRAM caching won't help; you'd need more DSP slices / a deeper pipeline. Why this step? You fix the binding constraint, never the slack one.

Recall Verify

$B \cdot I = 800$ , $P_{p e ak} = 500$ , $min = 500$ . Compute-bound because $P_{p e ak} < B \cdot I$ . ✓

C6 — Memory-bound (roofline, left side)

Ceiling (a). $B \cdot I = 20 \times 5 = 100 GOP/s$ ; $min (500, 100) = 100$ . Memory-bound. Why this step? Memory only feeds $100$ ; the $500$ of compute mostly sits idle.
Double the compute (b). $min (1000, 100) = 100 GOP/s$ — unchanged. Why this step? You widened the slack side; the bottleneck (memory) never moved. This is the "more logic used ≠ faster" mistake from the parent note.
Raise intensity via BRAM (c). New $B \cdot I = 20 \times 30 = 600$ ; $min (500, 600) = 500 GOP/s$ . Why this step? Reusing cached data means fewer DRAM trips per op → higher $I$ → you slide up the diagonal onto the compute roof. $5 \times$ faster.

Recall Verify

(a) $min (500, 100) = 100$ . (b) $min (1000, 100) = 100$ (no change). (c) $min (500, 600) = 500$ ; $500/100 = 5 \times$ . ✓

C7 — Real-world word problem: pick the device

FPGA latency (a). First result after $S$ ticks: $20 \times 5 ns = 100 ns = 0.1 μ s$ . Why this step? Latency = pipeline fill = $S T$ . Compare to the $10 μ s$ budget → passes with vast margin.
FPGA throughput (b). After the pipe is full it emits one sample per tick, so a frame of $N = 1000$ samples takes $N T = 1000 \times 5 ns = 5 μ s \leq 8 μ s$ . ✓ Why this step? Throughput is the sustained rate; multiplying the frame size $N$ (given in the problem) by the tick $T$ gives the per-frame time, and $5 μ s < 8 μ s$ meets the deadline.
GPU check (c). Throughput $6 μ s \leq 8 μ s$ ✓ but latency $50 μ s > 10 μ s$ ✗. Why this step? The GPU batches to get throughput, blowing the latency budget. Reject it.
Decision. The FPGA meets both; the GPU fails latency. Choose the FPGA — the classic low-latency streaming win.

Recall Verify

FPGA latency $= 100 ns \leq 10, 000 ns$ ✓; frame time $5 μ s \leq 8 μ s$ ✓; GPU latency $50 μ s > 10 μ s$ ✗. FPGA is the only device passing both. ✓

C8 — Exam twist: the clock-unit trap + efficiency

Convert the clock (the trap). $T = \frac{1}{200 \times 1 0 ^{6} Hz} = 5 \times 1 0^{- 9} s = 5 ns$ . Why this step? MHz is millions of ticks per second; forgetting to invert gives nonsense. Always turn frequency into a period before plugging into a time formula.
Pipeline time (a). $(S + M - 1) T = (12 + 9999) \times 5 ns = 10, 011 \times 5 ns = 50, 055 ns \approx 50.06 μ s$ . Why this step? Straight into the pipeline-time formula with the correct $T$ : 11 fill ticks plus $M - 1 = 9999$ pops, all $\times 5 ns$ .
CPU time (b). $M \times S \times 1 ns = 10, 000 \times 12 \times 1 ns = 120, 000 ns = 120 μ s$ . Why this step? The serial machine has no overlap: every one of the $M = 10, 000$ items costs its full $S = 12$ operations, each $1 ns$ , so total $= M \cdot S \cdot 1 ns$ .
Efficiency (c). $\frac{CPU time}{pipeline time} = \frac{120 , 000}{50 , 055} \approx 2.40$ ? No — efficiency here means the speedup $\frac{M S}{S + M - 1} = \frac{120 , 000}{10 , 011} \approx 11.99$ . Why this step? Efficiency is the honest speedup ratio $\frac{M S}{S + M - 1}$ (same total work $M S$ over the pipe's actual $S + M - 1$ ticks). At $11.99$ we sit at $99.9%$ of the ceiling $S = 12$ , because the $11$ -tick fill cost is negligible against $10, 000$ streamed items — this is exactly the $M \to \infty$ limit approaching $S$ .

Recall Verify

$T = 5 ns$ ; pipe $= 50, 055 ns$ ; CPU $= 120, 000 ns$ ; efficiency $= 120, 000/10, 011 \approx 11.99 \approx S = 12$ . Matches the parent note's numbers. ✓

Recall check

FPGA speedup for a single item (

M = 1

) through any

S

-stage pipeline?

Exactly

1

— no overlap possible, so pipelining buys nothing.

Why does a memory-bound kernel ignore extra compute units?

Because

P \leq min (P_{p e ak}, B \cdot I)

and

B \cdot I

is the binding term; widening

P_{p e ak}

leaves the min unchanged. Raise

I

(BRAM reuse) instead.

What sets a pipeline's clock period?

The slowest single stage,

T = t_{ma x}

— never the average; violating it breaks timing closure.

Convert

200 MHz

to a period.

T = 1/ (200 \times 1 0^{6}) = 5 ns

Speedup ceiling of an

S

-stage pipeline as

M \to \infty

S

— one full computation finishes every cycle once the pipe is full.