Research Project: Sparcity: Seyrek Hesaplama için Bir Optimizasyon ve Ortak Tasarım Çerçevesi
Loading...
Contributors
Funders
ID
TB.00602
Authors
Erten, Didem Unat
Faculty Member
Publications
Bringing order to sparsity: a sparse matrix reordering study on multicore CPUs
(Association for Computing Machinery, Inc, 2023) Düzakın, Emre; Erten, Didem Unat; Torun, Tuğba; Trotter, James D.; Ekmekçibaşı, Sinan; Langguth, Johannes; Ilic, Aleksandar; Department of Computer Engineering; Graduate School of Sciences and Engineering; Yes; College of Engineering; GRADUATE SCHOOL OF SCIENCES AND ENGINEERING
Many real-world computations involve sparse data structures in the form of sparse matrices. A common strategy for optimizing sparse matrix operations is to reorder a matrix to improve data locality. However, it's not always clear whether reordering will provide benefits over the unordered matrix, as its effectiveness depends on several factors, such as structural features of the matrix, the reordering algorithm and the hardware that is used. This paper aims to establish the relationship between matrix reordering algorithms and the performance of sparse matrix operations. We thoroughly evaluate six different matrix reordering algorithms on 490 matrices across eight multicore architectures, focusing on the commonly used sparse matrix-vector multiplication (SpMV) kernel. We find that reordering based on graph partitioning provides better SpMV performance than the alternatives for a large majority of matrices, and that the resulting performance is explained through a combination of data locality and load balancing concerns. © 2023 Owner/Author(s).
