Optimizing strassen matrix multiply on GPUs

Ayaz ul Hasan Khan, Mayez Al-Mouhamed, Allam Fatayer

Research output: Chapter in Book/Report/Conference proceedingConference contribution


© 2015 IEEE. Many core systems are basically designed for applications having large data parallelism. Strassen Matrix Multiply (MM) can be formulated as a depth first (DFS) traversal of a recursion tree where all cores work in parallel on computing each of the NxN sub-matrices that reduces storage at the detriment of large data motion to gather and aggregate the results. We propose Strassen and Winograd algorithms (S-MM and W-MM) based on three optimizations: a set of basic algebra functions to reduce overhead, invoking efficient library (CUBLAS 5.5), and parameter-tuning of parametric kernel to improve resource occupancy. On GPUs, W-MM and S-MM with one recursion level outperform CUBLAS 5.5 Library with up to twice as faster for large arrays satisfying N>=2048 and N>=3072, respectively. Compared to NVIDIA SDK library, S-MM and W-MM achieved a speedup between 20x to 80x for the above arrays. The proposed approach can be used to enhance the performance of CUBLAS and MKL libraries.
Original languageEnglish (US)
Title of host publication2015 IEEE/ACIS 16th International Conference on Software Engineering, Artificial Intelligence, Networking and Parallel/Distributed Computing (SNPD)
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
ISBN (Print)9781479986767
StatePublished - Jun 2015
Externally publishedYes

Bibliographical note

KAUST Repository Item: Exported on 2020-10-01
Acknowledgements: The authors would like to acknowledge the support provided by King Abdulaziz City for Science and Technology (KACST) through the Science & Technology Unit at King Fahd University of Petroleum & Minerals (KFUPM) for funding this work through project No.12-INF3008-04 as part of the National Science, Technology and Innovation Plan. We are also very thankful to King Abullah University of Science and Technology (KAUST) for providing access to their K20X GPU cluster to run the experiments.
This publication acknowledges KAUST support, but has no KAUST affiliated authors.


Dive into the research topics of 'Optimizing strassen matrix multiply on GPUs'. Together they form a unique fingerprint.

Cite this