Rinnakkaisalgoritmi
Tietojenkäsittelytieteessä rinnakkaisalgoritmi , toisin kuin perinteiset sekventiaaliset algoritmit , on algoritmi , joka voidaan toteuttaa osissa useilla eri tietokoneilla, minkä jälkeen saatujen tulosten yhdistäminen ja oikea tulos saadaan .
Jotkut algoritmit on melko helppo jakaa itsenäisesti suoritettaviksi paloiksi. Esimerkiksi kaikkien lukujen 1 - 100 000 tarkistustyön jakaminen sen selvittämiseksi, mitkä niistä ovat alkulukuja , voidaan tehdä osoittamalla jokaiselle käytettävissä olevalle prosessorille jokin lukujen osajoukko ja yhdistämällä sitten tuloksena olevat alkulukujoukot (esimerkiksi GIMPS -projekti toteutetaan samalla tavalla ) .
Toisaalta suurin osa tunnetuista pi :n arvon laskentaan tarkoitetuista algoritmeista ei salli jakamista rinnakkaisiin osiin, koska ne vaativat algoritmin edellisen iteroinnin tuloksen. Iteratiiviset numeeriset menetelmät , kuten esimerkiksi Newtonin menetelmä tai kolmen kappaleen ongelma , ovat myös puhtaasti peräkkäisiä algoritmeja. Joitakin esimerkkejä rekursiivisista algoritmeista on melko vaikea rinnastaa. Yksi esimerkki on kaavioiden syvyyshaku .
Rinnakkaisalgoritmit ovat erittäin tärkeitä moniprosessorijärjestelmien jatkuvan parantamisen ja nykyaikaisten prosessorien ytimien määrän lisääntymisen vuoksi . On yleensä helpompaa suunnitella tietokone yhdellä nopealla prosessorilla kuin tietokoneella, jossa on useita hitaita prosessoreita (olettaen, että saavutetaan sama suorituskyky ). Prosessorien suorituskyky kuitenkin kasvaa pääasiassa teknisen prosessin parantamisen (tuotantostandardien alenemisen) vuoksi, mitä haittaavat mikropiirielementtien koon fyysiset rajoitukset ja lämmönpoisto. Nämä rajoitukset voidaan voittaa siirtymällä moniprosessointiin, mikä on tehokasta jopa pienissä tietokonejärjestelmissä.
Peräkkäisten algoritmien monimutkaisuus ilmaistaan käytetyn muistin määränä ja algoritmin suorittamiseen vaaditussa ajassa (prosessorijaksojen lukumäärässä). Rinnakkaisalgoritmit edellyttävät toisen resurssin käytön huomioon ottamista: eri prosessorien välisen viestinnän alijärjestelmää. On kaksi tapaa kommunikoida prosessorien välillä: jaettu muisti ja viestien välitys.
Jaetut muistijärjestelmät edellyttävät lisälukkojen käyttöönottoa käsiteltäville tiedoille, mikä asettaa tiettyjä rajoituksia käytettäessä lisäprosessoreita.
Viestintäjärjestelmissä käytetään kanavien ja viestilohkojen käsitteitä, mikä luo lisäliikennettä väylään ja vaatii lisämuistia viestien jonotukseen. Nykyaikaisten prosessorien suunnittelussa voidaan tarjota erityisiä kytkimiä (ristipalkkeja), jotka vähentävät sanomanvaihdon vaikutusta tehtävän suoritusaikaan.
Toinen rinnakkaisten algoritmien käyttöön liittyvä ongelma on kuormituksen tasapainottaminen . Esimerkiksi alkulukujen etsiminen välillä 1 - 100 000 on helppo jakaa käytettävissä olevien prosessorien kesken, mutta jotkut prosessorit voivat saada enemmän työtä, kun taas toiset lopettavat käsittelyn aikaisemmin ja ovat käyttämättömänä. Kuormituksen tasapainotusongelmat pahenevat entisestään käytettäessä heterogeenisiä laskentaympäristöjä, joissa laskentaelementit eroavat merkittävästi suorituskyvyltään ja käytettävyydestään (esimerkiksi grid - järjestelmissä).
Useita rinnakkaisia algoritmeja, joita kutsutaan hajautetuiksi algoritmeiksi , on erityisesti kehitetty käytettäviksi klustereissa ja hajautetuissa laskentajärjestelmissä ottaen huomioon useita tällaisen käsittelyn ominaisuuksia.