Top-k Spatial Join on GPU

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