20.500.12556/RUL-140056 Indeksna struktura za učinkovito vzporedno iskanje in vstavljanje točk v večdimenzionalnem prostoru magistrsko delo An indexing structure for efficient parallel point lookups and insertions in a multidimensional space Za 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. For efficient work with points in space we require a suitable data and indexing structure, upon which we are able to rely on during the development of algorithms. We have a wide selection of such structures to choose from, but the majority of them do not allow us to insert new points in a multithreaded context without the use of auxiliary protection mechanisms. Such structures limit the execution of the critical parts of programs to one thread at a time, which prevents us from efficiently utilizing all the available computing power at our disposal. We therefore require an indexing structure that allows us to lookup points as well as insert new points in parallel without auxiliary protection mechanisms that limit execution speed. We developed a quadtree-based indexing structure which limits the critical parts of the program to the leaves of the tree, which in turn lowers the probability of a thread collision and subsequently allows for significantly faster execution of the algorithm. We tested the tree using the parallel domain discretization algorithm and showed that when using many threads of execution the use of our indexing structure leads to significantly faster execution of the algorithm compared to the previous solution. iskalno drevo vzporedno računanje diskretizacija domene indexing tree parallel computing domain discretization true false false Slovenski jezik Angleški jezik Magistrsko delo/naloga 2022-09-10 08:15:08 2022-09-10 08:15:12 2024-05-29 12:45:59 0000-00-00 00:00:00 2022 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 126810 120760323 4992.pdf 4992.pdf 1 0A9907010DEA4C28B4B29466FA107F43 69ec86c4c2483ae33776eccf0ec833e6df40fc6a0860d19a9f1797b466ad03c9 df82837d-30cf-11ed-92af-00155dcfd717 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=160721 Fakulteta za matematiko in fiziko Fakulteta za računalništvo in informatiko 0 0 0