Formáty pro řídké matice na GPU
| školitel: | doc. Ing. Tomáš Oberhuber, Ph.D. |
| e-mail: | zobrazit e-mail |
| typ práce: | bakalářská práce, diplomová práce |
| zaměření: | MI_MM, MINF, APIN |
| klíčová slova: | řídké matice, GPU, paralelní algoritmy |
| popis: | Vědecké a inženýrské výpočty často vedou na velké řídké matice – tedy matice, ve kterých je většina prvků nulová. Operace násobení řídké matice a vektoru (Sparse Matrix–Vector Multiplication, SpMV) je základním stavebním kamenem v mnoha algoritmech – zejména v: 1. numerickém řešení parciálních diferenciálních rovnic (např. FEM/FVM), 2. iterativních metodách pro řešení lineárních systémů (CG, BiCGStab, GMRES), 3. optimalizačních algoritmech (gradienty, Jacobiany), 4. strojovém učení (např. trénování sparse modelů). SpMV je paměťově omezená operace – to znamená, že její výkon je více ovlivněn přístupem do paměti než výpočetním výkonem samotného procesoru. Právě proto je její efektivní implementace na GPU velmi náročná, ale zároveň extrémně důležitá pro výkonnost celého systému. Mezi nejpopulárnější formáty pro ukládání řídkých matic patří CSR formát. Ačkoliv je tento formát velmi rozšířený a paměťově efektivní, paralelizace SpMV nad CSR na GPU je náročná kvůli: nerovnoměrnému počtu nenulových prvků v řádcích (load imbalance), neoptimálním přístupům do globální paměti GPU. Výzkum efektivních paralelních algoritmů pro GPU se tak dělí na snahy maximálně optimalizovat GPU kernely pro CSR formát nebo návrh nových formátů, lépe navržených přímo pro GPU. Cíle práce: 1. Prostudovat různé paralelní algoritmy pro SpMV nad CSR formátem na GPU nebo alternativní formáty. 2. Implementovat a porovnat vybrané algoritmy v knihovně TNL jako rozšíření datové abstrakce segmenty v této knihovně. 3. Porovnat výkon s existujícími knihovnami (např. cuSPARSE, Ginkgo). Přínosy pro studenta: 1. Získá detailní znalost programování pro GPU včetně praktické zkušenosti s vývojem a laděním GPU kernelů. 2. Naučí se pokročilé techniky programování v C++. 3. Přispěje k výzkumu nebo vývoji knihovny TNL. 4. Práce má přímé využití v HPC, numerické simulaci i optimalizaci. |
| literatura: | 1. Oberhuber T., Klinkovský J., Fučík R., TNL: Numerical library for modern parallel architectures, Acta Polytechnica, vol. 61, no. SI, pp. 122-134, 2020. 2. Gao, Jianhua, et al. \"A systematic literature survey of sparse matrix-vector multiplication.\" arXiv preprint arXiv:2404.06047 (2024). 3. Zhao, Zhixiang, et al. \"Recursive Hybrid Compression for Sparse Matrix‐Vector Multiplication on GPU.\" Concurrency and Computation: Practice and Experience 37.4-5 (2025). 4. Jiang, Jiafan, Jianqiang Huang, and Haodong Bian. \"GTLB: A Load-Balanced SpMV Computation Method on GPU.\" Proceedings of the 2023 7th International Conference on High Performance Compilation, Computing and Communications. 2023. 5. Liu, Weifeng, and Brian Vinter. \"CSR5: An efficient storage format for cross-platform sparse matrix-vector multiplication.\" Proceedings of the 29th ACM on International Conference on Supercomputing. 2015. 6. Xu, Jianfei, Lianhua He, and Zhong Jin. \"Mixed precision SpMV on GPUs for irregular data with hierarchical precision selection.\" CCF Transactions on High Performance Computing (2025): 1-13. 7. Zeng, Guangsen, and Yi Zou. \"Leveraging Memory Copy Overlap for Efficient Sparse Matrix-Vector Multiplication on GPUs.\" Electronics 12.17 (2023): 3687. 8. Gao, Jianhua, et al. \"Revisiting thread configuration of SpMV kernels on GPU: A machine learning based approach.\" Journal of Parallel and Distributed Computing 185 (2024): 104799. |
| naposledy změněno: | 20.05.2025 09:10:53 |
za obsah této stránky zodpovídá:
Pavel Strachota | naposledy změněno: 9.9.2021