Retrospective: M7 (the sssp operators engine and mosp)

Status: complete on the branch m7-mosp (from main at 8842acf, the merge of pull request #4 with M5; main at 0.1.0rc1 merged in by the review and fix step), reviewed and fixed (“Review and fix” below; ADR 0029 awaits the author). M7 is 0.2 work: it merges into main only after the 0.1.0 release. Steps 1-4 each have a section below; the milestone’s acceptance table, the verification from a fresh clone, the re-estimate and the open items close the record.

Step 1: the sssp operators engine (sssp-operators)

What was built

Commit	What
fd2d30e	the device building blocks shared by the two CUDA engines (packed words, stamp claims, the warp-aggregated append, the warp reductions, device_csr) moved unchanged from fused.cuh to kernels.cuh; the fused kernel’s SASS is identical for all three instantiations
511556b	the CUDA operators engine (operators.cuh, operators.cu): MOSP_ESCHER@4b86159’s multi-kernel host loop with MOSP-CUDA@e220ee2’s semantics, one framework hook per phase (Tier A); engine::automatic falls back to it without cooperative launch, engine::operators selects it (ADR 0026)
4405ff3	both engines in every CUDA sssp suite, a larger engine-equality test, the operators engine’s input checks and budget; the kit’s C4 over presets, sizes, mixes and three batches
bfd3dde	dyng-compat-mosp --cuda-engine, compare.py --configs cuda-fused,cuda-operators, perf_ab.py engines
83880cc	ADR 0026 (accepted under delegation), the algorithm page, the backend how-to, the framework and conformance guides, the CHANGELOG
(this record)	parity/results/M7.md sections 1-2 with the corpus and engine A/B records, this section

Results

• Conformance check C4 runs for sssp on CUDA (it was skipped everywhere in 0.1) and passes for the three graph types; the kit’s C4 now compares after compute() and three batches for every preset, the small and medium sizes and every batch mix.

• The golden corpus: 495/495 byte-identical with the operators engine, with 32- and 64-bit edge offsets (parity/results/M7.md section 1).

• The randomized suites in the CUDA executable compare the operators engine with the fused engine and with the host backends on every chain (trees, invalidated, affected, packed_parents); the MOSP fixtures, the packing boundary, the distance-only fallback, the input checks (an out-of-range distance, a parent cycle), the steady-state allocations and the strict budget run on both engines.

• Speed against the fused engine (parity/results/M7.md section 2; informational, no gate): 1.03-1.18x on the 50K batches of the four gate graphs, 1.10-1.62x on the local 10K batches, whose many short near-far rounds each cost a host round trip of about 8-9 us.

Deviations and decisions (with reasons)

1. MOSP_ESCHER’s structure, MOSP-CUDA’s semantics. PLAN 6.4.2 names MP1 as the structure to follow. MP1 is an earlier state of the algorithm and differs from MOSP-CUDA@e220ee2 in details that change outputs or error reports (no parent-cycle detection, candidates above the bound packed, no distance-only fallback, no affected). The engine keeps MP1’s shape and takes every detail from the fused kernel, so the bytes are the same (ADR 0026 items 1 and 3).

2. Fewer host round trips than MP1. MP1 synchronizes after Step 1, after the pull, twice per threshold raise and once per push iteration. Here the pointer-jumping rounds end on the device (a round after a converged one returns at once), the frontier’s length and the threshold stay on the device, so an update synchronizes 3 + iterations + epochs times. That is the engine’s I9 budget, stated after the phase.

3. Grid-stride kernels with at most as many blocks as the device holds at once (MP1 launches one thread per item). The pointer-jumping rounds that have nothing left to do then cost one empty launch of a few hundred blocks instead of n / 256 blocks.

4. Rule of two. Nothing enters cpp/src/operators: cycle_count’s CUDA code shares none of these operators (it uses work counters and CUB scans), and the planned second user of invalidate_subtree and the pull is hyper_sssp (0.3). The shared device blocks of the two sssp engines live in the sssp folder (kernels.cuh). PLAN 4.5.3’s schedule, sync_rule and tie_break policies were not needed (one schedule; the tie rule is the packed minimum).

5. CHANGELOG placement. The M7 entries are a block at the end of [Unreleased] (before [0.0.1]), so the release-prep pull request on main, which rewrites the head of [Unreleased], does not touch the same lines; after 0.1.0 the block stays under [Unreleased].

Open items

• The operators engine’s speed on updates with many short near-far rounds (1.4-1.6x the fused engine on the local batches). It is the fallback, not the default, and has no gate; if it ever matters, several rounds per synchronization (or a CUDA graph of the rounds) would remove most of the round trips. The risk docs/developer/plan.md lists for 0.2.0 (“the operators engine within 1.05x of the fused one”) materialised on the local batches (1.4-1.6x); no gate applies (criterion 1 makes the comparison informational).

Notes for the next steps

• mosp composes K sssp problems: the engine choice is sssp::options::cuda_engine of each objective (the sketch’s mosp::options::engine passes it through). The operators engine shares the pooled sssp_cuda_workspace (its control block is sized for either engine).

• dyng-compat-mosp already sums whichever engine’s stages ran for the per-objective SOSP region, so a mosp driver can reuse that rule.

Step 2: mosp (mosp-core)

What was built

Commit	What
827612f	sssp: sssp_solve_view(), a static solve through sssp’s static enactor on a graph view that is not a container (the combined CSR) into caller-owned arrays; sssp::update() accepts a batch without insertions whatever its weight count
d174147	io::write_path_costs() (MOSP’s mospCosts.txt) and <dyng/testing/mosp_oracle.hpp> (combined_graph_reference(), mosp_path_costs_reference())
d848c52	dyng::mosp on the sequential, OpenMP and CUDA backends (cpp/src/algorithms/mosp/: mosp.cpp the composition and the finalize step, sequential.cpp / openmp.cpp / cuda.cu the combined graph, the path costs on the host); the manifest, the registries, the API baseline (<dyng/mosp.hpp> frozen); the kit’s traits (K = 3, preferences {2, 1, 3}) and the kit’s graphs with several weight columns; the hand and randomized suites
33b4196	dyng-compat-mosp --mosp, compare.py comparing combined/, the preference fixtures cpp/tests/data/mosp_combined (parity/fixtures/mosp/make_mosp_fixtures.sh) and their CTests
adf2d6e	ADR 0027 (accepted under delegation), the CHANGELOG
eecc9e1	dyng-compat-mosp --mosp computes the path costs only to write them (as mosp; the gates run --no-output)
(this record)	the compat tools need mosp in a subset build (CMakeLists.txt); the sketch and the history pages updated; parity/results/M7.md section 3, this section

Results

• The golden corpus with the whole MOSP update (--mosp): 495/495 byte-identical on sequential, OpenMP with 1, 4 and 16 threads, and on cuda with the fused and the operators engine with 32- and 64-bit edge offsets, for the K updated trees, the updated CSR, the invalidated counters and, new, combined/{distancesCsr,SSSPTreeCsr,mospCosts}.txt (K from 1 to 5 and 32 in the corpus). Records M7-mosp-goldens-host.json, M7-mosp-goldens-cuda.json.

• Preference vectors: the 8 committed cases (the thesis example with Pref {4, 1, 4} and {4, 4, 1}, K = 2..4 with preferences, -k 2 on a 4-column graph) byte-identical on every backend; both originals agreed on them first. The thesis’ costs (15, 3, 20) and (15, 24, 7) are asserted by the hand tests on every backend. At scale: roadNet-CA (K = 3, Pref {4, 1, 4}, the 50K and the local 10K batches) byte-identical to MOSP-OpenMP’s mosp on the OpenMP backend, and to MOSP-CUDA’s on cuda (section 3).

• The conformance kit: C1-C12 for mosp on every backend and graph type (C4 compares the fused and the operators engine through the K updates and the combined solve; C8’s budget on cuda is K + 3 synchronizations; C10 pairs mosp with sssp and cycle_count); sssp’s and cycle_count’s suites still pass with mosp as a C10 partner on 3-column graphs.

• ctest -L cpu (dev): 694/694; ctest -L gpu (dev-cuda, GPU 1): 321/321; compute-sanitizer memcheck, synccheck and racecheck on the mosp CUDA suites: 0 errors.

• Portability: the Clang 18 syntax pass (171 files, 0 failures) and the fortified cpu-only Release build are clean; ci/docs.sh passes (670 declarations in the API baseline); ci/scaffold_check.sh passes (the kit’s changes keep the scaffold green).

Deviations and decisions (with reasons)

1. mosp_problem is a participant, not a framework problem. PLAN 4.5.2 calls mosp “plain C++ composition”; the framework has no composite problem type and mosp is its first user (rule of two). detail::mosp_problem implements update_participant and owns K problem_participant<sssp_problem>: one commit for the K objectives, each objective through its own update enactor (stages nested in mosp.objective), then the finalize step. It composes with any result in dyng::update() (C10).

2. The combined solve on a view. The combined CSR is pooled scratch, not a dyng::graph (sketch question 3), so sssp got sssp_solve_view(): the static enactor with the backend’s engine on a raw view, into caller-owned arrays. The sequential engine’s distance-only parent recovery reads in-edges (the OpenMP and CUDA engines read out-edges there), so the sequential combine builds the combined graph’s in-edge CSR when the packing does not fit; tested with L = 2^20 on 2^21 vertices.

3. API additions to the sketch (ADR 0027): options::num_objectives (MOSP’s -k); delta applies to the K updates only (the originals solve the combined graph with its own automatic width); the path costs cover the K objectives and are host memory on every backend (the compat driver writes the original’s every-column file with -k); affected counts the vertices whose combined distance or MOSP parent changed (a second pair of combined arrays, swapped); max_objectives is 64 (the originals stop at 32: one byte per insertion and objective in the commit’s classification).

4. sssp accepts batches without insertions of any weight count (as graph::apply()): the kit’s empty batches on 3-column graphs and mosp’s objectives need it. A behaviour relaxation of a frozen header’s function, recorded in ADR 0027 and the CHANGELOG.

5. The kit’s weight columns. test_traits::num_weights (default 1) gives the kit’s graphs K columns; columns 1..K-1 are a fixed function of the edge and column 0, so the kit’s generators, inverses (C5) and re-weightings stay unchanged; C7 checks K + 1 columns, C10 uses the larger count of the pair.

6. The compat driver’s default stays SOSP-only. The sssp gates’ timed regions (parity/timed_regions/sssp.toml, perf_ab.py) measure the SOSP part and subtract the original’s combined step; --mosp is the clone of the whole mosp driver. With --no-output the clone does not compute the path costs, as mosp computes them only to write mospCosts.txt (the gate protocol runs --no-output on both sides).

7. Not done in this step (the next steps of M7): the Python binding dyng.mosp, the CLI (dyng mosp compute|update), the performance gates and the timed-region map of mosp. Until the binding exists, python/tests/test_api_surface.py::test_uniform_contract[mosp] fails (the registry lists mosp), so ci/python.sh is red between the steps.

Open items

• The path costs are a sequential host pass (MOSP’s mospPathCosts): about 0.5-1.4 s on roadNet-CA under the machine’s load at the time (random accesses over 2M vertices). The originals compute them only while writing mospCosts.txt, concurrently with the other files; in dynG they are part of update() unless compute_path_costs is false. A parallel or device version (sketch question 1, “device later”) would matter for end-to-end runs that write the costs.

• The timings seen while checking parity at scale were taken under the shared lock on a loaded machine (another user’s 26-core job): not measurements. The gate step measures under the exclusive lock.

Notes for the next steps

• Python: dyng.mosp.compute(g, source=0, preferences=[...]), Result.path_costs as an (n, K) host array, Result.from_arrays over lists of arrays (sketch, “Python”); the CLI’s dyng mosp update can reuse io::write_path_costs() and the combinedGraph/ layout of the compat driver.

• Gates: “(a) compute” = the K mosp.objective regions (sssp’s engine stages inside) + mosp.combine + mosp.combined_sssp + mosp.finalize against the originals’ gpu_compute_ms / compute_ms (dyng-compat-mosp --mosp prints both in its RESULT compute_ms= line; the original’s combined step is its combined_graph_gpu / combined_graph_compute stage); “(b) end to end” with --no-output on both sides.

Step 3: parity and performance of mosp (mosp-parity-perf)

What was built

Commit	What
9e5dd82	the path costs on the handle’s host threads on openmp and cuda (a level-synchronous traversal of the MOSP tree; the sequential backend keeps the port); the tree’s download timed in mosp.path_costs
e8bf3c1	dyng-compat-mosp --mosp --timing writes the setup’s stages as setup rows
29702d7	parity/perf_ab.py mosp (the M7 gates; parity/timed_regions/mosp.toml) and perf_ab.py prepare --widen (the K sweep’s input)
c443051	the paper-scale goldens [sets.mosp_scale] (parity/mosp_scale_goldens.py: SHA-256 of every output file of 20 benchmark cases, cross-checked with MOSP-CUDA) and their replay compare.py mosp_scale
2a72b59	perf_ab.py memory --mosp (the device memory of the whole MOSP update)
864f228	perf_ab.py’s perf lock waits in the kernel instead of polling (a test with a chain of shared holders)
0ddd0d1	perf_ab.py mosp leaves the path-cost region out when the port computes none (-k below the columns, --no-output)
5e20e0f	the combined solve counts affected in place on cuda (sssp_solve_view(..., count_changes), the fused kernel’s count_changes parameter, the operators engine’s counted unpack); the device spare arrays, the count kernel and one synchronization gone (the device-memory gate)
18583f0, 7ddf284, 80ce979, 33c7130, (this record)	the records: paper-scale parity, the K sweep, the mosp gates on both backends, the device memory before and after the fix, the sssp gate re-check; parity/results/M7.md sections 4-10, this section, the CHANGELOG

Results

• Parity at paper scale: the 20 mosp_scale cases (the four gate graphs x three batches, Pref {4, 1, 4} on roadNet-CA, the K sweep) byte-identical (SHA-256 of every output file, the invalidated counters) on sequential, OpenMP (28 threads) and cuda with both engines; the golden corpus 495/495 on eight configurations on the final code (M7.md section 4).

• The K sweep: roadNet-CA widened to 4 objectives (mospPrep widen), K = 1..4 and two preference vectors, byte-identical on every backend; timings reported (M7.md section 5; cuda K = 2..4, OpenMP K = 4 only).

• The mosp gates (M7.md section 6): “(a) compute” 0.992-1.005 on cuda and 0.669-0.924 on OpenMP (gate 1.05), “(b) end to end” 0.704-0.907 and 0.754-0.919 (gate 1.10), on roadNet-PA, roadNet-CA, rgg_n_2_20_s0 and road_usa with the three bench batches each. All met.

• Device memory (PLAN 8.6, <= 1.05x): missed at first (1.068-1.075x on the road graphs), fixed (5e20e0f): 1.015-1.019x, rgg 0.931x (M7.md section 8).

• The sssp gates re-checked on roadNet-CA and road_usa, both backends: all met (M7.md section 9).

• The combined step (“watch”): 0.55-0.72x on OpenMP, 1.00-1.04x on cuda with kernels that are not slower than MOSP-CUDA’s (M7.md section 7).

• Tests on the final code: ctest -L gpu (dev-cuda, GPU 1) 322/322, ctest -L cpu (dev) 702/702, pytest parity/tests 49 passed; compute-sanitizer memcheck, racecheck and synccheck on the mosp CUDA cases that run the in-place count (the thesis example, the stats, vertex growth, the distance-only mode with both engines, clone) and memcheck on the sssp engine tests: 0 errors; the Clang 18 syntax pass (172 files, 0 failures) and the fortified cpu-only build are clean; pre-commit and ci/docs.sh pass (the API snapshot unchanged, 670 declarations).

Deviations and decisions (with reasons)

1. “(b) end to end” writes every output file on both sides, not --no-output as step 2’s notes proposed. The published end-to-end figures (MOSP-CUDA’s results/README.md: “from reading the text inputs … to writing all outputs”) include the writes, and the originals compute the path costs only while writing mospCosts.txt; with --no-output neither side would compute them, and dynG’s mosp::update() cost of them would go unmeasured. perf_ab.py mosp --no-output remains as an option.

2. The device-memory gate was measured and fixed in this step. Milestone criterion 4 lists the timing gates; PLAN 8.6’s table also gates device memory (<= 1.05x), and M3 measured it for sssp. mosp missed it by keeping a second MOSP tree on the device for affected. The fix changes the fused kernel’s unpack condition (a parameter instead of !from_scratch; the update path is unchanged in behaviour and registers), so the cuda corpus, the paper-scale goldens, the cuda mosp gates and the cuda sssp gate re-check were all run again on the final code; the earlier cuda records are kept under -before- names. The host backends keep their second pair of arrays: host memory has no gate, and their engines write the output arrays during the search, so the counted unpack would not apply without restructuring them.

3. The paper-scale goldens store hashes, as PLAN 8.3 prescribes for paper-scale cases (the command lines and the SHA-256 of each output file), plus the SHA-256 of every input file (the inputs come from perf_ab.py prepare, not dyng prep, which does not exist yet) and the invalidated counters; the export was cross-checked against MOSP-CUDA.

4. The K sweep is parity plus reported timings. PLAN 6.4.4 lists it under parity; its timing has no gate. With -k below the graph’s columns, both sides write MOSP’s every-column mospCosts.txt, so the “(b)” of K = 2 and 3 is not the library’s figure.

5. The lock of the harness. perf_ab.py polled the perf lock with LOCK_NB once a second and waited for more than half an hour behind another agent’s back-to-back shared holders; it now blocks in flock(2) after the first try (with the timeout as an interval timer), and the step’s runs were wrapped in a blocking flock(1) (perf_ab.py runs under its ancestor’s hold). No measurement rule changed.

6. The combined step on cuda is 1.00-1.04x and not optimized further. It is a reported region inside the gated “(a)” (0.996-1.005x); Nsight Systems shows dynG’s combine and solve kernels at or below MOSP-CUDA’s times, so the remaining difference is host time around the same kernels at the locked clocks, not the MP2-style atomic regression PLAN 6.4.4 warns about.

Open items

• The ci scripts were not re-run from a fresh clone in this step (ci/check.sh --parity, ci/gpu_local.sh, ci/docs.sh, ci/python.sh: the last step’s verification). ci/python.sh stays red until the Python binding dyng.mosp exists (step 2, open item 1). ci/gpu_local.sh’s parity step replays --configs cuda only.

• The OpenMP K sweep timings of K = 2 and 3 were not taken (informational; M7.md section 5).

• The combined step’s 0-4 % on cuda (section 6 above, M7.md section 7) could be looked at with a locked-clock Nsight Systems run if it ever matters; it does not reach any gate.

• From step 1: the operators engine’s speed on many short near-far rounds (the risk listed for 0.2.0 materialised on the local batches, 1.4-1.6x; no gate applies).

Notes for the next steps

• The gate commands: parity/perf_ab.py mosp --backend {cuda,openmp} --graph <g> [--gpu 0] --runs 21 (road_usa --runs 11), parity/perf_ab.py memory --mosp --gpu 0 --graph <g>, parity/compare.py mosp_scale --exe <dyng-compat-mosp> --configs ...; on a shared machine wrap each in flock $DYNG_SCRATCH/perf.lock (blocking).

• The Python binding can expose mosp::stats::affected with the same meaning on every backend (the cuda count now comes from the solve’s unpack; the values are those of the host count).

Step 4: Python, command line, documentation and close-out (python-docs-finish)

What was built

Commit	What
4699edb	dyng.mosp (python/bindings/mosp.cpp, python/dyng/mosp.py): compute, update, Options, Stats (with the K dyng.sssp.Stats), Result (distances(k), parents(k), the combined arrays, the path costs as a zero-copy (n, K) dyng.Array, from_arrays over lists of arrays, clone); dyng.Array reports 2-D shapes; mosp results in dyng.update; dyng.io.write_path_costs, dyng.testing.combined_graph / mosp_path_costs; the stubs; DYNG_BUILD_PYTHON needs mosp; python/tests/test_mosp.py
834d86d	`dyng mosp compute
156dfea	examples/{cpp,python}/mosp_update (the thesis example’s combined files against the originals’, CTest on sequential, OpenMP and cuda, pytest on the host backends)
4889ba1	ci/gpu_local.sh: the corpus replayed with both CUDA engines, synccheck on the CUDA mosp suite
edc9a7a	ADR 0028 (accepted under delegation, approvals-log row), the mosp page (Python, command line, the performance table), the sssp page (the engine table, the engine choice from Python and the command line), the Python API page, CHANGELOG, README, history
4a61c07, aadc8de, 32e132f	what the first fresh-clone run of ci/check.sh --parity found: the objective count K (and a thread count T) of steps 2-3 broke the naming rules of ADR 0004 (clang-tidy, now num_k and team; no behaviour change); ci/tests/test_regen.py scaffolded mosp as a “planned” algorithm (now label_propagation); three property docstrings of dyng.mosp began with “name:”, which napoleon read as a type (Sphinx -W)
(this record)	docs/developer/plan.md’s M7 row, this section with the milestone’s acceptance table, the verification and the re-estimate

Results

• The Python suite: 437 passed and 4 skipped (torch, cupy, pandas not installed) in the working tree, including 24 mosp tests (the thesis example with Pref {4, 1, 4} and {4, 4, 1} on both host backends; the Hypothesis property with 60 examples: random graphs with 1-4 objectives, random preferences and batches with vertex growth, against a pure-Python oracle) and 13 mosp CLI and example tests. dyng mosp update is byte-identical to the committed files of both originals on the 8 preference cases, to dyng-compat-mosp --mosp on all 42 committed cases (34 SOSP cases, 8 preference cases; every output file, obj<k>/ and combinedGraph/), and to MOSP-OpenMP’s own mosp binary ($DYNG_SCRATCH/ref/MOSP-OpenMP@c352151/unpatched/bin/mosp) on the 8 preference cases.

• scripts/regen.py --stubs --check, mypy (strict, 31 files) and griffe (no breaking change of the Python API against main) pass; the C++ API baseline is unchanged (670 declarations).

Deviations and decisions (with reasons)

1. Per-objective accessors are methods (Result.distances(k)), not list properties: the C++ API’s shape, and a list would read K arrays on every access (ADR 0028, alternatives).

2. dyng.Array is no longer always 1-D. PLAN 5.5 sketches path_costs.to_numpy() with shape (n, K); the C++ array is vertex-major, so the 2-D view is zero-copy. ndim, shape and len() follow the view (unchanged for the 1-D arrays); griffe sees no signature change.

3. No --pref / -k aliases on dyng mosp: PLAN 5.6 maps flags one to one to option fields; the original spellings stay in dyng-compat-mosp --mosp. List-valued fields became a new kind of generated flag (comma-separated, MOSP’s --pref syntax).

4. Every column’s costs with --num-objectives below the columns, as the original writes mospCosts.txt; the extra columns come from dyng.testing.mosp_path_costs, as the compat driver uses the C++ reference. The library’s own path_costs keep covering the K objectives (ADR 0027).

5. dyng mosp compute writes the combined files of the static solve next to mospPrep init’s trees (no original command writes them for a static solve; the formats are the driver’s).

6. Examples added (PLAN 9.6: one per algorithm) although the step did not list them.

7. ci/gpu_local.sh changed (both engines in the parity step, synccheck on mosp): open items of steps 1-3, needed for the milestone’s C4-on-the-corpus criterion.

8. README and docs/developer/plan.md: shared with the release-prep pull request on main. Only the status rows of M7 changed (one row of the README’s status table split into the M7 row and the remaining 0.2 row; the M7 row of the plan’s milestone table); the orchestrator should check these two rows when it merges after 0.1.0.

Notes

• The first fresh-clone run of ci/check.sh --parity failed in tidy, harness, scaffold and docs (the three defects above; scaffold and docs both build the Sphinx site). Steps 2 and 3 had run the pieces (ci/docs.sh before the Python module existed, the Clang syntax pass, the unit tests) but not ci/check.sh’s clang-tidy step; the naming rule only shows there. The second run, on 32e132f, passed every step.

Milestone acceptance

#	Criterion	Evidence	Status
1	sssp engine::operators on CUDA (MP1’s multi-kernel host loop; operators in the framework where two users exist); engine::automatic = fused with cooperative launch, operators otherwise; C4 byte-identical on the 495-case corpus and the randomized tests; operators against fused measured on the four gate graphs	step 1 (ADR 0026: rule of two, nothing in cpp/src/operators); the corpus with --configs cuda,cuda-operators 495/495 in the fresh clone (ci/gpu_local.sh, below) and on the final code of step 3 (eight configurations); parity/results/M7.md section 2 (1.03-1.18x on the 50K batches, 1.10-1.62x on the local batches; informational)	met
2	dyng::mosp (PLAN 5.1, 6.4.4) on sequential, OpenMP and CUDA, K sssp problems on one workspace, the combined graph, path costs; the kit’s C1-C12 on every backend (C10 with cycle_count or sssp); Python dyng.mosp, CLI `dyng mosp compute	update`, docs page	steps 2-3 (ADR 0027); step 4 (ADR 0028; docs/algorithms/mosp.md with the sections of PLAN 9.5, “Differences from the paper”, “Paper vs fixed code” and the performance table)
3	Byte parity with MOSP-CUDA e220ee2 and MOSP-OpenMP c352151 (obj<k>/, combinedGraph/) on the MOSP corpus; the thesis example; combined_graph_reference + Dijkstra; K in 1..4; the K sweep	steps 2-3 (parity/results/M7.md sections 3-5: the corpus on every backend and engine, the 8 preference fixtures, the 20 paper-scale cases incl. the K sweep); step 4: dyng mosp update equal to the originals’ files, to dyng-compat-mosp --mosp on 42 cases and to MOSP-OpenMP’s mosp; the thesis costs and the oracle in C++ and Python	met
4	Gates (PLAN 8.6): “(a) compute” <= 1.05x, “(b) end to end” <= 1.10x on the four graphs and both backends; the sssp gates re-checked	step 3 (parity/results/M7.md sections 6, 8, 9: “(a)” 0.992-1.005 cuda / 0.669-0.924 OpenMP, “(b)” 0.704-0.907 / 0.754-0.919; device memory 0.931-1.019x; the sssp gates on roadNet-CA and road_usa met). Step 4 changed no measured code path (the bindings, the CLI, and the renaming of local names)	met
5	A fresh clone passes ci/check.sh --parity, ci/gpu_local.sh, ci/docs.sh, ci/python.sh; portability pre-checks clean; the API snapshot changed only by reviewed additions with an ADR under delegation; CHANGELOG; this retrospective	“Verification” below; the C++ baseline gained <dyng/mosp.hpp>, io::write_path_costs and <dyng/testing/mosp_oracle.hpp> under ADR 0027 (670 declarations), the Python API only additions under ADR 0028 (griffe: no breaking change); CHANGELOG blocks “M7: …” at the end of [Unreleased]	met

Verification (fresh clone of m7-mosp at 32e132f)

All runs in $DYNG_SCRATCH/m7-verify/clone (a clone of the local repository, git checkout m7-mosp), with the shared perf lock for every heavy step:

Check	Result
ci/check.sh --parity	all checks passed in 22 min: clang-format; cpu-only and dev built and ctest -L cpu passed (675/675 and 704/704); clang-tidy (naming rules); reuse; provenance (152 files); regen; the harness tests (89 passed); ci/python.sh (the editable install into the clone’s build/py-venv, stubs current, mypy strict, pytest 437 passed and 4 skipped for torch / cupy / pandas); the griffe API check; the scaffold check (80 probe tests); ci/docs.sh (Doxygen coverage, 7 snippets, the API baseline of 670 declarations, Sphinx -W, the link check); pre-commit; the parity preset (ctest -L parity, 4/4: the sssp corpus with the whole MOSP update on sequential and OpenMP, the cycle_count corpus)
ci/gpu_local.sh (dev-cuda, GPU 1)	all steps passed in 50 min (RTX A5000, driver 590.48.01, CUDA 13.1): the build; ctest -L gpu 323/323 (the mosp examples on cuda included); ctest -L cpu in the CUDA build 704/704; the golden corpus with --configs cuda,cuda-operators ALL EQUAL, 495 cases x 2 configurations (the whole MOSP update per case: byte parity with MOSP-CUDA and C4 on the corpus), the cycle_count CUDA corpus 48/48; compute-sanitizer memcheck on every gpu executable, synccheck on the sssp, mosp and cycle_count suites, racecheck on cycle_count: 0 errors; clang-tidy on the CUDA branches
ci/docs.sh, ci/python.sh	inside ci/check.sh above (and ci/docs.sh alone in the working tree on the same code: OK)
Portability pre-checks	the Clang 18 syntax pass over a dev + DYNG_BUILD_PYTHON=ON database: 187 files, 0 failures (the bindings included); the fortified (-D_FORTIFY_SOURCE=3) cpu-only build with the Python module: clean, no warnings

Re-estimate of the roadmap

Measured. M7 was estimated within the 0.2 row of docs/developer/plan.md (M7-M9: 1.5-2 weeks focused). It took about one long day of wall-clock time for its four steps (2026-09-30 afternoon to 2026-10-01 afternoon by the commit times), of which roughly a third was measurement: the corpus on eight configurations, the paper-scale goldens, the gates on two backends and four graphs at locked clocks, the device memory, and the re-measurement after the device-memory fix, with long waits for the exclusive perf lock behind other agents’ campaigns. The independent review of M7 is still to come; earlier reviews found real defects every time (about half a day of fixes, more when they reopen measurements).

Milestone	Plan (working weeks)	After M3 (focused)	Now: focused effort, incl. review and fix	Calendar incl. author gates	Main risk
M7 sssp operators engine + mosp	(in 0.2’s 8-12)	(in 0.2’s 1.5-2 weeks)	done (about 1 day), plus its review and fix (0.5-1 day)	the pull request after 0.1.0	the review reopening gate measurements
M8 ESCHER store + hypergraph	(in 0.2)		3-5 days	1-2 weeks	the staged CBST merge (both originals’ traces after every step); the first hypergraph container and its headers
M9 triad_count	(in 0.2)		2-4 days	1-2 weeks	the paper suites’ sizes; memory <= 1.05x; content-addressed deletions until M8’s keys
0.2.0	8-12	1.5-2 weeks	about 1.5-2 weeks from now (unchanged)	4-6 weeks	the release after 0.1.0’s; consent records are not needed (Appendix E)

The 0.2 risk “the operators engine within 1.05x of the fused one” (docs/developer/plan.md, section 4) is not met on the local batches (1.4-1.6x) and was never a gate (milestone criterion 1 makes the comparison informational); it moves to the open items as a possible optimization.

Review and fix

The independent review of M7 (at d2e0bdb) confirmed 16 findings, two of them (7 and 12) the same defect seen from two sides. Each is fixed or recorded below, in small commits on m7-mosp.

#	Finding (severity)	What was done	Commit
1	The host backends and cuda follow different originals’ packing rules, so non-canonical imported trees inside the window (n - 1) * W <= max_distance < n * W give different trees, against the docs’ cross-backend claim (high)	a parity rule, not delegated: ADR 0029 proposed (option A, each backend as its original, recommended; option B, one rule everywhere), GOVERNANCE.md open decisions; code unchanged; the docs state the exception; SsspPackingWindow.NonCanonicalTreesFollowEachOriginalsPackingRule pins it (n = 65537, both window ends); per-backend parity against both originals checked once (parity/results/M7.md section 11)	7c8af0d, c6a432f, c2781d9
2	mosp.md: “every tree is canonical” (low)	reworded: the MOSP tree always, the K trees after compute() or a canonicalizing import; the window caveat	c6a432f
3	The gate write-up drops PLAN 8.6’s noisy flags (medium)	M7.md section 6: the spreads of both sides and the flags in the table, a paragraph on the flagged rows (all 24 end-to-end, 7 of 12 OpenMP compute); mosp.md section 5	c2781d9
4	OpenMP combined step: the original allocates its workspace inside the timed stage, dynG’s pool was warm (low)	stated in M7.md section 7 with an estimate of the first-touch cost; the cold-workspace reading is an open item (below)	c2781d9
5	mosp.toml: mosp.finalize described as a kernel and a sync that 5e20e0f removed (low)	both notes corrected (cuda: reads the solve’s count; host: count_changed() and the swap)	bacbc88
6	“The plan’s 0.2 estimate” is the plan’s listed 0.2.0 risk (low)	reworded in this retrospective and in M7.md section 2; the confirmation request dropped; the plan’s risk cell gains the outcome	c2781d9, 9ad1778, this section
7, 12	A CUDA mosp update that adds vertices goes one sync over its I9 budget (the release of the pinned tree copy; strict budgets throw and poison) (medium)	the reserving run’s synchronizations are measured and counted; the mosp executables (hand, randomized, conformance) run every test with strict budgets; MospBackend.StrictBudgetsHoldWithNewVerticesAndBothEngines (fails without the fix)	d3a5f47
8	sssp.hpp’s @sync (and the sssp page, stats.hpp) promise one sync on cuda although engine::automatic can run the operators engine (medium)	both @sync paragraphs give the fused and the operators counts and name the fallback; sssp.md section 4; engine_used’s comment	c6a432f
9	PLAN 11.3’s M7 deliverable .dgb missing and unrecorded (medium)	moved to M8, recorded (deviation 3 below; plan.md M7/M8 rows, python_gaps.md)	9ad1778
10	framework.md’s translate row and mosp’s template card describe a hook mosp does not have (low)	the translate row (mosp needed none; hyper_sssp first), a row for mosp’s hand-written participant (no composite problem type), the card	bacbc88
11	mosp.hpp’s @throws lists the valid configuration as the error and overstates the batch weight check (low)	“not one preference per objective (or none)”; only insertions with another weight count (also the Python docstring)	c6a432f
13	The combined solve’s budget on the operators engine is the update formula, one too many (low)	sssp_cuda_host_syncs() (2 + iterations + epochs for a static solve, 3 + … for an update), returned by sssp_solve_view(); the hand test above pins it exactly (fails with the old formula)	d3a5f47
14	Merging into the current main (0.1.0rc1) conflicts in 6 files, and the M7 side would downgrade sssp and cycle_count to experimental (medium)	origin/main merged into m7-mosp (no history rewritten): the generated tables regenerated (sssp, cycle_count stable; mosp experimental), main’s maturity line plus the operators engine, both approvals logs, perf_ab.py by hand (main’s input hashing, also in perf_ab.py mosp), the M7 CHANGELOG blocks moved back under [Unreleased]; then the release certificate taught mosp’s goldens and fixtures	71775ac, be943d7
15	C8 hard-codes the fused budget: fails without cooperative launch, never checks the operators engine (medium)	C8 runs with engine::automatic and engine::operators where a backend has both, against test_traits::host_sync_budget(backend, stats) (sssp: per engine; mosp: its own bound for operators, which depends on epochs mosp::stats does not carry); checked by breaking sssp’s operators budget once (C8 then fails in its operators pass)	b191c9d
16	test_traits::num_weights missing from the traits docs (low)	test_traits.hpp and conformance.md list it (and the new budget hook)	b191c9d

Deviations and decisions (with reasons)

1. The packing window waits for the author (finding 1). It is a parity rule (GOVERNANCE.md: not delegated), so nothing in the code changed: ADR 0029 is Proposed with option A, the behaviour since M1b, which keeps byte parity with both originals on every input and qualifies C3 by one documented exception. The window needs at least 65537 vertices with int32 weights (or, on roadNet-CA, a largest weight of 4462121 or 4462122) and non-canonical imported trees; no golden, paper-scale or randomized case lies in it. Option B would change one line per engine and the test’s expectation.

2. The merge of main came first. Every later fix was made on the merged tree, so the docs that both sides edit carry 0.1.0’s maturity and M7’s additions together. Merging main brought one more conflict-free change to fix: parity/certify.py (new in 0.1.0rc1) read num_files and manifest_sha256 of every golden set, which mosp_scale (SHA-256 per case) does not have, and found cpp/tests/data/mosp_combined missing from fixtures.toml (be943d7).

3. .dgb moves to M8 (finding 9). PLAN 11.3 lists .dgb binary batches for M7, while PLAN 6.2 ships them with the ESCHER store (order 7, M8), and no M7 deliverable reads them (the MOSP parity uses insert.txt / delete.txt, the tests and examples .dgt); the format (magic DYNGBAT1, a versioned header, CRC32, the streaming batch_reader with pinned staging) is better designed with the hypergraph batches it must also hold. Still 0.2.

4. Strict budgets for the mosp executables, not for every test. The defect of findings 7 and 12 printed hundreds of warnings that ctest hides. The mosp executables now arm strict budgets for every test (support/strict_budgets_environment.hpp); the whole CPU and GPU suites were also run once with DYNG_STRICT_BUDGETS=1 and pass, but making that the default for every executable is a policy change for all algorithms (the OpenMP engines’ reservations differ with the thread count of the runner), left to a later milestone.

5. mosp’s C8 budget with the operators engine is mosp’s own (finding 15): the combined solve’s epochs are not in mosp::stats (adding a field would change the frozen header), so the traits return run_dependent_budget there and C8 checks the bounded budget mosp declares; the hand test pins that budget exactly (used == limit in the steady state).

6. No new gate measurement. The fixes change no output and add, in a gated region, two reads of the thread’s budget counters (zero without DYNG_DEBUG_BUDGETS, which the parity presets do not set) and one integer expression, so the section 6 gate records stand (parity/results/M7.md section 12).

Results

• ctest -L gpu (dev-cuda, GPU 1): 325/325, no budget warning in the log; with DYNG_STRICT_BUDGETS=1 all pass too (the review saw 28 failures there). ctest -L cpu (dev): 707/707, also with DYNG_STRICT_BUDGETS=1.

• The packing window against both originals (n = 65537 at both ends, the review’s n = 65538 case, a canonical control): each backend byte-identical to its own original in every file; the canonical case equal everywhere (parity/results/M7.md section 11).

• pytest parity/tests ci/tests: 130 passed (the certificate tests include the mosp set).

• Portability: the Clang 18 syntax pass over the dev database (173 files) and a dev + DYNG_BUILD_PYTHON=ON database (187 files), 0 failures; the fortified (-D_FORTIFY_SOURCE=3) cpu-only build with the Python module: clean, no warnings.

• Fresh clone of m7-mosp at 939433c ($DYNG_SCRATCH/m7-verify/clone, shared perf lock):

Check	Result
ci/check.sh --parity	all checks passed in 24 min: clang-format; cpu-only 678/678 and dev 707/707; clang-tidy; reuse; provenance (152 files); regen; the harness tests (130 passed); ci/python.sh (stubs, mypy strict, pytest 437 passed, 4 skipped for torch / cupy / pandas); the griffe check; the scaffold check (80 probe tests); ci/docs.sh (Doxygen coverage, 7 snippets, the API snapshot of 670 declarations unchanged, Sphinx -W, the link check); pre-commit; the parity preset (ctest -L parity 4/4)
ci/gpu_local.sh (dev-cuda, GPU 1)	all steps passed in 72 min: ctest -L gpu 325/325, ctest -L cpu in the CUDA build 707/707, the golden corpus with --configs cuda,cuda-operators ALL EQUAL (495 cases x 2), the cycle_count CUDA corpus 48/48, memcheck, synccheck (sssp, mosp, cycle_count), racecheck: 0 errors; clang-tidy on the CUDA branches

Open items

• The ADR 0029 decision (open item 5 below).

• A cold-workspace reading of dynG’s OpenMP combined step (finding 4): needs a mode of dyng-compat-mosp that runs the update on a fresh pool; ungated and informational, so it is left for a later measurement campaign.

• After the final 0.1.0 release (release-0.1.0-final) merges into main, merging main into m7-mosp again conflicts only in CHANGELOG.md (git merge-tree, at the fix’s head): keep the M7 blocks under [Unreleased] above ## [0.1.0].

Open items for the lead maintainer

1. The operators engine’s speed on updates with many short near-far rounds (1.4-1.6x the fused engine on the local 10K batches, 1.03-1.18x on the 50K batches): the risk listed for 0.2.0 materialised on the local batches; no gate applies. Several rounds per synchronization or a CUDA graph of the rounds would close most of the gap if it is ever wanted.

2. The merge after 0.1.0. main at 0.1.0rc1 is merged into m7-mosp (review and fix); the CHANGELOG’s M7 blocks are under [Unreleased]. Against release-0.1.0-final only CHANGELOG.md conflicts (the release renames the heading right below the M7 blocks): keep the blocks under [Unreleased] above ## [0.1.0].

3. Informational gaps of step 3: the OpenMP K-sweep timings of K = 2 and 3 (parity is complete), and a locked-clock Nsight look at the CUDA combined step’s 0-4 % (inside a gated region that is met).

4. The Python CUDA path of dyng.mosp is tested through the C++ suites only: the CPU wheel has no CUDA backend until the plugin wheels of 0.1.x (M6); the binding is the same code for both.

5. ADR 0029, the packing window (a parity rule; GOVERNANCE.md, open decisions): for non-canonical imported trees inside (n - 1) * W <= max_distance < n * W the host backends follow MOSP-OpenMP’s packing rule and cuda MOSP-CUDA’s, so their tie parents differ, each byte-identical to its own original. Option A (recommended, the current behaviour): keep it and document the exception to C3. Option B: one rule everywhere, giving up byte parity with one original on those inputs.