Paralelni algoritmi na grafovima

master's thesis

• Title (english): Parallel algorithms on graphs
• Author: Jurica Horvat
• Mentor: Mladen Jurak (mentor)
• Committee member: Mladen Jurak (predsjednik povjerenstva)
• Committee member: Zvonimir Bujanović (član povjerenstva)
• Committee member: Miljenko Marušić (član povjerenstva)
• Committee member: Nikola Sandrić (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2023-07-18, Croatia
• Scientific / art field, discipline and subdiscipline: NATURAL SCIENCES; Mathematics

Abstract

U ovom diplomskom radu analiziramo poznate algoritme na grafovima i implementiramo ih u jeziku C++, koristeći paralelizaciju kao sredstvo za optimizaciju. U uvodnom poglavlju smo se bavili izazovima koji se općenito javljaju kod programiranja višedretvenih aplikacija s dijeljenom memorijom. U drugom poglavlju smo stvorili bazu za konkurentno programiranje u modernom jeziku C++20, gdje smo istaknuli nekoliko korisnih i često korištenih sinkronizacijskih mehanizama te naveli korisne primjere. U glavnom dijelu rada smo se bavili s tri algoritma: pretraživanje u širinu (BFS), topološko sortiranje usmjerenih grafova bez ciklusa te Boruvkin algoritam za traženje minimalnog razapinjućeg stabla grafa. Za svaki od tih algoritama smo najprije opisali sekvencijalnu verziju, a onda ju paralelizirali i pritom detaljno analizirali mjesta izložena stanjima natjecanja. Na kraju smo sva tri algoritma implementirali u jeziku C++ i testirali njihova izvodenja sa različitim brojem korištenih dretvi, na odabranim testnim primjerima. Na samom kraju rada je iznesen motivacijski primjer, kojim se ističe korisnost algoritama na grafovima (konkretno, algoritama za traženje minimalnog razapinjućeg stabla) u stvarnom svijetu.

Abstract (english)

In this thesis, we analyze well-known algorithms on graphs and implement them in the language C++, using parallelization as a tool for optimization. In the introductory chapter, we dealt with the challenges that generally arise when programming multithreaded applications with shared memory. In the second chapter, we created a base for concurrent programming in the modern C++20 language, where we highlighted several useful and frequently used synchronization mechanisms and provided useful examples. In the main part of the thesis, we covered three famous algorithms: breadth-first search (BFS), topological sorting of directed acyclic graphs, and Boruvka’s algorithm for finding the minimum spanning tree of a graph. For each of these algorithms, we first described sequential version, then parallelized it step by step and thoroughly analyzed the places exposed to data races. In the end, we implemented all three algorithms in the C++ and tested their performances with a variable number of running threads. At the very end of the thesis, a motivational example is presented, which highlights the usefulness of algorithms on graphs (specifically, algorithms for finding minimum spanning tree) in the real world.

• Keywords: jezik C++; jezik C++20; BFS; Boruvkin algoritam
• Keywords (english): language C++; C++20 language; BFS; Boruvka’s algorithm
• Language: croatian
• URN:NBN: urn:nbn:hr:217:915961
• Study programme: Title: Computer Science and Mathematics; Study programme type: university; Study level: graduate; Academic / professional title: sveučilišni magistar računarstva i matematike (sveučilišni magistar računarstva i matematike)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Open access
• Created on: 2024-02-08 16:03:36