Lue ensin tällä sivulla olevat yleisohjeet. Tarkemmat tiedot löytyvät tehtäväkohtaisista ohjeista. Jokaiseen tehtävään on saatavilla oma zip-tiedosto, josta löytyvää koodia voit käyttää ratkaisujesi pohjana.
| Tehtävä | Palautuksia | Pisteet | Max. | Taso | Pak. | Määräaika |
|---|---|---|---|---|---|---|
| SO4: lomituslajittelu | ||||||
Toteuta tehokas rinnakkainen lajittelualgoritmi CPU:lle, joka perustuu lomituslajitteluun (merge sort). |
||||||
| – | – | 5 + 0 | ★+ | Pak. | 2025-08-31 klo 23:59:59 | |
| SO5: pikalajittelu | ||||||
Toteuta tehokas rinnakkainen lajittelualgoritmi CPU:lle, joka perustuu pikalajitteluun (quicksort). |
||||||
| – | – | 5 + 0 | ★+ | Pak. | 2025-08-31 klo 23:59:59 | |
| SO6: nopea GPU-ratkaisu | ||||||
Toteuta tehokas rinnakkainen lajittelualgoritmi GPU:lle. Mikä tahansa lajittelualgoritmi käy, mutta kantalukulajittelu (radix sort) voi olla yksinkertaisin valinta. |
||||||
| – | – | 5 + 0 | ★★★ | Pak. | 2025-08-31 klo 23:59:59 | |
Tässä tehtävässä toteutetaan rinnakkaisia lajittelualgoritmeja, jotka suoriutuvat paremmin kuin yksisäikeinen std::sort.
Määritettynä on seuraava 64-bittistä etumerkitöntä kokonaislukua edustava tietotyyppi:
typedef unsigned long long data_t;
Toteuta seuraava funktio:
void psort(int n, data_t* data)
Tässä n merkitsee syötetaulukon data kokoa. Kaikki syötealkiot ovat tyyppiä data_t, eli 64-bittisiä etumerkittömiä kokonaislukuja.
Funktion tulee käyttäytyä täsmälleen samoin kuin:
std::sort(data, data+n);
Eli funktion kutsumisen jälkeen taulukon tulee olla järjestetty. Voit tarpeen mukaan allokoida ylimääräistä muistia välitulosten tallentamista varten.
Toteutuksessa on sallittua ja toivottavaa käyttää C++-standardikirjaston yksisäikeisiä funktioita. Koodissa voi vapaasti käyttää esimerkiksi yksisäikeistä std::sort-funktiota sekä muita algoritmikirjastosta löytyviä työkaluja.
Monisäikeistämistä varten voi käyttää OpenMP:n primitiivejä.
Älä määrittele (hard-code) säikeiden määrää, vaan anna OpenMP:n tehdä tämä valinta ja käytä säikeiden lukumäärän selvittämiseksi esimerkiksi funktioita omp_get_max_threads ja omp_get_num_threads. Näin koodisi on automaattisesti yhteensopiva esimerkiksi OMP_NUM_THREADS-ympäristömuuttujan kanssa. Koodin tulee toimia kohtuullisen tehokkaasti, kun säikeiden määrä on 1–20, ja sen tulee toimia oikein myös suuremmilla määrillä säikeitä. Ohjelma ei saa kaatua, jos esimerkiksi OMP_NUM_THREADS muutetaan 20:sta 21:een, eikä se saa välittömästi palata yksisäikeiseen toteutukseen, jos OMP_NUM_THREADS muutetaan 20:sta 19:ään.
GPU-tehtävässä on käytettävä tavallista CUDA-rajapintaa. Esimerkiksi Thrust-kirjastoa ei ole lupa käyttää.
Lomituslajittelutehtävässä (merge sort) ja pikalajittelutehtävässä (quicksort) voi hyvin käyttää yksisäikeistä std::sort-funktiota perustapauksessa (riippumatta siitä, mitä algoritmia standardikirjasto sattuu käyttämään oletusarvona); olennaista on, että monisäikeiset osuudet perustuvat tehtävän mukaisesti lomituslajitteluun tai pikalajitteluun. Lomitusta (merging) ja ositusta (partitioning) varten voi vapaasti käyttää mitä tahansa strategiaa, ja myös esimerkiksi vektorikäskyjen käyttäminen on suositeltavaa aina, kun mahdollista.