Parallell Delaunay-triangulering i Java og CUDA

Abstract

I de senere år har hardwareprodusenter, i stedet for å øke klokkehastigheten, duplisert kjerner på prosessorer. Konsekvensen er at prosessorer stadig får flere kjerner. Skjermkortleverandører har også sett potensialet av økt regnekraft, og i det siste har de lansert utviklingspakker som gjør det mulig å bruke skjermkort til mer enn å bare tegne opp grafikk på skjerm.

Denne oppgaven ser hovedsakelig på Delaunay-triangulering i planet. Oppgaven baserer seg på en eldre implementasjon, hvor algoritmene har blitt trukket ut og reimplementert til å passe for objektorienterte språk. Implementasjonen har så blitt optimalisert og parallellisert i flere varianter.

Til slutt gjøres en radikal endring i algoritmen for å prøve å tilpasse Delaunay-triangulering for NVIDIAs CUDA-plattform. Endringen er basert på en oppdagelse som ble gjort av forfatteren under arbeidet med denne oppgaven, og den er beskrevet i detalj i en artikkel som følger med som vedlegg.

In the recent years hardware producers have, instead of increasing clock frequency of their processors, duplicated cores in their processors. As a consequence, processors continuously keep getting more cores. Graphic card vendors have also seen the potential of increased computational power, and lately they have introduced development kits that make it possible to use their cards for more than just drawing graphics onto the screen.

This thesis looks primarily at the Delaunay-triangulation in the plane. The thesis is based on an earlier triangulation implementation, but where the algorithms have been extracted and reimplemented to fit for using object-oriented languages. The implementation has then been optimized and parallellized in several versions.

A radical change is done in the algorithm in the end in order to try to adapt the implementation for NVIDIAs CUDA-platform. The change is based on a discovery made by the author during the work of this thesis and is described in detail in an article that is included as an attachment.