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.

Overview of the compilation, in which a tensor contraction is emitted as a TEIR program, which a deterministic optimizer rewrites through transformations before a lowering maps it to LIBXSMM kernels and OpenMP loops

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.

Four schedules of the running example as trees of loop nodes and invocations, from the emitted scalar program to a parallel program around a batch-reduce GEMM

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).

Table 1 The transformations of TEIR, each with an example in the notation of Fig. 2#

Transformation

Example

Effect

Split

Split applied to a small TEIR schedule, before and after

Replaces a loop over an axis by an outer and an inner loop whose extents multiply to the original extent. Split enables blocking.

Merge

Merge applied to a small TEIR schedule, before and after

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

Promote applied to a small TEIR schedule, before and after

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

Pack applied to a small TEIR schedule, before and after

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

Reorder applied to a small TEIR schedule, before and after

Exchanges a loop with the loop that is its only child. The loop order determines how tiles are reused in the caches.

Sink

Sink applied to a small TEIR schedule, before and after

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

Parallelize applied to a small TEIR schedule, before and after

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.

Table 2 Decisions of the optimizer and the transformations that carry them out#

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.

Table 3 Machines of the evaluation#

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.

Table 4 The contractions of the row-major and the column-major set in einsum notation with the sizes of their indices. The last column gives the work of one execution in \(10^9\) floating-point operations, which is \(2 \prod_{x} |x|\) over all indices \(x\) of the contraction.#

#

Row-major set

Column-major set (TCCG)

Index sizes

Work (GFLOP)

1

efbad,cf->abcde

dabfe,fc->edcba

a=48, b=36, c=24, d=36, e=48, f=36

5.16

2

efcad,bf->abcde

dacfe,fb->edcba

a=48, b=24, c=36, d=36, e=48, f=36

5.16

3

dbea,ec->abcd

aebd,ce->dcba

a=96, b=84, c=24, d=96, e=96

3.57

4

ecbfa,fd->abcde

afbce,df->edcba

a=48, b=36, c=36, d=24, e=48, f=48

6.88

5

deca,be->abcd

aced,eb->dcba

a=96, b=24, c=84, d=96, e=84

3.12

6

bda,dc->abc

adb,cd->cba

a=384, b=384, c=24, d=384

2.72

7

ebad,ce->abcd

dabe,ec->dcba

a=96, b=84, c=24, d=84, e=96

3.12

8

dega,gfbc->abcdef

aged,cbfg->fedcba

a=24, b=20, c=20, d=24, e=20, f=20, g=24

4.42

9

dfgb,geac->abcdef

bgfd,caeg->fedcba

a=24, b=20, c=20, d=24, e=20, f=20, g=24

4.42

10

degb,gfac->abcdef

bged,cafg->fedcba

a=24, b=20, c=20, d=24, e=20, f=20, g=24

4.42

11

degc,gfab->abcdef

cged,bafg->fedcba

a=24, b=20, c=20, d=24, e=20, f=20, g=24

4.42

12

dca,bd->abc

acd,db->cba

a=384, b=24, c=376, d=384

2.66

13

ea,ebcd->abcd

ae,dcbe->dcba

a=96, b=84, c=84, d=84, e=96

10.92

14

eb,aecd->abcd

be,dcea->dcba

a=96, b=84, c=84, d=84, e=96

10.92

15

ec,abed->abcd

ce,deba->dcba

a=96, b=84, c=84, d=84, e=96

10.92

16

adec,ebd->abc

ceda,dbe->cba

a=96, b=84, c=84, d=84, e=96

10.92

17

cad,dcb->ab

dac,bcd->ba

a=384, b=376, c=384, d=384

42.58

18

acd,dbc->ab

dca,cbd->ba

a=384, b=376, c=376, d=384

41.69

19

acd,db->abc

dca,bd->cba

a=384, b=376, c=376, d=384

41.69

20

adc,bd->abc

cda,db->cba

a=384, b=384, c=376, d=376

41.69

21

ac,cb->ab

ca,bc->ba

a=7248, b=7240, c=7248

760.69

22

aebf,fdec->abcd

fbea,cedf->dcba

a=96, b=84, c=84, d=84, e=84, f=96

917.68

23

eafd,fbec->abcd

dfae,cebf->dcba

a=96, b=84, c=84, d=84, e=96, f=96

1048.77

24

aebf,dfce->abcd

fbea,ecfd->dcba

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.

Table 5 Backends of the comparison#

Backend

Version

Measured on

TBLIS

commit eb719e71

AVX-512, Neon

TVM

0.26.0, tuned with MetaSchedule for 2000 trials per contraction

AVX-512, Neon

einsum_ir

26.2.1

AVX-512, Neon

PyTorch

2.14.0, torch.einsum

AVX-512, Neon, SME

TPP-MLIR

commit 7d62d4fa

AVX-512, Neon, SME

ExecuTorch

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.

Table 6 Performance of TEIR in GFLOPS, as the geometric mean over the 24 contractions of a set#

Set

AVX-512 (Ryzen AI Max)

Neon (Grace)

SME (M4 Max)

Row-major

1022

2833

1115

Column-major

1159

2948

1456

Bar chart of the speedup of TEIR over each backend on the three machines, in row-major and in column-major order

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.

Median GFLOPS of all backends for each of the 24 TCCG contractions on the AMD Ryzen AI Max PRO 390, in row-major and in column-major order

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.

Median GFLOPS of all backends for each of the 24 TCCG contractions on the NVIDIA Grace CPU, in row-major and in column-major order

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.

Median GFLOPS of all backends for each of the 24 TCCG contractions on the Apple M4 Max, in row-major and in column-major order

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.