SRB-ELL: A Vector-Friendly Sparse Matrix Format for SpMV on Scratchpad-Augmented Architectures
Source abstract
Abstract
Sparse Matrix–Vector Multiplication (SpMV) is a critical computational kernel in high-performance computing (HPC) and artificial intelligence (AI). However, its irregular memory access patterns lead to frequent cache misses on multi-level cache hierarchies, significantly degrading performance. Scratchpad memory (SPM), a software-managed, low-latency on-chip memory, offers improved data locality and control, making it a promising alternative for irregular workloads. To enhance SpMV performance, we propose a vectorized execution framework targeting SPM-augmented processors. Recognizing the limitations of traditional formats for vectorization, we introduce Sorted-Row-Block ELL (SRB-ELL), a new matrix storage format derived from ELLPACK (ELL). SRB-ELL stores only non-zero elements, partitions the matrix into row blocks, and sorts them by block size to improve load balance and SIMD efficiency. We implement and evaluate SRB-ELL on a custom processor architecture with integrated SPM using the gem5 simulator. Experimental results show that, compared to vectorized CSR-based SpMV, the SRB-ELL design achieves up to 1.48× speedup and an average of 1.19×.
Source: crossref · Quality: baseline
Research context
OpenAlex topics: Parallel Computing and Optimization Techniques · Advanced Data Storage Technologies · Distributed and Parallel Computing Systems
SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.
Affiliations
College of Computer Science and Technology, National University of Defense Technology, Changsha 410073, China
School of Computer, Electronics and Information, Guangxi University, Nanning 530004, China
References (43)
Show source-provided references
1. Asanović, K. (1998). Vector Microprocessors. [Ph.D. Dissertation, University of California].
2. Espasa, R., Valero, M., and Smith, J.E. (1998, January 13–17). Vector Architectures: Past, Present and Future. Proceedings of the 12th International Conference on Supercomputing (ICS), Melbourne, Australia. Available online: https://dl.acm.org/doi/10.1145/277830.277935.10.1145/277830.277935 ↗
3. AMD Corporation (2019). AMD64 Architecture Programmer’s Manual Volume 4: 128-Bit and 256-Bit Media Instructions, AMD.
4. Intel Corporation (2015). Intel 64 and IA-32 Architectures Software Developer’s Manual Volume 2A: Instruction Set Reference, Intel.
5. Hennessy, J.L., and Patterson, D.A. (2017). Computer Architecture, Sixth Edition: A Quantitative Approach, Morgan Kaufmann Publishers Inc.. [6th ed.].
6. Satish, N., Kim, C., Chhugani, J., Saito, H., Krishnaiyer, R., Smelyanskiy, M., Girkar, M., and Dubey, P. (2012, January 9–13). Can Traditional Programming Bridge the Ninja Performance Gap for Parallel Computing Applications?. Proceedings of the 39th Annual International Symposium on Computer Architecture (ISCA), Portland, OR, USA. Available online: http://dl.acm.org.recursos.biblioteca.upc.edu/citation.cfm?id=2337159.2337210.10.1109/ISCA.2012.6237038 ↗
7. Bramas, B., and Kus, P. (2018). Computing the Sparse Matrix Vector Product Using Block-Based Kernels without Zero Padding on Processors with AVX-512 Instructions. arXiv, Available online: http://arxiv.org/abs/1801.01134.10.7717/peerj-cs.151 ↗
8. Sunderam, V.S., van Albada, G.D., Sloot, P.M.A., and Dongarra, J.J. (2005). Vectorized Sparse Matrix Multiply for Compressed Row Storage Format. Computational Science–ICCS 2005, Springer.10.1007/b136575 ↗
9. Gilbert, J.R., Reinhardt, S., and Shah, V.B. (2006). High-Performance Graph Algorithms from Parallel Sparse Matrices. International Workshop on Applied Parallel Computing, Springer.
10. Greathouse, J.L., and Daga, M. (2014, January 16–21). Efficient Sparse Matrix-Vector Multiplication on GPUs Using the CSR Storage Format. Proceedings of the SC’14: Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, New Orleans, LA, USA.10.1109/SC.2014.68 ↗
11. Kepner, J., Alford, S., Gadepally, V., Jones, M., Milechin, L., Robinett, R., and Samsi, S. (2019, January 24–26). Sparse Deep Neural Network Graph Challenge. Proceedings of the 2019 IEEE High Performance Extreme Computing Conference (HPEC), Waltham, MA, USA.10.1109/HPEC.2019.8916336 ↗
12. Parashar, A., Rhu, M., Mukkara, A., Puglielli, A., Venkatesan, R., Khailany, B., Emer, J., Keckler, S., and Dally, W. (2017, January 24–28). SCNN: An Accelerator for Compressed-Sparse Convolutional Neural Networks. Proceedings of the 44th Annual International Symposium on Computer Architecture (ISCA), Toronto, ON, Canada.
13. Optimizing Multi-Grid Preconditioned Conjugate Gradient Method on Multi-Cores10.1109/TPDS.2024.3372473 ↗
14. Dense Linear Solver on Many-Core CPUs: Characterization and Optimization
15. The LINPACK Benchmark: Past, Present and Future10.1002/cpe.728 ↗
16. Dongarra, J., and Heroux, M.A. (2013). Toward a New Metric for Ranking High Performance Computing Systems, Sandia National Laboratories. Sandia Report SAND2013-4744.
17. Evgeniou, T., and Pontil, M. (1999). Support Vector Machines: Theory and Applications. Advanced Course on Artificial Intelligence, Springer.
18. Kepner, J., Aaltonen, P., Bader, D., Buluç, A., Franchetti, F., Gilbert, J., Hutchison, D., Kumar, M., Lumsdaine, A., and Meyerhenke, H. (2016, January 13–15). Mathematical Foundations of the GraphBLAS. Proceedings of the 2016 IEEE High Performance Extreme Computing Conference (HPEC), Waltham, MA, USA.10.1109/HPEC.2016.7761646 ↗
19. Leskovec, J., and Krevl, A. (2025, August 31). SNAP Datasets: Stanford Large Network Dataset Collection. Available online: http://snap.stanford.edu/data.
20. Liu, W., and Vinter, B. (2015, January 8–11). CSR5: An Efficient Storage Format for Cross-Platform Sparse Matrix-Vector Multiplication. Proceedings of the 29th ACM International Conference on Supercomputing (ICS), Newport Beach, CA, USA.10.1145/2751205.2751209 ↗
21. CSX: An Extended Compression Format for SpMV on Shared Memory Systems10.1145/2038037.1941587 ↗
22. yaSpMV: Yet Another SpMV Framework on GPUs10.1145/2692916.2555255 ↗
23. Cao, W., Yao, L., Li, Z., Wang, Y., and Wang, Z. (2010, January 22–24). Implementing Sparse Matrix-Vector Multiplication Using CUDA Based on a Hybrid Sparse Matrix Format. Proceedings of the 2010 International Conference on Computer Application and System Modeling (ICCASM), Taiyuan, China.
24. Buluç, A., Fineman, J.T., Frigo, M., Gilbert, J.R., and Leiserson, C.E. (2009, January 11–13). Parallel Sparse Matrix-Vector and Matrix-Transpose-Vector Multiplication Using Compressed Sparse Blocks. Proceedings of the Twenty-First Annual Symposium on Parallelism in Algorithms and Architectures (SPAA), Calgary, AB, Canada.10.1145/1583991.1584053 ↗
25. Eigen (2025, August 31). The Matrix Class, Dense Matrix and Array Manipulation. Available online: https://www.eigen.tuxfamily.org/dox/group__TutorialMatrixClass.html.
26. Kjolstad, F., Chou, S., Lugato, D., Kamil, S., and Amarasinghe, S. (November, January 30). TACO: A Tool to Generate Tensor Algebra Kernels. Proceedings of the 2017 32nd IEEE/ACM International Conference on Automated Software Engineering (ASE), Urbana, IL, USA.10.1109/ASE.2017.8115709 ↗
27. Pavon, J., Valdivieso, I.V., Barredo, A., Ramasubramanian, N., Hernandez, R., Badia, R.M., Ayguadé, E., and Labarta, J. (March, January 27). VIA: A Smart Scratchpad for Vector Units with Application to Sparse Matrix Computations. Proceedings of the 2021 IEEE International Symposium on High-Performance Computer Architecture (HPCA), Seoul, Republic of Korea.10.1109/HPCA51647.2021.00081 ↗
28. Lowe-Power, J., Ahmad, A.M., Akram, A., Alian, M., Amslinger, R., Andreozzi, M., Arvanitis, A., Bates, S., Bewick, G., and Black, G. (2020). The gem5 Simulator: Version 20.0+. arXiv, Available online: https://arxiv.org/abs/2007.03152.
29. Arm (2025, August 31). Arm Compiler for Linux: Scalable Vector Extension (SVE) Intrinsics Reference Guide. Available online: https://developer.arm.com/documentation/dht0002/.
30. Arm (2025, August 31). Arm Architecture Reference Manual: Armv8, for Armv8-A Architecture Profile. Available online: https://developer.arm.com/documentation/102476/latest/.
31. The ARM Scalable Vector Extension10.1109/MM.2017.35 ↗
32. Arm (2025, August 31). Arm Architecture Reference Manual Supplement, the Scalable Vector Extension (SVE), for Armv8-A; Version Beta. Available online: https://developer.arm.com/documentation/ddi0584/ag/.
33. Tang, W.T., Zhao, R., Lu, M., Liang, Y., Huynh, P.H., Li, X., and Goh, R.S.M. (2015, January 7–11). Optimizing and Autotuning Sparse Matrix-Vector Multiplication on Intel Xeon Phi. Proceedings of the 13th IEEE/ACM International Symposium on Code Generation and Optimization (CGO), San Francisco, CA, USA.10.1109/CGO.2015.7054194 ↗
34. Liu, X., Smelyanskiy, M., Chow, E., and Dubey, P. (2013, January 10–14). Efficient Sparse Matrix-Vector Multiplication on x86-based Manycore Processors. Proceedings of the 27th ACM International Conference on Supercomputing (ICS), Eugene, OR, USA.10.1145/2464996.2465013 ↗
35. Kreutzer, M., Hager, G., Wellein, G., Fehske, H., and Bishop, A.R. (2013). A Unified Sparse Matrix Data Format for Modern Processors with Wide SIMD Units. arXiv, Available online: http://arxiv.org/abs/1307.6209.
36. Anzt, H., Tomov, S., and Dongarra, J. (2014). Implementing a Sparse Matrix Vector Product for the SELL-C/SELL-C-σ Formats on NVIDIA GPUs, University of Tennessee. Technical Report ut-eecs-14-727.
37. Chen, L., Jiang, P., and Agrawal, G. (2016, January 12–18). Exploiting Recent SIMD Architectural Advances for Irregular Applications. Proceedings of the 14th International Symposium on Code Generation and Optimization (CGO), Barcelona, Spain.10.1145/2854038.2854046 ↗
38. Xie, B., Zhan, J., Liu, X., Gao, W., Jia, Z., He, X., and Zhang, L. (2018, January 24–28). CVR: Efficient Vectorization of SpMV on x86 Processors. Proceedings of the 2018 International Symposium on Code Generation and Optimization (CGO), Vienna, Austria.10.1145/3168818 ↗
39. Pinar, A., and Heath, M.T. (1999, January 14–19). Improving Performance of Sparse Matrix-Vector Multiplication. Proceedings of the 1999 ACM/IEEE Conference on Supercomputing, Portland, OR, USA.10.1145/331532.331562 ↗
40. Vuduc, R.W., and Moon, H.J. Fast Sparse Matrix-Vector Multiplication by Exploiting Variable Block Structure. Proceedings of the International Conference on High Performance Computing and Communications.
41. Cuthill, E., and McKee, J. (1969, January 26–28). Reducing the Bandwidth of Sparse Symmetric Matrices. Proceedings of the 1969 24th National Conference, New York, NY, USA.10.1145/800195.805928 ↗
42. (2025, August 31). SuiteSparse Matrix Collection. Available online: https://sparse.tamu.edu/.
43. The University of Florida Sparse Matrix Collection