DocumentCode :
729449
Title :
Optimizing strassen matrix multiply on GPUs
Author :
ul Hasan Khan, Ayaz ; Al-Mouhamed, Mayez ; Fatayer, Allam
Author_Institution :
Dept. of Comput. Eng., KFUPM, Dhahran, Saudi Arabia
fYear :
2015
fDate :
1-3 June 2015
Firstpage :
1
Lastpage :
6
Abstract :
Many core systems are basically designed for applications having large data parallelism. Strassen Matrix Multiply (MM) can be formulated as a depth ¿rst (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 (SMM 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, SMM 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.
Keywords :
graphics processing units; matrix algebra; multiprocessing systems; DFS traversal; GPU; MM; NxN submatrices; Strassen matrix multiply; algebra functions; core systems; data motion; data parallelism; optimizing Strassen matrix multiply; recursion tree; Algorithm design and analysis; Graphics processing units; Kernel; Libraries; Matrices; Registers; Standards; CUDA Programming; Fast Matrix Multiplication; Graphics Processing Unit (GPU); Strassen;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Software Engineering, Artificial Intelligence, Networking and Parallel/Distributed Computing (SNPD), 2015 16th IEEE/ACIS International Conference on
Conference_Location :
Takamatsu
Type :
conf
DOI :
10.1109/SNPD.2015.7176172
Filename :
7176172
Link To Document :
بازگشت