Original Information
Title: NUMA-Aware Optimization of Sparse Matrix-Vector Multiplication on ARMv8-based Many-Core Architectures
Published Conference: The 17th Annual IFIP International Conference on Network and Parallel Computing (CCF Class C Conference)
Author List
1) Yuxiaosong, China University of Petroleum (Beijing), School of Information Science and Engineering, Major in Computer Science and Technology, Graduate Class of 2019 2) Ma Huihui, China University of Petroleum (Beijing), School of Information Science and Engineering, Major in Computer Science and Technology, Graduate Class of 2019 3) Qu Zhengyu, China University of Petroleum (Beijing), School of Information Science and Engineering, Major in Computer Science and Technology, Graduate Class of 2019 4) Fang Jianbin, National University of Defense Technology, College of Computer, Software Research Institute 5) Liu Weifeng, China University of Petroleum (Beijing), School of Information Science and Engineering, Department of Computer Science
Abstract
Sparse Matrix-Vector Multiplication (SpMV) is one of the core programs in scientific and engineering computing, and its performance often has a significant impact on sparse iterative solvers. In this paper, we propose a NUMA-Aware optimization technique for SpMV. We first use hypergraph partitioning to segment and rearrange the input sparse matrix to achieve better cache locality, and then optimize the algorithm for NUMA architecture, including blocking and binding NUMA node techniques, which can utilize bandwidth more effectively and achieve better performance. Tests on the ARMv8-based Phytium 2000+ 64-core processor show that our NUMA-Aware method achieves an average speedup of 1.76x and a maximum speedup of 2.88x compared to OpenMP parallel SpMV.
Background and Motivation
Sparse Matrix-Vector Multiplication (SpMV) is the operator that multiplies a sparse matrix A with a dense vector x to obtain a dense vector y. It is one of the Level 2 Basic Linear Algebra Subprograms (BLAS), and its performance often has a significant impact on sparse iterative solvers. Since the algorithms implemented for SpMV typically have a low ratio of floating-point computations to memory accesses, and the memory access patterns are very irregular, it is a typical memory and latency-bound algorithm. Modern multi-core and many-core processors usually use NUMA architecture to achieve better scalability, yet many current SpMV optimization efforts lack the utilization of NUMA features in modern processors such as ARM CPUs. To improve the performance of SpMV on modern processors, we develop a NUMA-supported SpMV method in this work.
Design and Implementation
In our algorithm, we first need to partition the hypergraph representation of the sparse matrix. The figure below illustrates the difference before and after matrix reordering using hypergraph partitioning, showing that some non-zero elements of the matrix have moved to the diagonal blocks. The number of non-zero elements in the off-diagonal blocks of the matrix before hypergraph partitioning (a) is 48, but after partitioning (c), the number reduces to 38.
(a) The original sparse matrix A is 16×16, (b) The row network representation of the hypergraph H of matrix A and the partitioning of H, (c) The reordering of matrix A according to the hypergraph partitioning. It can be seen that the non-zero entries in the reordered matrix are aggregated into the diagonal blocks, indicating that the number of connections between the four partitions has decreased. After reordering, the matrix is partitioned into submatrices, i.e., row blocks, and the vector is also partitioned into subvectors. We then use the memory allocation API in libnuma-2.0 to allocate memory for submatrices and subvectors on each NUMA node. The pseudo-code of the algorithm is listed in the figure below. In the algorithm, start and end (line 3) represent the starting and ending positions of each thread’s rows, Xpos and remainder (line 6) are used to find the vector x needed for local computation. When allocating matrices and vectors, our algorithm creates Pthread threads and binds them to the corresponding NUMA nodes (lines 10-12), allowing each thread to compute a row of the submatrix allocated on the same NUMA node (lines 1-9). Since the memory on the node only stores a part of the complete vector, threads will simultaneously access both local and remote subvectors.
NUMA-Aware SpMV Pseudo Code
Experimental Results
We tested OpenMP SpMV and NUMA-Aware SpMV on the ARMv8-based Phytium 2000+ 64-core processor and compared them. The experimental dataset consists of sparse matrices from the SuiteSparse Matrix Collection. The experimental results indicate that hypergraph partitioning has a significant impact on the performance of NUMA-Aware SpMV, while it has little effect on OpenMP SpMV. Furthermore, for the same matrix, the number of hypergraph partitions can lead to significantly different performances; the more non-zero elements in the diagonal blocks after hypergraph partitioning, the better the performance.
Performance comparison of OpenMP SpMV (left) and NUMA-Aware SpMV (right) on Phytium 2000+. In each subplot, the x-axis and y-axis represent the number of threads and the number of partitions, respectively. The heatmap values are expressed in single precision GFlop/s.
The above figure shows the performance comparison of OpenMP SpMV and NUMA-Aware SpMV for 15 test matrices. Compared to OpenMP SpMV, our NUMA-Aware SpMV achieves an average speedup of 1.76x and a maximum speedup of 2.88x (matrix M6). Both regular and irregular matrices achieved significant speedups. The average speedup for irregular matrices is 1.91x, while for regular matrices, it is 1.59x.
About the Author
Liu Weifeng, Professor
———————————————————-
Professor at the School of Information Science and Engineering, China University of Petroleum (Beijing), Dean, EU Marie Curie Scholar. He obtained his Bachelor’s and Master’s degrees from the Computer Department of China University of Petroleum (Beijing) in 2002 and 2006, respectively. From 2006 to 2012, he worked at the China Petroleum Exploration and Development Research Institute as an Assistant Engineer, Engineer, and Senior Researcher, mainly focusing on high-performance algorithms for oil geophysical exploration. He received his Ph.D. in Computational Science from the University of Copenhagen, Denmark, in 2016, primarily researching high-performance sparse linear algebra subprograms. His main research interests include numerical linear algebra and parallel computing, with a particular focus on data structures, parallel algorithms, and software for sparse matrices. His research work has been published in major international conferences and journals such as SC, ICS, PPoPP, ASPLOS, IPDPS, JPDC, FGCS, and Parco. He is also a reviewer for several important international journals such as TPDS, SISC, and TKDE, and a program committee member for major international conferences such as SC, ICS, and ICPP. He is a senior member of IEEE and a member of CCF, ACM, and SIAM.
Contact:
Scan QR Code ｜ Follow Us
Images in the text are sourced from the original text. If there is any infringement, please contact us to delete.