Käsitteet

Rinnakkaisskaalautuminen

Kun syötettyjen tietojen koko pidetään vakiona ja laskentayksiköiden määrää lisätään, puhutaan tavallisesti vahvasta rinnakkaisskaalautumisesta. Rinnakkaisohjelmoinnin tarkoituksena on tässä tapauksessa lyhentää ongelman ratkaisuaikaa. Rinnakkaisnopeutus voidaan määritellä seuraavasti:

$ S = \frac{Ts}{T{p}}, $

jossa $Ts$ on suoritusaika peräkkäin tai yhdellä laskentayksiköllä ja $Tp$ on suoritusaika $p$ laskentayksiköllä.

Ihanteellisessa tilanteessa nopeutuksen tulisi olla suoraan verrannollinen laskentayksiköiden määrään (kuva alla). Jos esimerkiksi Alice ja Bob kutsuisivat matemaattisesti yhtä lahjakkaat ystävänsä Joen ja Lucyn auttamaan lukujen yhteenlaskussa, laskutoimitus kestäisi vain viisi sekuntia verrattuna 20 sekuntiin Alicen laskiessa kaiken yksin. Valitettavasti tosielämän ongelmissa asiat eivät usein mene näin. Itse asiassa laskentayksiköiden määrän lisääminen tietyn käännepisteen yli voi pidentää suoritusaikaa.



Kuten aiemmin todettiin, rinnakkaislaskentaa käytetään paitsi ongelmanratkaisun nopeuttamiseen myös laajempien tai tarkempien ongelmien tutkimiseen. Näissä tilanteissa sekä tietojen että laskentayksiköiden määrää lisätään samanaikaisesti, jolloin puhutaan heikosta rinnakkaisskaalautumisesta. Ihanteellisessa heikon skaalautumisen tapauksessa suoritusaika pysyy vakiona, kun tietojen ja laskentayksiköiden määrää lisätään samassa suhteessa. Jos Alice esimerkiksi haluaisi laskea yhteen 80 lukua 20 luvun sijaan ja pyytäisi Bobia, Joeta ja Lucya auttamaan, ihannetapauksessa 20 sekuntia riittäisi, aivan kuten alkuperäisessä ongelmassakin.

Vahvan skaalautumisen kaltaisesti ihanteellinen heikko skaalaus on harvoin toteutettavissa tosielämän ongelmissa, vaikka hyvä heikko skaalautuminen on yleensä helpompi saavuttaa kuin hyvä vahva skaalautuminen.




Rinnakkaisskaalauksen rajoitukset

Useat tekijät voivat rajoittaa skaalautuvuutta. Yleensä rinnakkaisohjelman on suoritettava joitakin lisätoimia, joita peräkkäisohjelman ei tarvitse tehdä. Laskutoimituksia voi olla tarpeen toistaa, tietoja on ehkä siirrettävä tai joitain laskentayksiköitä mahdollisesti synkronoitava. Jos työkuorman jakautumisessa on epätasapainoa, suoritusaikaa rajoittaa hitain suoritusyksikkö, koska muiden on odotettava, että se saa työnsä valmiiksi. Ohjelmassa voi olla myös peräkkäisiä osia (eli osia, joita ei voi rinnakkaistaa). Jos määrittelemme ongelman murto-osan, joka voidaan rinnakkaistaa pfpf, suurin mahdollinen nopeutus (ns. Amdahlin laki) on

$ S
{max} = \frac{1}{1 - p_f} $

Jos esimerkiksi vain 90 % ongelmasta voidaan rinnastaa, suurin mahdollinen nopeutus on 10 käytettyjen suoritinytimien määrästä riippumatta.

Yhteenvetona voidaan todeta, että suurimmat rinnakkaisskaalautuvuutta rajoittavat syyt ovat seuraavat:

  • rinnakkaistamisen yleishäviöt
  • ylimääräiset laskutoimitukset
  • tiedonsiirtoon ja synkronointiin kuluva aika
  • epätasainen kuormitus
  • ongelman peräkkäisosat.


Havainnollistetaan nyt muutamia näistä rajoituksista Alicen ja hänen ystäviensä avulla ja oletetaan, että kahden luvun yhteen laskeminen vie aikaa yhden sekunnin ja yhden luvun ilmoittaminen 0,1 sekuntia. Jos Alice tekisi laskutoimituksen yksin, tuloksen saavuttaminen veisi 19 sekuntia, kun käsiteltäviä lukuja on yhteensä 20 (eli $T_s=19Ts=19$, jossa luku 19 ilmaisee suoritettavien laskutoimitusten määrää). Jos hän työskentelee yhdessä Bobin kanssa, molemmat voivat laskea 10 lukua samanaikaisesti yhdeksässä sekunnissa, jos ei oteta huomioon työn valmisteluun ja jakamiseen tarvittavaa aikaa. Bobin on kuitenkin ilmoitettava osatuloksensa Alicelle, ja Alicen on suoritettava lopullinen yhteenlasku. Tarvittava kokonaisaika on siis

$ T_2 = 9 + 0.1 + 1 = 10.1 $

Kun Joe ja Lucy tulevat avuksi, kukin näistä neljästä henkilöstä voi laskea yhteen viisi lukua, mutta osasummien ilmoittamiseen Alicelle ja lopulliseen laskentaan tarvitaan enemmän aikaa:

$ T_4 = 4 + 3 \cdot 0.1 + 3 \cdot 1 = 7.3 $

Jos työntekijöiden määrää lisätään entisestään kahdeksaan henkilöön, eteen tulee uusi ongelma: 20 lukua ei voida jakaa tasaisesti kahdeksalle työntekijälle (20/8=2,5), minkä vuoksi kuormitus on epätasainen. Paras vaihtoehto on, että neljä henkilöä käsittelee kolme lukua ja toiset kaksi lukua (4⋅3+4⋅2=20). Koska kaikki rinnakkaiset työt on kuitenkin suoritettava ennen kuin Alice voi kerätä osatulokset ja yhdistää ne lopulliseksi tulokseksi (tällaista toimintoa kutsutaan reduktioksi), toiminnan "rinnakkainen aika" määräytyy kolmea lukua käsittelevien työntekijöiden mukaan, ja kokonaisaika on

$ T_8 = 2 + 7 \cdot 0.1 + 7 \cdot 1 = 9.7 $

Kahdeksalta työntekijältä menee siis enemmän aikaa kuin neljältä! Jos työnjako olisi tehty vähemmän älykkäällä tavalla, kuten jos seitsemän työntekijää käsittelisi kahta lukua ja yksi työntekijä kuutta lukua, tarvittava aika olisi 12,7 sekuntia, mikä olisi jopa hitaampaa kuin jos kaksi työntekijää laskisi kumpikin 10 lukua.

Tästä esimerkistä huomataan, että kun työntekijöitä on enemmän, yksittäisen työntekijän tarvitsema laskenta-aika lyhenee, mutta viestintäaika ja loppusumman saamiseen tarvittava aika kasvavat vastaavasti. Vaikka reduktio voidaan käytännössä tehdä hieman älykkäämmällä tavalla kuin mitä tässä on esitetty, se aiheuttaa kuitenkin rinnakkaistamisesta johtuvia yleishäviöitä. Yleisesti ottaen mitä pienemmiksi aliongelmat tehdään, sitä suuremmiksi kasvavat viestinnän ja kuormituksen epätasapainot. Jos ongelmana olisi esimerkiksi 1001 luvun yhteenlasku (edelleen jonkin verran epätasaista kuormitusta), yleishäviöt olisivat huomattavasti pienemmät:

$ T_s = 1000, $

$ T_8 = 125 + 7 \cdot 0.1 + 7 \cdot 1 = 132.7, $

ja

$ S = \frac{Ts}{T{8}} = 7.5 $

mitä pidettäisiin erittäin hyvänä rinnakkaisnopeutuksena.

Lisäksi jos tarkastellaan heikkoa skaalautuvuutta, jossa ongelman koko kasvaa 160 lukuun ja käytettävissä on kahdeksan työntekijää, tarvittava aika olisi $19 + 7 \cdot 0.1 + 7 \cdot 1 = 26.7 s$.

Vaikka useimmat tosielämän ongelmat ovat paljon monimutkaisempia kuin Alicen ja hänen ystäviensä ratkaisema ongelma, on selvää, että rinnakkaistamisesta johtuvien yleishäviöiden minimoiminen ja laskennan ja viestinnän välisen suhteen maksimoiminen voi olla erittäin haastavaa, kun samalla vielä pyritään säilyttämään hyvä kuormantasaus useita rinnakkaisia työntekijöitä käytettäessä.