FindingID: p3-radix-ballot
Status: stable / task 2026-09-seminar05-milestones — M4 (A5 radix scatter simd_ballot)

2026-09 第 5 回ゼミ milestones · M4 · A5 radix scatter simd_ballot

M4/A5 radix_scatter simd_ballot 2段化 — 12.5k gate 採用、-14.9%、default flip

radix_scatter (tile_bin.metal) の local rank 計算を、256 thread の threadgroup memory を O(lid) 逐次に読む既存実装から、simdgroup 内 <code>simd_ballot</code> + popcount (段1) と simdgroup 間の小さい exclusive prefix (段2) に置換した。sentinel <code>RADIX_BUCKETS</code> (=16) が <code>RADIX_BITS</code> (=4) の下位ビットのみでは digit 0 と衝突する罠 (16 & 0xF == 0) は、同一 digit マスクの初期値を <code>simd_ballot(valid)</code> にすることで回避した。sort parity は unit test (境界サイズ 255/256/257 の sentinel collision ケース込み) + 本番規模 407,267 splats の <code>splat bench --parity</code> の両方で bit exact。12.5k Lego 同一 session 交互 A/B n=3 (off-r1→on-r1→off-r2→on-r2→off-r3→on-r3) で train elapsed 149.883 → 127.530s (-14.9%)、3 pair 個別 (-14.72% / -15.15% / -14.87%) が高い一貫性を示し、有意閾値 max(2σoff,1%)=1.18% の 12.6 倍。PSNR guard も pass (on 36.143 dB ≥ off 36.121 dB − 0.05、Δ +0.022 dB)。採用、`RadixScatterKind` の default を `SimdBallot` に flip、`cargo test --workspace --release` 全 pass。

positiverank: highadopted-default-flip-radix-scatter-simd-ballot第 1 軸第 3 軸m4a5radix-scattersimd-ballottile-binsort-paritylegogpu-gateadopteddefault-flip

Δ PSNR

12.5k 同一 session 交互 A/B n=3: on **36.143 dB** (36.15227 / 36.05730 / 36.21933) vs off **36.121 dB** (36.19775 / 36.01755 / 36.14695) = **+0.022 dB**。task 指定 guard (on mean ≥ off mean − 0.05 dB) に **pass** (+0.022 > -0.05)。config header の絶対 guard (36.202 ± 0.1 dB、帯 [36.102, 36.302]) にも on/off とも **pass**。final splats は on 408,084 (408,408 / 409,074 / 406,770) / off 409,363 (408,928 / 411,049 / 408,113) で on が -0.31% 少ない (既存 atomic 非決定性 chaos の範囲内、方向は一貫していない)。sort parity は `tile_offsets` で byte-exact だが、同じ parity report は `sorted_idx` の 0.217% (2105/969838) に既知の tie-order 非決定性を記録しており、これが rasterize 順序ひいては atomic 加算順序に伝播するため end-to-end の PSNR は parity だけでは pin されない — したがって観測された小さい非方向性の PSNR 散らばりは想定内であり、M2 Tier1 gate (p3-tier1-bit-exact) が観測したような系統的分離は見られない

Δ Wallclock

12.5k full run 同一 session 交互 A/B n=3: **off 149.883s (σ 0.591%) → on 127.530s (σ 0.794%) = -14.914%**。3 pair 個別 Δ は -14.72% (r1) / -15.15% (r2) / -14.87% (r3) とレンジ 0.43 pt の高い一貫性。有意閾値 max(2σ_off,1%) = 1.182%、実測 Δ は**その 12.6 倍**。σ 非対称比 1.34× (off<on) は汚染の典型署名とされる 3× を大きく下回り、on 側が GPU 律速でむしろ host jitter に鈍いという機構と整合する。replay bench (p3-radix-ballot 旧版、production default stack、n=3、GPU 専有未確認) の -12.9%〜-13.3% という directional 参考値とも整合し (12.5k full run のほうがやや大きい -14.9%、407k 固定 checkpoint 断面と 12.5k 平均 pair 数分布の違いで説明可能)、forward_submission=per_stage での radix 単独 gpu_ms -63.7% とも方向・大きさの両方で整合する

Impact

tasklist A5 (radix は帯域 36% の latency 律速と算術証明済み) の実装検証。既存 O(lid) 逐次 threadgroup memory scan を simdgroup ballot 2 段化に置換し、BackendConfig `radix_scatter` の enum variant `simd_ballot` として追加、**2026-08-30 M4 GPU gate で default に採用**。sort parity は unit test 3 本 (境界サイズ 0/1/255/256/257/1234/100000、ties 多発 n=5000、3 種の radix_scan 実装すべて) と本番規模 (407,267 splats) `splat bench --parity` の両方で bit exact PASS。**12.5k Lego 同一 session 交互 A/B n=3 (off-r1→on-r1→off-r2→on-r2→off-r3→on-r3、独立 10s load sampler で汚染監視、binary sha256 は series 前後で不変) で train elapsed 149.883 → 127.530s = -14.9%**、3 pair 個別 (-14.72% / -15.15% / -14.87%) が高い一貫性を示し、有意閾値 max(2σ_off,1%)=1.18% の **12.6 倍**という大差で通過。σ は off 0.59% / on 0.79% (非対称比 1.34×、汚染の署名である 3× を大きく下回る)。**PSNR guard も pass** (on mean 36.143 dB ≥ off mean 36.121 dB − 0.05 dB、Δ +0.022 dB、両 arm とも config header の絶対 guard 36.202±0.1 dB にも収まる)。final splats は on 408,084 / off 409,363 で -0.31% (既存 atomic 非決定性 chaos の範囲内)。session 開始時の ambient load 18.86〜22.8 (Spotlight `mediaanalysisd`/`mds_stores` 再インデックス、reboot 後) という p2-s3 が破棄基準にした汚染クラスの中で実施したが、同一 session 交互設計と 3 pair の高い一貫性 (レンジ 0.43 pt) がこれを吸収したことを §0 で示す。**結論: 採用。`RadixScatterKind::default()` を `SimdBallot` に flip、`cargo test --workspace --release` 全 pass**。

本文

tasklist A5 (`tile_bin.metal:464-475`) が指摘した「radix scatter の local rank 計算が O(lid) 逐次 threadgroup memory scan で latency 律速」を、simdgroup 内 simd_ballot + popcount (段1) と simdgroup 間の小さい exclusive prefix (段2、GROUP_SIZE/32=8 simdgroup) に置換した新 kernel radix_scatter_ballot で検証した。罠 (tasklist 記載どおり): sentinel RADIX_BUCKETS (=16=0b10000) は RADIX_BITS (=4) の下位ビットだけを見ると digit 0 (0b0000) と区別がつかない (16 & 0xF == 0)。同一 digit マスクの初期値を simd_ballot(valid) にして無効 lane を明示的に除外することでこれを回避した (実装コメント + unit test の境界サイズ 255/256/257 が pin)。2026-08-30 の 12.5k full run GPU gate で採用、default flip 済み。

0. 12.5k full run gate — 計測環境 (ambient load 汚染クラスの中での実施)

電源 / 機体: AC 接続 (`pmset -g batt` で series 開始前・各 run 前後・series 終了後まで一貫して `AC Power`、driver 自身が battery 検出で即中断する gate を内蔵)、M4 Max。GPU 権は main から付与済み、他 agent の GPU 使用は無し
**ambient load 汚染クラス** (p2-s3 が破棄基準にした種類): series 開始時点で 1 分 load average **18.86 → 22.8** まで上昇。原因は `mediaanalysisd` (CPU 201〜280%) / `mds_stores` (55〜71%) / `apfsd` (55〜66%) — 直近の reboot (uptime ~3h) 後の Spotlight 再インデックスで、p2-s3 が明示的に挙げた汚染源と同型。`mdutil` での一時停止は sudo 権限が無く不可
1 回目の起動を中断し撮り直した: 既定の `LOAD_LIMIT=6.0`/`QUIESCE_MAX=90` (15 min cap) で起動したところ、ambient がその閾値を超えたまま推移しており quiesce が収束する見込みが無いと判断 (advisor レビュー指摘: 15 min×6 run の待ちが同一 session 内の緩やかな load 低下と交絡し、後半 run ほど有利になるドリフトを自ら作ってしまう)。**学習中の run が 1 本も始まっていない時点で** driver プロセスと独立 load sampler を kill し (sampler の孤児化を mtime 停止で確認)、`LOAD_LIMIT=24`/`QUIESCE_MAX=8` (80s cap、ambient に合わせる) で撮り直した。破棄された学習データは無い
**採用した規律 (`s3-gate-abbaab.sh` の「ambient が高い日は LOAD_LIMIT を上げ、run 内 load で事後判定する」を踏襲)**: ① quiesce 待ちの上限を ambient に合わせて短くし run を back-to-back に保つ (交互 A/B の要点は「ドリフトを両 arm に均等に配る」ことなので、run 間の空白を長くするほど不利)、② 独立 10s sampler (`runs-logs/m4-12500-loadsamples.log`) で series 全体の load を記録し、各 run の `pre_date`/`post_date` 窓と突き合わせて run 単位の load 平均/最大を事後計算 (p3-tier1-bit-exact が「記録していない」と自己批判した穴を埋める)
run 窓内 load 平均 (in-window mean、独立 sampler 由来): off: r1 17.45 / r2 15.40 / r3 13.38 (series を通じて単調に低下)。on: r1 13.85 / r2 12.78 / r3 14.26。off 平均 15.41 は on 平均 13.63 よりやや高いが (série 全体で load が下がっていく中で off が各 pair の前半に来るため)、**r3 だけ on (14.26) が off (13.38) より高い**にもかかわらず r3 の Δ (-14.87%) は他 2 pair (-14.72% / -15.15%) と同水準 — load の相対関係が逆転しても効果量が変わらないことが、Δ が load ドリフトの artifact ではなく実効果であることの直接証拠になる
binary provenance: 全 6 run は単一 binary (sha256 `ff46e94ed9b0361dbf8f6a556222067e8b12563dc98df52c1bf47a80ebfd8117`、series 開始前・終了後の両方で計測し一致確認) — `p3-tier1-bit-exact` が撮り直しの原因にした binary 差し替え問題は本 gate では発生していない。series 実行中に main 側 HEAD が a238179 → d132cce (docs-only、`docs/strategy/2026-09-seminar05-milestones.md` 1 行追加) に進んだが `config.rs`/`tile_bin.rs`/`util.rs` に差分無く、binary sha256 の不変で無関係と確認済み
flag 実測確認: 各 log の `[backend] BackendConfig { … }` 行から `radix_scatter` を抽出し、off-r1/r2/r3 が `LinearRank` (3/3)、on-r1/r2/r3 が `SimdBallot` (3/3) であることを確認 — 意図した arm が正しく走っていることの直接証拠
driver script (新規、汎用化): `splat/scripts/gate-ab-n3.sh <off_prefix> <on_prefix> <run_prefix>` — `s3-gate-abbaab.sh` を任意の A/B gate に使えるよう一般化。各 run 前後で `date +%s.%N`/`uptime`/`pmset -g batt` を `.meta` に記録、battery 検出で即 `exit 2`、series 全体を通す独立 load sampler、series 完了を sentinel file (`<run_prefix>-gate.DONE`) で通知 (`pgrep -f <script名>` によるポーリングは**ポーリングコマンド自身の argv にスクリプト名の文字列が含まれ続けるため自己マッチし無限ループになる**ことを実地検証済みで、それを避ける設計)
汚染疑いによる再実行: **無し**。σ 非対称比 1.34× (閾値相当の 3× を大きく下回る)、3 pair の Δ レンジ 0.43 pt という高い一貫性、および上記 r3 の load 逆転ケースが効果量を変えなかったことから、汚染疑いでの pair 再実行は不要と判断した
**session 健全性チェック — off arm が既知 baseline を再現**: off mean **149.883s** は `p2-s3-iteration-pipelining` の depth2 baseline (151.70s、-1.2%) および `p3-tier1-bit-exact` の off arm (155.40s、-3.6%) の近傍にある。ambient load 20 超の中でも同一 default スタックの過去 2 回の独立 gate と整合する値が出たことは、`p2-s3-iteration-pipelining` §3 が「同一 session の off arm が S2 gate 当日の S2 arm を +0.3% で再現」を session 健全性の証拠として使ったのと同じ論法で、本 session が汚染下でも壊れていなかったことの直接証拠になる

1. 実装 — BackendConfig flag-gate、既存 3 call site すべてに配線

新 kernel: `radix_scatter_ballot` (`shaders/forward/tile_bin.metal`)。buffer 署名・threadgroup memory 長 (1024 byte) は既存 `radix_scatter` と同一なので、Rust 側は PSO を差し替えるだけで済む
flag: `BackendConfig::radix_scatter: RadixScatterKind` (旧 default `LinearRank` → **本 gate で `SimdBallot` に flip**)。`apply_backend_config` → `GpuTileBinner::use_radix_scatter_ballot: Cell<bool>` → `scatter_pso()` helper
call site 網羅: `scatter_pso()` は `radix_sort_core` の legacy CPU-scan path、GpuFlat path、`encode_radix_passes_hier` (S2 hierarchical、production default) の **3 箇所すべて**で使われるため、`radix_scan` の値に関わらず一貫して切り替わる (test `radix_sort_ballot_scatter_matches_across_scan_kinds` で pin)
コンパイラ規約: `xcrun metal -c` で単体コンパイル確認 (warning は既存の未使用定数 1 件のみ、本変更と無関係)。`cargo build --release` workspace 全体 clean

2. sort parity (bit exact) — unit test 3 本 + 本番規模 splat bench --parity

test / 経路	何を pin するか	結果
`radix_sort_ballot_scatter_matches_linear_rank`	n ∈ {0,1,255,256,257,1234,100000} で keys/idx が既存実装と bit exact。255/256/257 は sentinel collision trap (partial group で無効 lane が混じる境界) を明示カバー	PASS (全 7 サイズ)
`radix_sort_ballot_scatter_stability_ties`	n=5000, key %100 の ties 多発ケースで stability	PASS
`radix_sort_ballot_scatter_matches_across_scan_kinds`	3 call site (Cpu/GpuFlat/GpuHierarchical scan) すべてで flag が一貫して効くこと	PASS (3 scan kind 全て)
`splat bench --parity` (本番規模、407,267 splats、Lego 12.5k checkpoint)	`tile_offsets` byte 一致 + grad 5 種 tol PASS	PASS (下表)

PARITY 行 (本番規模 407,267 splats)	結果
loss_value	baseline=0.004296378 candidate=0.004296381 diff=3.260e-9
sorted_idx	INFO (非 gate、既知の tie-order 非決定性 — 2105/969838 = 0.217% 差、`p2-bench-harness-calibration` と同じ既存の性質で本変更由来ではない)
tile_offsets	PASS (exact byte equality, n=2500)
means_grad	PASS (max_abs_diff=1.080e-5)
log_scales_grad	PASS (max_abs_diff=4.642e-8)
rot_quats_grad	PASS (max_abs_diff=1.611e-7)
raw_opacities_grad	PASS (max_abs_diff=2.539e-8)
sh_coeffs_grad	PASS (max_abs_diff=2.618e-7)
PARITY OVERALL	PASS

workspace 全体 test / build も clean (default flip 後に再確認済み)

default flip 後の `cargo build --release` (workspace) / `cargo test --release --workspace` の両方が全 pass (splat-metal 86 + 2 ignored、splat-train-v1 70、colmap-reader 8、splat-cli 8、splat-io 7、splat-summary 1、他 crate 0、失敗 0)。既存 sort parity test にも regression なし。

3. replay bench screen — production default stack (chained) で n=3 (方向性の先行確認、GPU 専有は当時未確認)

arm (`splat bench`, iters=200, warmup=20, n=3)	median ms/iter	mean ms/iter	σ	GPU busy% (median)	busy ms/iter	sync-tax ms/iter
off (`radix_scatter=linear_rank`)	15.545	15.556	0.18%	82.3%	12.785	2.749
on (`radix_scatter=simd_ballot`)	13.536	13.489	0.82%	79.4%	10.749	2.787
Δ	-12.9%	-13.3%	—	-2.9 pt	-15.9%	+1.4%

この replay bench は 12.5k full run gate (§0) によって符号・大きさとも確証された

旧版 finding はこの n=3 を「off×3→on×3 の逐次 run で GPU 専有未確認、σ 非対称 4.5×」を理由に directional 参考値にとどめていた。§0 の 12.5k full run gate (同一 session 交互 A/B、独立 load sampler つき) は -14.9% を計測し、この replay bench の -12.9%〜-13.3% と符号・大きさの両方で整合する (12.5k full run のほうがやや大きいのは、407,267 splats 固定 checkpoint の pair 数分布が 12.5k を通した平均よりやや大きい可能性がある、という下記 callout の予想どおり)。したがって本節の数値はもはや未確定ではなく、独立した full run gate によって裏付けられた一致証拠として読む。

replay bench は refine を含まない — 12.5k full run gate (§0) で確認済み

`splat bench` は `train_step` を N 回呼ぶだけの fixed-workload replay で、refine/MCMC tick を含まない (S3 finding と同じ制約)。今回の測定は 407,267 splats (Lego 12.5k 到達後の checkpoint) を固定して回しているため、radix の pair 数分布は 12.5k 全体を通した平均的な pair 数 (splat 数が 0 → 407k へ増える過程の平均) よりやや大きめに出ている可能性があった — §0 の 12.5k full run gate (-14.9%) はこの replay bench (-12.9%〜-13.3%) を上回る短縮を示しており、この予想と整合する。

4. radix 単体の gpu_ms — forward_submission=per_stage での補助計測 (参考値、n=1)

arm (forward_submission=per_stage、iters=200、n=1)	ts_fwd_radix_sort total_ms	gpu_ms/call	ms/iter (全体)
off (`radix_scatter=linear_rank`)	717.94	3.32	16.468
on (`radix_scatter=simd_ballot`)	286.63	1.21	14.077
Δ	-60.1% (total)	-63.7%	-14.5%

per_stage は production の経路ではない — 「radix だけの寄与」を切り出すための補助計測

production default (`forward_submission=chained`, S2) では radix の全 pass が forward 全体の 1 CB / 1 wait に畳まれ、`ts_fwd_radix_sort` のような単独 label は取れない (`ts_forward` に project/emit/radix/extract/rasterize がまとめて計上される)。radix だけの gpu_ms を切り出すため、この節だけ legacy `forward_submission=per_stage` (S2 以前の経路、production では使わない) で計測している。ts_fwd_radix_sort は histogram + hierarchical scan + scatter の全 pass (11〜16 pass) を含む合計であり、scatter 単体の寄与ではない点に注意 — とはいえ scatter が O(lid) 逐次 scan の中で最も高コストな kernel だった (tasklist の latency 律速の主張と整合) ため、この -63.7% の大半は scatter 由来と推定される。chained mode の `ts_forward` gpu_ms は 5.452 → 3.336 ms/iter (-38.8%) で、上記 per_stage の縮小方向と整合する。この n=1 計測も §0 の 12.5k full run gate (-14.9%) と方向が一致する。

5. 12.5k full run GPU gate — 実測 (採用)

実行順	arm	config	train elapsed (s)	PSNR (dB)	final splats	run 窓内 load1 平均 / 最大
1	off (A)	m4-12500-off-r1	150.90	36.19775	408,928	17.45 / 21.30
2	on (B)	m4-12500-on-r1	128.69	36.15227	408,408	13.85 / 18.37
3	off (A)	m4-12500-off-r2	149.47	36.01755	411,049	15.40 / 17.98
4	on (B)	m4-12500-on-r2	126.82	36.05730	409,074	12.78 / 17.36
5	off (A)	m4-12500-off-r3	149.28	36.14695	408,113	13.38 / 15.64
6	on (B)	m4-12500-on-r3	127.08	36.21933	406,770	14.26 / 17.66
mean	off	—	149.883 (σ 0.591%)	36.1207	409,363	15.41
mean	on	—	127.530 (σ 0.794%)	36.1430	408,084	13.63
Δ	—	—	-14.914%	+0.0223	-0.31%	—

有意性 — 閾値 max(2σ,1%) を 12.6 倍超過、3 pair の一貫性が極めて高い

off 側 sample σ (n=3, n-1 分母) は 0.591%、on 側は 0.794%。有意閾値は max(2σ_off, 1%) = 1.182%。実測 Δ は -14.914%、閾値の 12.6 倍という大差。3 pair 個別の Δ は -14.72% (r1) / -15.15% (r2) / -14.87% (r3) でレンジわずか 0.43 pt — p2-s3 (採用、レンジは pair 間で比較的広かった) や M2 Tier1 (棄却、閾値に肉薄) と比べても際立って一貫している。σ の非対称比は 1.34× (off < on) で、汚染の典型署名とされる 3〜4.5× (M2 Tier1 4.66×、p3-radix-ballot 旧版 replay bench 4.5×) を大きく下回り、on 側が GPU 律速でむしろ host jitter に鈍いという機構と整合する健全な非対称。

PSNR guard — pass、systematic な分離は見られない

on の PSNR 3 値 (36.15227 / 36.05730 / 36.21933) と off の 3 値 (36.19775 / 36.01755 / 36.14695) は完全分離しておらず (on-r1 < off-r1、on-r2 > off-r2、on-r3 > off-r3 と方向が混在)、mean Δ は +0.022 dB。task 指定 guard (on mean ≥ off mean − 0.05 dB) に pass。config header の絶対 guard (36.202 ± 0.1 dB) にも on/off とも帯内で pass。M2 Tier1 gate (p3-tier1-bit-exact) が観測した n=3 完全分離・系統的 PSNR 低下 (-0.065 dB、guard 抵触) とは対照的。sort parity は `tile_offsets` で byte-exact だが `sorted_idx` は既知の tie-order 非決定性 (0.217%、§2 表) を含み、これが rasterize/atomic 加算順序に伝播するため parity の byte-exactness は end-to-end PSNR を pin しない — 観測された小さい非方向性の散らばりはこの既知の非決定性の範囲内として想定どおり。

ambient load 汚染クラスの中での実施 — 交互設計と per-pair 一貫性がこれを吸収したと判断する根拠

series 開始時の 1 分 load average は 18.86〜22.8 と、p2-s3 が round 1 を全破棄した汚染クラス (Spotlight `mediaanalysisd`/`mds_stores` 再インデックス) と同型だった。`sudo` 権限が無く `mdutil` での一時停止はできなかったため、①交互 A/B 設計で drift を両 arm に均等に配る、②quiesce 待ちを ambient に合わせて短く保ち run を back-to-back にする (長い quiesce 待ちのほうが「後半 run ほど有利」という別種のドリフトを生む、advisor レビュー指摘)、③独立 load sampler で run 単位の load を事後記録する、の 3 点で対応した。r3 pair で on の load (14.26) が off (13.38) より高いにもかかわらず r3 の Δ (-14.87%) が他 2 pair と同水準だったことは、観測された Δ が load 差の artifact ではなく実効果であることの直接証拠になる。ただし load sampler は 10s 間隔のスナップショットであり、run 内のより短い時間スケールの CPU バーストまでは捉えていない点は限界として残す。

6. 結論 — 採用、default flip

結論: **採用**。`splat/crates/splat-train-v1/src/config.rs` の `RadixScatterKind::default()` (`#[default]` 属性) と `BackendConfig::default()` の手書き実装の両方を `LinearRank` → `SimdBallot` に flip。enum doc の verdict を「未検証 (GPU gate 前)」→「採用 (default)」+ 実測値に更新 (3 点セット規約)、`LinearRank` 側にも敗退 verdict を追記
test 確認: flip 後に `cargo build --release` (workspace) / `cargo test --workspace --release` を実行し、全 crate 0 failure (splat-metal 86+2ignored / splat-train-v1 70 / 他 0) を確認
config への影響 — `splat check` 全 config sweep 実施済み (S3 前例と同型): S3 の default flip 前例 (p2-s3-iteration-pipelining §0) にならい実施。`radix_scatter` を明示指定した config は 291 本中 12 本のみ (本 finding の gate 用 6 本 + M1 replay 用 4 本 + parity 2 本)。残り 279 本は今後すべて新 default (`SimdBallot`) で走る。`./target/release/splat check --config <path>` を全 291 config に実行した結果 **215 PASS / 76 FAIL**、失敗した 76 本すべての理由を個別確認したところ (a) `[bench]` section を持つ bench-schema config (`check` は train schema 専用で対象外)、または (b) `[backend]` のみの parity-candidate 差分ファイル (`missing field 'experiment'`、`splat bench --parity` 専用で完結した config ではない) のいずれかで、**`radix_scatter`/default flip に起因する新規失敗は 0 件**。train config は全 215 本が load 成功
次の一手: M5a (SSIM float4 化) など後続 milestone は本 flip 後の stack を土台にする。msplat 等価比較・Pareto v3 (M7) の入力にも本 -14.9% を反映する