Top

Published in:

2021 | OriginalPaper | Chapter

A Dynamic Parameter Tuning Method for High Performance SpMM

Authors : Bin Qi, Kazuhiko Komatsu, Masayuki Sato, Hiroaki Kobayashi

Published in: Parallel and Distributed Computing, Applications and Technologies

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Sparse matrix-matrix multiplication (SpMM) is a basic kernel that is used by many algorithms. Several researches focus on various optimizations for SpMM parallel execution. However, a division of a task for parallelization is not well considered yet. Generally, a matrix is equally divided into blocks for processes even though the sparsities of input matrices are different. The parameter that divides a task into multiple processes for parallelization is fixed. As a result, load imbalance among the processes occurs. To balance the loads among the processes, this paper proposes a dynamic parameter tuning method by analyzing the sparsities of input matrices. The experimental results show that the proposed method improves the performance of SpMM for examined matrices by up to 39.5% and 12.3% on average.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter A Relaxed Balanced Lock-Free Binary Search Tree

next chapter Data Caching Based Transfer Optimization in Large Scale Networks

Bell, N., Dalton, S., Olson, L.: Exposing fine-grained parallelism in algebraic multigrid methods. SIAM J. Sci. Comput. 34(4), C123–C152 (2012). https://doi.org/10.1137/110838844MathSciNetCrossRefMATH

Buluç, A., Fineman, J.T., Frigo, M., Gilbert, J.R., Leiserson, C.E.: Parallel sparse matrix-vector and matrix-transpose-vector multiplication using compressed sparse blocks, pp. 233–244. SPAA 2009, Association for Computing Machinery, New York, NY, USA (2009). https://doi.org/10.1145/1583991.1584053

Chen, Y., Li, K., Yang, W., Xiao, G., Xie, X., Li, T.: Performance-aware model for sparse matrix-matrix multiplication on the sunway taihulight supercomputer. IEEE Trans. Parallel Distrib. Syst. 30(4), 923–938 (2019). https://doi.org/10.1109/TPDS.2018.2871189CrossRef

Dalton, S., Olson, L., Bell, N.: Optimizing sparse matrix–matrix multiplication for the gpu. ACM Trans. Math. Softw. 41(4) (2015). https://doi.org/10.1145/2699470

Davis, T.A., Hu, Y.: The university of florida sparse matrix collection. ACM Trans. Math. Softw. textbf38(1) (2011). https://doi.org/10.1145/2049662.2049663

Deveci, M., Trott, C., Rajamanickam, S.: Performance-portable sparse matrix-matrix multiplication for many-core architectures. In: 2017 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW), pp. 693–702 (2017). https://doi.org/10.1109/IPDPSW.2017.8

Forum, M.P.: MPI: a message-passing interface standard. Technical report, USA (1994)

Gilbert, J., Reinhardt, S., Shah, V.: A unified framework for numerical and combinatorial computing. Comput. Sci. Eng. 10, 20–25 (2008). https://doi.org/10.1109/MCSE.2008.45CrossRef

Gilbert, J.R., Moler, C., Schreiber, R.: Sparse matrices in matlab: design and implementation. SIAM J. Matrix Anal. Appl. 13(1), 333–356 (1992). https://doi.org/10.1137/0613024

10.

Graf, D., Labib, K., Uznański, P.: Hamming distance completeness and sparse matrix multiplication (2018)

11.

Green, O., Mccoll, R., Bader, D.: GPU merge path: a GPU merging algorithm (2014). https://doi.org/10.1145/2304576.2304621

12.

Gremse, F., Höfter, A., Schwen, L.O., Kiessling, F., Naumann, U.:Gpu-accelerated sparse matrix-matrix multiplication by iterative row merging. SIAM J. Sci. Comput. 37(1), C54–C71 (2015).https://doi.org/10.1137/130948811

13.

Komatsu, K., et al.: Performance evaluation of a vector supercomputer sx-aurora tsubasa. In: Proceedings of the International Conference for High Performance Computing, Networking, Storage, and Analysis. SC 2018, IEEE Press (2018)

14.

Li, J., Wang, F., Araki, T., Qiu, J.: Generalized sparse matrix-matrix multiplication for vector engines and graph applications. In: 2019 IEEE/ACM Workshop on Memory Centric High Performance Computing (MCHPC). pp. 33–42 (2019)

15.

Li, K., Yang, W., Li, K.: Performance analysis and optimization for SPMV on GPU using probabilistic modeling. IEEE Trans. Parallel and Distrib. Syst. 26(1), 196–205 (2015). https://doi.org/10.1109/TPDS.2014.2308221CrossRef

16.

Liu, W., Vinter, B.: A framework for general sparse matrix-matrix multiplication on GPUs and heterogeneous processors. J. Parallel Distrib. Comput. 85, 47–61 (2015). https://doi.org/10.1016/j.jpdc.2015.06.010

17.

Matam, K., Krishna Bharadwaj Indarapu, S.R., Kothapalli, K.: Sparse matrix-matrix multiplication on modern architectures. In: 2012 19th International Conference on High Performance Computing, pp. 1–10 (2012). https://doi.org/10.1109/HiPC.2012.6507483

18.

Nagasaka, Y., Nukada, A., Matsuoka, S.: High-performance and memory-saving sparse general matrix-matrix multiplication for NVIDIA pascal GPU. In: 2017 46th International Conference on Parallel Processing (ICPP), pp. 101–110 (2017). https://doi.org/10.1109/ICPP.2017.19

19.

Vingelmann, P., Fitzek, F.H.: NVIDIA Cuda, release: 10.2.89 (2020). https://developer.nvidia.com/cuda-toolkit

20.

Ordonez, C., Zhang, Y., Cabrera, W.: The gamma matrix to summarize dense and sparse data sets for big data analytics. IEEE Trans. Knowl. Data Eng. 28(7), 1905–1918 (2016). https://doi.org/10.1109/TKDE.2016.2545664CrossRef

21.

Parger, M., Winter, M., Mlakar, D., Steinberger, M.: Speck: accelerating GPU sparse matrix-matrix multiplication through lightweight analysis. In: Proceedings of the 25th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, pp. 362–375. PPoPP 2020, Association for Computing Machinery, New York, NY, USA (2020). https://doi.org/10.1145/3332466.3374521

22.

Satish, N., Harris, M., Garland, M.: Designing efficient sorting algorithms for manycore GPUs. In: 2009 IEEE International Symposium on Parallel Distributed Processing, pp. 1–10 (2009). https://doi.org/10.1109/IPDPS.2009.5161005

23.

Schaub, M.T., Trefois, M., van Dooren, P., Delvenne, J.C.: Sparse matrix factorizations for fast linear solvers with application to laplacian systems. SIAM J. Matrix Anal. Appl. 38(2), 505–529 (2017). https://doi.org/10.1137/16m1077398

24.

Xie, Z., Tan, G., Liu, W., Sun, N.: IA-SPGEMM: an input-aware auto-tuning framework for parallel sparse matrix-matrix multiplication. In: Proceedings of the ACM International Conference on Supercomputing, pp. 94–105. ICS 2019, Association for Computing Machinery, New York, NY, USA (2019). https://doi.org/10.1145/3330345.3330354

25.

Yang, W., Li, K., Mo, Z., Li, K.: Performance optimization using partitioned SPMV on GPUs and multicore CPUs. IEEE Trans. Comput. 64(9), 2623–2636 (2015). https://doi.org/10.1109/TC.2014.2366731MathSciNetCrossRefMATH

Title: A Dynamic Parameter Tuning Method for High Performance SpMM
Authors: Bin Qi
Kazuhiko Komatsu
Masayuki Sato
Hiroaki Kobayashi
Publisher: Springer International Publishing
Book: Parallel and Distributed Computing, Applications and Technologies
Print ISBN: 978-3-030-69243-8

Electronic ISBN: 978-3-030-69244-5

Copyright Year: 2021
DOI: https://doi.org/10.1007/978-3-030-69244-5_28

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner