CK-Engine Thread Pool

§1 What Is a "Pool"?

A pool is a set of expensive resources you create once and reuse over and over, instead of creating and destroying them every time you need one.

The word "pool" shows up in many places in systems programming:

The common pattern: creating the resource is expensive; using it is cheap. A pool pays the creation cost once, then amortizes it over thousands of uses.

§2 The Problem: Why Not Just Use OpenMP?

OpenMP looks appealing — just add #pragma omp parallel for and you get parallelism. But there's a hidden cost.

During inference, CK-Engine runs the transformer decode loop. For each token generated, it calls kernel functions (matrix-vector multiplies, RMSNorm, SwiGLU, etc.) roughly 500+ times. Each call is a short burst of work (microseconds to low milliseconds).

OpenMP's Fork/Join Model

With each fork/join costing 50–200µs and 500+ kernel calls per token:

Real Measurement from CK-Engine (gemv_omp.c)

/*
 * Measured on i7-3630QM (4C/8T), Qwen 0.5B:
 *   Serial kernels:   170 ms/tok  (5.9 tok/s)
 *   OMP parallel:     327 ms/tok  (3.1 tok/s)  ← 1.9x SLOWER
 *
 * The math is correct (10/10 parity tests pass) but the
 * threading model is wrong for this workload.
 */

OpenMP parallelism made it almost 2x slower. The fork/join overhead completely ate the parallelism gains and then some.

§3 Anatomy of CK-Engine's Thread Pool

Let's look at the actual data structure. Every field exists for a specific reason.

struct ck_threadpool {
    /* --- Dispatch state (each on its own cache line) --- */
    _Alignas(64) atomic_int   n_dispatch;   // bumped to wake workers
    _Alignas(64) atomic_int   n_complete;   // workers signal "I'm done"
    _Alignas(64) ck_work_fn_t work_fn;      // pointer to current kernel
                 void        *work_args;    // arguments for the kernel

    /* --- Barrier for mid-kernel sync --- */
    ck_barrier_t barrier;

    /* --- Worker management --- */
    int          n_threads;    // total (including main)
    ck_worker_t  workers[64];  // thread handles

    /* --- Shutdown / pause --- */
    _Alignas(64) atomic_int stop;    // set to 1 to kill workers
    _Alignas(64) atomic_int paused;  // set to 1 for power saving

    /* --- Hybrid sleep mechanism --- */
    pthread_mutex_t mutex;
    pthread_cond_t  cond_dispatch; // workers sleep here
    pthread_cond_t  cond_done;     // main sleeps here
};

Why _Alignas(64) Everywhere?

Each atomic counter is placed on its own 64-byte cache line. This prevents "false sharing" — where two unrelated variables on the same cache line cause all CPU cores to fight over that cache line. More on this in §8.

The Worker Struct

typedef struct {
    pthread_t thread;            // OS thread handle
    int       id;               // 0 = main, 1..N-1 = workers
    struct ck_threadpool *pool; // back-pointer to the pool
} ck_worker_t;

Thread 0 is always the main thread — the one that calls ck_threadpool_dispatch(). It doesn't get a new pthread. It does its share of the work alongside the workers.

§4 Lifecycle: Create → Dispatch → Destroy

Global Pool Convenience

For CK-Engine, there's a global singleton pool accessed via ck_threadpool_global(). It uses pthread_once to ensure thread-safe lazy initialization — no matter how many threads call it simultaneously, the pool is created exactly once.

static ck_threadpool_t *g_threadpool = NULL;
static pthread_once_t  g_threadpool_once = PTHREAD_ONCE_INIT;

ck_threadpool_t *ck_threadpool_global(void) {
    pthread_once(&g_threadpool_once, global_pool_init);
    return g_threadpool;
}

§5 Dispatch Deep Dive: What Actually Happens

Let's trace exactly what happens when CK-Engine needs to run one kernel across 4 threads.

Key Details

• No thread creation. Workers are already alive, spinning or sleeping. The only cost is bumping an atomic counter.
• Main thread participates. Thread 0 does 1/N of the work alongside the workers. No wasted CPU.
• Single-thread fast path. If n_threads == 1, dispatch just calls fn(0, 1, args) directly — zero overhead.
• Completion tracking. Each worker atomically increments n_complete. The last worker (N−2-th increment) signals the condvar to wake main if it fell asleep waiting.

Inside the Work Function

Each kernel receives (ith, nth, args) and partitions work by thread index:

void gemv_parallel(int ith, int nth, void *args) {
    gemv_args_t *a = args;
    // Each thread computes its slice of output rows
    int rows_per_thread = a->M / nth;
    int start = ith * rows_per_thread;
    int end   = (ith == nth - 1) ? a->M : start + rows_per_thread;

    for (int row = start; row < end; row++) {
        vec_dot(a->K, &a->y[row], a->W + row * a->K, a->x);
    }
}

§6 Spin-Wait vs. Sleep: The Hybrid Polling Design

How do worker threads wait for work? There are two extremes, and CK-Engine uses both.

CK-Engine's Hybrid Approach

Workers do both:

1. First, spin for CK_THREADPOOL_SPIN_COUNT (1024) iterations, checking the atomic dispatch counter.
2. If no work arrives during spin, fall back to pthread_cond_wait() (sleep).
3. When new work arrives, spinning workers wake instantly; sleeping workers wake via condvar broadcast.

// worker_main() — the hybrid wait loop
for (;;) {
    int spins = 0;
    for (;;) {
        if (atomic_load(&pool->stop))  return NULL;  // shutdown?

        int current = atomic_load(&pool->n_dispatch);
        if (current != last_dispatch) {              // new work!
            last_dispatch = current;
            break;                                   // go execute
        }

        _mm_pause();    // x86 hint: "I'm spinning, save power"
        spins++;

        if (spins >= 1024) {                        // tired of spinning?
            pthread_mutex_lock(&pool->mutex);
            // Re-check under lock (avoid missed wakeup!)
            if (no_new_work && !stopping)
                pthread_cond_wait(&pool->cond_dispatch, &pool->mutex);
            pthread_mutex_unlock(&pool->mutex);
            spins = 0;
        }
    }
    // execute work...
}

What Is _mm_pause()?

It's an x86 intrinsic that tells the CPU: "I'm in a spin-wait loop." The CPU can then:

• Reduce power consumption of the spinning core
• Free up execution resources for the sibling hyper-thread
• Avoid memory-order violations that would require pipeline flushes

On non-x86 (ARM, etc.), CK-Engine defines CK_SPIN_PAUSE() as a no-op.

§7 Atomics, Mutexes, and Memory Ordering

These are the fundamental building blocks of any concurrent system. Let's understand each one from scratch.

What Is an Atomic Operation?

An atomic operation is one that completes in a single, indivisible step from the perspective of all other threads. No other thread can see a "half-done" state.

CK-Engine uses atomics for:

• n_dispatch — the "new work available" counter. Main increments it; workers read it.
• n_complete — workers increment when done. Main reads it to know when all are finished.
• n_arrived (barrier) — threads increment when reaching the barrier point.
• stop, paused — simple flags, but still need atomic reads/writes for visibility across cores.

Memory Ordering

CPUs and compilers can reorder memory operations for performance. Memory ordering tells them: "don't reorder this particular operation past certain points."

What Is a Mutex?

A mutex (mutual exclusion) is a lock. Only one thread can hold it at a time. Everyone else waits. CK-Engine uses mutexes only for the condvar sleep mechanism — the hot path (spin-wait) doesn't touch the mutex at all.

// Mutex usage — only in the cold sleep path
pthread_mutex_lock(&pool->mutex);
  // Re-check condition (avoid lost wakeup)
  if (still_no_work)
      pthread_cond_wait(&pool->cond_dispatch, &pool->mutex);
      //     ^^ releases mutex, sleeps, re-acquires on wake
pthread_mutex_unlock(&pool->mutex);

What Is a Condition Variable (Condvar)?

A condvar lets a thread say: "Wake me up when something changes." It works together with a mutex:

1. Wait side: Lock mutex → check condition → if false, cond_wait (atomically releases mutex + sleeps) → on wake, re-acquires mutex
2. Signal side: Lock mutex → change state → cond_broadcast (wakes all waiters) → unlock

CK-Engine has two condvars:

• cond_dispatch — workers wait here when idle (no work to do)
• cond_done — main thread waits here when all workers are still busy

§8 Cache Lines & False Sharing

This is one of the most important performance concepts in multi-threaded code.

How CPU Caches Work (Simplified)

CPUs don't read individual bytes from RAM. They read in cache lines — 64-byte chunks. When one core writes to a cache line, all other cores that have a copy of that line must invalidate it (MESI protocol). This is called a cache coherency miss.

This is why every atomic_int in the pool struct has _Alignas(64) — it forces each one onto its own cache line, eliminating false sharing entirely.

§9 The Barrier: How Threads Synchronize

A barrier is a meeting point. All threads must arrive before any can proceed.

CK-Engine implements a custom spin-wait barrier using two atomic counters: n_arrived (how many threads reached the barrier) and n_phase (which "round" of the barrier we're on).

// barrier_wait() — ck_threadpool.c:89–111
static void barrier_wait(ck_barrier_t *b) {
    const int phase = atomic_load(&b->n_phase);

    if (atomic_fetch_add(&b->n_arrived, 1) == n - 1) {
        // I'm the LAST thread to arrive
        atomic_store(&b->n_arrived, 0);       // reset for next use
        atomic_store(&b->n_phase, phase + 1); // advance phase
    } else {
        // NOT the last thread — spin until phase advances
        while (atomic_load(&b->n_phase) == phase) {
            _mm_pause();
        }
    }
}

The phase counter trick allows the barrier to be reused without an explicit reset — each barrier use just increments the phase. After many spins without the last thread arriving, threads call sched_yield() to be nice to the OS on oversubscribed systems.

§10 Thread Pool vs. OpenMP — Side-by-Side

§11 Thread Pool vs. Memory Pool — Same Idea, Different Resource

Both are "pools" — they pre-create expensive resources. The key differences are about what they pool and what synchronization they need.

The Deeper Conceptual Link

Synchronization Comparison

§12 Why Is It Faster?

Cost Breakdown: OpenMP vs. Thread Pool

The Five Reasons It's Faster

§13 Real Numbers: Before & After

Measured on i7-3630QM (4 cores / 8 threads), Qwen2 0.5B model, Q4_K_M quantization.

Where Does Overhead Go?

§14 How Parallelization Actually Works

Forget the abstractions for a moment. Here is exactly what happens, from physical hardware up.

Step 1: Pin Threads to Physical Cores

At startup, the thread pool creates N−1 persistent pthreads. Ideally, each thread is pinned (affined) to a distinct physical CPU core using sched_setaffinity() or pthread_setaffinity_np(). This means the OS scheduler will not migrate a thread to a different core — it stays put.

Why pin? Three reasons:

• Cache locality: A pinned thread keeps its L1/L2 caches warm. If the OS migrates a thread to a different core, the old core's cache is useless and the new core starts cold.
• No scheduler jitter: The OS scheduler makes decisions every ~1–4ms. Thread migration adds 5–20µs of latency. For sub-millisecond kernels, that's significant.
• NUMA awareness: On multi-socket systems, accessing memory attached to a remote socket costs 2–3x more than local memory. Pinning keeps threads close to their data.

CK-Engine's Current State

The system topology module (src/system_topology.c) can discover the CPU layout:

// topology_discover_affinity() reads the process CPU mask
cpu_set_t mask;
if (sched_getaffinity(0, sizeof(mask), &mask) == 0) {
    for (int i = 0; i < MAX_CPUS; i++) {
        if (CPU_ISSET(i, &mask)) {
            aff->affinity_cpus[aff->num_affinity_cpus++] = i;
        }
    }
}

The GGML layer has full NUMA-aware pinning with three strategies: DISTRIBUTE (round-robin across NUMA nodes), ISOLATE (all threads on same node), and NUMACTL (respect external numactl settings). Intel hybrid CPU detection (P-core vs E-core via CPUID) is also available to skip efficiency cores for compute-heavy work.

Step 2: Identify Embarrassingly Parallel Loops

An embarrassingly parallel loop is one where every iteration is completely independent — no iteration reads what another writes. These loops can be split across cores with zero synchronization.

Here's what the thread pool does to every such loop:

// BEFORE: Serial loop over M rows
for (int row = 0; row < M; row++) {
    compute_row(row, ...);
}

// AFTER: Thread pool splits the loop across N threads
void work_fn(int ith, int nth, void *args) {
    int rows_per_thread = M / nth;
    int start = ith * rows_per_thread;
    int end   = (ith == nth - 1) ? M : start + rows_per_thread;

    for (int row = start; row < end; row++) {
        compute_row(row, ...);   // exact same computation, just a slice
    }
}
ck_threadpool_dispatch(pool, work_fn, &args);

Each thread computes a contiguous slice of the output. Thread 0 does rows 0..249, thread 1 does rows 250..499, etc. The total work is the same; it's just divided.

Step 3: Ensure No Two Threads Write to the Same Cache Line

This is the critical constraint. The rule is:

In practice, this means the output array partition must be cache-line aligned at the boundaries between threads. Since a cache line is 64 bytes = 16 floats:

For transformer kernels, this alignment happens naturally because:

• Each output row is typically 512–4096 floats (2KB–16KB) — many cache lines per row.
• We split on row boundaries, so each thread owns complete rows.
• Row addresses are aligned to CK_CACHE_LINE (64 bytes) in the memory allocator.
• The only "dangerous" case is the last few elements at a boundary, but with row-level splitting this never happens.

Step 4: What About Reads?

Reads are shared freely. This is what makes matrix operations so parallelizable:

The MESI cache coherency protocol makes shared reads essentially free. When multiple cores read the same cache line, each core gets its own copy in "Shared" (S) state. No invalidation occurs. The cache line stays resident in every core's L1/L2 simultaneously.

Step 5: Handle Reductions Carefully

Some kernels have reduction operations — where all threads must contribute to a single result (e.g., sum, max). These break the "no shared writes" rule and need special handling.

In CK-Engine's kernels, reductions are intra-token (within a single token's D-dimensional vector), not inter-token. Since we parallelize across tokens (not within a single token's dimension), each thread's reduction is completely private — no cross-thread communication needed.

The Complete Picture

§15 Per-Kernel Parallelization Analysis

Every kernel in the transformer decode loop has a natural parallelization dimension. Here's exactly how each one splits across threads, what data is shared, what is exclusive, and where reductions happen.

GEMV — Matrix-Vector Multiply

File: src/kernels/gemv_omp.c
Operation: y[M] = W[M×K] · x[K]
Call frequency: ~37% of decode time (logits projection is the largest single GEMV)

void gemv_q8_parallel(int ith, int nth, void *args) {
    gemv_args_t *a = args;
    int rows_per_thread = a->M / nth;
    int start = ith * rows_per_thread;
    int end   = (ith == nth - 1) ? a->M : start + rows_per_thread;

    for (int row = start; row < end; row++) {
        // Each thread: dot product of one W row with shared x
        vec_dot_q8_0_q8_0(a->K, &a->y[row],
                          &a->W_blocks[row * blocks_per_row],
                          a->x_blocks);
    }
}

GEMM — Matrix-Matrix Multiply

File: src/kernels/gemm_kernels.c
Operation: C[M×N] = A[M×K] · B[K×N] + bias[N]
Used for: Prefill (processing entire prompt at once — M > 1)

RMSNorm — Root Mean Square Normalization

File: src/kernels/rmsnorm_kernels.c
Operation: y[t,d] = x[t,d] · γ[d] / sqrt(mean(x[t]²) + ε)
Called: Before every attention and FFN block (2x per layer ≈ 48 calls for 24 layers)

The reduction (sum of x² across the D dimension) happens within a single token. Since we split across tokens, not across dimensions within a token, each thread does its own reduction with zero cross-thread communication.

void rmsnorm_parallel(int ith, int nth, void *args) {
    rmsnorm_args_t *a = args;
    int tokens_per_thread = a->T / nth;
    int t_start = ith * tokens_per_thread;
    int t_end   = (ith == nth - 1) ? a->T : t_start + tokens_per_thread;

    for (int t = t_start; t < t_end; t++) {
        float *x = a->input + t * a->aligned_D;
        float *y = a->output + t * a->aligned_D;

        // Phase 1: sum of squares (PRIVATE reduction — within this token only)
        __m512 sum_sq = _mm512_setzero_ps();
        for (int d = 0; d < a->D; d += 16)
            sum_sq = _mm512_fmadd_ps(_mm512_loadu_ps(&x[d]),
                                      _mm512_loadu_ps(&x[d]), sum_sq);
        float rms = sqrtf(_mm512_reduce_add_ps(sum_sq) / a->D + 1e-6f);

        // Phase 2: normalize (element-wise, reads shared gamma)
        __m512 rstd = _mm512_set1_ps(1.0f / rms);
        for (int d = 0; d < a->D; d += 16)
            _mm512_storeu_ps(&y[d],
                _mm512_mul_ps(_mm512_mul_ps(_mm512_loadu_ps(&x[d]), rstd),
                              _mm512_loadu_ps(&a->gamma[d])));
    }
}

Attention — Q·K^T/√d → Softmax → Attn·V

File: src/kernels/attention_kernels.c
Operation: Multi-head scaled dot-product attention with causal mask
Three phases: Score computation, softmax, weighted value summation

Attention is the most complex kernel but also the most naturally parallel. Each attention head is a self-contained computation:

1. Phase 1 (Score): For each query position i, compute score[h,i,j] = Q[h,i] · K[h,j] / √d for all j ≤ i (causal mask). Triangle of dot products per head.
2. Phase 2 (Softmax): Per row: find max, subtract, exp, sum, normalize. The reduction (max, sum) is within a single row — private to the thread owning that head.
3. Phase 3 (Value): output[h,i] = ∑j score[h,i,j] · V[h,j]. Accumulates over j — but within a single head, so private to the owning thread.

Softmax — With Causal Masking

File: src/kernels/softmax_kernels.c
Operation: softmax(row) = exp(row - max) / sum(exp(row - max)), applied to each row of the attention score matrix
Called: Once per attention layer, integrated into the attention computation

SwiGLU — Gated Linear Unit Activation

File: src/kernels/swiglu_kernels.c
Operation: output[t,d] = SiLU(gate[t,d]) × value[t,d] where input is split into gate and value halves
Called: Once per FFN block (1x per layer)

RoPE — Rotary Position Embedding

File: src/kernels/rope_kernels.c
Operation: Rotate Q and K vectors using precomputed sin/cos tables based on token position
Called: Once per attention block (1x per layer, applied to Q and K separately)

Embedding Lookup

File: src/kernels/embedding_kernels.c
Operation: output[t] = token_embeddings[token_id[t]] + pos_embeddings[t]
Called: Once per forward pass (first operation)

KV Cache Write

File: src/kernels/kv_cache_kernels.c
Operation: Copy new K and V vectors for current token into the cache at position token_index
Called: Once per layer (append new token's K,V to cache)

Summary: Parallelization Map

§16 Testing & Validation

The thread pool dispatch layer is validated by a dedicated parity test suite that compares every dispatch wrapper against its serial counterpart. The tests verify both numerical correctness (bit-for-bit parity within tolerance) and performance (speedup from parallelization).

Test Suite: test_threadpool_parity.c

Location: tests/test_threadpool_parity.c

Test Dimensions (Qwen2 0.5B shapes)

Tests run on real model dimensions to catch alignment and edge-case issues:

How to Run

# Quick parity check (~5 seconds)
make test-threadpool-parity-quick

# Full parity + speed test (all model dimensions)
make test-threadpool-parity

# Verbose output (shows max_abs_diff, max_rel_diff for every config)
make test-threadpool-parity-verbose

Correctness Criteria

CI Integration

The thread pool parity test runs automatically in three places:

The nightly workflow (.github/workflows/nightly.yml) runs on every push to main, every pull request, and nightly at 2am UTC. If the thread pool dispatch diverges from serial output, the test exits with code 1 and the nightly report marks it as failed.

ADR: Thread Pool Replaced OpenMP for Parallelization

The codebase previously had an OpenMP parallelization pass (parallel_pass.py) that annotated IR operations with #pragma omp parallel for. This was superseded by the persistent pthread thread pool for the following reasons:

Files affected by this decision:

• version/v6.6/scripts/parallel_pass.py — header documents "SUPERSEDED BY THREAD POOL DISPATCH"
• version/v6.6/scripts/build_ir_v6_6.py — run_parallel_pass() commented out with ADR
• version/v6.6/scripts/ck_run_v6_6.py — --parallel-decode flag deprecated (warns and continues)

Related Test Suites

The thread pool parity test complements existing tests that cover other aspects of the parallelization stack: