Input format is not an algorithm knob. Base case, record order, and the split between the seeding and scoring alphabets are.
records chrA chrB
packed A C g T & N A T & (final & stored, not in block_len)
seeding A C × T × × A T × (only uppercase A/C/G/T)
scoring A C L T E N A T E (A C G T L N X E)A.1 — Decode records without changing themStep 1 of 5
WHAT GOES IN: A reference or query path containing FASTA, FASTA.gz, or 2bit data. WHAT HAPPENS: Magic bytes choose the reader; names, record order, base case, and soft masks are preserved. WHAT COMES OUT: The same ordered `(name, bases)` records regardless of container format. INVARIANT: Equivalent inputs produce the same decoded sequence set before planning or GPU work.
Readable journey
A.1 — Decode records without changing them
- what goes in
- A reference or query path containing FASTA, FASTA.gz, or 2bit data.
- what happens
- Magic bytes choose the reader; names, record order, base case, and soft masks are preserved.
- what comes out
- The same ordered `(name, bases)` records regardless of container format.
- invariant
- Equivalent inputs produce the same decoded sequence set before planning or GPU work.
- Input path → Format detector: first four bytes
- Format detector → Record reader: FASTA, gzip, or 2bit
- Record reader → Ordered records: names + case-preserved bases
A.2 — Pack chromosome-atomic buffers
- what goes in
- Ordered records selected for one bin.
- what happens
- Records are concatenated with one `&` separator and a chromosome start table is recorded.
- what comes out
- One packed byte buffer plus chromosome-relative mapping metadata.
- invariant
- The trailing separator exists in storage but is excluded from the GPU-visible block length.
- Ordered records → pack: name + bases in input order
- pack → Packed buffer: chrA & chrB &
- pack → Chr table: name, start, length
- pack → Packed buffer: block_len excludes final &
A.3 — Keep seeding and scoring alphabets separate
- what goes in
- Case-preserved ASCII bases from the packed bin.
- what happens
- Seeding accepts only uppercase ACGT, while scoring encodes lowercase, N, IUPAC, and separators distinctly.
- what comes out
- Seed validity decisions and an eight-symbol scoring buffer.
- invariant
- Lowercase invalidates a seed window but is not confused with an uppercase scoring base.
- Packed bases → Seeding alphabet: full seed window
- Seeding alphabet → Kernels: 2-bit ACGT or invalid
- Packed bases → Scoring encoder: every byte
- Scoring encoder → Kernels: A C G T L N X E
A.4 — Build chromosome-atomic bins
- what goes in
- Record IDs, lengths, input ordinals, and independent reference/query targets.
- what happens
- Longest records enter the currently lightest bin; ties fall back to input order and bin ID.
- what comes out
- Deterministic reference and query bins whose records remain in input order.
- invariant
- A chromosome is never split merely to meet a target size.
- Record metadata → LPT binning: id, length, ordinal
- LPT binning → Reference bins: balanced whole records
- LPT binning → Query bins: independently targeted bins
A.5 — Preflight the work-unit grid
- what goes in
- Reference bins, query bins, device budget, MAX_HITS, and worker count.
- what happens
- The planner forms the Cartesian grid, estimates the largest unit, and halves both targets until it fits; `--kegalign-bins` fails instead of shrinking.
- what comes out
- Ordered WorkUnits and a deterministic worker assignment: count-quota unit slices on matching devices, otherwise whole reference bins.
- invariant
- Shrinking changes the frozen layout before allocation; it never splits a chromosome inside a WorkUnit.
- Reference bins → Memory preflight: candidate layout
- Query bins → Memory preflight: candidate layout
- Memory preflight → Memory preflight: fit or halve targets
- Memory preflight → WorkUnits: ordered R × Q grid
- WorkUnits → GPU workers: unit slices or whole bins