TEIR: A Tiled Execution IR for Tensor Contractions#
The Tiled Execution IR (TEIR) is a compiler intermediate representation for tensor contractions. It represents a contraction as loops around operations on small tiles, which a lowering maps to kernels. A TEIR program consists of axes, tile operations, and a schedule. The axes define the iteration space and the access pattern on the tensors, and the tile operations define the computations on tiles. The schedule arranges the invocations of the tile operations in time and in space.
Motivation#
Tensor contractions are central to scientific computing, for example in quantum chemistry and tensor decompositions, and to machine learning. Fast implementations execute a contraction as loops around kernels that operate on small tiles. An implementation chooses which dimensions of the iteration space the kernels cover, how the loops around them block for the caches, which loops run in parallel, and in which loops operands are packed. These choices depend on each other, on the layouts of the tensors, and on the hardware.
Approaches based on BLAS libraries, such as the einsum of PyTorch, transpose whole tensors to execute a single batched matrix multiplication internally, which costs memory traffic. TBLIS fuses the transpositions into the packing of its BLIS-style loops. TPP-MLIR generates loops around LIBXSMM kernels. TVM represents loop nests as schedules and searches for rewrites of them with tuning runs.
A TEIR program is rewritten by transformations that preserve its result, as a TVM schedule is. It is executed as loops around kernels, as in TBLIS and TPP-MLIR.
Compilation pipeline#
A contraction is compiled in three steps (Fig. 1). An emitter
translates the contraction, given in einsum notation together with the sizes
of its indices, into an initial TEIR program. In einsum notation,
dfae,cebf->dcba names the indices of the two inputs and of the output, and
the indices that are missing in the output, here e and f, are summed over.
The optimizer then rewrites the initial program by a sequence of transformations. Besides the program, it reads two descriptions of the target. The hardware parameters are the number of cores, the number of FP32 elements in a vector register, and the sizes of the L1, L2, and L3 caches. The program that calls the compiler determines them by querying the machine on which the contraction will run. The kernel capabilities describe the kernel library that the lowering targets. They state whether the library provides batch-reduce GEMM kernels and whether its kernels use a vector extension or a matrix extension such as SME.
The lowering finally maps the tile operations of the optimized program to kernels and the loops of its schedule to sequential and parallel code.
Fig. 1 Compilation of a tensor contraction with TEIR.#
The intermediate representation#
Fig. 2 shows four TEIR programs for the contraction
dfae,cebf->dcba, which serves as the running example.
Fig. 2 TEIR programs for the running example dfae,cebf->dcba. (a) The emitted
program is scalar, and no invocation maps to a kernel. (b) The Zero is sunk
into the K loops, and a, b, and f are promoted into the tile
operations. (c) The first input is packed into a buffer, and the
Contraction maps to a matrix-multiplication kernel (GEMM). (d) After
promoting e and parallelizing the loop over d, the Contraction maps to
a batch-reduce GEMM (BRGEMM). Brackets next to a loop list its buffers, and
italic labels name kernels. Panels (b) to (d) are hand-written examples.#
- Axes
An axis is a dimension of the iteration space with an extent. For every tensor, it carries a stride and an offset, counted in elements of that tensor. A stride of zero means that the axis does not index the tensor. Every index of the einsum expression starts as one axis, and the strides encode the layouts of the tensors. In the running example, the axis a has unit stride in the output and the stride |e| in the first input. Each axis also has a type. An M axis indexes only the first input and the output, an N axis only the second input and the output, a K axis only the two inputs, and a batch axis all three tensors.
- Tile operations
A tile operation describes a computation on tiles. Zero sets its output tile to zero, Copy copies its input tile to its output tile, and Contraction accumulates the contraction of its two input tiles into its output tile. Each tile operation lists its tile axes, which span the tiles. A Contraction sorts its tile axes into the roles M, N, and K. A tile operation without tile axes is scalar.
- Schedule
The schedule is an ordered forest of loop nodes and invocation nodes. A loop node iterates one axis and is either sequential or parallel. Sequential loops order the work in time, and parallel loops distribute it in space. An invocation node is a leaf that applies a tile operation to the tiles at the current indices of the enclosing loops. A node may carry a guard such as first(e), which restricts it to the first iteration of an enclosing loop. Guards let an initialization share the loops of a reduction. A buffer, which the Pack transformation introduces, belongs to a loop or to the whole program. Every iteration of its loop has its own instance, so buffers inside a parallel loop are private to each iteration.
Transformations#
A transformation rewrites a TEIR program into another program that computes the same output, up to the order of the floating-point accumulations. TEIR has seven transformations (Table 1).
Transformation |
Example |
Effect |
|---|---|---|
Split |
Replaces a loop over an axis by an outer and an inner loop whose extents multiply to the original extent. Split enables blocking. |
|
Merge |
Replaces a loop and the loop that is its only child by one loop. The two axes have to be contiguous in all tensors. Merge reduces the number of loops. |
|
Promote |
Removes a loop and adds its axis to the axes of its descendant tile operations whose operands the axis indexes. Promote enlarges the tiles and moves work from loops into kernels. |
|
Pack |
Replaces an operand by a buffer with a chosen layout in the tile operations below a chosen loop. For an input, a new Copy fills the buffer from the input before the buffer is read, as in the example. For the output, the tile operations write into the buffer, and a new Copy after them transfers the buffer to the output. Pack gives operands the layouts that kernels need. |
|
Reorder |
Exchanges a loop with the loop that is its only child. The loop order determines how tiles are reused in the caches. |
|
Sink |
Moves a node into the sibling loop next to it. A node before the loop is guarded with its first iteration, a node after it with its last. |
|
Parallelize |
Makes a sequential loop parallel. This requires that the iterations of the loop write to different parts of the output. Loops over M, N, and batch axes meet this requirement because their axes index the output. Loops over K axes do not, because all of their iterations accumulate into the same elements. |
Optimizer#
The optimizer is applied to the initial TEIR program that the emitter generates. This program has one loop per axis around a scalar Zero and a scalar Contraction, as in Fig. 2 (a). The optimizer is deterministic and computes the optimized program directly from the axes of the program, the hardware parameters, and the kernel capabilities.
It takes four decisions in a fixed order (Table 2). Each decision is taken once and is carried out by transformations. A later decision builds on the earlier ones and does not change them.
Step |
Name |
Decision |
Transformations |
|---|---|---|---|
1 |
Normalization |
Which loops can be combined |
Reorder, Merge |
2 |
Tiles |
Which axes become tile axes of the Contraction and how large the tiles are |
Split, Promote |
3 |
Loops |
In which order the remaining loops are nested and which of them run in parallel |
Sink, Reorder, Parallelize |
4 |
Packing |
Which operands are copied into buffers and at which loop |
Pack |
Step 1: Normalization. Loops of extent one are removed. Two axes of the
same type that are contiguous in all tensors address memory like one longer
axis. The optimizer moves their loops next to each other and merges them. In
abc,cd->abd, for example, a and b are adjacent in the first input and
in the output, so their loops merge into one loop over an M axis of extent
|a| · |b|.
Step 2: Tiles. The Contraction of the optimized program has to map to a GEMM kernel, which requires one tile axis per role. For each of the roles M, N, and K, the optimizer selects one axis and a tile size. The tile size is the number of consecutive indices of the axis that one kernel call covers. The optimizer prefers axes with unit stride and otherwise selects the axis with the smallest strides. The tile sizes meet two conditions. The three tiles of a kernel call fit together into one cache, which is the L1 cache for kernels that use AVX-512 or Neon and the L2 cache for kernels that use SME. In addition, the contraction consists of enough tiles to give work to every core, which leads to smaller tiles for contractions with few operations per tensor element.
Each selected axis is then split at its tile size. The inner axis is promoted and becomes a tile axis, and the outer axis remains a loop that iterates the tiles. If the kernel library provides batch-reduce GEMMs, a second K axis is promoted as the batch-reduce axis.
Step 3: Loops. The remaining loops iterate the outer parts of the split axes and the axes that were not selected in step 2. The loops among them that iterate K axes are placed innermost, directly around the Contraction, and run sequentially, because all of their iterations accumulate into the same output tile. The Zero is sunk into these loops, where a guard restricts it to their first iteration. The loops that iterate M, N, and batch axes are placed around the loops over the K axes and run in parallel, because each of their iterations writes a different part of the output. The parallel loops are ordered by the amount of data that changes from one iteration to the next, with the loop that changes the most data outermost. Consecutive iterations of the inner loops thus reuse tiles that are already in the caches.
Step 4: Packing. The kernels have BLAS-like interfaces. They address a tile as a column-major matrix with a leading dimension, which requires unit stride on one of the tile axes of the operand. The optimizer packs an operand if none of its tile axes has unit stride, if the kernel is faster with the transposed layout, or if the columns of its tile would evict each other from the cache because they map to the same cache sets. A packed input tile is copied into its buffer right before the Contraction that reads it. For a packed output, the Contraction accumulates into the buffer, and a Copy after the loops over the K axes transfers the buffer to the output tensor. There is one exception for large inputs. An input that exceeds its share of the L3 cache and is read more than twice by the kernels is packed once as a whole before the loops of the contraction, and not tile by tile inside them.
Implementation#
The compiler is implemented in MLIR and targets multicore CPUs. A TEIR program is a single MLIR operation that stores its axes, tile operations, buffers, and schedule as attributes. The emitter is called through a C++ API. The caller passes the hardware parameters (see Compilation pipeline), and the API attaches them to the operation.
The optimizer is an MLIR pass that replaces this operation by one that holds the optimized program. It expresses its decisions as a list of transformations, applies them in order, and checks the validity of the program after each one.
The lowering maps the loops of the schedule to loops of MLIR’s SCF dialect, and the parallel loops among them become OpenMP loops. Tile operations with a matching kernel become operations of a modified XSMM dialect adapted from TPP-MLIR, which in turn become calls of LIBXSMM kernels. LIBXSMM generates these kernels at runtime for AVX-512 on x86 and for Neon and the Scalable Matrix Extension (SME) on Arm. The remaining operations lower to MLIR’s LLVM dialect, and MLIR’s execution engine compiles the module in process.
The lowering selects the kernel of a tile operation from its tile axes. A Zero or a Copy with one or two tile axes maps to an elementwise kernel, which also transposes, and to scalar loops otherwise. A Contraction with one tile axis per role maps to a GEMM, and a Contraction with a second K axis maps to a batch-reduce GEMM (BRGEMM), which sums the products over that axis into one output tile. Every kernel treats a tile as a column-major matrix and thus needs unit stride on one of its tile axes.
Evaluation#
Setup#
The evaluation covers three instruction-set extensions on three machines (Table 3). All computations use single-precision (FP32) arithmetic.
Extension |
Machine |
Cores used |
|---|---|---|
AVX-512 |
HP Z2 Mini G1a with an AMD Ryzen AI Max PRO 390 |
all 12 Zen 5 cores |
Neon |
NVIDIA Grace CPU Superchip |
the 72 Neoverse V2 cores of one of the two CPUs |
SME |
Mac Studio with an Apple M4 Max |
the 12 performance cores, which form two clusters with one SME unit each |
Benchmark#
The benchmark is the set of 24 contractions of the Tensor Contraction Code Generator (TCCG) by Springer and Bientinesi. They comprise coupled-cluster contractions and integral transformations from quantum chemistry and tensor-times-matrix products from tensor decompositions.
TCCG defines its contractions in column-major order, where the first index of a tensor has unit stride. Einsum strings on this page are read in row-major order, where the last index has unit stride. The evaluation uses two sets of 24 contractions each (Table 4). The column-major set is the TCCG benchmark with its original memory layouts, which are obtained by reversing the index string of every tensor. The row-major set uses the index strings of TCCG unchanged. Its tensors have other memory layouts, so its contractions differ from those of the column-major set and only share their index sizes.
# |
Row-major set |
Column-major set (TCCG) |
Index sizes |
Work (GFLOP) |
|---|---|---|---|---|
1 |
|
|
a=48, b=36, c=24, d=36, e=48, f=36 |
5.16 |
2 |
|
|
a=48, b=24, c=36, d=36, e=48, f=36 |
5.16 |
3 |
|
|
a=96, b=84, c=24, d=96, e=96 |
3.57 |
4 |
|
|
a=48, b=36, c=36, d=24, e=48, f=48 |
6.88 |
5 |
|
|
a=96, b=24, c=84, d=96, e=84 |
3.12 |
6 |
|
|
a=384, b=384, c=24, d=384 |
2.72 |
7 |
|
|
a=96, b=84, c=24, d=84, e=96 |
3.12 |
8 |
|
|
a=24, b=20, c=20, d=24, e=20, f=20, g=24 |
4.42 |
9 |
|
|
a=24, b=20, c=20, d=24, e=20, f=20, g=24 |
4.42 |
10 |
|
|
a=24, b=20, c=20, d=24, e=20, f=20, g=24 |
4.42 |
11 |
|
|
a=24, b=20, c=20, d=24, e=20, f=20, g=24 |
4.42 |
12 |
|
|
a=384, b=24, c=376, d=384 |
2.66 |
13 |
|
|
a=96, b=84, c=84, d=84, e=96 |
10.92 |
14 |
|
|
a=96, b=84, c=84, d=84, e=96 |
10.92 |
15 |
|
|
a=96, b=84, c=84, d=84, e=96 |
10.92 |
16 |
|
|
a=96, b=84, c=84, d=84, e=96 |
10.92 |
17 |
|
|
a=384, b=376, c=384, d=384 |
42.58 |
18 |
|
|
a=384, b=376, c=376, d=384 |
41.69 |
19 |
|
|
a=384, b=376, c=376, d=384 |
41.69 |
20 |
|
|
a=384, b=384, c=376, d=376 |
41.69 |
21 |
|
|
a=7248, b=7240, c=7248 |
760.69 |
22 |
|
|
a=96, b=84, c=84, d=84, e=84, f=96 |
917.68 |
23 |
|
|
a=96, b=84, c=84, d=84, e=96, f=96 |
1048.77 |
24 |
|
|
a=96, b=84, c=84, d=96, e=84, f=84 |
917.68 |
TEIR is compared with the backends of Table 5. Every contraction ran 10 times as warm-up and 200 times for the measurement. The reported performance is the median of the 200 runs in GFLOPS (\(10^9\) floating-point operations per second). A backend completed a contraction if compilation, warm-up, and all 200 runs finished without error. The backends ran without a time limit, with two exceptions. A tuning trial of TVM was limited to 2 minutes. TPP-MLIR was the only backend that needed a limit for its runs, because some of them did not terminate in acceptable time. The warm-up and the runs of a contraction were stopped after 20 minutes and repeated up to two times, and the contraction counts as not completed if the third attempt was stopped as well.
Backend |
Version |
Measured on |
|---|---|---|
commit eb719e71 |
AVX-512, Neon |
|
0.26.0, tuned with MetaSchedule for 2000 trials per contraction |
AVX-512, Neon |
|
26.2.1 |
AVX-512, Neon |
|
2.14.0, |
AVX-512, Neon, SME |
|
commit 7d62d4fa |
AVX-512, Neon, SME |
|
1.5.1 with the XNNPACK backend |
SME |
As a reference, every contraction is accompanied by a matrix multiplication of the same size. Its three sizes are the products of the extents of the M, N, and K axes of the contraction. It runs in the BLAS library of the vendor, which is AOCL-BLAS 5.1 on the Ryzen machine, NVPL BLAS on the Grace CPU, and Accelerate on the M4 Max.
Results#
TEIR completed all 24 contractions of both sets on all three machines. Table 6 gives its performance in the geometric mean over the 24 contractions, and Fig. 3 its speedups over the other backends. In row-major order, the smallest speedup on each machine is 1.9 over TVM on the Ryzen machine and 1.5 over PyTorch on the Grace CPU and on the M4 Max. In column-major order, it is 2.1 over TBLIS on the Ryzen machine, 1.2 over TVM on the Grace CPU, and 1.5 over PyTorch on the M4 Max.
Set |
AVX-512 (Ryzen AI Max) |
Neon (Grace) |
SME (M4 Max) |
|---|---|---|---|
Row-major |
1022 |
2833 |
1115 |
Column-major |
1159 |
2948 |
1456 |
Fig. 3 Speedup of TEIR over the other backends. A speedup is the geometric mean of the ratio of the performance of TEIR to the performance of the backend over the contractions that the backend completed. For a backend that completed fewer than 24 contractions, their number is given in parentheses. The vertical line marks equal performance.#
Two TVM results are missing because the tuning of TVM has not finished. On the Ryzen machine, TVM has only been tuned for the row-major set. On the Grace CPU, the contractions 21 to 24 of the column-major set are missing.
On the Ryzen machine (Fig. 4), TEIR reaches 388 to 2696 GFLOPS per contraction in row-major order and 414 to 2712 GFLOPS in column-major order. It is the fastest backend on 19 of the 24 contractions in row-major order, where einsum_ir is ahead on three contractions and TVM on two. In column-major order, it is the fastest backend on 22 contractions, and einsum_ir is ahead on the other two.
Fig. 4 Median performance per contraction on the AMD Ryzen AI Max PRO 390 using AVX-512, in row-major order (top) and column-major order (bottom). A backend without a marker did not complete the contraction. The dashed lines mark the matrix multiplication of the same size in the vendor BLAS library, which is the same measurement in both panels.#
On the Grace CPU (Fig. 5), TEIR reaches 955 to 5726 GFLOPS per contraction in row-major order and 501 to 5928 GFLOPS in column-major order. It is the fastest backend on 18 contractions in row-major order, where TVM is ahead on three contractions, PyTorch on two, and TBLIS on one. In column-major order, it is the fastest backend on 17 contractions, and TVM is ahead on four contractions, TPP-MLIR on two, and einsum_ir on one.
Fig. 5 Median performance per contraction on the NVIDIA Grace CPU using Neon, in row-major order (top) and column-major order (bottom). A backend without a marker did not complete the contraction. The dashed lines mark the matrix multiplication of the same size in the vendor BLAS library.#
On the M4 Max (Fig. 6), TEIR reaches 326 to 3453 GFLOPS per contraction in row-major order and 459 to 3740 GFLOPS in column-major order. It is the fastest backend on 17 contractions in row-major order, where PyTorch is ahead on four contractions, ExecuTorch on two, and TPP-MLIR on one. In column-major order, it is the fastest backend on 21 contractions, and PyTorch is ahead on the other three.
Fig. 6 Median performance per contraction on the Apple M4 Max using SME, in row-major order (top) and column-major order (bottom). A backend without a marker did not complete the contraction. The dashed lines mark the matrix multiplication of the same size in the vendor BLAS library.#
SC’26 poster#
TEIR is presented as a research poster at SC’26. The
poster and its
extended abstract are available as
PDFs.