Block Householder apply re-reads the whole basis V once per column task; traffic grows with the thread count

Problem

Since #88 removed the row split, the block Householder apply (C ← C − V T Vᴴ C) splits only over the target's columns. Each column task computes W_j = Vᴴ C_j and then C_j −= V W_j, so every task reads the whole basis V (m × k) twice. Total V traffic per call grows linearly with the number of tasks:

traffic(V) ≈ 2 · tasks · m · k · sizeof(T)

At 8 threads this already shows on evo (Zen5c, 8 cores sharing an 8 MiB L3). From 161c4fe's table, column-only / row split (ms), F order, 8T:

basis / target	column-only	row split	`V` size (f64)
4096x64 / 192	1.603	1.393	2 MiB
4096x96 / 160	2.399	2.005	3 MiB
4096x256 / 256	8.522	7.906	8 MiB

Smaller bases (4096x16, 4096x32, where V fits easily) and 4T do not show it. The likely mechanism is that 8 re-reads of a 2-8 MiB V no longer stay in the shared L3 and the call becomes bandwidth-bound (not yet verified with counters).

This is not a host-specific constant: the re-read is proportional to the thread count. At 32 or 64 threads (primerose, broccoli: 64 cores) it would multiply V traffic by 32-64 for any V larger than a thread's share of the cache, which is exactly where block applies matter (tall QR, qr_factor, svd_thin).

The removed row split had the opposite trade-off (each thread reads 1/threads of V, but pays threads partial k × n sums and capped the column split at four tasks), so restoring it is not the answer either.

Proposal

Make V traffic independent of the task count:

Pack V once, share it. As in a BLIS-style GEMM (what reference LAPACK's DLARFB delegates to): pack the V panel once per call (or per row block) into a buffer all workers read, and split the target's columns over threads. Each worker streams its own C_j and the shared packed V from L2/L3.
Or a 2-D split chosen from m, k, n and the thread budget: r row blocks × c column blocks with r · c = tasks, so each task reads m/r × k of V and the partial sums are k × n/c. The choice must come from the shapes and the token's dispatch cost model, not from constants fitted to one host.

Done when

V bytes read per call (measured with perf stat LLC/memory counters, or computed from the schedule) do not grow with the thread count.
Scaling on a high-core host: 1/8/16/32/64 threads for 4096x{64,96,256} and a taller case (e.g. 16384x256), f64/c64, C/F. Use broccoli (64 cores, otherwise idle) for the scaling curve, and evo with the campaign protocol (boost off) for the regression gate at 4T/8T. Compare with OpenBLAS (DLARFB structure) at the same thread counts.
No regression on the 32 householder_apply cells of householder_apply on tall shapes is 2.2x to 3.1x slower than upstream at 4T/8T since 0.25.0 #79 or the tall qr_factor/qr/svd_thin/svd_values guards.

Related: #79 (fixed by #88), #85 (threadteam-only dispatch, in progress).

🤖 Generated with Claude Code

高並列スケーラビリティ監査 #95 の子 issue として登録しました。同種の問題 (#91〜#94) の計測は、この issue の計測が終わってから行います。

Measured on broccoli (EPYC 7702P, 64 cores Zen2, 16 MiB L3 per 4-core CCX, SMT off, boost 0)

Measurement only, no code change. Revision 0a4713a (faer-v0.25.2, origin/main when the run
started) and 747debf (the parent of #88, row split still present); upstream faer v0.24.4 in the
same binary. Protocol: the campaign harness (fbench) at prime 250 ms / 5 reps / median, two
process sets, arms interleaved, whole-L3-domain idle guard, observer pinned off the measured set,
CPU sets aligned to whole CCXes (1T 60 … 32T 32-63, 60T 4-63; the 64T cell shares the
observer CCX and is reported but not used for any conclusion).

No hardware counters on this host: perf is not installed and perf_event_paranoid=3 with no
root, so perf_event_open returns EACCES for PERF_COUNT_HW_CACHE_LL and ..._INSTRUCTIONS.
Basis traffic below is the schedule-derived nominal volume the issue allows, with the host's own
measured read ceilings beside it (64 cores, 2048 MiB set: 293 GB/s; 8 MiB shared per CCX:
830 GB/s from L3, 123 GB/s for one CCX's four threads).

1. The apply against its own two products, 4096x256, f64, F order (ms)

The two products were timed standalone in the same binary, same order, same budgets
(W = V^H C = 256x4096x256; C -= V W = 4096x256x256):

T	`householder_apply`	legs (`V^H C` + `V W`)	apply / legs	apply speedup	legs speedup
1	41.09	21.42 + 20.03 = 41.45	1.01	1.0x	1.0x
8	7.76	3.47 + 3.43 = 6.90	1.12	5.3x	6.0x
16	5.93	2.19 + 2.00 = 4.19	1.42	6.9x	9.9x
32	4.04	1.41 + 1.20 = 2.62	1.54	10.2x	15.8x
60	3.67	0.97 + 0.79 = 1.76	2.08	11.2x	23.5x
64*	3.41	1.08 + 0.68 = 1.76	1.94	12.0x	23.5x

* non-conforming: shares the observer CCX.

The two products the apply is made of scale 23.5x on 60 cores; the apply that calls them inside
min(threads, K) column tasks scales 11.2x, and the gap appears exactly as the tasks get narrow
(1.0x at 1T, 2.1x at 60T). The row-split revision (747debf) behaves the same at high budgets
(60T: 3.78 ms vs 3.67), so this is not about which axis is split.

2. Why: the split makes every task 1-4 columns wide

Same public call, m = 4096, k = 256 (basis 8 MiB), target restored outside the clock, m/k/n
independent (so the basis is fixed while the target's width varies):

T	target n	columns per task	achieved GFLOPS
60	64	1.1	68.5
60	256	4.3	158.6
60	1024	17.1	204.8
16	64	4.0	59.0
16	1024	64.0	162.6

At a fixed basis and budget, going from 1 to 17 columns per task triples the achieved rate. A task
that owns 4 columns does a rank-4 product (essentially four gemvs) plus the whole k x k
triangular solve, so the work per basis byte read is what collapses — the traffic model in the issue
is right, and this is the quantity it is really about.

3. Traffic, against the ceilings

shape	T	ms	nominal basis MiB/call	implied GB/s
4096x256	32	4.08	496	119
4096x256	60	3.67	930	247
16384x256	32	18.10	2032	110
16384x256	60	19.69	3810	189

At 4096x256/60T the implied basis read is ~85% of the host's measured DRAM ceiling, so the schedule
does reach a bandwidth wall — but the unsplit alternative reads 16 MiB per call, and the legs above
show those same bytes are not a compute limit. The re-read is manufactured by the split, not an
intrinsic property of the operation.

16384x256 (V = 32 MiB, past one CCX's 16 MiB L3) stops improving at 32T (18.1 ms) and is 9% slower
at 60T, while 4096x256 (8 MiB) still improves to 60T. That is the footprint effect the issue
predicts, and it is where the traffic argument does bite.

4. Reference

OpenBLAS ?larfb (?geqrf+?larft factors from the same input, budget set and read back):
11.86 / 12.29 / 13.86 ms at 8/16/60T against the apply's 8.00 / 6.24 / 3.38 on the same fixture —
the fork is 1.5-4.1x faster, and ?larfb does not scale here either.
OpenBLAS dgemm on the legs: 4096x256x256 60T 2.87 ms vs the fork's matmul 0.79 ms.

So "we are behind a reference that reads V once" is not what this host says; the gap is inside our
own schedule.

Verdict on the issue's hypothesis

Schedule (confirmed from the source): n_tasks = min(threads, K) column tasks, each consuming
the whole basis twice, so nominal basis volume grows with the budget — 4x at 4T, 60x at 60T for
4096x256 (930 MiB per call against 16 MiB at 1T).
Traffic (consistent for the wide basis, not the binding constraint for the narrow one): at
60T the implied rate reaches the DRAM ceiling; but at the same budgets the products themselves run
23.5x faster standalone, so the traffic is a consequence of the split, not the operation.
4096x64 / 4096x96 at 60-64T: unstable, no conclusion. There the harness's samples are
bimodal (1.24-3.0 ms within one cell) and the decoupled probe disagrees with the harness by 2-5x
(0.51 vs 2.64 ms). I have not attributed that, and I am not claiming a narrow-basis regression from
it. The unchanged upstream row's between-set spread over the whole grid was +9.7%, so anything
under ~10% here is not resolvable either.

Which fix

Fix 2 (2-D split) is the one the evidence points at, not fix 1: the measured problem is that a task
owns 1-4 columns, and only a split that keeps n/c columns per task and cuts the basis read to
m/r fixes both at once. Packing V once removes the traffic but leaves the 4-column tasks, whose
cost here is larger than the traffic (row 1: the legs are 2x faster than the apply at 60T while
reading the basis only twice).

Before either, the cheap experiment to measure is not a new schedule at all: when the target is
narrow relative to the budget, do not split its columns and let the two products take the whole
budget — the legs standalone are 0.97 + 0.79 ms at 60T against the apply's 3.67 ms. If that holds
inside the apply, it is a floor change (the #91 territory), and it is the measurement that would
decide between (c), fix 1 and fix 2 rather than guessing.

The 32 householder_apply cells of #79 and the tall qr/svd guards are not re-measured here: this
phase changed nothing, so those pages stay valid.

Fixing this here together with #160 stage 2 (maintainer, 2026-10-30): the block apply will pack the basis once per call and share it, instead of each column task re-reading all of V. One PR for both.

Candidates for this issue (owner-packed apply following OpenBLAS's level-3 buffer roles, whole-team GEMMs, and today's column split) and the broccoli run that compares them: #160 (latest comment, branch probe/160-qr-phases-v2 at 0edc74b).

probe(#160, #90): T packed once per call in the owner-packed apply, e…

The two-arm experiment for this issue (shared V and T pack with per-thread reusable working memory, against main) is specified in #160 (latest comment, probe fd17c8d); results will be collected there. Adoption: if it helps without regressions (maintainer, 2026-10-30).

Shared V/T pack (owner-packed apply): measured, not adopted in its current form

Record for this issue. Measurements are in #160: broccoli 1-64T (comment and the result after it) and evo 1-8T.

What was tried (probe fd17c8d, mode 5). The design follows OpenBLAS's level3_thread.c / memory.c buffer roles:

participant i packs row slice i of V (with the unit head made explicit) into its own reusable buffer, which it first-touches;
the caller packs T once into its own buffer;
after one barrier, participant i owns column block i, with a private W_i, and reads every slice.

V is read from memory once per call, and the slices together are one copy of V, not p copies. Steady state is allocation-free.

Result (the maintainer's rule: adopt if it improves without regressions).

	arm B / arm A
this issue's shapes at 16-32T (broccoli)	0.45-0.88
this issue's shapes at 8T (evo)	0.64-0.89
Q formation at 4096	0.87-0.97
`qr_factor`'s apply stage at 4096/64T	0.81
`qr_factor` at 1024/64T (broccoli)	1.57
Q formation at 1024/64T (broccoli)	2.76
`qr_factor` at 1024/4T (evo)	1.10
every #90 shape at 64T (broccoli)	1.09-8.90, spreads 4-18x within each arm
16384×256 at 8T (evo)	1.16
`qr_factor`'s panel stage, 4096/16T	123 → 139 ms

The effect this issue predicted is real at 16-32T, but the arm regresses elsewhere, as the last five rows show. Not adopted as it stands. The default stays the column split (mode 0).

What has to be explained before a gated retry (for example, restricted to a wide V and to at most 32 participants). These are unverified leads:

The 64T collapse. The large spread points at the barrier rather than the arithmetic. With 64 spinning participants on CPUs 0-63, one preempted participant stalls the whole barrier. This is the same signature as the Cholesky 1024/64T collapse being probed in Thread scaling against MKL on 64 cores: gemm, qr and svd at n=1024/2048/4096 (stage 1: measurement and diagnosis) #160. Cross-CCX reads of the other 15 CCXs' slices are a second candidate.
The panel stage slowing down. Mode 5 also takes the panel's narrow applies (a target of 1-64 columns). There each call pays the pack, a barrier and a first-touch growth for a few columns per participant. A retry must leave those applies alone. The row-split candidate for narrow targets (mode 6) is measured separately, as the panel fix.
Small n. At 1024 the pack plus the barrier costs more than the re-read of a 0.25 MiB basis saves, more so at higher budgets.

Priority now goes to the qr_factor panel (#160).

Folded into the umbrella #168 (parallel structure of the factorizations). This issue is re-scoped or closed against its items.

Navigation Menu

Repository navigation

Block Householder apply re-reads the whole basis V once per column task; traffic grows with the thread count #90

Problem

Proposal

Done when

Measured on broccoli (EPYC 7702P, 64 cores Zen2, 16 MiB L3 per 4-core CCX, SMT off, boost 0)

1. The apply against its own two products, 4096x256, f64, F order (ms)

2. Why: the split makes every task 1-4 columns wide

3. Traffic, against the ceilings

4. Reference

Verdict on the issue's hypothesis

Which fix

Shared V/T pack (owner-packed apply): measured, not adopted in its current form

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Block Householder apply re-reads the whole basis V once per column task; traffic grows with the thread count #90

Description

Problem

Proposal

Done when

Activity

shinaoka commented on Oct 28, 2026

shinaoka commented on Oct 29, 2026

Measured on broccoli (EPYC 7702P, 64 cores Zen2, 16 MiB L3 per 4-core CCX, SMT off, boost 0)

1. The apply against its own two products, 4096x256, f64, F order (ms)

2. Why: the split makes every task 1-4 columns wide

3. Traffic, against the ceilings

4. Reference

Verdict on the issue's hypothesis

Which fix

shinaoka commented on Oct 30, 2026

shinaoka commented on Oct 30, 2026

shinaoka commented on Oct 30, 2026

shinaoka commented on Oct 30, 2026

Shared V/T pack (owner-packed apply): measured, not adopted in its current form

shinaoka commented on Oct 30, 2026

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions