Strassen’s matrix multiplication on gpus

We provide efficient single- and double-precision GPU (Graphics Processing Unit) implementa-tions of Strassen’s matrix multiplication algorithm as well as of Winograd’s variant of this algorithm. The single-precision implementations of these two algorithms are compared analytically using the arithmetic count, device-memory transactions, and device memory to multiprocessor data volume metrics. Our analysis indicates that, for 16384 × 16384 matrices, our single-precision implementation of Strassen’s algorithm limited to four levels of recursion reduces the number of arithmetics by 41.3%, the number of transactions by 33.7%, and the volume by 29.2 % relative to the best known GPU implementation of the classical n3 matrix multiplication algorithm. The corresponding reductions achieved by Winograd’s variant are 41.3%, 35.1%, and 31.5%. Experimental results obtained using an NVIDIA C1060 GPU indicate a speedup of 32 % for Strassen’s 4-level implementation and 33 % for Winograd’s variant relative to the sgemm code in CUBLAS 3.0 when multiplying 16384 × 16384 ma-trices. Our double-precision implementations of Strassen’s and Winograd’s algorithms, respectively, achieve a speedup of 20.2 % and 21 % relative to dgemm when the matrix size n is 8192. The maximum numerical error introduced by Strassen’s and Winograd’s algorithms are about 2 orders of magnitude higher than those for sgemm when n = 16384 and about 1 order of magnitude higher than for dgemm for n = 8192. The average numerical error introduced by Strassen’s and Winograd’s algorithms are, respectively, 2 and 3 orders of magnitude higher than those for sgemm when n = 16384 and about 1 order of magnitude higher than for dgemm for n = 8192