Pipelines, latency and dependency chains

The chain1 and chain16 loops on this page run the same 98,304 floating-point additions, yet on an Apple M5 Pro chain16 finishes about eight and a half times faster. Nothing was removed: chain1 adds into one register, so each addition waits for the one before, while chain16 adds into sixteen, so the core runs several at once.

A modern core is a pipelinepipeline: The division of instruction handling into stages so that a core works on several instructions at once, each in a different stage, finishing about one a cycle when nothing stalls. with more than one adder, and it reorders work to keep them busy. When each instruction needs the previous result, that machinery sits idle and the code runs one addition at a time. When the work is independent, the same core finishes several additions a cycle. Here you measure the gap, name the two numbers behind it, latencylatency: The time from when an instruction starts to when its result is ready for another instruction to use, usually counted in clock cycles. and throughputthroughput: How many instructions of a kind a core can finish each clock cycle when their inputs are ready, set by how many execution units it has for them., and break a chain with several accumulatorsaccumulator: A register a loop adds into each pass to build a running total; several independent accumulators let a core add in parallel instead of in one chain..

A dependency chain runs at the speed of one step

chains.s writes eight loops that each do 48 additions of 1.0 a pass, spread over a different number of accumulators: chain1 uses one register, chain2 two, up to chain16. An assembler macro writes the bodies, so the only thing that changes between them is how many independent running totals there are:

// chains.s (AArch64, macOS): the same 48 floating-point additions a pass, spread over 1 to 16 accumulators.
// double chainK(long passes) adds 1.0 to its K accumulators 48 times a pass and returns their total.
        .text

// CHAIN name, rounds, registers: a function whose loop runs `rounds` rounds of one fadd into each listed register.
// CHAIN _chain3, 16, 16, 17, 18 makes a loop of 16 x 3 = 48 fadds: d16, d17, d18, d16, d17, d18, ...
        .macro  CHAIN name, rounds, regs:vararg
        .p2align 4
        .globl  \name
\name:
        fmov    d1, #1.0                // the value every fadd adds
        .irp    r, \regs
        movi    d\r, #0                 // each accumulator starts at 0.0
        .endr
1:
        .rept   \rounds
        .irp    r, \regs
        fadd    d\r, d\r, d1            // reads the accumulator the previous round wrote
        .endr
        .endr
        subs    x0, x0, #1
        b.ne    1b
        movi    d0, #0                  // after the loop: add the accumulators together, once
        .irp    r, \regs
        fadd    d0, d0, d\r
        .endr
        ret
        .endm

        CHAIN   _chain1, 48, 16
        CHAIN   _chain2, 24, 16, 17
        CHAIN   _chain3, 16, 16, 17, 18
        CHAIN   _chain4, 12, 16, 17, 18, 19
        CHAIN   _chain6, 8, 16, 17, 18, 19, 20, 21
        CHAIN   _chain8, 6, 16, 17, 18, 19, 20, 21, 22, 23
        CHAIN   _chain12, 4, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27
        CHAIN   _chain16, 3, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31

// long adds(long passes), the ruler: 48 integer adds a pass, each waiting for the one before.
        .p2align 4
        .globl  _adds
_adds:
        mov     x1, #0
1:
        .rept   48
        add     x1, x1, #1
        .endr
        subs    x0, x0, #1
        b.ne    1b
        mov     x0, x1
        ret

chain1 is a dependency chaindependency chain: A run of instructions each of which uses the result of the one before, so they cannot overlap and the run takes the sum of their latencies.: every fadd d16, d16, d1 reads d16 and writes d16, so the next one cannot begin until this one’s result is ready. The core has more than one floating-point adder, but chain1 never gives it a second, independent addition to start, so the adders stand idle between steps. Step through one pass of chain1 beside one pass of chain4 and watch which additions can run together:

The driver times every loop, fastest call of 1,001, and prints a ruler: it also times a chain of dependent integer adds, one per cycle, to turn nanoseconds into cycles and find the clock. It checks that each loop added correctly before trusting its timing:

import pathlib
import sys

sys.path.insert(0, str(pathlib.Path(__file__).parent / "sessions"))
import session

session.run("""
# The processor and the system the timings come from
/usr/sbin/sysctl -n machdep.cpu.brand_string
sw_vers -productName
# Assemble the loops, compile the timer, and look at the start of chain3's loop as the assembler wrote it
clang -O2 -o chains chains_main.c chains.s
llvm-objdump -d --no-show-raw-insn --no-leading-addr --disassemble-symbols=_chain3 chains | sed -n '6,14p' | sed 's/^[[:space:]]*//'
./chains
""")

# The processor and the system the timings come from
$ /usr/sbin/sysctl -n machdep.cpu.brand_string
Apple M5 Pro
$ sw_vers -productName
macOS
# Assemble the loops, compile the timer, and look at the start of chain3's loop as the assembler wrote it
$ clang -O2 -o chains chains_main.c chains.s
$ llvm-objdump -d --no-show-raw-insn --no-leading-addr --disassemble-symbols=_chain3 chains | sed -n '6,14p' | sed 's/^[[:space:]]*//'
<_chain3>:
fmov	d1, #1.00000000
movi	d16, #0000000000000000
movi	d17, #0000000000000000
movi	d18, #0000000000000000
fadd	d16, d16, d1
fadd	d17, d17, d1
fadd	d18, d18, d1
fadd	d16, d16, d1
$ ./chains
98304 additions a call, fastest of 1001 calls
ruler: one dependent add took 0.2306 ns, one cycle at 4.34 GHz
chains  ns/fadd  cycles/fadd  cycles a step  speed-up
     1   0.4849         2.10           2.10     1.00x
     2   0.2424         1.05           2.10     2.00x
     3   0.1734         0.75           2.26     2.80x
     4   0.1305         0.57           2.26     3.71x
     6   0.1043         0.45           2.71     4.65x
     8   0.0860         0.37           2.99     5.64x
    12   0.0627         0.27           3.26     7.73x
    16   0.0572         0.25           3.97     8.47x
every call added correctly: yes

In the run above chain1 takes about 2.1 cycles a step: with nothing to overlap, each step costs the time for one fadd to produce its result. That is why a dependency chain is the slowest way to do the work. The core’s extra adders are there; the code just never asks them to run anything.

Independent work runs at the same time

Read down the speed-up column of the same run. chain2 is twice as fast as chain1, chain3 nearly three times and chain4 nearly four, while the cycles a step column stays a little over two: each chain still waits for its own last result, and the others run beside it. The additions are the same; only their independence changed. An out-of-orderout-of-order execution: A core starting any instruction whose inputs are ready rather than in strict program order, so independent work proceeds while a slow result is awaited. core looks past program order for instructions whose inputs are ready and starts them on any idle adder. chain4 writes four different registers each pass, so four additions have their inputs ready at once and the core keeps four in flight. That overlap is instruction-level parallelisminstruction-level parallelism: Running several independent instructions at the same time within one core, so work that does not depend on earlier results need not wait for it..

Past four chains the gain slows, because the core can start only so many additions a cycle. The cycles a step column shows it: from six chains on it climbs above the latency, to 4.0 at sixteen, because each chain now waits for a free adder as well as for its own result. chain16 does a fadd every 0.25 cycles: the loop has gone from waiting on latency to waiting on adders.

Latency and throughput are different numbers

The run measured two different things. One chain measured latency: the cycles from an addition’s start until its result can feed the next one, about 2.1 cycles for fadd here. Sixteen chains measured throughput: how many additions the core finishes each cycle when their inputs are ready, about four. A single fadd in isolation and a loop full of independent fadds run at speeds that differ by more than eight times, and both are correct answers to “how fast is fadd”.

The ceiling on the speed-up follows from the two numbers: one chain does one fadd every 2.1 cycles and the core can do four a cycle, so the most independence can buy is 2.1 × 4, about eight and a half, which is what sixteen chains reached. The same arithmetic says about eight additions in flight should fill four adders, yet chain8 reached only 5.6×: a real core does not overlap independent work perfectly, so the measured table, not the arithmetic alone, says how many accumulators pay.

Several accumulators break the chain

Most real chains are not written by hand; they hide in a reduction, a loop that folds an array into one value. sum.c is the plain shape, one running total carried from element to element:

// sum.c: the loop every reduction starts as. One accumulator, s, carries the whole sum from element to element.
double sum(const double *a, long n) {
    double s = 0.0;
    for (long i = 0; i < n; i++)
        s += a[i];
    return s;
}

That single s is a dependency chain exactly like chain1. Splitting it into several independent totals and adding them once at the end breaks the chain, and it is the same transformation the compiler can do for you. But it may not always: regrouping a sum is reassociationreassociation: Regrouping the operations of a sum or product, such as (a+b)+(c+d) for a+b+c+d; safe for integers but able to change the rounding of floating-point values., and reassociating floating-point numbers can change the rounding. The session compiles sum.c three ways and then runs the two double builds on the same 65,536 values:

import pathlib
import sys

sys.path.insert(0, str(pathlib.Path(__file__).parent / "sessions"))
import session

session.run("""
# The loop of sum.c at -O2: Clang may not reorder floating-point additions, so one chain carries the sum
clang -O2 -S -o strict.s sum.c
awk '/Inner Loop Header/ { f = 1; next } f { print } f && /b[.]ne/ { exit }' strict.s
# -ffast-math allows reassociation: the loop gets accumulators
clang -O2 -ffast-math -S -o fast.s sum.c
awk '/Inner Loop Header/ { f = 1; next } f { print } f && /b[.]ne/ { exit }' fast.s
# Integer addition can be regrouped freely, so the same loop over long gets accumulators at plain -O2
clang -O2 -S -o isum.s isum.c
awk '/Inner Loop Header/ { f = 1; next } f { print } f && /b[.]ne/ { exit }' isum.s
# Both double builds of sum.c, linked with the same sum_main.c and run on Apple silicon on the same numbers
clang -O2 -c -o sum_strict.o sum.c
clang -O2 -ffast-math -c -o sum_fast.o sum.c
clang -O2 -o strict sum_main.c sum_strict.o
clang -O2 -o fast sum_main.c sum_fast.o
./strict
./fast
""")

# The loop of sum.c at -O2: Clang may not reorder floating-point additions, so one chain carries the sum
$ clang -O2 -S -o strict.s sum.c
$ awk '/Inner Loop Header/ { f = 1; next } f { print } f && /b[.]ne/ { exit }' strict.s
	ldp	q1, q2, [x9, #-32]
	mov	d3, v1[1]
	mov	d4, v2[1]
	ldp	q5, q6, [x9], #64
	mov	d7, v5[1]
	mov	d16, v6[1]
	fadd	d0, d0, d1
	fadd	d0, d0, d3
	fadd	d0, d0, d2
	fadd	d0, d0, d4
	fadd	d0, d0, d5
	fadd	d0, d0, d7
	fadd	d0, d0, d6
	fadd	d0, d0, d16
	subs	x10, x10, #8
	b.ne	LBB0_5
# -ffast-math allows reassociation: the loop gets accumulators
$ clang -O2 -ffast-math -S -o fast.s sum.c
$ awk '/Inner Loop Header/ { f = 1; next } f { print } f && /b[.]ne/ { exit }' fast.s
	ldp	q4, q5, [x9, #-32]
	ldp	q6, q7, [x9], #64
	fadd.2d	v0, v4, v0
	fadd.2d	v1, v5, v1
	fadd.2d	v2, v6, v2
	fadd.2d	v3, v7, v3
	subs	x10, x10, #8
	b.ne	LBB0_5
# Integer addition can be regrouped freely, so the same loop over long gets accumulators at plain -O2
$ clang -O2 -S -o isum.s isum.c
$ awk '/Inner Loop Header/ { f = 1; next } f { print } f && /b[.]ne/ { exit }' isum.s
	ldp	q4, q5, [x8, #-32]
	ldp	q6, q7, [x8], #64
	add.2d	v0, v4, v0
	add.2d	v1, v5, v1
	add.2d	v2, v6, v2
	add.2d	v3, v7, v3
	subs	x10, x10, #8
	b.ne	LBB0_5
# Both double builds of sum.c, linked with the same sum_main.c and run on Apple silicon on the same numbers
$ clang -O2 -c -o sum_strict.o sum.c
$ clang -O2 -ffast-math -c -o sum_fast.o sum.c
$ clang -O2 -o strict sum_main.c sum_strict.o
$ clang -O2 -o fast sum_main.c sum_fast.o
$ ./strict
total 11.667578183235785, fastest call 0.498 ns a value
$ ./fast
total 11.667578183235779, fastest call 0.072 ns a value

At plain -O2 the double loop keeps one chain: Clang may not change the order of floating-point additions, because (a + b) + c and a + (b + c) can round differently, and its 0.50 ns a value is close to the 0.48 ns a fadd of chain1. With -ffast-math it is allowed to reorder, and the loop gains four vector accumulators (fadd.2d v0, v4, v0 and three more, each adding two doubles at once), so eight running totals overlap and the loop runs about seven times faster, for the same reason chain8 beat chain1. The integer version gets accumulators at plain -O2 with no flag, because two’s-complement addition is associative: regrouping it never changes the result.

The price is in the last digit. The strict build printed 11.667578183235785 and the fast build 11.667578183235779: the same 65,536 numbers added in a different order, rounded a little differently. Neither is wrong.

A model estimates the cost without running

The same reasoning holds on x86-64 and RISC-V, but timing their code takes their processors, and Apple silicon runs neither natively. llvm-mca fills the gap: it reads a block of machine code and a scheduling modelscheduling model: A compiler's table of each instruction's latency and how many can issue per cycle on one named processor, used to estimate how fast a block of code runs. of one named core, then reports the cycles, deterministically and without running anything. The session analyses the one-, three- and six-chain loops on AMD’s Zen 4 model and on SiFive’s P670 model, 24 additions a pass:

import pathlib
import sys

sys.path.insert(0, str(pathlib.Path(__file__).parent / "sessions"))
import session

session.run("""
# llvm-mca runs each loop 100 times through LLVM's scheduling model of one processor and counts the cycles
llvm-mca --version | head -2
# x86-64: the model of AMD's Zen 4 cores (znver4); the instruction table shows addsd's latency and cost
llvm-mca -mtriple=x86_64-linux-gnu -mcpu=znver4 -iterations=100 chains_x86.s | grep -E '^\\[[0-9]\\] Code Region|^Total Cycles|^Block RThroughput'
llvm-mca -mtriple=x86_64-linux-gnu -mcpu=znver4 -iterations=100 chains_x86.s | grep -m1 -E '^ 1 .*addsd'
# RISC-V: the model of SiFive's P670 core
llvm-mca -mtriple=riscv64-linux-gnu -mcpu=sifive-p670 -iterations=100 chains_riscv.s | grep -E '^\\[[0-9]\\] Code Region|^Total Cycles|^Block RThroughput'
llvm-mca -mtriple=riscv64-linux-gnu -mcpu=sifive-p670 -iterations=100 chains_riscv.s | grep -m1 -E '^ 1 .*fadd[.]d'
""")

# llvm-mca runs each loop 100 times through LLVM's scheduling model of one processor and counts the cycles
$ llvm-mca --version | head -2
Homebrew LLVM version 23.1.2
  Optimized build.
# x86-64: the model of AMD's Zen 4 cores (znver4); the instruction table shows addsd's latency and cost
$ llvm-mca -mtriple=x86_64-linux-gnu -mcpu=znver4 -iterations=100 chains_x86.s | grep -E '^\[[0-9]\] Code Region|^Total Cycles|^Block RThroughput'
[0] Code Region - one-chain
Total Cycles:      7203
Block RThroughput: 12.0
[1] Code Region - three-chains
Total Cycles:      2404
Block RThroughput: 12.0
[2] Code Region - six-chains
Total Cycles:      1205
Block RThroughput: 12.0
$ llvm-mca -mtriple=x86_64-linux-gnu -mcpu=znver4 -iterations=100 chains_x86.s | grep -m1 -E '^ 1 .*addsd'
 1      3     0.50                        addsd	xmm0, xmm15
# RISC-V: the model of SiFive's P670 core
$ llvm-mca -mtriple=riscv64-linux-gnu -mcpu=sifive-p670 -iterations=100 chains_riscv.s | grep -E '^\[[0-9]\] Code Region|^Total Cycles|^Block RThroughput'
[0] Code Region - one-chain
Total Cycles:      4803
Block RThroughput: 12.0
[1] Code Region - three-chains
Total Cycles:      1604
Block RThroughput: 12.0
[2] Code Region - six-chains
Total Cycles:      1204
Block RThroughput: 12.0
$ llvm-mca -mtriple=riscv64-linux-gnu -mcpu=sifive-p670 -iterations=100 chains_riscv.s | grep -m1 -E '^ 1 .*fadd[.]d'
 1      2     0.50                        fadd.d	ft0, ft0, ft11

Read the instruction table first. On Zen 4 addsd has a latency of 3 cycles and a reciprocal throughput, the RThroughput column, of 0.50 cycles, meaning two can start each cycle. The one-chain region takes 7,203 cycles for 100 passes, about 3 cycles an addsd: the latency, because one chain cannot overlap. Three chains take 2,404, about 1 cycle each, and six chains 1,205, about 0.50, the throughput ceiling that Block RThroughput: 12.0 predicted for the 24-instruction block. The SiFive P670 model gives fadd.d a latency of 2, so its one-chain region is 4,803 cycles and its six-chain region reaches the same 0.50. Different cores, the same story: a chain runs at the latency, and enough independent chains reach the throughput.

A model is not a measurement. llvm-mca’s own documentation notes that it models the core’s scheduler, not the branch predictor or the memory system, and treats every load as a cache hit. A loop whose data does not fit in cache runs at the speed memory can deliver it, far below the model’s estimate, so measure on your own data before you count on a number.

Practise

Work on copies of chains.s and sum.c, above, and of the two drivers that time them; the text diff tool lines up two listings side by side.

// chains_main.c: times chain1 ... chain16 on the same work, with the integer add chain as a ruler.
// Every call does 2,048 passes of 48 additions. Each loop is called 1,001 times, all of them taking turns,
// and the fastest call counts: a slower call measured something else running on the machine too.
#include <pthread/qos.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

double chain1(long), chain2(long), chain3(long), chain4(long), chain6(long), chain8(long), chain12(long), chain16(long);
long adds(long);

enum { CALLS = 1001, PASSES = 2048, PER_PASS = 48, LOOPS = 8 };

static uint64_t now(void) { return clock_gettime_nsec_np(CLOCK_UPTIME_RAW); }

static int by_value(const void *a, const void *b) {
    uint64_t x = *(const uint64_t *)a, y = *(const uint64_t *)b;
    return (x > y) - (x < y);
}

int main(void) {
    // The highest quality-of-service class asks macOS for a performance core.
    pthread_set_qos_class_self_np(QOS_CLASS_USER_INTERACTIVE, 0);
    double (*loop[LOOPS])(long) = {chain1, chain2, chain3, chain4, chain6, chain8, chain12, chain16};
    const int chains[LOOPS] = {1, 2, 3, 4, 6, 8, 12, 16};
    static uint64_t t[LOOPS + 1][CALLS];       // the last row times the ruler
    const double work = (double)PASSES * PER_PASS;
    int right = 1;
    for (int c = 0; c < CALLS; c++) {
        uint64_t t0 = now();
        long sum = adds(PASSES);
        t[LOOPS][c] = now() - t0;
        if (sum != (long)work) right = 0;
        for (int i = 0; i < LOOPS; i++) {
            t0 = now();
            double total = loop[i](PASSES);
            t[i][c] = now() - t0;
            if (total != work) right = 0;
        }
    }
    for (int i = 0; i <= LOOPS; i++) qsort(t[i], CALLS, sizeof t[i][0], by_value);
    double cycle = t[LOOPS][0] / work;         // ns for one dependent integer add: one cycle
    printf("%.0f additions a call, fastest of %d calls\n", work, CALLS);
    printf("ruler: one dependent add took %.4f ns, one cycle at %.2f GHz\n", cycle, 1 / cycle);
    printf("chains  ns/fadd  cycles/fadd  cycles a step  speed-up\n");
    for (int i = 0; i < LOOPS; i++) {
        double ns = t[i][0] / work, cycles = ns / cycle;
        printf("%6d  %7.4f  %11.2f  %13.2f  %7.2fx\n", chains[i], ns, cycles, cycles * chains[i],
               (double)t[0][0] / t[i][0]);
    }
    printf("every call added correctly: %s\n", right ? "yes" : "no");
    return right ? 0 : 1;
}

// sum_main.c: sums the same 65,536 numbers, 1/1 + 1/2 + ... + 1/65536, with whichever build of sum() it is linked
// with, and prints the total to 17 significant digits and the fastest of 501 calls.
#include <pthread/qos.h>
#include <stdint.h>
#include <stdio.h>
#include <time.h>

double sum(const double *a, long n);

enum { N = 65536, CALLS = 501 };
static double a[N];

int main(void) {
    pthread_set_qos_class_self_np(QOS_CLASS_USER_INTERACTIVE, 0);
    for (long k = 0; k < N; k++)
        a[k] = 1.0 / (double)(k + 1);
    double total = 0.0;
    uint64_t best = UINT64_MAX;
    for (int c = 0; c < CALLS; c++) {
        uint64_t t0 = clock_gettime_nsec_np(CLOCK_UPTIME_RAW);
        total = sum(a, N);
        uint64_t t = clock_gettime_nsec_np(CLOCK_UPTIME_RAW) - t0;
        if (t < best) best = t;
    }
    printf("total %.17g, fastest call %.3f ns a value\n", total, (double)best / N);
    return 0;
}

1. In chains.s, make the ruler _adds add into two registers in turn, x1 and x2, and combine them at the end with add x0, x1, x2. Predict before you run what happens to the one cycle at line and to every cycles column, then explain why a ruler must be a single dependency chain.
2. Build sum.c at -O2 and at -O2 -ffast-math and run both with the commands of the reassociation session. Note the two totals and the two times, then raise the array to 4,000,000 values and see whether the gap between the builds changes.
3. In mca_session.py, change -mcpu=znver4 to -mcpu=skylake and compare addsd’s latency and the one-chain cycles with Zen 4’s.

The exercise turns the two limits of this page into a model: given the latency, the number of adders and the number of accumulators, predict the cycles a pass takes, and check the model against the Zen 4 and P670 numbers recorded above.

def cycles_per_pass(adds, latency, units, chains):
    """Cycles one pass takes: `adds` additions over `chains` accumulators, on `units` adders of `latency` cycles."""
    return 0  # replace with your code


def chains_needed(latency, units):
    """The fewest accumulators that keep all `units` adders busy."""
    return 0  # replace with your code

"""Sample tests: the Zen 4 and SiFive P670 models the page recorded, and a few made-up cores."""

from cycles import chains_needed, cycles_per_pass


def test_zen4_one_chain_runs_at_the_latency():
    assert cycles_per_pass(24, 3, 2, 1) == 72


def test_zen4_three_chains():
    assert cycles_per_pass(24, 3, 2, 3) == 24


def test_zen4_six_chains_reach_the_adders():
    assert cycles_per_pass(24, 3, 2, 6) == 12


def test_zen4_twelve_chains_are_no_faster_than_six():
    assert cycles_per_pass(24, 3, 2, 12) == 12


def test_p670_one_chain():
    assert cycles_per_pass(24, 2, 2, 1) == 48


def test_p670_three_chains():
    assert cycles_per_pass(24, 2, 2, 3) == 16


def test_p670_six_chains():
    assert cycles_per_pass(24, 2, 2, 6) == 12


def test_a_share_of_a_cycle_is_kept():
    assert cycles_per_pass(10, 3, 1, 4) == 10
    assert cycles_per_pass(10, 3, 4, 4) == 7.5


def test_one_adder_is_the_limit_at_once():
    assert cycles_per_pass(8, 1, 1, 1) == 8
    assert cycles_per_pass(8, 1, 1, 4) == 8


def test_chains_needed_on_the_recorded_models():
    assert chains_needed(3, 2) == 6
    assert chains_needed(2, 2) == 4


def test_chains_needed_on_made_up_cores():
    assert chains_needed(4, 2) == 8
    assert chains_needed(2, 4) == 8
    assert chains_needed(5, 1) == 5
    assert chains_needed(1, 3) == 3

Interview questions

A warm-up: a loop sums an array into one double and a profiler calls it latency-bound. What does that mean, and what is the first thing you try?

Latency-bound means the loop’s speed is set by how long each operation takes to produce a result the next one needs, not by how much the core could do in parallel. The sum is one dependency chain: each s += a[i] waits for the previous s. The first thing to try is several independent accumulators, say four partial sums added into in turn and combined at the end, so four additions are in flight at once. In C that often means building with -ffast-math, or writing the partial sums by hand, and accepting that the total may change in its last digits because the additions are regrouped. Then measure: the gain stops once the core’s adders are full, which on the machine on this page took sixteen accumulators and gave about eight and a half times the speed.

Two deeper questions build on this lesson, one on proving the speed-up with a model in a build pipeline and one on latency against throughput:

Key takeaways

• A dependency chain, where each instruction needs the previous result, runs at one operation per operation latency, no matter how many execution units the core has spare.
• Independent instructions let an out-of-order core overlap work; sixteen independent accumulators made the addition loop about eight and a half times faster, once every adder was busy.
• Latency is the wait for one result and throughput is how many results a cycle; a chain pays the latency, independent work approaches the throughput, and their product bounds the speed-up.
• A compiler gives a reduction several accumulators by itself when the operation is associative, as integer addition is; floating-point addition needs -ffast-math, which can change the last digits of the total.
• llvm-mca estimates the cycles of a block on a named core deterministically and without running it, but it models only the core’s scheduler and assumes cache hits, so measure on real data.