Hidden GEMMs: How Optimized Math Libraries Work
summary
Shows how a naive C triple loop yields ~1,200 ms while simple loop reordering cuts that to ~167 ms and cache-aware tiling plus ICC brings it to ~56 ms (NumPy 74 ms, MATLAB/MKL ~20 ms). On GPU a naive kernel is ~280 ms; using shared-memory tiling, coalesced access and avoiding bank conflicts drops kernels to ~48–55 ms and cuBLAS hits ~11 ms; a Titan X can reach ~1 ms. Techniques and tradeoffs are measured and shown to work.
AI-written summary · about
chapters (39)
- 0:00Intro
- 1:31Outline
- 2:09Why bother?
- 3:21GEMM in Cholesky and LU
- 3:33GEMM definition
- 4:04Test machine specs
- 5:43CPU - Naive GEMM (C-like Java*)
- 5:57CPU - Naive GEMM (C-like Python*)
- 6:22CPU GEMM in Octave/MATLAB
- 6:35Modern CPUs
- 7:27Trip through the Intel pipeline
- 8:59Seq Access and Prefetch
- 10:01GEMM with loop reordering
- 11:49CPU - Tiled GEMM
- 12:52CPU Tiled GEMM - GCC
- 13:15CPU Tiled GEMM - ICC
- 14:14Pointer Aliasing
- 15:25CPU Pipeline Clock cycle
- 15:46CPU Pipeline Bubble
- 16:13CPU Loop Unrolling
- 17:03Packed add (GCC fail)
- 17:55Other algorithms
- 19:25More CPU tweaks - intrinsics
- 19:50Fused multiply-add (FMA)
- 21:32GPU Design Decisions
- 25:50CUDA Steps (Host Perspective)
- 26:53GPU - Naive Global GEMM
- 28:19GPU - Shared GEMM (Tiling) Global Memory
- 29:19Aligned / Coalesced Global Mem.
- 30:02Aligned + Coalesced Access
- 30:25Misaligned, Coalesced Access
- 30:50Misaligned + Uncoalesced Access
- 31:08Aligned + Coalesced vs. Strided
- 31:53Coalesced Global Memory
- 32:42Shared Bank Conflict Resolution
- 33:28GEMM via outer product
- 35:31GPU Computation Optimization
- 35:47Recap
- 36:45CUBLAS GEMM - Titan X
related talks
01h 00mThe Blaze High Performance Math Library
19mOptimizing for GPUs
18mCompiling Strassen-like Matrix Multiplication Algorithms to Fast CUDA Kernels
08mGPU Programming with Triton Kernels
33mWhen GPUs Make Python Slower: Patterns and Pitfalls
19mOptimizations and abstractions for sparse machine learning
01h 06mEfficient GPU Programming with Modern C++
31m"Optimizing Scientific Python with C++, CUDA, and Serverless Compute"