Poster: Beating MKL and ScaLAPACK at Rectangular Matrix Multiplication Using the BFS/DFS Approach
James Weldon Demmel, David Eliahu, Armando Fox, Shoaib Kamil, Benjamin Lipshitz, Oded Schwartz, Omer Spillinger · 2012
We implement a Communication Avoiding Recursive Matrix Multiplication algorithm (CARMA) . First communication-optimal parallel algorithm for all dimensions of matrices . The shared-memory version of CARMA is only '-50 lines of code . Much simpler than 3D SUMMA [8], the rectangular version of 2.5D [9] . Fasterthan MKL and ScaLAPACK in practice: . Faster for skinny matrices in which k is the largest dimension: up to 7X speedup single-node, 141X speedup distributed o Faster for large square matrices: up to 1.2χ speedup single-node, 3X speedup distributed o Comparable performance for other matrix dimensions o Speedup is mainly due to reduced communication (see bar charts in Performance Results").