PaperlayerView exact revision on arXiv

Source-linked AI summary

Waypoint: Analytically Modeling GEMM for CPUs

Srinidhi N, Sunanda Somwase, Hemant Kumar Chandrakant Chandavar, Eashan Dash, Varun Agrawal, Prakash Raghavendra

arXiv:2610.34914v2cs.DCcs.AI

TL;DR

CPU GEMM performance depends on choosing tiles for the hardware and input shape, while Roofline estimates may differ from realistic performance. Waypoint estimates GEMM performance and searches tile sizes; OPAM uses it to select tiles, performs comparably to state-of-the-art libraries, and reports LLM inference speedups on new hardware.

  • Problem

    Roofline estimates can differ from realistic GEMM performance, while tile choices depend on both hardware and input matrix shape.

    Source: §1 · pp. 1–2

  • Method

    Waypoint models realistic performance and estimates tile-specific performance to search for optimal tile sizes; OPAM uses Waypoint-Tile to select tiles for each input and hardware configuration.

    Source: §1 · p. 2

  • Results

    1.36–1.98× speedups for LLM inference on new hardware accompany OPAM's comparable performance to state-of-the-art GEMM libraries across hardware configurations and input sizes.

    Source: §1 · p. 2

  • Takeaways & Limitations

    OPAM adapts to new hardware configurations and achieves near-peak performance without manual tuning.

    Source: §1 · p. 2

    For multithreaded GEMM, Waypoint assumes equal tile distribution or static scheduling, which may not be optimal; some shapes run faster with fewer than the prescribed threads.

    Source: §6 · pp. 11–12

Abstract

from arXiv · show

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 \times$ speedups.

1 Introduction

CPU GEMM matters across machine-learning workloads, but tile choices depend on hardware and input shape, and Roofline estimates can differ from realistic performance. Waypoint models achievable performance and searches tile sizes; OPAM uses it to select tiles.

1 Introduction

  • Existing libraries target a hardware or shape class, while optimal tiles depend on hardware and input shape [31], and Roofline estimates can differ from realistic performance.The paper notes that tile sizes can affect memory access efficiency and hardware utilization.Source: §1 · pp. 1–2
  • Waypoint's hardware- and input-parametric estimates are intended to help designers assess realistic performance on experimental hardware, including ISA extensions such as AMX, ACE, and APX.OPAM uses Waypoint-Tile to select tiling parameters automatically for a GEMM shape and hardware configuration.Source: §1 · pp. 1–2
  • Waypoint-Strict models GEMM performance independently of software implementation and tightens Roofline estimates by accounting for additional issued compute instructions and more accurate memory bandwidth.The paper proves it is tighter than Roofline and reports that state-of-the-art libraries realize its estimates.Source: §1 · p. 2
  • Waypoint-Tile estimates performance for a specific tile size, models cache misses and their costs, and searches candidate sizes to select an optimal tile.It accounts for cache levels, cache-line sizes, and memory-bandwidth limitations while narrowing the search space.Source: §1 · p. 2
  • Waypoint-Strict estimates are consistently closer to observed performance (geomean 1.096×), and Waypoint-Tile's best-tile estimate predicts realistic performance (geomean 1.012×).The authors use these accuracy results to support identifying optimal tile sizes and estimating performance on future hardware.Source: §1 · p. 2
  • 1.36–1.98× speedups for LLM inference on new hardware accompany OPAM's comparable performance to state-of-the-art GEMM libraries across configurations and input sizes.OPAM also adapts to new hardware configurations and achieves near-peak performance without manual tuning.Source: §1 · p. 2

2 Analytical Model

Waypoint first estimates GEMM performance independently of implementation, then models tiled implementations to estimate and select tile sizes for particular hardware and matrix shapes. Its costs account for compute instructions, memory hierarchy effects, and threading overhead.

2.1 Waypoint-Strict

  • Waypoint-Strict estimates GEMM latency from hardware parameters and operation inputs, combining compute, memory, and threading costs.The hardware configuration includes compute-instruction properties, register and cache information, memory bandwidth, core count, and frequency.Source: §2.1 · p. 3

2.1.1 Compute latency

  • Compute latency includes required core instructions plus support costs for zeroing registers, loading inputs, and storing outputs.The model derives instruction count from GEMM dimensions and the core instruction’s element capacity; it also allows matrix instructions through user-specified instruction dimensions.Source: §2.1.1 · p. 3

2.1.2 Memory latency; 2.1.3 Threading overhead

  • Memory-channel contention is modeled for multithreaded GEMM, while threading overhead assumes threads do not contend for data and can include costs when working sets exceed cache capacity.The model also accounts for reduction costs when threads split the K dimension.Source: §2.1.2 · p. 3, §2.1.3 · pp. 3–4

2.1.4 Theoretical results

  • For any GEMM operation on given hardware, Waypoint-Strict latency is at least the Roofline estimate.The model adds costs such as register zeroing and data movement in compute-bound cases, and accounts for effective bandwidth and possible threading overhead.Source: §2.1.4 · p. 4

2.2 Waypoint-Tile

  • Waypoint-Tile estimates a tiling option’s latency by combining repeated micro-kernel and macro-kernel costs, then searches tile choices for the best option.The model includes compute and cache-access costs at the micro-kernel level and data movement at the macro-kernel level.Source: §2.2 · pp. 4–5

2.1.5 Soundness of the assumptions

  • Waypoint-Tile predicts best-tiling estimates within 5%; Waypoint-Strict improves on Roofline by up to 3%, and optimized libraries match estimates with a 0.03% gap.Figure 1 compares additional latency captured by Waypoint-Strict and Roofline across hardware, data types, and GEMM shapes.Source: Figure 1 · p. 4, §2.1.5 · p. 4, §2.2 · p. 5

2.2.1 Micro-kernel cost; 2.2.2 Macro-kernel cost

  • Micro-kernel tile selection balances cache-miss reuse costs against register-pressure and load-to-FMA latency bounds; macro-kernel costs model capacity misses across cache levels.For macro-kernel costs, the model treats the streamed B matrix separately from A and C, and includes partial-result loading when Kc < K.Source: §2.2.1 · p. 5, §2.2.2 · p. 6

2.3 Packing

  • OPAM packs inputs into blocks sized by least common multiples of possible register and K tile sizes, preserving full-cache-line accesses and fixed-stride locations across tile choices.The paper reports that further packing optimizations add cost without significant performance improvement.Source: §2.3 · p. 7

3 Model based GEMM library

OPAM applies Waypoint-derived tiling parameters to GEMM, with exhaustive and fast heuristic search options. The evolved fast heuristic is 18,851× faster than exhaustive search while keeping estimated latency within 1.94% of the best parameters.

OPAM implementation

  • OPAM uses Waypoint parameters to decompose GEMM, Parlooper[15] to generate OMP-parallel loops, and a JIT library that emits and caches microkernel assembly.The authors report that Libxsmm lacked the flexibility needed to generate kernels from analytically derived parameters.Source: §3 · p. 7

Search options

  • OPAM supports exhaustive search over a Waypoint-Tile-pruned parameter space and a fast heuristic alternative for latency-sensitive applications such as LLM inference.The exhaustive search considers optimal Mr and Nr values and bounds Mc, Nc, and Kc using cache sizes.Source: §3 · p. 7

Fast heuristic search

  • OpenEvolve evolves Waypoint-Tile-informed seed heuristics through mutations, scores candidates against pinned exhaustive-search optima, and produces a reusable heuristic after 100 iterations.The evolution targets a curated set of GEMM shapes used in modern LLM inference workloads; heuristic generation is a one-time cost.Source: Figure 3 · p. 7, §3 · pp. 7–8
  • 18,851× faster than exhaustive search, the fast heuristic selects tiling parameters with estimated latency within 1.94% (maximum) of the best Waypoint-derived parameters.The evaluation includes the cost of the fast heuristic search.Source: §3 · p. 8

4 Evaluation

The evaluation tests Waypoint’s model accuracy, OPAM’s performance against established libraries, and effects on end-to-end LLM inference. OPAM is competitive with existing libraries, while shape-adaptive tiling improves inference performance.

4.1 Experimental Setup

  • The evaluation compares OPAM with AOCL-BLAS and AOCL-DLP on Zen 5 and Zen 6 across FP32, BF16, and INT8, and with SFC only on FP32 and BF16 because SFC does not support INT8.For end-to-end LLM inference, OPAM is integrated into AMD-PACE and compared with a baseline using TPP to dispatch GEMM calls.Source: §4 · p. 8, §4.1 · pp. 8–9

4.2 RQ1: Model accuracy

  • Waypoint-Strict predicts actual GEMM performance within 9.6%, while Waypoint-Tile estimates the best tiling option with a geometric mean error of 1.2%.Waypoint-Tile ranks the top option within 5% of peak performance for 88.7% of shapes and strictly best in 62.7%.Source: §4 · p. 8, §4.2 · p. 9

4.4 RQ3: End-to-end LLM inference performance

  • 1.36× to 1.98× average TTFT speedups were observed across batch sizes, input lengths, models, and hardware architectures.The gains are attributed primarily to improved GEMM computation times for odd inference shapes.Source: §4 · p. 8, §4.4 · p. 10

4.2 RQ1: Model accuracy

  • For hypothetical AI Compute Extensions, Waypoint predicts that data-movement costs temper the expected GEMM gains as compute throughput increases.The analysis covers proposed tile-operation throughput configurations relative to Zen 5 across 44 shapes per datatype; accelerated kernels can become memory-bound.Source: §4.2 · p. 9, Table 3 · p. 9

4.3 RQ2: OPAM performance comparison

  • Including packing cost, OPAM is 1.168× faster than AOCL-BLAS, 1.210× faster than SFC, and 1.136× faster than AOCL-DLP.Gains over AOCL-BLAS and AOCL-DLP are attributed primarily to shape-adaptive tiling and comparable packing cost; gains over SFC to lower packing cost and comparable GEMM performance.Source: §4.3 · p. 10

4.5 Extending to other architectures

  • The model’s principles are described as extendable beyond AMD x86 to architectures with layered memory hierarchies and pipelined vector or matrix units.Intel x86 is described as an immediate fit, while ARM’s variable-length vector and matrix extensions fit the model’s parametric design.Source: §4.5 · p. 10

5 Related work

Prior GEMM work developed tiled libraries, empirical tuning, and analytical models, but earlier approaches did not generally adapt tile choices to specific input shapes. Waypoint extends analytical modeling to CPU GEMM and alternative implementations, with OPAM tracking Waypoint-Tile estimates.

5 Related work

  • Tiled GEMM libraries build on work showing that smaller blocks improve cache utilization, while later studies used empirical methods to tune tiling parameters.The cited empirical work also studied performance effects of different tiling choices.Source: §5 · p. 10
  • Waypoint extends analytical tiling models by adapting parameters to both hardware architecture and the specific input matrix shape.Prior models adapted to hardware or specific shape classes.Source: §5 · p. 10
  • Figure 5 presents relative performance comparisons of AOCL-BLAS, SFC, AOCL-DLP, and Waypoint-Tile versus OPAM, with results separated by hardware architecture.Source: Figure 5 · p. 11
  • Roofline-based approaches estimate peak performance, while other models capture architectural effects but may be architecture-specific or require target-hardware traces.Waypoint is described as accurate and parametric in hardware architecture for estimating realistic achievable performance.Source: §5 · p. 11
  • Waypoint generalizes a GPU-focused GEMM modeling approach to CPUs, and its models can predict alternative implementations such as Space Filling Curve layouts.The cited figure reports end-to-end inference speedups on prefill-heavy workloads across hardware and models, with geometric means and full-range whiskers.Source: §5 · p. 11, Figure 6 · p. 11

6 Discussion and Conclusion

Waypoint combines realistic GEMM performance estimation with tile selection, and OPAM uses it to guide tiling across hardware. Its multithreaded model assumes simple work splits, which can miss better thread configurations for some matrix sizes.

6 Discussion and Conclusion

  • The multithreaded model assumes equal tile distribution or static scheduling, which may not reflect the optimal parallel execution strategy.These assumptions constrain how the model represents thread-level work splitting.Source: §6 · p. 11
  • For some matrix sizes, using fewer than the prescribed number of threads can yield better performance, motivating more sophisticated thread management..Source: §6 · p. 12
  • Waypoint provides a tighter-than-Roofline GEMM estimate and helps select tiling parameters; OPAM uses the model and matches state-of-the-art libraries on existing hardware.The conclusion also reports gains on future hardware and improved end-to-end CPU inference performance.Source: §6 · p. 12

A Appendix A: Heuristic Search Details

The appendix describes an OpenEvolve search for fast heuristics against Waypoint-derived best tiling parameters, using curated GEMM shapes and diverse seed programs.

A Appendix A: Heuristic Search Details

A.1 Seed programs

  • Six seed programs target different shape classes and form separate evolutionary islands, providing diverse starting heuristics.The seed set is intended to enable mutation, combination, and evolution toward effective fast-search heuristics.Source: §A.1 · p. 14
  • The seeds cover datatype and dimension ratios, cache bounds, multithreading splits, arithmetic intensity, AI/AMX instructions, and baseline or prior-best programs..Source: §A.1 · p. 14

A.2 Fast heuristic search results

The fast heuristic search results are presented as the average expected-latency difference from exhaustive search.

A.2 Fast heuristic search results

  • The results plot the average expected-latency difference between fast heuristic search and exhaustive search..Source: §A.2 · p. 14

B.1 Evaluation shapes

The evaluation uses 51 unique GEMM shapes, tested across two hardware configurations and three data types.

B.1 Evaluation shapes

  • 51 unique GEMM shapes are included in the evaluation.Table 5 lists the evaluated shapes.Source: §B.1 · p. 14
  • Each shape is evaluated on both hardware configurations.Source: §B.1 · p. 14
  • Each shape is evaluated for all three data types described in Section 4.Source: §B.1 · p. 14

B.2 Packing cost

OPAM’s packing cost is compared with implementation packing cycles across the evaluated shapes using geometric-mean ratios.

B.2 Packing cost

  • Table 6 reports OPAM packing cost relative to the implementation packing cost.Source: §B.2 · p. 14
  • The reported values are geometric-mean ratios of implementation packing cycles to OPAM packing cycles.Source: §B.2 · p. 14
  • The ratios cover all evaluated shapes.Source: §B.2 · p. 14

C Model Assumptions

Waypoint’s estimates rely on assumptions about hardware behavior. These assumptions simplify frequency, instruction choice, data access, cache behavior, bandwidth sharing, and store throughput.

C Model Assumptions

  • Waypoint estimates rely on assumptions about the behavior of the underlying hardware.Source: C Model Assumptions · p. 14
  • Waypoint assumes fixed CPU frequency when estimating GEMM performance and memory-access cycles.For variable frequency, the model can be extended by incorporating frequency changes into cycle estimates.Source: C Model Assumptions · p. 14
  • Waypoint assumes compute uses the highest-throughput, lowest-latency instruction and does not explore mixed-instruction use.For x86, it assumes AVX512 FMA/VNNI.Source: C Model Assumptions · p. 14
  • Waypoint assumes compute data is loaded from contiguous memory strides at the lowest loading cost, which the authors consider valid for pre-packed GEMM data.Source: C Model Assumptions · p. 14
  • The cache model distinguishes access latencies across levels but does not model inclusivity, write-back policies, or replacement strategies.The authors state that a more complex cache model could estimate access latencies better.Source: C Model Assumptions · p. 14
  • For multi-thread GEMM, Waypoint shares memory bandwidth across threads and assumes stores reach peak subsystem throughput because result locations typically reside in caches.Source: C Model Assumptions · p. 14
Loading 2610.34914v2…