Publication:
Bringing order to sparsity: a sparse matrix reordering study on multicore CPUs

dc.contributor.coauthorTrotter, James D.
dc.contributor.coauthorEkmekçibaşı, Sinan
dc.contributor.coauthorLangguth, Johannes
dc.contributor.coauthorIlic, Aleksandar
dc.contributor.departmentDepartment of Computer Engineering
dc.contributor.departmentGraduate School of Sciences and Engineering
dc.contributor.kuauthorDüzakın, Emre
dc.contributor.kuauthorErten, Didem Unat
dc.contributor.kuauthorTorun, Tuğba
dc.contributor.schoolcollegeinstituteCollege of Engineering
dc.contributor.schoolcollegeinstituteGRADUATE SCHOOL OF SCIENCES AND ENGINEERING
dc.date.accessioned2024-12-29T09:39:32Z
dc.date.issued2023
dc.description.abstractMany 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).
dc.description.indexedbyScopus
dc.description.openaccessHybrid Gold Open Access
dc.description.publisherscopeInternational
dc.description.sponsoredbyTubitakEuTÜBİTAK
dc.description.sponsorshipThis work was supported by the SparCity project of the European High-Performance Computing Joint Undertaking under grant agreement No. 956213. Koç University is supported by the Turkish Science and Technology Research Centre Grant No. 120N003, and INESC-ID is supported by Fundação para a Ciência e a Tec-nologia (FCT) through the UIDB/50021/2020 project. The research presented in this paper has also made use of the Experimental Infrastructure for Exploration of Exascale Computing (eX3), which is financially supported by the Research Council of Norway under contract 270053.
dc.identifier.doi10.1145/3581784.3607046
dc.identifier.isbn979-840070109-2
dc.identifier.quartileN/A
dc.identifier.scopus2-s2.0-85179552954
dc.identifier.urihttps://doi.org/10.1145/3581784.3607046
dc.identifier.urihttps://hdl.handle.net/20.500.14288/23029
dc.keywordsGraph partitioning
dc.keywordsMatrix reordering
dc.keywordsMulticore
dc.keywordsSparse matrix-vector multiply
dc.language.isoeng
dc.publisherAssociation for Computing Machinery, Inc
dc.relation.grantno120N003
dc.relation.ispartofProceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, SC 2023
dc.subjectMatrix algebra
dc.titleBringing order to sparsity: a sparse matrix reordering study on multicore CPUs
dc.typeConference Proceeding
dspace.entity.typePublication
local.contributor.kuauthorTorun, Tuğba
local.contributor.kuauthorDüzakın, Emre
local.contributor.kuauthorErten, Didem Unat
local.publication.orgunit1College of Engineering
local.publication.orgunit1GRADUATE SCHOOL OF SCIENCES AND ENGINEERING
local.publication.orgunit2Department of Computer Engineering
local.publication.orgunit2Graduate School of Sciences and Engineering
relation.isOrgUnitOfPublication89352e43-bf09-4ef4-82f6-6f9d0174ebae
relation.isOrgUnitOfPublication3fc31c89-e803-4eb1-af6b-6258bc42c3d8
relation.isOrgUnitOfPublication.latestForDiscovery89352e43-bf09-4ef4-82f6-6f9d0174ebae
relation.isParentOrgUnitOfPublication8e756b23-2d4a-4ce8-b1b3-62c794a8c164
relation.isParentOrgUnitOfPublication434c9663-2b11-4e66-9399-c863e2ebae43
relation.isParentOrgUnitOfPublication.latestForDiscovery8e756b23-2d4a-4ce8-b1b3-62c794a8c164

Files

Original bundle

Now showing 1 - 1 of 1
Thumbnail Image
Name:
IR04446.pdf
Size:
1.63 MB
Format:
Adobe Portable Document Format