systile

Matmul-native data structures & algorithms, written from scratch in Rust.

One idea, taken to its conclusion: build data structures and algorithms whose dominant operation is a dense matrix multiply. On a CPU that is usually a bad trade — a hash map beats a matmul-based map, a queue beats matrix powers. But on a systolic accelerator (a TPU's matrix unit, a GPU's tensor cores) dense matmul is the cheap primitive and branch-y pointer chasing is the expensive one, so the trade flips. systile is a library of structures built for that world.

It starts with a substrate — the Padded Tile Lattice, a tensor laid out the way a TPU's memory is actually addressed (8 × 128 (sublane, lane) tiles, padding, bf16/int8 dtypes) with a CPU reference simulator of the systolic matmul — and then builds a stack of pillars on top of it. You do not need a TPU: everything runs on the CPU model, honestly framed as matmul-native (maps efficiently onto the MXU), not TPU-exclusive.

The pillars

Every structure reduces its core operation to a matmul through the same systolic engine. The honest framing, capacity math, and citations live in HOLOGRAPHIC.md.

Why a data structure "for TPUs"?

A TPU is not a flat array machine. Three hardware facts drive its data layout, and systile encodes all three:

Because padding is mandatory, the structure tracks both the logical shape you asked for and the padded shape it actually stores, plus a validity Mask so reductions and dense round-trips never fold in garbage.

Install

cargo add systile

# Cargo.toml
[dependencies]
systile = "0.9"

No required dependencies; #![forbid(unsafe_code)]; builds on stable Rust ≥ 1.74.

Quick start

use systile::prelude::*;

let a = PaddedTileLattice::from_dense(
    2, 3, &[1.0f32, 2.0, 3.0, 4.0, 5.0, 6.0], Geometry::TPU_V,
).unwrap();
let b = PaddedTileLattice::from_dense(
    3, 2, &[7.0f32, 8.0, 9.0, 10.0, 11.0, 12.0], Geometry::TPU_V,
).unwrap();

// Matmul runs in the same blocked dataflow a systolic array uses.
let (c, stats) = a.matmul_with_stats(&b).unwrap();
assert_eq!(c.to_dense(), vec![58.0, 64.0, 139.0, 154.0]);
println!("array utilisation: {:.1}%", stats.utilisation() * 100.0);

The headline: a data structure whose operations are matmuls

On top of the tiling substrate, systile ships an invented container — the Holographic Tensor Store (HoloMemory) — a key→value map that holds every entry summed on top of every other inside a single fixed-width vector, and recovers a value by algebra plus one matrix multiply.

use systile::prelude::*;

let mut book = HoloMemory::new(8192, 1000, 0xC0FFEE); // 8192-dim, 1000 value symbols
for name in 0..200 {
    book.insert(name, (name * 7 + 3) % 1000);          // bind + bundle into ONE vector
}

// Look up all 200 names at once — a single (200 × 8192)·(8192 × 1000) matmul.
let hits = book.batch_get(&(0..200).collect::<Vec<_>>());
let correct = (0..200).filter(|&n| hits[n].0 == (n * 7 + 3) % 1000).count();
assert_eq!(correct, 200); // 100% recall, well under the d/(2 ln M) capacity bound

200 entries live in 32 KB of f32; lookup of the whole batch is one MXU-shaped GEMM. On a CPU this is a worse map than a hash table — it only pays off where dense matmul is the cheap primitive and you batch thousands of probes: a TPU. It's approximate and bounded (K_max ≈ d / (2 ln M)), degrading gracefully past capacity. The full mechanism, capacity math, honest novelty assessment, and citations are in HOLOGRAPHIC.md. Try it:

cargo run --release --example holo_kv          # 200 pairs in one vector, 1 matmul
cargo run --release --example holo_capacity    # recall vs the d/(2 ln M) bound
cargo run --release --example resonator_factor # factor a product with no known factors
cargo run --release --example holo_precision   # f32 vs bf16 cleanup recall
cargo run           --example holo_analogy      # "Dollar of Mexico?" -> peso, zero training
cargo run --release --example graph_paths      # shortest paths as tropical matrix powers
cargo run --release --example automaton_divisibility  # decide divisibility by matmul
cargo run --release --example classifier_demo  # train by bundling, classify by matmul
cargo run --release --example index_search     # exact k-NN search as one matmul
cargo run --release --example bloom_membership # Bloom membership as one matmul
cargo run --release --example sort_by_matmul   # sort via comparison + permutation matmul
cargo run --release --example scan_prefix      # prefix sums as a triangular matmul
cargo run --release --example conv_search      # pattern search as im2col correlation
cargo run --release --example sketch_frequency # Count-Min frequency estimates by matmul
cargo run --release --example topk_select      # top-k via comparison-count matmul
cargo run --release --example edit_distance    # Levenshtein as tropical matmul
cargo run --release --example pagerank_demo    # PageRank as power-iteration matmuls
cargo run --release --example dft_spectrum     # DFT as a Fourier-matrix matmul
cargo run --release --example viterbi_decode   # most-likely HMM path via max-plus matmul
cargo run --release --example attention_retrieval # softmax attention as soft retrieval

Features

• A family of matmul-native containers on a hyperdimensional (VSA) substrate (Hyper algebra + Codebook matmul cleanup):
  • HoloMemory — key→value store in superposition; batched lookup is one matmul.
  • HoloSet — set membership as a matmul; union by bundling; norm-based cardinality.
  • HoloSequence — order via permutation binding; whole-sequence decode in one matmul.
  • Resonator — factor a bound product back into its unknown symbols by iterated matmul cleanup (an Mᶠ search run as a short sequence of GEMMs), with exact verification and restarts.
• TensorGraph — graph algorithms as semiring matrix powers (GraphBLAS-style): reachability (boolean), all-pairs shortest paths (tropical/min-plus), and walk counting (ordinary) — each in ⌈log₂ n⌉ dense matmuls via repeated squaring.
• TensorAutomaton — a finite-state machine run as matmuls: one-hot state vector × per-symbol transition matrix. Branchless string recognition; a whole batch advances with |alphabet| masked matmuls per position (e.g. decide divisibility by matrix multiply).
• HoloClassifier — a hyperdimensional classifier: train by bundling (no gradients, no epochs — fitting is vector addition) and classify by matmul against the class-prototype matrix. 100% on the synthetic clustering demo.
• TensorIndex — exact nearest-neighbour / similarity search (the vector-DB workload): score a batch of queries against the whole corpus in one (b × dim)·(dim × n) matmul, then take top-k.
• TensorBloom — a counting Bloom filter whose batch membership test is one matmul of item signatures against the filter's presence vector; no false negatives, deletion supported, false-positive rate exposed.
• TensorSort — sorting as comparison matmul: the rank vector is C·1 (row sums of the pairwise comparison matrix) and the sorted output is P·x, an O(n²)-matmul trade against O(n log n) branches.
• TensorScan — prefix sums as a triangular matmul (L·x): inclusive, exclusive, and suffix scans with O(1) dependency depth.
• TensorConv — 1-D pattern search as im2col cross-correlation: gather all windows and dot them against the kernel in one matmul, then argmax for the match.
• CountMinSketch — frequency estimation where each row's query is a matmul of a one-hot column selection against that row's counters; never underestimates.
• TensorTopK — top-k selection as a comparison-count matmul (count = C·1, keep count < k), batched, no full sort.
• TensorEditDistance — Levenshtein distance as a tropical (min-plus) shortest path through the alignment grid, relaxed by iterated min-plus matmuls.
• TensorPageRank — PageRank by power iteration: repeated M·r matmuls against the column-stochastic Google matrix until the ranks converge.
• TensorDFT — the discrete Fourier transform as a matmul by the Fourier matrix: forward/inverse and magnitude spectra, real and complex.
• TensorViterbi — most-likely HMM state decoding by max-plus (MaxPlus semiring) matmul stepping with a back-pointer traceback.
• TensorAttention — scaled dot-product attention softmax(QKᵀ/√d)·V, the transformer core, read as a soft associative memory.
• PaddedTileLattice<T> — the core 2-D tiled tensor, generic over element type.
• bf16 — a from-scratch bfloat16 with round-to-nearest-even and a full set of arithmetic / comparison / conversion impls.
• Systolic matmul simulator — weight-stationary, f32-accumulated, verified bit-for-bit against a naive triple loop, and it reports MAC utilisation.
• Tile-level sparsity — find and skip the all-zero tiles a kernel would waste cycles on.
• Affine int8 quantisation — symmetric and asymmetric calibration that preserves the hardware tiling end to end.
• Transpose & relayout — re-tile the same logical data under a new geometry.
• Element-wise maps and reductions — padding-correct by construction.
• #![forbid(unsafe_code)], no required dependencies.

Examples

cargo run --example quickstart
cargo run --example bf16_roundtrip
cargo run --example quantize_matmul
cargo run --example sparsity_report
cargo run --example padding_inspect
cargo bench

Layout, in one picture

A 3 × 5 logical matrix on Geometry::TPU_V (8 sublanes × 128 lanes) pads up to a single 8 × 128 tile. Element (row, col) lives at:

offset = tile_index * (sublanes * lanes) + sublane * lanes + lane

tile_index walks tiles in row-major order; within a tile the order is row-major over (sublane, lane). That is exactly the order a TPU's vector memory expects, so as_storage_slice() is copy-ready.

Status

systile is young and the API may shift before 1.0. The simulator is a reference model, not a cycle-accurate one: it reproduces the blocking and accumulation order of a systolic array (and so its numerics), not its timing.

License

Licensed under either of MIT or Apache-2.0 at your option.