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.