betaFeedback

WorksComputer Science

Waypoint: Analytically Modeling GEMM for CPUs

Abstract

High-performance General Matrix Multiplication (GEMM) implementations rely on breaking down GEMM into carefully selected tiles to achieve peak performance. We present Waypoint, a new analytical model to automatically identify the optimal tile size for a given hardware and input matrix shape. Waypoint estimates the achievable performance for a given tile choice by capturing all the architectural effects including interactions with memory hierarchy, instruction-level parallelism, and multi-threading. Using the estimates as a proxy, we search through the space of possible tile sizes to identify the one that maximizes performance. Additionally, Waypoint helps hardware designers estimate realistic performance on experimental hardware optimizations. We build a new GEMM library OPAM for CPUs that uses Waypoint to automatically break down GEMM and achieve performance that matches state-of-the-art GEMM libraries and helps accelerate LLM inference on CPUs achieving 1.36−1.98×1.36 - 1.98 \times speedups.

Introduction

Matrix Multiplication operations make up for a large part of the core computation in several modern machine learning based applications such as image processing, recommendation systems, and more recently, Large Language Model (LLM) inference. To ensure that these applications run efficiently, it is crucial to optimize the performance of General Matrix Multiplication (GEMM) operations on the underlying hardware. While the industry has moved towards developing specialized hardware accelerators such as GPUs, CPUs remain important for cost-sensitive use cases and small-scale inference workloads. Hardware vendors continue to enhance CPU architectures with new features aimed at improving GEMM performance.

On CPUs, improving GEMM performance involves careful coordination between the hardware and the software that implements GEMM operations. Hardware designers continue to innovate and introduce features that push the peak performance achievable. At the same time, software implementations optimize the use of these hardware features to achieve high performance.

A naive 3-loop implementation of the matrix multiplication algorithm is far from achieving peak performance. Instead, the libraries use specialized hardware features (e.g. vector/matrix instructions), and carefully organize the input matrices in memory so as to reduce the cost of accessing them for the computation. They do so by breaking down the GEMM operation into smaller units called tiles. For each tile, the libraries use vector/matrix instructions to compute the output, and between successive tiles, they ensure that memory accesses are efficient.

The tile sizes are critical to achieving high performance and need to be chosen carefully. Selecting suboptimal tile sizes can lead to inefficient memory accesses and under-utilization of the hardware’s computational capabilities. The right tile depends both on the hardware and the specific input matrix size that the application invokes 1. Therefore, an ideal solution would adapt the tile sizes not only to the hardware but also to specific input sizes.

Existing state-of-the-art GEMM libraries [16, 30] identify the tile sizes that are either optimal for a given hardware, or the specific class of shapes (e.g., tall and skinny [23], irregular [31]) but do not adapt them to the application’s needs. Many techniques are used to identify the tile sizes for a given hardware such as - manual expert-driven tuning resulting in handwritten assembly, automated empirical analysis [7, 10], and analytical modeling [24, 26, 31].

In this paper we propose a new analytical model to derive optimal tile sizes that are tailored not just for the hardware but also for the specific input matrix sizes that the application uses. Our model addresses another crucial challenge that the hardware designers face when innovating to accelerate performance on future hardware. They need to be able to estimate the realistic performance achievable on experimental hardware designs. They routinely propose new ISA extensions (e.g. AMX [21], ACE [33], APX [20]) aimed at optimizing GEMM performance.

Existing analytical models address the challenge partially. They provide a Roofline [32] estimate of the maximum achievable performance. But depending on the matrix sizes, the realistic achievable performance is far from the Roofline.

Building a realistic performance model requires accounting for different architectural effects that are accompanied with a GEMM operation such as cache effects, pipelining, multi-threaded execution, and memory bandwidth limitations. The traditional Roofline model makes simplistic assumptions to over-approximate the peak performance achievable. It assumes that either the cost of computation dominates the cost of accessing data (i.e. compute-bound) or vice versa (i.e. memory-bound), which rarely holds true in practice. Therefore, a more nuanced model that captures both computation and memory access costs accurately is necessary to predict realistic GEMM performance.

In what follows, we describe our contribution - a new analytical model WAYPOINT that is parametric both in the hardware architecture, and the application’s needs (input matrix sizes). WAYPOINT provides accurate estimates of the realistic performance achievable, aiding hardware designers, and identifies the optimal tile sizes, enabling automatic and efficient GEMM implementations.

We build our model in two stages. First, we develop WAYPOINT-STRICT, to provide realistic estimates of GEMM performance on a given hardware independent of the software implementation. We prove theoretically that WAYPOINT-STRICT is tighter than the Roofline model and show empirically that state-of-the-art GEMM libraries realize these estimates. In compute-bound scenario, WAYPOINT-STRICT accounts for the cost of additional instructions that are always issued with the main compute instruction. Similarly for the memory-bound scenario, WAYPOINT-STRICT uses more accurate bandwidth values to calculate the time it takes to fetch data. As a result, in both scenarios, WAYPOINT provides estimates that are tighter than the Roofline.

Second, we refine WAYPOINT-STRICT for a tile based GEMM implementation resulting in WAYPOINT-TILE that estimates GEMM performance for a specific tile size. Using WAYPOINT-TILE’s estimates, we search through possible tile sizes to select the optimal one. Building WAYPOINT-TILE is challenging because it requires accurately modeling the interaction between the tile size and the memory hierarchy, including cache levels, cache line sizes, and memory bandwidth limitations. WAYPOINT-TILE accurately estimates the number of cache misses that are imposed by a tile size and adds the associated miss costs. In building WAYPOINT-TILE, we identify several insights that allow us to rule out certain tile sizes and narrow down the search for an optimal one.

Empirically, we evaluate the accuracy of both WAYPOINT-STRICT and WAYPOINT-TILE against state-of-the-art GEMM libraries. We find that WAYPOINT-STRICT estimates are consistently closer to the observed performance (a geomean of 1.096×). Similarly, we compare the estimate of the best tile size identified by WAYPOINT-TILE and find that the model is accurate in predicting realistic performance (a geomean of 1.012×). These accuracy results allow us to confidently use the models for identifying the optimal tile size and estimating the performance on future hardware.

We develop a GEMM library OPAM that uses WAYPOINT-TILE to select the best tile size for each input matrix size and hardware configuration. OPAM performs comparable to state-of-the-art GEMM libraries across different hardware configurations and input sizes. Further on new hardware configurations, OPAM is able to quickly adapt and achieve near-peak performance without any manual tuning. Finally, we use OPAM to accelerate LLM inference on CPUs achieving 1.36 – 1.98× speedups on new hardware.

To summarize, our contributions are,

  • An accurate implementation agnostic analytical model WAYPOINT-STRICT, to estimate GEMM performance that is parametric in both the hardware architecture and the application’s needs. A more refined model, WAYPOINT-TILE that is specific to a tile-based GEMM implementation and used in practice to identify the optimal tile-size.

  • A GEMM library OPAM that uses WAYPOINT-TILE to automatically select optimal tiling parameters for a given GEMM shape and hardware configuration, achieving near-peak performance without extensive manual or automated tuning.

  • Using OPAM, we accelerate LLM inference on current and future CPUs.

Analytical Model

The Roofline model [32] distinguishes a computation between a compute-bound scenario, where performance is limited by the processing capacity of the CPU, and a memory-bound scenario, where performance is limited by the memory bandwidth. It provides upper bounds in either case based on the peak computational throughput and memory bandwidth of the hardware.

Building on the Roofline model specifically for GEMM computations, we first develop an implementation-agnostic WAYPOINT-STRICT that refines the cost in both compute-bound and memory-bound scenarios. Then, we further refine the compute cost assuming a tiled GEMM implementation to obtain a WAYPOINT-TILE that captures accurately the number of cache misses and the associated costs. We prove theoretically that the WAYPOINT-STRICT is tighter than the Roofline model and empirically show (in § 4) that the WAYPOINT-TILE is accurate.

Waypoint-Strict

The Waypoint-Strict is parametric in the hardware configuration, including cache sizes, memory bandwidth, and compute instructions and provides an estimate of the number of cycles a GEMM operation will take on the given hardware. Formally a hardware configuration HH consists of the following constants:

  • The instruction reciprocal throughput for the core compute instruction τfma\tau_{fma} and the dimensions of the instruction δfma\delta_{fma}. The instruction is defined for each data-type and instruction set architecture (ISA) of the CPU. For example, in an x86-ISA based CPU using AVX512 family of SIMD instructions, the instruction reciprocal throughput for a single precision FMA instruction in AMD ‘Zen 5’ architecture is 0.5 cycles/instruction and contains 16×116 \times1 elements.

  • Register file information such as the number of registers available to issue FMA instructions NregN_{reg} and width of the registers in bits WregW_{reg}.

  • Cache sizes (SL1,SL2,SL3S_{L1}, S_{L2}, S_{L3}) and access reciprocal throughput (TL1,TL2,TL3T_{L1}, T_{L2}, T_{L3}) for the different levels of the memory hierarchy. For example, on AMD ‘Zen 5’ cores, the L1 data cache is 48 KB with an access reciprocal throughput of 0.5 cycles.

  • Memory bandwidth information, including the peak bandwidth per memory channel DbwD_{bw} and the number of channels DnD_n.

  • Maximum number of cores CmaxC_{max} and the frequency ff of the CPU. The frequency is used to convert the number of cycles to time.

We define a GEMM operation opop as one that computes an output matrix C=a(A⋅B)+bCC = a(A \cdot B) + bC of size M⋅NM \cdot N where the input matrices are of size M⋅KM \cdot K and K⋅NK \cdot N using TT threads on the data-type dd of width WdW_d bits, and scalars aa and bb. We assume for simplicity that a=1a = 1 and b=0b = 0.

Given the hardware and GEMM operation, the Waypoint-Strict computes the latency LopL_{op} of the GEMM operation as follows:

L(op)=max⁡(Lc(op)op.T,Lm(op))+Lmt(op)L(op) = \max\left(\frac{L_c(op)}{op.T}, L_m(op)\right) + L_{mt}(op)

where LcL_c is the compute latency, LmL_m is the memory latency, and LmtL_{mt} is the threading overhead for the GEMM operation opop. In what follows, we describe each of the components in detail.

Compute latency

The Waypoint-Strict assumes a deterministic compute instruction to be used for a given data-type and hardware architecture e.g. AVX512 VNNI is used for Int8 GEMM on x86-ISA based CPUs. The exact mapping can be provided as input. We first compute the number of compute instructions NfmaN_{fma} required to perform the GEMM:

Nfma=M⋅N⋅K/δfmaN_{fma} = M \cdot N \cdot K/\delta_{fma}

Where δfma\delta_{fma} is used to denote the number of elements in an instruction e.g. In an AVX512 VNNI instruction that computes a column-wise dot product of two 4×164 \times16 matrices of 8-bit integers, δfma=4×16=64\delta_{fma} = 4 \times16 = 64.

Instruction Modularity. By allowing the user to define the dimensions of the core compute instruction, we accommodate new advances in the x86-ISA architecture that enable matrix instructions such as AMX, ACE, Arm SME. A matrix instruction can compute a matrix product of two matrices of size mfma⋅kfmam_{fma} \cdot k_{fma} and kfma⋅nfmak_{fma} \cdot n_{fma} in a single instruction. Therefore, the number of compute instructions is Nc=M⋅N⋅K/(mfma⋅kfma⋅nfma)N_c = M \cdot N \cdot K/(m_{fma} \cdot k_{fma} \cdot n_{fma}).

The latency of the compute instructions is computed as Nfma∗τfmaN_{fma} * \tau_{fma} where τfma\tau_{fma} is the instruction reciprocal throughput for the core computation.

In addition to the latency of the compute instruction, the total compute latency LcL_c includes the latency of support instructions for zeroing the registers LzL_z, loading the input matrices LdinL_{din} into the registers (assuming perfect cache behavior), and storing the output matrix back to memory LdoutL_{dout}. We assume that stores hit the nearest cache and thus incur the lowest latency.

Memory latency

The memory latency LmL_m is computed using the peak memory bandwidth applicable for the GEMM operation.

Lm(op)=(M⋅K+K⋅N+M⋅N)⋅Wd⋅fDbw⋅dnL_m(op) = \frac{(M \cdot K + K \cdot N + M \cdot N) \cdot W_d \cdot f}{D_{bw} \cdot d_n}

where dn≤Dnd_n \le D_n is the number of memory channels accessible to the GEMM operation.

When running multithreaded GEMM programs, the bandwidth available to each thread may be lower than the peak bandwidth because of contention among threads accessing memory. We capture the effect of this contention using a model that distributes work across different memory channels, allowing us to predict data-access latency more accurately.

For example, on AMD ‘Zen 5’ processors, if a GEMM operation uses fewer than eight threads (the size of a single Core Complex Die, or CCD), it can utilize the memory bandwidth of a single CCD. If more threads are used, the operation may need to access multiple CCDs, potentially increasing effective memory latency because of contention across memory channels.

Threading overhead

To compute the threading overhead, we assume that there is no data contention between threads. This assumption is grounded in practice, as it reflects the behavior of well-optimized GEMM implementations. When the assumption does not hold, the threads must synchronize to read and write data, incurring additional overhead.

It follows from our assumption that each thread consumes the entire KK dimension to compute the result and the input matrices are split only in the MM and NN dimensions. Let MtM_t and NtN_t be the splits across the MM and NN dimensions of the output matrix for each thread.

The data needed by each thread is SAt=Mt⋅K⋅WdS_{A_t}=M_t\cdot K\cdot W_d and SBt=K⋅Nt⋅WdS_{B_t}=K\cdot N_t\cdot W_d. The data that does not fit in the caches, Δ=SAt+SBt−(SL3+SL2+SL1)\Delta=S_{A_t}+S_{B_t}-(S_{L3}+S_{L2}+S_{L1}), is repeatedly accessed from memory by multiple threads, incurring significant overhead. We define the threading overhead as follows:

Lmt=min⁡(Δ⋅Mt,Δ⋅Nt)⋅1Dbw⋅dnL_{mt}=\min(\Delta\cdot M_t,\Delta\cdot N_t)\cdot\frac{1}{D_{bw}\cdot d_n}

To capture the scenario in which the KK dimension is also split, we account for the cost of the reduction operation that follows the partial computations across different threads. This reduction typically involves summing the partial results along the KK dimension, which introduces additional memory accesses and synchronization overhead.

Theoretical results

The Roofline model estimates peak performance for a given GEMM operation as,

P=min⁡(Cpeak,Bpeak⋅I(op))=2⋅M⋅N⋅K⋅fLr(op)P=\min(C_{peak},B_{peak}\cdot I(op))=\frac{2\cdot M\cdot N\cdot K\cdot f}{L^{r}(op)}

where CpeakC_{peak} is the peak compute performance of the CPUs, BpeakB_{peak} is the peak memory bandwidth of the CPU, I(op)I(op) is the operational intensity of the GEMM operation, and Lr(op)L^{r}(op) is the Roofline latency. Formally,

Cpeak=2⋅δfma⋅op.T⋅fτfmaBpeak=max⁡D(Dbw⋅Dn)C_{peak}=\frac{2\cdot\delta_{fma}\cdot op.T\cdot f}{\tau_{fma}} \qquad B_{peak}=\max_D(D_{bw}\cdot D_n)
I(op)=2⋅M⋅N⋅K(M⋅K+K⋅N+M⋅N)⋅WdI(op)=\frac{2\cdot M\cdot N\cdot K}{(M\cdot K+K\cdot N+M\cdot N)\cdot W_d}

Substituting the definitions, the resulting latency estimate Lr(op)L^{r}(op) of the Roofline model is:

Lr(op)={M⋅N⋅K⋅τfmaδfma⋅Tif I>CpeakBpeak(M⋅N+M⋅K+K⋅N)⋅Wd⋅fDbwmax⋅DnmaxotherwiseL^{r}(op)= \begin{cases} \dfrac{M\cdot N\cdot K\cdot\tau_{fma}}{\delta_{fma}\cdot T} & \text{if } I>\dfrac{C_{peak}}{B_{peak}}\\[6pt] \dfrac{(M\cdot N+M\cdot K+K\cdot N)\cdot W_d\cdot f}{D_{bw}^{max}\cdot D_n^{max}} & \text{otherwise} \end{cases}

To compare, the Waypoint-Strict is designed to provide more realistic estimates of latency in comparison to the Roofline model. We capture the result in the following theorem,

Theorem 2.1. For any GEMM operation opop on a given hardware configuration HH, Lr(op)≤L(op)L^{r}(op)\leq L(op).

The theorem follows trivially from the definitions of L(op)L(op) and Lr(op)L^{r}(op). In the compute bound case, the Waypoint-Strict accounts for additional cost in the compute latency LcL_c such

as the cost of zeroing registers, loading, and storing data. Similarly, in the memory bound case, the effective bandwidth is at most Dbw⋅DnD_{bw}\cdot D_n. In both cases, the additional threading overhead LmtL_{mt} might be non-zero. Therefore, the Waypoint-Strict is tighter than Roofline.

Soundness of the assumptions

Figure 1 reinforces the theoretical result empirically. We compare the latency estimates of the Waypoint-Strict and the Roofline model on two different hardware configurations for many different shapes. The modest improvement over Roofline (upto 3%) is significant since performance of optimized GEMM libraries match the estimates (with 0.03% gap) for specific input matrix sizes.

Additional latency captured by the Waypoint-Strict relative to Roofline across GEMM shapes

Figure 1. Additional latency captured by the Waypoint-Strict relative to Roofline across GEMM shapes, separated by hardware and data type. Boxes show the interquartile range and median; points show individual shapes.

Waypoint-Tile

While the Waypoint-Strict provides a tighter-than-roofline estimate, it does not provide a mechanism to realize the estimates. Therefore, we refine the Waypoint-Strict to account for a tiling-based GEMM implementation. The Waypoint-Tile helps identify the best tiling parameters for a given GEMM operation on a given hardware configuration. Using the tiling parameters, we construct a GEMM implementation (Section 3) that demonstrates the realizability of the estimates. To identify the best tiling parameters, we augment the GEMM operation with three levels of tiling parameters: the register tiles (Mr,Nr)(M_r,N_r) that form the two inner loops of Algorithm 1, the cache-tile parameters (Mc,Nc,Kc)(M_c,N_c,K_c), and the multithreading-tile parameters (Mt,Nt)(M_t,N_t). The Waypoint-Tile computes the latency of the GEMM operation for a given tiling option. Note that Algorithm 1 is one possible instantiation of the tiled implementation. In our implementation, we select the loop ordering that works best for a given tile parameter set.

Given the Waypoint-Tile, we then search the space of possible tiling options to identify the best. While theoretically, the search space suffers from combinatorial explosion, we describe heuristics to prune the search. In Section 4, we also show that the best tiling parameters identified using the Waypoint-Tile improve over the state-of-the-art GEMM libraries across many different matrix shapes and hardware configurations. Waypoint-Tile makes certain assumptions of the behavior of the underlying hardware and implementation such as strided data accesses, fixed frequency workload, and using the best compute instruction available (e.g. AVX512 on x86 Systems). For the sake of brevity, we defer the details to Appendix C

Algorithm 1 Tiled GEMM: C+=A⋅BC += A \cdot B

Require: A∈RM×KA \in\mathbb{R}^{M \times K}, B∈RK×NB \in\mathbb{R}^{K \times N}, C∈RM×NC \in\mathbb{R}^{M \times N}

Require: Thread tile (Mt,Nt)(M_t, N_t), Macro tile (Mc,Nc,Kc)(M_c, N_c, K_c), Micro tile (Mr,Nr,Kr)(M_r, N_r, K_r)

  1. for jd←0j_d \leftarrow0 to N−1N - 1 step NtN_t

  2. for id←0i_d \leftarrow0 to M−1M - 1 step MtM_t

  3. for jc←jdj_c \leftarrow j_d to jd+Nt−1j_d + N_t - 1 step NcN_c

  4. for ic←idi_c \leftarrow i_d to id+Mt−1i_d + M_t - 1 step McM_c

  5. for kc←0k_c \leftarrow0 to K−1K - 1 step KcK_c

  6. for jr←jcj_r \leftarrow j_c to jc+Nc−1j_c + N_c - 1 step NrN_r

  7. for ir←ici_r \leftarrow i_c to ic+Mc−1i_c + M_c - 1 step MrM_r

  8. C[ir,jr]+=A[ir,kc]⋅B[kc,jr]C[i_r, j_r] += A[i_r, k_c] \cdot B[k_c, j_r]

  9. end for

  10. end for

  11. end for

  12. end for

  13. end for

  14. end for

  15. end for

Apart from providing accurate estimates of GEMM operation for a given tiling option, the Waypoint-Tile also ranks the different tiling options accurately, based on their expected performance. We show empirically that the estimates of the best-tiling options are accurate within 5% for existing hardware configurations.

The Waypoint-Tile reformulates the compute cost LcL_c taking the tiling parameters into account. Specifically, we first break up the computation into micro-kernels – the inner most loop that iterates over the (Mr,Nr,Kc)(M_r, N_r, K_c) dimensions. Then, for each micro-kernel, we account for additional costs such as cache access overheads when the tiling parameters are not optimal. Further, we add overheads for data movement costs at the macro-kernel level – the outer (Mc,Nc)(M_c, N_c) loops. We redefine the compute cost LcL_c as follows,

Lc=Lμ∗Nμ+Lω∗NωL_c = L_\mu* N_\mu+ L_\omega* N_\omega

where LμL_\mu and NμN_\mu are the latency and number of micro-kernels, and LωL_\omega and NωN_\omega are the latency and number of macro-kernels.

We identify several analytical insights that capture the architectural behavior of the CPU and help prune the search space for the best tiling parameters. We describe the Waypoint-Tile in detail below.

Micro-kernel cost

The micro-kernel loop computes an output matrix of size Mr×NrM_r \times N_r from input matrices of sizes Mr×KcM_r \times K_c and Kc×NrK_c \times N_r. The micro-kernel is the innermost loop of the GEMM operation, where the bulk of the computation occurs, and is typically implemented in handwritten assembly code optimized for the specific hardware. The data needed for the micro-kernel is fetched from the L1 cache (closest to the CPU).

The handwritten assembly code for the micro-kernel has the following segments: (1) zero/load instructions to initialize the registers used to store the result; (2) prefetch instructions to fetch future data into the cache; (3) load instructions to load the input matrices into registers; (4) FMA instructions to perform the core computation; and (5) store instructions to store the result back to memory.

We associate a cost with each of the above segments and compute their sum as the total cost of the micro-kernel. All components depend on the number of registers used in the hand-written assembly in relation to the number of registers available in the hardware.

Reuse Overhead. A key component of the micro-kernel latency cost is accurately modeling the cost of loading data. Optimal kernels under a perfect cache incur no cost to load data because of out-of-order execution. However, depending on the size of the data loaded (in terms of cache lines), a fraction of the load instructions will miss the cache and incur additional costs. We refer to this cost as reuse overhead. The reuse overhead is computed as the number of cache lines that incur a cache miss multiplied by the effective access latency from the L2 cache.

Let AregA_{\mathrm{reg}} and BregB_{\mathrm{reg}} be the number of registers used to store data from the input matrices AA and BB (derived using MrM_r and NrN_r respectively). Then, then number of registers used to store the result, CregC_{\mathrm{reg}} is Creg=Areg⋅BregC_{\mathrm{reg}} = A_{\mathrm{reg}} \cdot B_{\mathrm{reg}}. Together, the total number of registers used in one loop iteration of the micro-kernel is Rused=Areg+Breg+CregR_{\mathrm{used}} = A_{\mathrm{reg}} + B_{\mathrm{reg}} + C_{\mathrm{reg}}.

Two equations govern the computation of reuse-overhead and, in effect, determine the optimal values of MrM_r and NrN_r. First, a lower bound on the register pressure, defined as the ratio of input and output registers. Second, an upper bound on the load-to-fma latency ratio, defined as the ratio of the load instruction latency to the FMA instruction latency. Formally,

Lemma 2.2. Register pressure equation: The ratio of input and output registers is lower bounded by an architecture-dependent constant α\alpha.

Areg+BregCreg≥α\frac{A_{\mathrm{reg}} + B_{\mathrm{reg}}}{C_{\mathrm{reg}}} \ge\alpha

For a given hardware architecture HH, we calculate the bound α\alpha based on integer solutions to the equation,

Areg+Breg+Creg≤NregA_{reg} + B_{reg} + C_{reg} \le N_{reg}

Lemma 2.3. Load-to-fma latency ratio: The ratio of the load instruction latency to the FMA instruction latency is upper bounded by 1.

(Areg+Breg)⋅τloadCreg⋅τfma≤1\frac{(A_{reg} + B_{reg}) \cdot\tau_{load}}{C_{reg} \cdot\tau_{fma}} \le1

When either of the conditions are violated, the micro-kernel stalls to load the data, incurring a non-zero reuse cost. When register pressure bound is violated, the micro-kernel is using more registers than available and hence leads to register spilling. Similarly, when load-to-fma latency ratio bound is violated, some of the loads are not hidden due to pipelining. The additional loads incur a cost of loading from the higher level cache.

The equations, along with the assumption that NregN_{reg} is small (typically ≤32\le32), effectively reduce the search space for optimal MrM_r and NrN_r (Figure 2 highlights the possible candidates for ‘Zen 5’). Therefore, we are able to enumerate all possibilities and find the optimal one. To further narrow the list, we order them based on the number of bytes loaded from memory in one iteration. The candidate that

Figure 2. Candidate register tile sizes (MrM_r, NrN_r) for AMD ‘Zen 5’ architecture. The candidates are generated by enumerating all possible values of MrM_r and NrN_r that satisfy the register pressure and load-to-fma latency ratio bounds.

loads fewer bytes is preferred since it minimizes the number of total memory accesses.

Macro-kernel cost

The micro-kernel cost described above accounts for all the compute cost of the GEMM operation. In contrast, the macro-kernel cost we describe below accounts for the cost of moving data between the primary memory and the L2 cache. The macro-kernel computes an output matrix of size Mc×NcM_c \times N_c using inputs of size Mc×KcM_c \times K_c and Kc×NcK_c \times N_c, and is where the bulk of data movement happens.

When computing the output, the macro-kernel loop streams through either the AA or BB matrix. The number of cache misses depends on which matrix is streamed. Without loss of generality, we describe the macro-kernel cost assuming BB is streamed. We define the macro-kernel cost LωL_\omega as,

Lω=CapacityMissCost⁡(H,T,SAc+SCc)+β⋅CapacityMissCost⁡(H,T,SBc)(1)L_\omega= \operatorname{CapacityMissCost}(H,T,S_{A_c}+S_{C_c}) + \beta\cdot\operatorname{CapacityMissCost}(H,T,S_{B_c}) \tag*{(1)}

where SAc=Mc∗Kc∗WdS_{A_c}=M_c * K_c * W_d, SBc=Kc∗Nc∗WdS_{B_c}=K_c * N_c * W_d, and SCc=Mc∗Nc∗WdS_{C_c}=M_c * N_c * W_d are the sizes of the input matrices A and B and output matrix C respectively. CapacityMissCost⁡(H,T,S)\operatorname{CapacityMissCost}(H,T,S) denotes the cost of a capacity miss for a working set of size SS and is defined in Algorithm 2. Essentially, if the data set overflows L2, then we compute the cost of moving data from L3 to L2 and similarly if the data overflows L3, we compute the cost of fetching the overflowed data from memory to L3. We compute the capacity cost independently for the B matrix, and the A and C matrices together due to their differences in access patterns. Additionally, when Kc<KK_c < K, we account for the cost of accumulating the partial results by including the cost of loading the result matrix.

The parameter β∈[0,1]\beta\in[0,1] in (1) is an architecture-dependent cost determined by the aggressiveness of the prefetcher. The prefetcher performs well when the data access pattern follows a fixed stride length, as it does when we stream through the B matrix in the macro-tile. Therefore, only a fraction of the B matrix incurs a capacity-miss cost. However, the A and C matrices are not streamed, so we do not expect the prefetcher to perform well.

Packing

GEMM libraries expect that the input matrices are pre-packed into memory a specific layout that depends on the tiling parameters. They expose routines to pack the matrices into the required format before performing the matrix multiplication. Without packing the inputs, the performance of the resulting GEMM operation degrades. The instruction used to load data in the innermost kernel differs from the optimal one, leading to inefficient memory accesses and suboptimal utilization of the cache hierarchy. Since the packing format depends on the tiling parameters, adopting a shape-dependent tiling strategy incurs additional costs.

However, with Waypoint-Tile, we identify a common packing strategy that works across different tiling parameters. Specifically, the packed layout should ensure two invariants: each access loads an entire cache line, and successive access locations follow a fixed stride length. We find that additional packing optimizations do not yield significant performance improvements and only lead to higher packing costs. Therefore, in OPAM, we pack the input matrices into blocks of (Mp×KpM_p \times K_p), where MpM_p and KpK_p are the least common multiples of all possible values of MrM_r and KrK_r, respectively.

Model based GEMM library

To demonstrate that the parameters obtained from Waypoint are realizable and achieve the expected performance, we implement a GEMM library OPAM that uses the parameters derived from Waypoint-Tile for a given GEMM operation and hardware.

OPAM is implemented in C++. In the library, we first use the tiling parameters generated by Waypoint to break down the large GEMM operation and then dispatch the micro-kernel to a JIT based small GEMM library included in OPAM. To break down the large GEMM, we use Parlooper[15], a library that dynamically generates loops with support for OMP based parallelization. Then, in the inner most loop, the JIT based small GEMM library generates the assembly instructions to compute the micro-kernel and caches it for subsequent uses. As an alternative to the JIT based GEMM library, we evaluated Libxsmm[17] and found it lacking the flexibility needed to generate kernels based on analytical-model-derived parameters. Therefore, we use our own JIT based small GEMM library. In Section 4 we report the GEMM performance comparison with state-of-the art GEMM libraries and show that OPAM is competitive.

OPAM supports two methods for finding the best tiling parameters: exhaustive search and fast heuristic-driven search. During exhaustive search, we evaluate all possible tiling parameters after pruning the search space based on insights from Waypoint-Tile. Specifically, we search only optimal

MrM_r and NrN_r values and bound the McM_c, NcN_c, and KcK_c values based on the cache sizes. However, for latency-sensitive applications such as LLM inference, the fast heuristic search offers a quick alternative.

The fast-heuristic search is developed using recent advances in algorithmic evolution[8, 9, 27]. We use OpenEvolve[28], an open-source implementation of AlphaEvolve[27], to discover the heuristics. Our evolution process is focused on obtaining fast heuristics for a curated set of GEMM operations (or shapes) that modern LLM inference workloads invoke. However, the methodology can be used to discover heuristics that are tailored for any set of GEMM operations that the workload demands. The fast-heuristic generation is a one-time cost and the resulting heuristics can be used for all future GEMM operations.

Figure 3 demonstrates the flow to obtain the heuristic search algorithm. OpenEvolve starts with a set of seed programs as candidates for heuristics search. Our seeds are derived using insights from the tiling parameters generated by Waypoint-Tile. Then, OpenEvolve runs for many iterations, generating candidate heuristics in a genetic-mutation based algorithm. In each iteration we check the correctness of the tiling parameters and use Waypoint-Tile is used to score the candidates. A candidate is good if the estimate of the selected tile parameter is not far from the best known. After running for 100 iterations, OpenEvolve generates a fast-heuristic search algorithm that can be used to very quickly select near-optimal tiling parameters for a given set of GEMM operations and hardware. We defer the details of the OpenEvolve configuration to Appendix § 8.

High-level workflow for evolving a Waypoint CPU split-factor heuristic

Figure 3. High-level workflow for evolving a Waypoint CPU split-factor heuristic. Seed heuristics and LLM-generated mutations are evaluated against pinned exhaustive-search optima; the resulting metrics drive selection of the best heuristic.

CategoryCount
Small GEMM (<512<512)4
Medium Square (512512–40964096)9
Large GEMM (>4096>4096)8
Tall skinny (M>NM>N)4
Fat Short (M<NM<N)2
Odd Shapes4
LLM Shapes20

Table 1. Evaluated GEMM shapes

The resulting fast-heuristic search is 18851×18851\times faster than the exhaustive search and discovers tiling parameters whose estimated latency is within 1.94% (maximum) of the best tiling parameters derived by Waypoint[1]. In our evaluation we show that the fast-heuristic search accelerates LLM performance on both current and future hardware. Our results include the cost of the fast heuristic search.

Evaluation

We evaluate the accuracy of our analytical model and the performance of OPAM relative to three existing state-of-the-art libraries, AOCLTM-BLAS [3], AOCLTM-DLP [2], and SFC [13]. AOCL-BLAS and AOCL-DLP are state-of-the-art tiling-based GEMM libraries that are optimized for AMD CPUs and support low-precision GEMM kernels used in machine learning workloads. While AOCL-BLAS uses hand-written micro-kernels, AOCL-DLP contains a JIT engine that dynamically generates the micro-kernel. In contrast, SFC is applicable to all x86 processors and implements a novel traversal mechanism (using space-filling curves) to minimize data access costs.

Our evaluation is focused on the AMD Zen architecture. Specifically, we evaluate on ‘Zen 5’ (Turin) [11] and ‘Zen 6’ (Venice). Across both architectures, all our evaluations are performed for 3 different data types, FP32, BF16, and INT8. We evaluate the performance of the OPAM for a set of 51 unique GEMM shapes (summarized in Table 5) (306 comparisons in total) that are commonly used in modern LLM inference workloads. A detailed list of the shapes used to evaluate can be found in Appendix § 9.

Table 5. GEMM evaluation shapes. MM, NN, and KK are the matrix dimensions, and TT is the number of threads.

MMNNKKTTMMNNKKTT
646464140966440961
642048641409612840961
96969614096409640961
12832288011281433640964
12812812811282867240964
12828802880112812825640964
1282880409612048204820484
1282880576014096409640964
128409612818192819281924
1284096409611281433640968
12840961433611282867240968
12851202880112812825640968
1285760288012048204820488
1286144409614096409640968
12814336409618192819281928
128286724096112814336409616
12812825640961128128256409616
256256256120482048204816
288192384140964096409616
512512512181928192819216
768512256116384163841638416
9927681024181928192819232
102410241024116384163841638432
2048642048116384163841638464
204812820481163841638416384128
2048204820481

Table 5.

With our evaluation we aim to answer the following research questions:

RQ1 Is the model accurate for different data types and architectures?

RQ2 How well does OPAM compare to state-of-the-art implementations?

RQ3 Does using the analytical model based OPAM improve the performance of end-to-end LLM inference?

The Waypoint-Strict and Waypoint-Tile models are evaluated against the Roofline model and the actual performance of GEMM operations implemented in the three libraries. Waypoint-Strict is tighter than Roofline and predicts actual performance to within 9.6%. Waypoint-Tile is accurate both in ranking different tiling options and in estimating the performance of the best tiling option compared with the libraries (geometric mean of 1.2%).

OPAM achieves performance comparable to that of the three libraries across all configurations. When including packing costs, OPAM beats AOCL-BLAS by 16.7%, AOCL-DLP by 13.6%, and SFC by 21.0%. Further, when comparing pure GEMM computation, OPAM is 10.8% faster than AOCL-BLAS and achieves performance similar to AOCL-DLP (0.85% slower) and SFC (0.8% faster).

Finally, we evaluate end-to-end LLM inference performance using PACE™ [4], a vLLM-compatible framework with optimized inference kernels for AMD CPUs. We embed the fast-heuristic search in PACE and evaluate it against a baseline implementation that does not use Waypoint. We find that the shape-adaptive tiling strategy of Waypoint yields average time-to-first-token (TTFT) speedups of 1.36× to 1.98× across different batch sizes, input lengths, models, and hardware architectures.

For the remainder of the section, we first describe the experimental setup and then elaborate on the results for each of the research questions.

Experimental Setup

The models are compared against two hardware architectures. One, AMD ‘Zen 5’ (Turin) EPYC 9755 128-Core Processor with 512MB of L3 cache running at a fixed frequency of 2.7GHz. The other, AMD ‘Zen 6’ (Venice) EPYC 9996 256-Core Processor with 1GB of L3 cache running at a fixed frequency of 2.5GHz. We were provided advanced access to ‘Zen 6’ processor by AMD. While production systems are run with variable frequency, we fix the frequency to ensure consistent performance measurements and to isolate the performance improvements of our approach. We present comparison numbers to AOCL-BLAS and AOCL-DLP for all 3 data types (Int8, BFloat16, and FP32), and SFC for only 2 data types (BFloat16 and FP32) since SFC does not support Int8. The OPAM is implemented in C++ and compiled using GCC 13.3.0. All comparisons are done by measuring cycles using the rdtsc instruction. To mitigate the effects of randomness when measuring the performance of GEMM libraries, for each shape, we run 10 warm-up trials and 100 measurement trials and report the best latency numbers. All numbers are reported using geometric mean.

DatatypeThreadsnMedianMeanMax
Int81581.001x1.005x1.031x
Int82-8241.000x1.001x1.011x
Int8>8201.000x1.001x1.002x
BFloat161581.001x1.004x1.031x
BFloat162-8241.000x1.002x1.013x
BFloat16>8201.001x1.001x1.005x
Float321581.001x1.004x1.031x
Float322-8241.001x1.003x1.014x
Float32>8201.002x1.002x1.006x

Table 2 (PDF p. 9). Roofline vs Waypoint-Strict comparison for different data types across architectures. We report the median, mean, and max ratios of Waypoint-Strict to Roofline estimates across different shapes. A value of ‘1.000x‘ means Waypoint-Strict and Roofline estimate match.

For measuring end-to-end LLM inference times, we integrate OPAM into AMD-PACE[4]. Our measurement compares against a baseline version that uses TPP [14] to dispatch GEMM calls. Our inference runs on 128 threads.

RQ1: Model accuracy

Table 2 shows the comparison of Waypoint-Strict against the Roofline model across different data types and architectures. As shown, Waypoint-Strict is tighter than the Roofline model. Specifically when the data needed for computation is large, Waypoint-Strict deviates from the Roofline (up to 1.031x) accounting for the storage, and multi-threaded execution costs.

Algorithm 2 Macro-kernel cost LωL_\omega
Require: Working-set size SS, L2 size SL2S_{L2}, L3 size SL3S_{L3}, thread count TT for a given hardware configuration HH
1: procedure CapacityMissCost(H,T,SH,T,S)
2: if S≤SL2S \le S_{L2} then
3: return 0
4: end if
5: SL3-resident←min⁡(S,SL3)−SL2S_{L3\text{-}resident} \leftarrow\min(S,S_{L3}) - S_{L2}
6: L←MoveFromL3Latency⁡(H,SL3-resident)L \leftarrow\operatorname{MoveFromL3Latency}(H,S_{L3\text{-}resident})
7: if S>SL3S > S_{L3} then
8: L←L+FetchFromMemLatency⁡(H,S−SL3,T)L \leftarrow L+\operatorname{FetchFromMemLatency}(H,S-S_{L3},T)
9: end if
10: return LL
11: end procedure

Table 2.

Waypoint-Tile predicts the performance of a given tiling solution more accurately than Waypoint-Strict but does not guarantee a tight upper bound. Figure 4 compares the predictions of Waypoint-Tile and Waypoint-Strict with the measured performance of the three implementations. As shown, Waypoint-Strict serves as a tight upper bound on GEMM performance. The depicted AOCL-BLAS performance measurements form a bimodal distribution, with the two modes corresponding to the different architectures (‘Zen 5’ and ‘Zen 6’).

Figure 4. Waypoint-Tile vs Waypoint-Strict vs Implementations (AOCL-BLAS, SFC, and AOCL-DLP). We report the ratios and distribution for all the shapes.

Further, the Waypoint-Tile is able to accurately rank different tiling options for a given GEMM shape. To ensure the correctness of the ranking, we evaluate the 1st, 5th, and 10th tiling options for each GEMM shape and compare the predicted performance against the measured performance. We find that the Waypoint-Tile is able to accurately rank the top tiling option for 88.7% (within 5% of the peak performance) of the evaluated GEMM shapes and strictly the best in 62.7% of the cases.

Future hardware predictions. A key contribution of Waypoint is its ability to predict the performance of future proposed hardware.

ACE throughputBFloat16Int8
17.21x7.45x
212.84x13.48x
421.47x23.00x

Table 3. Predicted geometric-mean GEMM speedup from the proposed AI Compute Extensions (ACE) across 44 shapes per datatype vs ‘Zen 5’ hardware. ACE throughput is effective number of Tile operations that can be issued per cycle.

To demonstrate this, we evaluate the performance of the GEMM operation on a hypothetical future hardware that implements the proposed AI compute instructions [33] where one Tile operation computes a 16 × 16 × 4 (for Int8) and 16 × 16 × 2 (for BFloat16). Table 3 shows the predicted performance gap of the GEMM averaged across all shapes for different throughput configurations of the AI compute instructions relative to ‘Zen 5’ hardware. In ‘Zen 5’, the VNNI instruction can be issued at the rate of 2/cycle and the tile op does the work equivalent to 16 VNNI instruction. As shown in the table, the model tempers the expected performance improvements of 8× (1 tile op/cycle),16×, and 32×, accounting for the data movement costs when compute is accelerated. The result shows that adding many compute units will not automatically scale the performance linearly because the kernels will become memory bound.

RQ2: OPAM performance comparison

Figure 5 compares the performance of the OPAM relative to three state-of-the-art implementations and the Waypoint-Tile estimates for the same set of GEMM shapes. We observe that the OPAM closely follows the performance predicted by the Waypoint-Tile, demonstrating the accuracy and practical utility of our approach. On ‘Zen 5’, OPAM meets the performance of existing, highly optimized GEMM libraries. However on ‘Zen 6’ the libraries are yet to be tuned (especially for the Int 8 datatype) as the hardware is not readily available, but OPAM demonstrates a significant performance advantage over the existing implementations.

Relative performance of AOCL-BLAS, SFC, AOCL-DLP, and the Waypoint-Tile vs OPAM, separated by hardware architecture.

Figure 5. Relative performance of AOCL-BLAS, SFC, AOCL-DLP, and the Waypoint-Tile vs OPAM, separated by hardware architecture.

Packing cost differences The different implementations also differ in their packing strategies. As mentioned in 2.3, the implementations extract peak performance by assuming that the data is pre-packed into contiguous memory regions in a specific format. For example, SFC requires that the data is laid out in the sequence of the space filling curve. This additional transformation increases the packing cost compared to more straightforward packing strategies used in AOCL-BLAS, AOCL-DLP, and OPAM.

When comparing GEMM performance, SFC often achieves higher throughput due to its optimized data layout and tiling strategies. However, this comes at the cost of increased packing overhead. Comparing the packing costs, we find that OPAM achieves a 1.40× speedup over AOCL-DLP, 1.29× over AOCL-BLAS, and 2.44× over SFC. We include a detailed table in Appendix § 9. The higher packing cost can offset the performance gains in scenarios where the packing overhead is significant relative to the time taken to compute the result.

Discussion Including both the packing cost and GEMM latency, we observe that OPAM is overall 1.168× faster than AOCL-BLAS, 1.210× faster than SFC, and 1.136× faster than AOCL-DLP. Conceptually, the gains of OPAM over AOCL-BLAS and AOCL-DLP are primarily due to its shape-adaptive tiling strategies and comparable packing cost. In contrast, the gains over SFC are primarily driven by significantly lower packing cost and comparable GEMM performance matching the data reuse achieved by the optimized SFC algorithm.

RQ3: End-to-end LLM inference performance

We evaluate the impact of Waypoint on end-to-end inference performance of Large Language models using, AMD-PACE [4]. Figure 6 shows the average end-to-end inference speedup on prefill heavy inference workloads that primarily rely on the performance of GEMM calls. Other workloads that involve more GEMV operations retain existing performance levels. As shown, Waypoint consistently improves inference performance across different hardware and model configurations.

Figure 6. End-to-end inference speedup of Waypoint on prefill heavy LLM workloads across different hardware and models. Bars show the geometric mean; whiskers show the full range across batch sizes and input lengths.

The graph depicts speedups across batch sizes of 8, 16, 32, 64, and 128 for input lengths of 1024 and 2048. With higher batch sizes, the cost of inference heavily skews towards GEMM operation latency. Therefore, by integrating WAYPOINT, we see the highest gains in higher batch sizes (e.g. 3.6× for batch size 128 on ‘Zen 5’ with Qwen 3 8B and 9.15× for batch size 128 on ‘Zen 6’ with Qwen 3 8B). The gains are attributed primarily to improvements in GEMM computation times of the odd shapes encountered in LLM inference, driven by the shape-adaptive tiling strategy of WAYPOINT. The graph also shows the ability of WAYPOINT to accelerate inference on new hardware. The range of speed up is larger in ‘Zen 6’ compared to ‘Zen 5’.

Extending to other architectures

While our focus in the evaluation is on AMD x86 processor family, the principles used in both Waypoint-Strict and Waypoint-Tile are general and can be easily extended to other architectures. The estimates of performance depend primarily on a layered memory hierarchy and a pipelined vector/matrix processing unit.

The model immediately translates to Intel x86 processors given their similarity in ISA and hardware architecture to AMD x86 processors. Further, the model can be adopted to ARM processors. ARM processors also feature a layered memory hierarchy and pipelined vector/matrix processing units, although the specific details of the cache sizes, memory bandwidth, and vector instruction sets differ. Specifically, the variable vector length in ARM’s Scalable Vector Instruction and Scalable Matrix Extension fit well with the parametric nature of Waypoint-Strict and Waypoint-Tile. The length and number of lanes of the registers are parametric in the model and can be configured based on the hardware architecture.

Related work

There has been extensive work on modeling and optimizing the performance of General Matrix Multiplication (GEMM) operations on various hardware architectures.

GotoBLAS [16] introduced a layered approach to implement GEMM operations in the BLAS standard library [1]. They identified the optimization that most libraries [2, 3, 30] today adopt. Namely, that breaking down the large GEMM operation into smaller blocks (tiles) significantly improves cache utilization and overall performance. Subsequent works [6, 7, 10] developed empirical methods to identify the optimal tiling parameters for a given hardware architecture and study the effects of different tiling choices on performance [5].

However, to overcome the time-consuming and resource intensive process of empirically identifying the best tiling parameters, analytical model approaches [24, 34, 35] have been proposed. These models [26] adapt to different hardware and to specific classes of shapes [31]. WAYPOINT extends prior works to identify optimal tiling parameters by being parametric and general not just in the hardware architecture but also in the specific input matrix shape.

The performance of tile-based GEMM implementations are sensitive to the data-layout of the input matrices in memory. To alleviate this, recent works have borrowed ideas from communication-avoiding algorithms [12, 13] to reduce data movement and improve cache utilization. They propose and show that by carefully organizing the input matrices in the order of a Space Filling Curve reduces cache misses and helps extract peak performance. Waypoint models are general enough to accurately predict the performance of such alternative implementations while at the same time, matching their performance with OPAM.

While the traditional Roofline model [32] has been widely adopted to predict peak performance on proposed hardware designs, it fails to provide realistic estimates. As a result, the software never ceases to be optimized on existing hardware and hardware designers are unable to predict the realistic achievable performance on proposed hardware. Execution-Cache-Memory (ECM) [18, 19], instruction-level models [22], and GPU specific models [25] have extended the Roofline model to capture different architectural effects and provide more realistic estimates. However, these models are either heavily tailored to a specific architecture, or require execution traces to be collected from the target hardware. Waypoint furthers the research by being both accurate and parametric in the hardware architecture, allowing hardware designers to get reliable estimates of the realistic performance achievable.

Our work is closely motivated by a similar effort focused on GPUs [29] which predicts performance of GEMM operations on GPUs by accounting for cache-miss rates, memory access overheads and other architectural effects. Our work Waypoint, generalizes the approach while demonstrating its applicability to CPUs.

Discussion and Conclusion

Under multi-threaded GEMM operations, Waypoint makes simplistic assumptions on the strategy to split work among different threads such as equal distribution of tiles or static scheduling, which may not always reflect the optimal parallel execution strategy. We observe that for certain input matrix sizes, using lower than the prescribed number of threads can yield better performance, highlighting the need for more sophisticated thread management strategies in future work.

We present Waypoint, a two part analytical model which first provides a tighter than Roofline estimate for GEMM performance and second, helps select the optimal tiling parameters to realize the estimates. The model derives several insights into estimating, and narrowing the search for optimal tiling parameters, ultimately enabling high-performance GEMM across diverse hardware architectures. We implement a GEMM library OPAM that uses the analytical model of Waypoint to guide its tiling decisions, and show that it achieves performance close to the theoretical estimates. OPAM matches the performance of state-of-the-art GEMM libraries on existing hardware while showing considerable gains on future hardware architectures. Finally, we show that using OPAM and Waypoint speeds up end-to-end CPU inference tasks significantly, demonstrating the practical impact of our approach.

References

Appendix A: Heuristic Search Details

We run OpenEvolve to discover fast-search heuristics that offer a fast alternative to the exhaustive search of WAYPOINT. To discover the heuristics, we first curate a set of GEMM operations (or shapes) that modern LLM inference workloads invoke. Then, we build a baseline of best tiling parameters for each shape using WAYPOINT.

Starting with a predefined set of seed programs that contain initial heuristics, OpenEvolve runs many iterations, generating candidate heuristics that are evaluated against the baseline. Below we elaborate on the details of the seed programs and the evaluation process. AVX512 FMA/VNNI instruction is used compute operations. We do not explore the possibility of a mixed instruction use for a specific workload.

Strided Data access: WAYPOINT assumes that the data needed for compute is loaded into the registers in strides of contiguous memory locations. WAYPOINT accounts for the strided access by assuming the lowest cost for loading data into registers. For GEMM workloads, the assumption is valid since data is pre-packed to align accesses with cache lines and stride lengths.

Cache memory model: WAYPOINT assumes that the different level of caches provide different access latencies and that lower levels of caches have faster access times. We do not make any assumptions on the inclusivity, write-back policies, or replacement strategies of the caches. The model only considers the access latency differences between cache levels. A more complex model of the caches will help in determining the access latencies better.

Partial bandwidth when loading data: For multi-core (thread) GEMM operations, WAYPOINT assumes that the memory bandwidth is shared across all threads. Hence, each thread only receives a fraction of the total bandwidth available. The fractional cost is accounted for when computing the data accesses from memory.

Peak store throughput: We assume that stores occur at the peak throughput of the memory subsystem. Since the result-matrix locations targeted by store instructions typically reside in caches rather than main memory, the store operations are not expected to be bottlenecked by main memory and can achieve peak throughput.

Seed programs

We generate 6 seed programs each containing independent set of heuristics that target a specific class of the shapes. The goal with the seeds is to provide a diverse set of possible heuristics that could be used to arrive at the final program and allow OpenEvolve to mutate, combine, and evolve them over many iterations to discover effective fast-search heuristics. Each seed program corresponds to a single island of evolution in OpenEvolve. The seeds are,

  1. Tiling based primarily on data type and ratio of matrix dimensions.

  2. Uses L1/L2 cache sizes to bound the tiling options.

  3. Targets optimal multi-threading splits based on the shape of the GEMM operation.

  4. Use arithmetic intensity to guide the inner most tiling decisions.

  5. Target specifically the AI Compute Instructions / AMX instructions.

  6. Initially baseline or the previous best program.

Fast heuristic search results

We plot below the average difference in expected latency between the fast heuristic search algorithm and the exhaustive search algorithm.

Appendix B: GEMM evaluation shapes

Evaluation shapes

Table 5 lists the 51 unique GEMM shapes used in our evaluation. Each shape is evaluated on both hardware configurations and for all three data types described in § 4.

Packing cost

Table 6 contains the packing cost speedup of OPAM. Values are geometric-mean ratios of implementation packing cycles to OPAM packing cycles for all the shapes.

Model Assumptions

The estimates derived using Waypoint (both the Simple and Waypoint-Tiles) rely on certain assumptions about the behavior of the underlying hardware. We list below the assumptions along with the reasoning.

Fixed frequency workloads: Waypoint estimates the performance of a GEMM operation assuming that the CPU frequency is fixed. We calculate the number of cycles required to access data from memory using the frequency of the machine. Under a variable frequency scenario, one can extend the model by incorporating the dynamic changes in frequency to adjust the cycle estimates accordingly.

Best instruction for compute: Due to the highly optimized nature of GEMM kernels, Waypoint assumes that the best instruction i.e. the one with the highest throughput and lowest latency, is used for the compute operations. For example, in x86-ISA based CPU, Waypoint assumes that the AVX512 FMA/VNNI instruction is used compute operations. We do not explore the possibility of a mixed instruction use for a specific workload.

Strided Data access: WAYPOINT assumes that the data needed for compute is loaded into the registers in strides of contiguous memory locations. WAYPOINT accounts for the strided access by assuming the lowest cost for loading data into registers. For GEMM workloads, the assumption is valid since data is pre-packed to align accesses with cache lines and stride lengths.

Cache memory model: WAYPOINT assumes that the different level of caches provide different access latencies and that lower levels of caches have faster access times. We do not make any assumptions on the inclusivity, write-back policies, or replacement strategies of the caches. The model only considers the access latency differences between cache levels. A more complex model of the caches will help in determining the access latencies better.

Partial bandwidth when loading data: For multi-core (thread) GEMM operations, WAYPOINT assumes that the memory bandwidth is shared across all threads. Hence, each thread only receives a fraction of the total bandwidth available. The fractional cost is accounted for when computing the data accesses from memory.

Peak store throughput: We assume that stores occur at the peak throughput of the memory subsystem. Since the result-matrix locations targeted by store instructions typically reside in caches rather than main memory, the store operations are not expected to be bottlenecked by main memory and can achieve peak throughput.

Table 4. Average difference in expected latency between the fast heuristic search algorithm and the exhaustive search algorithm across different shape categories and architectures.

Shape categoryZ5 FloatZ5 BF16Z5 Int8Z6 FloatZ6 BF16Z6 Int8
Small Square0.002%0.000%0.443%0.010%0.018%0.000%
Medium Square0.144%0.060%0.059%0.242%0.251%0.426%
Large Square0.089%0.059%0.055%0.234%0.295%0.514%
Tall Skinny0.692%0.145%0.473%0.111%0.093%0.006%
Fat short0.110%0.121%0.127%0.106%0.114%0.209%
Odd Shapes0.698%0.651%0.838%0.710%0.698%1.590%
LLM Shapes0.250%0.200%0.235%0.081%0.074%0.292%
Overall0.247%0.157%0.253%0.200%0.211%0.427%

Table 4.

Hardware / ImplType12–8> 8
‘Zen 5’
AOCL-BLASINT82.02×2.02\times3.01×3.01\times10.34×10.34\times
AOCL-BLASBFloat160.40×0.40\times1.37×1.37\times4.40×4.40\times
AOCL-BLASFloat321.11×1.11\times1.78×1.78\times5.05×5.05\times
AOCL-DLPINT82.11×2.11\times3.75×3.75\times10.23×10.23\times
AOCL-DLPBFloat160.44×0.44\times1.42×1.42\times4.48×4.48\times
AOCL-DLPFloat321.17×1.17\times1.89×1.89\times5.05×5.05\times
SFCBFloat162.05×2.05\times1.64×1.64\times1.73×1.73\times
SFCFloat323.92×3.92\times2.26×2.26\times3.66×3.66\times
‘Zen 6’
AOCL-BLASINT81.62×1.62\times1.51×1.51\times1.94×1.94\times
AOCL-BLASBFloat160.50×0.50\times0.65×0.65\times0.97×0.97\times
AOCL-BLASFloat321.01×1.01\times0.79×0.79\times1.52×1.52\times
AOCL-DLPINT81.60×1.60\times2.93×2.93\times2.35×2.35\times
AOCL-DLPBFloat160.55×0.55\times0.61×0.61\times0.98×0.98\times
AOCL-DLPFloat321.13×1.13\times0.86×0.86\times1.57×1.57\times
SFCBFloat162.45×2.45\times1.15×1.15\times1.36×1.36\times
SFCFloat323.49×3.49\times1.89×1.89\times3.55×3.55\times

Table 6. Packing cost relative to OPAM. Values are geometric-mean ratios of implementation packing cycles to OPAM packing cycles for different thread counts.

References

  1. [1]2002. An updated set of basic linear algebra subprograms (BLAS). ACM Trans. Math. Softw. 28, 2 (June 2002), 135–151. https://doi.org/10.1145/567806.567807
  2. [2]2026. amd/aocl-dlp. https://github.com/amd/aocl-dlp original-date: 2025-09-02T10:58:34Z.
  3. [3]Advanced Micro Devices, Inc. 2025. AMD AOCL-BLAS: BLAS-like Library Instantiation Software Framework. https://github.com/amd/blis. Accessed: 2026-07-06.
  4. [4]Advanced Micro Devices, Inc. 2026, 1.2.0. AMD PACE: AMD Platform Aware Compute Engine. https://github.com/amd/amd-pace
  5. [5]Guillermo Aleajos, Adrián Castelló, Pedro Alonso-Jordá, Francisco D. Igual, Héctor Martínez, and Enrique S. Quintana-Ortí. 2024. Algorithm 1039: Automatic Generators for a Family of Matrix Multiplication Routines with Apache TVM. ACM Trans. Math. Softw. 50, 1, Article 6 (March 2024), 34 pages. https://doi.org/10.1145/3638532
  6. [6]Jason Ansel, Shoaib Kamil, Kalyan Veeramacheni, Jonathan Ragan-Kelley, Jeffrey Bosboom, Una-May O’Reilly, and Saman Amarasinghe. 2014. OpenTuner: An Extensible Framework for Program Autotuning. In Proceedings of the 23rd International Conference on Parallel Architectures and Compilation (PACT ’14). Association for Computing Machinery, 303–316. https://doi.org/10.1145/2628071.2628092
  7. [7]Jeff Bilmes, Krste Asanovic, Chee-Whye Chin, and Jim Demmel. 1997. Optimizing matrix multiply using PHiPAC: a portable, high-performance, ANSI C coding methodology. In Proceedings of the 11th International Conference on Supercomputing (Vienna, Austria) (ICS ’97). Association for Computing Machinery, New York, NY, USA, 340–347. https://doi.org/10.1145/263580.263662
  8. [8]Audrey Cheng, Shu Liu, Melissa Pan, Zhifei Li, Shubham Agarwal, Mert Cemri, Bowen Wang, Alexander Krentzel, Tian Xia, Jongseok Park, Shuo Yang, Jeff Chen, Lakshya Agrawal, Ashwin Naren, Shulu Li, Ruiying Ma, Aditya Desai, Jiarong Xing, Koushik Sen, Matei Zaharia, and Ion Stoica. 2025. Let the Barbarians In: How AI Can Accelerate Systems Performance Research. arXiv:2512.14806 [cs.SE] https://arxiv.org/abs/2512.14806
  9. [9]Audrey Cheng, Shu Liu, Melissa Pan, Zhifei Li, Bowen Wang, Alex Krentzel, Tian Xia, Mert Cemri, Jongseok Park, Shuo Yang, Jeff Chen, Lakshya Agrawal, Aditya Desai, Jiarong Xing, Koushik Sen, Matei Zaharia, and Ion Stoica. 2025. Barbarians at the Gate: How AI is Upending Systems Research. arXiv:2510.06189 [cs.AI] https://arxiv.org/abs/2510.06189
  10. [10]R Clint Whaley, Antoine Petitet, and Jack J Dongarra. 2001. Automated empirical optimizations of software and the ATLAS project. Parallel Comput. 27, 1-2 (Jan. 2001), 3–35.
  11. [11]Brad Cohen, Mahesh Subramony, and Mike Clark. 2024. Next Generation "Zen 5" Core. In 36th IEEE Hot Chips Symposium, HCS 2024, Stanford, CA, USA, August 25–27, 2024. IEEE, 1–27. https://doi.org/10.1109/HCS61935.2024.10665102
  12. [12]James Demmel, David Elahiu, Armando Fox, Shoaib Kamil, Benjamin Lipshitz, Oded Schwartz, and Omer Spillinger. 2013. Communication-Optimal Parallel Recursive Rectangular Matrix Multiplication. In 2013 IEEE 27th International Symposium on Parallel and Distributed Processing. IEEE, 261–272. https://doi.org/10.1109/IPDPS.2013.80
  13. [13]Evangelos Georgans, Alexander Heinecke, and Pradeep Dubey. 2026. Space Filling Curves is All You Need: Communication-Avoiding Matrix Multiplication Made Simple. arXiv:2601.16294 [cs.DC] https://arxiv.org/abs/2601.16294
  14. [14]Evangelos Georgantas, Dhiraj Kalamkar, Sasikanth Avancha, Men-achem Adelman, Cristina Andersson, Alexander Breuer, Jeremy Brues-tle, Narendra Chaudhary, Abhisek Kundu, Denise Kutnick, Frank Laub, Vasimuddin Md, Sanchit Misra, Ramanarayan Mohanty, Hans Pabst, Barukh Ziv, and Alexander Heinecke. 2021. Tensor processing primitives: a programming abstraction for efficiency and portability in deep learning workloads. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis (St. Louis, Missouri) (SC ’21). Association for Computing Machinery, New York, NY, USA, Article 14, 14 pages. https://doi.org/10.1145/3458817.3476206
  15. [15]Evangelos Georganas, Dhiraj Kalamkar, Kirill Voronin, Abhisek Kundu, Antonio Noack, Hans Pabst, Alexander Breuer, and Alexander Heinecke. 2024. Harnessing Deep Learning and HPC Kernels via High-Level Loop and Tensor Abstractions on CPU Architectures. In 2024 IEEE International Parallel and Distributed Processing Symposium (IPDPS). IEEE, 950–963. https://doi.org/10.1109/IPDPS57955.2024.00089
  16. [16]Kazushige Goto and Robert A. van de Geijn. 2008. Anatomy of High-Performance Matrix Multiplication. ACM Trans. Math. Software 34, 3 (May 2008), 1–25. https://doi.org/10.1145/1356052.1356053
  17. [17]Alexander Heinecke, Greg Henry, Maxwell Hutchinson, and Hans Pabst. 2016. LIBXSMM: accelerating small matrix multiplications by runtime code generation. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis (Salt Lake City, Utah) (SC ’16). IEEE Press, Article 84, 11 pages. https://doi.org/10.1109/SC.2016.83
  18. [18]Johannes Hofmann, Dietmar Fey, Jan Eitzinger, Georg Hager, and Gerhard Wellein. 2016. Analysis of Intel’s Haswell Microarchitecture Using the ECM Model and Microbenchmarks. In Architecture of Computing Systems – ARCS 2016, Frank Hang, João M. P. Cardoso, Thilo Pionteck, Dietmar Fey, Wolfgang Schröder-Preikschat, and Jürgen Teich (Eds.). Springer International Publishing, Cham, 210–222.
  19. [19]Aleksandar Ilic, Frederico Pratas, and Leonel Sousa. 2014. Cache-aware Roofline model: Upgrading the loft. IEEE Computer Architecture Letters 13, 1 (2014), 21–24. https://doi.org/10.1109/L-CA.2013.6
  20. [20]Intel. 2026. Introducing Intel® Advanced Performance Extensions (Intel® APX) – intel.com. https://www.intel.com/content/www/us/en/developer/articles/technical/advanced-performance-extensions-apx.html [Accessed 10-09-2026].
  21. [21]Intel Corporation. 2022. Accelerate Artificial Intelligence (AI) Workloads with Intel Advanced Matrix Extensions (Intel AMX). Solution Brief. Intel Corporation. https://www.intel.com/content/dam/www/central-libraries/us/en/documents/2022-12/accelerate-ai-with-amx-sb.pdf
  22. [22]Jan Laukemann, Julian Hammer, Johannes Hofmann, Georg Hager, and Gerhard Wellein. 2018. Automated Instruction Stream Throughput Prediction for Intel and AMD Microarchitectures. In 2018 IEEE/ACM Performance Modeling, Benchmarking and Simulation of High Performance Computer Systems (PMBS). 121–131. https://doi.org/10.1109/PMBS.2018.8641578
  23. [23]Chendi Li, Haipeng Jia, Hang Cao, Jianyu Yao, Boqian Shi, Chunyang Xiang, Jinbo Sun, Pengqi Lu, and Yunquan Zhang. 2021. AutoTSMM: An Auto-tuning Framework for Building High-Performance Tall-and-Skinny Matrix-Matrix Multiplication on CPUs. In 2021 IEEE Intl Conf on Parallel and Distributed Processing with Applications, Big Data and Cloud Computing, Sustainable Computing and Communications, Social Computing and Networking (ISPA/BDCloud/SocialCom/SustainCom). 159–166. https://doi.org/10.1109/ISPA-BDCloud-SocialCom-SustainCom52081.2021.00034
  24. [24]Tze Meng Low, Francisco D. Igual, Tyler M. Smith, and Enrique S. Quintana-Orti. 2016. Analytical Modeling Is Enough for High-Performance BLIS. ACM Trans. Math. Softw. 43, 2, Article 12 (Aug. 2016), 18 pages. https://doi.org/10.1145/2925987
  25. [25]Sangkyu Lym, Donghyun Lee, Mike O’Connor, Niladrish Chatterjee, and Mattan Erez. 2019. DeLTA: GPU Performance Model for Deep Learning Applications with In-Depth Memory System Traffic Analysis. In 2019 IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS). 293–303. https://doi.org/10.1109/ISPASS.2019.000041
  26. [26]Héctor Martínez, Sandra Catalán, Francisco D Igual, José R Herrero, Rafael Rodríguez-Sánchez, and Enrique S Quintana-Ortí. 2025. Cache-aware optimization of matrix multiplication and matrix factorizations on multicore processors. Cluster Comput. 28, 12 (Nov. 2025).DOI
  27. [27]Alexander Novikov, Ngân Vũ, Marin Eisenberger, Emilien Dupont, Po-Sen Huang, Adam Zsolt Wagner, Sergey Shirobokov, Borislav Kozlovskii, Francisco J. R. Ruiz, Abbas Mehrabian, M. Pawan Kumar, Abigail See, Swarat Chaudhuri, George Holland, Alex Davies, Sebastian Nowozin, Pushmeet Kohli, and Matej Balog. 2025. AlphaEvolve: A coding agent for scientific and algorithmic discovery. arXiv:2506.13131 [cs.AI] https://arxiv.org/abs/2506.13131
  28. [28]Asankhaya Sharma. 2025. OpenEvolve: an open-source evolutionary coding agent. https://github.com/algorithmicsuperintelligence/openevolve
  29. [29]Ryan Swann, Muhammad Osama, Xiaohu Guo, Bryant Nelson, Lixun Zhang, Alex Brown, Yen Ong, Ali Yazdani, Sean Siddens, Ganesh Dasika, and Alex Underwood. 2025. tritonBLAS: Triton-based Analytical Approach for GEMM Kernel Parameter Selection. arXiv:2512.04226 [cs.DC] https://arxiv.org/abs/2512.04226
  30. [30]Field G. Van Zee and Robert A. van de Geijn. 2015. BLIS: A Framework for Rapidly Instantiating BLAS Functionality. ACM Trans. Math. Software 41, 3 (June 2015), 14:1–14:33. https://doi.org/10.1145/2764454
  31. [31]Cunyang Wei, Haipeng Jia, Yunquan Zhang, Jianyu Yao, Chendi Li, and Wenjuan Cao. 2024. IrGEMM: An Input-Aware Tuning Framework for Irregular GEMM on ARM and X86 CPUs. IEEE Transactions on Parallel and Distributed Systems 35, 9 (2024), 1672–1689. https://doi.org/10.1109/TPDS.2024.3432579
  32. [32]Samuel Williams, Andrew Waterman, and David A. Patterson. 2009. Roofline: an insightful visual performance model for multicore architectures. Commun. ACM 52, 4 (2009), 65–76. https://doi.org/10.1145/1498765.1498785
  33. [33]x86 Ecosystem Advisory Group. 2026, 11.6.2. AI Compute Extensions (ACE) Specification. Technical Report. x86 Ecosystem Advisory Group. https://x86ecosystem.org/resource/ai-compute-extensions-ace-specification Specification Release.
  34. [34]Kamen Yotov, Xiaoming Li, Gang Ren, Michael Bulaksis, Gerald DeJong, Maria Garzaran, David Padua, Keshav Pingali, Paul Stodghill, and Peng Wu. 2003. A comparison of empirical and model-driven optimization. SIGPLAN Not. 38, 5 (May 2003), 63–76. https://doi.org/10.1145/780822.781140
  35. [35]K. Yotov, Xiaoming Li, Gang Ren, M.J.S. Garzaran, D. Padua, K. Pingali, and P. Stodghill. 2005. Is Search Really Necessary to Generate High-Performance BLAS? Proc. IEEE 93, 2 (2005), 358–386. https://doi.org/10.1109/JPROC.2004.840444

Paper details

vlnc:W_628fya9n
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents