LUTs, Flip-Flops & Routing

Chapter 4 said that an FPGA's logic blocks compute with look-up tables. Here is the whole idea in one sentence: any Boolean function of \(k\) inputs is completely described by its truth table, which has \(2^k\) rows; so store the output column in a \(2^k\)-bit memory and use the inputs as the address. Reading the memory is evaluating the function.

A 6-input LUT therefore holds 64 bits, called its INIT value, and can be any one of\(2^{64} \approx 1.8\times10^{19}\) functions. An AND gate, a parity check, a 4-to-1 multiplexer and a random-looking function all cost the same: one LUT, one LUT delay. This is very different from the gates of Chapter 1, where a bigger expression meant more gates. Inside an FPGA, the question is never “how many gates?” but “how many inputs?”.

Since a LUT is just memory, we can model one in a few lines. The model below takes the 64-bit INIT value as a parameter (Verilog) or generic (VHDL) and returns the bit at the address formed by the six inputs. Next to it is a 4-to-1 multiplexer: four data inputs plus two select inputs make exactly six, so Vivado maps it to one LUT6.

// Behavioural model of a 6-input look-up table: a 64-bit memory
// (the INIT value) read at the address formed by the six inputs.
module lut6_model #(
    parameter [63:0] INIT = 64'h0000_0000_0000_0000
) (
    input  wire [5:0] i,      // i[5] is the most significant address bit
    output wire       o
);
    assign o = INIT[i];
endmodule

-- Behavioural model of a 6-input look-up table: a 64-bit memory
-- (the INIT value) read at the address formed by the six inputs.
library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;

entity lut6_model is
    generic (
        INIT : std_logic_vector(63 downto 0) := (others => '0')
    );
    port (
        i : in  std_logic_vector(5 downto 0);   -- i(5) is the most significant address bit
        o : out std_logic
    );
end entity;

architecture rtl of lut6_model is
begin
    o <= INIT(to_integer(unsigned(i)));
end architecture;

// A 4-to-1 multiplexer: 4 data + 2 select = 6 inputs, one output.
// Any function of six inputs fits in ONE LUT6, so this is one LUT.
module mux4 (
    input  wire [3:0] d,
    input  wire [1:0] s,
    output wire       y
);
    assign y = d[s];
endmodule

-- A 4-to-1 multiplexer: 4 data + 2 select = 6 inputs, one output.
-- Any function of six inputs fits in ONE LUT6, so this is one LUT.
library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;

entity mux4 is
    port (
        d : in  std_logic_vector(3 downto 0);
        s : in  std_logic_vector(1 downto 0);
        y : out std_logic
    );
end entity;

architecture rtl of mux4 is
begin
    y <= d(to_integer(unsigned(s)));
end architecture;

What INIT value turns the LUT into mux4? Order the inputs as address bits i[3:0] = d, i[5:4] = s. When s = 0 the output follows d[0]= address bit 0, which is 1 on every odd address: the pattern …1010, i.e. AAAA in the lowest 16 bits. Doing the same for s = 1, 2, 3 gives CCCC, F0F0 andFF00. The testbench programs lut6_model with 64'hFF00_F0F0_CCCC_AAAA and checks it against mux4 for all 64 inputs.

`timescale 1ns / 1ps
// Program a LUT model with the mux4 truth table and compare it with mux4
// for all 64 input combinations.
module lut6_tb;
    reg  [5:0] i;
    wire       y_mux, y_lut;
    integer    n, errors;

    mux4 ref_mux (.d(i[3:0]), .s(i[5:4]), .y(y_mux));
    lut6_model #(.INIT(64'hFF00_F0F0_CCCC_AAAA)) lut (.i(i), .o(y_lut));

    initial begin
        errors = 0;
        for (n = 0; n < 64; n = n + 1) begin
            i = n;
            #1;
            if (y_lut !== y_mux) errors = errors + 1;
        end
        if (errors == 0)
            $display("PASS: LUT6 with INIT=FF00F0F0CCCCAAAA equals mux4 on all 64 inputs");
        else
            $display("FAIL: %0d mismatches", errors);
        $finish;
    end
endmodule

-- Program a LUT model with the mux4 truth table and compare it with mux4
-- for all 64 input combinations.
library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;

entity lut6_tb is
end entity;

architecture sim of lut6_tb is
    signal i            : std_logic_vector(5 downto 0) := (others => '0');
    signal y_mux, y_lut : std_logic;
begin
    ref_mux : entity work.mux4
        port map (d => i(3 downto 0), s => i(5 downto 4), y => y_mux);
    lut : entity work.lut6_model
        generic map (INIT => x"FF00F0F0CCCCAAAA")
        port map (i => i, o => y_lut);

    stimulus : process
        variable errors : natural := 0;
    begin
        for n in 0 to 63 loop
            i <= std_logic_vector(to_unsigned(n, 6));
            wait for 1 ns;
            if y_lut /= y_mux then errors := errors + 1; end if;
        end loop;
        if errors = 0 then
            report "PASS: LUT6 with INIT=FF00F0F0CCCCAAAA equals mux4 on all 64 inputs";
        else
            report "FAIL: " & integer'image(errors) & " mismatches" severity error;
        end if;
        wait;
    end process;
end architecture;

Both simulators print PASS: LUT6 with INIT=FF00F0F0CCCCAAAA equals mux4 on all 64 inputs. If you open a synthesised design in Vivado and click on a LUT, its properties show exactly such an INIT string. (In real designs you never write INIT values by hand — synthesis computes them — but knowing what they mean demystifies the device.)

The Python program does what synthesis does for a single LUT: it evaluates a function on every input combination, packs the results into an INIT value, and verifies it. It then asks how many LUT6s an \(n\)-input function needs, comparing a “tree” function such as a wide AND (each LUT absorbs six signals and emits one, so\(\lceil (n-1)/5 \rceil\) LUTs) with the worst case of an arbitrary function, built by Shannon expansion\(f = x\,f_1 + \bar x\, f_0\) on one input at a time.

The orange curve grows like \(2^n/64\): an arbitrary function of 16 inputs needs about a thousand LUTs, because it really is a 64-Kbit table — the job of block RAM (Chapter 6). Luckily, real logic is rarely arbitrary; adders, comparators and AND trees grow slowly.

A 7-series LUT is built as two 5-input LUTs (32 bits each) sharing inputs I0–I4, plus a final 2:1 multiplexer controlled by I5. It has two outputs:

• O6 — the full 6-input function (the mux selects the upper or lower LUT5 using I5);
• O5 — the output of the lower LUT5 alone.

So a LUT6 can implement one function of six inputs, or two functions of up to five inputs each as long as they share the same (at most five) input signals; in that case I5 is tied high by the tools. Adders use this: one LUT produces both the propagate signal for the carry chain and a second signal from the same inputs. Vivado's utilization report counts “LUT as Logic” per physical LUT6, whether one or both outputs are used.

A LUT alone only does combinational logic. Xilinx groups LUTs with the other things every design needs into a slice. A 7-series slice contains:

• 4 LUT6 (named A, B, C, D), each fracturable as above;
• 8 storage elements: two per LUT. All eight can be D flip-flops; four of them can alternatively be latches. They share the slice's clock, clock enable and set/reset signals — which is why designs with many different enables or resets pack less densely;
• a CARRY4: a dedicated 4-bit carry chain, the fast ripple-carry logic of Chapter 2 in hard silicon, linked vertically to the slices above and below;
• wide multiplexers F7AMUX, F7BMUX and F8MUX, which combine LUT outputs into functions of 7 or 8 inputs (or 8:1 and 16:1 multiplexers) without spending more LUTs.

Two slices form a configurable logic block (CLB), the tile repeated across the chip. Slices come in two flavours. In a SLICEL (“logic”) the LUTs are only function generators. In a SLICEM (“memory”) the LUTs can also be written while the design is running:

• as distributed RAM: each LUT becomes a 64 × 1 bit RAM with a synchronous write and an asynchronous (combinational) read; the four LUTs of a slice combine into deeper or multi-port memories;
• as a shift register (SRL32): each LUT becomes a 32-stage shift register with a selectable tap, replacing up to 32 flip-flops.

About one slice in three is a SLICEM; every CLB contains either two SLICELs or one SLICEL and one SLICEM. The XC7Z020's 53,200 LUTs live in 13,300 slices (6,650 CLBs), with twice as many flip-flops: 106,400.

Recall the full adder from Chapter 2: \(s_i = a_i \oplus b_i \oplus c_i\) and\(c_{i+1} = a_i b_i + c_i(a_i \oplus b_i)\). Write \(p_i = a_i \oplus b_i\) (“propagate”). Then the carry can be computed with a multiplexer:

That is exactly how the CARRY4 is built: per bit, one dedicated multiplexer (MUXCY) for the carry and one XOR gate (XORCY) for the sum. The LUT only has to compute \(p_i\) (and pass \(a_i\) through), so an\(N\)-bit adder costs \(N\) LUTs and \(\lceil N/4 \rceil\) CARRY4s. Because the carry hops between dedicated cells instead of through general routing, it is very fast: a few tens of picoseconds per bit, so a 32-bit add easily runs well above the 125 MHz of the PYNQ-Z2.

// Registered 8-bit adder with carry out. Synthesis maps it to
// 8 LUTs (one per bit) + 2 CARRY4 blocks + 9 flip-flops.
module add8 (
    input  wire       clk,
    input  wire [7:0] a,
    input  wire [7:0] b,
    output reg  [8:0] sum = 9'd0     // sum[8] is the carry out
);
    always @(posedge clk) begin
        sum <= a + b;                // 9-bit result: widths extended
    end
endmodule

-- Registered 8-bit adder with carry out. Synthesis maps it to
-- 8 LUTs (one per bit) + 2 CARRY4 blocks + 9 flip-flops.
library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;

entity add8 is
    port (
        clk : in  std_logic;
        a   : in  std_logic_vector(7 downto 0);
        b   : in  std_logic_vector(7 downto 0);
        sum : out std_logic_vector(8 downto 0)   -- sum(8) is the carry out
    );
end entity;

architecture rtl of add8 is
begin
    process (clk)
    begin
        if rising_edge(clk) then
            -- resize to 9 bits first so the carry is kept
            sum <= std_logic_vector(resize(unsigned(a), 9) + resize(unsigned(b), 9));
        end if;
    end process;
end architecture;

Synthesis turns a + b into exactly that structure: eight LUTs computing\(a_i \oplus b_i\), two CARRY4 blocks in two vertically adjacent slices, and nine flip-flops for the registered sum and carry out. Notice the VHDL resize to 9 bits: in numeric_std the result of + has the width of the wider operand, so without it the carry would be thrown away. In Verilog the addition takes the width of the 9-bit destination. An exhaustive testbench checks all 65,536 sums in both languages.

`timescale 1ns / 1ps
module add8_tb;
    reg        clk = 1'b0;
    reg  [7:0] a = 8'd0, b = 8'd0;
    wire [8:0] sum;
    integer    n, errors;

    add8 dut (.clk(clk), .a(a), .b(b), .sum(sum));
    always #4 clk = ~clk;                     // 125 MHz

    initial begin
        errors = 0;
        for (n = 0; n < 65536; n = n + 1) begin
            @(negedge clk);
            {a, b} = n;
            @(posedge clk); #1;               // result is registered: one cycle later
            if (sum !== a + b) errors = errors + 1;
        end
        if (errors == 0)
            $display("PASS: all 65536 additions correct");
        else
            $display("FAIL: %0d errors", errors);
        $finish;
    end
endmodule

library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;

entity add8_tb is
end entity;

architecture sim of add8_tb is
    signal clk  : std_logic := '0';
    signal a, b : std_logic_vector(7 downto 0) := (others => '0');
    signal sum  : std_logic_vector(8 downto 0);
    signal done : boolean := false;
begin
    dut : entity work.add8 port map (clk => clk, a => a, b => b, sum => sum);
    clk <= not clk after 4 ns when not done;  -- 125 MHz

    stimulus : process
        variable errors : natural := 0;
    begin
        for n in 0 to 65535 loop
            wait until falling_edge(clk);
            a <= std_logic_vector(to_unsigned(n / 256, 8));
            b <= std_logic_vector(to_unsigned(n mod 256, 8));
            wait until rising_edge(clk);
            wait for 1 ns;                    -- result is registered: one cycle later
            if unsigned(sum) /= n / 256 + n mod 256 then errors := errors + 1; end if;
        end loop;
        if errors = 0 then
            report "PASS: all 65536 additions correct";
        else
            report "FAIL: " & integer'image(errors) & " errors" severity error;
        end if;
        done <= true;
        wait;
    end process;
end architecture;

A delay line — a value that must come out exactly \(N\) clock cycles after it went in — is common in signal processing and pipelines. Written naively, it is a chain of \(N\) flip-flops. But if the chain has no reset, Vivado can put up to 32 stages in one SLICEM LUT configured as an SRL (shift register LUT).

// A 16-cycle delay line. With no reset, synthesis packs the whole
// shift register into ONE LUT of a SLICEM used as an SRL (SRL16/SRL32),
// instead of 16 flip-flops.
module delay16 #(
    parameter DEPTH = 16
) (
    input  wire clk,
    input  wire ce,          // clock enable: shift only when high
    input  wire d,
    output wire q
);
    reg [DEPTH-1:0] sr = {DEPTH{1'b0}};

    always @(posedge clk) begin
        if (ce)
            sr <= {sr[DEPTH-2:0], d};
    end

    assign q = sr[DEPTH-1];
endmodule

-- A 16-cycle delay line. With no reset, synthesis packs the whole
-- shift register into ONE LUT of a SLICEM used as an SRL (SRL16/SRL32),
-- instead of 16 flip-flops.
library ieee;
use ieee.std_logic_1164.all;

entity delay16 is
    generic (
        DEPTH : positive := 16
    );
    port (
        clk : in  std_logic;
        ce  : in  std_logic;   -- clock enable: shift only when high
        d   : in  std_logic;
        q   : out std_logic
    );
end entity;

architecture rtl of delay16 is
    signal sr : std_logic_vector(DEPTH - 1 downto 0) := (others => '0');
begin
    process (clk)
    begin
        if rising_edge(clk) then
            if ce = '1' then
                sr <= sr(DEPTH - 2 downto 0) & d;
            end if;
        end if;
    end process;

    q <= sr(DEPTH - 1);
end architecture;

The testbench shifts a 100-bit pattern through and checks that q is d delayed by exactly 16 cycles (both languages: PASS: q equals d delayed by 16 cycles (84 bits checked)). Vivado typically implements this as one SRL16E/SRLC32E LUT; depending on settings it may keep the final stage in an ordinary flip-flop, because a flip-flop output is faster than an SRL output.

`timescale 1ns / 1ps
module delay16_tb;
    reg  clk = 1'b0, ce = 1'b1, d = 1'b0;
    wire q;
    reg  [99:0] pattern = 100'h9_A3F0_5C1E_7724_B0D9_8E61_35AC;
    integer n, errors;

    delay16 dut (.clk(clk), .ce(ce), .d(d), .q(q));
    always #4 clk = ~clk;

    initial begin
        errors = 0;
        for (n = 0; n < 100; n = n + 1) begin
            @(negedge clk);
            if (n >= 16 && q !== pattern[n-16]) errors = errors + 1;
            d = pattern[n];
        end
        if (errors == 0)
            $display("PASS: q equals d delayed by 16 cycles (84 bits checked)");
        else
            $display("FAIL: %0d errors", errors);
        $finish;
    end
endmodule

library ieee;
use ieee.std_logic_1164.all;

entity delay16_tb is
end entity;

architecture sim of delay16_tb is
    signal clk  : std_logic := '0';
    signal ce   : std_logic := '1';
    signal d, q : std_logic := '0';
    signal done : boolean := false;
    constant pattern : std_logic_vector(99 downto 0) := x"9A3F05C1E7724B0D98E6135AC";
begin
    dut : entity work.delay16 port map (clk => clk, ce => ce, d => d, q => q);
    clk <= not clk after 4 ns when not done;

    stimulus : process
        variable errors : natural := 0;
    begin
        for n in 0 to 99 loop
            wait until falling_edge(clk);
            if n >= 16 and q /= pattern(n - 16) then errors := errors + 1; end if;
            d <= pattern(n);
        end loop;
        if errors = 0 then
            report "PASS: q equals d delayed by 16 cycles (84 bits checked)";
        else
            report "FAIL: " & integer'image(errors) & " errors" severity error;
        end if;
        done <= true;
        wait;
    end process;
end architecture;

Between the CLBs runs the programmable interconnect. Next to every CLB sits a switch matrix: a dense block of multiplexers (controlled, like everything else, by configuration bits) that connects the CLB's inputs and outputs to wire segments of different lengths — short ones reaching the neighbouring tiles, medium ones spanning a few tiles, and long lines crossing large parts of the chip. A signal travelling from one LUT to another crosses one or more of these multiplexers and segments.

Each crossing adds delay, and wires have resistance and capacitance. In a modern FPGA a LUT costs on the order of a tenth of a nanosecond, while a single routing hop costs several times that. On typical paths routing accounts for half or more of the total delay. That changes how you think about speed:

• fewer LUT levels between flip-flops means fewer hops, so logic depth matters more than logic size;
• placement matters: the tools place connected logic close together, and a congested or very full device slows down;
• signals that fan out to hundreds of destinations (enables, resets) need long wires and often limit speed.

Chapter 15 measures all this with Vivado's timing reports, where every path is broken down into “logic” and “net” delay. Dedicated paths — carry chains, F7/F8 muxes, and the cascades inside DSP and block RAM columns (Chapter 6) — bypass the general routing and are much faster.

Signals enter and leave the chip through I/O blocks (IOBs) arranged in banks around the fabric. Each IOB contains an input buffer, an output driver with tri-state control, and programmable settings for the voltage standard (LVCMOS33, LVCMOS18, LVDS…), drive strength, slew rate and pull-up/pull-down resistors. All pins of one bank share a supply voltage, which is why the XDC files of Chapters 13 and 14 set IOSTANDARD LVCMOS33 on every PYNQ-Z2 pin: those banks are powered at 3.3 V on the board.

Next to each IOB is dedicated logic for fast interfaces: input and output registers (so the flip-flop sits right at the pin, for predictable timing), double-data-rate registers (IDDR/ODDR) that capture on both clock edges, programmable delay lines (IDELAY), and serialisers/deserialisers (ISERDES/OSERDES) that convert between a slow wide bus and a fast narrow one. Their use is beyond this course, but it is good to know they exist when you read a data sheet.

+-------------------------+------+
| Site Type               | Used |
+-------------------------+------+
| Slice LUTs              |    8 |
|   LUT as Logic          |    8 |
| Slice Registers         |    9 |
| CARRY4                  |    2 |
| Bonded IOB              |   26 |   <- 8 + 8 + 9 data pins + clk
+-------------------------+------+

Notice that the I/O count, not the logic, is what such a small design “uses up”. In real designs the inner signals stay inside the fabric, and only a handful of pins connect to LEDs, buttons and connectors.