At Carmenta we have a long tradition of welcoming master’s thesis students from universities in Sweden, Germany and France. We believe that working closely with academia brings fresh perspectives and helps drive both innovation and growth.
This project, completed in 2024, is a great example of the valuable contributions students bring to our team. We’re especially pleased that the author, Louise Tidestav, has since joined us full-time.
In mapping systems, numerous calculations and analyses are performed on geospatial features, which consist of geometries (such as points, lines, polygons, or 3D meshes) combined with a set of attributes (such as city names and populations). Many of these calculations and analyses are trivially parallelizable, making them well-suited for execution on a GPU.
This master’s thesis explored a small domain-specific language designed to express these types of calculations in a manner suitable for GPU execution. For Carmenta, this project was of interest as we are interested in enabling our customers to perform geospatial calculations on GPUs without requiring advanced knowledge of GPU programming.
Figure: Execution time for point in polygon, v = 10 000
This thesis explores how a domain-specific language (DSL) for simple geospatial operators on the GPU can be developed, and evaluates the level of functionality and performance of such a DSL. The purpose of such a DSL is to simplify implementation of geospatial operators on the GPU, in order to increase productivity and performance.
An embedded and interpreted DSL was designed and implemented according to the geospatial domain. The level of functionality of the DSL was evaluated based on what geospatial operators are supported and with the Framework for Qualitative Assessment of DSLs (FQAD). The level of functionality was evaluated too high for the DSL, as simple geospatial operators are supported and the FQAD evaluation determined that the DSL was effective. To evaluate the performance gains, three interpreters for the DSL were implemented, one sequential on the CPU, one parallel on the CPU and one on the GPU. The execution time for five geospatial operators and algorithms was measured for different problem sizes for the three interpreters.
The GPU interpreter achieved large speedups for large problem sizes compared to the sequential CPU interpreter. The GPU interpreter achieved speedups for four out of five operators compared to the parallel CPU interpreter for large problem sizes. In conclusion, this thesis demonstrates the potential of a domain-specific language for geospatial computations on the GPU.
Tidestav, Louise. A domain-specific language for geospatial computations on the GPU: A study on the level of functionality and the performance gains (2024).
This master's thesis explores optimizing terrain vehicle routing using GPU-parallelism. By leveraging the regular structure of terrain graphs, the thesis focuses on improving the efficiency of single-source shortest path (SSSP) algorithms.
Read more
Collaborative single-display teamwork without any widget or button. A case study using Carmenta Engine. This thesis introduced a new form of interfacing with the Carmenta Engine on touch screen. Its results show that through using the technique of hand chords, several users can work with the one large touchscreen simultaneously.
Read more