ComputeThreadPool workers idle threads: ceiling-division partitioning leaves up to ~47% of the pool unused

[kkokosa]

Found by inspection while comparing the attention kernel against a slide describing it — not by profiling. No measured regression is attached; see "Impact" for why it may still be worth fixing.

The pattern

Every ComputeThreadPool worker partitions its work the same way:

int itemsPerThread = (totalItems + threadCount - 1) / threadCount;   // ceiling
int start = threadIdx * itemsPerThread;
int end   = Math.Min(start + itemsPerThread, totalItems);
if (start >= totalItems) return;                                     // thread does nothing

Ceiling division front-loads work: every thread takes the rounded-up share, so the tail threads get start >= totalItems and return immediately. Threads idle even when there is work left that could have been spread more evenly.

12 occurrences:

File	Lines	Partitioned over
Kernels/Attention.cs	275, 337, 706	heads
Kernels/MatMul.cs	463, 2079, 2354, 2373, 2391	groups / tiles
Kernels/MatMulKQuants.cs	1922, 2016	tiles / tokens
Kernels/MatMulQ5_0.cs	941, 1213	tiles / groups

(MatMul.cs:2079 is GemmR4TiledQ8Worker, added in #400 — it copied the surrounding convention.)

Why attention is the acute case

Severity depends on how close the item count is to the thread count. For the matmul workers the item count is large — a 2048-row Q8_0 weight gives 512 four-row groups, so 32 threads get 16 each and nothing idles.

Attention partitions over heads, and head count is the same order as core count. For a 2048-hidden / headDim-64 model that is 32 heads:

heads	threads	per thread	threads used	idle
32	32	1	32	0
32	24	2	16	8 (33%)
32	20	2	16	4 (20%)
33	32	2	17	15 (47%)
64	48	2	32	16 (33%)

The N = T + 1 case is the worst: one extra item over thread count doubles everyone's share and idles nearly half the pool.

Note the distinct, non-buggy case: with 16 heads on 32 threads, 16 threads idle simply because a head is the smallest unit — that is a granularity limit, not a partitioning flaw.

Fix

Standard balanced split — every thread gets floor(N/T) or ceil(N/T) items, none idle while N >= T:

int baseCount = totalItems / threadCount;
int remainder = totalItems % threadCount;
int start = threadIdx * baseCount + Math.Min(threadIdx, remainder);
int end   = start + baseCount + (threadIdx < remainder ? 1 : 0);

Worth extracting as a shared helper (e.g. ComputeThreadPool.PartitionRange(total, threadIdx, threadCount, out start, out end)) rather than fixing 12 copies independently, since the current duplication is how the flaw spread.

Impact — honest assessment

• On the default configuration this machine runs (32 heads, 32 threads) there is no imbalance at all, which is presumably why it has gone unnoticed.
• It bites on explicit --threads values that do not divide the head count, on machines whose core count is not a power of two, and on models whose head count sits just above the thread count.
• Attention is only about 1% of compute in an ETW profile of a 611-token prefill plus 111-token decode — matmul dominates at roughly 53%. So even a 33% idle rate inside attention is a small absolute number for this workload. It would matter more at long context, where attention grows relative to matmul.

So: a real defect, cheap to fix, with a modest and configuration-dependent payoff. Filing it because it is the kind of thing that silently caps scaling on someone else's hardware, not because it is costing measurable time here.

Acceptance criteria

• A shared partition helper exists and is used by all 12 worker sites.
• For any totalItems >= threadCount, no thread receives an empty range.
• Per-thread item counts differ by at most 1.
• Unit tests over the helper covering N < T, N == T, N == T + 1, N a multiple of T, and N just under a multiple.
• Numerical output unchanged — this is a work-distribution change only; each thread still owns a disjoint output range, so results must be identical.
• No throughput regression on the default configuration; ideally a measured improvement with a deliberately awkward --threads value (e.g. --threads 24 on a 32-head model).

References

• src/DotLLM.Cpu/Threading/ComputeThreadPool.cs
• src/DotLLM.Cpu/Kernels/Attention.cs — AttentionWorker, TiledAttentionWorker, QuantizedTiledAttentionWorker
• src/DotLLM.Cpu/Kernels/MatMul.cs, MatMulKQuants.cs, MatMulQ5_0.cs
• docs/ATTENTION.md