Mojo Tiles and Tiling

Tiling (also called blocking) is a technique that divides a large dataset into smaller chunks called tiles, processing each tile completely before moving to the next. Tiles are sized to fit inside the CPU cache, which is many times faster than main memory. Tiling transforms a cache-unfriendly algorithm into a cache-friendly one.

Why Cache Size Matters

  Memory hierarchy — speed and size:

  CPU Registers  │ ~0.3 ns  │ ~1 KB     ← fastest
  L1 Cache       │ ~1 ns    │ ~64 KB
  L2 Cache       │ ~4 ns    │ ~512 KB
  L3 Cache       │ ~12 ns   │ ~8 MB
  RAM            │ ~60 ns   │ ~16 GB
  SSD            │ ~100 µs  │ ~1 TB     ← slowest

  RAM is 200× slower than L1 cache.
  Keeping hot data in cache = massive speedup.

Cache Misses Without Tiling

Problem: Naive matrix multiply accesses memory column-by-column
for a 1000×1000 matrix stored row-by-row.

  Row-major storage:
  [ row0_col0, row0_col1, ... row0_col999,
    row1_col0, row1_col1, ... row1_col999,
    ...
    row999_col0, ... ]

  Accessing column j requires jumping 1000 elements per step.
  Each jump likely evicts the previous cache line → cache miss storm.
  Performance: slow, dominated by memory latency.

Tiling Concept

Without tiling (row × full column):
  Process: row 0 × all 1000 cols → big memory jumps

With tiling (row-tile × col-tile):
  Process: rows 0–31 × cols 0–31  → fits in L1 cache
  Process: rows 0–31 × cols 32–63 → fits in L1 cache
  ...

  Each tile is small enough to stay in cache during computation.
  No evictions = no cache misses = full cache speed.

Using tile in Mojo

Mojo's algorithm module provides a tile function that handles the tiling loop structure for you.

from algorithm import tile
from memory import UnsafePointer

fn process_row(data: UnsafePointer[Float32], row_start: Int, tile_size: Int):
    for i in range(tile_size):
        data[row_start + i] = data[row_start + i] * 2.0

fn main():
    let n = 64
    var arr = UnsafePointer[Float32].alloc(n)
    for i in range(n):
        arr.init_pointee_copy(Float32(i + 1))

    alias tile_size = 16

    @parameter
    fn process_tile[size: Int](start: Int):
        for i in range(size):
            arr[start + i] *= 2.0

    tile[process_tile, tile_size](n)

    print(arr[0])   # 2.0   (1 × 2)
    print(arr[15])  # 32.0  (16 × 2)

    for i in range(n):
        (arr + i).destroy_pointee()
    arr.free()

Tiled Matrix Multiply

Matrix multiplication is the canonical example where tiling delivers enormous speedups. The naive version thrashes the cache; the tiled version stays cache-warm.

Naive matrix multiply (pseudocode):
  for i in range(N):
      for j in range(N):
          for k in range(N):
              C[i,j] += A[i,k] * B[k,j]   ← B accessed column-by-column

Tiled matrix multiply (pseudocode):
  for i in range(0, N, TILE):
      for j in range(0, N, TILE):
          for k in range(0, N, TILE):
              # Process tile [i:i+TILE, j:j+TILE]
              for ii in range(i, min(i+TILE, N)):
                  for jj in range(j, min(j+TILE, N)):
                      for kk in range(k, min(k+TILE, N)):
                          C[ii,jj] += A[ii,kk] * B[kk,jj]

Tiled access pattern visualization (4×4 matrix, tile=2):

  Step 1: Process tile A[0:2, 0:2] × B[0:2, 0:2] → C[0:2, 0:2]
  ┌──┬──┬──┬──┐   ┌──┬──┬──┬──┐   ┌──┬──┬──┬──┐
  │██│██│  │  │ × │██│██│  │  │ → │██│██│  │  │
  │██│██│  │  │   │██│██│  │  │   │██│██│  │  │
  │  │  │  │  │   │  │  │  │  │   │  │  │  │  │
  │  │  │  │  │   │  │  │  │  │   │  │  │  │  │
  └──┴──┴──┴──┘   └──┴──┴──┴──┘   └──┴──┴──┴──┘
  A                B               C  (partial result)

  Each ██ tile fits entirely in L1 cache during the inner loop.

Choosing Tile Size

Tile size selection:
  - L1 cache is typically 32–64 KB
  - Float32 = 4 bytes
  - Tile of 32×32 Float32 = 32 × 32 × 4 = 4 KB → fits in L1
  - Tile of 64×64 Float32 = 64 × 64 × 4 = 16 KB → fits in L1

  For matrix multiply (3 matrices in cache simultaneously):
  3 × 32×32 × 4 = 12 KB → safe for a 32 KB L1 cache
  alias TILE = 32   ← typical good starting point

Tiling Combined with Vectorization

For maximum performance, tile the outer loops and vectorize
the innermost loop:

  for each tile:            ← tiling (cache-friendly)
      for each row in tile:
          SIMD operation on tile row  ← vectorization (SIMD)
          parallelize across tiles   ← parallelism (multi-core)

  This three-level strategy underpins how high-performance
  libraries like BLAS achieve near-theoretical peak performance.

Key Takeaways

Tiling divides large datasets into cache-sized chunks to minimize slow main memory accesses. Tiles sized to fit in L1 or L2 cache let the CPU operate at cache speed throughout the inner loop. The classic application is matrix multiplication, where column-major access patterns cause cache thrashing without tiling. Mojo's tile function handles the tiling loop structure automatically. For peak performance, combine tiling with vectorization and parallelization — this three-level strategy mirrors what professional HPC libraries do internally.