Pebbling Game and Alternative Basis for High Performance Matrix Multiplication
Oded Schwartz, Noa Vaknin · SIAM Journal on Scientific Computing · 2023
Abstract. Matrix multiplication is one of the most extensively used kernels in scientific computing. Although subcubic algorithms exist, most high performance implementations are based on the classical [Formula: see text] matrix multiplication. Designing an algorithm that obtains even modest improvements in performance over existing implementations, requires carefully addressing challenges such as reducing computation costs, communication costs, and memory footprint. We provide the first high performance general matrix-matrix multiplication that utilizes the alternative basis method on Strassen’s algorithm. We reduce the basis transformation overheads and decrease the memory footprint of the bilinear phase by using the pebbling game optimization scheme, consequentially improving both arithmetic and communication costs. Our algorithm outperforms DGEMM on feasible matrix dimensions starting at [Formula: see text]. It obtains an increasing speedup of up to nearly [Formula: see text] speedup for larger matrix dimensions when running sequentially, and even larger speedups for certain matrix dimensions when running in parallel.