Párhuzamos algoritmus

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.