Seyrek Alt Üçgen Matris Çözümü Optimizasyonu İçin Verimli Graf Dönüşüm Stratejileri

Abstract

Seyrek alt üçgen matris çözümünün (SAÜMÇ) çok çekirdekli mimarilerde optimizasyonu, veri bağımlılıklarından ve girdi matrisin düzensiz seyreklik yapısından kaynaklanan performans darboğazları nedeniyle zordur. Literatürde, matrisi daha küçük alt problemlere bölerek ve bu alt problemleri uygun yöntemlerle ve/veya uygun mimariler üzerinde çözerek performansı artırmayı amaçlayan geniş bir SpTRSV optimizasyon yöntemleri yelpazesi bulunmaktadır. Matrisin bölünmesine alternatif olarak, bağımlılık grafının dönüştürülmesi yoluyla seyreklik yapısının daha homojen bir hâle getirilmesi de etkili bir optimizasyon yöntemi olarak literatürde öne çıkmıştır. Satırlarla temsil edilen denklemleri yeniden yazarak bağımlılık grafını dönüştürmek, sınırlı hesaplamalara sahip bölgelerde paralel yürütmeyi etkinleştirir veya geliştirir, yük dengelemesini sağlar ve grafın kritik patika uzunluğunu azaltır. Bu çalışmada, seyrek girdi matrisinin ve kullanılan mimarinin özelliklerinden yararlanan üç sezgisel (heuristic) tabanlı graf dönüşüm stratejisi önerilmektedir. İki farklı SAÜMÇ uygulamasıyla yapılan deneylerde, geliştirilen stratejiler 3,42× ve 2,88×’e kadar hızlanma elde ederek, literatürdeki sezgisel tabanlı bir dönüşüm stratejisinin ulaştığı 2,13× ve 1,31×’lik en yüksek hızlanmaları aşmaktadır. Geliştirilen graf dönüşüm stratejileri, kullanılan SAÜMÇ algoritmasından bağımsız olup diğer optimizasyon teknikleriyle entegre edilebilir niteliktedir; bu da esneklik ve taşınabilirlik sağlamaktadır.

Keywords

• Seyrek Alt Üçgen Matris Çözümü
• Paralel Hesaplama
• Performans Optimizasyonu
• Graf Dönüşümü
• Sezgisel Algoritma

Supporting Institution

Türkiye Bilimsel ve Teknolojik Araştırma Kurumu (TÜḂİTAK)

Project Number

121E612

Ethical Statement

Hazırlanan makalede etik kurul izni alınmasına gerek yoktur.

Efficient Graph Transformation Strategies for Optimizing Sparse Triangular Solve

Abstract

Sparse triangular solve (SpTRSV) is challenging to optimize on multicore systems due to performance bottlenecks arising from data dependencies and the irregular sparsity pattern of the input matrix. The literature offers a wide range of SpTRSV optimization techniques that partition the matrix into smaller subproblems, which are then solved using suitable methods and/or mapped onto appropriate architectures. As an alternative to partitioning, transforming the dependency graph to achieve a more homogeneous sparsity pattern has also emerged as an effective optimization strategy in literature. Transforming the dependency graph by rewriting the equations represented by rows enables or enhances parallel execution in regions with limited computations, improves load balancing, and reduces the critical path length. In this work, we propose three heuristic-based graph transformation strategies that exploit features of the sparse input matrix and the underlying architecture. Experiments with two different SpTRSV implementations demonstrate maximum speedups of 3.42× and 2.88×, surpassing a previously proposed heuristic-based transformation strategy that attains maximum speedups of 2.13× and 1.31×. The proposed graph transformation strategies are agnostic to the underlying SpTRSV algorithm and can be integrated with other optimization techniques, offering both flexibility and portability.

Keywords

• Sparse Triangular Solve
• Parallel Computing
• Performance Optimization
• Graph Transformation
• Heuristic-Based Algorithm

Supporting Institution

The Scientific and Technological Research Council of Türkiye (TÜḂİTAK)

Project Number

121E612

Ethical Statement

Obtaining ethics committee approval is not needed.

References

1. Naumov M. Parallel Solution of Sparse Triangular Linear Systems in Preconditioned Iterative Methods on the GPU. NVIDIA, Technical Report; 2011.
2. Saad Y. Iterative Methods for Sparse Linear Systems. Computers & Mathematics with Applications 2001;8:423-440. doi:10.1016/S0898-1221(01)80034-2.
3. Van Loan CF, Golub GH. Matrix Computations. 3rd ed. Baltimore: Johns Hopkins University Press; 1996.
4. Çuğu İ. Parallel Solution of Sparse Triangular Linear Systems on Multicore Platforms [Yüksek Lisans Tezi]. Ankara: Bilkent Üniversitesi; 2018.
5. Ahmad N, Yılmaz B, Unat D. A Split Execution Model for SpTRSV. IEEE Transactions on Parallel and Distributed Systems 2021;32(11):2809-2822. doi:10.1109/TPDS.2021.3074501.
6. Bradley AM. A Hybrid Multithreaded Direct Sparse Triangular Solver. İçinde: SIAM Workshop on Combinatorial Scientific Computing (CSC), Philadelphia; 2016, s. 13-22. doi:10.1137/1.9781611974690.ch2.
7. Mayer J. Parallel Algorithms for Solving Linear Systems with Sparse Triangular Matrices. Computing 2009;86(4):291-312. doi:10.1007/s00607-009-0066-3.
8. Totoni E, Heath MT, Kale LV. Structure-Adaptive Parallel Solution of Sparse Triangular Linear Systems. Parallel Computing 2014;40(9):454-470. doi:10.1016/j.parco.2014.06.006.

9. Yılmaz B. Graph Transformation and Specialized Code Generation for SpTRSV. arXiv:2103.11445; 2021.
10. Yılmaz B, Yıldız AF. A Graph Transformation Strategy for Optimizing SpTRSV. arXiv:2206.05843; 2022.
11. Yılmaz B. A Novel Graph Transformation Strategy for Optimizing SpTRSV on CPUs. Concurrency and Computation: Practice and Experience 2023;35(24):e7761. doi:10.1002/cpe.7761.
12. Anderson E, Saad Y. Solving Sparse Triangular Linear Systems on Parallel Computers. International Journal of High Speed Computing 1989;1(1):73-95. doi:10.1142/S0129053389000056.
13. Li R, Saad Y. GPU-Accelerated Preconditioned Iterative Linear Solvers. The Journal of Supercomputing 2013;63(2):443-466. doi:10.1007/s11227-012-0825-3.
14. Yılmaz B, Sipahioğlu B, Ahmad N, Unat D. Adaptive Level Binning: A New Algorithm for Solving Sparse Triangular Systems. İçinde: HPCAsia 2020. ACM; 2020, s. 188-198. doi:10.1145/3368474.3368486.
15. Li R. On Parallel Solution of Sparse Triangular Linear Systems in CUDA. arXiv:1710.04985; 2017.
16. Liu W, Li A, Hogg JD, Duff IS, Vinter B. A Synchronization-Free Algorithm for Parallel Sparse Triangular Solves. İçinde: Euro-Par 2016. Springer; 2016, s. 617-630. doi:10.1007/978-3-319-43659-3_45.
17. Liu W, Li A, Hogg JD, Duff IS, Vinter B. Fast Synchronization-Free Algorithms for Parallel Sparse Triangular Solves with Multiple Right-Hand Sides. Concurrency and Computation: Practice and Experience 2017;29(21):e4244. doi:10.1002/cpe.4244.
18. Su J, Zhang F, Liu W, He B, Wu R, Du X, et al. CapelliniSpTRSV: A Thread-Level Synchronization-Free Sparse Triangular Solve on GPUs. İçinde: ICPP 2020. ACM; 2020, s. 2:1-2:11. doi:10.1145/3404397.3404400.
19. Davis TA, Hu Y. The University of Florida Sparse Matrix Collection. ACM Transactions on Mathematical Software 2011;38(1):1:1-1:25. doi:10.1145/2049662.2049663.
20. Istanbul Technical University National Center for High Performance Computing (UHeM). Erişim adresi: https://www.uhem.itu.edu.tr/ [Erişim tarihi 9 Kasım 2025].
21. OpenMP Architecture Review Board. OpenMP Application Programming Interface Version 5.0. Erişim adresi: https://www.openmp.org/specifications/ [Erişim tarihi 9 Kasım 2025].
22. Aliaga JI, Dufrechou E, Ezzatti P, Quintana-Ortí ES. Accelerating the Task/Data-Parallel Version of ILUPACK’s BiCG in Multi-CPU/GPU Configurations. Parallel Computing 2019;85:79-87. doi:10.1016/j.parco.2019.02.005.
23. Park J, Smelyanskiy M, Sundaram N, Dubey P. Sparsifying Synchronization for High-Performance Sparse Triangular Solver. İçinde: ISC 2014. Springer; 2014, s. 124-140. doi:10.1007/978-3-319-07518-1_8.
24. Iwashita T, Nakashima H, Takahashi Y. Algebraic Block Multi-Color Ordering Method for Parallel Sparse Triangular Solver in ICCG Method. İçinde: IPDPS 2012. IEEE; 2012, s. 474-483. doi:10.1109/IPDPS.2012.51.
25. Ma S, Saad Y. Distributed ILU(0) and SOR Preconditioners for Unstructured Sparse Linear Systems. İçinde: International Conference on Parallel Processing. IEEE; 1998, s. 266-273.
26. Naumov M, Castonguay P, Cohen J. Parallel Graph Coloring with Applications to the Incomplete-LU Factorization on the GPU. NVIDIA, Technical Report; 2015.
27. Suchoski B, Severn C, Shantharam M, Raghavan P. Adapting Sparse Triangular Solution to GPUs. İçinde: ICPP Workshops (ICPPW). IEEE; 2012, s. 140-148. doi:10.1109/ICPPW.2012.23.
28. Lu Z, Niu Y, Liu W. Efficient Block Algorithms for Parallel Sparse Triangular Solve. İçinde: ICPP 2020. ACM; 2020, s. 63:1-63:11. doi:10.1145/3404397.3404413.
29. Çuğu İ, Manguoğlu M. A Parallel Multithreaded Sparse Triangular Linear System Solver. Computers & Mathematics with Applications 2020;80(2):371-385. doi:10.1016/j.camwa.2019.09.012.
30. Smith B, Zhang H. Sparse Triangular Solves for ILU Revisited: Data Layout Crucial to Better Performance. International Journal of High Performance Computing Applications 2011;25(4):386-391. doi:10.1177/1094342010389857.
31. Zhang F, Su J, Liu W, He B, Wu R, Du X, et al. YuenyeungSpTRSV: A Thread-Level and Warp-Level Fusion Synchronization-Free Sparse Triangular Solve. IEEE Transactions on Parallel and Distributed Systems 2021;32(9):2321-2337. doi:10.1109/TPDS.2021.3066635.
32. Kamin S, Garzarán MJ, Aktemur B, Xu D, Yılmaz B, Chen Z. Optimization by runtime specialization for sparse matrix-vector multiplication. İçinde: Proceedings of the 2014 International Conference on Generative Programming: Concepts and Experiences (GPCE 2014). New York, NY, USA: Association for Computing Machinery; 2014, s. 93-102. doi:10.1145/2658761.2658773.
33. Rong H, Park J, Xiang L, Anderson TA, Smelyanskiy M. Sparso: Context-Driven Optimizations of Sparse Linear Algebra. İçinde: PACT 2016. ACM/IEEE; 2016, s. 247-259. doi:10.1145/2967938.2967943.
34. Cheshmi K, Kamil S, Strout MM, Dehnavi MM. Sympiler: Transforming Sparse Matrix Codes by Decoupling Symbolic Analysis. İçinde: SC’17. ACM; 2017, s. 13:1-13:13. doi:10.1145/3126908.3126936.
35. Patel R, Ahrens W, Amarasinghe S. SySTeC: A Symmetric Sparse Tensor Compiler. İçinde: CGO 2025. ACM/IEEE; 2025, s. 47-62. doi:10.1145/3650212.3652148.
36. Hu Z, Sun J, Li Z, Sun G. AG-SpTRSV: An Automatic Framework to Optimize Sparse Triangular Solve on GPUs. ACM Transactions on Architecture and Code Optimization 2024;21(4):70. doi:10.1145/3674911.