hspZ: GPU-accelerated HSPs backend
hspZ v0.0.4

E. X-drop materialization

One warp recovers exact right and left maxima, endpoints, score, and the closed HSP interval.

The materializer repeats the exact score work for a tiny survivor set so the fast gate never becomes the source of record endpoints.

warp lane       0   1   2   …  30  31
sequence base   p   p+1 p+2 … p+30 p+31
prefix score    ───────── inclusive scan ─────────
running max     ───────── prefix maximum ─────────
X-drop ballot   first set lane ends this direction
endpoint        earliest lane attaining the winning maximum
E.1 — Restore each surviving anchorStep 1 of 5
React Flow

WHAT GOES IN: Stable survivor IDs, packed raw anchors, and encoded sequences. WHAT HAPPENS: One warp resolves each survivor ID back to its original reference/query anchor. WHAT COMES OUT: An ordered stream of anchors for the exact materializer. INVARIANT: The materializer sees the same anchor coordinates as the score gate, in the same relative order.

Readable journey

Step 1

E.1 — Restore each surviving anchor

what goes in
Stable survivor IDs, packed raw anchors, and encoded sequences.
what happens
One warp resolves each survivor ID back to its original reference/query anchor.
what comes out
An ordered stream of anchors for the exact materializer.
invariant
The materializer sees the same anchor coordinates as the score gate, in the same relative order.
  1. Survivor IDs → Packed anchors: original hit index
  2. Packed anchors → Materializer warp: reference + query anchor
Step 2

E.2 — Extend right in warp tiles

what goes in
One anchor, the substitution matrix, and X-drop.
what happens
Thirty-two lanes score consecutive bases, scan prefix sums and maxima, and ballot the first lane beyond X-drop.
what comes out
The right maximum score and earliest position where it occurs.
invariant
An equal later maximum never replaces the earliest winning endpoint.
  1. Anchor → 32-base tile: next right tile
  2. 32-base tile → Prefix scan: substitution scores
  3. Prefix scan → X-drop ballot: running score + maximum
  4. X-drop ballot → Right maximum: first drop or sequence edge
Step 3

E.3 — Extend left with the same rule

what goes in
The same anchor and scoring state reset for the left side.
what happens
Lanes walk bases before the anchor, tile by tile, until the first X-drop or sequence boundary.
what comes out
The left maximum score and earliest left extent.
invariant
Right and left use the oracle's duplicated direction-specific coordinate rules.
  1. Anchor → 32-base tile: next left tile
  2. 32-base tile → Prefix scan: reverse offsets
  3. Prefix scan → X-drop ballot: running score + maximum
  4. X-drop ballot → Left maximum: first drop or sequence edge
Step 4

E.4 — Recover the closed HSP interval

what goes in
Anchor coordinates plus left and right winning extents.
what happens
The left extent shifts both starts; both directional extents combine into one inclusive length field.
what comes out
Candidate `ref_start`, `query_start`, `len`, and total score.
invariant
`SegmentPair.len` is an extent, so the printed interval covers `start..=start+len`.
  1. Anchor → SegmentPair: anchor coordinates
  2. Left extent → SegmentPair: shift both starts
  3. Right extent → SegmentPair: close the inclusive extent
Step 5

E.5 — Store only accepted records

what goes in
Candidate interval, score, and the entropy-adjusted decision.
what happens
Lane zero writes one aligned 16-byte SegmentPair and a done flag, or writes rejection status.
what comes out
Materialized HSP/status arrays ready for stable compaction.
invariant
Every active output slot is fully overwritten before the host or another kernel reads it.
  1. Candidate HSP → Entropy decision: total score + closed interval
  2. Entropy decision → SegmentPair store: accepted 16-byte record
  3. Entropy decision → Done flag: 1 accepted or 0 rejected