From hardware code to bitstream

You know what synthesis, placement, routing and static timing do for an ASIC; the Synthesis, Placement, Routing and Signoff chapters cover them. The FPGA versions solve the same problems with one constraint added: every resource, delay and wire already exists. That turns each step into an assignment problem onto a fixed resource graph, and it changes the algorithms in specific ways:

• Mapping is covering, not matching. A K-input LUT implements any of the $2^{2^K}$ functions of K inputs, so the mapper never asks which function a piece of logic computes, only whether it has at most K inputs.⁶ Depth-optimal mapping is then solvable in polynomial time; area-optimal mapping is not.
• Placement is discrete and typed. Logic, RAM and DSP blocks sit in columns of sites; the placer assigns instances to legal sites of the right type and cannot resize anything.¹⁰
• Routing is path search with fixed capacity. Every track and pin is a node of a routing-resource graph; the router picks paths so no node is used twice.⁷ Negotiated congestion was invented for exactly this case.⁹
• Timing closure has no gate sizing or buffering. The delay model is fixed per device and speed grade; the levers are logic structure, placement and constraints.²⁰
• Bitstream generation needs a device database. For open tools that database came from reverse-engineering projects such as IceStorm, Trellis and X-Ray.¹¹

FPGA synthesis differs from ASIC synthesis mainly at the back end. Coarse-grained passes infer primitives before any gate-level mapping: memory inference matches an array’s ports, widths and read timing to the RAM primitive (or falls back to LUT RAM or flip-flops), DSP inference folds multiply, add and accumulator register into one hard block, and carry chains are wrapped so the LUT mapper leaves them alone.² Only the residue becomes an AIG for ABC, whose FPGA mappers handle fixed and variable LUT sizes.⁴ A generic wide LUT can then be decomposed into the device’s physical LUTs plus dedicated multiplexers, as Yosys does for 7- and 8-input functions on Xilinx 7-series (two or four LUT6s plus MUXF7 and MUXF8).¹²

Two consequences for RTL style. First, inference is pattern matching, so a memory with an asynchronous read or an unusual reset can silently become thousands of flip-flops instead of one RAM block; check the utilization report. Second, vendor primitives instantiated directly in RTL make the code device-specific, which matters when an FPGA design is a prototype of an ASIC (see Verification, where FPGA prototyping is covered).

HLS adds scheduling, allocation and binding on top. Its central metric is the initiation interval $II$, bounded below by resource limits (memory ports) and by loop-carried dependences. For a loop body with $m$ memory accesses on a memory with $p$ ports, $II \ge \lceil m/p \rceil$. Partitioning arrays across banks raises $p$.²⁷

The subject graph is usually an AIG. Cut enumeration runs in topological order: a primary input has only its trivial cut, and for an AND node $n$ with fanins $n_1, n_2$,

with dominated cuts (supersets of another cut) removed.⁵ Depth-oriented mapping then labels each node with the best level any of its cuts achieves, where the level of a cut is $1 + \max_{m \in C} \ell(m)$, and keeps that cut as the node’s representative.⁵ Because a K-LUT accepts any function, every enumerated cut is usable; a cell mapper would discard cuts whose function no library cell matches, which is why ASIC mapping needs Boolean matching and FPGA mapping does not.

Area recovery runs in passes under the required times of that depth. Area flow gives a global estimate that divides shared logic among its fanouts:

and a second pass with exact local area (the LUTs that selecting a cut would add, counted by dereferencing the cut’s fanout-free cone) refines it.⁵ Exhaustive enumeration blows up for large K; keeping only a few priority cuts per node (5 to 10) gives depth-optimal results on 95% of benchmarks even with a single cut, and with 8 cuts reduces memory 10× and runtime 5× for 6-LUTs at comparable quality.⁵ The FlowMap labeling itself, which computes the same depth labels with network flow instead of enumeration, is in Under the hood.

The mapper enumerates all non-dominated K-feasible cuts of a two-input-gate network. “Depth first” takes the depth-optimal labels and then recovers area with area flow under those required times; “Area first” minimizes area flow alone; “Depth only” keeps FlowMap’s largest-volume cut with no recovery.⁵⁶ Try:

• The adder at K = 6 in “Depth only” versus “Depth first”: same depth, how many LUTs does recovery save, and where did the duplicated gates go?
• Turn on depth labels. Check that each LUT root’s label is one more than its deepest leaf.
• Compare “LUT bits used” across K for the comparator. Bigger LUTs cut depth but cost $2^K$ bits each, the architecture trade-off behind the choice of K.

The model counts LUTs and levels only. Real mappers also see carry chains, wide-function multiplexers and per-input delays, and work on AIGs that have been restructured first.

Typical FPGA placement runs four steps: an initial placement or floorplan, global placement under resource constraints, packing and legalization to exact sites, then detailed placement to fix the worst cases. Macros complicate it: carry chains, cascaded DSPs and LUT-plus-mux groups must occupy adjacent sites in one column.¹⁰

VPR’s annealer is the reference design. Its cost is a bounding-box sum with a fanout correction $q(n)$ (1 for nets of up to three terminals, rising to 2.79 at 50) and, for non-uniform channels, division by the average channel capacity $C_{av}$:

Its adaptive schedule sets the starting temperature to 20 times the standard deviation of cost over $N_{\text{blocks}}$ random swaps, tries $10\, N_{\text{blocks}}^{1.33}$ moves per temperature, and cools fastest when almost every move or almost no move is accepted. A range limiter shrinks the swap distance to keep the acceptance rate near 0.44. Cutting moves per temperature by 10× made placement 10× faster and only about 10% worse.⁷ The full schedule is in Under the hood.

Analytic placers (HeAP and its successors) minimize a quadratic or smoothed wirelength, then spread cells by region against each resource type’s supply, which annealing cannot match for runtime on large netlists. A 2023 open-source analytic placer reports critical-path delay within 2.2% and 0.59% of two Vivado releases at 14% and 8.5% more runtime.¹⁰ Packing order matters too: the Titan study traced much of VPR’s wirelength gap to Quartus II to VPR’s focus on dense packing.¹⁹

PathFinder’s node cost combines a base cost (the node’s delay), a present-sharing term that grows with the number of other nets on the node, and a history term that grows every iteration the node is overused; every net is rerouted every iteration, and timing-critical connections weight delay over congestion.⁹ The Routing chapter’s Under the hood works through the cost function. FPGA-specific details:

• Graph search per net. Each net is a Dijkstra (maze) expansion over the graph, run $k-1$ times for a $k$-terminal net. VPR keeps the wavefront when it reaches a sink and re-expands from the newly added wire at zero cost instead of restarting, which matters for high-fanout nets. It also limits each net to 3 channels outside its terminals’ bounding box and gives up after 45 iterations.⁷
• Lookahead. nextpnr’s router is timing-driven rip-up and reroute with A* search, which steers each expansion toward the sink with an estimate of the remaining cost.¹²
• Pin equivalence. All inputs of a LUT are functionally equivalent, so the architecture description can mark them interchangeable and the router may use whichever one is free.⁷
• Database size. The ECP5-85K graph (4M wires, 28M switches) takes 1 GB uncompressed; nextpnr deduplicates repeated tiles to 38 MB.¹²

A path’s delay is clock-to-Q, then alternating routing and LUT delays, then setup. With $L$ LUT levels the data arrival is roughly

and on an FPGA the net terms are usually larger than the LUT terms, because routing dominates delay.⁸ That makes the logic-level count a good first predictor, which is why vendor methodology asks designers to check the logic-level distribution against the target frequency and speed grade early.²⁰

Closure practice that follows from a fixed fabric:

• Restructure, don’t resize. Retiming in synthesis can move registers from low-level paths into high-level ones, applied globally or only to the blocks that fail.²⁰
• Separate logic delay from net delay. Too many levels is a design problem; long nets come from placement constraints or congestion and are fixed in placement or floorplanning.²¹
• Explore the tool’s search space. Placement and routing are heuristic, so different strategies and directives give different results; parallel runs and incremental flows from a good reference checkpoint trade compute for turnaround.²¹

Timing also feeds back into every earlier step: mapping can trade area for depth, T-VPack packs critical connections together, and placers and routers weight critical nets.⁸⁹

Bitstream generation is a serialization of the routing-resource graph’s chosen edges and every primitive’s configuration through the device database. On 7-series, configuration memory is addressed by frame: a 32-bit frame address, 101 words per frame (100 for the tiles in the column, one for the horizontal clock row), frames striped two words per tile, written in multiples of the frame size with auto-incrementing addresses and CRC checks on the register writes.¹⁶ F4PGA uses a textual intermediate, FASM, that names each enabled feature before it is packed into frames.¹⁷

The open databases come from fuzzers that sweep one feature at a time (logic, RAM, I/O, clocking, interconnect) through the vendor tools and correlate the changed bits.¹⁵ The same databases supply what nextpnr needs to place, route and time: locations, connectivity, and cell and interconnect timing.¹² nextpnr models each architecture as an API implementation rather than a flat description file, which lets it handle the irregularities of real devices; VPR instead generates architectures from parameters, which is what architecture research needs (for example, finding the smallest FPGA or narrowest channel a benchmark fits).¹²

Visibility is bounded by depth × width: each probed bit per sample costs block-RAM capacity, so a deep capture of a wide bus can exhaust the device’s RAM. Probes are attached either in RTL or on the synthesized netlist; the latter preserves the RTL but still needs place and route, and the added logic and routing can perturb timing near the probed paths.²² Trigger logic ranges from simple comparators to state-based sequences.²³

The practical cost is compile time. Each probe change is a new implementation run, which is why vendors emphasize incremental implementation from a reference checkpoint.²¹ The capture also happens in a clock domain of your choosing; signals from other domains are sampled asynchronously, with the same caveats as any clock domain crossing.

Read the Titan numbers with their context: Stratix IV-class architecture models, 2013 tool versions, and VPR’s runtime dominated by packing (about 78%) while Quartus II spent the largest share, 49%, in placement. VPR’s placer was in fact faster than Quartus II’s, partly because it packed more densely into fewer blocks; its router was 3.4× slower and routed high-fanout clock nets that Quartus II put on dedicated networks.¹⁹ The gap between academic and commercial tools has narrowed since: a 2023 open analytic placer reports critical-path delay within 0.59% of Vivado 2021.2 at 8.5% more runtime.¹⁰

The routing-graph sizes explain why databases matter: the ECP5-85K graph needs 1 GB uncompressed and 38 MB after nextpnr deduplicates repeated tiles, and the deduplicated 85K database is only 13% larger than the 25K one.¹²

• Depth versus area in mapping. Depth-optimal mapping duplicates logic; area recovery wins much of it back but not all, and exact area minimization is NP-complete.⁶⁵
• Packing density versus wirelength. Dense packing minimizes block count but can lengthen wiring; Titan attributed much of VPR’s 2.6× wire gap to it.¹⁹
• Annealing versus analytic placement. Annealing handles irregular legality naturally and trades quality for runtime smoothly; analytic placement scales to millions of cells but needs careful spreading and legalization for typed sites and macros.⁷¹⁰
• Closure by compute. Placement and routing are heuristics whose results depend on their settings, so teams buy closure with parallel strategy runs and incremental flows rather than design changes, which costs machines and time.²¹
• Open versus vendor flows. Open tools give full control and run anywhere, and their authors position them for research and experimentation rather than production, where certified vendor flows remain the norm.¹²

Whether any of this beats building an ASIC is a question of volume, speed and power, the subject of Where FPGAs win.

1. Cut-based LUT mapping

The mapper in the simulation, and ABC’s classic flow, are four passes over a topologically ordered subject graph:⁵

for n in topological order:                 # 1. enumerate cuts
  if n is a primary input: cuts[n] = {{n}}
  else: cuts[n] = {{n}} ∪ merge(cuts[a], cuts[b], K)   # drop dominated
for n in topological order:                 # 2. depth labels
  best[n] = argmin over nontrivial c in cuts[n] of 1 + max(label[m] for m in c)
  label[n] = that minimum
required = propagate(max output label)      # 3. area recovery
for n in topological order:
  best[n] = argmin area_flow(c) over cuts with depth(c) <= required[n]
cover = {}; frontier = outputs              # 4. cover from outputs
while frontier: n = pop(); cover += LUT(n, best[n]); frontier += gates in best[n]

The number of cuts grows quickly with K, which is why practical mappers keep a handful of priority cuts per node instead of all of them.⁵

2. FlowMap: depth labels by network flow

FlowMap computes the same optimal labels without enumerating cuts. Let $p$ be the largest label among node $t$’s predecessors. The label of $t$ is either $p$ or $p + 1$. To test for $p$, collapse $t$ together with every predecessor labeled $p$ into a single sink, give every node capacity 1, connect a source to the primary inputs, and run max-flow. If the flow is at most K, the min cut is a K-feasible cut of height $p - 1$, so $t$ gets label $p$; otherwise it gets $p + 1$. Augmenting paths stop as soon as the flow exceeds K, so each test costs $O(K\,|E|)$ and the whole labeling $O(K\,N\,|E|)$.⁶

Among minimum-height cuts FlowMap takes the one with the largest volume (found by searching from the source in the residual graph and taking the complement), which packs the most logic into each LUT. Covering then works back from the outputs and replicates shared logic implicitly, so a post-pass is needed to cut the LUT count.⁶ The simulation’s “Depth only” mode shows that raw result.

3. Area flow and exact area

Area recovery combines two views. Area flow, computed in one pass from inputs to outputs, spreads the cost of shared logic across its fanouts:

Exact local area then counts the LUTs a cut would really add: dereference the cut’s leaves, recurse into leaves whose reference count drops to zero, sum, and re-reference. The recursion only visits the cut’s maximum fanout-free cone, which is usually small.⁵ Duplication-free mapping, which restricts covering to fanout-free cones, can be solved optimally per cone, but the global area optimum may need duplication.⁶

4. Greedy packing

VPack and T-VPack build one cluster at a time: choose a seed (the unclustered element with the most used inputs, or in T-VPack the most critical), then repeatedly absorb the element with the highest attraction until the cluster is full or no legal element remains.⁸ In VPack, attraction is the number of nets shared with the cluster:

T-VPack ranks first by the highest criticality of any connection joining the element to the cluster, then uses shared nets to break ties, so critical connections end up inside clusters on the fast local wiring.⁸

5. VPR’s annealing schedule

T0       = 20 × stddev(cost over N_blocks random swaps)
moves(T) = 10 × N_blocks^1.33
T_next   = α × T, where α = 0.5   if R_accept > 0.96
                         0.9   if 0.8  < R_accept ≤ 0.96
                         0.95  if 0.15 < R_accept ≤ 0.8
                         0.8   if R_accept ≤ 0.15
D_limit  = D_limit × (1 − 0.44 + R_accept), clamped to [1, chip size]
stop when T < 0.005 × cost / N_nets

Each move swaps two blocks (or a block and an empty site of the same type) within the range limit; the move is accepted if the cost falls, or with probability $e^{-\Delta C / T}$ if it rises.⁷ Because a move’s cost change only involves the nets of the moved blocks, each evaluation is incremental, which is what makes millions of moves affordable.

6. Routing and analytic placement

Negotiated-congestion routing on the routing-resource graph is worked through in Routing; the FPGA-specific additions (incremental wavefronts, bounding-box limits, A* lookahead) are in the routing section above.⁷¹² Analytic placement for FPGAs follows the ASIC recipe in Placement (quadratic or smoothed wirelength, then spreading) with per-resource-type density, carry-chain and DSP-cascade macros, and a legalization step that maps cells to typed sites.¹⁰

Where FPGAs win turns this chapter’s costs into decisions: the area, speed and power gap to an ASIC, NRE and break-even volume, prototyping and emulation, and FPGAs beside processors. For how chip teams use this flow before tapeout, see Verification; for the fabric parameters (K, cluster size, routing architecture) that the algorithms here are tuned for, see Lookup tables and the FPGA fabric.