Communication-avoiding parallel strassen: implementation and performance

Abstract

Abstract—Matrix multiplication is a fundamental kernel of many high performance and scientific computing applications. Most parallel implementations use classical O(n 3) matrix multiplication, even though there exist Strassen-like matrix multiplication algorithms that have lower arithmetic complexity, as the classical ones perform better in practice. We recently obtained a new parallel algorithm that is based on Strassen’s fast matrix multiplication (SPAA ’12) that minimizes communication: it communicates asymptotically less than all classical and all previous Strassen-based algorithms, and it attains corresponding lower bounds. It is also the first parallel-Strassen algorithm that exhibits perfect strong scaling. In this paper, we show that the new algorithm is also faster in practice. We benchmark and compare the performance of our new algorithm to previous algorithms on Franklin (Cray XT4), Hopper (Cray XE6), and Intrepid (IBM BG/P). We demonstrate significant speedups over previous algorithms both for large matrices and for small matrices on large numbers of processors. We model and analyze the performance of the algorithm, and predict its performance on future exascale platforms. I.