Paralelizacija algoritmov za reševanje problema podgrafnega izomorfizmaSamotorčan, Leon (Avtor) Slivnik, Boštjan (Mentor) Čibej, Uroš (Komentor) paralelizacijapodgrafni izomorfizemOpenMPgranularnostPri 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.20212021-09-14 15:35:03Diplomsko delo/naloga130398VisID: 32507COBISS_ID: 78319363sl