Abstract
Moderne datamaskiner blir stadig mer parallelle. Det er nå vanlig at prosessorer har alt fra 2 til 8 kjerner. I tillegg blir det også mer vanlig å benytte skjermkort som en medprosessor for enkelte typer beregninger. Dette betyr at det i økende grad blir viktig for oss som utviklere å ta hensyn til parallelle arkitekturer dersom vi ønsker god ytelse i applikasjonene våre.
I denne oppgaven vil vi forsøke å parallellisere algoritmer både for flerkjerne-CPU og for GPU. Samtidig ser vi nærmere på ett av informatikkens mest fundamentale problemer, nemlig sortering. Vi ser på flettesortering og venstre-radix-sortering, og undersøker hvordan disse algoritmene kan parallelliseres. Samtidig leter vi etter generelle metoder for å parallellisere algoritmer.
Gjennom arbeidet vår ser vi at det på flerkjerne-CPU er lett å oppnå en viss grad av parallellitet. Samtidig ser vi at det er vanskelig å skrive algoritmer som skalerer godt når antall kjerner øker. På skjermkort ser vi at det er svært mye vanskeligere å skrive effektive algoritmer, og at det er færre bruksområder hvor det lønner seg.
Modern computer systems are becoming increasingly parallel. It's now common with everything from 2 to 8 cores in modern processors. It's also increasingly common to use GPUs as coprocessors for certain types of computations. This means it's becoming increasingly important for us as developers to consider parallel architectures in order to achieve good efficiency in our applications.
In this thesis we will attempt to make parallel algorithms for both multicore CPU and GPU. We will look at one of the most fundamental problems in computer science, namely sorting. We look at merge sort and MSB radix sort, and examine ways of making them parallel. At the same time we look for general methods for making algorithms parallel.
Through our work we see that it's easy to achieve some degree of parallelism on multicore CPU. Unfortunately we also see that it's difficult to write algorithms that scale well when the number of cores increase. On GPUs we see that it's much more difficult to write efficient algorithms, and that there are fewer situations where such algorithms are beneficial.