Repository navigation
fork の並列化の高並列 (32〜64 スレッド) スケーラビリティ監査 #95
Description
目的
fork 独自の並列化・分割・閾値・スレッド配分の変更が、高並列 (p = 32〜64 以上、複数 CCD/NUMA) で破綻しないかを洗い直します (メンテナ指示)。
きっかけは #90 です。block Householder apply の列分割では、列タスクごとに V 全体を読み直すので、V の読み込み量が p に比例します。8T の Zen5c でもすでに 8〜16% 遅いセルがあります。
方法
- 対象:
origin/main=0a4713aを読み、upstream base0ecd846(PATCHSET の Upstream base) との diff のうち、並列化に関わるものをすべて見ました。PATCHSET の KEEP / EXPERIMENT 行と照合しています。 - 範囲: householder・thread・cost は直接読みました。matmul/三角、LU/QR/Cholesky、EVD/SVD/sparse は分担して読み、主要な主張 (tridiag の合算、sparse の workspace、三角積の無条件呼び出し、copy の分割、full-pivoting の adapt) はコードで再確認しました。
- 計測: していません。broccoli で Block Householder apply re-reads the whole basis V once per column task; traffic grows with the thread count #90 の計測が進行中のためです。各子 issue の計測計画は Block Householder apply re-reads the whole basis V once per column task; traffic grows with the thread count #90 の計測の後に実施します。
- 比較: OpenBLAS / LAPACK との対照は記憶によるもので、ソースは読んでいません。
評価の観点
- 共有オペランドの読み込み量が p に比例する
- p 個の部分バッファを逐次に合算する
- タスク数の固定上限や、p と無関係な分割数で使われないスレッドが出る
- 粒度が細かすぎる、または閾値が p を考慮しない
- 同期・競合が p に比例する
- NUMA/CCX をまたぐ共有データ
結果表
「確認」の列: 確 はコードで確認済み、推 は推測 (未計測)。
| 場所 / PATCHSET 行 | 分割の形 | p に対するコスト | 危険度 | upstream / OpenBLAS との違い | 推奨 | 確認 | issue |
|---|---|---|---|---|---|---|---|
householder.rs:654-797 一般形 block apply の列分割 / "Thread-budget column split" |
n_tasks = min(p, K) の列タスクが、各自 V^H C_j と C_j -= V W_j を実行 |
V の読み込み ≈ 2·p·m·k。部分和はなし |
高 | upstream は min(p, K, 4) 列タスク × 内側 p/4 で、V の読み直しは最大 4 倍。OpenBLAS (dlarfb → BLAS-3) は V を 1 回 pack して共有 |
修正 | 確 (8T で実害あり) | #90 |
utils/cost.rs の全ゲート / "Parallel floors …" 3 行、"Architecture keyed …" |
判定は estimate ≥ 3·s·cost(min(p,6))、通れば全幅 |
floor が p によらず一定、1 スレッドあたりの仕事は estimate/p、実際の dispatch cost は p とともに増える |
中〜高 (全体の土台) | upstream は固定の要素数閾値 (p 非依存) で、fork は 8T 計測に合わせて floor を下げた。OpenBLAS はサイズに比例してスレッド数を減らす | 計測 → 修正 | 確 (表と判定) / 推 (64 幅のコスト) | #91 |
linalg/mod.rs:77 copy_across_layouts、matref.rs:1631 to_owned / "Row-major QR/LU/col-piv QR", "Row-major to_owned" |
列を p 分割、ゲートなし。to_owned は Seq | 書き戻しの false sharing は ncols/p < 8 (f64) で発生。直列 first-touch は O(mn) |
中〜高 | upstream にはこの経路がない | 修正 | 確 (分割・ゲートなし) / 推 (実害) | #92 |
evd/tridiag.rs:390-461 |
n × p の部分和を逐次合算 |
合算 p·rem 対 並列部 rem²/2p。損益分岐 p* ≈ √(rem/2) |
高 (絶対性能) / fork 起因は低〜中 | 構造は upstream と同じで、fork は入口を下げた | 計測 → 修正 | 確 / 推 (p*) | #93 |
matmul/mod.rs:1000-1056 matvec_colmajor |
m × p の部分和を毎回確保して逐次合算 |
p·m |
中 | upstream 構造。OpenBLAS の dgemv_n は行分割 |
計測 | 確 | #93 |
sparse/linalg/matmul.rs:107 |
Seq でも m × p workspace を呼び出しスレッドが memset |
m·p (直列) |
中〜高 | upstream 構造。fork のゲートは幅を直していない | 修正 | 確 | #93 |
householder.rs:279-317 upgrade の deep 分岐 / "Row-split reduction in the compact-WY factor's deep half" |
行を p 分割、n×n×p の部分和を逐次合算 |
合算 p·n²/2。rows ≥ 4p なので仕事の約 1/8 以下 |
低 | fork 固有 | 問題なし (監視) | 確 | #93 |
matmul/triangular.rs:733 三角積の x86 カーネル |
ゲートなしで gemm(.., p) |
小さな積でも p 全員が同期 | 中 | upstream も同じ。fork の floor 統一で取りこぼし | 修正 | 確 | #94 |
matmul/mod.rs:1162 K==1 rank_update |
ゲートなしで列を p 分割 | 同期 ∝ p | 低〜中 | upstream 構造 | 修正 | 確 | #94 |
| native GEMM / spicy_matmul / "Native gemm thread budget in flops" | 1 section と数えて p 全体を渡す | 実際のセクション数は 2·⌈k/kc⌉ |
中 | upstream は 32³ MAC で無条件 (fork の方が保守的) | 計測 | 確 (sections = 1) / 推 (カーネル内) | #94 |
householder.rs:520-536 階数 1 の腕を一般形へ / "Threaded rank-one Householder apply" |
N=1 の apply を列分割 | v (m 要素) の読み込みは p 倍だが小さい。タスク数は min(p, K) で、パネル幅 K ≤ 16 のため p = 64 では内側 p/K |
低 | upstream は N=1 で Seq | 問題なし (#90 の修正で一緒に見直す) | 確 | #90 |
utils/mod.rs:164 for_each_with_par |
内側の幅は p / n_jobs の切り捨て |
最大 n_jobs - 1 スレッドが遊ぶ |
低 | fork の helper | 問題なし (余りの配分は将来) | 確 | — |
utils/mod.rs:35 join_raw の幅 / "Width split in join_raw" |
p - p/2 と p/2 |
正しい | なし | upstream は両側に p - p/2 (過剰) |
問題なし | 確 | — |
| LU 部分ピボット trailing floor / swap stage | 再帰レベルごとにゲート、swap は列幅比例の join_sized |
判定は #91 に依存 | 低〜中 | upstream は常に par。OpenBLAS getrf_parallel は look-ahead + 融合 |
#91 で計測 | 確 | #91 |
| bidiag / Hessenberg / full-piv LU / col-piv QR / BK の 1 step 1 region | step ごとに p 幅の region | n 回の barrier。fork の floor は upstream より低い | 低〜中 | LAPACK は BLAS-3 化 (laqps, labrd) |
#91 で計測 | 確 / 推 | #91 |
| D&C (bidiag SVD / tridiag EVD) の join と merge GEMM | 2 分木で幅を半分ずつ | 葉は約 n/128 (SVD) / n/64 (EVD) 個で、p > 葉数なら遊ぶ。secular は直列 | 中 (絶対性能) / fork 起因はなし | upstream と同じ構造。fork はゲート追加でむしろ改善。LAPACK も gemm 外は直列 | 問題なし (将来の課題) | 確 | — |
| Schur, QZ, gen_hessenberg, sparse cholesky/lu/qr, Cholesky | par の受け渡しのみ |
— | なし | — | 問題なし | 確 | — |
横断的な所見: NUMA/CCX を意識したスレッド配置や first-touch は、fork にも upstream にもありません。#92、#93 の直列確保・初期化がその典型です。
計測の順序 (#90 の計測が終わってから)
- 並列ゲートの dispatch cost が幅 6 で頭打ち、通れば常に全幅: p=32〜64 で floor 付近の region が過剰に開く #91-1: 空 section の dispatch cost を幅 2〜64 で計測 (outside / in-pool / Team)。他すべての前提です。
- row-major コピー (copy_across_layouts / to_owned): ゲートなし・列分割で書き戻しが false sharing・直列 first-touch #92: row-major コピー (
perf c2c) - p 個の部分バッファを逐次合算する reduction (tridiag, matvec_colmajor, 疎×疎, compact-WY upgrade) の高並列スケーリング #93: tridiag /
eighのスケーリング → matvec、疎×疎 - cost ゲートなしで全幅を渡す経路: 三角積の x86 カーネル、K==1 の rank_update、GEMM のセクション数過少計上 #94 と 並列ゲートの dispatch cost が幅 6 で頭打ち、通れば常に全幅: p=32〜64 で floor 付近の region が過剰に開く #91-2: floor 付近のスケーリング (GEMM、LU、Cholesky、EVD/SVD 前段)
いずれも 1/8/16/32/64T。broccoli (64 コア) でスケーリング曲線を取り、回帰ゲートは evo で campaign protocol (boost off) で取ります。
子 issue
- Block Householder apply re-reads the whole basis V once per column task; traffic grows with the thread count #90 block Householder apply の V 読み直し (既存)
- 並列ゲートの dispatch cost が幅 6 で頭打ち、通れば常に全幅: p=32〜64 で floor 付近の region が過剰に開く #91 cost モデル: dispatch cost が幅 6 で頭打ち、全幅のみ
- row-major コピー (copy_across_layouts / to_owned): ゲートなし・列分割で書き戻しが false sharing・直列 first-touch #92 row-major コピーの分割とゲート
- p 個の部分バッファを逐次合算する reduction (tridiag, matvec_colmajor, 疎×疎, compact-WY upgrade) の高並列スケーリング #93 p 個の部分バッファの逐次合算
- cost ゲートなしで全幅を渡す経路: 三角積の x86 カーネル、K==1 の rank_update、GEMM のセクション数過少計上 #94 ゲートなしで全幅を渡す経路
🤖 Generated with Claude Code
Metadata
Metadata
Assignees
Labels
No labels
Activity
shinaoka commentedon Oct 28, 2026
PR #52 (merge
5e45c57) の高並列監査git diff 5e45c57^1 5e45c57を読みました。計測はしていません。結論: revert は不要で、前方修正で足ります。 #52 は、#90 の型 (各タスクが同じ大きなオペランドを p 回読み直す) も、新しい p 比例の部分バッファも持ち込んでいません。逆に、bidiag 本体の高並列での形はむしろ良くなっています。
svd/bidiag.rsのbidiag_blocked_phase/_panel、dlabrd型、パネル 16、残り 128 以下は unblocked)region_pays((m-p)(n-p), 2)で判定。各 step の積は 2 本 (y = A^H uはmatvec_rowmajorの行分割、x = A rはmatvec_colmajor)。補正項はすべてPar::Seq。trailing update はパネルごとにmatmul2 本for_eachの fused 更新 (各タスクが長さ m のベクトル 3 本を読むので、ベクトルの読み込みは3·m·p) が GEMM 2 本に置き換わった。X/Y の scratch は p に依存しないx = A rのmatvec_colmajorm × pの部分和を毎回MemBuffer::newで確保して逐次合算p·m対 並列部m·n/p。損益分岐 p ≈ √nz2 = A22 wk^Hが同じ経路で、step あたりの呼び出し回数も同じ)for_each(nthreads)列分割をそのまま使用3mpが行列本体128mを上回るupgrade_householder_factorのNARROW_BASIS(n ≤ 8 なら呼び出しスレッドで内積)rows·n²/2、列を最大 n 回読む。rows と p を見ない固定規則dlasq1と同じ構造)pub use spindle、crate doc、Par::Rayondoc)with_lock(n)を推奨with_lock(64)だと、直列区間 (dqds、Amdahl 部) で最大 63 スレッドが一定時間 spin してから眠るwork_rows(列 stride のパディング)計測計画 (#90 の計測の後)
svd_values/svd_thin/bidiag_in_place: f64/c64、n = 256, 512, 1024, 2048 と 4096×256、1/8/16/32/64T。with_lockの有無で比較し、5e45c57^1と5e45c57の pair で取る。NARROW_BASIS: 65536×8 と 262144×8 の QR を 1/64T で、旧 deep 分割と比べる。matvec_colmajorの合算の割合 (p 個の部分バッファを逐次合算する reduction (tridiag, matvec_colmajor, 疎×疎, compact-WY upgrade) の高並列スケーリング #93 の計測で一緒に取る)。🤖 Generated with Claude Code
shinaoka commentedon Oct 28, 2026
Plan for the children of this audit (monitoring side, maintainer delegated the order on 2026-10-29):
shinaoka commentedon Oct 29, 2026
The finding that
lu1024 does not scale (faer#99, broccoli comment, finding 2) is tracked as tensor4all/faer-benchmark#36, fix in tensor4all/faer-benchmark#37. The cause is the harness, not faer: since faer-benchmark#35 the forkluandsolverows calllu_in_placewithPar::Seq. faer's LU gates and team dispatch are parallel onmain(counters in the issue). Not part of #91.shinaoka commentedon Oct 29, 2026
Per-process serial mode at 16T (faer#99 re-measurement): tracked in #107 (probe on branch
fix/team-serial-mode, broccoli 16T run requested).shinaoka commentedon Oct 29, 2026
Follow-up from #109's evo gate: #111 (no heap allocation inside per-step parallel sections).
shinaoka commentedon Oct 29, 2026
MKL / OpenBLAS / fork at high thread counts on broccoli — the two questions
oneAPI MKL 2026.2 is installed here and the campaign's
link-mklarm builds and runs (it links theexplicit layers
libmkl_intel_lp64+libmkl_intel_thread+libmkl_core+libiomp5). Two notes onrunning it:
mkl_set_num_threads()segfaults with this build on this host, so the budget has to beset through
MKL_NUM_THREADS(read back throughmkl_get_max_threads, which works); andMKL_VERBOSE=1reports
oneMKL 2026 Update 2 ... Intel(R) Architecture processors, Lnx 1.59GHz lp64 intel_threadwithDyn:1 FastMM:1 NThr:8on the call — the generic Intel-architecture path, no AVX-512 selection onZen2, and nothing was overridden for the AMD host.
Whole run: EPYC 7702P (Zen2, SMT off, boost 0, governor
performance), fork7e5e9e3, f64, per-cellwhole-L3-domain idle guard, 2 process sets at 64T and 1 set elsewhere (another user's processes sit at
5-9 % on single CPUs today, so wide cells cannot pass the 5 % gate and are recorded with the reading).
(1) Small sizes: does the fork get much slower at high threads? (fast-mode ms, 64T/1T)
No small size blows up. Seven of the eight cells are 0.93-1.02x, i.e. 64 threads cost what one
thread costs; the one cell over 1.2x is
lu128 at 1.40x (0.20 -> 0.28 ms), which is visible butis 0.08 ms. For scale: MKL's small-size behaviour is far worse than ours at n=32, where its threading
overhead alone makes gemm 10x slower than at 1T (0.0067 -> 0.10 ms), and OpenBLAS manages 1.84x on
qr 128. At these sizes the fork is the most thread-insensitive of the three.
One caveat that matters more than any number above: the raw medians showed
gemm 128at 40x slowerat 64T (0.147 -> 6.0 ms). That is the #107 per-process mode, not a size effect — its repetitions went
0.019, 0.019, 15.98, 11.98, 15.98, 0.022, 0.021 ms, i.e. the mode inflates a cell by up to 800x and
it hits small sizes as hard as large ones. Every number in these tables is the fast level (fastest
repetition per process, fastest process per cell); the mode hit 6 of the 64T cells here.
(2) Large sizes: does the fork scale like MKL? (faer/MKL = speedup ratio; <0.8 marked)
Where we match or beat MKL: gemm everywhere, qr at 2048, cholesky at 2048.
gemm 2048is 1.1-1.7xbetter than MKL's scaling and
gemm 4096is parity (1.01 / 0.99 / 0.80).Where we do not:
luat every size (0.46-0.82, and 0.37 at 4096/64T: 4.4x against MKL's 12.1x —this is exactly the subject of #123),
qrat 4096 (0.45-0.71), andcholeskyat 4096 for32/64T (0.79/0.69). OpenBLAS is far off on everything except gemm, so MKL is the right yardstick here.
The
cholesky 2048 64Tcell is listed for completeness only: every repetition there stayed in the #107mode (256 ms against 16 ms at 32T), so it says nothing about scaling. Nothing was measured on a
partition this run.
Raw: per-cell CSVs and the two drivers (
fbenchfor the small grid, three standalone drivers for thelarge one, since the harness's own reference check costs 131 s at n=2048 and cannot be used there).
shinaoka commentedon Oct 30, 2026
Folded into the umbrella #168 (parallel structure of the factorizations). This issue is re-scoped or closed against its items.