preprint · arXiv (Cornell University) · 2018
Implementing Strassen's Algorithm with CUTLASS on NVIDIA Volta GPUs
Jianyu Huang, Chenhan D. Yu, Robert A. Geijn
Cited by 9Open access
Abstract
Conventional GPU implementations of Strassen's algorithm (Strassen) typically rely on the existing high-performance matrix multiplication (GEMM), trading space for time. As a result, such approaches can only achieve practical speedup for relatively large, "squarish" matrices due to the extra memory overhead, and their usages are limited due to the considerable workspace. We present novel Strassen primitives for GPUs that can be composed to generate a family of Strassen algorithms. Our algorithms utilize both the memory and thread hierarchies on GPUs, reusing shared memory and register files inherited from GEMM, fusing additional operations, and avoiding extra workspace. We further exploit intra- and inter-kernel parallelism by batching, streaming, and employing atomic operations. We also develop a performance model for NVIDIA Volta GPUs to select the appropriate blocking parameters and predict the performance for GEMM and Strassen. Overall, our 1-level Strassen can achieve up to 1.11x speedup with a crossover point as small as 1,536 compared to cublasSgemm on a NVIDIA Tesla V100 GPU. With additional workspace, our 2-level Strassen can achieve 1.19x speedup with a crossover point at 7,680.
Cite this paper
Huang, J., Yu, C. D., & Geijn, R. A. (2018). Implementing Strassen's Algorithm with CUTLASS on NVIDIA Volta GPUs. arXiv (Cornell University). https://doi.org/10.48550/arxiv.1808.07984
Huang, Jianyu, et al. “Implementing Strassen's Algorithm with CUTLASS on NVIDIA Volta GPUs.” arXiv (Cornell University), 2018, https://doi.org/10.48550/arxiv.1808.07984.
Huang, Jianyu, Chenhan D. Yu, and Robert A. Geijn. 2018. “Implementing Strassen's Algorithm with CUTLASS on NVIDIA Volta GPUs.” arXiv (Cornell University). https://doi.org/10.48550/arxiv.1808.07984.
Huang, J., Yu, C.D. and Geijn, R.A. (2018) ‘Implementing Strassen's Algorithm with CUTLASS on NVIDIA Volta GPUs’, arXiv (Cornell University). Available at: https://doi.org/10.48550/arxiv.1808.07984.
@misc{huang2018implementing,
title = {{Implementing Strassen's Algorithm with CUTLASS on NVIDIA Volta GPUs}},
author = {Huang, Jianyu and Yu, Chenhan D. and Geijn, Robert A.},
journal = {arXiv (Cornell University)},
year = {2018},
doi = {10.48550/arxiv.1808.07984}
}Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.