A split execution model for SpTRSV
Yükleniyor...
Dosyalar
Tarih
2021
Yazarlar
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.