Programming Parallel Computers
MF: mediaanisuodatin
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 |
|---|---|---|---|---|---|---|
| MF1: perustason CPU-toteutus | ||||||
Toteuta yksinkertainen, perättäinen perusratkaisu. Varmista, että se toimii kuten pitääkin. Älä pyri tässä vaiheessa hyödyntämään rinnakkaisuutta missään muodossa. Tässä on tarkoitus käyttää suoraviivaista, naiivia algoritmia, joka laskee mediaanin erikseen kullekin pikselille lineaariaikaisella hakualgoritmilla. |
||||||
| – | – | 5 + 0 | ★ | Pak. | 2026-08-31 klo 23:59:59 | |
| MF2: moniytimellinen rinnakkaisuus | ||||||
Rinnakkaista tehtävän MF1 ratkaisu OpenMP:llä siten, että ratkaisussa hyödynnetään useita CPU-ytimiä rinnakkain. |
||||||
| – | – | 3 + 0 | ★ | Pak. | 2026-08-31 klo 23:59:59 | |
| MF9a: parempi algoritmi | ||||||
Suunnittele parempi algoritmi, joka ei laske mediaania uudelleen jokaiselle pikselille erikseen. Tee siitä mahdollisimman tehokas, myös erittäin suurikokoisille ikkunoille. Käytä kaikkia CPU:lta löytyviä resursseja. |
||||||
| – | – | 5 + 0 | ★★★ | Pak. | 2026-08-31 klo 23:59:59 | |
Yleiset ohjeet
Tässä tehtävässä toteutetaan kaksiulotteinen mediaanisuodatin suorakulmaisella suodatusikkunalla.
Rajapinta
Toteuta seuraava funktio:
void mf(int ny, int nx, int hy, int hx, const float* in, float* out)
Tässä in ja out osoittavat float-taulukoihin, joista kussakin on ny*nx alkiota. Funktion kutsuja varaa taulukot, joten muistinhallintaa ei tarvita.
Pikselin (x,y) alkuperäinen arvo on taulukossa in[x + nx*y] ja sen uusi arvo tallennetaan taulukkoon out[x + nx*y].
Haluttu tuloste
Tulosteen pikseli (x,y) sisältää mediaanin kaikista pikseleistä koordinaateilla (i,j), joille
0 <= i < nx,0 <= j < ny,x - hx <= i <= x + hx,y - hy <= j <= y + hy.
Tämä on liukuva ikkuna. Huomaa, että ikkunassa on enintään (2*hx+1) * (2*hy+1) pikseliä, mutta reunojen läheisyydessä pikseleitä on vähemmän.
Lisätietoja
Tässä tehtävässä vektorin a = (a1, a2, …, an) mediaani määritellään seuraavasti:
- Olkoon x1, x2, …, xn a:n arvoja kasvavassa järjestyksessä.
- Jos n = 2k + 1, a:n mediaani on xk+1.
- Jos n = 2k, a:n mediaani on (xk + xk+1)/2.
Esimerkkejä
Alla olevat esimerkit havainnollistavat, mitä oikein toteutettu ohjelma tekee, kun sitä sovelletaan bittikarttakuvan kuhunkin värikomponenttiin. Näissä esimerkeissä kullekin värikomponentille kunkin pikselin arvo on liukuvan ikkunan (mitat (2k+1) × (2k+1)) sisällä olevien pikseliarvojen mediaani. Vie hiiri tuloskuvien päälle nähdäksesi eroavaisuudet syötekuvan ja tuloskuvan välillä.
k = 1
k = 2
k = 5
k = 10
Kohinan poisto, k = 1
Kohinan poisto, k = 2
Vinkkejä tehtäviin MF1–MF2
Käytä mediaanin etsimiseen nopeaa valinta-algoritmia. Älä käytä lajittelua; quickselect ja muut hyvät valinta-algoritmit ovat paljon lajittelua nopeampia. Standardikirjastosta löytyy valmiiksi hyvä C++-toteutus, joten tätä ei tarvitse keksiä uudelleen.
Vinkkejä tehtävään MF9a
Tässä esimerkkitekniikoita tehtävän MF9a ratkaisemiseen:
- Jaa kuva pienempiin, osittain päällekkäisiin lohkoihin. Jos ikkunan koko on esimerkiksi 21 × 21, järkevä lohkon koko voisi olla 50 × 50. Ratkaise mediaanisuodatinongelma kullekin lohkolle erikseen; sijoita lohkot siten, että kukin tulostekuvan pikseli on peräisin tarkalleen yhdestä lohkosta. Ole tarkkana reunojen kanssa.
- Lajittele syötedata kunkin lohkon sisällä ja korvaa alkuperäiset arvot niiden järjestysluvuilla. Samanarvoiset luvut voi järjestää keskenään vapaasti, esimerkiksi jos syötedata oli (1.0, 1.0, 0.1, 0.9, 0.5, 0.2, 1.0), muuta se seuraavanlaiseksi: (4, 5, 0, 3, 2, 1, 6). Näin tehtävästä tulee paljon yksinkertaisempi: liukulukujen sijaan mediaani etsitään pienistä, toisistaan eroavista kokonaisluvuista.
- Nyt liukuvan ikkunan voi esittää bittivektorina. Esimerkiksi jos lohkon koko on 50 × 50, liukuva ikkuna voidaan esittää 2500 bitin vektorina. Älä laske kokonaan uutta bittivektoria kullekin ikkunan sijainnille — kun ikkuna siirtyy pisteestä (x,y) pisteeseen (x+1,y), tarvitsee vain nollata 2k+1 bittiä ja asettaa 2k+1 bittiä.
- Hyödynnä bittirinnakkaisuutta ja bittien käsittelyyn tarkoitettuja CPU-käskyjä. Mediaanin tehokkaaseen etsintään bittivektorista voi käyttää esimerkiksi funktioita __builtin_popcountll (POPCNT-käsky), __builtin_ctzll (TZCNT-käsky) ja _pdep_u64 (PDEP-käsky). Esilaskettujen arvojen tallentaminen välimuistiin saattaa myös olla hyödyksi.
- Kiinnitä huomiota muistiviittausten paikallisuuteen. Onko esimerkiksi järkevämpää liikuttaa ikkunaa vasemmalta oikealle vai ylhäältä alas?
- Voit käyttää OpenMP:tä useiden lohkojen käsittelemiseen rinnakkain.