perf(amr): source-centric transposed CSR for the coarse–fine fill adjoint
まだ誰も着手していません。
評価
- 難易度
- 5/5
- 見積もり時間
- 1週間以上
- 初心者へのやさしさ
- 45/100
- issue の種類
- リファクタリング
- 明瞭さ
- おおむね明確
- 活発さ
- 活発
- 技術スタック
- julia
調査の方向性
Start with halo_update_adjoint! and the existing (fills, terms) CSR, then review the forward fusion in #84 and descriptor context from #42. Measure schedule rebuild cost and transposed-CSR footprint for both layouts, and run test/exchange_schedule.jl, including its bit-parity and zero-allocation assertions. Done means the adjoint remains the exact transpose, preserves bit parity, and passes both layout checks.
索引モデルが issue の本文から書いたものです。
説明
What
halo_update_adjoint! still runs one scatter-add broadcast per CSR term, and after the forward gather was fused (#84) it is by far the slower half of the exchange. Fusing it bit-identically needs a source-centric transposed CSR built at schedule time; this issue is that work.
Why it was not done in #84
The forward gather is dst-centric and each dst cell is written by exactly one fill, so one broadcast per fill reproduces the per-term loop's arithmetic exactly. The transpose is a scatter, and a fill's term windows collide on shared source cells, so a dst-centric single pass would accumulate into a colliding cell in dst-cell order instead of term order and change the roundoff. Measured on refined forests (x < 0.5, maxlevel 2), counting the scatter-adds a phase issues and how many land on a cell some earlier term of the same fill already wrote:
| forest | phase | fills | scatter-adds | colliding |
|---|---|---|---|---|
| 3D 32³, 8³ blocks | interpolation | 1024 | 77 824 | 40 960 |
| 3D 32³, 8³ blocks | restriction | 64 | 9 216 | 0 |
| 3D 32³, 4³ blocks | interpolation | 4096 | 77 824 | 0 |
| 2D 256², 32² blocks | interpolation | 64 | 3 584 | 1 792 |
| 2D 256², 32² blocks | restriction | 16 | 1 280 | 0 |
Restriction rows never collide, and interpolation rows only collide once the tangential windows are wider than one cell (blocksize ≥ 6). Fusing "only collision-free rows" was considered and rejected: it makes the exchange's cost depend on the blocksize in a way nothing in the API hints at.
The measured lopsidedness
Min-of-N, alternating processes, three rounds, on this machine (macOS/aarch64, Julia 1.12), µs:
| leg | forward (fused) | adjoint (per-term) |
|---|---|---|
3D 32³ / 4³ blocks, BlockField |
677 | 3322 |
| 3D 32³ / 4³ blocks, packed | 672 | 3448 |
| 3D 32³ / 8³ blocks, packed | 205 | 983 |
| 2D 256² / 32² blocks, packed | 14.5 | 46.2 |
So the adjoint is 3–5× the forward on exactly the geometry #84 was aimed at, and #84's acceptance is met on the forward half only.
Shape of the fix
Emit, alongside each phase's (fills, terms) CSR, a transposed CSR keyed by source cell: for every source cell touched by the phase, the list of (dst cell, weight) contributions in the order the current loop applies them — fills in reverse order, terms within a fill in forward order. The adjoint sweep then walks source cells once, accumulating left to right, which is the same accumulation sequence per cell and therefore bit-identical, followed by the dst zeroing pass.
Things to settle before building it:
- Storage. This is cell-granular, not slab-granular: ~78 k contributions for the 3D interpolation phase above, each needing a block index plus a Cartesian index on both ends. That is the descriptor bloat #42/#84's CSR shape was chosen to avoid, and it is rebuilt on every regrid — measure the build cost and the footprint before committing to it.
- Layout independence. Contributions cannot be precomputed as linear indices:
BlockFieldandPackedBlockFieldindex the same cell differently, so the record has to stay (block, CartesianIndex) and the sweep pays the decode. - Acceptance. The exchange must stay the exact transpose of the forward (dot-product identity to roundoff), the existing bit-parity testsets in
test/exchange_schedule.jlmust keep comparing against something that is not a re-written copy of the new loop, and the zero-allocation assertions must hold for both layouts.
Related: #84 (forward fusion), #42 (isbits descriptors).
🤖 Filed by Claude — Kyle's ghost cells, my scatter-adds.
- 主要言語
- Julia
- スター
- 3
- フォーク
- 1
- 平均マージ
- 1日 28分
- マージ済み PR（30日）
- 6
環境構築
このプロジェクトには開発コンテナ、Dockerfile、コントリビューションガイドがありません。まず README を読み、一般的な手順ははじめてのコントリビューションガイドを参照してください。
はじめの一歩
- issue を最後まで読み、次にプロジェクトのコントリビューションガイドを読みます。
- 着手することを issue にコメントします — 二人が同じ作業をするのを防げます。
- リポジトリをフォークし、ブランチを切って変更します。
- issue 番号を参照したプルリクエストを送ります。
RallypointOne/MatrixFreeOperators.jl のほかの issue
-
難易度 4/5 3〜5日 初心者へのやさしさ 45/100
-
enhancement
難易度 4/5 3〜5日 初心者へのやさしさ 48/100
-
perf(forest): thread the reference BlockForest path — leaf sweeps and exchange descriptor loopsオープンperformance
難易度 4/5 3〜5日 初心者へのやさしさ 48/100
-
enhancement
難易度 5/5 1週間以上 初心者へのやさしさ 25/100
-
enhancement
難易度 5/5 1週間以上 初心者へのやさしさ 25/100
RallypointOne/MatrixFreeOperators.jl#81 · コメント 1 件 ·
RallypointOne/MatrixFreeOperators.jl の issue をすべて見る
似ている issue
-
bug
難易度 2/5 1〜3時間 初心者へのやさしさ 61/100
-
難易度 2/5 1〜3時間 初心者へのやさしさ 83/100
-
難易度 2/5 1〜3時間 初心者へのやさしさ 72/100
JuliaDecisionFocusedLearning/ImplicitDifferentiation.jl#231 ·
-
難易度 2/5 1〜3時間 初心者へのやさしさ 76/100
JuliaDocs/PkgPage.jl#52 ·
-
難易度 2/5 1〜3時間 初心者へのやさしさ 66/100
メンテナーはふだん 1 日以内に返信