MateriaaliTehtävät

Programming Parallel Computers

Kurssit Aalto 2026Kirjaudu sisäänApua

Aalto 2026

Sisällysluettelo Kilpailu PalautuksetPre 0CP 1 2a 2b 2c 3a 3b 4 5 9aIS 2 4 6a 6b 9aMF 1 2 9aSO 4 5 6LLM 9aP 9aX 0a 0b 9a 9b

CP: korrelaatioparit

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	Alustavat pisteet	Pisteet	Max.	Taso	Suos.	Määräaika
CP1: perustason CPU-toteutus
Toteuta yksinkertainen, peräkkäinen ratkaisu. Älä pyri tässä vaiheessa hyödyntämään rinnakkaisuutta missään muodossa; keskity siihen, että koodi toimii oikein. Käytä kaikissa laskutoimituksissa kaksinkertaisen tarkkuuden liukulukuja. Automaattinen vektorointi ei ole käytössä tässä tehtävässä.
	–	–	–	5 + 0	★	Suos.	2026-04-26 klo 23:59:59
CP2a: käskytason rinnakkaisuus
Hyödynnä käskytason rinnakkaisuutta CP1-tehtävän ratkaisusi rinnakkaistamiseen. Varmista, että suoritustehon kannalta keskeisimmät operaatiot on liukuhihnoitettu tehokkaasti. Älä käytä vielä muita rinnakkaisuuden muotoja. Käytä kaikissa laskutoimituksissa kaksinkertaisen tarkkuuden liukulukuja. Automaattinen vektorointi ei ole käytössä tässä tehtävässä.
	–	–	–	3 + 0	★	Suos.	2026-05-03 klo 23:59:59
CP2b: moniytimellinen rinnakkaisuus
Rinnakkaista CP1-tehtävän ratkaisusi OpenMP:n ja useiden säikeiden avulla siten, että toteutuksessa hyödynnetään rinnakkain useita CPU-ytimiä. Älä käytä vielä muita rinnakkaisuuden muotoja tässä tehtävässä. Käytä kaikissa laskutoimituksissa kaksinkertaisen tarkkuuden liukulukuja. Automaattinen vektorointi ei ole käytössä tässä tehtävässä.
	–	–	–	3 + 0	★	Suos.	2026-05-03 klo 23:59:59
CP2c: vektorointi
Rinnakkaista CP1-tehtävän ratkaisusi vektorioperaatioiden avulla siten, että yhdellä käskyllä voidaan suorittaa useita aritmeettisia operaatioita. Älä käytä vielä muita rinnakkaisuuden muotoja. Käytä kaikissa laskutoimituksissa kaksinkertaisen tarkkuuden liukulukuja. Automaattinen vektorointi ei ole käytössä tässä tehtävässä.
	–	–	–	3 + 0	★	Suos.	2026-05-03 klo 23:59:59
CP3a: nopea double-tyypin ratkaisu
Käytä kaikkia CPU:n resursseja ja tee ratkaisustasi mahdollisimman nopea. Hyödynnä mahdollisuuksien mukaan käskytason rinnakkaisuutta, useita säikeitä sekä vektorikäskyjä. Optimoi myös muistihaut. Käytä kaikissa laskutoimituksissa kaksinkertaisen tarkkuuden liukulukuja.
	–	–	–	5 + 2	★★	Suos.	2026-05-10 klo 23:59:59
CP3b: nopea float-tyypin ratkaisu
Käytä kaikkia CPU:n resursseja ja tee ratkaisustasi mahdollisimman nopea. Hyödynnä mahdollisuuksien mukaan käskytason rinnakkaisuutta, useita säikeitä sekä vektorikäskyjä. Optimoi myös muistihaut. Tässä tehtävässä saa käyttää yksinkertaisen tarkkuuden liukulukuja.
	–	–	–	5 + 2	★★	Suos.	2026-05-10 klo 23:59:59
CP4: perustason GPU-toteutus
Toteuta perustason ratkaisu GPU:lle. Varmista, että koodi toimii oikein ja on kohtuullisen tehokas. Toteuta kaikki suoritustehon kannalta keskeiset osiot GPU:lla; kevyempää esi- ja jälkikäsittelyä voi tehdä myös CPU:lla. Muista tarkistaa kaikki CUDA-operaatiot virheiden varalta. Tässä tehtävässä saa käyttää yksinkertaisen tarkkuuden liukulukuja.
	–	–	–	5 + 0	★	Suos.	2026-05-17 klo 23:59:59
CP5: nopea GPU-ratkaisu
Käytä kaikkia GPU:n resursseja ja tee ratkaisusta mahdollisimman nopea. Tässä tehtävässä saa käyttää yksinkertaisen tarkkuuden liukulukuja.
	–	–	–	10 + 2	★★	Suos.	2026-05-24 klo 23:59:59
CP9a: parempi algoritmi
Yritä käyttää Strassenin algoritmia matriisitulojen laskemisen nopeuttamiseksi. Toteuta tehtävän CP3b ratkaisusi uudelleen Strassenin algoritmin perusajatusta hyödyntäen. Riittää, että hyödynnät Strassenin algoritmia (tehtävään sopeutettuna) ylimmillä rekursiotasoilla; tämän jälkeen voit taas käyttää naiivia algoritmia. Pelkkä naiivin algoritmin käyttö ei riitä, vaikka ratkaisu olisikin riittävän nopea. Ole tarkkana pyöristysvirheissä. Saatat tarvita kaksinkertaisen tarkkuuden liukulukuja testien läpäisemiseksi.
	–	–	–	5 + 0	★★★	Suos.	2026-05-31 klo 23:59:59

Yleiset ohjeet

Syötteenä on m vektoria, joissa kussakin on n lukua. Tehtävänä on laskea korrelaatio jokaisen syötevektoriparin välillä.

Rajapinta

Toteuta seuraavanlainen funktio:

void correlate(int ny, int nx, const float* data, float* result)

Tässä data on osoitin, joka viittaa syötematriisiin, jossa on ny riviä ja nx saraketta. Kun 0 <= y < ny ja 0 <= x < nx, rivin y ja sarakkeen x alkio on tallennettu taulukon alkioon data[x + y*nx].

Funktion tulee laskea syötematriisin rivien i ja j väliset korrelaatiokertoimet kaikille i:n ja j:n arvoille, kun 0 <= j <= i < ny, ja tallentaa tulos taulukon alkioon result[i + j*ny].

Huomaa, että korrelaatio on symmetrinen, jolloin riittää laskea pelkkä tulosmatriisin yläkolmio. Alakolmiota i < j ei tarvitse määrittää.

Taulukot data ja result ovat funktion kutsujan valmiiksi varaamia, joten niiden suhteen ei tarvitse erikseen tehdä muistinhallintaa. Huomaa, että funktion kutsuhetkellä taulukko result ei sisällä kelvollisia arvoja. Huomaa erityisesti, ettei sitä välttämättä ole alustettu arvoilla 0.

Lisätietoja

Syöte ja tulos annetaan aina yksinkertaisen tarkkuuden liukulukuina (tyyppi float). Tehtävästä riippuen joissakin laskutoimituksissa käytetään kuitenkin myös kaksinkertaisen tarkkuuden liukulukuja.

Jos tehtävässä ohjeistetaan käyttämään kaksinkertaisen tarkkuuden liukulukuja, kaikissa aritmeettisissa operaatioissa on käytettävä tyyppiä double. Samoin kaikki välitulokset tulee tallentaa tyypin double-muuttujiin. Vasta lopullinen tulos pyöristetään yksinkertaisen tarkkuuden liukuluvuksi.
Jos tehtävän ohjeissa sallitaan yksinkertaisen tarkkuuden liukulukujen käyttö, on hyvä käyttää float-tyyppiä aina, kun mahdollista.

Varmista kuitenkin aina, että tulosten numeerinen tarkkuus on riittävä. Arviointityökalu tarkistaa, että virhemarginaali on riittävän pieni. Usein suoraviivainen ja tehokas toteutus on myös riittävän tarkka. Jos kuitenkin pyöristysvirheet tuottavat päänvaivaa, kurssihenkilökunta antaa mielellään lisäohjeita.

Esimerkkejä

Näistä esimerkeistä näet, miltä oikeanlainen toteutus näyttää bittikarttakuvaan sovellettuna.

Syöte (kuva 1): vektori i = kuvan rivi i
Tuloste (kuva 2): punainen pikseli pisteessä (i, j) = positiivinen korrelaatio rivien i ja j välillä, sininen pikseli = negatiivinen korrelaatio

Vinkkejä

Järkevä tapa laskea parittaiset korrelaatiot:

Normalisoi ensin syöterivit siten, että jokaisen rivin aritmeettinen keskiarvo on 0. Ole tarkkana, ettet muuta tässä pareittaisia korrelaatioita.
Normalisoi sitten syöterivit siten, että jokaisella rivillä alkioiden neliöiden summa on 1. Tarkista tässäkin, että pareittaiset korrelaatiot eivät muutu.
Olkoon X normalisoitu syötematriisi.
Laske matriisitulo Y = XX^T (yläkolmio riittää).

Kaikki korrelaatioparit ovat nyt matriisissa Y. Ainoa laskennallisesti raskas vaihe on matriisitulon laskenta. Normalisoinnit voidaan tehdä lineaariajassa.