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.
|
