diplomsko delo
Leon Samotorčan (Author), Boštjan Slivnik (Mentor), Uroš Čibej (Co-mentor)

Abstract

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.

Keywords

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

Data

Language: Slovenian
Year of publishing:
Typology: 2.11 - Undergraduate Thesis
Organization: UL FRI - Faculty of Computer and Information Science
Publisher: [L. Samotorčan]
UDC: 004:51(043.2)
COBISS: 78319363 Link will open in a new window
Views: 843
Downloads: 67
Average score: 0 (0 votes)
Metadata: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

Other data

Secondary language: English
Secondary title: Parallelizing algorithms for solving subgraph isomorphism
Secondary abstract: 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.
Secondary keywords: 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;
Type (COBISS): Bachelor thesis/paper
Study programme: 1000407
Thesis comment: Univ. v Ljubljani, Fak. za računalništvo in informatiko
Pages: 44 str.
ID: 13403707