Lajittelualgoritmien rinnakkaistaminen GPU-arkkitehtuurilla

Abstract

Datan määrän yhä kasvaessa lajittelualgoritmien tehokas hyödyntäminen on ollut lukuisten tutkimusten kohteena. Tässä tutkielmassa keskitytään pikalajittelun ja kantalukulajittelun rinnakkaistamiseen GPU-arkkitehtuurilla. Käytetyt lähteet keskittyvät NVIDIAn GPU-laitteiden ja CUDA-ohjelmointirajapinnan hyödyntämiseen toteutuksissaan. Tutkielmassa on myös esitetty CUDAn toimintaa ja arkkitehtuuria lyhyesti. Lajittelualgoritmien toimintaperiaate käydään läpi ennen tuloksien tarkastelemista. Lajittelualgoritmien rinnakkaistaminen on toteutettu kaikissa tutkielmassa käsiteltävissä algoritmeissa siten, että lajiteltava data osioidaan jollakin kyseiselle algoritmille sopivalla tavalla sopiviin osioihin, jotka jaetaan säielohkoille ja niiden sisällä sijaitsevien säikeiden työstettäväksi. Eri lajittelualgoritmeilla on erilaisia tapoja, kuinka ne suorittavat tehokkaasti lajittelun useilla säikeillä. Molemmissa lajittelualgoritmeissa rinnakkaistaminen GPU-arkkitehtuurilla on tuonut merkittäviä suoritusaikojen parannuksia. Eri vuosina toteutettujen tutkimusten väliset vertailut paljastuivat kuitenkin ongelmallisiksi, sillä parissakin eri lähteessä oli epäuskottavat tulokset. Vaikuttaisi siltä, että niissä on tapahtunut jonkinlainen merkintävirhe tai artikkelissa on mahdollisesti jätetty jotain olennaista kertomatta, mistä suoritusajat kokonaisuudessaan koostuvat. Lähteiden sisällä olevat suoritusaikojen vertailut kuitenkin vaikuttivat loogisilta ja mahdollisilta.