Rinnakkaislaskenta



Rinnakkaislaskennan ideana on jakaa laskennallinen ongelma pienempiin samanaikaisesti suoritettaviin aliongelmiin suorituskyvyn parantamiseksi.




Useat laskentayksiköt voivat sitten ratkaista aliongelmia samanaikaisesti eli rinnakkain. Nykyaikaisissa suorittimissa laskentayksikkö on tavallisesti yksi suoritinydin.

Rinnakkaislaskenta lyhentää muun muassa tietyn ongelman laskenta-aikaa. Esimerkiksi sääennusteet, jotka perustuvat vahvasti sääsimulaatioihin, eivät olisi valmiita ajoissa, jos ne laskettaisiin vain yhdellä ytimellä. Jos ongelma jaetaan useisiin alitehtäviin ja ne lasketaan erikseen, laskenta-aika lyhenee merkittävästi. Seuraavan viikon sää voidaan siten ennustaa etukäteen.

Rinnakkaislaskennan mittakaava on 90-luvulta lähtien kasvanut supertietokoneiden lisääntyvän virrankulutuksen rajoittamiseksi. Lämmöntuotanto pysyy hallittavana, kun useita alitehtäviä lasketaan samanaikaisesti useilla eri laskentayksiköillä. Myöhemmin alitehtävien tulokset yhdistetään varsinaisen ongelman ratkaisemiseksi. Rinnakkaislaskennalla on myös muita etuja, joita tarkastellaan tarkemmin tämän kurssin aikana.



Se, miten ongelma jaetaan pienempiin alitehtäviin, riippuu täysin tapauksesta. Tähän on olemassa erilaisia paradigmoja ja ohjelmointitapoja. Myöhemmin tarkastelemme muutamia niistä vähän tarkemmin.

Lisätietoja on videossa Johdanto rinnakkaisohjelmointiin.

https://www.youtube.com/watch?v=aucZUdvkVyI

Videon tekstit suomeksi

Videon tekstit suomeksi

Tällä videolla kerromme
00:01 rinnakkaisohjelmoinnista. Esittelemme
00:03 rinnakkaisohjelmoinnin perusteet,
00:04 ja siirrymme sitten esimerkkeihin
00:06 taulukon alkioiden summaamisesta ja kuvankäsittelystä.
00:08 Perinteisesti tietokoneet ovat keskittyneet
00:10 suorittamaan ohjelmat peräkkäisesti.
00:12 Ohjelmat on jaettu
00:13 erillisiin komentoihin, jotka
00:14 prosessori suorittaa yksi kerrallaan, kun taas
00:18 rinnakkaisohjelmoinnissa ohjelmoija
00:19 tekee aliohjelmia.
00:20 Jokainen niistä suoritetaan
00:22 omalla erillisellä prosessorillaan.
00:24 Rinnakkaisohjelmoinnissa suoritetaan
00:26 useita komentoja samanaikaisesti,
00:27 mikä vaatii koordinointia.
00:29 Kun katsellaan
00:31 prosessoreiden kehittymistä vuodesta 1970 vuoteen 2018,
00:34 havaittavissa on tietokoneen ytimien lukumäärän
00:36 ja kellotaajuuden kasvu.
00:39 Samalla transistorien lukumäärä on
00:41 kaksinkertaistunut joka toinen vuosi vuodesta
00:42 1970 vuoteen 2018. On tärkeää
00:44 huomata, että x-akseli on lineaarinen ja
00:46 y-akseli on logaritminen. Tästä
00:49 kuvasta voi nähdä, että ennen vuotta 2003
00:51 tietokoneista tehtiin nopeampia
00:53 kasvattamalla transistoreiden lukumäärää ja kellotaajuutta.
00:54 Mutta vuodesta 2003 eteenpäin prosessorit
00:56 olivat jo niin täynnä transistoreita,
00:58 että kellotaajuuden nostaminen
01:00 suorituskyvyn parantamiseksi ei enää
01:01 onnistunut, sillä prosessoreista tulisi liian
01:02 kuumia. Näin ollen prosessorien tehon nostamiseksi
01:04 valmistajat lisäsivät ytimiä ja
01:06 pitävät kellotaajuuden suunnilleen samana, mikä on
01:08 johtanut rinnakkaisohjelmoinnin kehittymiseen.
01:09 Tässä on esimerkki
01:13 taulukon alkioiden summaamisesta.
01:15 Taulukossa on lukuja yhdestä
01:17 30:een ja tehtävänämme on
01:18 laskea nämä luvut yhteen.
01:21 Peräkkäin toimittaessa kävisimme läpi
01:22 läpi koko listan ja summaisimme jokaisen
01:23 luvun yksitellen, kunnes saisimme lopullisen summan.
01:27 Rinnakkaisohjelmoinnissa sen sijaan voimme
01:29 jakaa taulukon kahteen
01:30 kahdeksan numeron listaan ja laskea listakohtaiset summat
01:33 erikseen ja rinnakkain.
01:34 Sitten voimme
01:36 laskea ne lopuksi yhteen
01:37 ja saamme lopullisen summan. Meidän ei ole pakko
01:39 luoda kahta kahdeksan luvun listaa. Jos haluamme,
01:41 voimme tehdä neljä neljän luvun tai
01:43 kahdeksan kahden luvun listaa.
01:45 Seuraavaksi vaikeampi esimerkki, jossa
01:47 käytetään kuvasuodattimia. Oletetaan, että haluamme
01:49 käyttää Laplace-suodatinta kuvaan.
01:51 Tätä suodatinta käytetään havaitsemaan
01:54 reunat valokuvissa. Suodatin toimii niin, että
01:56 se muokkaa kuvan jokaisen pikseliarvon
01:58 ympäröivien pikseleiden pohjalta ja
01:59 luo Laplace-kuvan.
02:01 Jos käytämme suodatinta
02:03 numeroon kolme oikealla olevan
02:05 Laplace-matriisin perusteella, saamme arvoksi
02:06 miinus yksi.
02:07 Tämän jälkeen etsimme pienimmän ja
02:09 suurimman arvon uudesta pikselitaulukosta ja
02:11 normalisoimme sen. Voimme
02:13 rinnakkaistaa menetelmän jakamalla kuvan
02:15 riveihin tai sarakkeisiin, ja sen jälkeen
02:17 liittää osat ja normalisoida
02:18 jälkikäteen. Koska
02:21 jokainen rivi tai sarake tarvitsee tietoa
02:22 oman osuutensa ulkopuolelta, tämä on
02:24 huomattavasti vaikeampaa verrattuna
02:26 edellisen esimerkin rivien yhteenlaskuun.
02:27 Normalisointia ei myöskään voida tehdä ennen kuin
02:29 Laplace-suodatinta on käytetty jokaiseen
02:31 yksittäiseen pikseliin, joten tässä tavassa
02:32 voi syntyä myös pullonkauloja.
02:34 Yhteenvetona on tärkeää tietää myös,
02:36 että rinnakkaisprosessointia voi tapahtua sekä ohjelmallisesti että laitteistossa
02:37 vaikka tässä videolla onkin
02:39 käsitelty vain rinnakkaisohjelmointia.
02:40 Kun tarkastellaan kahta edellistä
02:42 esimerkkiä, joissa käsitellään kuvansuodatusta ja
02:43 taulukon alkioiden summausta, voidaan ymmärtää,
02:45 että joitain ohjelmia on erittäin vaikea
02:47 rinnakkaistaa. Erityisesti tämä näkyy
02:48 esimerkissä, jossa on kuvasuodatusta, sillä
02:50 normalisointia voidaan käyttää vasta kun
02:52 kaikille pikseleille on käytetty
02:53 Laplace-suodatinta. Tämä tarkoittaa,
02:55 että rinnakkaistamisen hyödyt
02:56 ovat rajalliset.
02:58 Suoritusnopeuden kasvua kuvaa Amdahlin laki, jossa
03:00 nopeutuminen on yksi jaettuna yksi vähennettynä P:llä.
03:02 P on osuus koodista, joka
03:03 tosiasiallisesti on mahdollista suorittaa rinnakkain.
03:05 Tähän päättyy video
03:06 rinnakkaisohjelmoinnista. Kiitos, kun katsoit!


Esimerkki: Kuinka summa lasketaan rinnakkaislaskennassa?

Oletetaan, että Alice ja Bob haluavat laskea 20 luvun summan, esimerkiksi ruokaostosten hinnan. Joko Alice tai Bob voisi suorittaa laskutoimituksen yksin, aivan kuten yksi suoritinydin, ja laskea sen peräkkäisesti. Mutta kuinka he voisivat tehdä sen rinnakkain?

Laskeakseen summan rinnakkain Alice ja Bob voisivat jakaa luvut puoliksi, minkä jälkeen kumpikin laskisi oman puolikkaansa summan (kuva alla). Tämän jälkeen heidän tarvitsisi vain laskea osasummat yhteen saadakseen kaikkien lukujen kokonaissumman. Jos Alicen yksin suorittamassa laskennassa kestäisi enintään 20 sekuntia, Alice ja Bob voisivat yhdessä ratkaista ongelman vain 10 sekunnissa, jos heillä on suunnilleen samat matemaattiset taidot. Lisäksi, jos kumpikin heistä pystyisi yksinkin laskemaan 20 lukua, yhdessä he voisivat käsitellä 40 lukua. Tällainen rajoitus voisi johtua tietokoneen laskentayksikön käytettävissä olevan muistin määrästä.

Alicen ja Bobin ongelma havainnollistaa rinnakkaislaskennan kahta etua: rinnakkaislaskenta nopeuttaa laskemista ja mahdollistaa suuremmat laskelmat.