Rinnakkaisten järjestysalgoritmien ajan- ja energiankäyttö

Abstract

Järjestysalgoritmit ovat laaja-alaisesti käytettyjä erilaisissa sovelluksissa ja niitä on tutkittu laaja-alaisesti jo vuosikymmenien ajan varsinkin ajankäytön kannalta. Koska prosessorien suoritusnopeudet alkavat saavuttaa teoreettista huippuaan, rinnakkaislaskennasta on tullut tärkeä työkalu suoritusnopeuden kasvattamiseen. Tämän työn tavoitteena on selvittää mitkä järjestysalgoritmit hyötyivät suoritusnopeudeltaan rinnakkaistetusta toteutuksesta, sekä mikä oli rinnakkaistettujen algoritmien energiankäyttö verrattuna sarjallistettuihin versioihin. Työ on kirjallisuustutkielma, jossa käydään läpi tutkimuksia rinnakkaistetuista järjestysalgoritmeista, jotka on toteutettu eri teknologioilla sekä eri alustoilla. Käytettyjä teknologioita olivat OpenCL, CUDA sekä OpenMP, ja tukitut algoritmit olivat bitonic sort, odd-even sort, quicksort, rank sort sekä shell sort. Työssä käydään läpi rinnakkaislaskennan sekä järjestysalgoritmien teoriaa, jonka jälkeen vertaillaan tutkimusten tuloksista mitkä algoritmit ja millä syöteko’oilla hyötyivät rinnakkaistetusta toteutuksista, miten ne vertautuivat toisiinsa ja mikä oli rinnakkaistetun version energiankäyttö verrattuna sarjallistettuun versioon. Työssä huomattiin, että näytönohjaimia hyödyntävien järjestysalgoritmien energiankulutuksesta on niukalti tutkimusta. Tutkimuksista selvisi, että varsinkin algoritmin datariippuvuudet vaikuttivat rinnakkaistamisesta saatuun hyötyyn. Esimerkiksi bitonic sort nopeutui huomattavasti rank sortiin ja odd-even sortiin verrattuna OpenCL:llä toteteutetuilla näytönohjaimia hyödyntävissä sovelluksissa kaikilla syöteko’oilla. Esimerkiksi 217:llä alkiolla bitonic sortin suoritusaika oli alle sekuntin verrattuna odd-even sortin sekä ranked sortin yli 100:aan sekuntiin. OpenMP:llä toteutetuista moniytimistä prosessoria hyödyntävistä algoritmeista quicksort hyötyi eniten vasta tarpeeksi suurilla syöteko’oilla. 10000:lla alkiolla quicksortin ajankäyttö kasvoi neljää ja kahdeksaa ydintä hyödyntäessä. Nopeutus kuitenkin kasvoi alkiomäärän kasvaessa yli 100000:een. Energiankäytöstä löytyi vain OpenMP:llä toteutettu moniytimistä prosessoria hyödyntäviä algoritmeja tutkinut tutkimus. Tutkimuksessa todettiin, että jos algoritmin rinnakkaistoteutus oli ajallisesti tehokkaampi kuin sarjallinen tutkimus, niin se oli myös energiankäytöltään tehokkaampi. Syyksi arvioitiin, että koko tietokoneen energiankäyttö on huomattavaan suuri osa verrattuna useamman ytimen energiankäyttöön.