A split execution model for SpTRSV

Yükleniyor...
Küçük Resim

Tarih

2021

Dergi Başlığı

Dergi ISSN

Cilt Başlığı

Yayıncı

IEEE Computer Society

Erişim Hakkı

info:eu-repo/semantics/closedAccess

Özet

Sparse Triangular Solve (SpTRSV) is an important and extensively used kernel in scientific computing. Parallelism within SpTRSV depends upon matrix sparsity pattern and, in many cases, is non-uniform from one computational step to the next. In cases where the SpTRSV computational steps have contrasting parallelism characteristics some steps are more parallel, others more sequential in nature, the performance of an SpTRSV algorithm may be limited by the contrasting parallelism characteristics. In this work, we propose a split-execution model for SpTRSV to automatically divide SpTRSV computation into two sub-SpTRSV systems and an SpMV, such that one of the sub-SpTRSVs has more parallelism than the other. Each sub-SpTRSV is then computed by using a different SpTRSV algorithm and possibly executes on a different platform (CPU or GPU). By analyzing the SpTRSV Directed Acyclic Graph (DAG) and matrix sparsity features, we use a heuristics-based approach to (i) automatically determine suitability of an SpTRSV for split-execution, (ii) find the appropriate split-point, and (iii) execute SpTRSV in a split fashion using two SpTRSV algorithms while managing any required inter-platform communication. Experimental evaluation of the execution model on two CPU-GPU machines with matrix dataset of 327 matrices from the SuiteSparse Matrix Collection shows that our approach correctly selects the fastest SpTRSV method (split or unsplit) for 88% of matrices on the Intel Xeon Gold (6148) + NVIDIA Tesla V100 and 83% on the Intel Core I7 + NVIDIA G1080 Ti platform achieving speedups in the range of 1.01 10 and 1.03 6.36, respectively. IEEE

Açıklama

Anahtar Kelimeler

Computational Modeling, CPU-GPU Computing, Fats, Graphics Processing Units, Heterogeneous Computing, Kernel, Parallel Algorithms, Phased Arrays, Sparse Linear Systems, Sparse Matrices, Sparse Triangular Solve, SpTRSV, SpTS

Kaynak

IEEE Transactions on Parallel and Distributed Systems

WoS Q Değeri

Q2

Scopus Q Değeri

Q1

Cilt

Sayı

Künye

Ahmad, N., Ylmaz, B., & Unat, D. (2021). A Split Execution Model for SpTRSV. IEEE Transactions on Parallel and Distributed Systems.