Output is a semantic stage: dedup scope, previous-input comparisons, strand traversal, coordinate conversion, and ordinal replay all affect final bytes.
reference ref_start ref_end query query_start query_end strand score
chr20 10541 10608 chr19 7731 7798 + 4187
coordinates: chromosome-relative · 1-based · inclusiveG.1 — Compact accepted HSPsStep 1 of 5
WHAT GOES IN: Materialized SegmentPairs and their inclusive-scan done flags. WHAT HAPPENS: The device copies accepted records into increasing materializer order and the host receives only the active prefix. WHAT COMES OUT: A dense vector of raw accepted HSPs for one MAX_HITS chunk. INVARIANT: Compaction changes storage density, never the relative order of accepted records.
Readable journey
G.1 — Compact accepted HSPs
- what goes in
- Materialized SegmentPairs and their inclusive-scan done flags.
- what happens
- The device copies accepted records into increasing materializer order and the host receives only the active prefix.
- what comes out
- A dense vector of raw accepted HSPs for one MAX_HITS chunk.
- invariant
- Compaction changes storage density, never the relative order of accepted records.
- Materialized HSPs → Stable compactor: candidate records
- Done scan → Stable compactor: inclusive accepted ranks
- Stable compactor → Raw accepted HSPs: accepted records in order
G.2 — Reproduce oracle deduplication
- what goes in
- Raw accepted HSPs from one chunk and strand.
- what happens
- A stable diagonal sort makes equivalent runs adjacent; unique-copy compares each record with the previous input record.
- what comes out
- One survivor for each oracle equivalence run.
- invariant
- Comparing with the last kept record instead would be wrong because containment is not transitive.
- Raw HSPs → Diagonal stable sort: diagonal, ref start, len, score
- Diagonal stable sort → Previous-input dedup: adjacent contained runs
- Previous-input dedup → Kept HSPs: first item of each run
G.3 — Put survivors in LASTZ order
- what goes in
- Deduplicated SegmentPairs.
- what happens
- A second stable sort orders query start, reference start, length, then descending score.
- what comes out
- LASTZ query-major segment order.
- invariant
- Sort stability and unsigned wrapping diagonal semantics are part of byte parity.
- Kept HSPs → LASTZ stable sort: query/ref/len/score keys
- LASTZ stable sort → Ordered segments: query-major order
G.4 — Convert to chromosome coordinates
- what goes in
- Block-relative SegmentPairs, chromosome tables, and strand.
- what happens
- Upper-bound lookup finds each chromosome; starts become one-based and ends remain inclusive. Minus records are traversed in reverse.
- what comes out
- Eight numeric/text fields for each `.segments` line.
- invariant
- Coordinate conversion never stitches across the `&` separator between chromosomes.
- Ordered HSPs → Record converter: block-relative start + extent
- Record converter → Chr tables: upper-bound chromosome lookup
- Chr tables → Record converter: name + block offset
- Record converter → Segment text: 1-based inclusive fields
G.5 — Emit deterministic files or one archive
- what goes in
- Completed WorkUnits arriving in any GPU completion order.
- what happens
- Ordinals are replayed; optional diagonal partitioning runs before a directory or reproducible tar sink writes non-empty entries. With `--query-list`, every job has its own ordinal cursor, `-D` history and sink.
- what comes out
- `tmp<n>.block<q>.r<r>.{plus,minus}[.splitN].segments` files.
- invariant
- Worker completion order never changes filenames, partition history, archive entry order, or bytes.
- Completed WorkUnits → Ordinal buffer: out-of-order results
- Ordinal buffer → Optional partitioner: next ordinal only
- Optional partitioner → Output sink: whole or split records
- Output sink → Output sink: directory or reproducible tar