Párhuzamos algoritmus
| Ez a szócikk nem tünteti fel a független forrásokat, amelyeket felhasználtak a készítése során. Emiatt nem tudjuk közvetlenül ellenőrizni, hogy a szócikkben szereplő állítások helytállóak-e. Segíts megbízható forrásokat találni az állításokhoz! Lásd még: A Wikipédia nem az első közlés helye. |
A számítástudományban a párhuzamos algoritmusok alatt olyan algoritmusokat értünk, amelyek a feladatot több részre osztva, több processzoron futnak egyidejűleg.
Bizonyos algoritmusok, mint a lineáris keresés vagy a maximumkeresés, könnyen párhuzamosíthatóak, hiszen elegendő az inputot részekre darabolni, s az egyes inputdarabokat rendelni hozzá az egyes processzorokhoz, majd végül összefésülni az eredményt.
Léteznek azonban nehezen párhuzamosítható algoritmusok, mint például a legtöbb iteratív numerikus algoritmus és a rendező algoritmusok.
A párhuzamos algoritmusok gyakorlati előnye, hogy gyorsabb a futási idejük soros társaiknál, hiszen egyidejűleg több processzor dolgozik a feladaton. Sokkal egyszerűbb több lassú processzort építeni egy számítógépbe, mint egy gyorsat, így adott előállítási áron nagyobb sebesség érhető el több processzoros architektúra esetén. Emellett a processzorok sebessége felülről korlátos, tehát nem növelhető a végtelenségig az egyprocesszoros gépek teljesítménye, így a fejlesztés szükségszerűen a többprocesszoros rendszerek irányába mozdul el.
A soros algoritmusok költségét idő- és tárbonyolultsággal szokás jellemezni, értve ez alatt az algoritmus processzoridő és memóriaigényét. A párhuzamos algoritmusok esetében van egy harmadik optimalizálandó érték is, a processzorok kommunikációja. Két elterjedt modell létezik a processzorok kommunikációjának megvalósítására, nevezetesen az osztott memóriás és az üzenetküldős modellek.
Az osztott memóriás modellben a processzorok egy közös memóriát használnak és azon keresztül kommunikálnak egymással. Itt felmerülnek a konkurens írás és olvasás problémái, amelyek egyrészt az adminisztrációs műveletköltségek miatt lassítják a futást, másrészt részben soros végrehajtásra kényszerítik a processzorokat az erőforrásokra várakozás miatt.
