Elamur Research⌕
☰
home / papers / 2020 / Sparse GPU Kernels for Deep Learning

Sparse GPU Kernels for Deep Learning

Paper · 2020 · Trevor Gale, Matei Zaharia, Cliff Young et al.

Summary

Sparse neural networks promise fewer FLOPs and parameters, but on GPUs they rarely run faster than dense ones. Existing sparse libraries are tuned for scientific matrices that are over 99% sparse, while deep learning matrices are only moderately sparse. Block-structured sparsity restores speed but can hurt accuracy. The authors first characterize the sparse matrices that occur in deep learning: 3,012 weight matrices from 49 pruned ResNet-50 and Transformer models, compared against the SuiteSparse collection. They find that DL matrices are much denser, have longer rows and have far more uniform row lengths. Building on these properties, they write CUDA kernels for SpMM and SDDMM that work on plain CSR with unstructured sparsity. The kernels use 1-D tiling, vector memory access on misaligned sparse data and a decoupled load-balancing scheme. On V100 GPUs they beat cuSPARSE by 3.58× (SpMM) and 2.19× (SDDMM) in geometric mean. Sparse Transformer and MobileNet models gain 1.2–2.1× end to end with no loss of accuracy. The result makes unstructured sparsity practical for both inference and training, and the code is released as Sputnik.

Key points

  • Dataset: 3,012 sparse weight matrices from 49 models, produced with four sparsification algorithms.
    • ResNet-50 on ImageNet, keeping only models above 70% top-1 accuracy.
    • Transformer on WMT14 English-German, keeping only models above 20 BLEU.
    • Baseline for comparison: the 2,833 matrices of the SuiteSparse Matrix Collection.
  • Matrix properties: relative to scientific matrices, the average DL matrix has 13.4× lower sparsity, rows that are 2.3× longer, and a coefficient of variation in row length that is 25× smaller.
  • Kernel speed: geometric-mean speedups of 3.58× (SpMM) and 2.19× (SDDMM) over Nvidia cuSPARSE on V100. The best problems reach 27% of single-precision peak.
  • Break-even point: on an LSTM-sized SpMM problem, the sparse kernel overtakes dense from about 71% sparsity. Vendor libraries need roughly 14× fewer nonzeros to reach the same speed.
  • End-to-end gains: sparse Transformer and MobileNet models run 1.2–2.1× faster and use up to 12.8× less memory at matching accuracy. Code: github.com/google-research/sputnik.

Interesting ideas

  • I1. Profile real workloads first. Before optimizing, the authors measured the statistics of their target matrices (sparsity, mean row length, row-length CoV) and contrasted them with the standard benchmark collection. This showed that the benchmark did not represent their workload. Any project that reuses tools built for another domain could run the same check first.
  • I2. Use row-length CoV as an imbalance signal. Variation in row length is a cheap, single-number predictor of load imbalance. It could just as well flag skew in batching variable-length sentences or partitioning uneven trade records.
  • I3. Specialize the operation to how it is actually used. The SDDMM kernel drops the element-wise scaling and assumes a transposed operand, because that is the form gradients and sparse attention need. The authors still note that the general case remains easy to add. Fitting an operator to its real call pattern, while keeping it extensible, often yields large gains.
  • I4. Keep load balancing separate from parallelization. "Row swizzle" balances work independently of how the computation is split across processing elements. Each part can then be changed or tuned without touching the other.
  • I5. Stay with a standard format and no structural constraints. Working directly on standard CSR, without forcing block patterns, avoids trading model quality for speed. The kernels also stay compatible with existing tooling. This is a useful principle when designing any data-format or compression layer.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Institutions

🏢GoogleMountain View · United States492 works · 440,462 citations🎓Stanford UniversityStanford · United States506 works · 330,052 citations🏢Google DeepMindLondon · United Kingdom72 works · 84,326 citations

 Fields, topics and concepts

📚 Shelves 4The field of science this work belongs to (OpenAlex fields).Computer Science · 18,614 worksComputer Vision and Pattern Recognition · 3,486 worksComputational Theory and Mathematics · 321 worksHardware and Architecture · 167 works

🧭 Topics 1Research subjects and languages the work is about.GPU & parallel computing · 41 works

Cite

Cite as Trevor Gale, Matei Zaharia, Cliff Young and Erich Elsen. 2020. Sparse GPU Kernels for Deep Learning. SC 2020.

The paper itself, not this page. BibTeX from the library's record of the work. arXiv 2006.10901

@inproceedings{gale2020sparse,
  title = {{Sparse GPU Kernels for Deep Learning}},
  author = {Trevor Gale, Matei Zaharia, Cliff Young and Erich Elsen},
  booktitle = {SC 2020},
  year = {2020},
  doi = {10.1109/sc41405.2020.00021},
  eprint = {2006.10901},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.1109/sc41405.2020.00021}
}

References

55 references, 13 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. K. He, X. Zhang, S. Ren, and J. Sun, “Deep Residual Learning for Image Recognition,” in 2016 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2016, Las Vegas, NV, USA, June 27-30, 2016, 2016.
  2. A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, L. Kaiser, and I. Polosukhin, “Attention is All you Need,” in Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, 4-9 December 2017, Long Beach, CA, USA, 2017.
  3. S. Han, J. Pool, J. Tran, and W. J. Dally, “Learning both Weights and Connections for Efficient neural network,” in Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, December 7-12, 2015, Montreal, Quebec, Canada, 2015. find
  4. S. Narang, G. Diamos, S. Sengupta, and E. Elsen, “Exploring Sparsity in Recurrent Neural Networks,” in 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings, 2017. find
  5. M. Zhu and S. Gupta, “To Prune, or Not to Prune: Exploring the Efficacy of Pruning for Model Compression,” in 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 - May 3, 2018, Workshop Track Proceedings, 2018. find
  6. R. Child, S. Gray, A. Radford, and I. Sutskever, “Generating Long Sequences with Sparse Transformers,” CoRR, vol. abs/1904.10509, 2019.
  7. Y. LeCun, J. S. Denker, and S. A. Solla, “Optimal Brain Damage,” in Advances in Neural Information Processing Systems 2, [NIPS Conference, Denver, Colorado, USA, November 27-30, 1989], 1989. find
  8. D. Molchanov, A. Ashukha, and D. P. Vetrov, “Variational dropout sparsifies deep neural networks,” in Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6-11 August 2017, 2017. find
  9. C. Louizos, M. Welling, and D. P. Kingma, “Learning Sparse Neural Networks through L_0 Regularization,” in 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 - May 3, 2018, Conference Track Proceedings, 2018. find
  10. N. Kitaev, L. Kaiser, and A. Levskaya, “Reformer: The Efficient Transformer,” in International Conference on Learning Representations, 2020. [Online]. Available: https://openreview.net/forum?id=rkgNKkHtvB ↗
  11. A. Roy, M. Saffar, A. Vaswani, and D. Grangier, “Efficient content-based sparse attention with routing transformers,” CoRR, vol. abs/2003.05997, 2020.
  12. S. Narang, E. Undersander, and G. F. Diamos, “Block-Sparse Recurrent Neural Networks,” CoRR, vol. abs/1711.02782, 2017. — [arXiv:1711.02782](https://arxiv.org/abs/1711.02782) find
  13. S. Gray, A. Radford, and D. P. Kingma, “Block-sparse gpu kernels,” https://blog.openai.com/block-sparse-gpu-kernels/, 2017. ↗
  14. N. Kalchbrenner, E. Elsen, K. Simonyan, S. Noury, N. Casagrande, E. Lockhart, F. Stimberg, A. van den Oord, S. Dieleman, and K. Kavukcuoglu, “Efficient Neural Audio Synthesis,” in Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässan, Stockholm, Sweden, Ju… find
  15. Z. Yao, S. Cao, W. Xiao, C. Zhang, and L. Nie, “Balanced sparsity for efficient DNN inference on GPU,” in The Thirty-Third AAAI Conference on Artificial Intelligence, AAAI 2019, The Thirty-First Innovative Applications of Artificial Intelligence Conference, IAAI 2019, The Ninth AAAI Symposium on Edu… find
  16. E. Elsen, M. Dukhan, T. Gale, and K. Simonyan, “Fast Sparse Convnets,” CoRR, vol. abs/1911.09723, 2019. — [arXiv:1911.09723](https://arxiv.org/abs/1911.09723) find
  17. T. Gale, E. Elsen, and S. Hooker, “The State of Sparsity in Deep Neural Networks,” CoRR, vol. abs/1902.09574, 2019. — [arXiv:1902.09574](https://arxiv.org/abs/1902.09574) find
  18. O. Russakovsky, J. Deng, H. Su, J. Krause, S. Satheesh, S. Ma, Z. Huang, A. Karpathy, A. Khosla, M. S. Bernstein, A. C. Berg, and F. Li, “Imagenet large scale visual recognition challenge,” Int. J. Comput. Vis., vol. 115, no. 3, pp. 211–252, 2015.
  19. O. Bojar, C. Buck, C. Federmann, B. Haddow, P. Koehn, J. Leveling, C. Monz, P. Pecina, M. Post, H. Saint-Amand, R. Soricut, L. Specia, and A. Tamchyna, “Findings of the 2014 workshop on statistical machine translation,” in Proceedings of the Ninth Workshop on Statistical Machine Translation. Baltimo…
  20. T. A. Davis and Y. Hu, “The university of florida sparse matrix collection,” ACM Trans. Math. Softw., vol. 38, no. 1, 2011. find
  21. P. Micikevicius, “GPU Performance Analysis and Optimization,” http://on-demand.gputechconf.com/gtc/2012/presentations/S0514-GTC2012-GPU-Performance-Analysis.pdf, 2012. ↗
  22. I. Nisa, A. Sukumaran-Rajam, S. E. Kurt, C. Hong, and P. Sadayappan, “Sampled dense matrix multiplication for high-performance machine learning,” in 25th IEEE International Conference on High Performance Computing, HiPC 2018, Bengaluru, India, December 17-20, 2018. IEEE, 2018, pp. 32–41. find
  23. C. Hong, A. Sukumaran-Rajam, I. Nisa, K. Singh, and P. Sadayappan, “Adaptive sparse tiling for sparse matrix multiplication,” in Proceedings of the 24th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP 2019, Washington, DC, USA, February 16-20, 2019, J. K. Hollingswort… find
  24. M. Naumov, L. S. Chien, P. Vandermersch, and U. Kapasi, “cuSPARSE Library,” https://www.nvidia.com/content/GTC-2010/pdfs/2070_GTC2010.pdf, 2010. ↗
  25. H. Anzt, S. Tomov, and J. J. Dongarra, “Accelerating the LOBPCG method on gpus using a blocked sparse matrix vector product,” in Proceedings of the Symposium on High Performance Computing, HPC 2015, part of the 2015 Spring Simulation Multiconference, SpringSim ’15, Alexandria, VA, USA, April 12-15,… find
  26. C. Yang, A. Buluç, and J. D. Owens, “Design Principles for Sparse Matrix Multiplication on the GPU,” in Euro-Par 2018: Parallel Processing - 24th International Conference on Parallel and Distributed Computing, Turin, Italy, August 27-31, 2018, Proceedings, 2018, pp. 672–687. find
  27. S. Narang, “DeepBench: Benchmarking Deep Learning Operations on Different Hardware,” https://github.com/baidu-research/DeepBench, 2016. ↗
  28. N. Parmar, A. Vaswani, J. Uszkoreit, L. Kaiser, N. Shazeer, A. Ku, and D. Tran, “Image Transformer,” in Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässan, Stockholm, Sweden, July 10-15, 2018, 2018. find
  29. M. Tan and Q. V. Le, “Efficientnet: Rethinking Model Scaling for Convolutional Neural Networks,” in Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, 2019.
  30. J. Luitjens, “CUDA Pro Tip: Increase Performance with Vectorized Memory Access,” https://devblogs.nvidia.com/cuda-pro-tip-increase-performance-with-vectorized-memory-access/, 2013. ↗
  31. Nvidia, “CUDA C++ Programming Guide,” https://docs.nvidia.com/cuda/cuda-c-programming-guide/, 2019. ↗
  32. D. Merrill and M. Garland, “Merge-Based Parallel Sparse Matrix-Vector Multiplication,” in Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, SC 2016, Salt Lake City, UT, USA, November 13-18, 2016, 2016. find
  33. A. Kerr, D. Merrill, J. Demouth, and J. Tran, “CUTLASS: Fast Linear Algebra in CUDA C++,” https://devblogs.nvidia.com/cutlass-linear-algebra-cuda/, 2017. ↗
  34. S. Pai, “How the Fermi Thread Block Scheduler Works,” https://www.cs.rochester.edu/~sree/fermi-tbs/fermi-tbs.html, 2014. ↗
  35. C. D. Polychronopoulos and D. J. Kuck, “Guided self-scheduling: A practical scheduling scheme for parallel supercomputers,” IEEE Trans. Computers, vol. 36, no. 12, pp. 1425–1439, 1987. find
  36. F. Zhu, J. Pool, M. Andersch, J. Appleyard, and F. Xie, “Sparse Persistent RNNs: Squeezing Large Recurrent Networks On-Chip,” in 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 - May 3, 2018, Conference Track Proceedings, 2018. find
  37. P. Micikevicius, S. Narang, J. Alben, G. F. Diamos, E. Elsen, D. García, B. Ginsburg, M. Houston, O. Kuchaiev, G. Venkatesh, and H. Wu, “Mixed precision training,” in 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 - May 3, 2018, Conference Track… find
  38. A. Adinets, “Adaptive parallel computation with cuda dynamic parallelism,” https://devblogs.nvidia.com/introduction-cuda-dynamic-parallelism/, 2014. ↗
  39. S. Chetlur, C. Woolley, P. Vandermersch, J. Cohen, J. Tran, B. Catanzaro, and E. Shelhamer, “cudnn: Efficient primitives for deep learning,” CoRR, vol. abs/1410.0759, 2014.
  40. K. Cho, B. van Merrienboer, Ç. Gülçehre, D. Bahdanau, F. Bougares, H. Schwenk, and Y. Bengio, “Learning phrase representations using RNN encoder-decoder for statistical machine translation,” in Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing, EMNLP 2014, Octobe…
  41. S. Hochreiter and J. Schmidhuber, “Long short-term memory,” Neural Computation, vol. 9, no. 8, pp. 1735–1780, 1997. find
  42. Z. Dai, Z. Yang, Y. Yang, J. G. Carbonell, Q. V. Le, and R. Salakhutdinov, “Transformer-xl: Attentive language models beyond a fixed-length context,” in Proceedings of the 57th Conference of the Association for Computational Linguistics, ACL 2019, Florence, Italy, July 28- August 2, 2019, Volume 1:… find
  43. A. G. Howard, M. Zhu, B. Chen, D. Kalenichenko, W. Wang, T. Weyand, M. Andreetto, and H. Adam, “Mobilenets: Efficient convolutional neural networks for mobile vision applications,” CoRR, vol. abs/1704.04861, 2017.
  44. M. Sandler, A. G. Howard, M. Zhu, A. Zhmoginov, and L. Chen, “Mobilenetv2: Inverted residuals and linear bottlenecks,” in 2018 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2018, Salt Lake City, UT, USA, June 18-22, 2018. IEEE Computer Society, 2018, pp. 4510–4520. find
  45. A. Howard, R. Pang, H. Adam, Q. V. Le, M. Sandler, B. Chen, W. Wang, L. Chen, M. Tan, G. Chu, V. Vasudevan, and Y. Zhu, “Searching for mobilenetv3,” in 2019 IEEE/CVF International Conference on Computer Vision, ICCV 2019, Seoul, Korea (South), October 27 - November 2, 2019. IEEE, 2019, pp. 1314–1324… find
  46. S. Ioffe and C. Szegedy, “Batch normalization: Accelerating deep network training by reducing internal covariate shift,” in Proceedings of the 32nd International Conference on Machine Learning, ICML 2015, Lille, France, 6-11 July 2015, ser. JMLR Workshop and Conference Proceedings, F. R. Bach and D.… find
  47. F. Vázquez, G. O. López, J. Fernández, I. García, and E. M. Garzón, “Fast sparse matrix matrix product based on ELLR-T and GPU computing,” in 10th IEEE International Symposium on Parallel and Distributed Processing with Applications, ISPA 2012, Leganes, Madrid, Spain, July 10-13, 2012. IEEE Computer… find
  48. F. Vázquez, J. Fernández, and E. M. Garzón, “A new approach for sparse matrix vector product on NVIDIA gpus,” Concurr. Comput. Pract. Exp., vol. 23, no. 8, pp. 815–826, 2011. find
  49. H. Anzt, S. Tomov, and J. J. Dongarra, “Implementing a sparse matrix vector product for the sell-c / sell-c-σ formats on nvidia gpus,” 2014. find
  50. J. Park, S. R. Li, W. Wen, P. T. P. Tang, H. Li, Y. Chen, and P. Dubey, “Faster cnns with direct sparse convolutions and guided pruning,” in 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings, 2017. find
  51. S. R. Li, J. Park, and P. T. P. Tang, “Enabling sparse winograd convolution by native pruning,” CoRR, vol. abs/1702.08597, 2017. — [arXiv:1702.08597](https://arxiv.org/abs/1702.08597) find
  52. A. Lavin and S. Gray, “Fast algorithms for convolutional neural networks,” in 2016 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2016, Las Vegas, NV, USA, June 27-30, 2016. IEEE Computer Society, 2016, pp. 4013–4021.
  53. A. Buluç, J. T. Fineman, M. Frigo, J. R. Gilbert, and C. E. Leiserson, “Parallel sparse matrix-vector and matrix-transpose-vector multiplication using compressed sparse blocks,” in SPAA 2009: Proceedings of the 21st Annual ACM Symposium on Parallelism in Algorithms and Architectures, Calgary, Albert… find
  54. J. Li, J. Sun, and R. W. Vuduc, “Hicoo: hierarchical storage of sparse tensors,” in Proceedings of the International Conference for High Performance Computing, Networking, Storage, and Analysis, SC 2018, Dallas, TX, USA, November 11-16, 2018. IEEE / ACM, 2018, pp. 19:1–19:15. find
  55. Nvidia, “NVIDIA A100 tensor core gpu architecture,” https://www.nvidia.com/content/dam/en-zz/Solutions/Data-Center/nvidia-ampere-architecture-whitepaper.pdf, 2020. ↗

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/gale-2020-sparse-gpu-kernels-deep-learning/