FPGA-based acceleration: Exercises — Hardware deep dive

The three formulas we lean on all page long — restated so nothing is used before it is shown:

Formula Toolbox restated

Pipeline cycles for $M$ items through $S$ stages (the slowest stage sets clock period $T$ ): $cycles = S + (M - 1), Time_{p i p e} = (S + M - 1) T$ Why is there no extra "drain" term? A pipeline fills in $S - 1$ cycles before the first result appears on cycle $S$ ; after that one result exits every cycle. The last of the $M$ items exits on cycle $S + (M - 1)$ . Draining is not separate work — it is just the tail items walking out one per cycle, already counted in the $(M - 1)$ . So $S + (M - 1)$ covers fill, steady state, and drain together.

Speedup — where does $\frac{M S}{S + M - 1}$ come from? Compare two ways to run the same job.

Serial (no pipeline): each item must pass through all $S$ stages before the next item may start, because there is only one worker doing one stage at a time. One item costs $S$ cycles, so $M$ items cost $M \times S$ cycles. That is the numerator: $serial cycles = M S$ .
Pipelined: the $S$ stages are $S$ separate workers arranged in a line, each handing its output to the next. That overlap is exactly what turns $M S$ into $S + M - 1$ cycles (derived just above). That is the denominator.

Divide the slower by the faster (the clock period $T$ cancels because both use the same clock): $Speedup = \frac{serial cycles}{pipelined cycles} = \frac{M S}{S + M - 1} M \to \infty S .$ Intuition for the limit: as $M$ grows huge, the fixed " $S - 1$ " head-start cost is a drop in the ocean, so pipelined time $\approx M$ cycles versus serial $M S$ cycles — a clean $S \times$ win, one item's worth of work finishing every cycle.

Roofline — the ceiling on achievable performance. Here $P$ = performance, measured in operations per second (how many useful compute operations the design actually completes each second): $P \leq min (P_{p e ak}, B \cdot I)$ where $P_{p e ak}$ = the hardware's maximum ops/second if never starved for data, $B$ = memory bandwidth in bytes/second, and $I$ = arithmetic intensity = operations performed per byte moved. The product $B \cdot I$ therefore has units $(bytes/s) \times (ops/byte) = ops/s$ , matching $P$ .

Here $T$ (the clock period) is the time for one tick of the clock; if the clock frequency is $f$ (ticks per second) then $T = 1/ f$ . A period of $5 ns$ means $f = 200 MHz$ , because $1/ (5 \times 1 0^{- 9} s) = 200 \times 1 0^{6}$ ticks/s.

Level 1 — Recognition

Exercise 1.1

Match each block to the single job it exists for: LUT, Flip-Flop, BRAM, DSP slice, Interconnect.

Recall Solution

LUT (Look-Up Table): a tiny truth-table memory that becomes any boolean gate of its inputs — the atom of custom logic.
Flip-Flop: a 1-bit register that holds pipeline state between two clock edges.
BRAM: on-chip SRAM that keeps data near the compute so you avoid slow DRAM trips.
DSP slice: a hardwired multiply-accumulate unit; multipliers are expensive built from LUTs, so they are hardened.
Interconnect: programmable wires + switches that let you connect blocks into any topology.

See Configurable Logic Blocks (LUTs & Flip-Flops) for the LUT/FF pair in depth.

Exercise 1.2

A $6$ -input LUT stores how many output bits, and why exactly that many?

Recall Solution

A $k$ -input LUT stores $2^{k}$ bits — one output for every combination of its inputs. With $k = 6$ : $2^{6} = 64 bits.$ Six inputs have $64$ possible input patterns; the truth table needs one output entry per pattern. Write any boolean function's truth table into those $64$ cells and the LUT is that function.

Exercise 1.3

"Field-programmable" — what does field mean, and what physical object does the programming?

Recall Solution

Field = after manufacturing, out in the world (the "field"), not baked in at the factory. The programming is done by a bitstream: a configuration file that flips every LUT cell and interconnect switch into the pattern that realises your circuit. Contrast an ASIC, whose logic is fixed forever at fabrication.

Level 2 — Application

Exercise 2.1

A pipeline has $S = 8$ stages and streams $M = 5000$ items at clock $T = 4 ns$ . Find the total time and the speedup over the serial version.

Recall Solution

Cycles: $cycles = S + (M - 1) = 8 + 4999 = 5007.$ Time: $5007 \times 4 ns = 20028 ns \approx 20.03 μ s .$ Speedup: $\frac{M S}{S + M - 1} = \frac{5000 \times 8}{5007} = \frac{40000}{5007} \approx 7.99.$ Just shy of the ideal $8 \times$ : the $S - 1 = 7$ fill cycles are tiny against $5000$ items. This is Pipelining and Throughput in one line.

Exercise 2.2

Same $S = 8$ pipeline but only $M = 8$ items. What speedup now, and what lesson does it teach?

Recall Solution

$\frac{M S}{S + M - 1} = \frac{8 \times 8}{8 + 8 - 1} = \frac{64}{15} \approx 4.27.$ Only $\approx 4.27 \times$ , not $8 \times$ . Lesson: the fill cost $S - 1$ is fixed; it only becomes negligible when $M ≫ S$ . Short streams pay the fill penalty heavily. Latency (first result after $S$ cycles) dominates when $M$ is small.

Exercise 2.3

An FPGA runs at $250 MHz$ and completes $1000$ operations every cycle. A CPU runs at $4 GHz$ and completes $10$ operations every cycle. Which has higher throughput, and by how much?

Recall Solution

Throughput $=$ (ops/cycle) $\times$ (cycles/second): $FPGA = 1000 \times 250 \times 1 0^{6} = 2.5 \times 1 0^{11} ops/s .$ $CPU = 10 \times 4 \times 1 0^{9} = 4 \times 1 0^{10} ops/s .$ Ratio: $\frac{2.5 \times 1 0 ^{11}}{4 \times 1 0 ^{10}} = 6.25.$ The FPGA is $6.25 \times$ faster despite its far lower clock — parallelism $\times$ pipelining beats raw clock speed.

Level 3 — Analysis

Exercise 3.1

A kernel has arithmetic intensity $I = 2 ops/byte$ and runs on hardware with bandwidth $B = 20 GB/s$ and peak compute $P_{p e ak} = 100 GOP/s$ . Is it compute-bound or memory-bound, and what is the best achievable $P$ ?

Recall Solution

Roofline: $P \leq min (P_{p e ak}, B \cdot I)$ . $B \cdot I = 20 \times 1 0^{9} \times 2 = 40 \times 1 0^{9} = 40 GOP/s .$ Compare to $P_{p e ak} = 100 GOP/s$ . Since $40 < 100$ , the memory roof is lower: $P \leq min (100, 40) = 40 GOP/s \Rightarrow memory-bound .$ You are leaving $60 GOP/s$ of compute idle.

The figure below plots this. Its horizontal axis is ==arithmetic intensity $I$ in ops/byte (how much compute each fetched byte feeds); its vertical axis is performance $P$ == in GOP/s (billions of operations per second). The sloped orange line is the memory roof $B \cdot I$ , the flat violet line is $P_{p e ak}$ , the navy line is the actual attainable roof (the lower of the two), and the magenta dot marks this kernel at $I = 2$ sitting on the sloped (memory) part — read $P = 40$ straight off the vertical axis. See Roofline Model & Arithmetic Intensity.

Figure s01 — Roofline. X-axis: arithmetic intensity $I$ (ops/byte). Y-axis: performance $P$ (GOP/s). The magenta dot ( $I = 2$ ) sits on the sloped memory roof: memory-bound at $P = 40$ . Push intensity right past the ridge ( $I = 5$ ) and the violet dot ( $I = 8$ ) hits the flat compute ceiling at $P = 100$ .

Exercise 3.2

For Exercise 3.1, you buffer data in BRAM to reuse each byte $4 \times$ , raising intensity to $I = 8 ops/byte$ . Recompute $P$ . What is now the limiting factor?

Recall Solution

New memory roof: $B \cdot I = 20 \times 1 0^{9} \times 8 = 160 GOP/s .$ Now $min (P_{p e ak}, B \cdot I) = min (100, 160) = 100 GOP/s$ — the compute roof wins. The design is now compute-bound. On the roofline plot (figure s01) the operating point has moved right past the "ridge" where the sloped memory line meets the flat compute ceiling. Raising $I$ further no longer helps; only more compute units would.

Exercise 3.3

A design uses $90%$ of the FPGA's LUTs but sustains only $30%$ of peak throughput. Its intensity sits left of the roofline ridge. Someone proposes adding more compute units. Good idea?

Recall Solution

No. Left of the ridge means the workload is memory-bound — bandwidth $B$ , not compute, is the ceiling. More compute units add area and power but sit idle waiting for data. The correct fix is to raise arithmetic intensity $I$ : cache/reuse data in BRAM, tile the loops, stream so each fetched byte feeds many operations. Fix the bottleneck, not the abundant resource.

Level 4 — Synthesis

Exercise 4.1

Design a streaming accelerator for a $K = 16$ -tap FIR filter $y [n] = \sum_{k = 0}^{15} c_{k} x [n - k]$ . List the hardware blocks, say why each exists, and give the steady-state throughput.

Recall Solution

Blocks and their jobs:

16 DSP slices — one multiply per tap $c_{k} x [n - k]$ , all in the same cycle → 16-way spatial parallelism. (Hardened multipliers, not LUT-built.)
Adder tree, $lo g_{2} 16 = 4$ levels, each level registered — sums the 16 products. Pipelining the tree keeps the slowest stage small so the clock stays fast. This is dataflow.
Shift register of length 16 for $x$ — each cycle one new sample shifts in; every stored sample feeds a different tap over time. This gives data reuse: no byte is re-fetched from DRAM, so intensity stays high.

Throughput: after the pipeline fills, one $y [n]$ per clock cycle. A CPU does $\approx 16$ multiply-adds serially per output, so the speedup $\approx K = 16$ , bounded by input bandwidth. See High-Level Synthesis (HLS) for expressing this in C.

Exercise 4.2

For the Exercise 4.1 design at $T = 4 ns$ , streaming $M = 10000$ samples, the pipeline depth (fill) is $S = 1 + 4 = 5$ stages (1 multiply + 4 adder levels). Compute total time and the speedup over a serial CPU doing $16$ ops per sample at $1 ns/op$ .

Recall Solution

FPGA time: $cycles = S + (M - 1) = 5 + 9999 = 10004.$ $Time_{F P G A} = 10004 \times 4 ns = 40016 ns \approx 40.02 μ s .$ CPU time: $10000 \times 16 \times 1 ns = 160000 ns = 160 μ s .$ Speedup: $\frac{160}{40.016} \approx 4.0.$ Only $\approx 4 \times$ even though we placed 16 multipliers — because the FPGA clock period ( $4 ns$ ) is $4 \times$ the CPU op time ( $1 ns$ ). The parallelism-16 win is partly cancelled by the slower clock: $16/4 = 4$ . This is exactly the trade-off between low clock and high parallelism.

Level 5 — Mastery

Exercise 5.1 (degenerate case)

What is the pipeline speedup when $S = 1$ ? Interpret physically.

Recall Solution

$\frac{M S}{S + M - 1} = \frac{M \cdot 1}{1 + M - 1} = \frac{M}{M} = 1.$ Speedup $= 1$ for every $M$ . A "one-stage pipeline" has nothing to overlap — there is a single combinational block, no registers splitting the work, so pipelining buys nothing. Pipelining only pays when $S \geq 2$ , and its ceiling grows with $S$ .

Exercise 5.2 (limiting behaviour, both directions)

Fix $S = 10$ . Evaluate the speedup at $M = 1$ , $M = 10$ , $M = 1000$ , and $M \to \infty$ . Describe the curve's shape.

Recall Solution

$M = 1 : \frac{10 \cdot 1}{10 + 1 - 1} = \frac{10}{10} = 1.$ $M = 10 : \frac{10 \cdot 10}{10 + 10 - 1} = \frac{100}{19} \approx 5.26.$ $M = 1000 : \frac{10 \cdot 1000}{10 + 1000 - 1} = \frac{10000}{1009} \approx 9.91.$ $M \to \infty : \to S = 10.$ The curve rises from $1$ (one item = pure latency, no overlap) and saturates toward the horizontal asymptote $S = 10$ . It is concave: fast gains early, diminishing returns as $M$ grows.

The figure below draws exactly this curve. Its horizontal axis is the ==number of streamed items $M$ == (drawn on a log scale so both small and large $M$ are visible); its vertical axis is the speedup (dimensionless, "how many times faster than serial"). The three sample points and the dashed asymptote at $S = 10$ are marked.

Figure s02 — Speedup $M S / (S + M - 1)$ for $S = 10$ . X-axis: number of streamed items $M$ (log scale). Y-axis: speedup (×, dimensionless). Rises from $1$ at $M = 1$ , passes $5.26$ at $M = 10$ and $9.91$ at $M = 1000$ , and flattens toward the dashed line $S = 10$ .

Exercise 5.3 (two-roof crossover — the ridge point)

On a roofline with $P_{p e ak} = 100 GOP/s$ and $B = 25 GB/s$ , find the arithmetic intensity $I_{⋆}$ where the memory roof meets the compute roof (the "ridge"). What does an operating point at exactly $I_{⋆}$ mean, and which way should you move a point that lands left of it?

Recall Solution

The ridge is where the two roofs are equal: $B \cdot I_{⋆} = P_{p e ak} \Rightarrow I_{⋆} = \frac{P _{p e ak}}{B} = \frac{100 \times 1 0 ^{9}}{25 \times 1 0 ^{9}} = 4 ops/byte .$ At $I_{⋆} = 4$ the design is perfectly balanced: it saturates memory bandwidth and peak compute simultaneously. Left of $I_{⋆}$ ⇒ memory-bound; right of $I_{⋆}$ ⇒ compute-bound. A point that lands left of $I_{⋆}$ should be pushed rightward — raise its intensity $I$ (buffer and reuse data in BRAM so each fetched byte feeds more operations) until it reaches the ridge; past $I_{⋆}$ there is nothing more to gain from intensity, and only extra compute units would help.

Exercise 5.4 (synthesis of both models — when is the FPGA worth it?)

A workload streams $M = 2000$ items, needs $S = 20$ pipeline stages, clock $T = 5 ns$ . It is memory-bound: intensity $I = 1 op/byte$ , bandwidth $B = 8 GB/s$ , each item is $8$ bytes and needs $40$ ops. Compute (a) the ideal pipelined compute time, (b) the roofline memory-bound time, (c) which one actually governs — and explain why we must use total-ops $/ (B \cdot I)$ , not raw bytes $/ B$ .

Recall Solution

(a) Pipelined compute time (assuming data is always available — the compute roof only): $cycles = S + M - 1 = 20 + 1999 = 2019, Time_{co m p u t e} = 2019 \times 5 ns = 10095 ns \approx 10.1 μ s .$

(b) Roofline memory-bound time. Why not just bytes $/ B$ ? Raw transfer time $= bytes / B = (2000 \times 8) / (8 \times 1 0^{9}) = 2 μ s$ tells you only how long the wires are busy — it ignores how much useful compute each byte must feed. The roofline measures performance in ops/s, so the honest memory-bound time is total operations divided by the memory-limited op-rate $B \cdot I$ : $Time_{m e m} = \frac{total ops}{B \cdot I} = \frac{M \times 40}{B \times I} = \frac{2000 \times 40}{8 \times 1 0 ^{9} \times 1} = \frac{80000}{8 \times 1 0 ^{9}} = 10 μ s .$ The two numbers differ ( $2 μ s$ vs $10 μ s$ ) precisely because each byte carries $I = 1$ op here, but each item is $8$ bytes yet demands $40$ ops — so the compute-per-byte the memory roof allows ( $B \cdot I$ ) is the real throttle, not the raw byte count. Using bytes $/ B$ would wrongly claim the job finishes in $2 μ s$ .

(c) Which governs? A design cannot finish faster than the slower of its two ceilings. Here compute time $\approx 10.1 μ s$ and memory-bound time $= 10 μ s$ are nearly equal, so this design sits right at the ridge — neither roof is badly slack. The memory roof governs by a hair ( $10.0 < 10.1$ means memory is the tighter of the two only marginally; in practice they co-limit). To go faster you must lift both: raise $B$ (more DRAM channels) and raise $I$ (BRAM reuse). Improving only one just makes the other roof the new wall.