Lookup Tables, Carry Chains, and the Routing Fabric

An application-specific integrated circuit implements a design by building wires and transistors for it. A field-programmable gate array does the opposite: it ships a fixed array of identical cells and a fixed switching network, and the design becomes a pattern of bits loaded into configuration memory. Nothing about the silicon changes between one design and the next. Everything that makes one design faster, larger, or cheaper than another follows from how well the mapped netlist fits a structure that was designed before the netlist existed.

The cell is a truth table, not a gate

The primitive of a modern fabric is a small memory with an output multiplexer. A $k$-input lookup table stores $2^k$ bits, one for each assignment of its inputs, and a tree of multiplexers selects the bit addressed by the current input pattern. A 4-input LUT therefore needs 16 configuration bits; a 6-input LUT needs 64. Because the multiplexer tree is built from pass transistors, the delay through the table is roughly independent of the function stored in it, which is the property that makes the structure programmable at all: an AND of six signals and an arbitrary six-variable function cost the same.

Vendors have converged on larger tables for a reason. The number of LUTs needed to implement a design falls quickly as $k$ grows, because deeper functions collapse into single cells, but the silicon area per cell grows as $2^k$ and the input multiplexing grows worse. Six inputs is the common compromise; several families use a fracturable arrangement in which one 6-input table can also serve as two 5-input functions sharing four inputs, which recovers density for logic that naturally splits.

Each cell also carries one or more flip-flops. In the common Xilinx arrangement a slice holds four 6-input LUTs and eight flip-flops, because each LUT output can drive two registers. That ratio is not incidental. Logic that is register-heavy, such as a shift register or a wide pipeline, exhausts slices while the lookup tables inside them sit idle, so a design’s real capacity is usually set by whichever of the two resources runs out first.

Registers in the cell are not bare flip-flops. They have a dedicated clock enable, a synchronous or asynchronous set/reset, and a bypass multiplexer that lets the cell behave combinationally. The enable and reset are driven from the general routing network, which means a wide enable signal with high fanout becomes a timing problem in its own right.

Why addition escapes the lookup table

A ripple-carry adder built from lookup tables would chain a carry through one table per bit, and each hop would pay the full table delay. Fabric designers long ago carved out a separate path for exactly this pattern. Every cell contains carry logic: a multiplexer that selects between the propagated carry and a generated carry, driven by two inputs.

The standard decomposition splits each bit into generate ($g = a \wedge b$), propagate ($p = a \oplus b$), and sum ($s = p \oplus c_{in}$). The carry into the next bit is $c_{out} = g \vee (p \wedge c_{in})$, which is a two-to-one multiplexer controlled by $p$. In older Xilinx devices this appeared as dedicated MUXCY and XORCY primitives; in current ones the same structure is grouped into carry blocks of four or eight bits with dedicated interconnect between them.

The consequence is that the carry chain, not the lookup table, is the critical path of an adder, and it is fast: a carry block propagates through a short vertical wire rather than through the general routing network. A 32-bit adder consumes 32 LUTs for the generate and propagate terms plus the carry chain, and its delay is a chain of carry multiplexers rather than a tree of logic levels. Long chains do eventually become slow, and synthesis tools break wide additions into tree structures or insert pipeline registers, but the fabric’s intent is clear: arithmetic is expected, and the fabric gives it a shortcut.

The same reasoning explains why comparators, counters, and address incrementers map efficiently, and why multiplication does not. A multiplier needs a carry-save reduction tree with a wide final addition, which is expensive in soft logic. That is why the larger devices include hardened multiplier-accumulate blocks, and why a design that instantiates many multipliers without using them will not fit at the density its LUT count suggests.

Routing is the design’s real constraint

Between the cells sits a switching network. The conventional model is an island-style fabric: logic blocks on a grid, channels between them, connection boxes that attach cell pins to channel wires, and switch boxes at channel intersections that join horizontal and vertical segments. Configuration bits set the pass transistors in those boxes, so a route is a sequence of wire segments joined by switches.

Segments come in several lengths. Single-length wires span one logic block and demand a switch at every step; longer segments span two, four, or six blocks and cross the array with fewer switches, at the cost of granularity. A few long lines run the full height or width of the device and are the natural home for high-fanout signals. Delay scales with the number of switches a path traverses, because each switch contributes resistance and capacitance, and it scales with the length of the wire. A route that crosses the die in single-length segments passes through dozens of switch boxes and can cost more than every lookup table on the path combined.

This is the central fact of FPGA timing. In a deep-submicron process, a lookup table and its register might switch in a fraction of a nanosecond, while a route spanning a large fraction of the die can consume several nanoseconds. Interconnect, not logic, dominates the delay of most critical paths, and it also dominates the area question: two designs with the same LUT count can differ by a factor in routability because one spreads its logic across the array and the other concentrates it into a region where the local channels saturate. The placement and routing problem that follows from this is treated in placement, routing, and congestion.

Configuration memory and what a bitstream is

Every choice described so far is a stored bit: the 64 bits of a lookup table mask, the select lines of the output multiplexer, the enable of a register, the pass transistors of a connection box, the mode of an I/O buffer. Configuration memory is organized into frames, each frame covering a column of resources at one row of the device, and a bitstream is a sequence of frame addresses followed by frame contents. Loading a bitstream writes every frame in turn, so the entire device state is defined by a few megabytes of data for a mid-range part.

Because the configuration cells are static RAM, they hold their contents only while powered. This is the defining trade of SRAM-based FPGAs: unlimited reconfigurability and ordinary CMOS processing, in exchange for a configuration step at every power-up and a sensitivity to single-event upsets in the configuration memory. A board must therefore provide a configuration source, whether a serial flash device read by the FPGA’s own configuration logic or a processor that writes the bitstream. Flash-based and antifuse-based fabrics avoid that step but give up either reprogrammability or fine-grained density.

The same memory structure enables partial reconfiguration, where a subset of frames is rewritten while the rest of the device keeps running, which is the subject of partial reconfiguration. It also creates a security question: unless readback is disabled and the bitstream is encrypted, the configuration of a device can be extracted and analyzed, which is why bitstream encryption exists on the larger families.

Where the abstraction misleads

Two habits cause most of the trouble when reasoning about fabric capacity. The first is treating LUT utilization as an area measure. A report that says 60 percent of lookup tables are used says nothing about whether the design will route, because routing demand is concentrated by locality and a dense cluster of logic can overuse a few channels while the rest of the array is empty. Utilization percentages are only comparable between designs with similar structure.

The second is trusting pre-route timing. Synthesis estimates wire delays from fanout and statistical models, and those estimates can be optimistic by a wide margin on long nets. Only the post-route timing report reflects the actual switch and wire delays, which is why a design that closes timing after synthesis can fail after place and route. The analysis that produces those numbers is covered in static timing analysis.

A third, subtler issue is that the fabric’s regularity hides resource heterogeneity. Dedicated blocks for memory, multiplication, and high-speed serial links are fixed in number and position, and a design that needs more of them than the part provides cannot substitute lookup tables at acceptable cost. The cell array is uniform only in the sense that its logic is; the device as a whole is a fixed budget of several distinct resources, each with its own placement constraints. Memory is the next of those to consider, in block RAM primitives and memory inference.