hspZ: GPU-accelerated HSPs backend
hspZ v0.0.4

D. Score gate

Reject almost every raw anchor with an exact score-only X-drop pass, then compact the rare survivors stably.

The funnel is intentionally extreme. On frozen workload A, the gate preserved the exact oracle output while avoiding full HSP materialization for nearly every hit.

162,123,203  raw seed-hit anchors
     27,342  score-gate survivors  (0.0169%)
     10,680  accepted raw HSPs
      4,248  final HSPs after host dedup

Nearly every hit ends here, so each instruction the gate spends per hit counts. Each side's first X-drop comes from one ballot of the lanes with any drop, and its value is read from the first dropping lane (the maximum before that drop). The keep test is one integer comparison against a threshold the host computes once, chosen so that it equals KegAlign's `f32`-rounded comparison; the output stays byte-identical. Measured on an L4 against the earlier four-ballot recovery and `f32` keep (hg38 × mm39 unit 0, one GPU, four reversed arms per variant, output identical to the frozen digest): score gate −30.1%, GPU busy −26.1% and wall −25.3% with the default reference-bucketed kernel; score gate −25.9% and wall −23.4% with the plain kernel (two arms per variant). Those unit-0 arms ran with the device seeder on and the gate kernel forced per pass. On the whole genome (L4, one GPU, production defaults, one reversed pair, output identical to the frozen digest) the wall fell from 9,949 s to 7,352 s (−26.1%). On an RTX 4090 (same unit, plain kernel): score gate −24.1%, GPU busy −21.9%, wall −18.4%.

D.1 — Feed coalesced anchor chunks to a warpStep 1 of 5
React Flow

WHAT GOES IN: Packed `(reference-end, query-end)` anchors in raw hit order. WHAT HAPPENS: A warp fetches 32 consecutive anchors coalescently and broadcasts one anchor at a time to its lanes. WHAT COMES OUT: Shared query windows and per-anchor reference coordinates ready for scoring. INVARIANT: Anchor order and identity are unchanged by the warp's memory mapping.

Readable journey

Step 1

D.1 — Feed coalesced anchor chunks to a warp

what goes in
Packed `(reference-end, query-end)` anchors in raw hit order.
what happens
A warp fetches 32 consecutive anchors coalescently and broadcasts one anchor at a time to its lanes.
what comes out
Shared query windows and per-anchor reference coordinates ready for scoring.
invariant
Anchor order and identity are unchanged by the warp's memory mapping.
  1. Packed anchors → Score-gate warp: 32 adjacent anchors
  2. Score-gate warp → Query-window cache: reuse equal query positions
  3. Score-gate warp → X-drop scorer: one anchor at a time
Step 2

D.2 — Compute a score-only X-drop bound

what goes in
One anchor, encoded sequences, substitution matrix, X-drop, and the keep threshold the host precomputed from K.
what happens
Lanes score right and left prefixes four bases per lane and stop on the first X-drop or edge: one ballot marks the lanes with any drop, and each side reads the maximum before its first drop from its first dropping lane (from its last lane when nothing drops). Only the best total score is kept.
what comes out
An upper score for the anchored ungapped segment and its keep decision.
invariant
The host computes once per engine the least total KegAlign's `f32`-rounded comparison keeps, so one integer comparison on the device decides exactly as that comparison does and the output is byte-identical.
  1. Host → Threshold gate: keep threshold, once per engine
  2. Anchor → Right prefix: score until X-drop or edge
  3. Anchor → Left prefix: score until X-drop or edge
  4. Right prefix → Threshold gate: maximum before the first drop
  5. Left prefix → Threshold gate: maximum before the first drop
  6. Threshold gate → Threshold gate: integer total vs keep threshold
Step 3

D.3 — Write one byte per decision

what goes in
The score-only total and the keep threshold for hsp threshold K.
what happens
The common reject path writes zero; plausible anchors write a one-byte survivor flag.
what comes out
A dense flag vector aligned with the original anchor array.
invariant
Rejection creates no HSP record, while every active flag slot is overwritten before reuse.
  1. Threshold gate → Reject path: total below the keep threshold
  2. Reject path → Byte flags: 0
  3. Threshold gate → Keep path: total at least the keep threshold
  4. Keep path → Byte flags: 1
Step 4

D.4 — Compact survivors without reordering

what goes in
One byte flag per raw anchor.
what happens
Device blocks count flags, the host scans only block sums, and stable local ranks emit original anchor IDs.
what comes out
A small, increasing list of survivor IDs for full materialization.
invariant
Stable compaction preserves raw hit order exactly, including under forced MAX_HITS chunking.
  1. Byte flags → Block counts: ballots of kept flags
  2. Block counts → Host prefix: one count per block
  3. Host prefix → Stable emitter: exclusive block offsets
  4. Stable emitter → Survivor IDs: original IDs in order
Step 5

D.5 — Optionally gate anchors by reference window

what goes in
One chunk's packed anchors, when reference-locality bucketing is on for this engine (`HSPZ_REF_BUCKETS`, default `auto`).
what happens
A stable counting sort groups the anchors into at most 32 reference-address buckets, each a window that fits three quarters of the L2, so consecutive warps gather from one cached window; the gate then writes one keep bit per anchor.
what comes out
Survivor IDs mapped back through each anchor's raw index and sorted into ascending raw hit order.
invariant
The materializer sees the same survivors in the same order as without bucketing, so the HSP set and file bytes are unchanged.
  1. Packed anchors → Bucket sort: reference address bucket
  2. Bucket sort → Score gate: bucket-major anchors + raw index
  3. Score gate → Survivor IDs: keep bits mapped to raw IDs
  4. Survivor IDs → Survivor IDs: sort back to raw hit order