Staging Blocked Evaluation over Structured Sparse Matrices
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866908829558505472 |
|---|---|
| author | Das, Pratyush Basareh, Amirhossein Dias, Adhitha Pelenitsyn, Artem Sundararajah, Kirshanthan Kulkarni, Milind Delaware, Ben |
| author_facet | Das, Pratyush Basareh, Amirhossein Dias, Adhitha Pelenitsyn, Artem Sundararajah, Kirshanthan Kulkarni, Milind Delaware, Ben |
| contents | The matrices used in many computational settings are naturally sparse, holding a small percentage of nonzero elements. Storing such matrices in specialized sparse formats enables algorithms that avoid wasting computation on zeros, significantly accelerating common matrix computations like sparse matrix-vector multiplication (SpMV) and sparse matrix-matrix multiplication (SpMM). In many real-world sparse matrices, however, nonzero elements are densely clustered in subregions of the matrix. For matrices that feature this sort of structured sparsity, hybrid formats can further improve performance by representing these subregions as dense blocks. Existing hybrid formats either fix the dimensions of dense blocks, padding irregular regions with zeros and wasting computation, or incur run-time overhead when iterating over variable-sized blocks.
This paper presents SABLE, a framework for accelerating structured sparse matrix computations by using staging to achieve the best of both of these approaches. Ahead of execution, SABLE inspects the matrix to identify variable-sized dense subregions, which it stores using a new hybrid format. It then eliminates the overhead typically associated with variable-sized blocks by using staging to generate specialized code that is amenable to vectorization. We evaluate SABLE on SpMV and SpMM kernels using matrices from the popular SuiteSparse data set. SABLE outperforms the best available SpMV baseline by ${\sim}$10\% on average, and SpMM baselines by ${\sim}$20\%. When parallelized, SABLE achieves further speedups of up to ${\sim}7\times$ on SpMV and SpMM over the best fully-sparse baseline when using 8 threads. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_00829 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Staging Blocked Evaluation over Structured Sparse Matrices Das, Pratyush Basareh, Amirhossein Dias, Adhitha Pelenitsyn, Artem Sundararajah, Kirshanthan Kulkarni, Milind Delaware, Ben Distributed, Parallel, and Cluster Computing Performance The matrices used in many computational settings are naturally sparse, holding a small percentage of nonzero elements. Storing such matrices in specialized sparse formats enables algorithms that avoid wasting computation on zeros, significantly accelerating common matrix computations like sparse matrix-vector multiplication (SpMV) and sparse matrix-matrix multiplication (SpMM). In many real-world sparse matrices, however, nonzero elements are densely clustered in subregions of the matrix. For matrices that feature this sort of structured sparsity, hybrid formats can further improve performance by representing these subregions as dense blocks. Existing hybrid formats either fix the dimensions of dense blocks, padding irregular regions with zeros and wasting computation, or incur run-time overhead when iterating over variable-sized blocks. This paper presents SABLE, a framework for accelerating structured sparse matrix computations by using staging to achieve the best of both of these approaches. Ahead of execution, SABLE inspects the matrix to identify variable-sized dense subregions, which it stores using a new hybrid format. It then eliminates the overhead typically associated with variable-sized blocks by using staging to generate specialized code that is amenable to vectorization. We evaluate SABLE on SpMV and SpMM kernels using matrices from the popular SuiteSparse data set. SABLE outperforms the best available SpMV baseline by ${\sim}$10\% on average, and SpMM baselines by ${\sim}$20\%. When parallelized, SABLE achieves further speedups of up to ${\sim}7\times$ on SpMV and SpMM over the best fully-sparse baseline when using 8 threads. |
| title | Staging Blocked Evaluation over Structured Sparse Matrices |
| topic | Distributed, Parallel, and Cluster Computing Performance |
| url | https://arxiv.org/abs/2407.00829 |