diplomsko delo
Leon Samotorčan (Avtor), Boštjan Slivnik (Mentor), Uroš Čibej (Komentor)

Povzetek

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.

Ključne besede

paralelizacija;podgrafni izomorfizem;OpenMP;granularnost;računalništvo in matematika;interdisciplinarni študij;univerzitetni študij;diplomske naloge;

Podatki

Jezik: Slovenski jezik
Leto izida:
Tipologija: 2.11 - Diplomsko delo
Organizacija: UL FRI - Fakulteta za računalništvo in informatiko
Založnik: [L. Samotorčan]
UDK: 004:51(043.2)
COBISS: 78319363 Povezava se bo odprla v novem oknu
Št. ogledov: 843
Št. prenosov: 67
Ocena: 0 (0 glasov)
Metapodatki: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

Ostali podatki

Sekundarni jezik: Angleški jezik
Sekundarni naslov: Parallelizing algorithms for solving subgraph isomorphism
Sekundarni povzetek: 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.
Sekundarne ključne besede: parallelization;subgraph isomorphism;OpenMP;granularity;computer science;computer and information science;computer science and mathematics;interdisciplinary studies;diploma;Računalništvo;Univerzitetna in visokošolska dela;
Vrsta dela (COBISS): Diplomsko delo/naloga
Študijski program: 1000407
Komentar na gradivo: Univ. v Ljubljani, Fak. za računalništvo in informatiko
Strani: 44 str.
ID: 13403707