row-major コピー (copy_across_layouts / to_owned): ゲートなし・列分割で書き戻しが false sharing・直列 first-touch #92

問題

linalg::copy_across_layouts (linalg/mod.rs:77-102) は、row-major の QR / column-pivoting QR / LU (部分ピボット・完全ピボット) が column-major の作業領域へ往復コピーするための関数です。fork 固有のコードです (PATCHSET "Row-major QR layout adaptation", "Row-major col-pivoting QR", "Row-major LU", "Regions dispatch through the caller's worker group")。高並列では次の問題があります。

1. cost ゲートがない。 n_tasks = min(p, ncols) で、往復 2 回とも p 幅の region を開きます。行列側の floor は p に依存しない 64*64 要素 (row_major_copy_pays) だけです。
   • 例: 64×64 を p = 64 で処理すると、64 要素のタスク 64 個の region が 2 回開きます。factor 本体は floor で Seq になるのに、コピーだけが並列オーバーヘッドを払います。
2. 書き戻しで false sharing が起きる。 書き戻し (copy_across_layouts(A, work, par)) の dst は row-major ですが、列で分割しています。1 タスクの列幅が cache line (f64 で 8 要素) を下回ると、隣のタスクが同じ行の同じ line に書きます。
   • 4096×256、p = 64: 4 列/タスクで、1 line を 2 スレッドが書きます。
   • 1024×64、p = 64: 1 列/タスクで、1 line を 8 スレッドが書きます。
   • 往路の読み込みも同じ理由で、line の読み込み量が最大で 8 / (ncols/p) 倍になります。
3. 初期化と first touch が直列。 作業領域 alloc::vec![zero(); m*n] は呼び出しスレッドが作ります。c64 ではここで直列の memset になり、ページが 1 NUMA ノードに偏ります。f64 では calloc になる可能性があります (std の IsZero 特殊化、推測)。
4. MatRef::to_owned の tile staging が直列。 mat/matref.rs:1631-1645 は Par::Seq で、PartialPivLu::new などの solver 経由 (solvers.rs:1096) はここを通ります。factor 本体は 1/p で縮むのに O(mn) の直列部分が残り、ページも呼び出しノードに載ります。
   • 割合の見積もり (推測): 4096² f64 でコピー約 30 ms (1024² の 2.0 ms からの外挿)、64T の LU は数十 ms。

upstream にはこの経路自体がありません (row-major をそのまま factor する)。

確認済み / 推測

• 確認済み (コード): 1、2 の分割の形。4 が Seq であること。3 の vec! が呼び出しスレッドで実行されること。
• 推測: false sharing の実害の大きさ、NUMA 偏りの影響、4 の割合。

副次所見 (並列化とは別)

PATCHSET "Row-major LU, partial pivoting" の行には "full-pivoting flavour is deliberately not adapted" とありますが、10ee1c9 以降のコード (lu/full_pivoting/factor.rs:498-518) は adapt しています。ledger とコードが食い違っています。

計測計画 (faer#90 の計測が終わってから)

• lu_in_place / qr_in_place / col_piv_qr を row-major で、f64/c64、64×64、256×256、1024×64、4096×256、1/8/16/32/64T で計ります。
• コピー region 単体の時間を測り、perf c2c で HITM を確認します。
• partial_piv_lu / qr の solver 経由を 4096² で計り、to_owned の割合と numastat を確認します。

推奨

修正します (1、2 は計測を待たずに設計で直せます)。

• コピーを memcpy レートの region_pays でゲートする。
• 分割単位を cache line の倍数にする。row-major 側が dst のときは行で分割する。
• to_owned の solver 経由に par を渡す。
• full-pivoting の adapt は残すか消すかを決め、ledger をコードに合わせる。

親: #95

🤖 Generated with Claude Code