Paralelní grafové algoritmy
| advisor: | doc. Ing. Tomáš Oberhuber, Ph.D. |
| e-mail: | show e-mail |
| type: | bachelor thesis, master thesis |
| branch of study: | MI_MM, MI_AMSM, MINF, APIN |
| key words: | grafové algoritmy, paralelní algoritmy |
| description: | 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. |
| references: | 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. |
| last update: | 20.05.2025 09:30:45 |
administrator for this page:
Ľubomíra Dvořáková | last update: 09/12/2011