Studentarbeten // Student Theses
Använd denna länk för att länka till samlingen:
Browse
Browsar Studentarbeten // Student Theses efter Författare "Aasa, Jakob"
Visar 1 - 2 av 2
Sökresultat per sida
Sortera efter
- PostEffektiv parallell slumptalsgenerering på GPU:er(2017) Lundberg, Marcus; Aasa, Jakob; Chalmers tekniska högskola / Institutionen för rymd- och geovetenskap; Chalmers University of Technology / Department of Earth and Space SciencesThis work compares several popular pseudo-random number generators implemented on a graphics processing unit (GPU). We consider generation for both uniform and normal distributions. The generators have also been tested using a selection of test algorithms to assess the quality of the output. As a final verification the generators have been tested in-situ on a simulation code. We chose to implement and test five different algorithms for generating uniform distributed numbers and three for generating normal distributed numbers. The generators were implemented with an object oriented programming approach in C++ using Nvidia’s CUDA framework. We have also included generators from Nvidia’s own random number generator library, cuRAND, to compare with our own. The test algorithms were implemented in C++ and CUDA as well. Our results show that some algorithms are not suited for use on GPUs, while other more GPU customized algorithms perform admirably. The results from the simulation code show that all of the generators except Wallace provide good output. The running time of the simulation code is about 100 to 250 times faster on the GPU depending on implementation compared to CPU. From our results we can recommend the Linear Congruental Generator (LCG) for generating uniform numbers if perfomance is a priority, and combining it with the Box-Muller Transform for generating normal distributed numbers.
- PostSpatial Indexing for Moving Geometry in Main Memory(2019) Aasa, Jakob; Lundberg, Marcus; Chalmers tekniska högskola / Institutionen för data och informationsteknik; Assarsson, Ulf; Stintorn, ErikSpatial indexes are data structures which store objects in the form of points or geometry in two or more dimensions in such a way that subsets can be queried with high performance. However, good query performance is no guarantee for a corresponding update performance. There is currently little research of spatial indexing for non-point geometry which receive frequent updates. This thesis studies and compares different spatial indexes for this kind of data. The evaluated data structures are the simple quadtree, the loose quadtree, theloose-linear quadtree, and the R*-tree. A dynamic array is also implemented to represent a naïve approach. Where applicable, we augment the spatial indexes with two update techniques: bottom-up updating and update memo, to assess if these improve performance. Evaluation is performed by a benchmark suite, where a scenario of objects sampled from different data distributions is used to quantify query and update performance of the spatial indexes. This evaluation is divided into two steps. First, parameters specific to each data structure is chosen, with 10 million objects in the scenario. Then, we compare the data structures, the update techniques, and the memory usage of the selection. We find that the loose quadtree performs best for all measured scenarios in both updates and queries, while the R*-tree is worst, if not counting the query performance of the dynamic array. Bottom-up updating and update memo yielded unsatisfactory performance given the extra memory that is needed. The contribution of this thesis is twofold. First, we perform a thorough performance comparison for spatial indexes that support moving non-point geometry. To our knowledge, there exist no such survey at the time of writing. Secondly, we present novel query algorithms for the loose-linear quadtree which perform at least an order of magnitude better than other existing approaches.