Analytical model finds best tile size for faster CPU matrix multiplication
Waypoint: Analytically Modeling GEMM for CPUs
Distributed, Parallel, and Cluster ComputingArtificial Intelligence
Summary
Multiplying large tables of numbers quickly on a computer is important for many tasks but can be tricky to do efficiently. The authors created a model called Waypoint that predicts how fast different ways of cutting these tables into smaller pieces will run on a CPU. By testing many sizes using this model, they find the fastest way to break down the task automatically. They built a new tool that uses this model and matches or beats top existing tools for matrix multiplication, making some AI tasks run faster on CPUs.
What this means in practice
- •For cpu software engineers: Optimize matrix multiplication in software libraries by selecting tile sizes that maximize CPU performance automatically.
- •For hardware design teams: Estimate realistic matrix multiplication performance on experimental CPU designs using the model for better hardware evaluation.
Authors
Srinidhi N, Sunanda Somwase, Hemant Kumar Chandrakant Chandavar, Eashan Dash, Varun Agrawal, Prakash Raghavendra
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 \times$ speedups.