Rinnakkaisuus

Wikipediasta
Siirry navigaatioon Siirry hakuun

Rinnakkaisuus (engl. concurrency, parallelism) tarkoittaa tietojenkäsittelytieteessä ongelman ratkaisemista siten, että sen osaongelmat ratkaistaan joko näennäisesti tai aidosti yhtä aikaa rinnakkaisissa laskennoissa.[1]

Laskennat voidaan suorittaa myös monessa tietokoneessa eli klusterissa, jolloin yleensä käytetään termiä hajautettu järjestelmä.

Eräissä tapauksissa erotellaan rinnakkaisuus (engl. parallel) ja yhtäaikaisuus (engl. concurrent) käsitteen selkeyden vuoksi. Esimerkiksi Flynnin luokittelussa SIMD-malli kuvataan rinnakkaisena mutta ei yhtäaikaisena, koska käsittelymalli ei sisällä vuoronnusta.

Rinnakkaisuustyypit

[muokkaa | muokkaa wikitekstiä]

Rinnakkaisuus voidaan jakaa kolmeen kategoriaan seuraavasti:

  • bittitason rinnakkaisuus
    • esimerkiksi suorittimen "dataleveys": 8-bittinen, 16-bittinen, 32-bittinen ja 64-bittinen suoritinarkkitehtuuri
  • käskytason rinnakkaisuus
    • rinnakkain kellojaksoa kohden suoritettavien käskyjen määrä (engl. instruction per clock cycle, IPC), superskalaariset suorittimet
    • riippuen myös mm. kääntäjästä ja suoritinarkkitehtuurista
  • tehtävätason rinnakkaisuus
    • yhtä tai useampaa ohjelmaa yhdelle tai useammalle datajoukolle
    • tehtävätasolla tyypillisesti käsitellä prosesseja ja säikeitä

Tehtävätason rinnakkaisuus

[muokkaa | muokkaa wikitekstiä]

Perinteisesti prosessi (engl. process) on tarkoittanut yhtä ajossa olevaa ohjelmaa. Rinnakkaisuus on tällöin sitä, että järjestelmässä on useita prosesseja ajossa yhtä aikaa. Näillä prosesseilla ei tarvitse olla mitään yhteistä, ja kukin niistä voi ratkaista omaa laskentaansa. Toisaalta prosessit voivat myös kommunikoida keskenään, jolloin niiden välille syntyy riippuvuuksia ja suoritettava laskenta on ainakin jossain määrin yhteinen. Käyttöjärjestelmän tehtävänä on suojata prosessit toisiltaan, tarjota niille mekanismeja keskinäiseen kommunikointiin ja päättää, mikä prosessi milloinkin on ajovuorossa (skedulointi, engl. scheduling eli vuoronnus).

Saman prosessin sisällä olevia rinnakkaisia itsenäisesti vuoronnettavia ohjelman osia kutsutaan yleensä säikeiksi (engl. thread), mutta myös termejä tehtävä (engl. task) ja kevytprosessi (engl. light-weight process) käytetään jonkin verran. Säie eroaa prosessista siten, että säikeellä ei ole omia resursseja kuten muistia, auki olevia tiedostoja ja niin edelleen, vaan se käyttää sen prosessin resursseja, johon se kuuluu. Säikeet ovat nykyään suosittu tapa toteuttaa laskennan rinnakkaisuutta yhden koneen sisällä, jos käyttöjärjestelmä tukee säikeitä.

Jos tietokoneessa on vain yksi suoritin, voi ainoastaan yksi prosessi (tai yksi säie) kerrallaan olla ajossa. Muut prosessit joutuvat odottamaan vuoroaan. Tämä ei aina aiheuta todellista hidastumista, sillä useimmat prosessit pyytävät välillä oheislaitteilta palvelupyyntöjä, joita ne joutuvat odottamaan. Odotuksen aikana voidaan hyvin suorittaa toista prosessia.

Mikäli tietokoneessa on useita suorittimia (moniprosessointi), voi ajossa olla niin monta prosessia (tai säiettä) kuin on suorittimiakin. Yleensä järjestelmän teho ei kuitenkaan kasva lineaarisesti suorittimien määrän myötä, sillä suorittimet häiritsevät hieman toisiaan käsitellessään yhteistä fyysistä muistia tai ajaessaan käyttöjärjestelmän ytimen koodia.

Rinnakkaisissa järjestelmissä tulee aina vastaan kilpailutilanne (engl. race condition), vaikka ohjelmat eivät muuten olisi sidoksissa toisiinsa. Tämä tarkoittaa sitä, että ne tarvitsevat edetäkseen samoja resursseja kuten muistia, levytilaa ja suoritinaikaa. Mikäli ohjelmat käyttävät yhteistä muistia (saman prosessin säikeet tai käyttöjärjestelmältä pyydetty yhteinen muistialue), ohjelmat voivat päivittää yhtä aikaa samaa muuttujaa tai tietorakennetta, mikä yleensä johtaa virheeseen. Tämän takia käyttöjärjestelmä tarjoaa mekanismeja resurssien hallittuun synkronointiin (engl. synchronization).

Testauksen kannalta rinnakkaisohjelmien perusongelma on ajoituksen muuttuminen ajokerrasta toiseen. Ajoituksen muuttuminen aiheuttaa sen, että sama ohjelma voidaan ajaa läpi hyvin monella eri tapaa, ja testausvaiheessa on mahdotonta saada aikaan kaikkia näitä mahdollisia laskentoja. Pienikin muutos ympäristössä voi muuttaa olennaisesti ajoitusta ja jokin piilevä virhe tulee näkyviin. Tätä voi kuvata myös tilaräjähdyksenä: perinteinen ohjelma suoritetaan sarjallisesti mahdollisten kontrollirakenteiden ohjaamana, mutta kuitenkin siten, että ohjelmalla on yksi ohjelmalaskuri, joka määrää laskennan sen hetkisen tilan yhdessä muistin sisällön kanssa. Rinnakkaisessa järjestelmässä ohjelmalaskureita on useita, eivätkä kaikki ohjelmat suorita samaa ohjelmakoodia. Laskennan tila on siis ohjelmalaskureiden ja muistin sisällön määräämä, jolloin mahdollisia tiloja on moninkertainen määrä sarjalliseen ohjelmaan verrattuna.

Bernsteinin ehdot

[muokkaa | muokkaa wikitekstiä]

A. J. Bernstein listasi vuonna 1966 ehdot rinnakkaisuuden toteuttamiseen:[2][3][4]

  1. mikäli prosessi Pi kirjoittaa muistialkioon Mi, niin mikään prosessi Pj ei voi lukea alkiota Mi
  2. mikäli prosessi Pi lukee muistialkiosta Mi, niin mikään prosessi Pj ei voi kirjoittaa alkioon Mi
  3. mikäli prosessi Pi kirjoittaa muistialkioon Mi, niin mikään prosessi Pj ei voi kirjoittaa alkioon Mi

Ehdot on suunniteltu tarkastelemaan muuttuuko ohjelman tulos mikäli ajosuoritusta muutetaan.

Ehdot ovat kuitenkin hyvin rajoittavat mikäli tietoa halutaan jakaa prosessien välillä. Jakamisen tapauksessa on siis voitava pakottaa käsittelyvuoroihin prosessien synkronoinnilla.

Amdahlin laki

[muokkaa | muokkaa wikitekstiä]

Gene Amdahl esitti vuonna 1967 lain rinnakkaisuudesta saatavalle suoritusnopeuden kasvulle.[5]

Operaatioiden rinnakkaistamista rajoittaa se, että tehtävän loogisesti sarjamuotoiset operaatiot on aina suoritettava peräkkäin. Siksi suorittimien lukumäärän kasvattamisesta saatava hyöty vähitellen vähenee rinnakkaisten prosessorien lukumäärän kasvaessa.[6]

Amdahlin laki voidaan esittää muodossa:

missä:

  • Slatenssi on teoreettinen rinnakkaistamisella saavutettava koko tehtävän nopeutuminen (nopeutumiskerroin),
  • p on alkuperäisen (sarjallisen) suoritusajan se osuus, joka voidaan rinnakkaistaa,
  • s rinnakkaistettavan tehtäväosuuden nopeutuminen, eli tämän osan suorittamiseen käytettävien säikeiden lukumäärä.
  1. Ilkka Haikala ja Hannu-Matti Järvinen: Käyttöjärjestelmät (luku 3). Talentum 2003. ISBN 951-762-837-4
  2. Bernstein, A. J.: "Program Analysis for Parallel Processing", s. 757-762. IEEE Trans. on Electronic Computers, 1966.
  3. Bernstein's Conditions cis.poly.edu. Arkistoitu 2.5.2017. Viitattu 21.2.2017.
  4. UNIT 2 CLASSIFICATION OF PARALLEL COMPUTERS computing.llnl.gov. Arkistoitu 1.2.2017. Viitattu 21.2.2017.
  5. Brown, Robert G.: Amdahl's Law phy.duke.edu. Viitattu 21.2.2017.
  6. Bach, Matt: Estimating CPU Performance using Amdahls Law pugetsystems.com. Viitattu 21.2.2017.

Aiheesta muualla

[muokkaa | muokkaa wikitekstiä]
Käännös suomeksi
Käännös suomeksi
Tämä artikkeli tai sen osa on käännetty tai siihen on haettu tietoja muunkielisen Wikipedian artikkelista.
Alkuperäiset artikkelit: en:Parallel computing & en:Synchronization (computer science) & en:Amdahl's law