Top-k Spatial Join on GPU

Abstract

Oppgaven utforsker romlige sammensettingsspørringer utført på GPU. Målet er å utforske om en top-k romlig sammensettingsspørring gir mening å utføre på GPU.

Først introduseres romlige sammensettninger generelt før den spesifikke spørringen blir definert. Så diskuteres karakteristikken til tradisjonelle datamaskinarkitekturer for å gi kontekst til hvorfor GPU arkitekturen er som den er og hvordan man effektivt kan programmere den.

Neste del av oppgaven diskuterer to forskjellige romlige søkestrukturer som heter R-trær og uniforme rutenett. Dette gir kontekst til valget for en romlig søkestruktur.

For å få en bedre forståelse av hvordan tidligere forskning har håndtert romlige sammensettninger på GPU, undersøker vi fire forskjellige metoder. Målet er å finne ut hvilke teknikker som passer bra til GPU arkitekturen og hvilke aspekter vi må være oppmerksom på når vi desinger vår egen algoritme.

Til slutt blir den nye algoritmen designet og sammenlignet med en enkel parallel algoritme på GPU. Resultatene viser at romlige sammensettningsspørringer alene passer bra til GPU parallelisering. Om man legger til top-k delen av problemet, støter vi på signifikante utfordringer hvor ingen av metodene vi testet ungikk store utfordringer med å utnytte GPU maskinvaren til sitt fulle potensial.

In this thesis we will investigate spatial join queries on GPU. The specific goal is to find if top-k spatial join queries are suitable for the GPU architecture.

We first discuss spatial join in general before we define the specific query we want to design an algorithm for.

Then the characteristics of traditional computer architectures are visited to understand the differences between it and the massively parallel GPU architecture. The GPU architecture is discussed to get a good understanding of the execution model. Important aspects that utilize the hardware to its full potential is also discussed.

Next, two common spatial indexes called R-tree and uniform grid are discussed This is to give context to our choice of the uniform grid as the spatial index for the top-k spatial distance join query.

To get a better understanding of how previous research have handled spatial join on GPU we choose four different spatial join methods to investigate. The purpose is to learn which techniques works well for GPU and what we need to be cautious of when designing our own algorithm.

Lastly the top-k spatial distance join algorithm is design and benchmarked against a simple parallel approach. The results show that the spatial distance join part of the problem is well suited for GPU parallelization. Adding the top-k part introduce significant challenges that leaves none of our benchmarked methods without significant drawbacks to the hardware utilization.