Lookup tables and the FPGA fabric

An FPGA is a two-dimensional array of tiles: soft-logic clusters of K-input LUTs and flip-flops, columns of hard memory and multiply-accumulate blocks, an I/O ring and hard IP, all embedded in a programmable interconnect. Every programmable element is controlled by a configuration cell, almost always SRAM.¹ That buys post-fabrication flexibility at a measured cost against a standard-cell ASIC in the same node: roughly 20–35× the area, 3–4× the critical-path delay and about 10× the dynamic power, and the survey attributes the gap largely to the routing fabric.¹

The chapter follows the tile from the inside out:

• LUTs as $2^K$-bit masks behind a mux tree, and why K settled at 4–6.
• Logic blocks: basic logic elements, clusters, carry chains, and each vendor’s names for them.
• Island-style routing: segments, connection boxes and switch boxes, and why they dominate area and delay.
• Hard blocks: block RAM, DSP slices and hard IP, and how much of the ASIC gap they close.
• Configuration: SRAM, flash and antifuse, bitstream structure, partial reconfiguration.

Products appear only as case studies, from AMD, Altera, Lattice and Microchip documentation and from the open bitstream-documentation projects IceStorm, Trellis and X-Ray. How a design becomes a bitstream (mapping, packing, placement, routing, timing) is the next chapter, From hardware code to bitstream.

A K-LUT is a $2^K$-bit mask and a $2^K{:}1$ mux, built as a tree of $2^K - 1$ two-input muxes in K levels. Two properties make it the universal soft-logic element: any K-input function fits (there are $2^{2^K}$ of them), and the delay through the tree depends only on K and the input pin used, not on the function.¹

The LUT-size question is a classic architecture trade-off. Ahmed and Rose’s experiments, summarized in the Kuon–Tessier–Rose survey, swept K with a full synthesis, packing, placement and routing flow over 28 benchmarks. Area per block grows with $2^K$ bits and with the routing tracks K input pins demand, while the block count falls; the product has an interior minimum. Critical-path delay falls monotonically with diminishing returns, with significant gains up to $K = 6$ and cluster sizes of three to four.¹

Fracturable LUTs

Large LUTs waste bits on the many small functions in real netlists, so modern 6-input LUTs fracture. An AMD 7-series LUT is either one 6-input LUT or two 5-input LUTs with separate outputs and common inputs.⁴ Altera’s ALM has up to eight inputs shared by two combinational cells and a 64-bit LUT mask, so it can implement two independent 4-input functions, one 6-input function, and some 7-input functions.¹⁰ The bits that once fed one wide function can then feed two narrow ones, at the cost of extra input muxing.

LUT masks can also be written while the device runs. In SLICEM slices of the 7 series, about a third of the total, a LUT becomes 64 bits of distributed RAM or a 32-bit shift register.⁴ Every ECP5 slice can act as distributed RAM.¹⁹

The basic logic element (BLE) is a K-LUT, a D flip-flop and an output select; a cluster groups N BLEs behind a local crossbar with I external inputs.¹ Clustering grows the logic block quadratically (the crossbar) instead of exponentially (a bigger LUT), and shared inputs keep I well below $KN$, which Under the hood quantifies. The crossbar need not be full: one study removed at least half of the cluster-input-to-LUT connections and 50–75% of the feedback connections with no loss in delay or cluster count, about a 10% area saving, at the cost of a router that must search inside clusters.¹

Control signals are where clusters differ most. In iCE40 the clock, clock enable and set/reset are shared by all eight cells of a tile, as is the clock-polarity bit, while use of the flip-flop and its set/reset behavior are per cell; the cell’s configuration is 20 bits.¹⁵ Some families force these controls to be shared cluster-wide while others let each element select its own; sharing saves routing but means flip-flops with different enables or resets can’t share a block.¹

Carry logic in detail

With a dedicated chain, each adder bit uses a LUT plus a carry mux and an XOR, with the carry on a hard wire between neighbors. In the 7 series each bit has a carry mux (MUXCY) and a dedicated XOR, four bits per slice, and CO3 of one slice drives the carry-in of the next to form wider adders.⁵ iCE40’s carry unit computes the majority of two LUT inputs and the incoming carry, and the chain enters a tile from the tile below.¹⁵ Vendors have added carry-lookahead and carry-skip structures to shorten the ripple.¹ Because the chain runs up a column, a wide adder occupies a vertical run of slices.⁵

The detailed routing architecture is set by a handful of parameters: channel width W, the segment-length distribution (and its stagger), input and output connection-box flexibility $F_{c,\mathrm{in}}$ and $F_{c,\mathrm{out}}$, and switch-box flexibility $F_s$ and pattern.¹ Hierarchical routing, used by some older Altera families, gave way to flat island style because real designs’ wire-length distributions rarely match a fixed hierarchy and crossing a level costs a large, fixed delay.¹

Switch-box patterns

With $F_s = 3$, a disjoint switch box connects track k only to track k on the other sides, which splits the fabric into W disjoint domains. The Wilton switch box uses the same number of switches but rotates track numbers on turns, so a route can change domain; both were designed for length-1 wires. With longer segments, most designs make turns only at segment ends and connect mid-wire points sparsely, as in the Imran and “shifty” patterns.¹

Directional, single-driver wiring

Early fabrics had bidirectional wires driven through tri-state buffers or pass transistors from several places; Betz and Rose’s study, in that era, found 50–80% pass-transistor switches best.² Modern fabrics use directional single-driver wires: each segment is driven by one multiplexer at its start, which merges the switch box and output connection box into one routing driver block and gives area and delay gains.¹ Both open-documented Lattice fabrics show it: iCE40 routing consists of directional tristate buffers, and ECP5 general routing is unidirectional.¹⁵²⁰

Area, delay and power

Because routing dominates area and delay, routing-architecture choices dominate FPGA quality.² Leakage is a particular problem: after configuration most interconnect is unused, but it still leaks, and 60–70% of total FPGA power has been attributed to the interconnect.¹ Architecture research evaluates all this empirically, by routing benchmarks on candidate fabrics; Under the hood shows how.

Kuon et al. distinguish soft-fabric heterogeneity (flip-flops and carry logic in every logic block) from tile-based heterogeneity (distinct tiles of hard structures, usually in columns).¹ Block RAMs are typically aligned in vertical columns within the tile array, and hard blocks reach the routing much as logic tiles do. ECP5 shows it directly: special functions connect through common interconnect blocks, “effectively a logic tile with the slices removed.”¹⁹

Memory blocks

Block RAMs are synchronous, dual-ported, aspect-configurable and cascadable. The 7-series RAMB36E1 runs from 32K × 1 to 1K × 36, or 512 × 72 in simple dual-port mode, with optional FIFO logic and ECC.⁶ M20K runs from 16K × 1 to 512 × 40.¹¹ PolarFire’s 20 Kb LSRAM is 1,024 × 20 and supports ECC at 33-bit width; its 768-bit µSRAMs fill the small-memory niche that LUT RAM fills elsewhere.²³

DSP blocks

The multiplier width is a bet on the workload. The DSP48E1’s 25 × 18 multiplier with a 48-bit ALU and cascade paths targets fixed-point filters.⁷ Altera’s blocks fracture into several narrow multipliers (up to eight 9 × 9 or four 18 × 18) or combine into wide ones.¹² The same multiply-accumulate is the core of the systolic arrays in AI accelerators; on an FPGA, a design builds such an array from DSP blocks and routing.

Hard IP and the area bound

The Kuon–Rose numbers are optimistic for hard blocks: only blocks a benchmark used were counted. Real designs must accept the chip’s fixed ratio of logic to RAM to DSP. With every hard block on a Stratix II in use, the area gap could fall to about 4.7×, a lower bound.¹ Hard IP pushes the same logic further for interfaces that soft logic can’t reach at all at speed, such as multi-gigabit SerDes and PCIe.²³

In an SRAM FPGA, dedicated circuitry initializes every configuration cell at power-up and then writes the user-supplied configuration into them.¹ Because every cell sits next to the element it controls, the configuration address space mirrors the floor plan. Project X-Ray’s description of the 7 series makes it concrete: a 32-bit frame address selects a block type (logic and I/O, or block-RAM content), half, clock row, column and minor frame; each frame carries 101 32-bit words, 100 for the tiles in that column of a clock row and one for the horizontal clock row.²¹

Volatility, security and upsets

SRAM configuration is volatile, so an external memory must hold it, and the stream crossing the board can be intercepted; modern families encrypt it.¹ Flash configuration (a floating-gate switching transistor controlled by a smaller programming transistor) is non-volatile and instant-on, but needs a special process and has finite endurance: 500 programming cycles for one cited family.¹ Metal-to-metal antifuses occupy no silicon area and switch with 20–100 Ω, but need large programming transistors, can’t be fully tested before programming (one family quoted 90% programming yield), and trail CMOS nodes by generations.¹

SRAM configuration cells can also be flipped by radiation, changing the circuit itself. Routing bits cause nearly 80% of configuration soft errors, and an upset-aware router reduced the number of sensitive bits by 14%; triple modular redundancy is the brute-force fix.¹

Partial reconfiguration constraints

Frames are the fundamental unit of configuration, so a reconfigurable region is made of whole frames; the static logic outside it keeps running while the region is replaced.²¹⁸ AMD lists reduced device size, algorithm flexibility and in-field updates among the uses.⁸

Before FPGAs, programmability came from two-level logic. A fuse PROM with N address inputs implements any N-input function, but area grows exponentially; PLAs added programmable AND and OR planes; PALs kept the AND plane programmable and fixed the OR plane, feeding D-flip-flop macrocells.¹ The dates vary slightly by source: the survey gives 1977 for MMI’s PAL, the Computer History Museum 1978.¹²⁵ PAL-style devices route through a near-full crossbar, which grows as inputs times outputs; CPLDs contain that by grouping macrocells into blocks around a central matrix.²⁶

Wahlstrom’s 1967 proposal already had both logic and interconnect configured from a stream of bits in static memory, with storage in each cell; SRAM’s area per switch kept it uncommercial until transistor cost fell in the mid-1980s.¹ The survey and the Computer History Museum date Xilinx’s first architecture to 1984; the XC2064 shipped in 1985.¹²⁵²⁴ By the survey’s writing, the largest parts had about 330,000 equivalent logic blocks and around 1,100 I/Os, plus hard memory and arithmetic.¹ Hard IP has kept growing since, up to whole processor subsystems, a theme taken up in Where FPGAs win.

The fabric has 120 routing bits (one per crossing and one per switch-box track) against 48 LUT bits, so routing is 71% of the configuration even in this toy. Input pins are modeled as connection-box muxes (one track per pin), as in VPR; outputs may drive several tracks. Nets are found with union-find; a net with two drivers is a short. Try:

• Build the adder with three LUTs (P = A ⊕ B, Sum = P ⊕ Cin, Cout = majority). Where does the channel run out of tracks, and how does opening a switch box let two nets share one track?
• Implement Cout as A·B + P·Cin instead of majority. Count the tracks needed through LUT3’s row: does it still fit in five?
• Load your part-1 table into a fabric LUT (“From the LUT editor”) and watch the bitstream change.

Comparing logic capacity across vendors by LUT count is unreliable: a fracturable 6-input LUT, an ALM and a 4-input LUT hold different amounts of logic. Count what a design needs (LUTs at a given K, flip-flops, carry bits, RAM bits by block geometry, multipliers by width) and map it to each architecture. The interconnect share of power and the gap figures come from the survey’s summary of 90 nm-era studies.¹ The tiny fabric in the sim spends 71% of its configuration bits on routing, a toy with one-hot switches; real fabrics encode muxes, but routing still holds most of the bits.¹

• Granularity. Larger LUTs and clusters shorten critical paths with diminishing returns (significant up to K = 6 and N ≈ 3–4) while area per block grows exponentially in K and quadratically in N.¹
• Segmentation and drivers. Length 4–8 segments beat length 1 in delay and area; directional single-driver wiring beats bidirectional, and pairs with switch patterns designed for multi-length wires.²¹
• Heterogeneity. Hard blocks reduce area and (with both DSP and RAM) power, but barely reduce delay, and their fixed ratio is a bet on the workload mix; the full-use bound of 4.7× is far from typical.¹
• Programming technology. SRAM tracks CMOS scaling but is volatile, large and upset-prone; flash and antifuse fix volatility and (for antifuse) security and switch resistance, at the cost of process and reprogrammability.¹
• Leakage. Most interconnect is idle after configuration but still leaks, so the routing that buys flexibility also sets a large part of static power.¹

How these costs compare with building an ASIC, and when the flexibility is worth them, is the subject of Where FPGAs win.

1. The LUT as a mux tree

A K-input LUT with mask $m \in \{0,1\}^{2^K}$ computes

built from $2^K - 1$ two-input multiplexers in K levels. In the sim, bit i is the output for inputs reading i in binary. Two counts drive the architecture: storage $2^K$ bits, and the number of distinct functions $2^{2^K}$. The tree’s delay is K pass-transistor stages plus buffering regardless of the function, which is why the mapper, not the LUT, decides how fast logic is: it chooses how many LUT levels sit on the critical path.¹

2. Sizing a cluster

For a cluster of N basic logic elements with K-input LUTs, the number of external inputs needed to use nearly all of them is not KN, because signals are shared. Betz and Rose found $I = 2N + 2$ for 4-input LUTs; Ahmed and Rose generalized it to

¹ For $K = 6$, $N = 10$, $I = 33$ rather than 60. That matters because every external input needs an input connection-box mux over a fraction $F_c$ of the channel’s W tracks, and every LUT input needs a local-crossbar mux over the $I + N$ signals inside the cluster.

A rough per-tile count of configuration bits makes the routing share concrete. With encoded muxes:

With illustrative values $K = 6$, $N = 10$, $I = 33$, $W = 200$ and $F_c = 0.15$: $B_{\mathrm{LUT}} = 640$, $B_{\mathrm{xbar}} = 60 \times 6 = 360$, and $B_{\mathrm{cb}} = 33 \times 5 = 165$, before any switch-box or wire-driver bits. Even counted compactly, the routing around a cluster needs about as many bits as its LUTs, and the switch boxes add more; that is the survey’s observation that most SRAM cells set routing mux selects.¹

3. Describing and evaluating a routing architecture

Architecture research is empirical: map benchmarks to the candidate fabric, place and route them, and measure area and delay with transistor-level models. VPR made that practical. Its architecture file describes logic-block pins, their sides and equivalences, the switch-box style and the Fc values; VPR turns the description into a routing-resource graph in which every track and pin is a node and every allowed switch an edge.³ A standard figure of merit for routing is the minimum number of tracks per channel at which a set of benchmarks routes.³ A simplified description in the style of today’s VPR format:

<architecture>
  <complexblocklist>
    <pb_type name="clb">
      <input  name="I" num_pins="33" equivalent="full"/>
      <output name="O" num_pins="10"/>
      <clock  name="clk" num_pins="1"/>
      <pb_type name="ble" num_pb="10">
        <pb_type name="lut6" blif_model=".names" num_pb="1"/>
        <pb_type name="ff"   blif_model=".latch" num_pb="1"/>
      </pb_type>
      <interconnect> <complete input="clb.I ble.out" output="ble.in"/> </interconnect>
      <fc in_type="frac" in_val="0.15" out_type="frac" out_val="0.10"/>
    </pb_type>
  </complexblocklist>
  <device> <switch_block type="wilton" fs="3"/> </device>
  <segmentlist>
    <segment freq="1.0" length="4" type="unidir"/>
  </segmentlist>
</architecture>

The tool flow that VPR represents (packing, simulated-annealing placement, negotiated-congestion routing) is covered in From hardware code to bitstream and, for ASICs, in Routing.

4. From routing choices to bits

Once routed, every resource decision becomes configuration: LUT masks, mux select codes on every wire driver and pin, flip-flop and carry modes, hard-block options. The bitstream is those bits arranged in the device’s configuration address space plus the commands to write it. In iCE40 the address space is a set of banks of configuration RAM and block RAM, written by commands that set a bank’s width, height and offset before streaming data, and closed with a CRC check.¹⁸

preamble
set bank width     (opcode 6)   # 16-bit value
set bank height    (opcode 7)
set bank offset    (opcode 8)
set bank number    (opcode 1)
write CRAM data    (opcode 0)   # width*height/8 bytes of configuration cells
... repeat for each CRAM bank ...
write BRAM data    (opcode 0)   # initial block-RAM contents
CRC check          (opcode 2)
wakeup

AMD’s 7-series stream is organized around frames instead: a 32-bit frame address (block type, half, clock row, column, minor index) and 101 words per frame: 100 for the 50 tiles of a column within a clock row and one for the horizontal clock row.²¹ Project X-Ray reconstructed this mapping black-box: scripts it calls fuzzers ask the vendor tools for large numbers of designs, and the resulting bitstreams are cross-correlated to discover what each bit does.²²

5. Configuration reliability

Because SRAM configuration cells define the circuit, a radiation-induced bit flip changes the hardware, not just a value. Routing bits account for nearly 80% of such configuration soft errors. One defensive router counted the sensitive configuration bits of each route alongside delay and cut them by 14%; triple modular redundancy masks errors at about three times the logic.¹ User flip-flops, which aren’t minimum-size, are less vulnerable than configuration cells, while block-RAM bits are vulnerable and can be protected with error correction.¹

Every architectural parameter here becomes a constraint there. K and fracturability set what technology mapping targets; cluster inputs, shared control sets and carry chains set packing; segment lengths, Fc and Fs shape the routing-resource graph the router searches; and frames and partial regions shape what a bitstream generator writes. From hardware code to bitstream covers those tools, including the open flow built on the documentation projects above, and Where FPGAs win weighs the FPGA–ASIC gap against non-recurring cost.