D71 — Metal cost-to-go field by segmented prefix-min scan¶
Decision¶
The Metal cost-to-go field solves each line as a segmented prefix-min scan of 64-bit keys d[j] − c·j on one 32-lane SIMD-group, sweeps each direction pair (forward, backward) and all layers in one dispatch, batches 16 then 8 rounds per command buffer with early-exit dispatches after convergence, and gives every calling thread its own command queue. Every round ends in the CPU reference's state, so fields and round counts are bit-identical.
Alternatives¶
Keep one thread per line (first kernel); threadgroup-wide Hillis-Steele scans with staged lines (tried: 3.2× single-caller, still slower than the CPU under 8 callers); a GPU-resident A*
Reason¶
Fields were 50 % of the router's CPU time on a private 4-layer board and the first kernel was slower than the CPU under portfolio load. The scan kernel: 4.6× one caller and 3× the CPU with 8 concurrent callers on 2,311 captured fields (0 mismatches), route 16.2 → 9.2 s and --mode routable 336 → 228 s with byte-identical outputs on default rules (0.075 mm lattice); on the project's rules (0.050 mm) the A* loop dominates and fields are ~1–5 % of a 121 s route (doc 07 §8.1). A* stays on the CPU (D5).