Parallel Matrix Multiplication
Parallel Matrix Multiplication (GEMM) is the operation C = α×A×B + β×C for dense matrices — the most important computational kernel in high-performance computing, deep learning, and scientific simulations, extensively optimized in BLAS libraries.
GEMM Complexity
- Naive triple-loop: O(N³) operations for N×N matrices.
- N=1024: 2 billion operations — serial takes ~2 seconds on single core.
- N=4096: 128 billion operations — needs parallelism.
BLAS (Basic Linear Algebra Subprograms)
- Level 3 BLAS: Matrix-matrix operations (GEMM, TRSM, SYRK).
- Vendor implementations: MKL (Intel), OpenBLAS, BLIS, cuBLAS (NVIDIA), rocBLAS (AMD).
- Drop-in replacement: Same API, dramatically different performance.
- MKL DGEMM: 90%+ of peak FLOPS on modern Intel CPUs.
CPU GEMM Optimization Techniques
Blocking (Tiling):
- Break matrices into blocks that fit in cache.
- Reduce cache miss rate from O(N³) → O(N³/B) for block size B.
- Three levels: Register tile → L1 tile → L2/L3 tile.
SIMD Vectorization:
- Use AVX-512 FMA to process 16 float/8 double FMAs per cycle.
- Register microkernel: 6×16 float accumulation in 48 registers (AVX-512).
Packing:
- Reorganize matrix panels into contiguous memory for stride-1 access.
- Eliminates TLB misses and streaming prefetch issues.
GPU GEMM
- cuBLAS GEMM: Uses Tensor Cores (16x16x16 matrix multiply per cycle).
- CUTLASS: Open-source CUDA GEMM with tunable tile sizes.
- Flash Attention: Fused attention is essentially batched GEMM with online softmax.
Distribution Across Nodes
- 2D block distribution: A and B partitioned in 2D across P processors.
- Cannon's algorithm: Communication-optimal 2D GEMM.
- SUMMA: Scalable Universal Matrix Multiplication Algorithm.
- ScaLAPACK, libflame: Distributed GEMM implementations.
GEMM optimization is the foundation of modern AI computing — 70–90% of transformer inference and training time is spent in matrix multiplications, and every 10% GEMM efficiency improvement translates directly to training cost and inference latency reduction.