Efficient Implementation of Matrix-Matrix Multiplication using SIMD and OpenMP Models on CPU Platforms

Akoushideh, Alireza; Shahbahrami, Asadollah

doi:10.48301/jear.2024.421627.1005

Efficient Implementation of Matrix-Matrix Multiplication using SIMD and OpenMP Models on CPU Platforms

Document Type : Original Article

Authors

Alireza Akoushideh ¹

Asadollah Shahbahrami ²

¹ Department of Electrical and Computer Engineering, Technical and Vocational University (TVU), Tehran, Iran.

² Department of Computer Engineering, Guilan University, Rasht, Iran.

10.48301/jear.2024.421627.1005

Abstract

Modern CPUs and GPUs come with multiple processing units, enabling the parallel execution of tasks, which enhances overall system performance. Various parallel programming models have been developed to take full advantage of this parallelism. For computation-heavy applications, such as matrix-matrix multiplication—a key operation in linear algebra frequently applied in scientific simulations and multimedia processing—achieving efficient implementation is essential to fully utilize hardware resources. This paper explores optimized implementations of matrix-matrix multiplication using several parallel programming techniques: SIMD, OpenMP, a Hybrid OpenMP-SIMD model, and OpenCL. Our experimental results highlight the effectiveness of these approaches, with observed speedups of up to 6.5x using SIMD, 3.2x with OpenMP, 16.7x via hybrid OpenMP-SIMD, and a notable 32x speedup with OpenCL, compared to a highly optimized serial baseline. These results demonstrate significant performance improvements when leveraging parallelism for matrix-matrix multiplication. This paper focuses on efficiently implementing matrix-matrix multiplication using popular parallel programming models: SIMD, OpenMP, Hybrid OpenMP-SIMD, and OpenCL. Our experimental results demonstrate the effectiveness of our implementations for different matrix sizes. Compared to an optimized serial implementation, we achieve significant speedups of up to 6.5x for SIMD, 3.2x for OpenMP, 16.7x for hybrid OpenMP-SIMD, and an impressive 32x for OpenCL implementations.

Keywords

Matrix-Matrix Multiplication

Parallel programming

SIMD

OpenMP

OpenCL

Subjects

Computer Engineering

[1] Ouerhani, Y., Jridi, M., & AlFalou, A. (2010, 1-2 July 2010). Fast face recognition approach using a graphical processing unit “GPU”. IEEE International Conference on Imaging Systems and Techniques, https://doi.org/10.1109/IST.2010.5548545

[2] Xu, H., Zhu, X., Wang, Q., & Liu, J. (2022, 18-20 Dec. 2022). Efficiently Executing Sparse Matrix-Matrix Multiplication on General Purpose Digital Single Processor. 2022 IEEE 24th Int Conf on High Performance Computing & Communications; 8th Int Conf on Data Science & Systems; 20th Int Conf on Smart City; 8th Int Conf on Dependability in Sensor, Cloud & Big Data Systems & Application (HPCC/DSS/SmartCity/DependSys), https://doi.org/10.1109/HPCC-DSS-SmartCity-DependSys57074.2022.00035

[3] Ghasempour Balagafshe, R., Akoushideh, A., & Shahbahrami, A. (2022). Matrix-matrix multiplication on graphics processing unit platform using tiling technique. Indonesian Journal of Electrical Engineering and Computer Science, 28(2), 8. https://doi.org/10.11591/ijeecs.v28.i2.pp1012-1019

[4] Bustio-Martínez, L., Cumplido, R., Letras, M., Hernández-León, R., Feregrino-Uribe, C., & Hernández-Palancar, J. (2021). FPGA/GPU-based Acceleration for Frequent Itemsets Mining: A Comprehensive Review. ACM Comput. Surv., 54(9), Article 179. https://doi.org/10.1145/3472289

[5] Jo, Y.-Y., Kim, S.-W., & Bae, D.-H. (2014). GPU-based matrix multiplication methods for social networks analysis Proceedings of the 2014 Conference on Research in Adaptive and Convergent Systems, Towson, Maryland.https://doi.org/10.1145/2663761.2664192

[6] Fawzi, A., Balog, M., Huang, A., Hubert, T., Romera-Paredes, B., Barekatain, M., Novikov, A., R. Ruiz, F. J., Schrittwieser, J., Swirszcz, G., Silver, D., Hassabis, D., & Kohli, P. (2022). Discovering faster matrix multiplication algorithms with reinforcement learning. Nature, 610(7930), 47-53. https://doi.org/10.1038/s41586-022-05172-4

[7] Akoushideh, A., Shahbahrami, A., & Joe Afshany, A. (2024). Parallelization of license plate localization on GPU platform. Multimedia Tools and Applications, 83(1), 2551-2564. https://doi.org/10.1007/s11042-023-15656-8

[8] Kelefouras, V., Kritikakou, A., Mporas, I., & Kolonias, V. (2016). A high-performance matrix–matrix multiplication methodology for CPU and GPU architectures. The Journal of Supercomputing, 72(3), 804-844. https://doi.org/10.1007/s11227-015-1613-7

[9] Hassan, S. A., Hemeida, A. M., & Mahmoud, M. M. M. (2016). Performance Evaluation of Matrix-Matrix Multiplications Using Intel's Advanced Vector Extensions (AVX). Microprocess. Microsystems, 47, 369-374. https://doi.org/10.1016/j.micpro.2016.10.002

[10] Kelefouras, V., Kritikakou, A., & Goutis, C. (2014). A Matrix–Matrix Multiplication methodology for single/multi-core architectures using SIMD. The Journal of Supercomputing, 68(3), 1418-1440. https://doi.org/10.1007/s11227-014-1098-9

[11] Gautier, T., & Lima, J. V. F. (2021, 2021-11-19). Evaluation of two topology-aware heuristics on level-3 BLAS library for multi-GPU platforms. PAW-ATM 2021 - 4th Annual Parallel Applications Workshop, Alternatives To MPI+X, Saint Louis, United States. https://hal.inria.fr/hal-03363275

[12] Aroon, M. A., Ismail, A. F., Matsuura, T., & Montazer-Rahmati, M. M. (2010). Performance studies of mixed matrix membranes for gas separation: A review. Separation and Purification Technology, 75(3), 229-242. https://doi.org/https://doi.org/10.1016/j.seppur.2010.08.023

[13] Salim, M., Akkirman, A. O., Hidayetoglu, M., & Gurel, L. (2015, 1-4 July 2015). Comparative benchmarking: matrix multiplication on a multicore coprocessor and a GPU. 2015 Computational Electromagnetics International Workshop (CEM), https://doi.org/10.1109/CEM.2015.7237429

[14] Pal, S., Beaumont, J., Park, D. H., Amarnath, A., Feng, S., Chakrabarti, C., Kim, H. S., Blaauw, D., Mudge, T., & Dreslinski, R. (2018, 24-28 Feb. 2018). OuterSPACE: An Outer Product Based Sparse Matrix Multiplication Accelerator. 2018 IEEE International Symposium on High Performance Computer Architecture (HPCA), https://doi.org/10.1109/HPCA.2018.00067

[15] Goto, K., & Geijn, R. A. v. d. (2008). Anatomy of high-performance matrix multiplication. ACM Trans. Math. Softw., 34(3), Article 12. https://doi.org/10.1145/1356052.1356053

[16] Jeong, H., Kim, S., Lee, W., & Myung, S.-H. (2012). Performance of SSE and AVX Instruction Sets. ArXiv. https://doi.org/10.48550/arXiv.1211.0820

[17] Oo, N. Z., & Chaikan, P. (2022, 4-7 May 2022). Fast Blockwise Matrix-Matrix Multiplication Using AVX and Prefetching on Shared Memory. 2022 13th Asian Control Conference (ASCC), https://doi.org/10.23919/ASCC56756.2022.9828222

[18] Chen, X., Gao, Y., Shang, H., Li, F., Xu, Z., Liu, X., & Chen, D. (2022). Increasing the Efficiency of Massively Parallel Sparse Matrix-Matrix Multiplication in First-Principles Calculation on the New-Generation Sunway Supercomputer. IEEE Transactions on Parallel and Distributed Systems, 33(12), 4752-4766. https://doi.org/10.1109/TPDS.2022.3202518

[19] Keatkaew, T., Woradit, K., & Champrasert, P. (2022, 5-8 July 2022). Hybrid Vectorization and Parallelization for Matrix-Matrix Multiplication on Multi-core Platform. 2022 37th International Technical Conference on Circuits/Systems, Computers and Communications (ITC-CSCC), https://doi.org/10.1109/ITC-CSCC55581.2022.9894915

[20] Intel® oneAPI Math Kernel Library. Microsoft. https://www.intel.com

[21] Corporation, I. Intel® 64 and IA-32 Architectures Optimization. Intel Corporation. https://www.intel.com/

[22] Chapman, B., Jost, G., & Pas, R. v. d. (2007). Using OpenMP; Portable Shared Memory Parallel Programming. The MIT Press. https://mitpress.mit.edu/9780262533027/using-openmp/

[23] Stone, J. E., Gohara, D., & Shi, G. (2010). OpenCL: A Parallel Programming Standard for Heterogeneous Computing Systems. Comput Sci Eng, 12(3), 66-72. https://doi.org/10.1109/mcse.2010.69

[24] Balagafshe, R. G., Akoushideh, A., & Shahbahrami, A. (2022). Matrix-matrix multiplication on graphics processing unit platform using tiling technique. Indonesian Journal of Electrical Engineering and Computer Science, 28(2), 1012-1019. https://doi.org/https://doi.org/10.11591/ijeecs.v28.i2.pp1012-1019

[25] Bogosavljević, I. (2021). Memory Access Pattern and Performance: the Example of Matrix Multiplication. Johnny’s Software Lab. Retrieved May 20 from https://johnnysswlab.com/memory-access-pattern-and-performance-the-example-of-matrix-multiplication/

[26] Memeti, S., Li, L., Pllana, S., Kołodziej, J., & Kessler, C. (2017). Benchmarking OpenCL, OpenACC, OpenMP, and CUDA: Programming Productivity, Performance, and Energy Consumption Proceedings of the 2017 Workshop on Adaptive Resource Management and Scheduling for Cloud Computing, Washington, DC, USA.https://doi.org/10.1145/3110355.3110356

[27] He, L., Shen, W., Li, Y., Shi, A., & Zhao, D. (2010, 28-31 May 2010). MPI+OpenMP Implementation and Results Analysis of Matrix Multiplication Based on Rowwise and Columnwise Block-Striped Decomposition of the Matrices. Third International Joint Conference on Computational Science and Optimization, https://doi.org/10.1109/CSO.2010.123

[28] Li, J., Ranka, S., & Sahni, S. (2013). In GPU matrix multiplication. Chapman-Hall/CRC Press. https://doi.org/10.1007/978-1-4613-9692-5_3

[29] Beckingsale, D. A. (2015). Towards Scalable Adaptive Mesh Refinement on Future Parallel Architectures [Doctor of Philosophy, The University of Warwick]. https://webcat.warwick.ac.uk/record=b2827209~S1

[30] Fang, J., Huang, C., Tang, T., & Wang, Z. (2020). Parallel programming models for heterogeneous many-cores: a comprehensive survey. CCF Transactions on High Performance Computing, 2(4), 382-400. https://doi.org/10.1007/s42514-020-00039-4

[31] OpenMP 5.1 Specification. (2021). The OpenMP ARB (Architecture Review Boards). https://www.openmp.org/specifications/

[32] Bertoni, C., Kwack, J., Applencourt, T., Ghadar, Y., Homerding, B., Knight, C., Videau, B., Zheng, H., Morozov, V., & Parker, S. (2020, 18-22 May 2020). Performance Portability Evaluation of OpenCL Benchmarks across Intel and NVIDIA Platforms. 2020 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW), https://doi.org/10.1109/IPDPSW50202.2020.00067

[33] Banger, R., Bhattacharyya, B., & Bhattacharyya, K. (2013). OpenCL Programming by Example. Packt Publishing. https://books.google.com/books?id=1O80ngEACAAJ

[34] Waidyasooriya, H. M., Hariyama, M., & Uchiyama, K. (2017). Design of FPGA-Based Computing Systems with OpenCL. Springer. https://doi.org/10.1007/978-3-319-68161-0

[35] Matsumoto, K., Nakasato, N., & Sedukhin, S. G. (2012, 10-16 Nov. 2012). Performance Tuning of Matrix Multiplication in OpenCL on Different GPUs and CPUs. 2012 SC Companion: High Performance Computing, Networking Storage and Analysis, https://doi.org/10.1109/SC.Companion.2012.59

[36] Cleverson, L., Ledur, D., Zeve, C., & Anjos, D. (2013). Comparative Analysis of OpenACC, OpenMP and CUDA using Sequential and Parallel Algorithms 11th Workshop on Parallel and Distributed Processing (WSPPD), UFRGS (Porto Alegre).

[37] Rizwan, M., Jung, E., Park, Y., Choi, J., & Kim, Y. (2022, 5-8 Dec. 2022). Optimization of Matrix-Matrix Multiplication Algorithm for Matrix-Panel Multiplication on Intel KNL. 2022 IEEE/ACS 19th International Conference on Computer Systems and Applications (AICCSA), https://doi.org/10.1109/AICCSA56895.2022.10017947

[38] General Matrix Multiply - Intel® SDK for OpenCL™ Applications. Intel. https://software.intel.com

[39] Mittal, S., & Vetter, J. S. (2015). A Survey of CPU-GPU Heterogeneous Computing Techniques. ACM Comput. Surv., 47(4), Article 69. https://doi.org/10.1145/2788396