A párhuzamosság típusai
Az elosztott programok fejlesztésének egy másik szempontja a párhuzamosság típusának megválasztása, mint adatalapú vagy gráfalapú párhuzamosság. Az adatalapú párhuzamosság az adatok elosztott jellegére épül, amelyeket több számítógépre oszt szét. A számítások emellett azonosak lehetnek az összes csomóponton, különböző adatokra alkalmazva. Az is lehetséges, hogy a különböző gépeken futó tevékenységek más-más számításokat végeznek. Ha a tevékenységek azonosak, akkor az elosztott program az egy program, több adat (SPMD), ellenkező esetben a több program, több adat (MPMD) kategóriába tartozik.
Az adatalapú párhuzamosság alapgondolata egyszerű: egy nagy fájlt több számítógépre elosztva lehetségessé válik a fájl különböző részeinek párhuzamos elérése és feldolgozása. Az adatok elosztásának egy korábbi modulban megismert népszerű technikája a fájlcsíkozás, amely egyetlen fájlt particionál és oszt el több kiszolgáló között. Az adatalapú párhuzamosság egy másik formája a teljes fájlok (particionálás nélküli) elosztása a számítógépek között, különösen a nagyon szabálytalan struktúrájú adatokat tartalmazó, kis méretű fájlok esetében. Kiegészítésül, az adatok elosztható az elosztott tevékenységek között explicit módon, üzenetátadással, vagy implicit módon, megosztott memória használatával, feltéve, hogy a mögöttes elosztott rendszer támogatja a memóriamegosztást.
9. ábra: SPMD elosztott program a megosztott memória programozási modell használatával
Adatalapú párhuzamosság valósul meg akkor, ha minden csomópont egy vagy több tevékenységet futtat az elosztott adatok különböző részein. Konkrét példaként tegyük fel, hogy az A tömb három számítógépen van megosztva egy elosztott, megosztott memóriájú rendszerben. Tegyük fel továbbá, hogy egy elosztott program egyszerűen összeadja az A tömb elemeit. Az 1., 2. és 3. gép utasítható úgy, hogy mindegyikük az A tömb egyharmadán, tehát 50 elemen végezze el az összeadási tevékenységet, ahogyan a 9. ábrán látható. Az adatok a memóriamegosztási programozási modell használatával oszthatók ki a tevékenységeknek, ehhez pedig szinkronizálási mechanizmus szükséges. Egy ilyen program nyilván az SPMD kategóriába tartozik. Egy másik megoldás, hogy az A tömböt egy (fő) tevékenység osztja el egyenlően (üzenetátadással) a három gép között, a fő tevékenység gépét is beleértve, ahogyan a 10. ábrán látható. A gépek egymástól függetlenül hajtják végre az összegzési tevékenységet, az előállított részösszegeket pedig végül a fő tevékenységnek kell összesítenie a végösszeg előállításához. Ilyen esetben minden tevékenység hasonló abban az értelemben, hogy ugyanazt az összegzési műveletet hajtják végre az A tömb különböző részein. A fő tevékenység azonban az adatokat is elosztja a tevékenységek között, valamint összesíti a részösszegeket, ezért kissé eltér a másik két tevékenységtől. Ez a program emiatt egyértelműen MPMD. A MapReduce-szal foglalkozó későbbi lecke be fogja mutatni, hogy a MapReduce adatalapú párhuzamosságot és MPMD programokat használ.
10. ábra: MPMD elosztott program az üzenetátadási programozási modell használatával
A gráfalapú párhuzamosság lényege nem az adatok, hanem a számítások elosztása. Az elosztott programok többsége valahol az e két forma közötti tartományba esik. A gráfalapú párhuzamosságot széles körben használják sok olyan területen, mint a gépi tanulás, az adatbányászat, a fizika és az elektronikus áramkörök tervezése. Ezeken a területeken sok probléma modellezhető olyan gráfként, amelyben a csúcsok a számításoknak felelnek meg, az élek pedig az adatfüggőségeket vagy a kommunikációt kódolják. Ismétlésként, egy $G$ gráf a $(V, E)$ rendezett pár, ahol $V$ a csúcsok véges halmaza, $E$ pedig az éleknek nevezett páronkénti relációk $E \subset (V \times V)$ véges halmaza. A csúcsokhoz és élekhez rendelt súlyokkal jelölhető az egyes csúcsokon végzendő munka, illetve az egyes éleken zajló kommunikáció mennyisége.
Az áramkörök tervezésének egy klasszikus problémájában a cél egyenlővé tenni egyes összetevők bizonyos csatlakozóinak elektromos potenciálját az azokat összekötő vezetékekkel. Ha a csatlakozók száma $n$, akkor ez $(n - 1)$ vezetékkel oldható meg, amelyek mindegyike két csatlakozót köt össze. Az összes ilyen elrendezés közül általában az a legelőnyösebb, amelyhez a legkevesebb vezeték szükséges. Ez az áramköri probléma nyilvánvalóan modellezhető gráfként. Az egyes csatlakozóknak egy-egy csúcs feleltethető meg, az $(u, v)$ csatlakozópárok közötti összeköttetésnek pedig egy-egy él. Az $u$ és $v$ közötti élhez rendelt $w(u, v)$ súllyal kódolható az $u$ és $v$ összekötésével járó költség (a szükséges vezeték hossza). A megoldandó probléma ekkor egy olyan körmentes $S$ részhalmaz megkeresése az élek $E$ halmazában, amely az összes $V$-beli csúcsot összeköti, és amelynek teljes
$$ w(S) = \Sigma_{(u, v)\in S} w(u, v) $$
súlya a minimális.
Mivel $S$ körmentes és összefüggő, az eredménynek egy fának, az úgynevezett minimális feszítőfának kell lennie. Az áramkör bekötésének problémája így a minimális feszítőfa megkeresésének problémájává alakul át, ez pedig megoldható például a Kruskal- vagy a Prim-algoritmussal.
11. ábra: Peremhálózati metrikával particionált gráf
A már gráfként modellezett program egy olyan gráfparticionálási módszerrel osztható szét egy elosztott rendszer gépei között, amely a hatékony elosztott számítás érdekében a munkát (tehát a csúcsokat) is szétosztja az elosztott csomópontok között. Ennek alapelve az adatalapú párhuzamosságéhoz hasonlóan egyszerű: egy nagy gráfot több számítógépre elosztva lehetségessé válik a gráf különböző részeinek párhuzamos feldolgozása, ennek eredménye pedig a gráfalapú párhuzamos kialakítás. A gráfparticionálás általános célja, hogy a csúcsok p darab egyenlő súlyú partícióra bontásával egyenletesen ossza szét a munkát p processzor között, ugyanakkor minimalizálva a csomópontok közötti, élekkel ábrázolt kommunikációt. Ezt a célkitűzést általában standard élvágási metrikának nevezik. Bár a gráfparticionálás problémája NP-nehézségű, heurisztikával elérhetők közel optimális megoldások. A 11. ábra konkrét példájában három partíció, $P_{1}$, $P_{2}$ és $P_{3}$ szerepel, amelyekben a $ \lbrace v_{1}, \cdots, v_{8} \rbrace $ csúcsok élvágási metrika alapján vannak felosztva. Minden él súlya 2, ami mindkét irányban 1 egységnyi adatkommunikációnak felel meg. Emiatt az ábrázolt élvágás teljes súlya 10. Más vágások nagyobb kommunikációs forgalmat eredményeznek. Belátható, hogy a gráfparticionálás kulcsfontosságú az intenzív kommunikációval járó alkalmazásoknál, és jelentős szerepet játszhat az alkalmazás összteljesítményének meghatározásában. Gráfparticionálást alkalmaz a későbbi leckékben részletesebben ismertetett Pregel és GraphLab is.
Hivatkozások
- T. H. Cormen, C. E. Leiserson, R. L. Rivest és C. Stein (2009. július 31.). Bevezetés az algoritmusok MIT Press, harmadik kiadás
- B. Hendrickson és T. G. Kolda (2000). Gráfparticionálási modellek párhuzamos számítástechnikához
- M. R. Garey, D. S. Johnson és L. Stockmeyer (1976). Néhány egyszerűsített NP-complete gráfproblémák elméleti számítástechnika
- B. Hendrickson és R. Leland (1995). A Chaco felhasználói útmutató 2.0-s technikai jelentés SAND95-2344, Sandia National Laboratories
- G. Karypis és V. Kumar (1998). Gyors és kiváló minőségű többszintű séma a szabálytalan gráfok particionálásához SIAM journal on Scientific Computing