PRP-2014: Parallelle, faseoppdelte og rekursive algoritmer

Parallell programmering blir mer og mer viktig ettersom vi får flere prosesseringsenheter i en datamaskin. Derimot kan slik programmering være vanskelig, fordi det kreves ekstra administrativ kode for å sette i gang parallellitet. Programflyten er også vanskeligere å se for seg, når forskjellige oppgaver i programmet kjører selvstendig i parallell. Derfor er Java PRP(Parallell recursive procedures) laget for å være et program mellom brukerens sekvensielle program, og kompilatoren. Java PRP lager et parallelt program, basert på det sekvensielle programmet, uten at det har noe påvirkning på resultatet. Dette gjør at man kan muligens oppnå bedre kjøretider, uten at man må ta for seg den administrative koden selv. Denne versjonen av Java PRP har sett nærmere på påvirkningen av delte variabler i parallelle programmer, og hvordan dette kan håndteres. Løsningen er at Java PRP tar for seg faseoppdelte programmer, der hver fase har en parallell del og en sekvensiell del, der vi kan håndtere delte variabler i den sekvensielle delen, og dermed få full parallellitet i den parallelle delen. Denne masteroppgaven tar for seg tre eksempler, hvor vi sammenligner en sekvensiell versjon og Java PRP sin parallelle versjon. De to første, nemlig finn største tall i en mengde og Quicksort, er ikke kjørt i flere faser, men baserer seg på én metode. Det siste og største eksempelet er Delaunay triangulering, og er et større program i tre faser. I alle tre eksemplene får vi en speedup. Selve Java PRP programmet kan man finne på http://folk.uio.no/peterlei. Her finner man filen under navnet JavaPRP.java.