Párhuzamos algoritmus
Az informatikában a párhuzamos algoritmus a hagyományos szekvenciális algoritmusokkal szemben egy olyan algoritmus , amely sok különböző számítástechnikai eszközön részenként implementálható, majd a kapott eredményeket kombinálja és megkapja a helyes eredményt.
Egyes algoritmusok meglehetősen könnyen lebonthatók egymástól függetlenül végrehajtható darabokra. Például az összes szám ellenőrzése 1-től 100 000-ig, hogy megtudja, melyik prím , elvégezhető úgy, hogy minden elérhető processzorhoz hozzárendelünk egy számok egy részhalmazát, majd az eredményül kapott prímkészleteket kombináljuk (például a GIMPS projekt hasonló módon valósul meg ) .
Másrészt a pi értékének kiszámítására szolgáló ismert algoritmusok többsége nem teszi lehetővé a párhuzamos részekre bontást, mivel az algoritmus előző iterációjának eredményét igénylik. Az iteratív numerikus módszerek , mint például a Newton-módszer vagy a háromtestű probléma , szintén tisztán szekvenciális algoritmusok. A rekurzív algoritmusok néhány példáját meglehetősen nehéz párhuzamosítani. Az egyik példa a mélység szerinti keresés a grafikonokon .
A párhuzamos algoritmusok nagyon fontosak a többprocesszoros rendszerek folyamatos fejlesztése és a modern processzorok magszámának növekedése miatt . Általában könnyebb egy gyors processzorral rendelkező számítógépet megtervezni, mint egy sok lassú processzort (feltéve, hogy ugyanaz a teljesítmény érhető el ). A processzorok teljesítménye azonban elsősorban a technikai folyamat javítása (gyártási színvonal csökkentése) miatt nő, amit a mikroáramköri elemek méretének fizikai korlátozása és a hőleadás akadályoz. Ezeket a korlátokat a többfeldolgozásra való átállással lehet áthidalni, ami még kis számítástechnikai rendszerek esetén is hatékony.
A szekvenciális algoritmusok összetettsége a felhasznált memória mennyiségében és az algoritmus végrehajtásához szükséges időben (a processzorciklusok számában) fejeződik ki. A párhuzamos algoritmusok megkövetelik egy másik erőforrás használatának figyelembevételét: a különböző processzorok közötti kommunikáció alrendszerét. A processzorok közötti kommunikációnak két módja van: megosztott memória és üzenettovábbítás.
Az osztott memória rendszerek további zárolást igényelnek a feldolgozott adatokhoz, ami bizonyos korlátozásokat ír elő további processzorok használatakor.
Az üzenetküldő rendszerek a csatornák és üzenetblokkok fogalmát használják, ami további forgalmat generál a buszon, és további memóriát igényel az üzenetek sorba állításához. A modern processzorok tervezésénél speciális kapcsolók (keresztlécek) biztosíthatók annak érdekében, hogy csökkentsék az üzenetváltás hatását a feladat végrehajtási idejére.
A párhuzamos algoritmusok használatához kapcsolódó másik probléma a terheléselosztás . Például az 1 és 100 000 közötti prímszámok keresése könnyen elosztható a rendelkezésre álló processzorok között, de egyes processzorok több munkát kaphatnak, míg mások korábban befejezik a feldolgozást és tétlenek lesznek. A terheléselosztási problémák tovább súlyosbodnak, ha heterogén számítási környezeteket használnak, ahol a számítási elemek teljesítménye és rendelkezésre állása jelentősen eltér (például grid rendszerekben).
Különféle párhuzamos algoritmusokat, úgynevezett elosztott algoritmusokat kifejezetten fürtökön és elosztott számítástechnikai rendszerekben való használatra fejlesztettek ki , figyelembe véve az ilyen feldolgozás számos jellemzőjét.