A párhuzamos számítástechnika a számítástechnika egy típusa, ahol a számításokat vagy folyamatokat egyidejűleg hajtják végre.^[1] A nagy problémákat gyakran fel lehet osztani kisebbekre, melyeket párhuzamosan lehet megoldani. A párhuzamos számítástechnikának többféle formája létezik: bitszintű, utasításszintű, adat- és feladat-párhuzamosság. A párhuzamosságot már régóta alkalmazzák a nagy teljesítményű számítástechnika területén, de szélesebb körű érdeklődést váltott ki a frekvenciaskálázás fizikai korlátai miatt.^[2] Mivel a számítógépek energiafogyasztása (és ennek következtében a hőtermelés) az utóbbi években aggodalomra ad okot,^[3] a párhuzamos számítástechnika a számítógép-architektúra meghatározó paradigmájává vált, főleg a többmagos processzorok formájában.^[4]

A párhuzamos számítástechnika szorosan kapcsolódik az egyidejű számítástechnikához – gyakran használják együtt és gyakran egymással felcserélve, bár a kettő különbözik egymástól: párhuzamosság létezhet egyidejűség nélkül (például bitszintű párhuzamosság), és egyidejűség létezhet párhuzamosság nélkül (például többfeladatosság egy egymagos processzoron az időosztás által).^[5][6] A párhuzamos számítástechnika során a számítási feladat jellemzően több, gyakran sok, nagyon hasonló alfeladatra bontható, amelyeket egymástól függetlenül lehet feldolgozni, és amelyek eredményeit a teljesítés után később egyesítik. Ezzel szemben az egyidejű számítástechnikában a különféle folyamatok gyakran nem foglalkoznak a kapcsolódó feladatokkal; az elosztott számítástechnikában az egyes feladatok változatos természetűek lehetnek és a végrehajtás során gyakran bizonyos folyamatok közötti kommunikációt igényelnek.

A párhuzamos számítógépeket nagyjából osztályozni lehet annak a szintnek az alapján, amelyen a hardver a párhuzamosságot támogatja: a többmagos és a többprocesszoros számítógépek esetében egyazon gépen több feldolgozóelem van, míg a fürtök, MPP-k és rácsszámítások több számítógépet használnak ugyanazon feladat elvégzéséhez. Speciális párhuzamos számítógép-architektúrákat alkalmaznak a hagyományos processzorok mellett bizonyos feladatok felgyorsítására.

Bizonyos esetekben a párhuzamosság átlátható a programozó számára, mint például a bitszintű vagy utasításszintű párhuzamosság, de kifejezetten a párhuzamos algoritmusok közül különösen azokat, amelyek egyidejűséget használnak, nehezebb megírni, mint szekvenciális társaikat,^[7] mivel az egyidejűség számos új potenciális szoftverhibát rejt, amelyek közül a versenyhelyzetek a leggyakoribbak. A különböző alfeladatok közötti kommunikáció és szinkronizálás általában a legnagyobb akadály az optimális párhuzamos programteljesítmény elérésében.

Egyetlen program gyorsulásának elméleti felső határát a párhuzamosítás eredményeként Amdahl törvénye adja meg.

Háttér

Hagyományosan a számítógépes szoftvereket soros számításra írták. Egy probléma megoldásához egy algoritmust állítanak össze és valósítanak meg soros utasításfolyamként. Ezeket az utasításokat egy számítógép központi feldolgozóegységén hajtják végre. Egyszerre csak egy utasítás hajtható végre – az utasítás befejezése után a következő kerül végrehajtásra.^[8]

A párhuzamos számítástechnika viszont több feldolgozóelemet használ egyszerre egy probléma megoldásához. Ezt úgy lehet elérni, hogy a problémát független részekre bontjuk, és mindegyik feldolgozóelem az algoritmus egy részét a többivel egyidejűleg hajtja végre. A feldolgozóelemek változatosak lehetnek és tartalmazhatnak olyan erőforrásokat, mint egy számítógép több processzorral, több hálózati számítógép, speciális hardver vagy az előbbiek bármelyikének kombinációi.^[8] A történelem során a párhuzamos számítástechnikát alkalmazták tudományos számításhoz és tudományos problémák szimulálásához, különösen a természettudomány és a műszaki tudományok, például a meteorológia területén. Ez a párhuzamos hardver és szoftver, valamint a nagy teljesítményű számítástechnika megtervezéséhez vezetett.^[9]

A frekvenciaskálázás volt a meghatározó oka a számítógépes teljesítmény javulásának az 1980-as évek közepétől 2004-ig. A program futási ideje megegyezik az utasítások számával szorozva az utasításonkénti átlagos idővel. Ha az órajelen kívül minden más állandó, akkor annak növelése csökkenti az egy utasítás végrehajtásához szükséges átlagos időt. A frekvencia növelése tehát csökkenti az összes processzorigényes program futási idejét.^[10] Ugyanakkor a processzor által adott ${\displaystyle P}$ energiafogyasztást a ${\displaystyle P=C\cdot U^{2}\cdot F}$ egyenlet adja meg, ahol ${\displaystyle C}$ a kapacitás ciklusonként kapcsolva (arányos azon tranzisztorok számával, amelyek bemenete változik), ${\displaystyle U}$ a feszültség és ${\displaystyle F}$ a processzor frekvenciája (másodpercenkénti ciklusok száma).^[11] A frekvencia növelése növeli a processzorban felhasznált energiamennyiséget. A processzorok növekvő energiafogyasztása végül az Intel 2004. május 8-i Tejas és Jayhawk processzorainak megszüntetéséhez vezetett, amelyeket általában a frekvenciaskálázás végének tekintenek és az uralkodó számítógép-architektúra paradigmájának neveznek.^[12]

Az energiafogyasztás és a túlmelegedés problémájának kezelése érdekében a processzorgyártók elkezdték a többmagos, energiahatékony processzorok gyártását. A mag a processzor számítási egysége, a többmagos processzorokban minden mag független és ugyanahhoz a memóriához egyidejűleg fér hozzá. A többmagos processzorok párhuzamos számítástechnikát hoztak az asztali számítógépekbe. Így a soros programok párhuzamosítása vált a fő programozási feladattá. 2012-ben a négymagos processzorok szabványossá váltak az asztali számítógépekben, míg a szerverek 10 és 12 magos processzorokkal rendelkeztek. Moore törvénye kimondja, hogy a processzoronkénti magok száma 18–24 hónaponként megduplázódik. Ez azt jelentheti, hogy 2020 után egy tipikus processzor tucatnyi vagy száz maggal rendelkezik.^[13]

Az operációs rendszer biztosítja, hogy a különféle feladatok és felhasználói programok párhuzamosan fussanak a rendelkezésre álló magokon. Ahhoz azonban, hogy egy soros program teljes mértékben kihasználhassa a többmagos architektúrát, a programozónak kell átszerkesztenie és párhuzamosítania a kódot. Az alkalmazások futtatásának gyorsítását már nem lehet frekvenciaskálázással elérni, hanem a programozóknak kell párhuzamosítaniuk a szoftverkódjukat, hogy kihasználhassák a többmagos architektúrák növekvő számítási teljesítményét.^[14]

Amdahl törvénye és Gustafson törvénye

Optimális esetben a párhuzamosítástól való gyorsulás lineáris lenne – a feldolgozóelemek számának megkétszerezésével a futási időt a felére, második alkalommal történő megkétszerezésére pedig ismét a felére kellene csökkenteni. Azonban nagyon kevés párhuzamos algoritmus éri el az optimális gyorsulást. Legtöbbjüknél csaknem lineáris sebességnövekedés tapasztalható kisszámú feldolgozóelem esetében, amely állandó értékké válik nagyszámú feldolgozóelem esetén.

Az algoritmus várható gyorsulását egy párhuzamos számítási platformon Amdahl törvénye adja meg:^[15]

${\displaystyle S_{\text{latency}}(s)={\frac {1}{1-p+{\frac {p}{s}}}},}$

ahol

• ${\displaystyle S_{\text{latency}}}$ a végrehajtás késleltetésének lehetséges gyorsulása az egész feladat esetében;
• ${\displaystyle s}$ a végrehajtás késleltetésének lehetséges gyorsulása a feladat párhuzamosítható része esetében;
• ${\displaystyle p}$ a feladat párhuzamosítható részének végrehajtási ideje a párhuzamosítás előtt a teljes feladat végrehajtási idejének százalékában.

Mivel az ${\displaystyle S_{\text{latency}}<{1 \over 1-p}}$, ezért a program egy kis része, amely nem párhuzamosítható, korlátozza a párhuzamosítástól elérhető teljes gyorsulást. Egy nagy matematikai vagy mérnöki feladatot megoldó program általában több párhuzamosítható és több nem párhuzamosítható (soros) részből áll. Ha a program nem párhuzamosítható része a futási idő 10%-át teszi ki ${\displaystyle (p=0,9)}$, legfeljebb tízszeres gyorsulást érhetünk el, függetlenül attól, hogy hány processzort használunk. Ez felső korlátot jelent a párhuzamos végrehajtóegységek hozzáadásának hasznosságára. „Ha egy feladat nem osztható szét szekvenciális korlátozások miatt, a feldolgozási teljesítmény növelése nem befolyásolja annak végrehajtási idejét. Az emberi terhesség kilenc hónapig tart, függetlenül attól, hogy hány nőt jelölünk ki.”^[16]

Amdahl törvénye csak azokra az esetekre vonatkozik, amikor a probléma nagysága rögzítve van. A gyakorlatban, mivel egyre több számítási erőforrás válik elérhetővé, hajlamosak nagyobb problémákhoz (nagyobb adatkészletekhez) szokni, és a párhuzamosítható részben eltöltött idő gyakran sokkal gyorsabban növekszik, mint a benne rejlő sorozatmunka.^[17] Ebben az esetben Gustafson törvénye kevésbé pesszimista és reálisabb értékelést ad a párhuzamos teljesítményről:^[18]

${\displaystyle S_{\text{latency}}(s)=1-p+sp.}$

Mind Amdahl, mind Gustafson törvénye feltételezi, hogy a program soros részének futási ideje független a processzorok számától. Amdahl törvénye azt feltételezi, hogy a teljes probléma rögzített méretű, tehát a párhuzamosan elvégzendő munka független a processzorok számától, míg Gustafson törvénye azt, hogy a párhuzamosan elvégzendő munka arányosan változik a processzorok számával.

Függőségek

Az adatfüggőségek megértése alapvető fontosságú a párhuzamos algoritmusok megvalósításában. Egyik program sem futhat gyorsabban, mint a függő számítások leghosszabb lánca (úgynevezett kritikus út), mivel a számításokat, amelyek függnek a lánc előzetes számításától, sorrendben kell végrehajtani. A legtöbb algoritmus azonban nem csupán egy hosszú függő számítási láncból áll; általában vannak lehetőségek független számítások párhuzamos végrehajtására.

Legyen ${\displaystyle P_{i}}$ és ${\displaystyle P_{j}}$ két programszegmens. Bernstein feltételei^[19] leírják, mikor a kettő független és párhuzamosan végrehajtható. ${\displaystyle P_{i}}$ számára legyen ${\displaystyle I_{i}}$ az összes bemeneti és ${\displaystyle O_{i}}$ a kimeneti változó, és ugyanígy a ${\displaystyle P_{j}}$ esetében. ${\displaystyle P_{i}}$ és ${\displaystyle P_{j}}$ függetlenek, ha teljesülnek a következők:

${\displaystyle I_{j}\cap O_{i}=\varnothing ,}$

${\displaystyle I_{i}\cap O_{j}=\varnothing ,}$

${\displaystyle O_{i}\cap O_{j}=\varnothing .}$

Az első feltétel megsértése valódi függőséget eredményez, ahol az első szegmens által adott eredményt a második szegmens felhasznál. A második feltétel hamis függőséget képvisel, amikor a második szegmens az első szegmenshez szükséges változót állít elő. A harmadik, egyben utolsó feltétel egy kimeneti függőséget képvisel: amikor két szegmens ír ugyanarra a helyre, akkor az eredmény a logikailag utoljára végrehajtott szegmenstől származik.^[20]

Nézzük meg a következő függvényeket, amelyek többféle függőséget mutatnak:

1: function Dep(a, b)
2: c := a * b
3: d := 3 * c
4: end function

Ebben a példában a 3. utasítás nem hajtható végre a 2. utasítás előtt (vagy akár azzal párhuzamosan), mert a 3. utasítás a 2. utasítás eredményét használja. Ez megsérti az 1. feltételt, és így valódi függőséget okoz.

1: function NoDep(a, b)
2: c := a * b
3: d := 3 * b
4: e := a + b
5: end function

Ebben a példában nincs függőség az utasítások között, tehát mindegyik párhuzamosan futtatható.

Bernstein feltételei nem teszik lehetővé a memória megosztását a különböző folyamatok között. Ehhez szükség van az utasítás hozzáférések közötti érvényesítésére, például szemaforokra, akadályokra vagy más szinkronizálási módszerre.

Versenyhelyzetek, kölcsönös kizárás, szinkronizálás és párhuzamos lassulás

A párhuzamos programok alfeladatait gyakran szálaknak hívják. Néhány párhuzamos számítógép-architektúra a szálak kisebb, könnyű verzióit, rostokat, míg mások nagyobb, folyamatoknak nevezett verziókat használnak. A szálakat azonban elfogadják az alfeladatok általános kifejezésének.^[21] A szálaknak gyakran szinkronizált hozzáférésre van szükségük egy objektumhoz vagy más erőforráshoz, például amikor frissíteniük kell egy köztük megosztott változót. Szinkronizálás nélkül a két szál közötti utasítások tetszőleges sorrendben összeilleszthetők. Vegyük például a következő programot:

Ha az 1B utasítást az 1A és a 3A között hajtják végre, vagy ha az 1A utasítást az 1B és a 3B között hajtják végre, akkor a program hibás adatokat fog előállítani. Ezt versenyhelyzetnek nevezik. A programozónak zárat kell használnia, hogy a kölcsönös kizárást érvényesítse. A zár egy programozási nyelvi konstrukció, amely lehetővé teszi, hogy az egyik szál átvegye az irányítást egy változó felett és megakadályozza, hogy más szálak olvassák vagy írják azt, amíg a változó fel nem oldódik. A zárat tartó szál szabadon végrehajthatja annak kritikus szakaszát (egy olyan programszakaszát, amely kizárólagos hozzáférést igényel valamilyen változóhoz) és az adat feloldását, amikor kész. Ezért a program helyes végrehajtásának garantálása érdekében a fenti program átírható zárak használatához: