Paralelní grafové algoritmy
| š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, MI_AMSM, MINF, APIN |
| klíčová slova: | grafové algoritmy, paralelní algoritmy |
| popis: | Grafy jsou přirozeným modelem pro popis vztahů v mnoha oblastech informatiky a vědy: od sociálních sítí přes neuronové struktury až po silniční mapy nebo chemické molekuly. Mnoho klasických algoritmů nad grafy – jako je hledání nejkratších cest, šíření informace, klasifikace vrcholů, maximální toky, topologické řazení, hledání klíčových cest (critical path method), detekci komunit – však bývá výpočetně náročných, zejména na velkých grafech. Zrychlení těchto algoritmů pomocí paralelizace na CPU nebo GPU je proto klíčové pro škálování na reálné aplikace. Paralelizace grafových algoritmů je výzvou kvůli: 1. nepravidelnému přístupu do paměti, 2. variabilnímu stupni vrcholů (load imbalance), 3. závislostem mezi výpočty. V současnosti existují pokročilé přístupy (např. level-synchronous BFS, frontier-based iterace, paralelní priority queues), a také knihovny jako Galois, Gunrock nebo cuGraph, které umožňují paralelní grafové výpočty na moderních architekturách. Cíle práce: 1. Prostudovat strategie paralelizace grafových algoritmů na CPU i GPU. 2. Implementovat nebo modifikovat vybraný algoritmus (např. PageRank, maximální tok, toplogické řazení) v knihovně TNL. 3. Porovnat efektivitu různých implementací (např. serial, OpenMP, CUDA). 4. Analyzovat vliv struktury grafu (např. degree distribution) na výkonnost. 5. Porovnat výkonnost s jinými implementacemi daného algoritmu. Přínos pro studenta: 1. Seznámí se s paralelními technikami pro práci s nepravidelnými datovými strukturami. 2. Získá zkušenosti s efektivním programováním na GPU a vícevláknových CPU. 3. Ziská zkušenosti s programováním v jazyce C++ s využitím jeho moderních vlastností. 4. Může přispět do open-source knihovny nebo připravit testovací scénáře na reálných grafech. |
| literatura: | 1. W. Kocay, D. L. Kreher, Graphs, Algorithms, and Optimization, Chapman and Hall/CRC, 2016. 2. R. Sedgewic, Algorithms in C, Part 5: Graph Algorithms, Addison-Wesley Professional, 2001. 3. Wang, Yangzihao, et al. \"Gunrock: GPU graph analytics.\" ACM Transactions on Parallel Computing (TOPC) 4.1 (2017): 1-49. |
| naposledy změněno: | 20.05.2025 09:30:45 |
za obsah této stránky zodpovídá:
Čestmír Burdík | naposledy změněno: 9.9.2021