20.500.12556/RUL-130398 Paralelizacija algoritmov za reševanje problema podgrafnega izomorfizma Parallelizing algorithms for solving subgraph isomorphism Pri analizi podatkov v obliki grafov je iskanje pojavitev manjšega grafa znotraj večjega eden pomembnejših problemov. Rečemo mu problem podgrafnega izomorfizma. V diplomskem delu se posvetimo različici problema, kjer iščemo število vseh induciranih podgrafnih izomorfizmov na neusmerjenih grafih. Opišemo tri sorodne algoritme za reševanje tega problema, ki jih implementiramo in nato paraleliziramo s pomočjo programskega vmesnik OpenMP. Pri paralelizaciji uporabimo pristop z dinamično delitvijo dela, kjer si niti izmenjujejo naloge preko skupne vrste nalog. Za izmenjavo nalog preizkusimo lastno implementacijo vrste in vgrajeno OpenMP-jevo rešitev. Uspešnost paralelizacije eksperimentalno ovrednotimo na dveh testnih množicah. Posvetimo se tudi vplivu granularnosti problema na čas izvajanja. In the analysis of graph data the search for an appearance of a smaller graph within a larger one is one of the more important problems. We call it the subgraph isomorphism problem. In this thesis we focus on a problem variant, where we search for the number of all induced subgraph isomorphisms on undirected graphs. We describe three related algorithms for solving this problem which we implement and then parallelize using an application programming interface called OpenMP. At parallelization we take on the approach of dynamic distribution of tasks where threads exchange tasks through a global queue. For task exchange we test our own implementation of the queue and the built-in OpenMP solution. Parallel algorithms are experimentally evaluated on two test sets. We also examine the impact of granularity on the execution time. paralelizacija podgrafni izomorfizem OpenMP granularnost parallelization subgraph isomorphism OpenMP granularity true false false Slovenski jezik Angleški jezik Diplomsko delo/naloga 2021-09-14 15:35:03 2021-09-14 15:35:07 2023-12-01 11:25:53 0000-00-00 00:00:00 2021 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 32507 78319363 Samotorcan_Leon_-_Paralelizacija_algoritmov_za_resevanje_problema_podgrafnega_izomorfizma.pdf Samotorcan_Leon_-_Paralelizacija_algoritmov_za_resevanje_problema_podgrafnega_izomorfizma.pdf 1 7E845E425E5B1E5F4A3A1904E93EC7F4 40d973e23320e03e64cb15171ff5903a0fd580c9e218aa12a0f285c3b66cf161 514bc8ef-1560-11ec-a523-00155dcfd717 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=147505 Fakulteta za računalništvo in informatiko Fakulteta za matematiko in fiziko 0 0 0