0.0 — Where hspZ sits
hspZ replaces the GPU Seed + Filter stage. It does not perform gapped extension, chaining, or netting.
Genomes→hspZ
Seed + Filter→LASTZ
gapped→Chain→Net
Seed + Filter→LASTZ
gapped→Chain→Net
0.1 — From genomes to segmentsStep 1 of 6
WHAT GOES IN: Softmasked FASTA, FASTA.gz, or 2bit reference and query records. WHAT HAPPENS: hspZ plans chromosome bins, finds seed hits, filters and extends HSPs, then orders them for LASTZ. WHAT COMES OUT: Non-empty plus/minus `.segments` files or one reproducible tarball. INVARIANT: Input format does not change the decoded sequence set.
Readable journey
0.1 — From genomes to segments
- what goes in
- Softmasked FASTA, FASTA.gz, or 2bit reference and query records.
- what happens
- hspZ plans chromosome bins, finds seed hits, filters and extends HSPs, then orders them for LASTZ.
- what comes out
- Non-empty plus/minus `.segments` files or one reproducible tarball.
- invariant
- Input format does not change the decoded sequence set.
- Input records → Planner: names, lengths, original order
- Planner → GPU Seed + Filter: reference × query WorkUnits
- GPU Seed + Filter → Ordered emitter: accepted HSPs + ordinal
- Ordered emitter → Input records: LASTZ-compatible .segments
0.2 — Plan chromosome-atomic work
- what goes in
- Record metadata, block targets, worker count, and device memory.
- what happens
- The planner builds deterministic bins, forms a reference × query grid, and halves unsafe targets.
- what comes out
- Ordered WorkUnits assigned to GPU workers as count-balanced unit slices or whole reference bins.
- invariant
- A chromosome is never split to satisfy a target or a memory budget.
- Record metadata → LPT planner: id, length, input order
- LPT planner → Memory preflight: chromosome-atomic bins
- Memory preflight → LPT planner: fit or halve target
- LPT planner → WorkUnits: reference bins × query bins
0.3 — Build and query a spaced-seed index
- what goes in
- One packed reference bin, one query interval, and a seed shape such as 12of19.
- what happens
- Reference positions are scattered into stable buckets; exact and permitted transition query seeds look them up.
- what comes out
- A cumulative stream of reference/query anchor positions.
- invariant
- Full seed windows containing an invalid base are rejected, and reference bucket order is stable.
- Reference bin → Stable SeedTable: count, scan, deterministic scatter
- Query interval → Query interval: exact seed + transition variants
- Query interval → Stable SeedTable: lookup each packed k-mer
- Stable SeedTable → Anchor stream: reference positions in bucket order
0.4 — Reject weak hits before materialization
- what goes in
- Packed anchors in exact hit-stream order.
- what happens
- A score-only X-drop gate marks plausible anchors; scans compact survivor IDs without reordering them.
- what comes out
- A dense list of the rare anchors worth full extension.
- invariant
- Compaction preserves the original hit order and MAX_HITS chunk scope.
- Packed anchors → Score gate: score-only left + right X-drop
- Score gate → Stable compaction: one survivor flag per hit
- Stable compaction → Stable compaction: count, scan, emit original IDs
- Stable compaction → HSP materializer: dense survivors in hit order
0.5 — Recover exact HSPs and apply entropy
- what goes in
- A surviving anchor and the encoded reference/query sequences.
- what happens
- One warp finds right and left X-drop maxima, recovers boundaries, and conditionally recounts matching bases for entropy.
- what comes out
- An accepted SegmentPair with exact endpoints and score, or rejection.
- invariant
- Earliest-maximum ties and KegAlign float conversion points are preserved.
- Surviving anchor → Warp X-drop: extend right in 32-base tiles
- Surviving anchor → Warp X-drop: extend left in 32-base tiles
- Warp X-drop → Entropy gate: score + closed HSP interval
- Entropy gate → SegmentPair: accept when threshold semantics pass
0.6 — Make multi-GPU completion deterministic
- what goes in
- WorkUnits distributed across independently finishing GPU workers.
- what happens
- Workers dedup and LASTZ-order HSPs per MAX_HITS chunk; results enter an ordinal buffer, then the emitter (one per job with `--query-list`) performs coordinate conversion, optional partitioning, and writing.
- what comes out
- The same bytes for one or many GPUs within the same layout.
- invariant
- Worker completion order never controls file order or partition history.
- GPU worker 1 → Ordinal buffer: finish WorkUnit 3
- GPU worker 0 → Ordinal buffer: finish WorkUnit 2
- Ordinal buffer → Emitter: replay WorkUnit 2
- Ordinal buffer → Emitter: replay WorkUnit 3
- Emitter → Segment files: deterministic bytes