tiles Directory Reference

Directories
	analysis
	library_nodes
	transformations

Files
	bank_conflicts.h
	buffer_layout.h
	The destination side of a tiled copy — the packed local buffer — as a (possibly swizzled) Layout over the coordinate [slot ++ tile].
	layout.h
	locality.h
	plugin.h
	swizzle.h
	tile.h
	Schedule-aware tile vocabulary: a Tile is a Layout (geometry from MemoryLayoutAnalysis) partitioned over the enclosing parallel loop nest (TileAxis) and classified into a required memory Space.
	tile_target.h
	The complete target-specific contract of the tile algebra.
	tile_target_registry.h
	tiled_copy.h
	A tiled copy plan: move one tile between memory levels.

Detailed Description

Tile Algebra: Reasoning About Memory Levels

The dominant bottleneck of modern processors is usually memory, not compute. Moving data through the memory hierarchy as fast as possible – on a CPU, from DRAM (global memory) up through several cache levels into the registers the ALU operates on – is therefore central to performance. On a CPU this movement is largely automatic: the compiler and hardware prefetchers steer the caches, leaving little to control explicitly. On GPUs and TPUs it is frequently explicit: data must be moved from global memory into shared memory / SRAM by hand.

This module provides a mathematical model for data in the memory hierarchy and for building transformations on it. The core unit is the tile: a compile-time-bounded region of memory. Consider copying a 1024x1024 matrix from A to B, both in DRAM. The naive nest below already defines tiles – the full matrices A, B, and, per iteration, the rows A_i, B_i – but the compiler and prefetcher already move these optimally, so explicit staging yields no benefit:

void copy(float* A, float* B) {
    // tiles: matrices A, B
    for (int i = 0; i < 1024; i++) {
        // tiles: rows A_i, B_i
        for (int j = 0; j < 1024; j++) {
            B[i * 1024 + j] = A[i * 1024 + j];
        }
    }
}

The loop transformations introduced earlier produce different tiles without changing program semantics:

void copy(float* A, float* B) {
    // tiles: matrices A, B
    for (int i_outer = 0; i_outer < 1024; i_outer += 32) {
        for (int j_outer = 0; j_outer < 1024; j_outer += 32) {
            // tile: a 32x32 2D subset
            for (int i = i_outer; i < i_outer + 32; i++) {
                for (int j = j_outer; j < j_outer + 32; j++) {
                    B[i * 1024 + j] = A[i * 1024 + j];
                }
            }
        }
    }
}

Strip-mining and loop interchange produce a 32x32 tile, which provides an explicit handle on data movement. The staging pattern is then almost always the same:

• Allocate a tile-sized buffer on the lower level (shared memory, stack, SRAM).
• Copy in the data from the higher level before the loop defining the tile.
• Copy out the data back to the higher level after the loop defining the tile.

This is the core pattern of tiling and local storage. The remaining complexity consists of variants of it:

• cooperative vs. thread-private loads,
• cooperative stores (reductions, atomics),
• double buffering / asynchronous loads and stores (staging the next tile while processing the current one).

Identifying which accesses form compile-time-bounded regions inside a loop is implemented in MemoryLayoutAnalysis. Classifying those regions into schedule- and storage-level-aware tiles is implemented in TileAnalysis.

The Layout

A layout is the function mapping tile elements to their memory locations. Represented as (shape, strides, offset), it denotes an affine map. The tiles module uses math::tensor::TensorLayout as the single source of truth for this type (tiles::Layout is an alias); a coordinate is addressed via resolve_element.

Definition (Layout). A layout of rank $d$ is a triple $L = (\mathbf{s}, \mathbf{t}, o)$ with a shape $\mathbf{s} \in \mathbb{N}^d$, a stride $\mathbf{t} \in \mathbb{Z}^d$, and an offset $o \in \mathbb{Z}$. It denotes the affine map

$$ L(x_0, \dots, x_{d-1}) \;=\; o + \sum_{k=0}^{d-1} t_k\, x_k, \qquad 0 \le x_k < s_k, $$

under the colexicographic convention: dim $0$ varies fastest.

Intuition. $\mathbf{s}$ is how many elements lie along each dim, $\mathbf{t}$ is how far apart they sit in memory, and $o$ is where the tile starts. Consider the $32\times 32$ tile above. Row-major addressing places element $(i, j)$ at $1024 \cdot i + j$, so the tile's top-left corner $(i_{\text{outer}}, j_{\text{outer}})$ lies at offset $o = 1024 \cdot i_{\text{outer}} + j_{\text{outer}}$. Within the tile, dim $0$ (the column $j$) steps by $1$ and dim $1$ (the row $i$) by $1024$ — one full row — giving stride $(1, 1024)$.

TensorLayout::total_elements() is the coordinate count $\prod_k s_k$ and resolve_element evaluates the map above; every buffer placement is an affine layout, and only the Swizzle conflict policy adds a non-affine relabelling on top.

Schedules and Memory Levels

The layout fixes the tile's geometry: which elements it covers and where they reside in memory. It does not determine which memory level the tile should be staged in; that is schedule-dependent. If a loop processes tiles independently across threads, each tile may reside privately in registers. If the threads process one tile cooperatively (a shared operand or a reduction), the tile must reside in memory visible to every cooperating thread.

Geometry alone is therefore insufficient: geometry and schedule together determine the minimum memory level a tile may occupy – the most local (fastest) space still visible to every thread that shares it. The level is derived by classifying the enclosing loops of the tile.

• Cooperation levels $\mathrm{Device} \sqsupset \mathrm{Group} \sqsupset \mathrm{Subgroup}$. Target-neutral tiers (OpenCL/SYCL vocabulary) for the scope of work sharing: a GPU grid / CPU threads cooperate at Device, a GPU thread block / Tenstorrent core-workers at Group, a GPU warp / wavefront at Subgroup. Each target maps its schedule onto these tiers via AxisSchedule::classify.
• Memory spaces $\mathrm{Global} \sqsupset \mathrm{Shared} \sqsupset \mathrm{Register}$ — how widely a location is visible. Each target maps levels to spaces via TileTarget::space: a scratchpad target (GPU) sends $\mathrm{Device}\mapsto\mathrm{Global}$, $\mathrm{Group}\mapsto\mathrm{Shared}$, $\mathrm{Subgroup}\mapsto\mathrm{Register}$ (a subgroup cooperates through register shuffles, needing no buffer), while a flat host (CPU) target sends every level to $\mathrm{Global}$, having no scratchpad. classify stamps each axis with its target's space and a derived has_scratchpad() capability, so the algebra never names a target.

Definition (axis role). For an enclosing loop with index variable $x$, its role in staging the tile with base address $b$ is

$$ \operatorname{role}(x) = \begin{cases} \textbf{Cooperative} & x \notin \operatorname{vars}(b), \ \textbf{Private} & x \in \operatorname{vars}(b). \end{cases} $$

Intuition. The test is whether the thread index appears in the address. If it does, distinct threads access distinct data, so each holds a private copy. If it does not, all threads of the axis access the same data and must stage it cooperatively.

Definition (required space). A cooperatively-staged tile must live in a space visible to every thread that cooperates on it. So the tile's required space is the coarsest space over its cooperative axes, and thread-private (registers) when there are none:

$$ \operatorname{space}(T) \;=\; \bigsqcup \, \texttt{space}(\operatorname{level}(a)) : a \in \operatorname{axes}(T),\ a\ \text{cooperative} \,