Indeksna struktura za učinkovito vzporedno iskanje in vstavljanje točk v večdimenzionalnem prostoruRojc, Blaž (Avtor) Cabello, Sergio (Mentor) Depolli, Matjaž (Komentor) iskalno drevovzporedno računanjediskretizacija domeneZa učinkovito delo s točkami v prostoru potrebujemo primerno podatkovno in indeksno strukturo, na katero se lahko zanašamo pri razvoju algoritmov. Na voljo imamo obsežen nabor takšnih struktur, a v večini nam ne omogočajo vstavljati novih točk v kontekstu več niti izvajanja brez dodatnih varovalnih mehanizmov. Takšne strukture omejijo izvajanje kritičnih delov programa eni niti naenkrat, kar nam prepreči učinkovito izrabo vseh računskih sredstev, ki so nam na voljo. Potrebujemo torej indeksno strukturo, ki nam omogoča tako vzporedno iskati kot tudi vzporedno vstavljati točke brez zunanjih varovalnih mehanizmov, ki omejujejo hitrost izvajanja. Razvili smo indeksno strukturo na podlagi štiriškega drevesa, ki kritične dele programa omeji na liste drevesa, kar zmanjša verjetnost trka dveh niti in posledično omogoča veliko hitrejše izvajanje algoritma. Drevo smo testirali na vzporednem algoritmu za diskretizacijo domene in pokazali, da pri uporabi velikega števila niti izvajanja uporaba naše indeksne strukture vodi do veliko hitrejšega izvajanja algoritma kot prejšnja rešitev.20222022-09-10 08:15:08Magistrsko delo/naloga140056VisID: 126810COBISS_ID: 120760323sl