Inside an FPGA

A processor designed from scratch is made as a chip of its own, which takes months and costs a fortune per design. An FPGA (field-programmable gate array) is a chip that becomes whatever circuit it’s told to be: a grid of small, identical logic blocks, with wires and switches between them, all set by a memory full of configuration bits. Change the bits and it’s a different circuit. The first, Xilinx’s XC2064 of 1985, had 64 logic blocks; the iCE40 UP5K these pages use has 5,280.

1 · The look-up table

The heart of an FPGA’s logic is the look-up table (LUT) from Synthesis: 16 stored bits, and a tree of multiplexers that the four inputs steer to one of them. Whatever the 16 bits are, that’s the truth table it computes.

One logic cell. Click the stored bits to change them, or fill them from the menu; click the inputs I0 to I3 at the bottom, and the multiplexers carry the bit they pick (highlighted) to the output. Each pattern of the inputs is a row of the truth table, so the 16 bits are the truth table. Tick use the flip-flop and the output comes from a flip-flop instead, which takes the LUT’s value at each Clock: one more configuration bit, and the cell is clocked logic.

That’s how 7 LUTs could hold the 7-segment decoder: one truth table each.

2 · The logic cell and the carry chain

The iCE40’s logic cell is exactly that: a 4-input LUT, a flip-flop, and a configuration bit choosing between them. Eight logic cells make a logic block, and the blocks fill most of the chip.

Each cell also has a little carry logic: the full adder’s carry, built in, with a dedicated wire up to the cell above. An adder then uses one cell per column, the LUT making the sum and the carry logic passing the carry straight up the chain, without going through the general wiring. That’s the ripple-carry adder again, with its slow part made as fast as it can be.

3 · Memories and multipliers

Some things are wasteful to build from LUTs, so FPGAs have them ready-made among the logic:

Block RAM: the UP5K has 30 blocks of 4 kilobits each, 120 kilobits in all.
Single-port RAM: four larger blocks, 1 megabit in all (128 KB): room for a 6502’s whole memory.
DSP blocks: eight multiply-and-add units, each multiplying two 16-bit numbers, for signal processing.

4 · Routing: the wires and switches

Between the logic blocks run wires: short ones to the neighbours, longer ones across the chip. Where wires cross, there are switches, each a transistor working as a switch, turned on or off by a configuration bit. A route through the chip is a chain of switches left on. On most FPGAs, the wiring and its switches take up much of the chip’s area.

Fitting a design onto all that is two jobs. Placement decides which logic cell does which part of the design; routing then finds, for every wire in the design, a path through the switches, with no two signals sharing a wire.

A toy FPGA: a grid of logic cells, each tile holding one (L is a LUT, F a flip-flop), with the design’s inputs and outputs on pins round the edge. The design comes from Yosys, as on the synthesis page. It starts scattered at random, with straight lines for the wires it needs. Click Place to watch simulated annealing tidy it up, then Route: thicker wires carry more signals. The adder’s cells stand in one column, as their carry chain must. The ALU, with far more wires, can’t be routed with 3 wires per edge: the router gives up with edges overused (red). Give it 5. (The counter’s clk pin has no wire here: a real FPGA sends its clocks on a network of their own, which reaches every flip-flop at once.)

Simulated annealing is named after the way metal is annealed: heated, then cooled slowly, so its atoms settle into an orderly state. The placer moves cells at random, always keeping moves that shorten the wiring and, while it’s still “hot”, keeping some that lengthen it too, so it doesn’t get stuck. As it cools, it accepts fewer and fewer bad moves. It was the standard way to place FPGA designs for decades, made so by VPR, the University of Toronto’s research tool from 1997.

The router here is PathFinder, from 1995, which is still the basis of FPGA routers: route every signal by its shortest path, even if wires end up shared; then make the shared wires dearer and route everything again, until no wire carries two signals.

5 · Timing

Every LUT and every switch takes time, so the longest path from one flip-flop to the next sets how fast the clock can go, as on Clocked circuits. The real tools work it out from the delays of every part. nextpnr, the open-source placer and router for the iCE40, reports for these designs on the UP5K:

Design	Logic cells (of 5,280)	Fastest clock
The 7-segment decoder	8	(no clock)
The 8-bit adder	12	(no clock)
The counter	18	95 MHz
The ALU	93	(no clock)

6 · The bitstream

All those configuration bits together are the bitstream: every LUT’s contents, every flip-flop’s settings, every switch. On the iCE40 they’re held in RAM on the chip, which forgets them when the power goes off, so at power-up the FPGA reads them from a flash memory chip beside it (or a computer sends them).

For the UP5K, the bitstream is 104,090 bytes, about 833,000 bits, whatever the design. A counter and a whole CPU give bitstreams of exactly the same size, because the bitstream sets every part of the chip, used or not; an unused LUT just holds zeros.

Summary

An FPGA is a grid of logic, memories and wires whose function is set by configuration bits.
A LUT is 16 stored bits and a multiplexer tree: any truth table of 4 inputs. With a flip-flop and carry logic, it’s a logic cell.
Placement puts the design’s cells on the chip (here by simulated annealing); routing finds every wire a path through the switches (here by PathFinder). Wiring is often what runs out first.
The longest path sets the fastest clock.
The bitstream holds every configuration bit, and is the same size for every design.