Szakdolgozat
Brosch Balázs 2009.
Budapesti Mőszaki és Gazdaságtudományi Egyetem Villamosmérnöki és Informatikai Kar Irányítástechnika és Informatika Tanszék
Brosch Balázs Párhuzamos algoritmusok megvalósítása MPI környezetben SZAKDOLGOZAT
KONZULENS
Dr. Szeberényi Imre
BUDAPEST, 2009.
2
ITT LESZ A FELADATKIÍRÁS
3
Nyilatkozat
Alulírott, Brosch Balázs, a Budapesti Mőszaki és Gazdaságtudományi Egyetem hallgatója kijelentem, hogy ezt a szakdolgozatot meg nem engedett segítség nélkül, saját magam készítettem, és a szakdolgozatban csak a megadott forrásokat használtam fel. Minden olyan részt, melyet szó szerint, vagy azonos értelemben de átfogalmazva más forrásból átvettem, egyértelmően, a forrás megadásával megjelöltem.
..............................................
Brosch Balázs
4
Tartalmi összefoglaló A szakdolgozat oktatási anyag formájában – a C programozási nyelvre alapozva – foglalja össze a Message Passing Interface (MPI) azon szolgáltatásait, amelyek elsajátításával bármely párhuzamosítható tudományos probléma megoldására képessé válnak a mérnökhallgatók. A párhuzamos programozás fontossága mellet szóló érvek bemutatása után ismertetem a párhuzamos számítást lehetıvé tevı architektúra és programozási modelleket, melyek között elhelyezem az MPI-t. Egy gyakran elıkerülı probléma részfeladatokra bontásával, és azok különbözı processzekhez rendelésével, valamint a terhelés kiegyensúlyozás problémakörének bemutatásával és a futási idı vizsgálatával elısegítem a hallgatók párhuzamos programozási szemléletének kialakítását. Az üzenetküldéses modell elemeinek bemutatásával ismertetem a blokkoló és a nem-blokkoló pont-pont kommunikációs függvényeket. Az alapvetı kollektív kommunikációs függvények mellett – mint például a szinkronizáló sorompó, az üzenetszórás, az adatok szétosztása és összegyőjtése, illetve a közben való mőveletvégzés – az összetett kollektív kommunikációs függvények is terítékre kerülnek. A konverziós problémák és feloldásuk oldaláról közelítem meg az MPI származtatott adattípusok és struktúrák átvitelét biztosító lehetıségeit. A cartesian topológiákat elınyös alkalmazhatóságát kétdimenziós adathalmazok feldolgozása kapcsán mutatom be. Kitérek továbbá a szekvenciális és a koordináta processzazonosítók közötti kapcsolatra, valamint a cartesian topológiák tovább bontási lehetıségére, a cartesian résztopológiákra is. Az üzenetküldéses kommunikációt árnyaló lehetıségek közül a felhasználó által definiált redukáló mőveletekre és az üzenetpróbálás alkalmazására mutatok be gyakorlati jelentıségő példákat. A kommunikátorok két fı csoportjának az intra- és inter-kommunikátoroknak az összehasonlításával rámuatatok szerepükre, valamint részletezem létre hozási lehetıségeiket. A gráf topológiák jellemzıinek és létre hozási módjának bemutatása mellett – néhány – a cartesian topológiákkal való hasolóságot valamint azoktól való eltérést is megemlítek. Végül két bonyolultabb párhuzamosítható feladatot fogalmazok meg, melynek megoldásával a hallgatók bizonyíthatják az MPI környezetben való – szemeszter során kialakult – jártasságukat.
5
Abstract The thesis as an educational material – assumes C programming language knowledge – summarizes those services of Message Passing Interface (MPI), which let the engineering undergraduates perform any parallelizable scientific problem. After listing arguments about the importance of parallel programming I introduce the required architectures and programming models, where also MPI belongs, for parallel computing. By splitting a common problem into subproblems, assigning them to processes and in addition explaining the meaning of load balancing and examing the parts of run time undergraduates are leaded into the parallel programming approach. Blocking and non-blocking point-to-point communication functions are detailed through presenting the elements of the message passing model. Beside the basic collective communication functions – like barrier synchronization, broadcast, scattering, gathering and reducing datas – the complex communicaton functions are also described. From the view of data converting problems and solutions I cover the topic of derived datatypes and I explain how MPI provides derived data transferring possibilities. I introduce Cartesian topologies by emphasizing their advantageous adaptability apropos of two dimensional set of data. Furthermore I reveal the contact between sequential and coordinate process identifiers and I show how to further joint Cartesian topologies into subtopologies. To fine message passing communication I describe how to create user-defined reduction operations and I also provide practical examples for the adaptability of message probing. By comparing the two main types of communicators: intra- and intercommunicators I point their role and I detail the possibilities how to create them. Presenting the properties and the way of creating graph topologies I draft some similarities and differences to Cartesian topologies. To conclude the course I suggest two complex parallelizable problem to the undergraduates to solve proving the perfection in MPI environment which they have learnt in this course.
6
Tartalomjegyzék I. Oktatási anyag tervezése ...................................................................... 9 I.1. Célkitőzés ...................................................................................................9 I.2. Oktatási módszertan, a tananyag szerkezete ........................................10 I.3. Mintapéldák jellegzetességei...................................................................10
II. Tananyag bemutatása ......................................................................... 11 II.1. Bevezetés a párhuzamos programozás elméletébe .............................11 II.1.1. Miért fontos a párhuzamos programozás? .................................................. 11 II.1.2. A hatékony párhuzamos számításhoz szükséges hardver és szoftver adottságok.................................................................... 11 II.1.3. Architektúra modellek................................................................................. 12 II.1.4. Párhuzamos programozási modellek .......................................................... 14 II.1.5. MPI bevezetı .............................................................................................. 14 II.1.6. Egy egyszerő MPI program bemutatása ..................................................... 15
II.2. Párhuzamos programozási szemlélet kialakítása ...............................17 II.2.1. Az MPI által definiált párhuzamos programozási eszköztár fıbb elemei .. 17 II.2.2. A feladat részfeladatokra bontása és a részfeladatok processzekhez rendelése .................................................... 17 II.2.3. Futási idı vizsgálata.................................................................................... 19
II.3. Pont-pont kommunikáció és fajtáinak megismerése ..........................20 II.3.1. Az üzenetküldéses modell elemei ............................................................... 20 II.3.2. Blokkoló függvények .................................................................................. 21 II.3.2.1. A blokkoló függvények felépítése ..................................................................21 II.3.2.2. „Joker” processz-azonosító, illetve üzenetcímke használata ..........................23 II.3.2.3. Hogyan valósítja meg az MPI az üzenetátvitelt?............................................24 II.3.2.4. A holtpont oka, és elkerülésének módja .........................................................24
II.3.3. Nem-blokkoló függvények ......................................................................... 26 II.3.3.1. A nem-blokkoló függvények használatának koncepciója...............................26 II.3.3.2. A nem-blokkoló függvények felépítése ..........................................................27 II.3.3.3. A küldı függvények variánsai ........................................................................31
II.4. Kollektív kommunikáció és fajtáinak megismerése ...........................33 II.4.1. Alapvetı függvények .................................................................................. 33 II.4.1.1. Szinkronizáló sorompó ...................................................................................33 II.4.1.2. Üzenetszórás ...................................................................................................34 II.4.1.3. Szétosztás........................................................................................................35 II.4.1.4. Összegyőjtés ...................................................................................................36 II.4.1.5. Összegyőjtés mőveletvégzéssel ......................................................................37
II.4.2. Alapvetı függvények variánsai................................................................... 38 II.4.2.1. Különbözı mérető részek szétosztása.............................................................38 II.4.2.2. Különbözı mérető részek összegyőjtése ........................................................39
II.4.3. Összetett függvények .................................................................................. 40 II.4.3.1. Összegyőjtés és mindenkinek elküldés...........................................................40 II.4.3.2. Összegyőjtés mőveletvégzéssel és mindenkinek elküldés..............................42 II.4.3.3. Szétosztás mindenkitıl mindenkinek..............................................................43 II.4.3.4. Összegyőjtés mőveletvégzéssel és szétosztás.................................................44
7
II.5. Származtatott adattípusok és struktúrák létrehozása és átvitele......46 II.5.1. Hogyan továbbítja az MPI az adattípusokat?.............................................. 46 II.5.2. Adatok csomagolt átvitele........................................................................... 47 II.5.3. Új adattípus (struktúra) létrehozása ............................................................ 48 II.5.3.1. Az új adattípus (struktúra) elıkészítése ..........................................................49 II.5.3.2. Az új adattípus (struktúra) véglegesítése ........................................................51
II.6. Cartesian topológiák áttekintése ..........................................................52 II.6.1. Cartesian topológia létrehozása .................................................................. 52 II.6.2. A szekvenciális és a koordináta processz-azonosítók közötti konverzió ... 53 II.6.3. Cartesian topológia résztopológiákra bontása ............................................ 54
II.7. Az üzenetküldéses kommunikációt árnyaló lehetıségek ...................57 II.7.1. Felhasználó által definiált „redukáló” mőveletek ....................................... 57 II.7.1.1. Az új „redukáló” mővelet megírása függvényként .........................................57 II.7.1.2. A megírt függvény „regisztrálása”..................................................................58 II.7.1.3. A kész „redukáló” mővelet használata ...........................................................59
II.7.2. Üzenetpróbálás............................................................................................ 60 II.7.2.1. Az üzenetpróbáló függvény felépítése............................................................60 II.7.2.2. Az üzenetpróbáló függvény használata ..........................................................61 II.7.2.3. Szignál üzenetek kezelése...............................................................................62
II.8. Intra- és inter-kommunikátorok összehasonlítása .............................64 II.8.1. Intra-kommunikátorok ................................................................................ 65 II.8.1.1. Intra-kommunikátorok létrehozása széthasítással...........................................65 II.8.1.2. Intra-kommunikátorok létrehozása lemásolással............................................66 II.8.1.3. Intra-kommunikátorok létrehozása módosítással ...........................................66
II.8.2. Inter-kommunikátorok ................................................................................ 70 II.8.2.1. Inter-kommunikátor létrehozása két intra-kommunikátor összekapcsolásával ...................................................71 II.8.2.2. Inter-kommunikátorok adatainak lekérdezése ................................................72
II.9. Gráf topológiák ......................................................................................74 II.9.1. Gráf topológiák létrehozása ........................................................................ 74 II.9.2. Gráf topológiák adatainak lekérdezése ....................................................... 75
II.10. Egy komolyabb párhuzamos algoritmus önálló megvalósítása.......78
III. Továbbfejlesztési lehetıségek ........................................................... 80 IV. Összefogalás ........................................................................................ 80 V. Irodalomjegyzék................................................................................... 81 VI. Mellékletek .......................................................................................... 82
8
I. Oktatási anyag tervezése I.1. Célkitőzés A szakdolgozat egy a Budapesti Mőszaki és Gazdaságtudományi Egyetem Villamosmérnöki és Informatikai Karának M.Sc. képzésében bevezetendı választható tárgy tematikájára tesz egy javaslatot, mely a párhuzamos programozás mérnökhallgatókkal való megismertetésével kívánja a napjainkban egyre növekvı számítási teljesítmény igény kiszolgálására irányuló törekvést támogatni. Mivel a párhuzamos programozási modellek közül az üzenet-átadásos módszer – lazán csatolt rendszerek esetén is hatékony megvalósíthatósága miatt – a legszélesebb körben implementálható [1], ezért az oktatási anyag középpontjában a leginkább fejlesztett üzenet-átadásos párhuzamos programozási modell standard interfésze, a Message Passing Interface (MPI) áll. A tematika kidolgozása során három fı irányelvet tartottam szem elıtt: A mérnökhallgatókat a problémamegoldási szemléletükben a soros programírás koncepciójából egy paradigma-váltáson keresztül átvezetni a párhuzamos programokban való gondolkodásig. Az egyes tananyagrészeket igyekeztem lényegre törıen, ugyanakkor precízen és kétértelmőséget nem hagyva összeállítani, hogy a tanulás során ne kelljen más forráshoz fordulni, hanem lehessen kizárólag az elsajátítandó kompetenciákra összpontosítani. Továbbá a fejezetek végén – segítségképp – ellenırzı kérdésekkel hangsúlyoztam ki az adott téma lényeges pontjait. Alapvetı C nyelvő programozási ismeretekre építve, az MPI biztosította lehetıségeknek törekedtem olyan mélységő ismeretét átadni, melynek birtokában a mérnökhallgatók a tudományos életben felmerülı bármilyen párhuzamosítható problémát képessé válnak megoldani. A párhuzamos programok írásában való készség kialakítását számos példaprogram bemutatásával céloztam meg.
9
I.2. Oktatási módszertan, a tananyag szerkezete A tematikát egy tízalkalmas, egyenként kilencven perces számítógépes laboratórium sorozatra terveztem. A tantárgy célja, hogy a kurzust elvégezve a hallgatók egy bonyolultabb párhuzamos algoritmust önállóan elkészítsenek. Az ehhez szükséges ismereteket kilenc témakörbe győjtöttem, a tizedik fejezet pedig a feladatkiírásokról szól, melyek mellé megoldási javaslatokat is mellékeltem. Minden fejezet a téma felvezetésével kezdıdik, majd az elméleti részek tárgyalásával, illetve annak példaprogramokkal történı illusztrálásával folytatódik. A téma felvezetésekor és az elmélet tárgyalásakor mindig kiemelt helyet kap a tárgyalt rész gyakorlati jelentıségének bemutatása. Az elsajátítandó technológiák és eszközök magyarázatait – ahol szükséges – ábrákkal tettem érthetıbbé. A témakörök tartalmát és terjedelmét úgy alakítottam ki, hogy egy laboratóriumi alkalom során egy fejezet – otthoni elızetes készülést követıen – végigkövethetı legyen. Tapasztalatom, hogy a tanulás akkor a leghatékonyabb, ha az elméletet azonnal gyakorlatba ültetjük, és addig nem haladunk tovább, amíg minden, megvalósítást érintı kérdést nem tisztáztunk; ezért szemléletes mintapéldákkal mutatom be az éppen tárgyalt technológiát. Továbbá az elıbbit erısítve, minden fejezet végén egy – a tanultak használatát igénylı – önállóan megoldandó feladatot fogalmazok meg. Ezek a feladatok – kis lépcsıfokokként – alkalmanként nem jelentenek nagy kihívást a hallgatók számára, viszont fokozatosan már egy bonyolultabb párhuzamos algoritmus megírására készítenek fel. A laboratóriumi foglalkozások elvégzése az adott fejezet elızetes elolvasását igényi. A hallgatók felkészültségének mérésére, illetve a számonkérések elıkészítésére, de elsı sorban a hallgatók tanulásának támogatására, ellenırzı kérdéseket fogalmaztam meg. Ezek az ellenırzı kérdések az adott fejezetben leírtakra kérdeznek rá, és a rájuk adott válaszok tételesen és a kérdések sorrendjében megtalálhatók a leírásban.
I.3. Mintapéldák jellegzetességei Minden fejezethez tartozik példaprogram: a fontosabbakhoz több, a kevésbé fontosakhoz kevesebb. A legegyszerőbb „hello” programtól a bonyolult párhuzamos algoritmus mintamegoldásáig összesen harmincöt példaprogramot készítettem. A példaprogramok mindig az elméleti rész szorosan összetartozó egységei után következnek, és középpontjukban mindig az ismertetett technológia áll. Tehát a példaprogramok kipróbálására szóló felhívásokat az elméleti leírásba ágyaztam, hogy ezzel is ergonómikusabbá és könnyebben tanulhatóvá tegyem az oktatási segédanyagot. A példaprogramok – a bonyolultabb algoritmusokat leszámítva – rendszerint a standard kimenetre írnak, átláthatóbbá téve a bemutatott technológia mőködését. A példaprogramok közül kiemelném a párhuzamosan futó processzek szempontjából kritikus eseteknek, a holtpontoknak a lehetséges okaira rámutató és azokat kiküszöbölı példaprogramokat. Az MPI eszköztárának megismerésén és használatán túl a példaprogramok a programozó elıl „elrejtett” implementáció mőködésének megismerését is célozzák. Összefoglalva törekedtem arra, hogy a gyakran felmerülı kérdéseket megelızve, a példaprogramok az MPI eszköztárának használatát tisztázva, azokat precízen bemutassák. A példaprogramok – a könnyebb kipróbálhatóság érdekében – a CD mellékleten találhatóak.
10
II. Tananyag bemutatása II.1. Bevezetés a párhuzamos programozás elméletébe A párhuzamos programozás [2] során nagyszámú – akár többmagos processzorú – számítógépet úgy kapcsolunk össze, hogy a független processzorok egymással egyidıben dolgozhassanak egy komplex probléma egy-egy kis részén. Így olyan feladattal is boldogulunk, ami túl nagy lenne egyetlen számítógép számára. Ahhoz, hogy élhessünk a párhuzamos számítás elınyeivel, a programunkat párhuzamossá kell tennünk, hogy kiértékelése egynél több processzen történhessen egyszerre, ahol egy processz alatt a program (vagy alprogramjának) egy példányát értjük, amint – autonóm módon – egy fizikai processzoron kiértékelıdik. A párhuzamos programozás elsıdleges célja, hogy számítási teljesítmény-növekedést érjünk el ugyanazon program soros végrehajtásához képest.
II.1.1. Miért fontos a párhuzamos programozás? Nagy számítás igényő tudományos problémák [3] megoldása A tudományos problémák komplexitása és nagy adatmérete nagy számítási kapacitást igényel. Ilyen például a biomolekulák kutatása, az idıjárás elırejelzés és a globális felmelegedés modellezése; de említhetünk olyan példát is, amit sokkal közelebb érzünk a mindennapjainkhoz: például az autópályák forgalmának elırejelzése, modellezése a dugók elkerülése céljából. Technológiai határ elérése A rendelkezésre álló számítási kapacitás sosem volt elegendı, hogy kiszolgálja a növekvı igényeket, ezért a 80-as években – amikor úgy tőnt, hogy elérték a technológiai határt – a párhuzamos programozás fejlesztésébe kezdtek. Napjainkban újra nagy teret kap a párhuzamosítás, és jelentıs energiákat fordítanak a párhuzamos programozás fejlesztésére és szabványosítására. Többmagos processzorok alkalmazásának felfutása A többmagos processzorok elterjedésével a párhuzamos programozás hatékony eszközt ad a kezünkbe ezek számítási kapacitásának kihasználására.
II.1.2. A hatékony párhuzamos számításhoz szükséges hardver és szoftver adottságok A National Science Foundation Office of Cyberinfrastructure a párhuzamos számítás következı sarokköveit fogalmazta meg [4]: A processzorok és a memória összekapcsolódásának gyors kommunikációt kell biztosítania a független processzorok között, valamint gyors adatátvitelt a memóriával. Rendelkezésre kell állnia egy protokollnak, ami a processzek összekapcsolódását definiálja. A megoldandó számítási problémának és a feldolgozandó adatnak – hatékonyan – kisebb, egymástól független egységekre bonthatónak kell lennie. A mechanizmusnak alkalmasnak kell lennie arra, hogy a részfeladatokat különbözı processzekhez rendelje.
11
II.1.3. Architektúra modellek A számítógép architektúrákat és programozási modelleket az adat és az utasítás mennyiségének függvényében a Flynn-féle osztályozás [5] négy csoportra osztja. Egy utasítás végrehajtása egy adaton. Single Instruction Single Data (SISD) Több utasítás végrehajtása egy adaton. Multiple Instruction Single Data (MISD) Egy utasítás végrehajtása több adaton. Single Instruction Multiple Data (SIMD) Több utasítás végrehajtása több adaton. Multiple Instruction Multiple Data (MIMD) Párhuzamos programozás során a több adattal (MD) dolgozó modelleket használjuk. A SIMD architektúra esetében ugyanolyan processzek értékelıdnek ki, a MIMD architektúra esetében pedig különbözı processzek is, amelyek egymástól részben függetlenül hajtódnak végre. A processzek futhatnak ugyanazon processzoron is, de a párhuzamos számítás akkor a leghatékonyabb, ha minden processzt egy külön processzorhoz rendelünk hozzá. A MIMD architektúra kétféle módon valósítható meg: közös memóriával [6] vagy elosztott memóriával [6]. A közös memóriás MIMD architektúra esetén a processzorok és a memóriák oly módon vannak összekapcsolva, hogy minden processzor hozzáférhet minden memóriához (1. ábra). Az összekapcsoló hálózat adatátviteli szélessége korlátozza – a szükséges kommunikáció mennyiség miatt – a processzorok számát.
1. ábra A fı memórián kívül a számítógépek két további memóriával is rendelkeznek: regiszterekkel és cache-sel. A regiszterek nagyon gyors, processzoron belüli memóriák, amik azokat az adatokat tárolják, amin a processzor éppen dolgozik. A regiszterek gyorsaságuk miatt költségesek, ezért mennyiségük az összes memóriához képest kicsi. A cache memória ugyan lassabb a regisztereknél, de jóval gyorsabb a fı memóriánál. Így az ára is olcsóbb a regisztereknél, viszont drágább a fı memóriánál. Használata azon a tapasztalaton nyugszik, hogy mind az utasítások, mind az adatok esetében többnyire szekvenciálisak a memória-hozzáférések, így – az éppen szükséges – kis mennyiségő szekvenciális utasítás és adat cache-ben való elhelyezésével jelentıs mértékben csökkenthetı a fı memóriához való látszólagos hozzáférési idı. Valójában a cache és a regiszterek között állandóan és kis egységekben történik az adatforgalom, míg a fı memória és cache között ritkábban és nagyobb egységekben (2. ábra). A cache különösen nagy szerepet kap a közös
12
memóriás architektúrák esetén, hiszen a több processzor egyidejő memória-hozzáférési kísérlete telítheti a buszt, jelentıs késleltetést okozva mind az adat, mint az utasítás hozzáférésekben.
2. ábra Bár a cache használata nagymértékő hozzáférési idı csökkenéshez vezet, alkalmazásával viszont az adat-konzisztencia problémájával szembesülünk. Ez abból fakad, hogy a közös memória használat révén több processzor olvashat és írhat át egyazon változót. Például, ha az „A” processzor hozzáfér egy olyan változónak az „A” processzor cache-ében tárolt másolatához, amit – ezt megelızıen – egy „B” processzor megváltoztatott (a saját cache-ében és esetleg már a fı memóriában is), akkor az „A” processzor már hibás, érvénytelen adattal dolgozik. Az ily módon kialakuló adat-inkonzisztenciát az adatforgalom figyelésével és a közös változók idıben való frissítésével küszöbölhetjük ki. Az elosztott memóriás MIMD architektúra esetén minden processzor saját memóriával rendelkezik (3. ábra). Lényegében különálló számítógépek kapcsolódnak össze egy feladat kiszámítása céljából. Az egyes számítógépeket „node”-oknak hívjuk. Minden node-nak gyors hozzáférése van a saját memóriájához, ezenkívül más node memóriájához is, amit nagysebességő összekapcsoló hálózat biztosít. Mivel egy tisztán elosztott memóriás architektúra esetén a memória nem közös, ezért a más node-ok memóriájában lévı adatok elérését a párhuzamos programozás eszköztára teszi lehetıvé.
3. ábra A nagy teljesítményő párhuzamos számítást biztosító architektúrák egyik legújabb változata a Symmetric Multi-Processing (SMP) [7], amely ötvözi a közös memóriás és az elosztott memóriás modelleket. Másként fogalmazva: közös memóriás architektúrák
13
kapcsolódnak össze nagysebességő hálózattal. Ez esetben egy-egy közös memóriás architektúra felel meg egy-egy „node”-nak, és ezek a node-ok az elosztott memóriás architektúrának megfelelıen kapcsolódnak össze.
II.1.4. Párhuzamos programozási modellek Üzenet-átadásos módszer Ahogy a neve is takarja, a processzek üzenetekkel kommunikálnak egymással. Ennek a modellnek a legelterjedtebb standard interfészét nevezzük Message Passing Interface-nek (MPI) [8]. Hasonló feladatokra alkalmas a Parallel Virtual Machine (PVM) [9] is. Az üzenetküldéses modell használata leginkább az elosztott memóriás rendszerekre jellemzı, de a közös memóriás és az SMP architektúrákra is alkalmazható. Ez utóbbi esetekben viszont – az üzenetküldéses megközelítésbıl fakadóan – a közös memória, mint elıny nincs kihasználva. Közös memóriás módszer Ezen modell használata a közös memóriás architektúrákon terjedt el, mert a közös memória nagyban leegyszerősíti a fordítók írását. Ez a módszer jellemzıen úgy nyilvánul meg, hogy a soros kódot kommentszerő utasításokkal (direktívákkal) egészítjük ki, amelyek kijelölik, hogy a fordító milyen arányban ossza szét az adatokat és az elvégzendı feladatokat a processzorok között; viszont az adatszétosztás és számítás valamint a processzorok közötti kommunikáció részletei a fordítóra vannak bízva. Példaként említhetı az OpenMP [10]. Egy másik standard interfész a High Performance Fortran (HPF) [11], amely mind elosztott memóriás, mind közös memóriás architektúrákon alkalmazható. Az HPF hátránya, hogy bár SMP architektúrákon is használható, de nem támogatja a hierarchikus struktúrákat, így ezek egyszerően elosztott rendszerekként kezelıdnek. Mind az OpenMP-t, mind az HPF-t elsısorban hurkok párhuzamosítására használják, amely kismértékő párhuzamosítás és az MPI által megvalósítható program szintő párhuzamosítás között jelentıs hatékonyságbeli különbség figyelhetı meg az MPI javára. Új megközelítés A hatékonyság fokozását célzó törekvés, mely az MPI elosztott memóriás és üzenetátadásos modelljét ötvözi az OpenMP közös memóriás és többszálú modelljével egyetlen párhuzamos modellben SMP architektúrára alapozva.
II.1.5. MPI bevezetı Az MPI (Message Passing Interface) a nagy számításteljesítményő üzenet-átadásos párhuzamos programozás standard interfésze, ami azt jelenti, hogy olyan C függvények győjteménye, amik mindegyike a processzek közötti kommunikáció támogatására szolgál. Az MPI bár meghívható függvényeket tartalmaz, mégsem könyvtár, hanem szabvány, aminek több megvalósítása, implementációja létezik. Az MPI program legalább két processzbıl áll, amelyek egyedi azonosítóval rendelkeznek, és amelyek egymással párhuzamosan hajtódnak végre. A processzek MPI függvényekkel kommunikálnak egymással, miközben egyenként egy nagy számítási feladat egy-egy kis részén dolgoznak. Az MPI elsı verziójában nem lehet futási idıben, dinamikusan processzt létre hozni, hanem a processzek számát futtatás elıtt rögzíteni kell.
14
II.1.6. Egy egyszerő MPI program bemutatása Az MPI egy szabvány, melynek több implementációja létezik. Munkám során az MPI LAM (Local Area Multicomputer) [12] implementációját használtam, amit Linux operációs rendszeren – internet kapcsolat mellett – a sudo apt-get install lam-dev paranccsal lehet telepíteni. Az alapértelmezett beállításoktól eltérı konfigurációhoz egy többlépéses telepítésen kell végighaladni, ami párhuzamos algoritmusok bemutatásához szükségtelen, így nem térünk ki rá. Tekintsük az alábbi egyszerő kódot! --- hello.c --#include <stdio.h> #include <mpi.h> // MPI header file importálása int main(int argc, char *argv[]) { int nprocs, myrank; MPI_Init(&argc,&argv);
// MPI inicializálása
MPI_Comm_size(MPI_COMM_WORLD, &nprocs); // Hány processz indult? MPI_Comm_rank(MPI_COMM_WORLD, &myrank); // Mi az azonosítóm? printf("Hello, az azonositom: %d (a %d db processzbol)\n", myrank, nprocs); MPI_Finalize(); return 0;
// MPI leállítása
} Az MPI függvényekkel kibıvített C kód lefordítása elıtt el kell indítanunk a LAM-ot a lamboot paranccsal. Ezt követıen a LAM mindaddig futni fog, amíg a lamhalt paranccsal le nem állítjuk. Az MPI programok futtatásához a LAM futása szükséges, hiszen a LAM valósítja meg az MPI-t. A kódunkat az mpicc -o hello hello.c paranccsal fordítjuk le. A lefordított kód futatásának elindításakor megadjuk, hogy hány példányban fusson le a kódunk, azaz hány processz induljon. A példában szereplı program olyan, hogy mindegyik processz ugyanezt hajtja végre. Például, ha négy példányban szeretnénk futtatni, akkor ezt az mpirun -np 4 hello paranccsal tesszük. Az MPI header file importálásán és a változók deklarálásán kívül a legelsı lépés az MPI inicializálása. Ezt követıen érdemes csak a C utasításokat használni, mert az MPI szabvány nem definiálja, hogy az MPI inicializálása elıtt lévı C utasításokat minden processznek végre kell-e hajtania. Elkerülve az MPI implementációk közötti különbségekbıl fakadó hibákat, a kód hordozhatóságát támogatva, érdemes ennek megfelelıen eljárni. Az MPI_Comm_size(MPI_COMM_WORLD, &nprocs); függvénnyel lekérdezzük, hogy összesen hány process indult, és számuk az nprocs változóba kerül. Az MPI_Comm_rank(MPI_COMM_WORLD, &myrank); függvénnyel lekérdezzük a processz egyedi azonosítóját, amire minden processz más-más választ kap, és ez az adott processz myrank változójába kerül. Ez alapján, az azonosító alapján tudjuk megkülönböztetni a processzeket, és a kommunikáció során is ezt használjuk a címzéshez.
15
A szükséges mőveletek, számítások – jelen esetben standard kimenetre írás – után leállítjuk az MPI-t és visszatérünk a main függvénybıl. A program futásának eredménye a következı: Hello, az azonositom: 1 (a 4 db processzbol) Hello, az azonositom: 2 (a 4 db processzbol) Hello, az azonositom: 3 (a 4 db processzbol) Hello, az azonositom: 0 (a 4 db processzbol) Az, hogy a processzek milyen sorrendben írnak a standard kimenetre nincs definiálva, és jelentısen függ a végrehajtó architektúrától. Ha befejeztük az MPI programjaink futtatását, akkor fontos, hogy – a fent leírt módon – leállítsuk a LAM-ot.
Ellenırzı kérdések: 1.) Hogyan érünk el számítási teljesítmény-növekedést a párhuzamos programozás alkalmazásával? 2.) Miért fontos a párhuzamos programozás? 3.) Mik a hatékony párhuzamos számításhoz szükséges hardver és szoftver adottságok? 4.) A számítógép architektúrákat és programozási modelleket mi alapján osztja fel a Flynn-féle osztályozás? Mik ezek a csoportok, és közülük melyeket használjuk a párhuzamos programozás során? 5.) A közös memóriás MIMD architektúra esetén mi jellemzı a processzorok és a memóriák kapcsolatára? Adat inkonzisztenciához vezethet-e ebben az esetben a cache használata? 6.) Mi a cache memória használatának elınye és hátránya? 7.) Az elosztott memóriás MIMD architektúra esetén mi jellemzı a processzorok és a memóriák kapcsolatára? Adat inkonzisztenciához vezethet-e ebben az esetben a cache használata? 8.) Mi a fı koncepciója az üzenetküldéses párhuzamos programozási modellnek? Milyen architektúrán terjedt el leginkább? Milyen szintő párhuzamosítás jellemzı rá? 9.) Mi a fı koncepciója a direktíva alapú párhuzamos programozási modellnek? Milyen architektúrán terjedt el leginkább? Milyen szintő párhuzamosítás jellemzı rá?
Feladatok: 1.) Üzemeljük be az MPI-t megvalósító LAM-ot! 2.) Próbáljuk ki az hello.c példaprogramot!
16
II.2. Párhuzamos programozási szemlélet kialakítása II.2.1. Az MPI által definiált párhuzamos programozási eszköztár fıbb elemei A kommunikációt menedzselı függvények Ide tartozik az MPI kommunikáció inicializálása és lezárása, a processzek számának és azonosítójának lekérdezése, valamint a processzek között alcsoportok kialakítása. Pont-pont kommunikációt megvalósító függvények Ez a fajta kommunikáció mindig processzpárok között történik. Minden üzenetet a küldésen kívül fogadni is kell. Ezen kommunikációt lebonyolító függvényeknek több változata van, melyek közül a megfelelı kiválasztásához a futási idıbeli kommunikáció megtervezésére és átlátására van szükség. Csoporton belüli kommunikációt megvalósító függvények Ezt a fajta kommunikációt kollektív kommunikációnak hívjuk, mert egy processzcsoport tagjai között zajlik. Az ide tartozó függvényeket rendkívüli hatékonyságuk miatt használjuk. Az egyszerő üzenetszóráson kívül sokkal komplexebb üzenetküldési módok is rendelkezésünkre állnak. Például egyetlen függvényhívással megvalósítható, hogy egy processz bufferében lévı adatokat feldaraboljunk és szétosszunk az összes processz között; vagy ennek az ellentéte, hogy összegyőjtsünk különbözı processzek buffereibıl adatokat egy processz bufferébe. Az adatok összegyőjtése közben ráadásul tetszıleges mőveletet végezhetünk rajtuk, és ekkor csak a végeredmény érkezik meg az üzenetet fogadó processzre. Továbbá lehetıség van több processzrıl több processzre küldeni adatokat egyetlen függvényhívással. Tetszıleges adatstruktúrák kialakítására szolgáló függvények Lehetıség van összetett, a megoldandó feladathoz leginkább illeszkedı adatstruktúrák létrehozására, küldésére és fogadására.
II.2.2. A feladat részfeladatokra bontása és a részfeladatok processzekhez rendelése Alapvetıen két dolgot lehet részekre bontani: a feldolgozandó adatokat és az elvégzendı mőveleteket. A részekre bontás célja, hogy az egyes részek egymással párhuzamosan, azaz egyidıben hajtódjanak végre, így nyerve idıt a soros végrehajtáshoz képest. Viszont a kommunikációra fordított idıvel romlik a hatékonyságunk. A fentiek miatt a probléma megoldása során használt modell kitalálása meghatározó jelentıséggel bír a program megírásának késıbbi menetére. A párhuzamos programunk leprogramozása elıtt tehát érdemes alaposan megvizsgálnunk, hogy a problémát milyen módon lehet a legoptimálisabban párhuzamosítani. Tekintsük a következı, nagy adathalmazon viszonylag egyszerő mőveleteket végrehajtó szekvenciálisan kiértékelıdı programot! 1. melléklet: main2_2.c
17
A program egy 24 bit/pixel színmélységő tetszıleges BMP képen végez mőveleteket, majd az eredményt egy új BMP fájlba menti. Elsı ránézésre kitőnik, hogy a fájlkezelést leíró kódrész nagyságrendekkel hosszabb a mőveletvégzést leíró kódrésznél. Amennyiben nagymérető képen végzünk mőveleteket, akkor mégis a mőveletvégzéshez szükséges idı a jelentısebb. A program párhuzamosításakor fájlkezelést és feldolgozó mőveleteket különböztethetünk meg egymástól. A fájlkezelés megléte miatt érdemes master - slave (munkavezetı - dolgozó) modellt alkalmazni. A fájlmőveleteket a masterhez, a feldolgozó mőveleteket pedig a slave processzekhez rendeljük. A feldolgozandó adatokat minél több részre osztjuk, annál nagyobb a párhuzamosítás hatásfoka. Szükség esetén a master processz is végezhet mőveleteket, de ekkor hatékonyság szempontjából szők keresztmetszetté válik, hiszen amíg feldolgozó mőveleteket végez, addig nem tud adatszétosztással és összegyőjtéssel, valamint fájlkezeléssel foglalkozni. Úgy képzeljük el a párhuzamos programunkat, hogy minden processzorhoz egyetlen processzt rendelünk, de ezt a hozzárendelést az MPI-t megvalósító LAM teljesen elrejti elılünk. A párhuzamos programot úgy írjuk meg, hogy bizonyos speciális feladatokhoz egyegy külön processzt rendelünk, a feldolgozó mőveletekhez pedig egy tetszıleges tagszámú csoportot. Tehát olyan programot írunk, aminek futtatása elıtt paraméterként megadjuk, hogy hány példányban hajtódjon végre. A mőveletek végrehajtása közben szükséges, hogy a processzek kommunikáljanak egymással. A master processz beolvassa a fájlból az adatokat, részekre osztja és szétküldi a slave processzeknek. Gyakran elıfordul, hogy a slave processzeknek, ahhoz, hogy fel tudják dolgozni a master processztıl kapott adatokat, egymással is kommunikálniuk kell. A jelen képfeldolgozás esetében az egyes processzek képrészletének „szélén” lévı pixelek feldolgozásához a szomszédos pixelek ismerete szükséges, melyek más processzek képrészletéhez tartoznak. Az adatokat úgy érdemes szétosztani a processzek között, hogy a mőveletvégzés során minél kevesebb kommunikációra legyen szükség, hiszen a kommunikációra fordított idı rontja a hatékonyságot a szekvenciálisan végrehajtható soros programhoz képest. A képfeldolgozás esetében sávokra érdemes osztani a képet, hogy csak két szomszédos processzel kelljen kommunikálnia minden processznek. Egyforma számítási teljesítményő processzorokból álló architektúrát feltételezve – amit az MPI-t megvalósító LAM elrejt elılünk –, egyforma mérető sávokat készítünk, illetve egy megmaradó kisebbet. Terhelés kiegyensúlyozás Amikor például azt vizsgáljuk, hogy az elıbb említett kisebb sáv hozzárendelhetı-e a master processzhez, vagy már szők keresztmetszetté tenné a rendszer számítási teljesítménye szempontjából, akkor a terhelés optimális elosztását keressük. A rendelkezésünkre álló architektúrát a lehetı legjobban kell kihasználnunk, amit a processzek és hozzájuk rendelhetı feladatok megfelelı párosításával érünk el. Olyan módon kell szétosztanunk a processzek között a terhelést, hogy minimalizáljuk azt az idıt, amikor egyes processzek várakoznak, miközben mások dolgoznak; különben elpazaroljuk a számításra fordítható erıforrásainkat. A terhelés kiegyensúlyozás azonos mőveleteket végzı processzek esetében kézenfekvı; míg különbözı feladatokat ellátó processzek között már mélyebb meggondolást igényel.
18
II.2.3. Futási idı vizsgálata A futási idı minden processz esetében alapvetıen három részre osztható: Számításra fordított idı A mőveletvégzésre, számolásra fordított idı az egyedüli hasznos dolog a számunkra, mert mind a várakozással, mind a kommunikációval romlik a hatékonyságunk. Amiatt írunk párhuzamos programokat, hogy a végrehajtáshoz, „lefuttatáshoz” szükséges idıt radikálisan lecsökkentsük. Optimális esetben, n számú processzel számolva, a soros végrehajtáshoz szükséges idı 1/n-szerese alatt végeznénk, de az elkerülhetetlen kommunikáció és (minimális várakozás) miatt ez a javulási arány teljesen nem érhetı el. Várakozással töltött idı Várakozási idınek azt az idıt nevezzük, amikor egy processz más processzektıl vár adatokat, és közben semmilyen hasznos munkát nem végez. Leggyakrabban a fájlmőveletek miatt várakoznak processzek, ugyanis ezt általában mindig egyetlen processz végzi. A várakozási idı – futási idıt lassító hatásának – csökkentését a mőveletvégzés és a kommunikáció egymással való átlapolásával érhetjük el. Ehhez rendelkezésre állnak olyan pont-pont kommunikációt megvalósító függvények, amiknek nem kell visszatérniük ahhoz, hogy az utánuk következı kód kiértékelıdhessen. Kommunikációhoz szükséges idı Az adatok küldéséhez és fogadásához szükséges idı egyértelmően hátrány a soros program futási idejéhez képest. Az MPI által definiált függvények széles választékából a kommunikációs folyamat optimálisan megtervezhetı, minimalizálva ezzel a kommunikációhoz szükséges idıt.
Ellenırzı kérdések: 1.) Mik az MPI által definiált párhuzamos programozási eszköztár fıbb elemei? Hogyan jellemezhetık röviden? 2.) Mindig egyenes arányosság van a kódrészek hosszúsága és a hozzájuk tartozó futási idık között? Hogyan befolyásolja ez a feladatok processzekhez rendelését? 3.) Milyen irányelveket tartunk szem elıtt a terhelés kiegyensúlyozás megtervezésekor? 4.) Milyen fıbb részekre bontható a futási idı? Ezek közül melyik a hasznos, és melyek a hátrányosak a párhuzamos programozás hatékonyságának szempontjából?
Feladatok: 1.) Tanulmányozzuk át az 1. mellékletben található main2_2.c soros programot és gondolkodjunk el rajta, hogyan párhuzamosítanánk azt! A gondolatmenetünket írjuk le, vagy rajzoljuk el!
19
II.3. Pont-pont kommunikáció és fajtáinak megismerése Az MPI az üzenetküldéses párhuzamos programozás standard interfésze, tehát alapvetıen kommunikációs formákat definiál. A legalapvetıbb közülük a két processz közötti pont-pont kommunikáció. Elsı megközelítésre egyszerőnek tőnik, hogy egy adott üzenetet az egyik processz oldalán el kell küldeni, és a másik oldalán fogadni kell. A gyakorlatban viszont – bár tényleg csak egy küldı és egy fogadó függvényt kell használni –, mégis alapos megfontolást igényel a használatuk. Például, ha egy processznek egyszerre több üzenetet küldenek, akkor melyiket fogadja el? A kérdést közelebbrıl megvizsgálva, valójában, ha az idınek megfelelıen kis felbontásával rendezzük sorba az üzenetek küldésének idıpontját, akkor a kérdés megoldódni látszik. A gyakorlatban viszont nem az üzenetek küldésének idıpontja a mérvadó, hanem hogy az adott processz mikor jut a programjának azon részére, amikor az üzenetek fogadásával tud foglalkozni. Tehát a helyzet inkább ahhoz hasonló, mint amikor az embernek megtelik a postaládája. Mi is csak akkor vesszük észre, hogy üzeneteink érkeztek, amikor megnézzük a postaládánkat. Ezt követıen – ahogy nekünk is –, a processznek is el kell döntenie, hogy milyen sorrendben dolgozza fel az üzeneteket. A másik, kommunikációt árnyaló kérdés, hogy mibıl tudja az üzenetet küldı processz, hogy akinek az üzenetet küldte, az már annak az ismeretében dolgozik-e tovább? Erre létezik minden pont-pont kommunikációt megvalósító függvénynek blokkoló és nem blokkoló változata. A blokkoló függvények addig nem térnek vissza, amíg a másik oldalon a címzett processz nem fogadta az üzenetet; a nem blokkoló függvények pedig a címzett processz fogadásától függetlenül visszatérnek. A blokkoló függvények esetében elıny az üzenet fogadásának bizonyossága, hátrány viszont a várakozási idı; a nem blokkoló függvények esetében pedig az az elıny, hogy nincs várakozási idı, viszont hátrány, hogy nincs visszajelzés az üzenet fogadásáról.
II.3.1. Az üzenetküldéses modell elemei Forrás- és célprocessz A pont-pont kommunikáció megvalósításában az MPI-ban mindkét oldalnak aktívan részt kell vennie. Az egyik processz küldi az üzenetet (forrásprocessz), a másik processz pedig fogadja (célprocessz). Általában a forrásprocessz és a célprocessz egymáshoz képest aszinkron módon dolgoznak, így az üzenetek küldése és fogadása is aszinkron módon történik. Emiatt fordulhat elı olyan eset, hogy a forrásprocessz már jóval azelıtt elküld egy üzenetet, mielıtt a célprocessz észlelné annak érkezését. Ugyanígy, az aszinkronitásra vezethetı vissza az az eset is, amikor a célprocessz elıbb fogadna egy üzenetet, mint azt a forrásprocessz elküldi. Üzenet felépítése Egy üzenet alapvetıen két fı részbıl áll: borítékból és tartalomból. Ezek jelentése nagyon hasonló a hagyományos postai gyakorlatban megszokottakhoz. A boríték tartalmazza a forrásprocessz és a célprocessz azonosítóját, annak a kommunikátornak a nevét, amelybe mindkét processz tartozik, és egy üzenetcímkét. A kommunikátor egy processz csoportot jelöl, amelybe a forrás- és célprocessz is beletartozik. A kommunikátor onnan kapta a nevét, hogy csak az egy csoportba, kommunikátorba tartozó processzek kommunikálhatnak egymással. A látszattal ellentétben, ez inkább támogatás, mint megkötés, mert az MPI_COMM_WORLD kommunikátorba minden processz beletartozik, és a további kommunikátorok létrehozásával csak
20
a kommunikációs lehetıségeinket növeljük (nagyban támogatva a késıbb bemutatott csoportos kommunikációt). Az üzenetcímke az üzenetek árnyaltabb beazonosítására szolgál, hiszen adott forrás- és célprocessz között is lehet egyszerre több üzenet. Az üzenet tartalma egy adattömbként, bufferként képzelhetı el, amely mellett rendelkezésünkre áll a tömb adattípusa és a mérete is, hogy hány darab adattípusban definiált egységet tartalmaz. Azáltal, hogy az MPI ilyen strukturált módon definiálja az üzenetek tartalmát, nagyban támogatja, hogy különbözı számábrázolást használó számítógépek is összekapcsolódhassanak, valamint a tetszıleges adattípus definiálásának lehetıségével leegyszerősíti az összetett adatstruktúrák átvitelét is. Függı üzenetek Az üzenetküldés menete addig, hogy a forrásprocessz kezdeményezi az üzenetküldést, egyértelmő; az üzenet borítékának és tartalmának átvitele viszont már összetettebb. Ez utóbbit az MPI-t megvalósító LAM elrejti elılünk, de a helyesen mőködı párhuzamos program tervezésekor fontos érteni, hogy mi történik a „háttérben”. Mivel az üzenetek küldése és fogadása nem szinkronizált, ezért a processzekre gyakran vár egy vagy több olyan üzenet, amit már elküldtek, de még nem fogadtak. Ezeket függı üzeneteknek nevezzük. Az MPI egy fontos tulajdonsága, hogy a függı üzeneteket nem rendezi FIFO sorba, hanem lehetıséget ad a célprocessznek, hogy az üzenetek tulajdonságai alapján választhasson közülük, hogy melyiket fogadja. Az üzenetfogadáshoz a célprocessz egy fogadó borítékkal rendelkezik, amit az MPI a függı üzenetek borítékjaihoz hasonlít, és ha egyezést talál, akkor a célprocessz fogadja az adott üzenetet. Ha nincs egyezés, akkor a fogadás mindaddig nem fejezıdik be, amíg a megfelelı üzenetet el nem küldték. Emellett a célprocessznek rendelkeznie kell az üzenet tartalmának fogadásához elegendı szabad memória területtel, amit mindig elızetesen kell lefoglalnia.
II.3.2. Blokkoló függvények II.3.2.1. A blokkoló függvények felépítése A legalapvetıbb pont-pont kommunikációs függvények az MPI_Send és az MPI_Recv. Mindketten blokkolják a hívó processzt, amíg a kommunikáció (üzenetátvitel) teljesen be nem fejezıdik. int MPI_Send ( void *buf, int count, MPI_Datatype dtype, int dest, int tag, MPI_Comm comm );
// Küldendı adatokat tartalmazó buffer // Küldendı adategységek száma // Adategység típusa // Célprocessz azonosítója // Üzenetcímke // Kommunikátor, melybe mindkét // processz beletartozik
Az elsı három paraméter az üzenet tartalma, a második három pedig a boríték. Mivel az MPI_Send-et a forrásprocessz hívja meg, ezért elegendı csak a célprocessz azonosítójának a megadása az üzenetcímke és a kommunikátor megjelölése mellett. Tehát minden paraméter bemenı. Ha a mővelet sikerült, akkor MPI_Success-szel tér vissza a függvény. Ha ezt nem is vizsgáljuk, a függvény akkor sem fog addig visszatérni, amíg az üzenetküldés teljesen be nem fejezıdött.
21
int MPI_Recv ( void *buf, int count, MPI_Datatype dtype, int source, int tag, MPI_Comm comm, MPI_Status *status );
// Fogadó buffer // Maximum fogadható // adategységek száma // Adategység típusa // Forrásprocessz azonosítója // Üzenetcímke // Kommunikátor, melybe mindkét // processz beletartozik // Információ a fogadott üzenetrıl
Az elıbbivel megegyezik a paraméterek sorrendje, ugyanakkor néhánynak közülük más a jelentésük és egy paraméterrel több van. Míg az elıbbi esetben a „buf” a küldendı adatokat tartalmazó buffert jelentette, addig itt a fogadó buffert, amit az üzenet fogadása elıtt elızetesen le kell foglalnunk a memóriában. A „count” mindkét esetben az adategységek számának megadására szolgál, ám míg az MPI_Send esetében a ténylegesen elküldeni kívánt adategységek számát jelenti, addig az MPI_Recv-nél a fogadó buffer méretét. Az azonos adattípus használata mind a küldı, mind a fogadó oldalon a programozó felelıssége; ugyanis eltérés esetén a kimenetel definiálatlan. Az MPI_Recv esetében a „source” és „tag” paraméterek arra szolgálnak, hogy a célprocessz a függı üzenetek közül kiválaszthassa azt, amelyikre szüksége van. A forrás azonosítójának helyén, illetve az üzenetcímke helyén használhatunk „joker” azonosítót, illetve címkét, és ekkor bármilyen forrásprocessztıl bármilyen üzenetcímkével fogadhatunk üzeneteket. Ennek tipikus alkalmazása a master processz esete, amikor az bármelyik slave processz üzenetküldését válogatás nélkül fogadja. A korábbi két paraméterrel ellentétben a kommunikátort mindig egyértelmően kell megadnunk. A „status” paraméterrel az üzenet fogadásával kapcsolatos információkhoz férünk hozzá. Például joker processzazonosító vagy üzenetcímke használata esetén, ennek segítségével kérdezhetjük le a küldı processz azonosítóját, az üzenet címkéjét, illetve a küldött adategységek számát. Az adategységek számának lekérdezésére azért van szükség – joker azonosító vagy címke használata esetén –, mert a különbözı üzenetek általában különbözı hosszúak; és mivel nem teljesen specifikált, hogy ki a két fél, az üzenet hosszát sem tudjuk elıre. A „buf” és a „status” kimenı paraméterek, a maradék öt pedig bemenı paraméter. Az MPI_Recv az MPI_Send-hez hasonlóan hibakóddal tér vissza, de csak akkor, ha az üzenetátvitel teljesen befejezıdött. Tekintsünk egy immár párhuzamosan megírt programot, melyben egy processz átküld egy tömböt egy másik processznek! 2. melléklet: main3_2_1.c Az MPI inicializálása után, a már megismert módon, lekérdezzük a processzek számát, illetve minden elindult processz lekérdezi az azonosítóját. Az azonosítókat használjuk feltételként, amikor a processzek között különbséget teszünk. Az üzenetet elıbb a 0 azonosítójú processz elküldi, majd az 1 azonosítójú fogadja. A program futtatásához elıször elindítjuk a LAM-ot a lamboot paranccsal. Ezt követıen lefordítjuk a kódot az mpicc -o main3_2_1 main3_2_1.c paranccsal. Két példányban való futtatáshoz az mpirun -np 2 main3_2_1 parancsot adjuk ki.
22
A program futásának eredménye a következı: 1.processz uzenetfogadas elott: 0 0 0 0 0 1.processz uzenetfogadas utan: 0 1 2 3 4 A LAM-ot a lamhalt paranccsal állíthatjuk le.
II.3.2.2. „Joker” processz-azonosító, illetve üzenetcímke használata Ha tetszıleges processztıl akarunk üzenetet fogadni, akkor az MPI_Recv függvényben a forrásprocessz azonosítójának helyére az MPI_ANY_SOURCE joker azonosítót írjuk. Tekintsünk egy olyan programot, amelyben a master processz a slave processzektıl tetszıleges sorrendben fogadja az adatokat! 3. melléklet: main3_2_2a.c A master processz tetszıleges sorrendben tudja fogadni az egyes slave processzek üzeneteit, tehát a joker processz-azonosító használatával kiküszöböltük, hogy az egyes slave processzeknek a sorukra kelljen várniuk. Amint egy processz végzett a munkájával, egybıl kiszolgálja a master. A slave processzek beazonosítása az MPI_Status típusú status struktúra status.MPI_SOURCE változójából kinyerhetı információval történik. Ha tetszıleges üzenetcímkével akarunk üzenetet fogadni, akkor az MPI_Recv függvényben az üzenetcímke helyére az MPI_ANY_TAG joker üzenetcímkét írjuk. Ekkor az üzenetcímke értékét az MPI_Status típusú status struktúra status.MPI_TAG változójából nyerhetjük ki. Akár a processz-azonosító és az üzenetcímke helyére is tehetünk egyszerre jokert, lehetıvé téve, hogy több processztıl, többféle üzenetet fogadhassunk azok küldési sorrendjében, minimalizálva a blokkoló függvényekre jellemzı várakozási idıt. Tekintsünk egy olyan programot, amelyben a master processz a slave processzektıl tetszıleges sorrendben különbözı mérető tömböket fogad! 4. melléklet: main3_2_2b.c A fogadott adattípus és az MPI_Recv függvény által visszaadott status változó ismeretében az MPI_Get_count függvénnyel lekérdezhetjük a ténylegesen küldött adategységek számát. int MPI_Get_count( MPI_Status *status, // Információ a fogadott üzenetrıl MPI_Datatype dtype, // Adategység típusa int *count ); // Ténylegesen küldött // adategységek száma Az egyetlen kimenı paraméter a „count” változó, hiszen a függvény a ténylegesen küldött adategységek számának meghatározására szolgál. Ne tévesszük össze az MPI_Recv függvényben szereplı buffer méretével! Az MPI_Get_count hibakóddal tér vissza.
23
A program futásának eredménye a következı: 0.processz uzenetfogadas elott: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1.processztol 111 uzenetcimkevel 10 darab adat erkezett Ezek: 10 11 12 13 14 15 16 17 18 19 2.processztol 222 uzenetcimkevel 5 darab adat erkezett Ezek: 20 21 22 23 24 0.processz uzenetfogadas utan: 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
II.3.2.3. Hogyan valósítja meg az MPI az üzenetátvitelt? Ahhoz, hogy hatékony párhuzamos programot írhassunk, fontos értenünk, hogy minként kezeli az MPI az üzenetküldı és -fogadó függvényhívásainkat. Amikor meghívjuk az MPI_Send függvényt, akkor két dolog történhet: Az egyik, hogy az üzenet átmásolódik a forrásprocesszrıl az MPI egy belsı bufferébe, ahonnan majd késıbb a célprocesszre kerül; vagy a másik lehetıség, hogy az üzenet addig a forrásprocessz bufferében tárolódik, amíg a célprocessz készen nem áll annak fogadásra, amikor is megtörténik az átvitel. Az elsı esetben a forrásprocessz továbbdolgozhat, miután az MPI belsı bufferébe másolódott a küldendı üzenet. A második esetben pedig ugyan kevesebbszer kell bufferbıl bufferbe másolni, és a felhasznált memóriaterület is kisebb, viszont ami a párhuzamos programozás szempontjából nagy hátrány, az az, hogy a forrásprocessznek várakoznia kell a célprocesszel való szinkronizációra. Attól függıen, hogy a küldendı adat mérete nagyobb-e, mint az MPI rendelkezésre álló, belsı memóriaterülete, az üzenet vagy azonnal az MPI belsı bufferébe kerül, ahonnan késıbb aszinkron módon továbbítódik; vagy a küldı és fogadó processz egymáshoz szinkronizálódik. Mind az MPI_Send, mind az MPI_Recv blokkoló függvények, ami azt jelenti, hogy egyikük sem tér vissza az üzenetátvitel befejezéséig. Az MPI_Recv esetében elég intuitív módon adódik az üzenetátvitel befejezésének jelentése, ami tehát a fogadó borítékkal megegyezı borítékú levél teljes tartalmának a fogadó processz bufferébe való másolásának befejezése. Az MPI_Send esetében pedig azt jelenti az üzenetátvitel befejezése, hogy forrásprocessz az üzenetet teljes egészében átadta az MPI-nak. Ez jelentheti a célprocesszel szinkronizált adatátvitel befejeztét, de az MPI belsı bufferébe való adatátvitel befejeztét is. Tehát a lényeg az, hogy ekkor már a forrásprocessz buffere felülírható.
II.3.2.4. A holtpont oka, és elkerülésének módja Holtpont akkor alakul ki, amikor legalább két processz – blokkoló függvényhívásaik miatt – vár egymásra. Két, egymással üzenetet cserélı processz példáján mutatjuk be, hogy pontosan milyen függvényhívási sorrendek okoznak holtpontot. A következı esetben biztosan holtpont alakul ki, mivel mindkét processz elıbb fogadni akarja a másik üzenetét, amit a fogadó függvények blokkolása miatt egyikük sem tud elküldeni. … if( myrank == 0 ) /* 0.processz */ { // Üzenetfogadás: 1.processz -> 0.processz MPI_Recv( fogad, 10, MPI_DOUBLE, 1, TAG1, MPI_COMM_WORLD, &status ); // Üzenetküldés: 0.processz -> 1.processz MPI_Send( kuld, 10, MPI_DOUBLE, 1, TAG0, MPI_COMM_WORLD ); } 24
else if( myrank == 1 ) /* 1.processz */ { // Üzenetfogadás: 0.processz -> 1.processz MPI_Recv( fogad, 10, MPI_DOUBLE, 0, TAG0, MPI_COMM_WORLD, &status ); // Üzenetküldés: 1.processz -> 0.processz MPI_Send( kuld, 10, MPI_DOUBLE, 0, TAG1, MPI_COMM_WORLD ); } … A teljes program: 5. melléklet: main3_2_4a.c A holtpontmentes párhuzamos program tervezésének legbiztosabb módja, hogy logikusan végigvezetjük gondolatban, hogy a függvényhívások sorrendjébıl fakadó feltételrendszernek van-e feloldása. A párhuzamos programok írásánál ennek az átlátása kulcsfontosságú. Ugyanakkor miközben végigkísérjük a függvényhívások feltételrendszerét, a korábban említett terhelés kiegyensúlyozásra vonatkozó modellünkön is finomíthatunk, figyelembe véve az egyes feladatok idıszükségletét. A következı kommunikáció biztosan holtpontmentes, mert a különbözı üzenetek küldése és fogadása nincs egymással átlapolva. A soron lévı üzenetet elküldjük illetve fogadjuk, és csak ezt követıen kerül sorra a következı üzenet. Tehát, még ha a küldött üzenet nagyobb is, mint az MPI belsı buffere, az üzenetátvitel nem okoz holtpontot, mert a két processz – a korábban megismert módon – szinkronizálódik egymáshoz. … if( myrank == 0 ) /* 0.processz */ { // Üzenetfogadás: 1.processz -> 0.processz MPI_Recv( fogad, N, MPI_DOUBLE, 1, TAG1, MPI_COMM_WORLD, &status ); // Üzenetküldés: 0.processz -> 1.processz MPI_Send( kuld, N, MPI_DOUBLE, 1, TAG0, MPI_COMM_WORLD ); } else if( myrank == 1 ) /* 1.processz */ { // Üzenetküldés: 1.processz -> 0.processz MPI_Send( kuld, N, MPI_DOUBLE, 0, TAG1, MPI_COMM_WORLD ); // Üzenetfogadás: 0.processz -> 1.processz MPI_Recv( fogad, N, MPI_DOUBLE, 0, TAG0, MPI_COMM_WORLD, &status ); } … A teljes program: 6. melléklet: main3_2_4b.c Ha mindkét processz elıször elküldi az üzenetét és csak azután fogadnak, akkor szükséges, hogy legalább az egyik üzenet függı üzenetként az MPI belsı bufferébe kerülhessen, hogy a hozzá tartozó MPI_Send (az MPI-ra bízva az üzenetét) visszatérhessen, és az MPI_Recv függvény fogadhassa az üzenetet. Ez a kommunikációs sorrend akkor mőködik holtpontmentesen, ha az MPI belsı buffere akkora, hogy legalább az egyik üzenet teljes egészében elfér benne. A következı példaprogram N paraméterét változtatva a program hol lefut, hol holtpontra kerül.
25
… if( myrank == 0 ) /* 0.processz */ { // Üzenetküldés: 0.processz -> 1.processz MPI_Send( kuld, N, MPI_DOUBLE, 1, TAG0, MPI_COMM_WORLD ); // Üzenetfogadás: 1.processz -> 0.processz MPI_Recv( fogad, N, MPI_DOUBLE, 1, TAG1, MPI_COMM_WORLD, &status ); } else if( myrank == 1 ) /* 1.processz */ { // Üzenetküldés: 1.processz -> 0.processz MPI_Send( kuld, N, MPI_DOUBLE, 0, TAG1, MPI_COMM_WORLD ); // Üzenetfogadás: 0.processz -> 1.processz MPI_Recv( fogad, N, MPI_DOUBLE, 0, TAG0, MPI_COMM_WORLD, &status ); } … A teljes program: 7. melléklet: main3_2_4c.c
II.3.3. Nem-blokkoló függvények II.3.3.1. A nem-blokkoló függvények használatának koncepciója A blokkoló függvényekkel ellentétben – melyek csak az üzenetátvitel befejezésekor tértek vissza –, a nem-blokkoló függvények már az üzenetátvitel kezdeményezése után visszatérnek kiküszöbölve ezzel az átvitel okozta késleltetést és a lehetséges holtpontot. Ez úgy valósul meg, hogy az üzenetátvitel kezdeményezése és teljesítése nem egy, hanem két függvényhívás hatására történik. A két függvényhívás között a processz szabadon végezhet egyéb számításokat, kihasználva az egyébként várakozással töltött idıt. A nem-blokkoló függvények két függvényhívása ugyanazt a kommunikációs hatást váltja ki, mint a blokkoló függvények egyetlen függvényhívása, csupán az MPI által definiált lehetıségeket más felületen keresztül használják fel. Ezen egyenértékőségük miatt a blokkoló és nem-blokkoló függvényeket lehet vegyesen is használni. Például, hogy a küldés blokkoló és a fogadás nem-blokkoló; vagy fordítva, hogy a küldés nem-blokkoló és a fogadás blokkoló. Visszatérve, a nem-blokkoló függvényekkel megvalósított kommunikáció egy processz részérıl két függvényhívást jelent. Ezek közül az elsı függvény a küldés vagy a fogadás kezdeményezése, amelyeket késleltetett küldésnek vagy késleltetett fogadásnak nevezünk. Miután a processz kezdeményezte az üzenetátvitelt, két különbözı módon ellenırizheti annak teljesülését. Az egyik lehetıség, hogy ellenırzi, de ha még nem fejezıdött be teljesen az átvitel, akkor folytatja az egyéb számításait, kihasználva a további várakozási idıt; a másik lehetıség pedig, hogy az ellenırzésbıl csak az átvitel teljes befejeztekor tér vissza. Intuitív módon az elıbbit tesztelésnek, az utóbbit pedig várakozásnak hívjuk. Az üzenet átvitelének kezdeményezése után a processznek valamilyen módon hivatkoznia kell tudnia a megkezdett átvitelre. Az MPI erre a célra lekérdezési paramétert definiál. Minden nem-blokkoló függvény ilyen lekérdezési paraméterrel tér vissza, mellyel azonosíthatók a megkezdett átvitelek.
26
II.3.3.2. A nem-blokkoló függvények felépítése Mindkét blokkoló függvénynek megvan a nem-blokkoló megfelelıje. int MPI_Isend ( void *buf, int count, MPI_Datatype dtype, int dest, int tag, MPI_Comm comm, MPI_Request *request );
// Küldendı adatokat tartalmazó buffer // Küldendı adategységek száma // Adategység típusa // Célprocessz azonosítója // Üzenetcímke // Kommunikátor, melybe mindkét // processz beletartozik // Lekérdezési paraméter
Az MPI_Isend paraméterezése – a plusz lekérdezési paramétert leszámítva – teljesen megegyezik az MPI_Send-ével; viszont meghívásakor csak az üzenetátvitel kezdeményezése történik meg. Tehát az MPI_Send-del ellentétben – amely csak akkor tér vissza, ha az MPI-ra bízta az üzenetét –, az MPI_Isend ezt nem várja meg, hanem az átvitel kezdeményezése után azonnal visszatér. Emiatt az MPI_Isend meghívását követıen ne módosítsuk (ne írjuk, ne olvassuk) annak paramétereit, hiszen amíg meg nem bizonyosodtunk az üzenetküldés befejeztérıl, addig ezen paraméterek megváltoztatása a küldött üzenet sérüléséhez vezethet. int MPI_Irecv ( void *buf, int count, MPI_Datatype dtype, int source, int tag, MPI_Comm comm, MPI_Request *request );
// Fogadó buffer // Maximum fogadható // adategységek száma // Adategység típusa // Forrásprocessz azonosítója // Üzenetcímke // Kommunikátor, melybe mindkét // processz beletartozik // Lekérdezési paraméter
Az MPI_Irecv paraméterezése hasonló az MPI_Recv-éhez, csupán abban különbözik, hogy az „MPI_Status *status” helyett, „MPI_Request *request” paraméter szerepel. Az MPI_Irecv által visszaadott lekérdezési paramétert felhasználva ellenırizhetjük a hozzá tartozó üzenetfogadás állapotát, vagy megvárhatjuk annak teljes befejezését. Mivel az MPI_Irecv használatakor csak az üzenetfogadás kezdeményezése történik meg, ezért amíg nem bizonyosodtunk meg arról, hogy teljesen befejezıdött az üzenetfogadás, addig ne módosítsuk (ne olvassuk, ne írjuk) az MPI_Irecv paramétereit, mert ez az üzenet sérüléséhez vezethet. Az üzenetátvitel (processzenként küldés vagy fogadás) teljes befejezését kétféleképpen ellenırizhetjük: tesztelve vagy várakozva. Tesztelés esetén úgy jutunk információhoz a nem-blokkoló függvényhez tartozó átvitel állapotáról, hogy az akár befejezıdött, akár nem, a tesztelı függvény visszatér és az eredmény függvényében dolgozhatunk tovább. Várakozás esetén – ahogy a neve is sejteti – a várakozó függvény csak az átvitel teljes befejeztekor tér vissza. Úgy is fogalmazhatunk, hogy az üzenetátvitel teljesülésének a tesztelés nem-blokkoló, míg a várakozás blokkoló változata.
27
int MPI_Wait ( MPI_Request *request, MPI_Status *status );
// A késleltetett küldés vagy fogadás // lekérdezési paramétere // Információ a fogadott üzenetrıl
A „request” lekérdezési paraméter a megkezdett átvitelek azonosítására szolgál, és az MPI_Isend illetve az MPI_Irecv tér vele vissza. A „status”-ból fogadás esetén információt nyerhetünk ki az üzenetrıl (ténylegesen fogadott adategységek száma, valamint „joker” használata esetén a forrásprocessz azonosítójának és az üzenetcímkének az értéke); küldés esetén pedig hibakódot tartalmaz. Az MPI_Wait csak akkor tér vissza, ha az üzenetátvitel a hívó processz oldaláról teljesen befejezıdött. Sikeres átvitel esetén a korábbi függvényekhez hasonlóan MPI_Success-ezel tér vissza. (Üzenetküldés esetén a „status” másfajta hibakódot tartalmaz.) Összefoglalva, a „request” bemenı, a „status” pedig kimenı paraméter. int MPI_Test ( MPI_Request *request, int *flag, MPI_Status *status );
// A késleltetett küldés vagy fogadás // lekérdezési paramétere // Az átvitel teljesülését jelzı zászló // Információ a fogadott üzenetrıl
A „request” paraméterrıl ugyanaz mondható el, mint az MPI_Wait esetében. Az MPI_Test abban különbözik az MPI_Wait-tıl, hogy akár befejezıdött az átvitel, akár nem, az MPI_Test mindenképpen visszatér, és a processz az eredmény függvényében folytathatja egyéb munkáját. A „flag” igaz értékével jelzi az átvitel befejeztét; és ekkor a „status” tartalma megegyezik az MPI_Wait esetén leírtakkal. Ha pedig a „flag” értéke hamis, akkor a „status” értéke definiálatlan marad. Emiatt a „flag”-nek csak igaz értéke mellett vizsgáljuk a „status” tartalmát. Üzenetfogadás esetén, ha a „flag” értéke igaz, akkor a „status”-ból kinyerhetjük a ténylegesen fogadott adategységek számát, valamint „joker” használata esetén a forrásprocessz azonosítójának és az üzenetcímkének az értékét is. (A flag igaz vagy hamis értékét logikai értelemben vesszük, tehát igaz > 0, hamis = 0.) Összefoglalva, a „request” bemenı, a „flag” és a „status” pedig kimenı paraméterek.
28
Leginkább a holtpont elkerülésének céljából használjuk a megismert nem-blokkoló függvényeket. A várakozási idı kihasználása a másik jelentıs tényezı, amit ha fix hosszúságú feladattal kívánunk kitölteni, akkor MPI_Wait-et; ha pedig a változó hosszúságú feladattal akarjuk optimálisan kihasználni, akkor MPI_Test-et használunk. Tekintsünk egy példaprogramot az MPI_Wait használatára! … if( myrank == 0 ) /* 0.processz */ { // Üzenetfogadás kezdeményezése: 1.processz -> 0.processz MPI_Irecv( fogad, N, MPI_DOUBLE, 1, TAG1, MPI_COMM_WORLD, &request ); // Üzenetküldés: 0.processz -> 1.processz MPI_Send( kuld, N, MPI_DOUBLE, 1, TAG0, MPI_COMM_WORLD ); // Várakozás MPI_Wait( &request, &status ); } else if( myrank == 1 ) /* 1.processz */ { // Üzenetfogadás kezdeményezése: 0.processz -> 1.processz MPI_Irecv( fogad, N, MPI_DOUBLE, 0, TAG0, MPI_COMM_WORLD, &request ); // Üzenetküldés: 1.processz -> 0.processz MPI_Send( kuld, N, MPI_DOUBLE, 0, TAG1, MPI_COMM_WORLD ); // Várakozás MPI_Wait( &request, &status ); } … A teljes program: 8. melléklet: main3_3_2a.c A kódrészlet üzenetcserét valósít meg. Mindkét processz elıször kezdeményezi az üzenetfogadást, majd blokkolva elküldi saját üzenetét, végül várakozik a másik üzenetének megérkezéséig. Ilyen módon akárhány processz kommunikációja holtpontmentesen összekapcsolható.
29
Tekintsünk egy példaprogramot az MPI_Test használatára! … if( myrank == 0 ) /* 0.processz */ { // Üzenetfogadás kezdeményezése: 1.processz -> 0.processz MPI_Irecv( fogad, N, MPI_DOUBLE, 1, TAG1, MPI_COMM_WORLD, &request ); // Üzenetküldés: 0.processz -> 1.processz MPI_Send( kuld, N, MPI_DOUBLE, 1, TAG0, MPI_COMM_WORLD ); // Elsı tesztelés esztelés MPI_Test(&request, &flag, &status); while (!flag) { /* Egyéb számítások a várakozási idı kihasználására */ for(j;j<=100;j++) szamol*=j; // Tesztelés MPI_Test(&request, &flag, &status); } // Számítás befejezése for(j;j<=100;j++) szamol*=j; } else if( myrank == 1 ) /* 1.processz */ { // Üzenetfogadás kezdeményezése: 0.processz -> 1.processz MPI_Irecv( fogad, N, MPI_DOUBLE, 0, TAG0, MPI_COMM_WORLD, &request ); // Üzenetküldés: 1.processz -> 0.processz MPI_Send( kuld, N, MPI_DOUBLE, 0, TAG1, MPI_COMM_WORLD ); // Elsı tesztelés esztelés MPI_Test(&request, &flag, &status); while (!flag) { /* Egyéb számítások a várakozási idı kihasználására */ for(j;j<=100;j++) szamol+=j; // Tesztelés MPI_Test(&request, &flag, &status); } // Számítás befejezése for(j;j<=100;j++) szamol+=j; } … A teljes program: 9. melléklet: main3_3_2b.c
30
II.3.3.3. A küldı függvények variánsai Az eddig megismert üzenetküldı függvényeket, mind a blokkolót, mind a nemblokkolót tovább specifikálhatjuk. Variánsaik négy csoportba oszthatók. Standard mód A leguniverzálisabb küldési mód, mert minden egyes üzenetküldés esetén az MPI választja meg küldés megvalósításának módját. Az eddigiekben az idetartozó függvények mőködését részleteztük. Szinkronizált mód A küldött üzenet mindig közvetlenül az egyik processz bufferébıl a másik processz bufferébe kerül, tehát még ideiglenesen sem kerül az MPI belsı bufferébe. A blokkoló esetben a függvény csak akkor tér vissza, ha a fogadó oldalon már megkezdıdött az adatok fogadása; nem-blokkoló esetben pedig csak a szinkronizált átvitelt kezdeményezi a függvény. Tehát egyik esetben sem lehetünk biztosak abban, hogy az üzenet teljes egészében megérkezett a fogadó oldalra; a blokkoló esetben viszont annyit biztosan tudunk, hogy a küldı függvény visszatérésekor az üzenet átmásolása már megkezdıdött. Bufferelt mód A küldött üzenet mindig az MPI belsı bufferébe másolódik, és csak onnan tovább a célprocesszre. Ha nincs elég szabad hely az MPI belsı bufferében, akkor hibakóddal tér vissza a függvény. Blokkoló esetben a függvény csak az MPI belsı bufferébe való másolás befejezése után tér vissza, míg nem-blokkoló esetben a másolás kezdeményezése után azonnal visszatér. Ready (Elıkészített) mód Ez a küldési mód azt feltételezi, hogy fogadó oldalon már kezdeményeztek egy üzenetfogadást. Mőködésében teljesen egyenértékő a standard küldı függvénnyel, viszont elınye, hogyha plusz információval rendelkezünk a fogadó processz állapotáról (tudniillik, hogy az már kezdeményezte egy olyan üzenet fogadását, aminek borítéka megegyezik a küldött üzenet borítékával), akkor az MPI belsı protokollja hatékonyabban tudja továbbítani az üzenetet. Ennek a gyorsabb megvalósításnak viszont az a hátránya, hogy ha az üzenet célprocessz oldali várását feltételezve küldünk, és ott még nem kezdeményezték a fogadást, akkor hibát okozunk és a további kimenetel definiálatlan. A blokkoló és nem-blokkoló változat között ugyanaz a különbség, mint a standard mód két változata között. Elnevezések, paraméterek Küldési mód Standard Szinkronizált Bufferelt Ready (Elıkészített)
Blokkoló függvény MPI_Send MPI_Ssend MPI_Bsend MPI_Rsend
Nem-blokkoló függvény MPI_Isend MPI_Issend MPI_Ibsend MPI_Irsend
A blokkoló függvények paraméterlistája az MPI_Send-ével egyezik meg, a nem-blokkoló függvényeké pedig az MPI_Isend-ével. Az MPI_Recv vagy az MPI_Irecv valamelyikét tetszılegesen használhatjuk az üzenetek fogadására, függetlenül a küldési módtól.
31
Ellenırzı kérdések: 1.) Mi történik, ha egyszerre több üzenetet küldenek ugyanannak a processznek? 2.) Milyen sorrendben dolgozza fel a fogadó processz a várakozó üzeneteket? 3.) Mik az üzenetküldéses modell elemei? 4.) Milyen módon kommunikál egymással a forrás- és a célprocessz, és ez milyen esetekhez vezet? 5.) Milyen részekbıl áll egy üzenet? 6.) Mikrıl kell gondoskodni függı üzenetek fogadásakor? 7.) Mikor, milyen esetekben használunk „joker” processz-azonosítót és üzenetcímkét? 8.) Honnan tudjuk meg a forrásprocessz azonosítóját, az üzenet címkéjét, illetve a küldött adategységek számát „joker” azonosító és címke használata esetén? 9.) Hogyan valósítja meg az MPI az üzenetátvitelt? Milyen két eset lehetséges? 10.) Miben különböznek a nem-blokkoló függvények a blokkoló függvényektıl? 11.) Mikor használunk MPI_Wait-et és mikor MPI_Test-et?
Feladatok: 1.) Próbáljuk ki a main3_2_1.c példaprogramot! 2.) Próbáljuk ki a main3_2_2a.c példaprogramot! 3.) Próbáljuk ki a main3_2_2b.c példaprogramot! 4.) Ellenırizzük, hogy tényleg holtpontra kerül-e a main3_2_4a.c példaprogram! 5.) Próbáljuk ki, hogy minden N érték esetén lefut-e a main3_2_4b.c példaprogram! 6.) Keressük meg, hogy mely N értékek esetén fut le, és mely N értékek esetén kerül holtpontra a main3_2_2b.c példaprogram! 7.) Próbáljuk ki a main3_3_2a.c példaprogramot! 8.) Próbáljuk ki a main3_3_2b.c példaprogramot! 9.) Írjunk egy programot, amelyben egy master és legalább három slave processz kommunikál egymással!
32
II.4. Kollektív kommunikáció és fajtáinak megismerése A csoporton belüli, vagy más szóval kollektív kommunikáció, – a pont-pont kommunikációhoz hasonlóan – szintén üzenetek küldését és fogadását jelenti, azzal a különbséggel, hogy az nem csak két, hanem több processz között történik. A párhuzamos programjainkat megírhatnánk kizárólag pont-pont kommunikáció alkalmazásával is, de támogatásként az MPI a gyakran szükséges üzenet-átviteli függvényhívás-sorrendeket optimálisan megvalósított szolgáltatássá összefogva bocsátja rendelkezésünkre. Ilyen módon a kollektív kommunikáció megvalósításának bonyolultságától eltekintve élvezhetjük hatékony hatásukat, és használhatjuk tömör kifejezıképességüket. Mivel kollektív kommunikáció során egy csoport összes tagja között történik üzenetátvitel, ezért nincs szükség – a pont-pont kommunikációnál megszokott – üzenetcímkére, viszont arra figyelni kell, hogy a csoport összes processze meghívja a kollektív kommunikációt megvalósító függvényt. A processzek kommunikátorba csoportosulnak; és csak az egy kommunikátorba tartozó processzek tudnak kommunikálni egymással. Az MPI_COMM_WORLD az összes processzt tartalmazza, de ezen belül létrehozhatunk kisebb halmazokat, azaz újabb kommunikátorokat is.
II.4.1. Alapvetı függvények II.4.1.1. Szinkronizáló sorompó Amikor egy processz olyan munkát végez, amelynek eredményére a többi processznek szüksége van, akkor a többi processznek várnia kell erre a processzre. Leggyakrabban a slave processzek várnak a master processzre, amíg az fájlmőveleteket végez. Az MPI_Barrier függvény megállítja az összes processzt mindaddig, amíg a csoport valamennyi tagja meg nem hívja ıt. int MPI_Barrier ( MPI_Comm comm );
// A szinkronizálandó processzek // közös kommunikátora
Bár az MPI_Barrier nem továbbít adatokat, mégis szinkronizálja az egy kommunikátorba (csoportba) tartozó processzeket azáltal, hogy csak azt követıen tér vissza, amikor már a csoport összes tagja meghívta ıt.
33
II.4.1.2. Üzenetszórás Az MPI_Bcast függvény hatására a forrásprocesszrıl az adott kommunikátorba tartozó összes processzre átmásolódik a küldött adat (4. ábra). A egyes processzeken ugyanolyan nevőnek kell lennie a fogadóbuffernek, mint a forrásprocessz küldıbuffere. Ez általában könnyen teljesíthetı is, mivel a változó deklarálások a programkód elején, az összes processz által végrehajtott területen vannak. A programozó felelıssége gondoskodni arról, hogy az adott csoportba tartozó összes processz meghívja ezt a függvényt, különben a kimenetel definiálatlan. Ugyanez a kitétel érvényes az összes többi kollektív kommunikációt megvalósító függvényre is.
4. ábra int MPI_Bcast ( void* buffer, int count, MPI_Datatype datatype, int root, MPI_Comm comm );
// A küldıbuffer és egyben // a fogadóbufferek kezdıcíme // Adategységek száma a küldıbufferben // Adategység típusa a küldıbufferben // Forrásprocessz azonosítója // Kommunikátor, melybe az összes // címzett és a küldı processz is // beletartozik
Összefoglalásul, a „buffer” kimenı, illetve bemenı paraméter; a maradék négy pedig mind bemenı paraméterek. Tekintsünk egy példaprogramot az MPI_Bcast használatára! 10. melléklet: main4_1_2.c
34
II.4.1.3. Szétosztás Az MPI_Scatter az MPI_Bcast-hoz hasonlóan egy processzrıl küld adatokat az összes kommunikátorbeli processzre – saját magát szintén beleértve – ; viszont az MPI_Bcast-tal ellentétben már különbözı adatokat küld. Meghívásakor a forrásprocessz a bufferében lévı tömböt egyenlı hosszúságú részekre darabolja fel, amiket az egyes processzeknek azonosítójuk sorrendjében oszt szét (5. ábra).
5. ábra // A küldıbuffer kezdıcíme // Az egy processznek küldendı // adategységek száma MPI_datatype send_type, // Adategység típusa a küldıbufferben void* recv_buffer, // A fogadóbufferek kezdıcíme int recv_count, // Egy fogadóbufferben // az adategységek száma MPI_Datatype recv_type, // Adategység típusa a fogadóbufferekben int root, // Forrásprocessz azonosítója MPI_Comm comm ); // Kommunikátor, melybe az összes // címzett és a küldı processz is // beletartozik
int MPI_Scatter ( void* send_buffer, int send_count,
Összefoglalva, a fogadóbufferek kivételével az összes paraméter bemenı.
35
II.4.1.4. Összegyőjtés Az MPI_Gather az adott kommunikátorba tartozó összes processzrıl összegyőjti az adatokat egyetlen processz bufferébe (6. ábra), tehát az MPI_Scatter-nek pont inverz mővelete.
6. ábra // A küldıbufferek kezdıcíme // Az egyes küldıbufferekben lévı, // küldendı adategységek száma // Adategység típusa // a küldıbufferekben // A fogadóbuffer kezdıcíme // A fogadóbufferben // az adategységek száma // Adategység típusa // a fogadóbufferben // Célprocessz azonosítója // Kommunikátor, melybe az összes // küldı és a címzett processz is // beletartozik
int MPI_Gather ( void* send_buffer, int send_count, MPI_datatype send_type, void* recv_buffer, int recv_count, MPI_Datatype recv_type, int dest, MPI_Comm comm );
Összefoglalva, a fogadóbuffer kivételével az összes paraméter bemenı. Tekintsünk használatára!
egy
példaprogramot
11. melléklet: main4_1_4.c
36
az
MPI_Scatter
és
az
MPI_Gather
II.4.1.5. Összegyőjtés mőveletvégzéssel Az MPI_Reduce az MPI_Gather-hez hasonlóan az adott kommunikátorba tartozó összes processzrıl győjti össze az adatokat. Amiben az MPI_Reduce több, mint az MPI_Gather, az az, hogy az összegyőjtött adatokon mőveletet végez, és csak a mővelet eredményét menti a célprocesszre (7. ábra). Alapértelmezésben csak olyan mőveletek definiáltak, amelyek csökkentik (redukálják) az küldött üzenet méretét. Ha tömböket győjtünk össze, akkor az azonos indexő elemek között végezhetünk mőveletet.
7. ábra // A küldıbufferek kezdıcíme // A fogadóbuffer kezdıcíme // Az egyes küldıbufferekben lévı, // küldendı adategységek száma // Adategység típusa // a küldıbufferekben // „Redukáló” mővelet // Célprocessz azonosítója // Kommunikátor, melybe az összes // küldı és a címzett processz is // beletartozik
int MPI_Reduce ( void* send_buffer, void* recv_buffer, int count, MPI_Datatype datatype, MPI_Op operation, int dest, MPI_Comm comm );
Összefoglalva, a fogadóbuffer kivételével az összes paraméter bemenı. Tekintsünk egy példaprogramot az MPI_Reduce használatára! 12. melléklet: main4_1_5.c
37
Néhány alapértelmezett „redukáló” mővelet MPI_MAX MPI_MIN MPI_SUM MPI_PROD MPI_LAND MPI_BAND MPI_LOR MPI_BOR MPI_LXOR MPI_BXOR
Maximum Minimum Összeg Szorzat Logikai És Bitenkénti És Logikai Vagy Bitenkénti Vagy Logikai Kizáró Vagy Bitenkénti Kizáró Vagy
II.4.2. Alapvetı függvények variánsai Ha különbözı mértékben szeretnénk szétosztani a terhelést a különbözı processzek között, akkor ezt az adattömb különbözı mérető részekre darabolásával, processzek közötti szétosztásával, majd a feldolgozást követıen összegyőjtésével tehetjük. Ennek hatékony megvalósítására szolgálnak a különbözı elemszámú tömbrészekkel dolgozó szétosztó (MPI_Scatterv) és összegyőjtı (MPI_Gatherv) függvények.
II.4.2.1. Különbözı mérető részek szétosztása Az MPI_Scatterv függvény segítségével az MPI_Scatter-rel megvalósítható adattömb feldarabolást és szétosztást valósíthatunk meg, viszont az egyes processzekhez már tetszıleges elemszámú tömbrészletet rendelhetünk. int MPI_Scatterv ( void* send_buffer, int* send_counts, int* displacements,
MPI_Datatype sendtype, void* recv_buffer, int recv_count, MPI_Datatype recvtype, int root, MPI_Comm comm );
38
// A küldıbuffer kezdıcíme // Az egyes processzeknek küldendı // tömbrészek elemszámai // Az egyes processzeknek küldendı // tömbrészeknek a küldıbuffer // kezdıcíméhez képesti relatív // kezdıcímei // Adategység típusa // a küldıbufferben // Az adott fogadóbuffer kezdıcíme // Az adott fogadóbufferben // az adategységek száma // Adategység típusa // a fogadóbufferekben // Forrásprocessz azonosítója // Kommunikátor, melybe az összes // címzett és a küldı processz is // beletartozik
Az egyes processzeknek küldendı tömbrészletek elemszámait és a küldıbuffer kezdıcíméhez viszonyított relatív kezdıcímeit a „send_counts” és „displacesments” int típusú tömbökben a processzek azonoítójának megfelelıen helyezzük el. A többi paraméter megegyezik az MPI_Scatter-nél megismertekkel. Összefoglalva, a fogadóbufferek kivételével az összes paraméter bemenı.
II.4.2.2. Különbözı mérető részek összegyőjtése Az MPI_Gatherv függvény az MPI_Gather-nél megismert adatösszegyőjtı funkciót látja el, viszont az MPI_Scatterv inverzeként már különbözı elemszámú tömbrészeket is össze tud rendezni egyetlen processz bufferébe. int MPI_Gatherv ( void* send_buffer, int send_counts, MPI_Datatype sendtype, void* recv_buffer, int* recv_counts, int* displacements,
MPI_Datatype recvtype, int root, MPI_Comm comm );
// A küldıbufferek kezdıcíme // Az egyes küldıbufferekben lévı, // küldendı adategységek száma // Adategység típusa // a küldıbufferekben // A fogadóbuffer kezdıcíme // Az egyes processzektıl fogadott // tömbrészletek elemszámai // Az egyes processzek által küldött // tömbrészeknek a fogadóbuffer // kezdıcíméhez képesti relatív // kezdıcímei // Adategység típusa // a fogadóbufferben // Célprocessz azonosítója // Kommunikátor, melybe az összes // küldı és a címzett processz is // beletartozik
Az egyes processzek tömbrészletének elemszámai az adott processz „send_count” változójában, illetve a célprocessz „recv_count” tömbjében az adott processz azonosítójának megfelelı indexő helyen vannak. A célprocesszre érkezı tömbrészletek a fogadóbuffer kezdıcíméhez képest a „displacements” tömbnek szintén az adott processz azonosítójának megfelelı indexő helyén lévı relatív kezdıcímre kerülnek. Összefoglalva, a fogadóbufferek kivételével az összes paraméter bemenı. Tekintsünk egy példaprogramot az MPI_Scatterv és az MPI_Gatherv használatára! 13. melléklet: main4_2_2.c Az 11. mellékletben szereplı main4_1_4.c példaprogramhoz képest – ahol az MPI_Scatter-et használtuk –, az MPI_Scatterv alkalmazával megvalósított üzenetküldés ugyan nagyobb elıkészítést igényel; viszont így, hogy a master processzhez kevesebb feldolgozást rendeltünk, az kevésbé válik szők keresztmetszetté, amikor a slave processzek már elkészültek a feldolgozással, és már visszaküldenék az adatokat. Ahogy a példaprogramban is bemutatásra került, az „sendcounts” illetve „recvcounts” tömböket, valamint a „displacements” tömböt értelemszerően csak a forrásprocesszen
39
(MPI_Scatterv esetén) illetve a célprocesszen (MPI_Gatherv esetén) kell megadni. A többi paramétert, mint például a „recvcount” illetve „sendcount” változókat az adott processznek megfelelıen kell megadni. Ekkor minden processz ugyanolyan nevő változót tesz a paraméterlistájára, viszont processzenként ezeknek a változóknak lehet más és más az értéke. Összefoglalásul Alapvetı kollektív kommunikációs függvények és variánsaik MPI_Barrier MPI_Bcast MPI_Scatter MPI_Scatterv MPI_Gather MPI_Gatherv MPI_Reduce -
II.4.3. Összetett függvények Az összetett kollektív függvények több, egymást követı kollektív függvényhívást valósítanak meg egyetlen függvényhívásban. Használatukkal tömörebbé és kifejezıbbé tehetjük a programkódunkat, és gyorsíthatjuk processzeink futását.
II.4.3.1. Összegyőjtés és mindenkinek elküldés Az MPI_Allgather függvény az MPI_Gather-hez hasonlóan az összes kommunikátorbeli processzrıl győjt össze az adatokat, viszont azokat nem csak egy, hanem az összes processzen letárolja (8. ábra). Tehát az MPI_Gather és az MPI_Bcast egymás utáni alkalmazását helyettesíti.
8. ábra
40
int MPI_Allgather ( void* sendbuf, int sendcount, MPI_Datatype sendtype, void* recvbuf, int recvcount, MPI_Datatype recvtype, MPI_Comm comm );
// A küldıbufferek kezdıcímei // Az egyes küldıbufferekben lévı, // küldendı adategységek száma // Adategység típusa // a küldıbufferekben // A fogadóbufferek kezdıcímei // Az egyetlen processztıl fogadandó // adategységek száma // Adategység típusa // a fogadóbufferekben // Kommunikátor, melybe az összes // küldı és címzett processz is // beletartozik
A „sendcount”-ba a processzek által egyenként küldött adategységek számát írjuk; a „recvcount”-ba pedig az egy processztıl fogadott adategységek számát. A „recvbuf” tömbnek – processzenként – tehát a processzek számaszor recvcount méretőnek kell lennie. Összefoglalva, a fogadóbufferek kivételével az összes paraméter bemenı. Tekintsünk egy példaprogramot az MPI_Allgather használatára! 14. melléklet: main4_3_1.c A példaprogramban, annak érdekében, hogy demonstrálhassuk az MPI_Allgather mőködését, mindegyik processz a standard kimenetre írja a fogadott üzenetét. Ha több processz írna párhuzamosan ugyanazon kimenetre, akkor a kimenetel definiálatlan lenne, ami természetesen nem megengedhetı. Az MPI_Barrier függvény segítségével érjük el, hogy ne legyen kavarodás, hanem a processzek várjanak egymásra. A már elkészült párhuzamos programok esetén általában csak egyetlen processz szokott írni a kimenetre, vagy olvasni a bemenetrıl, illetve a fájlokat kezelni; elkerülve ezzel a – függvény mőködésének szemléltetése céljából bemutatott – kisorosítást.
41
II.4.3.2. Összegyőjtés mőveletvégzéssel és mindenkinek elküldés Az MPI_Allreduce függvény ugyanannyival több az MPI_Reduce-nál, mint az MPI_Allgather az MPI_Gather-nél; azaz az összegyőjtött adatokkal végzett mővelet eredményét az összes processzen tárolja le (9. ábra). Ha tömbök elemein végzünk mőveletet, akkor az eredmények is – minden processzen – tömbben tárolódnak le.
9. ábra Az egyes processzek küldıbufferének azonos indexő elemein értelmezettek a mőveletek; az eredmények pedig ezen indexeknek megfelelı helyre tárolódnak le minden egyes processz fogadóbufferébe. A jobb átláthatóság kedvéért a 9. ábrán eredményenként különbözı nyilat használtunk. int MPI_Allreduce ( void* sendbuf, void* recvbuf, int count,
MPI_Datatype datatype, MPI_Op op, MPI_Comm comm );
// A küldıbufferek kezdıcímei // A fogadóbufferek kezdıcímei // Az egyes küldıbufferekben // lévı, küldendı adategységek // száma // Adategység típusa // a küldıbufferekben // „Redukáló” mővelet // Kommunikátor, melybe // az összes küldı és címzett // processz is beletartozik
Összefoglalva, a fogadóbufferek kivételével az összes paraméter bemenı. Tekintsünk egy példaprogramot az MPI_Allreduce használatára! 15. melléklet: main4_3_2.c
42
II.4.3.3. Szétosztás mindenkitıl mindenkinek Az MPI_Alltoall függvény ugyanazt a hatást eredményezi, mintha a kommunikátorban lévı összes processz egy-egy MPI_Scatter függvényhívást kezdeményezne. Az eddigi összes összetett kommunikációs függvényhez hasonlóan, itt is minden processz küld adatot minden processznek. A processzek azonosítói és a processzek fogadóbuffereibe érkezı adatok sorrendje között fontos összefüggés van: Az átvitt adatok – akár tömbök, akár pusztán változók – az ıket küldı processzek azonosítójának megfelelı helyre kerülnek fogadáskor (10. ábra).
10. ábra Tehát az „i”-edik processz által a „j”-edik processznek küldött adat a „j”-edik processz fogadóbufferében az „i * egyetlen processznek küldött adat hossza” kezdıcímő helyre kerül. Ha az adatok hosszától eltekintünk, akkor az MPI_Alltoall mővelet mátrixtranszponálásra emlékeztet. int MPI_Alltoall ( void* sendbuf, int sendcount,
MPI_Datatype sendtype, void* recvbuf, int recvcount, MPI_Datatype recvtype, MPI_Comm comm );
// A küldıbufferek kezdıcímei // Az egy processz által // egy processznek küldött // adategységek száma // Adategység típusa // a küldıbufferekben // A fogadóbufferek kezdıcímei // Az egyetlen processztıl fogadandó // adategységek száma // Adategység típusa // a fogadóbufferekben // Kommunikátor, melybe // az összes küldı és címzett // processz is beletartozik
Összefoglalva, a fogadóbufferek kivételével az összes paraméter bemenı. Tekintsünk egy példaprogramot az MPI_Alltoall használatára! 16. melléklet: main4_3_3.c
43
II.4.3.4. Összegyőjtés mőveletvégzéssel és szétosztás Az MPI_Reduce_scatter a processzek küldıbuffereinek azonos indexő elemein végez mőveletet, és az eredményeket szétosztja az egyes processzek között (11. ábra).
11. ábra Az MPI_Reduce_scatter az eddig bemutatott összetett kollektív kommunikációs függvényekkel ellentétben, nem feltétlen egyenlı mértékben osztja szét az érkezı adatokat – jelen esetben a mőveletek eredményeit – a processzek között. Lehetıség van arra, hogy számszerően megadjuk a szétosztás arányát. A „recvcounts” tömb „i”-edik indexő helyére írt számnak megfelelı számú adategység érkezik az „i”-edik processz fogadóbufferébe. int MPI_Reduce_scatter ( void* sendbuf, void* recvbuf, int *recvcounts,
MPI_Datatype datatype, MPI_Op op, MPI_Comm comm );
// A küldıbufferek kezdıcímei // A fogadóbufferek kezdıcímei // Az egyes processzek által // fogadott tömbrészletek // elemszámai // Adategység típusa // a küldıbufferekben // „Redukáló” mővelet // Kommunikátor, melybe // az összes küldı és címzett // processz is beletartozik
Összefoglalva, a fogadóbufferek kivételével az összes paraméter bemenı. Tekintsünk egy példaprogramot az MPI_Reduce_scatter használatára! 17. melléklet: main4_3_4.c
44
Összefoglalásul Amint láttuk, az MPI_Reduce_scatter-rel megvalósítható az egyenlı mértékő és a különbözı mértékő adatszétosztást is. Ellenben adad olyan függvény, mint például, az MPI_Allreduce, ahol a mővelet jellegébıl fakadóan csak az adatokat egyenlı mértékben szétosztó változat létezhet. Mind az MPI_Allgather-nek, mind az MPI_Alltoall-nak létezik az adatokat különbözı mértékben szétosztó változata is (MPI_Allgatherv és MPI_Alltoallv), melyek használata és paraméterezése az eddig megismert függvények alapján intuitívan adófik. Összetett kollektív kommunikációs függvények és variánsaik MPI_Allgather MPI_Allgatherv MPI_Allreduce MPI_Alltoall MPI_Alltoallv MPI_Reduce_scatter
Ellenırzı kérdések: 1.) Van-e végeredménybeli különbség a között, hogy üzenetátvitelekre kollektív kommunikációs függvényeket használunk, vagy pedig pont-pont kommunikációs függvények sorozatát? Ha van különbség, akkor miben van? Ha nincs, akkor miért használunk mégis kollektív kommunikációs függvényeket? 2.) Mi egy kommunikátor szerepe? Mire kell figyelni a kollektív kommunikációs függvények meghívásánál? 3.) Melyek az alapvetı kollektív kommunikációs függvények? Hogyan jellemezhetıek röviden? 4.) Melyek az alapvetı kollektív kommunikációs függvények variánsai? Hogyan jellemezhetık röviden? 5.) Melyek az összetett kollektív kommuniációs függvények? Hogyan jellemezhetık röviden?
Feladatok: 1.) Próbáljuk ki a main4_1_2.c példaprogramot! 2.) Próbáljuk ki a main4_1_2.c példaprogramot! 3.) Próbáljuk ki a main4_1_4.c példaprogramot! 4.) Próbáljuk ki a main4_1_5.c példaprogramot! 5.) Próbáljuk ki a main4_2_2.c példaprogramot! 6.) Próbáljuk ki a main4_3_1.c példaprogramot! 7.) Próbáljuk ki a main4_3_2.c példaprogramot! 8.) Próbáljuk ki a main4_3_3.c példaprogramot! 9.) Próbáljuk ki a main4_3_4.c példaprogramot! 10.) Írjunk egy programot, amelyben egy master és legalább három slave processz a lehetı leghatékonyabban dolgozik együtt és kommunikál egymással! Fogalmazzuk meg röviden, hogy miben rejlik a megírt program hatékonysága!
45
II.5. Származtatott adattípusok és struktúrák létrehozása és átvitele Az adatok, amikkel dolgozunk, és amiket küldeni, fogadni szeretnénk általában különbözı adattípusúak, és gyakran szétszórva helyezkednek el egy tömbben. Ha az eddig tanultak felhasználásával szeretnénk elküldeni ezeket a különbözı típusú és egy tömbben szétszórva elhelyezkedı adatokat, akkor az egynemő és a tömbben egymás mellett elhelyezkedı adatokat összefogva kisebb mérető, különálló üzenetekben küldenénk el. Például, ha egy háromszögeket tartalmazó struktúratömböt szeretnénk átküldni, illetve fogadni, akkor ez az oldalak és a szögek különbözı adattípusa miatt nagyon körülményes lenne. Vagy például, ha egy kétdimenziós mátrix almátrixait szeretnénk szétosztani a slave processzek között, akkor az almátrixok minden egyes sorát külön üzenetben küldhetnénk; nem beszélve arról, hogy az almátrixok összegyőjtésekor ugyanezen kommunikációs mőveletsort az ellenkezı irányban is meg kellene ismételnünk. Az almátrixok szétosztását megoldhatjuk még az almátrixok kisebb tömbökbe másolásával majd azok elküldésével, de ezen módszer hátránya az extra memóriaterület felhasználáson kívül, hogy a másolásra a processzornak plusz idıt kell fordítania, rontva ezzel a párhuzamos program hatékonyságát. Ezenkívül a különbözı adattípusok problémája továbbra sincs megoldva.
II.5.1. Hogyan továbbítja az MPI az adattípusokat? Ha mindenképpen egy üzenetben szeretnénk elküldeni az adatokat, akkor hajolhatunk arra, hogy a többségtıl eltérı adatok típusát átkonvertáljuk a többivel megegyezı típusúra, de mivel a konvertálás általában több processzoridıbe kerül, mint a másolás, ezért ez sem hatékony megoldás. Ha a konvertálási idıt úgy próbáljuk megspórolni, hogy – az azonos adattípus méretekre alapozva – pusztán felülírjuk a küldıbuffer adattípusát egy másik adattípussal, mondván, hogy a bitmintából majd a másik processz oldalán visszaállítjuk a helyes értéket, súlyos hibát vétünk! Ugyanis ezen módszer tesztelésekor valószínőleg helyesen fut majd le a programunk, de amikor ezt több processzoros környezetben futtatjuk, akkor már minden bizonnyal hibás mőködésre vezet; mikor viszont a hiba már csak nehezen vehetı észre. A hiba forrása, hogy az MPI nem csak bitmintákat, hanem értékeket is továbbít. Amikor olyan processzorokkal dolgozunk, melyek számábrázolása adattípusonként megegyezik, akkor az MPI optimalizálja az üzenetátvitel megvalósítását azáltal, hogy egyszerően csak a bitmintákat továbbítja. Ha viszont eltérı számábrázolást használó processzorokból áll az architektúra, amin a párhuzamos programunk fut, akkor az MPI a küldött változó – névleges adattípusának megfelelı – értékét megtartva, azt küldés elıtt egy standard, köztes számábrázolási formátumra alakítva továbbítja, majd a fogadó oldalon, az ottani architektúra számábrázolásának megfelelıen alakítja vissza. Ezáltal biztosított, hogy a tetszıleges számábrázolású számítógépek akadály nélkül összekapcsolhatóak legyenek. Így lehetséges, hogy az üzenetek tartalmát akkor is gond nélkül továbbítsuk, amikor az a két processz oldalán más-másképpen ábrázolódik.
46
II.5.2. Adatok csomagolt átvitele Ha különbözı típusú vagy tömbben nem egymás mellett elhelyezkedı adatokat szeretnénk egyetlen bufferbe csomagolva a processzek között átvinni, akkor ezt – elızetes konverziók nélkül – az MPI_Pack, az MPI_Unpack és MPI_Pack_size függvényekkel készíthetjük elı, és az eddig megismert kommunikációs függvények bármelyikével vihetjük át. Ezen függvények használatának elınye, hogy nincs szükség a nagyobb processzoridıt igénylı konverziókra, csupán az átviendı adatok megfelelı módon való bufferbe csomagolására, illetve onnan kicsomagolására. A csomagolás illetve kicsomagolás valójában adott címre való másolást és a címmutató léptetését jelenti. Az átvitelre használt buffer adattípusa bármilyen az MPI_Send által értelmezett típus lehet. Mivel a csomagolt adattípus (MPI_PACKED) mérete byte-okban mérendı, ezért érdemes char tömböt választani. Egy másik megfontolás lehet, hogy a buffer elején lévı adatok adattípusának, vagy a legtöbb küldendı adat adattípusának megfelelı buffert választunk. Mindennek csak a memóriaterület lefoglalása szempontjából van jelentısége, hiszen akár többféle adattípust is másolhatunk az így lefoglalt tömbünkbe, ami a becsomagolás után egy osztatlan MPI_PACKED adattípusú változóvá válik. A legszemléletesebben úgy képzelhetı el ez az átvitel, mint egy kívülrıl átlátszatlan FIFO sor átvitele. Az átviendı adatainakat az MPI_Pack-kel csomagoljuk be a forrás processz oldalán, és az MPI_Unpack-kel csomagoljuk ki a célprocessz oldalán. int MPI_Pack ( void* inbuf, int incount, MPI_Datatype datatype, void* outbuf, int outsize, int* position, MPI_Comm comm );
// Az átviteli bufferbe csomagolandó // tömb // Az átviteli bufferbe csomagolandó // tömb elemeinek a száma // Az átviteli bufferbe csomagolandó // tömb adattípusa // Az átviteli buffer // Az átviteli buffer mérete byte-ban // Az átviteli bufferben a következı // szabad hely címe // Kommunikátor, melybe a küldı // és a fogadó processzek tartoznak
// Az átviteli buffer // Az átviteli buffer mérete byte-ban // Az átviteli buffer címmutatója // Az átviteli bufferbıl kicsomagolandó // tömb int outcount, // Az átviteli bufferbıl kicsomagolandó // tömb elemeinek a száma MPI_Datatype datatype, // Az átviteli bufferbıl kicsomagolandó // tömb adattípusa MPI_Comm comm ); // Kommunikátor, melybe a küldı // és a fogadó processzek tartoznak
int MPI_Unpack ( void* inbuf, int insize, int* position, void* outbuf,
47
Az MPI_Pack_size függvénnyel határozhatjuk meg az átviteli buffer már feltöltött, byte-okban számolt méretét, pontosabban az átviteli bufferben a következı szabad hely címét. // Az átviteli bufferbe // csomagolandó tömb // elemszáma // Az átviteli bufferbe // csomagolandó // tömb adattípusa // Kommunikátor, melybe // a küldı és a fogadó // processzek tartoznak // A tömb becsomagolása után // a következı szabad cím
int MPI_Pack_size ( int incount,
MPI_Datatype datatype,
MPI_Comm comm,
int* size );
Tekintsünk egy példaprogramot becsomagolására, átvitelére és kicsomagolására!
különbözı
adattípusú
változók
almátrixának
elküldésre
18. melléklet: main5_2a.c Tekintsünk és fogadására!
egy
példaprogramot
egy
mátrix
19. melléklet: main5_2b.c
II.5.3. Új adattípus (struktúra) létrehozása Az MPI a csomagolt adatátvitelnél egy sokkal hatékonyabb átvitelt is biztosít a származtatott adattípusok formájában. Származtatott adattípusoknak az alapértelmezett MPI adattípusokból öszzeépített adattípusokat, struktúrákat nevezzük. Alapértelmezett adattípusok MPI adattípus MPI_CHAR MPI_SHORT MPI_INT MPI_LONG MPI_FLOAT MPI_DOUBLE MPI_LONG_DOUBLE
C megfelelıje signed char signed short int signed int signed long int float double long double
MPI adattípus MPI_UNSIGNED_CHAR MPI_UNSIGNED_SHORT MPI_UNSIGNED MPI_UNSIGNED_LONG MPI_BYTE MPI_PACKED
48
C megfelelıje unsigned char unsigned short int unsigned int unsigned long int -
A származtatott adattípusok használatának elınye a csomagolt adatátvitelhez képest, hogy nincs szükség plusz memóriaterületre, sem adatok másolására, ami processzoridı többlettel járna. Továbbá elıny, hogy lehet közvetlenül hozzáférni a létrehozott struktúra tagjaihoz, anélkül, hogy a be- illetve kicsomagolás procedúráján végigmennénk. A C nyelv struktúráihoz hasonlóan az MPI struktúrákat is csak egyszer kell definiálni, és onnantól kezdve az átvitelhez csak a kommunikációs függvényeket kell használni. Másrészrıl, csak akkor érdemes MPI struktúrát létrehozni, ha azt késıbb többször használni szándékozunk. A következıkben új adattípusok, struktúrák létrehozására szolgáló függvényekkel ismerkedünk meg. Az új struktúra létrehozása minden esetben két fı lépésbıl áll: A struktúra elkészítésébıl és a véglegesítésébıl.
II.5.3.1. Az új adattípus (struktúra) elıkészítése Szomszédos, azonos típusú adatok párokba, hármasokba, illetve kisebb csoportokba összefogására az MPI_Type_contiguous függvényt használjuk. Leginkább pontok koordinátáinak kezelésére alkalmas. int MPI_Type_contiguous ( int count, // Adategységek száma MPI_Datatype oldtype, // Adategységek típusa MPI_Datatype* newtype ); // Új adattípus Tekintsünk egy példaprogramot az MPI_Type_contiguous használatára! 20. melléklet: main5_3_1a.c Az MPI_Type_vector mátrixokból almátrixok kinyerésére szolgál. Paraméterként megadjuk, hogy a „count” darab „blocklength” hosszúságú „oldtype” típusú blokkok között „stride” darab „oldtype” típusú távolság legyen. int MPI_Type_vector ( int count, int blocklength,
int stride, MPI_Datatype oldtype, MPI_Datatype* newtype );
// Blokkok száma // Egy blokk hosszúsága // a késıbb megadott // adattípusban // A blokkok kezdıcímei közötti // egységek száma // Blokk egységének adattípusa // Új adattípus
Tekintsünk egy példaprogramot az MPI_Type_contiguous használatára! 21. melléklet: main5_3_1b.c
49
Még az MPI_Type_vector-nál is nagyobb szabadságot ad nekünk az új adattípusok létre hozásában az MPI_Type_indexed függvény, mert a blokkok hosszát és távolságát is blokkonként adhatjuk meg. Továbbá lehetıségünk van egy tömbrészletet egy üzeneten belül többször elküldeni, ugyanis minden blokk kezdıcímét a struktúra kezdıcímétıl mérve kell megadni. int MPI_Type_indexed ( int count, int* array_of_blocklengths, int* array_of_displacements,
MPI_Datatype oldtype, MPI_Datatype *newtype );
// Blokkok száma // Blokkok hosszai // Blokkok kezdıcímei // a struktúra // kezdıcíméhez // képest a felhasznált // adattípusban // Blokkok egységének // adattípusa // Új adattípus
Tekintsünk egy példaprogramot az MPI_Type_indexed használatára! 22. melléklet: main5_3_1c.c Az MPI_Type_struct – az MPI_Type_indexed különbözı adattípusokra való kiterjesztése – a legáltalánosabban használt függvény új adattípusok elıkészítésére. Paraméterként megadjuk, hogy „count” darab blokk tartozzon egy struktúrába, melyeknek hosszai az „array_of_blocklengths” tömbben, kezdıcímei az „array_of_displacements” tömbben, adattípusai pedig az „array_of_types” tömbben találhatóak. A blokkok kezdıcímeit a struktúra kezdıcíméhez képest kell megadni. Ezeket a kezdıcímeket tehát a struktúra tagjainak címeinek lekérdeésével, majd ezekbıl a struktúra kezdıcímének kivonásával kapjuk meg. int MPI_Type_struct ( int count, int* array_of_blocklengths, MPI_Aint* array_of_displacements,
MPI_Datatype* array_of_types, MPI_Datatype* newtype );
// Blokkok száma // Blokkok hosszai // Blokkok kezdıcímei // a struktúra // kezdıcíméhez // képest byte-ban // Blokkok adattípusa // Új adattípus
Tekintsünk egy példaprogramot az MPI_Type_struct használatára! 23. melléklet: main5_3_1d.c
50
A címek számítására az MPI_Address függvényt ajánlott használni, mely paraméterként visszaadja az adott változó címét. A & címoperátor használata egyszerőbbnek tőnik, de erre a célra kevésbé biztonságos. Ugyanis a „&variable” valójában egy pointer és nem egy cím. A C nyelv pedig nem követeli meg, hogy egy pointer értéke a mutatott változó abszolút címe legyen; ami általában azért teljesül. Mivel a pointerek értékének képzése nagyban függ az adott architektúrától, ezért ha biztonságosan mőködı kódra törekszünk, akkor használjuk az MPI_Address-t. int MPI_Address ( void* location, // Változó MPI_Aint* address ); // Változó címe
II.5.3.2. Az új adattípus (struktúra) véglegesítése Ahhoz, hogy használhassuk az újonnan létrehozott adattípusunkat, véglegesítenünk kell az MPI_Type_commit függvénnyel. Az adattípust csak elsı használata elıtt kell véglegesítenünk, és ezt követıen, mint az alapértelmezett adattípusokat használhatjuk. int MPI_Type_commit ( MPI_Datatype* datatype ); // Új adattípus Ha fel akarjuk szabadítani az adott származtatott adattípusunkat, akkor azt az MPI_Type_free függvénnyel tehetjük. Ha egy származtatott adattípust csak azért hoztunk létre, hogy egy másik származtatott adattípus létrehozásában felhasználjuk, akkor ezt követıen – az új adattípus sérülése nélkül – felszabadíthatjuk. Legkésıbb a programunk végén a származtatott adattípusokat érdemes felszabadítani. int MPI_Type_free ( MPI_Datatype* datatype );
// Felszabadítandó adattípus
Ellenırzı kérdések: 1.) Milyen jellegő feladatok kapcsán lehet szükség összetett, származtatott adattípusok használatára? 2.) Hogyan továbbítja az MPI az adattípusokat? Emiatt milyen hibát nem szabad elkövetni? Ugyanakkor milyen elınyei vannak ennek az eljárásnak? 3.) Hogyan történik az adatok csomagolt átvitele? Mikor érdemes ezt a módszert választani? 4.) Milyen két fı lépése van az új adattípus létrehozásának? Mikor érdemes ezt a módszert választani?
Feladatok: 1.) Próbáljuk ki a main5_2a.c példaprogramot! 2.) Próbáljuk ki a main5_2b.c példaprogramot! 3.) Próbáljuk ki a main5_3_1a.c példaprogramot! 4.) Próbáljuk ki a main5_3_1b.c példaprogramot! 5.) Próbáljuk ki a main5_3_1c.c példaprogramot! 6.) Próbáljuk ki a main5_3_1d.c példaprogramot! 7.) Írjunk egy programot, melyben egy struktúratömböt átküldünk az egyik processztıl a másiknak! Fogalmazzuk meg, hogy mi alapján döntöttünk a csomagolt átvitel vagy az új adattípus létrehozása és használata mellett!
51
II.6. Cartesian topológiák áttekintése Egy kép, vagy egy mátrix feldolgozásánál, ezeket érdemes részekre bontani, és párhuzamosan feldolgozni. Az adathalmazt – a származtatott adattípusok kapcsán megismert függvények alkalmazásával – többféleképpen darabolhatjuk kisebb részekre: akár sávokra, akár kisebb téglalapokra. Minden részt külön processzhez rendelünk, emiatt elınyös, ha a processzek azonosítói között valamilyen konvenciót tudunk kialakítani és követni, hogy átláthatóbbá és nem utolsó sorban tömörebbé, kifejezıbbé tegyük a kódunkat. Ezen konvenció virtuális topológiában nyilvánul meg, melynek egyik – MPI által támogatott fajtája – a cartesian topológia. A topológia processzek egymáshoz viszonyított kapcsolata, amit azonosítóik sorrendbe, rendszerbe foglalásával adunk meg. A processz azonosítók mindig kommunikátorban értelmezettek. Tehát, ha egy processz több kommunikátoba is tartozik, akkor minden kommunikátorban más és más az azonosítója, ami alapján hivatkozni lehet rá. Tehát egy új topológiát egy új kommunikátor létrehozásával készíthetünk.
II.6.1. Cartesian topológia létrehozása Az MPI_Cart_create függvény egy cartesian topológiát definiáló kommunikátor létrehozására szolgál. int MPI_Cart_create ( MPI_Comm old_comm, int ndims, int* dim_size, int* periods,
int reorder,
MPI_Comm* new_comm );
// Felhasználni kívánt // kommunikátor // Az új topológia // dimenzióinak száma // Az új topolgia // dimenzióinak méretei // Az új topológia az adott // dimenzióban periodikus (1), // vagy nem-periodikus (0) // A processzek azonosítójának // új kommunikátorbeli // átnevezésének/átrendezésének // engedélyezése (1), // vagy tiltása (0) // Új kommunikátor
Például, ha a processzeket egy négyzetháló rácspontjaihoz szeretnénk hozzárendelni, akkor kétdimenziós topológiát kell létrehozunk. A sorok és oszlopok számát a „dim_size” tömbben adjuk meg. Az így keletkezı processz-azonosítók kétdimenziós esetben egy számpárból fognak állni, amik koordinátaként is felfoghatók. A cartesian topológia esetében az, hogy a topológia valamelyik dimenziójának irányában periodikus, azt jelenti, hogy az adott dimenzió szerinti elsı és utolsó processz szomszédos egymással. Másként fogalmazva, ha egy cartesian topológia egy dimenziójának irányában periodikus, akkor bármely szám, melynek az adott dimenzió méretével vett modulója megegyezik egy processz azonosítójának megfelelı koordinátájával, akkor az az adott processzt jelöli ki. Ha egy papírra rajzolt négyzethálóval szeretnénk szemléltetni egy egydimenzió irányában periodikus, kétdimenziós topológiát, akkor a papírt az említett dimenzió irányában hengerré kéne hajtanunk. Ha pedig mindkét dimenzió irányában periodikus a kétdimenziós topológia, akkor a négyzethálós parírunk tórusszá alakul. A kétdimenziós topológia periodicitásának variációi a következıképpen befolyásolják a processzek azonosítóit (12. ábra). 52
12. ábra A processzek új azonosító koordinátái mögött, zárójelben az eredeti, szekvenciális azonosítójukat tüntettük fel. A „-1”-es azonosító azt jelenti, hogy az azonosítóhoz nem tartozik prcessz; amit másképp az MPI_PROC_NULL azonosítóval jelölünk. Valójában, mivel a kommunikációs függvények csak egyváltozós processzazonosítókat tudnak értelmezni, ezért a cartesian topológián belül is szekvenciálisak a processz-azonosítók, viszont mindegyikükhöz tartozik egy „ndims” tagú koordináta. A „reorder” paraméter értékétıl függıen a létrejövı cartesian topológián belül átnevezıdhetnek a szekvenciális processz-azonosítók az MPI_COMM_WORLD-beli szekvenciális processz-azonosítókhoz képest. Ennek engedésekor az MPI a cartesian topológiához legjobban illeszkedıen nevezi át az adott architektúrán futó processzeket. Így lehetıvé válik, hogy a processzorok közelségét is a hatékonyság „malmára hajtsuk”. Az MPI_Cart_create egy kollektív kommunikációs függvény, amit ebbıl következıen a felhasználandó kommunikátor összes processzének meg kell hívnia. Ha több pocessz áll rendelkezésre, mint amennyire a cartesien topológia létrehozásához szükség van, akkor a felesleges processzek MPI_PROC_NULL azonosítót kapnak. Processzhiány esetén pedig az MPI_Cart_create függvény hibakóddal tér vissza.
II.6.2. A szekvenciális és a koordináta processz-azonosítók közötti konverzió A cartesian topológia – a többkoordinátás azonosítók bevezetésével – lehetıséget teremt a processzek struktúrált kezelésére, viszont a kommunikációs függvények csak egyetlen változót tudnak processz-azonosítójént értelmezni. Emiatt szükség van a processzek cartesian topológiabeli koordináta azonosítói és a szekvenciális azonosítói közötti konverzióra. Erre az átalakításra szolgálnak az MPI_CART_COORDS és az MPI_CART_RANK függvények. Az MPI_Cart_coords függvénnyel – a szekvenciális processz-azonosító és a topológia legnagyobb dimenziószámának ismeretében – meghatározhatók a processz topológiabeli koordináta azonosítói.
53
int MPI_Cart_coords ( MPI_Comm comm, int rank, int maxdims, int* coords );
// A már létrehozott cartesian topológia // A processz szekvenciális azonosítója // A topológia dimenzióinak száma // A processz topológabeli koordinátái
Az MPI_Cart_rank függvénnyel pedig – a processz topológiabeli koordinátáinak ismeretében – a processz szekvenciális azonosítója határozható meg. // A már létrehozott cartesian topológia // A processz topológiabeli // koordinátái (dimenziónyi) // A processz szekvenciális azonosítója
int MPI_Cart_rank ( MPI_Comm comm, int* coords, int* rank );
Mind az MPI_CART_COORDS, mind az MPI_CART_RANK függvények lekérdezést valósítanak meg, tehát meghívásukkor az információ-szerzésen kívül nincs más hatásuk. Cartesian topológiával való dolgozás esetén az új kommunikátor létrehozását követıen érdemes lekérdezni az összes olyan processz azonosítóját, amellyel a használt modell alapján kommunikálni fog az adott processz; ezeket letárolva, nagyban gyorsítjuk a processz mőködését és a kódunk egyszerőségét.
II.6.3. Cartesian topológia résztopológiákra bontása Gyakran szeretnénk tovább csoportosítani a processzeinket, más szóval tovább bontani a topológiánkat kisebb dimenziójú részekre, hogy például a kollektív kommunikációs függvények elınyeit kihasználhassuk. Résztopológiát az MPI_Cart_sub függvénnyel jelölhetünk ki. // Szülı cartesian topológia // A szülı topológia azon // dimenziói, melyeket // hozzárendelünk (1) // a gyermek topológiához, // vagy kihagyunk (0) belıle MPI_Comm* new_comm ); // Gyermek cartesian topológia
int MPI_Cart_sub ( MPI_Comm old_comm, int* belongs,
Az MPI_Cart_sub használatakor tehát a már meglévı topológiába tartozó processzeket fogjuk össze egy-egy alcsoportba. Ha a „belongs” tömb megfelelı indexő helyére „1”-est írunk, akkor az általa kijelölt teljes dimenzió beletartozik majd a résztopológiába. Fontos látnunk, hogy résztopológiaként csak teljes dimenziók kijelölésére van lehetıség. Ez például kétdimenziós topológia esetén azt jelenti, csak teljes sorok, vagy teljes oszlopok alkothatnak résztopológiát. A „new_comm” paraméterben minden processz azt a kommunikátort kapja vissza, amelyikbe beletartozik. Így lehetséges az, hogy a külön résztopológiába tartozó processzeknek különbözı, de ugyanolyan nevő a kommunikátora. Az MPI_Cart_sub-ot mint kollektív függvényt, a szülı kommunikátor összes processzének meg kell hívnia. A gyermek topológiák öröklik a szülı topológia tulajdonságait, tehát ugyanolyan – csak kisebb dimenziószámú – cartesian topológiák maradnak. Dimenziószámukat, az egyes dimenziók méreteit és a periodicitásukat az MPI_Cartdim_get és az MPI_Cart_get függvényekkel kérdezhetjük le.
54
Az MPI_Cartdim_get függvénnyel az adott kommunikátorhoz tartozó résztopológia dimenzióinak számát kérdezhetjük le. Erre például akkor lehet szükség, ha a résztopológiát más függvényben hoztuk létre, mint ahol használni szeretnénk. int MPI_Cartdim_get ( MPI_Comm comm, int* ndims );
// A résztopológia kommunikátora // A résztopológia dimenzióinak // száma
A résztopológia dimenziószámának ismeretében, a résztopológiáról információkhoz az MPI_Cart_get függvény használatával juthatunk.
további
// A résztopológia kommunikátora // A résztopológia dimenzióinak // száma // A dimenziók méretei // A dimenziók periodicitása // A hívó processz résztopológiabeli // koordináta azonosítói
int MPI_Cart_get ( MPI_Comm comm, int maxdims, int* dims, int* periods, int* coords );
Az MPI_Cart_shift függvénnyel lehet kiaknázni mindazt az elınyt, amiért érdemes egyáltalán cartesian topológiát használni. Segítségével egyszerően kiszámíthatjuk egy processz cartesian topológiai szomszédainak szekvenciális azonosítóit. A processz-azonosítók kiszámítása a „láncolatszerő” üzenet-továbbítást támogadja a leginkább. Egyetlen dimenzió kiválasztásával és azon belül egy irány és egy lépték megadásával kérdezhetjük le az adott processz elıtti és utáni processzek azonosítóit. Egy „adatáttolást” elképzelve mindegyik processz egy – a sorban elıtte lévı – forrásprocesztıl kap, és egy – a sorban utána következı – célprocessznek ad adatokat. Ne felejtsük el, hogy az MPI_Cart_shift csupán lekérdezésre szolgál, és egyéb hatása nincs. int MPI_Cart_shift ( MPI_Comm comm, // Cartesian kommunikátor int direction, // Az „eltolás” tengelyébe esı dimenzió // sorszáma int displ, // Az „eltolás” mértéke és iránya int* source, // Forrásprocessz azonosítója int* dest ); // Célprocessz azonosítója Egy N dimenziós topológia esetén a dimenziók 0-tól (N-1)-ig sorszámozottak; és közülük csak egyet választhatunk ki az eltolás irányául. Ha a „displ” paraméter pozitív, akkor az adott processz – kiválasztott dimenzió irányába esı – két szomszédja közül a kisebb azonosítójú lesz a forrás-, a nagyobb azonosítójú pedig a célprocessz. Abban az esetben, mikor a „displ” paraméter negatív, az elıbbinek épp a fordítottja érvényes, vagyis hogy az adott processz nagyobbik azonosítójú szomszédja lesz a forrás-, és a kisebbik azonosítójú szomszédja pedig a célprocessz. A cartesian topológia periodicitása és az MPI_Cart_shift függvény mőködése nagyon jól összeegyeztetett, ugyanis ha periodikus az a dimenzió, amelynek irányában tolunk el, akkor a dimenzió szélén lévı processzeknek is két szomszédja van, ugyanúgy mint a dimenzió közepén lévıknek. Ha viszont nem-periodikus az eltolás irányába esı dimenzió, akkor a dimenzió szélén lévı processznek csak egy szomszédja van; és a másik oldali azonosító negatív, azaz érvénytelen értéket kap.
55
Tekintsünk egy példaprogramot cartesian topológia használatára! 24. melléklet: main6_3.c A példaprogram egy mátrixot oszt szét a kétdimenziós cartesian topológiába rendezett processzek között.
Ellenırzı kérdések: 1.) Milyen elınyei vannak a cartesian topológiák használatának? 2.) Hogyan viszonyul egymáshoz a topológia, a kommunikátor és a processz-azonosító? 3.) Mit jelent az, hogy egy kétdimenziós cartesian topológia egy, illetve két dimenzió irányában periodikus? 4.) Milyen következménye van annak, hogy az MPI_Cart_create és az MPI_Cart_sub függvények kollektív kommunikációs függvények? 5.) Miért van szükség az MPI_Cart_coords és az MPI_Cart_rank függvényekre? 6.) Milyen – dimenziókra vonatkozó – megkötésekkel lehet a már meglévı cartesian topológiából résztopológiákat származtatni? 7.) Mire szolgál az MPI_Cart_shift függvény?
Feladatok: 1.) Próbáljuk ki a main6_3.c példaprogramot! 2.) Terjesszük ki a main6_3.c példaprogramot úgy, hogy tetszıleges mérető mátrixot tudjon szétosztani a kilenc processzek között!
56
II.7. Az üzenetküldéses kommunikációt árnyaló lehetıségek II.7.1. Felhasználó által definiált „redukáló” mőveletek Az alapértelemzett „redukáló” mőveleteken kívül az MPI_Reduce a felhasználó által definiált mőveletekkel is meghívható. Így létre hozhatunk, és hatékonyan alkalmazhatunk olyan mőveleteket is, amelyek a megoldandó feladatunkhoz a legjobban illeszkednek. Értelemszerően, azok a redukáló mőveletek, melyeket az MPI_Reduce-szal való használat céljából hozunk létre, alkalmazhatóak a többi redukáló összetett kollektív kommunikációs függvénnyel is.
II.7.1.1. Az új „redukáló” mővelet megírása függvényként Az alapértelmezett „redukáló” mőveletekhez hasonlóan olyan új mőveleteket hozhatunk csak létre, amelyek az egyes processzek buffereinek összetartozó, azonos indexő elemein hajtódnak végre. Az új mőveletet egy kötött paraméterlistájú függvényként kell megadnunk: // Bemenı buffer // Be- és kimenı // buffer int* len, // A bufferek hossza MPI_Datatype* datatype ); // A bufferek // egységének // adattípusa
typedef void MPI_User_function ( void* invec, void* inoutvec,
A függvény írásakor a mőveletet úgy képzeljük el, mintha csak két processz lenne, melyek buffereiben lévı adatokat kombinálnánk. Tehát az operandusok a két bemenı bufferben, az „invec”-ben és az „inoutvec”-ben vannak. A mővelet eredménye – a függvény visszatérésekor – az „inoutvec” bufferben kerül letárolásra. A „len” változó tartalmazza az egyes bufferek hosszát. A „datatype” tartalmazza azt az adattípust, amivel az MPI_Reduce-t meghívták. Például, ha az egyes processzek buffereiben lévı, azonos indexő adatok négyzeteinek összegét szeretnénk egy redukáló mővelettel kiszámítani, akkor a következıképpen fog kinézni az ezt megvalósító függvényünk: void negyzet_osszeg(void *in, void *inout, int *len, MPI_Datatype *datatype) { double op1 = *(double*)in; double op2 = *(double*)inout; *(double*)inout = sqrt(op1 * op1 + op2 * op2); } A példa során azt feltételeztük, hogy double típusú adatokon fogjuk a redukáló mőveletet végrehajtani. Akár általunk definiált adattípust is használhatunk a függvényben, viszont a hívó és a használt adattípusok egyezésére ügyelnünk kell. Továbbá érdemes szem elıtt tartani, hogy a nem-folytonos adattípusok használata teljesítmény csökkenéshez vezethet. A redukáló függvényünket két processzt és buffereiket feltételezve írtuk meg. Valójában az MPI_Reduce-nál megismert üzenetátvitel valósul meg; tehát az MPI_Reduce kiterjeszti a mőveletünket az összes processzt bevonva, és az eredményt a hívásában megjelölt 57
processzre letárolva. Az MPI_Reduce a mőveletet úgy terjeszti ki az összes processzre, hogy a mőveleteket bináris fa struktúrában alkalmazza. A proceszek küldıbufferében lévı adatokból, mint levélelelmekbıl egy olyan fát szervez, melynek csomópontjaiban az adott mővelet eredménye van. Például az elıbb bemutatott négyzetösszeget kiszámoló függvény mőveletét, nyolc processz esetén alkalmazva, a 13. ábrán bemutatott módon valósítja meg az MPI_Reduce.
13. ábra Ahhoz, hogy minden adat csak egyszer legyen négyzetre emelve, két levélelem négyzetre emelése és összeadása után az eredményükbıl gyököt kell vonnunk, elıkészítve következı mőveletet. Továbbá a fogadó processzen egy korrigáló négyzetre emelésre van még szükség. Tehát a nyilak irányában történik a mőveletvégzés, illetve a legvégén a célprocesszre másolás. Kommunikációs függvények értelemszerően nem hívhatók meg a redukáló mővelet függvényén belül.
II.7.1.2. A megírt függvény „regisztrálása” Az elkészült függvénybıl az MPI_Op_create függvénnyel készíthetünk redukáló mőveletet. int MPI_Op_create ( MPI_User_function* function, int commute,
MPI_Op* op );
// Az új redukáló mővelet // függvénye // Ha a mővelet kommutatív, // akkor 1; // ha nem-kommutatív, // akkor 0 // Az új mővelet neve
Az MPI-ban minden redukáló mőveletnek asszociatívnak, azaz tetszılegesen csoportosíthatónak kell lennie a végeredmény megváltozása nélkül, annak érdekében, hogy – például a fent bemutatott módon – hatékonyabb legyen a mővelet végrehajtása. Tehát az asszociativitás terén nincs kompromisszum. A „commute” paraméter értékével megadhatjuk,
58
hogy az új mővelet kommutatív, legyen vagy sem. Ha kommutatív, azaz felcserélhetı, akkor a végeredmény független attól, hogy milyen sorrendben hajtódnak végre a mőveletek. Az elsı paraméter helyére értelemszerően a használni kívánt függvényt írjuk, az utolsó paraméter helyére pedig azt a nevet, amivel az MPI_Reduce-ban a létrehozott mőveletünkre szeretnénk hivatkozni.
II.7.1.3. A kész „redukáló” mővelet használata Tekintsünk egy példaprogramot egy új redukáló mővelet használatára! 25. melléklet: main7_1_3a.c Mivel egyes implementációkban (történelmi okoból) a matematikai könyvtár nem linkelıdik automatikusan a programhoz, ezért erre az -lm kapcsolóval kérhetjük a forditót. Tehát a példaprogramot az mpicc -o main7_1_3a main7_1_3a.c –lm paranccsal fordíthatjuk le. Tekintsünk egy példaprogramot egy származtatott adattípuson végrehajtott redukáló mőveletre! 26. melléklet: main7_1_3b.c
59
II.7.2. Üzenetpróbálás A több változattal rendelkezı MPI_Send és a hozzá tartozó MPI_Recv függvények az üzenetküldéses kommunikáció központjai. Használatukkal lehetıvé válik, hogy az egyik processz bufferébıl a másik processz bufferébe másolódjanak adatok. Amint megismertük, a küldı függvény különbözı módjaival, valamint a küldı / fogadó függvény blokkoló illetve nem-blokkoló változataival, tetszılegesen specifikálhatjuk a pont-pont kommunikációt. Az üzenetpróbálással – ahogy a neve is sejteti – egy processz anélkül tud a bejövı üzenetrıl információt szerezni, hogy fogadnia kellene azt. Számos oka lehet az üzenetpróbálás alkalmazásának. Például hasznos lehet tudni, hogy egy üzenet megérkezett-e már, vagy sem; hogy ennek függvényében folytathassa a processz a munkáját. Az üzenet paraméterei – borítéka – használhatók arra, hogy a processz eldöntse, hogy szüksége van-e az érkezı üzenetre. Például elképzelhetı, hogy csupán egy „üres” jelzı üzenet érkezett, egy esemény befejezıdésérıl, ami a fogadó processz számára nem hordoz releváns információt. Ekkor választhatja a processz, hogy nem fogadja az üzenetet, hanem egyszerően megszünteti az üzenetfogadást. Egy másik érv az üzenetpróbálás mellett, hogy amikor ismeretlen mérető üzenetet várunk, akkor ahhoz, hogy a memóriával is takarékoskodhassunk, már az üzenetfogadás elıtt pontosan ismernünk kell, hogy mekkora fogadóbuffert kell dinamikusan lefoglalnunk. Üzenetpróbálással a célprocessz hozzáférhet a forrásprocessz azonosítójához, az üzenet címkéjéhez és a fogadott adatok számához; viszont a fogadandó adattípust ismernie kell. Ezeknek a paramétereknek a lekérdezésére – eddigi ismereteink szerint – csak az üzenetfogadás befejezésekor volt lehetıségünk, amikor az MPI_Recv által visszaadott MPI_Status típusú „status” struktúrából nyertük ki ezeket az információkat.
II.7.2.1. Az üzenetpróbáló függvény felépítése Az MPI_Probe függvénnyel ugyanahhoz az MPI_Status típusú „status” struktúrához férhetünk hozzá, mint amit az MPI_Recv az üzenetfogadás befejezésekor visszaad. Így alkalmazásával hozzáférhetünk a forrásprocessz azonosítójához, az üzenet címkéjéhez és közvetett módon – a már megismert MPI_Get_count függvénnyel – a küldött adategységek pontos számához. int MPI_Probe ( int source, int tag, MPI_Comm comm, MPI_Status* status );
// Forrásprocessz azonosítója // Üzenetcímke // Kommunikátor, melybe a küldı és // a fogadó processz is beletartozik // Információ a fogadott üzenetrıl
A forrásprocessz azonosítója, az üzenetcímke és a kommunikátor bemenı paraméterek, ugyanis az MPI_Probe ezek közül az elsı kettıhöz keres egyezést a függı üzenetek borítékai között; a kommunikátor szerepe pedig alapvetı, hiszen az azonosítók is csak kommunikátoron belül értelmezettek. Ha az MPI_Probe egyezést talál, akkor a „status” struktúrában a keresett üzenetrıl minden információt a fogadó processz rendelkezésére bocsát. A „status” struktúrának és a fogadandó adatok típusának ismeretében az MPI_Get_count függvénnyel meghatározhatjuk a ténylegesen fogadott adategységek számát. Az MPI_Get_count függvény részletes bemutatása a 3.2.2. fejezetben található. Ha több processztıl szeretnénk többféle üzenetcímkével üzenetet fogadni, akkor használhatjuk az MPI_ANY_SOURCE, illetve MPI_ANY_TAG „joker” processz-azonosítót,
60
illetve üzenetcímkét; kiszélesítve ezzel azoknak a függı üzeneteknek a számát, amelyek üzenetpróbáláskor illeszkedhetnek a fogadó borítékhoz. Az MPI_Probe blokkoló függvény, tehát az ezt meghívó processznek mindaddig várnia kell, amíg ez vissza nem tér. A várakozási idı kiküszöbölésére az MPI_Probe-nak – mint sok eddig megismert függvénynek – létezik nem-blokkoló változata is. Az MPI_Iprobe teljesen egyenértékő az MPI_Probe-bal, csupán abban különbözik, hogy miután megvizsgálta, hogy talált-e a fogadó borítékhoz illeszkedı függı üzenetet, az eredménytıl függetlenül visszatér. Az egyezést egy „flag” beállításával jelzi. A flag igaz vagy hamis értékét logikai értelemben vesszük, tehát igaz > 0, hamis = 0. int MPI_Iprobe ( int source, int tag, MPI_Comm comm, int* flag, MPI_Status* status );
// Forrásprocessz azonosítója // Üzenetcímke // Kommunikátor, melybe a küldı és // a fogadó processz is beletartozik // Egy függı üzenet fogadó borítékkal // való egyezését jelzı „zászló” // Információ a fogadott üzenetrıl
Tehát az MPI_Probe és az MPI_Iprobe között ugyanaz a különbség, mint az MPI_Wait és az MPI_Test között. A függvénypárok között csupán az a különbség, hogy míg az elıbbiek az MPI_Recv elıtt használatosak, addig az utóbbiak az után.
II.7.2.2. Az üzenetpróbáló függvény használata Ahogy korábban már utaltunk rá, az üzenetpróbálásnak az egyik elınyös következménye az, hogy abban az esetben, ha nem tudjuk a várt üzenet pontos méretét, nem kell egy bizonyosan elegendıen nagy buffert lefoglalnunk az eredményes üzenetfogadás érdekében; hanem takarékoskodhatunk a memóriával azáltal, hogy pontosan akkora buffer foglalunk le, amekkorára ténylegesen szükség van. Tekintsünk egy példaprogramot a fogadóbuffer küldött adategységek számához illeszkedı lefoglalására! 27. melléklet: main7_2_2a.c Felmerülhet a kérdés, hogy ha különbözı adattípusú üzeneteket várunk egyidejőleg, akkor miként tegyük ezt. Az MPI_Probe függvénnyel nem tudjuk lekérdezni a küldött adatok típusát, de ha valamilyen konvenciót követünk, akkor a processz-azonosító vagy az üzenetcímke értékébıl következtethetünk rá, és a megfelelı módon paraméterezett fogadó függvénnyel várhatjuk. Tekintsünk egy példaprogramot a különbözı adattípusú üzenetek fogadására! 28. melléklet: main7_2_2b.c
61
II.7.2.3. Szignál üzenetek kezelése Processzek komunikációja során – a hatékonyságot szem elıtt tartva – lehetıség van arra, hogy a processzek csak jelezzenek egymásnak. Ekkor egy nullamérető tömböt küldünk át, melynek üzenetcímkéje hordozza a releváns információt. Ezt a fogadó oldalon üzenetpróbálással egyszerően lekérdezzük; majd illı, hogy a kezdeményezett, de be nem fejezett üzenetátvitelt megszüntessük. Ezeknek az ilymódon „félbe” maradt kommunikációknak, függı üzeneteknek a megszüntetése azért fontos, mert a küldı, illetve fogadó függvényeket nem engedve visszatérni, akár holtpontra is juttathatják az adott processz. A tényleges, de már szükségtelen üzenetek felszámolása – az elıbb említett okon kívül – azért is fontos, mert mind a processzeken, mind az MPI belsı memóriaterületén feleslegesen foglalják a helyet. Csak nem-blokkoló pont-pont kommunikációs függvények üzenetátvitelét lehet felszámolni fogadás nélkül, ugyanis ezek rendelkeznek MPI_Request típusú „request” paraméterrel. Tehát ha kilátás van arra, hogy az üzenetet a fogadó fél nem fogja fogadni, akkor nem-blokkoló függvénnyel küldjük az üzenetet / szignált. Az MPI_Cancel szolgál a függı üzenet érvénytelenítésére. Minden processz csak maga érvénytelenítheti a már biztosan be nem fejezıdı küldı vagy fogadó függvényhívásait. // Lekérdezési paraméter
int MPI_Cancel ( MPI_Request* request );
A már ismerıs lekérdezési paraméterrel hivatkozhatunk a kezdeményezett küldésre, illetve fogadásra. Az MPI_Cancel meghívását követıen azonnal visszatér; lehet hamarabb is, mint ahogy a kezdeményezett kommunikáció ténylegesen megszünik. Az MPI_Cancel használatát követıen továbbra is be kell fejezni a megkezdett kommunikációt, ami az MPI_Wait vagy az MPI_Test függvényekkel lehetséges. Tehát az MPI_Cancel a „request” paraméternek olyan értéket ad, hogy az MPI_Wait vagy az MPI_Test függvény a késleltetett kommunikáció teljesülését detektálja, és így az tényleg felszámolódjon. Amikor a kommunikáció már végleg megszőnik, akkor ennek megfelelıen a „status” paraméter is frissül. A „status”-t az MPI_Test_cancelled függvénnyel vizsgálhatjuk meg. A „flag” igaz értéke jelzi az üzenet megszüntét, ami azt is jelenti, hogy a „status” struktúra tagjai definiálatlan értéket kaptak. A flag igaz vagy hamis értékét logikai értelemben vesszük, tehát igaz > 0, hamis = 0. int MPI_Test_cancelled ( MPI_Status* status, int* flag );
// Információ az üzenetrıl // Az üzenet megszőnését jelzı // „zászló”
Tehát mielıtt egy olyan üzenet „status” információit használnánk föl, amely lehet, hogy addigra már megszünt, akkor elıbb ellenırizzük az állapotát az MPI_Test_cancelled függvénnyel. Képzeljük el, hogy „A” processz várakozik „B” processz egy üzenetére; miközben úgy alakul, hogy „B” processz mégsem tudja elküldeni az „A” processz által várt üzenetet. Ekkor „B” processz – praktikusan – egy szignál küldésével jelzi „A” processznek, hogy haladjon tovább, nem akadjon meg az üzenetre való várakozás miatt. Tekintsünk egy példaprogramot a fenti szintuáció üzenetpróbálással történı megoldására! 29. melléklet: main7_2_3.c
62
Ellenırzı kérdések: 1.) Milyen modellt követve írjuk meg a redukáló mőveletet megvlósító függvényt? Hogyan terjeszti ki az MPI_Reduce ezt a függvényt az összes processzre? 2.) Milyen kritériumoknak kell megfelelnie a redukáló mőveletet megvalósító függvénynek? 3.) Milyen esetekben elınyös üzenetpróbálást alkalmazni? Említsünk legalább három területet! 4.) Milyen információkhoz férhetünk hozzá az üzenetpróbálás alkalmazásával, és mi az amit már eleve ismernünk kell? 5.) Hogyan mőködik az MPI_Probe függvény? Miben tér el tıle az MPI_Iprobe? 6.) Mik a szignál üzenetek, és mire használhatóak? 7.) Milyen típusú kommunikációs függvények üzenetátvitelét lehet megszüntetni? Mik a kommunikáció teljes felszámolásának a lépései?
Feladatok: 1.) Próbáljuk ki a main7_1_3a.c példaprogramot! 2.) Próbáljuk ki a main7_1_3b.c példaprogramot! 3.) Próbáljuk ki a main7_2_2a.c példaprogramot! 4.) Próbáljuk ki a main7_2_2b.c példaprogramot! 5.) Próbáljuk ki a main7_2_3.c példaprogramot! 6.) Győjtsünk ötleteket, hogy milyen redukáló mőveleteket lenne érdemes megvalósítani! 7.) Győjtsünk ötleteket, hogy milyen feladatoknál lehet szükség üzenetpróbálásra!
63
II.8. Intra- és inter-kommunikátorok összehasonlítása A processzeket kommunikátorok csoportosítják, ugyanis a processzeknek csak kommunikátoron belül létezik azonosítója. Ha egy processz több kommunikátorba is beletartozik, akkor kommunikátoronként rendelkezik egy-egy külön azonosítóval. A kommunikátor elnevezés onnan származik, hogy csak az egy kommunikátorba tartozó processzek kommunikálhatnak egymással. Az MPI automatikusan biztosít egy alap kommunikátort – az MPI_COMM_WORLD-öt, melybe az összes processz beletartozik. Így az MPI_COMM_WORLD-öt használva az összes processz kommunikálhat egymással. További kommunikátorok definiálásával tovább csoportosíthatjuk a processzeket. Sok esetben elınyös lehet az MPI_COMM_WORLD-nek mint globális kommunikátornak a használata, azonban bizonyos esetekben – például, hogy processzek kisebb csoportján alkalmazhassuk a kollektív kommunikációs függvényeket – érdemes kisebb processz számú kommunikátorra szorítkozni. Kétféle kommunikátort hozhatunk létre: intra-kommunikátort vagy inter-kommunikátort; a kettı viszont kizárja egymást. Egy intra-kommunikátor processzek egyetlen csoportját tartalmazza, amelyen belül minden procesznek egyedi azonosítója van. A 14. ábrán két intra-kommunikátort látunk: az MPI_COMM_WORLD-öt és az MPI_COMM_NEW-t. A mindkét intra-kommunikátorba beletartozó processzek kommunikátoronként külön azonosítóval rendelkeznek.
14. ábra Az ábra alapján már jobban érthetı, hogy miért fontos a kommunikációs függvények használatakor a processz-azonosítók megadása mellett a kommunikátort is pontosan megjelölni. Egy inter-kommunikátor – az intra-kommunikátorokkal ellentétben – két külön processzcsoport között teremt kapcsolatot; tehát két különálló intra-kommunikátor között teszi lehetıvé a kommunikációt. Tehát például az – MPI_COMM_WORLD szerinti – 1. processz és 2. processz között kétféleképpen valósítható meg üzenetátvitel: Vagy az MPI_COMM_WORLD mint intrakommunikátor használatával; vagy pedig az MPI_COMM_WORLD és az MPI_COMM_NEW intra-kommunikátorok között egy inter-kommunikátor létrehozásával. Míg az MPI elsı verziójában inter-kommunikátoron keresztül csak pont-pont kommunikáció volt megvalósítható, addig az MPI második verziójában már a kollektív kommunikációs függvényeket is alkalmazhatjuk a két különálló processzcsoport között.
64
II.8.1. Intra-kommunikátorok Az MPI eszköztára többféleképpen ad lehetıséget kommunikátor létrehozására. Az MPI elsı verziójában egy meglévı intra-kommunikátort széthasíthatunk két vagy több alkommunikátorra, lemásolhatjuk, módosíthatjuk, vagy processzeinek újrarendezésével hozhatjuk létre az új kommunikátort. Az MPI második verziójában már össze is kapcsolhatunk intrakommunikátorokat, vagy akár teljesen újakat is indíthatunk.
II.8.1.1. Intra-kommunikátorok létrehozása széthasítással Az MPI_Comm_split intrakommunikátort.
függvénnyel
MPI_Comm_split ( MPI_Comm comm, int color, int key, MPI_Comm* newcomm );
hasíthatunk
szét
egy
már
meglévı
// Szülı intra-kommunikátor // Az alcsoportot kijelölı változó // Az alcsoporton belüli sorrendet // meghatározó változó // Gyermek intra-kommunikátor
A „color” és a „key” paraméterek alapján hasítódik szét a „comm” szülı komunikátor új komunikátorokra, alcsoportokra. Minden processz az alcsoportjának megfelelı kommunikátort kapja vissza a „newcomm” paraméterben. Bár az MPI_Comm_split kollektív függvény, amit minden szülı kommunikátorbeli processznek meg kell hívnia; mégis minden processz egyedien paraméterezheti fel ezt a függvényt. Ahányféle „color” paraméterrel hívják meg a szülı kommunikátor processzei az MPI_Comm_split-et, annyi „színő” új kommunikártor jön létre. Tehát az azonos színő processzek tartoznak egy alcsoportba. Az alcsoporton belüli processz sorrend a „key” paraméter alapján alakul ki. Ha két ugyanolyan színő processz ugyanazzal a „key” értékkel hívja meg az MPI_Comm_split-et, akkor az új kommunikátorbeli processz-azonosítójukat a szülı kommunikátorbeli azonosítójuk relatív sorrendje szerint kapják. A „color” és „key” paramétereknek nem-negatív egész számoknak kell lenniük. Ha egy processz egyik színő alcsoportba sem tartozik – más szóval nem hívja meg az MPI_Comm_split függvényt –, akkor MPI_UNDEFINED színővé válik; a gyermek kommunikátora pedig MPI_COMM_NULL értékővé. Minden MPI függvény, amit egy ilyen definiálatlan kommunikátorral hívunk meg, az hibával tér vissza. Tegyük fel, hogy a processzek a következı „color” és „key” paraméterekkel hívják meg az MPI_Comm_split-et:
65
Akkor az új intra-kommunikátorukban a processzek a 15. ábrán látható azonosítókat kapják:
15. ábra Tekintsünk egy példaprogramot, melyben az MPI_Comm_split-tel a fenti intrakommunikátorokat hozzuk létre! 30. melléklet: main8_1_1.c
II.8.1.2. Intra-kommunikátorok létrehozása lemásolással Egy új intra-kommunikátor létrehozásakor, elsı lépésként sokszor kényelmes pusztán lemásolni a szülı kommunikátort, amit az MPI_Comm_dup függvénnyel tehetünk. MPI_Comm_dup ( MPI_Comm comm, MPI_Comm* newcomm );
// Szülı intra-kommunikátor // Gyermek intra-kommunikátor
Az új intra-kommunikátor a szülı kommunikátor összes tulajdonságát – mint például az alcsoportok szerkezetét és a topológiát – átveszi. Ugyanakkor mégis egy új tartományú intra-kommunikátor jön létre.
II.8.1.3. Intra-kommunikátorok létrehozása módosítással Egy másik módja egy új intra-kommunikátor létrehozásának az, hogy kiválasztunk egy már meglévı intra-kommunikátort, módosítjuk annak összetételét, majd létrehozunk ez alapján egy új intra-kommunikátort. Tehát a szülı intra-kommunikátorból kinyerjük a processzek csoportját, a csoportot tetszésünk szerint módosítjuk, majd a processzek új csoportjához hozzárendelünk egy új intra-kommunikátort. A folyamatot a 16. ábrán követhetjük végig:
16. ábra A processzek csoportjának a szülı intra-kommunikátorból való kinyerésére az MPI_Comm_group függvény szolgál. int MPI_Comm_group ( MPI_Comm comm, MPI_Group* group );
66
// Szülı intra-kommunikátor // A kinyert processzek csoportja
A kinyert processz csoport módosítása a következı függvényekkel lehetséges: Kiválasztás és újrarendezés Az MPI_Group_incl függvénnyel a processzek csoportjából a felhasználni kívántakat emelhetjük ki egy újabb csoportba azosítóikat az új csoportbeli sorrendjükben a „n” hosszúságú „ranks” tömbbe írva. // A kinyert processzek csoportja // A „ranks” tömb hossza // A kiválasztott processzek // azonosítóit tartalmazó tömb MPI_Group* group_out ); // A processzek módoított csoportja
int MPI_Group_incl ( MPI_Group group, int n, int* ranks,
Tehát az MPI_Group_incl függvénnyel szőkíthetjük a processzek csoportját és átrendezhetjük a sorrendjüket. Az új csoportban az lesz az „i”-edik azonosítójú processz, amelyik a felhasznált csoportbeli azonosítóját a „ranks” tömb „i”-edik helyére írjuk. A „ranks” tömbbe csak létezı azonosítókat írhatunk, és mindegyiket kizárólag egyszer szerepeltethetjük, különben a program hibával tér vissza. Továbbá az „n” paraméter nem lehet nulla. Kihagyás Az MPI_Group_excl függvénnyel a processzek csoportjából a kihagyni kívántakat választhatjuk ki a „ranks” tömbbe írva. A csoportban maradó processzek azonosítóinak változatlan marad a relatív sorrendje. A „n” paraméter itt is ugyanúgy a „ranks” paraméter hosszát jelenti, viszont értékére csak az a kritérium vonatkozik, hogy ne legyen negatív. Az „n” nulla értéke esetén a felhasznált és a módosított csoport megegyezik egymással. További kritérium – az elızı csoportmódosító mőveletre vonatkozóakhoz hasonlóan –, hogy itt is csak létezı azonosítókat írhatunk a „ranks” tömbbe, és mindegyiket csak egyszer szerepeltethetjük. // A kinyert processzek csoportja // A „ranks” tömb hossza // A kihagyni kívánt processzek // azonosítóit tartalmazó tömb MPI_Group* newgroup );// A processzek módoított csoportja
int MPI_Group_excl ( MPI_Group group, int n, int* ranks,
Únió Az MPI_Group_union függvénnnyel két processz csoport únióját képezhetjük ismétlések nélkül. Tehát az új processz csoport minkét felhasznált csoport összes processzét tartalmazni fogja, viszont mindegyiket csak egyszer. int MPI_Group_union ( MPI_Group group1, MPI_Group group2, MPI_Group* group_out );
// Egyik kinyert csoport // Másik kinyert csoport // A két csoport úniója
Az MPI_Group_union-nal létrehozott új csoportban a processzek azonosítója úgy alakul, hogy elıször az elsı csoport elemei jönnek sorra – ahogy az eredeti csoportban voltak –, majd a második csoport elemei következnek szintén eredeti sorrendben. Természetesen a második csoport azon processz-azonosítói, amik már szerepeltek az elsıben, kimaradnak.
67
Metszet Az MPI_Group_intersection függvénnyel két csoport metszetét képezhetjük. Az új csoportban a processzek az elsı csoportbani relatív sorrendjükben kapnak új azonosítókat. int MPI_Group_intersection ( MPI_Group group1, MPI_Group group2, MPI_Group* group_out );
// Egyik kinyert // csoport // Másik kinyert // csoport // A két csoport // metszete
Különbség Az MPI_Group_difference függvénnyel két csoport különbségét képezhetjük. Tehát az új csoportba azok a processzek tartoznak bele, amelyek az elsı csoportba igen, de a másodikba nem tartoznak bele. MPI_Group_difference ( MPI_Group group1, MPI_Group group2, MPI_Group* newgroup );
// Egyik kinyert csoport // Másik kinyert csoport // A két csoport különbsége
A processzek elsı csoportbeli azonosítóik relatív sorrendjében kerülnek az új csoportba. Információk lekérdezése a csoportokról A csoportokról lekérdezı függvények segítségével juthatunk információkhoz, mint például a csoport mérete, a benne lévı processzek azonosítói, az processzek különbözı csoportbeli azonosítói közötti megfeleltetés vagy két csoport egyenlısége. Egy csoport méretét az MPI_Group_size függvénnyel kérdezhetjük le. // Csoport // Csoport mérete
int MPI_Group_size ( MPI_Group group, int* size );
Egy processz saját azonosítóját a csoportban az MPI_Group_rank függvénnyel kérdezheti le. Ha egy processz olyan csoportban kérdezi le az azonosítóját, amelynek nem tagja, akkor MPI_UNDEFINED azonosítót kap. int MPI_Group_rank ( MPI_Group group, int* rank );
// Csoport // A hívó processz azonosítója // a csoportban
Az MPI_Group_translate_ranks függvény processz-azonosítók csoportok közötti transzformálására szolgál. Például, ha ismerjük egy csoporton belül a processzek azonosítóját, és kíváncsiak vagyunk, hogy ugyanezeknek a processzeknek egy másik csoportban mi az azonosítója, akkor ezt a függvényt használjuk.
68
int MPI_Group_translate_ranks ( MPI_Group group1, // Csoport, melyben ismerjük // a processzek azonosítóit int n, // Az azonosítókat tartalmazó // tömb hossza int* ranks1, // Az ismert csoport // azonosítóit tartalmazó tömb MPI_Group group2, // Csoport, melyben // nem ismerjük a processzek // azonosítóit int* ranks2 ); // Az ismert csoport // azonosítóinak megfelelıi // az ismeretlen csoportban A tömbök hosszát jelölı „n” paraméternek és a processzek azonosítóinak természetesen nem-negatív számoknak kell lenniük. Ha a „ranks1” tömbben olyan azonosítót szerepeltetünk, mely nem szerepel az ismert csoportban, akkor a „ranks2” tömbben az azonos indexő helyen MPI_UNDEFINED azonosító lesz. Az MPI_Group_compare függvénnyel hasonlíthatunk össze két csoportot. Ha a két csoportban a processzek száma és a sorrendje is megegyezik, akkor az eredmény MPI_IDENT; ha a két csoportban ugyanazok a processzek szerepelnek, csak más sorrendben, akkor az eredmény MPI_SIMILAR; minden más esetben a csoportok különbözıek, tehát az eredmény MPI_UNEQUAL. int MPI_Group_compare ( MPI_Group group1, // Elsı csoport MPI_Group group2, // Második csoport int* result ); // Az összehasonlítás eredménye Csoportok megsemmisítése Új csoport kialakítása közben elıfordulhat, hogy köztes csoportokat is létre hozunk, amikre késıbb már nincs szükség. Ezeket a csoportokat az MPI_Group_free függvénnyel szabadíthatjuk fel. int MPI_Group_free ( MPI_Group* group);
// A felszabadítandó csoport
A csoport felszabadításával nem szabadítódik fel automatikusan az ahhoz tartozó kommunikátor, tehát szükség esetén azt külön kell megtennünk.
Új intra-kommunikátor rendelése a csoporthoz Az MPI_Comm_create függvénnyel hozhatunk létre új csoportot. A szülı intrakommunikátornak tartalmaznia kell az új intra-kommunikátort, valamint a szülı intrakommunikátor összes processzének meg kell hívnia az MPI_Comm_create-et, mint kollektív függvényt. Azok a szülı intra-kommunikátorbeli processzek, melyek nem tartoznak bele a módosított csoportba, azok az új intra-kommunikátora MPI_COMM_NULL lesz, azonosítójuk pedig MPI_UNDEFINED. Természetesen a processzeknek ugyanúgy felparaméterezve kell meghívniuk a függvényt.
69
int MPI_Comm_create ( MPI_Comm comm, MPI_Group group, MPI_Comm* comm_out );
// Szülı intra-kommunikátor // A módosított processz // csoport // Új intra-kommunikátor
Például a master-slave modellő programokban gyakran lehet szükség csak a dolgozó processzeket tartalmazó kommunikátor létrehozására. Tekintsünk egy példaprogramot a leggyakrabban szükséges intra-kommunikátor létrehozására! 31. melléklet: main8_1_3.c Ha egy kommunikátor már betöltötte a célját, ha már elvégeztük azt a feladatot, amihez a kommunikátorra szükség volt, akkor az MPI_Comm_free függvénnyel szabadíthatjuk fel a kommunikátort. Ahogy már említettük, a csoport és a kommunikátor felszabadítása két külön dolog, ezért két külön függvény szolgál e feladatokra. int MPI_Comm_free ( MPI_Comm* commp );
// A megsemmisítendı // kommunikátor
Az MPI_Comm_free kollektív függvény, ezért az összes processzének meg kell hívnia, ha az intra-kommunikátor megsemmisítése mellett döntünk.
II.8.2. Inter-kommunikátorok Egy inter-kommunikátor két különálló processz csoportot tartalmaz, és ezen intrakommunikátorok közötti kommunikációra szolgál. A processz csoportok különállósága azt jelenti, hogy a csoportok diszjunktak, nincs közös elemük; tehát nincs olyan processz, amely minkét csoportba, kommunikátorba beletartozna. Ebben a fajta kommunikációs struktúrában különbséget teszünk helyi és távoli kommunikátor között. Például „A” és „B” különálló processz csoportok esetén az „A” kommunikátor processzei számára az „A” kommunikátor a helyi és a „B” kommunikátor a távoli. A „B” kommunikátor processzei számára pedig pont fordítva, azaz a „B” kommunikátor a helyi és az „A” kommunikátor a távoli. Inter-kommunikátorok esetén ugyanolyan sorrendben kell felparaméterezni a pont-pont kommunikációs függvényeket, mint ahogy azt az intra-kommunikátoroknál megismertük. Csupán az a különbség, hogy a másik processzt – küldı függvényeknél a célprocesszt, a fogadó függvényeknél a forrásprocesszt – a távoli kommunikátorbeli azonosítójával kell megjelölni. Ennek az az elınye az MPI_COMM_WORLD használatához képest, hogy címezhetjük a processzeket a saját intra-kommunikátorukbeli címükkel. Megkötés viszont, hogy csak blokkoló kommunikációs függvényeket használhatunk. Az MPI elsı verziójában inter-kommunikátorokat nem használhatunk kollektív kommunikációra, míg az MPI második verziójában már erre is lehetıségünk van. Egy kommunikátorról az MPI_Comm_test_inter függvénnyel dönthetjük el, hogy inter- vagy intra-kommunikátor. A „flag” igaz értéke az inter-kommunikátort jelzi. A flag igaz vagy hamis értékét logikai értelemben vesszük, tehát igaz > 0, hamis = 0.
70
int MPI_Comm_test_inter ( MPI_Comm comm, // Ismeretlen típusú int* flag ); // A kommunikátor // „zászló”
II.8.2.1. Inter-kommunikátor összekapcsolásával
létrehozása
két
kommunikátor típusát jelzı
intra-kommunikátor
A feltétele annak, hogy két intra-kommunikátort összekapcsolva egy interkommunikátort hozhassunk létre az, hogy mindkét intra-kommunikátorban legyen egy-egy olyan processz, mely az összes csoporttársával – az azonos intra-kommunikátorbeli processzekkel – kommunikálni tud. Ennek a két „vezetı” processznek a kapcsolata teszi lehetıvé, hogy mint egy hídon keresztül a két intra-kommunikátor között a processzek kommunikálhassanak egymással. Szükség van egy harmadik, hídként szolgáló intrakommunikátorra is, melyen keresztül kommunikálhatnak a vezetı processzek, miközben részt vesznek az inter-kommunikátor létrehozásában. Ennek a harmadik, hídként szolgáló intrakommunikátornak általában az MPI_COMM_WORLD-öt szoktuk választani. Egy interkommunikátor általános struktúráját a 17. ábrán tekinthetjük meg.
17. ábra A két intra-kommunikátor inter-kommunikátorrá történı összekapcsolása az MPI_Intercomm_create függvénnyel lehetséges, amit mindkét intra-kommunikátor processzeinek meg kell hívnia. Mivel intra-kommunikátoronként különbözıképen kell felparaméterezni az MPI_Intercomm_create-et, ezért két kollektív függvényhívás szükséges.
71
MPI_Intercomm_create ( MPI_Comm local_comm, int local_leader,
MPI_Comm bridge_comm, int remote_leader,
int tag, MPI_Comm* intercomm );
// Helyi intra-kommunikátor // A helyi intra// kommunikátorban // a vezetı processz helyi // kommunikátorbeli // azonosítója // Hídként szolgáló // intra-kommunikátor // A távoli intra// kommunikátorban // a vezetı processz távolii // kommunikátorbeli // azonosítója // Biztonságos üzenetcímke // Létre jövı // inter-kommunikátor
Tekintsünk egy példaprogramot inter-kommunikátoron való üzenetátvitelre! 32. melléklet: main8_2_1.c
II.8.2.2. Inter-kommunikátorok adatainak lekérdezése A helyi kommunikátor adatait az intra-kommunikátoroknál megismert módon kérdezhetjük le. Az MPI_Comm_size-zal a processzek számát, az MPI_Comm_rank-kal a processzek azonosítóját kérdezhetjük le. Az MPI_Comm_group-pal a helyi intrakommunikátorból nyerhetjük ki a processzek csoportját. Ezek közül kettınek megvan a távoli kommunikátorra vonatkozó variánsa: Az MPI_Comm_remote_size és az MPI_Comm_remote_group. int MPI_Comm_remote_size ( MPI_Comm comm, int *size );
// Inter-kommunikátor // A távoli // intra-kommunikátorban // a processzek száma
int MPI_Comm_remote_group ( MPI_Comm comm, // Inter-kommunikátor MPI_group* group ); // A távoli // intra-kommunikátorhoz // tartozó csoport
72
Ellenırzı kérdések: 1.) Mi a kommunikátorok szerepe, miért hozunk létre belılük különbözı méretőeket és összetételőeket? 2.) Milyen viszonyban vannak egymással a processz-azonosítók és a kommunikátorok? Mint mondhatunk el azokról a processzekrıl, amelyek több kommunikátorba is beletartoznak? 3.) Milyen módon kommunikálhat egymással két olyan processz, melyek két különálló kommunikátorba tartoznak bele? Mi az alapvetı különbség az intra- és az interkommunikátorok között? 4.) Nevezzük meg, hogy milyen módokon hozhatunk létre intra-kommunikátort! 5.) Széthasítással keletkezı intra-kommunikátorok esetén mi a szerepe a "color" és a "key" paramétereknek? 6.) Miért szokás egy intra-kommunikátort lemásolni? Mi mondható el az új intrakommunikátorról? 7.) Milyen fıbb lépései vannak az intra-kommunikátorok módosítással történı létre hozásának? 8.) Hányféleképpen, milyen mőveletekkel módosítható egy processz csoport? 9.) Mire szolgál az MPI_Group_translate_ranks függvény? 10.) Mi mondható el a csoportok és a kommunikátorok megsemmisítésérıl, felszabadításáról? 11.) Milyen kritériumonak kell megfelelniük az inter-kommunikátort alkotó processz csoportoknak? 12.) Hogyan értelmezzük a helyi és távoli kommunikátor fogalmakat? 13.) Milyen kommunikációs függvényeket használhatunk inter-kommunikátorokban, és hogyan címezzük ezeket a függvényeket? 14.) Mi szükséges egy inter-kommunikátor létrehozásához, és hogyan épül fel a kapcsolat a két intra-kommunikátor között?
Feladatok: 1.) Próbáljuk ki a main8_1_1.c példaprogramot! 2.) Próbáljuk ki a main8_1_3.c példaprogramot! 3.) Próbáljuk ki a main8_2_1.c példaprogramot! 4.) Győjtsünk példákat, hogy milyen feladatok megoldásán egyszerősíthet újabb kommunikátor létre hozása!
73
II.9. Gráf topológiák A gráf topológiák – a cartesian topológiák mellet – az MPI által támogatott virtuális topológiák másik fı ága. Míg a cartesian topológiák inkább a mátrixszámítást támogatják, addig a gráf topológiák teljesen más célt szolgálnak. Segítségükkel processzek között kommunikációs irányokat jelölhetünk ki, a kapcsolatokat gráfok formájában megfogalmazva. A processzek gráf csomópontoknak, más szóval „node”-oknak feleltethetıek meg, valamint a közöttük lévı élek, nyilak a kommunikációs irányokat szimbolizálják. Mivel a kommunikáció két processz között általában kétirányú – amit az MPI alapvetıen feltételez –, ezért a nyilak is oda-vissza mutatnak; másként fogalmazva a gráfok mindkét irányban irányítottak. Tehát az MPI-ban használt gráfok irányítottságának jellemzıje a szimmetria.
II.9.1. Gráf topológiák létrehozása Az MPI_Graph_create függvénnyel egy általunk definiált gráf topológiát megvalósító kommunikátort hozhatunk létre. int MPI_Graph_create ( MPI_Comm old_comm, int nnodes, int* index,
int* edges,
int reorder,
MPI_Comm* new_comm );
// Szülı kommunikátor // Node-ok száma a gráfban // Az elsı „i” darab node // összes szomszédainak // száma 0-tól (nnodes-1)-ig // A node-ok azonosítóinak // sorrendjében a node-ok // szomszédainak azonosítói // A processzek azonosítóinak // újrarendezésének // engedélyezése vagy tiltása // Új kommunikátor
A gráf topológiával kapcsolatos információk a „new_comm” kommunikátorhoz rendelıdnek hozzá. A „reorder” paraméter igaz (>0) értékével engedélyezhetjük a processzek azonosítóinak újraosztását. Ha a „reorder” értéke hamis (=0), akkor az új kommunikátorban a processzek azonosítói megegyeznek a szülı kommunikátorbeli azonosítóikkal. Ha a „node”-ok száma a gráfban kisebb, mint a szülı kommunikátor mérete – processzeinek száma – , akkor a „felesleges” processzek a „new_comm” paraméterben MPI_COMM_NULL értéket kapnak vissza. Ha pedig nagyobb gráfot próbálunk felépíteni, mint ahány processz a szülı kommunikátorban rendelkezésre áll, akkor a függvény hibával tér vissza. Három paraméter: az „nnodes” változó, valamint az „index” és az „edges” tömbök határozzák meg a keletkezı gráf struktúráját. Az „nnodes”-ban adjuk meg a node-ok számát a gráfban, melyek 0-tól (nnodes-1)-ig sorszámozottak. Az „index” tömb „i”-edik indexő helyén az elsı „i” darab node összes szomszédainak száma áll. Az „edges” tömbben a nodeok azonosítóinak sorrendjében a node-ok szomszédainak azonosítói szerepelnek. Tehát az „edges” tömböt úgy képzeljük el, mint ha node-onként felsorolnánk a szomszédokat, és ezeket a felsorolásokat egymás mellé tennénk. Tehát összefoglalva az „index” tömb hossza a node-ok száma, az „edges” tömb hossza pedig az élek számának kétszerese (a kölcsönös irányítottság miatt). A gráf felépítéséhez az összes processznek a teljes gráf leírásával felparaméterezve kell meghívnia az MPI_Graph_create függvényt. 74
Tekintsünk a 18. ábrán látható gráfot:
18. ábra Ha a 18. ábrán lévı gráf topológiát szeretnénk létrehozni, akkor a „reorder” paramétertıl és a kommunikátoroktól eltekintve a következı értékeket kell adnunk az „nnodes” változónak, valamint az „index” és az „edges” tömböknek (19. ábra):
19. ábra Ezenkívül megfigyelhetjük, hogy az „i”-edik node fokszáma (i>0 esetben) az index[i]-index[i-1] összefüggésbıl adódik.
II.9.2. Gráf topológiák adatainak lekérdezése Ha egy konkrét gráf topológia jellemzıi nem állnak rendelkezésünkre – mert például egy másik függvényben hoztuk létre –, akkor az MPI_Graphdims_get és az MPI_Graph_get függvényekkel kérdezhetjük le ıket. Ezek a függvények hasonló szerepet töltenek be, mint a cartesian topológiák esetén az MPI_Cartdim_get és az MPI_Cart_get. Az MPI_Graphdims_get függvénnyel lekérdezzük az „index” tömbnek és az „edges” tömbnek a méretét; majd ezek ismeretében az MPI_Graph_get függvénnyel már hozzáférhetünk a fent említett tömbökhöz. int MPI_Graphdims_get ( MPI_Comm comm, int* nnodes, int* nedges );
75
// Gráf topológia kommunikátora // Az „index” tömb mérete // (csomópontok száma) // Az „edges” tömb mérete // (élek számának kétszerese)
// Gráf topológia kommunikátora // Az „index” tömb mérete // (csomópontok száma) // Az „edges” tömb mérete // (élek számának kétszerese) // „index” tömb // „edges” tömb
int MPI_Graph_get ( MPI_Comm comm, int maxindex, int maxedges, int* index, int* edges );
Az egyes processzek szomszédainak a számát az MPI_Graph_neighbors_count függvénnyel kérdezhetjük le, majd a tényleges szomszédokat az MPI_Graph_neighbors függvénnyel. int MPI_Graph_neighbors_count ( MPI_Comm comm, // Gráf topológia // kommunikátora int rank, // A hívó processz // azonosítója int* neighbors ); // A hívó processz // szomszédainak a száma int MPI_Graph_neighbors ( MPI_Comm comm, // Gráf topológia kommunikátora int rank, // A hívó processz azonosítója int maxneighbors, // A hívó processz szomszédainak // a száma int *neighbors ); // A hívó processz szomszédait // tartalmazó tömb Összefoglalva láthatjuk, hogy tetszıleges, a megoldandó feladathoz illeszkedı gráf alkotására és használatára van lehetıségünk. Ha egy topológiának még a típusát sem ismerjük, akkor azt az MPI_Topo_test függvénnyel határozhatjuk meg. A „status” paraméterben – annak megfelelıen, hogy a topológia cartesian, gráf, vagy csupán egy általános intra-kommunikátor – rendre MPI_CART, MPI_GRAPH vagy MPI_UNDEFINED értékeket kapunk vissza. // Gráf topológia kommunikátora // Információ a kommunikátorról
int MPI_Topo_test ( MPI_Comm comm, int* status );
Tekintsünk egy példaprogramot gráf topológia használatára! 33. melléklet: main9_2.c
76
Ellenırzı kérdések: 1.) Mit céloz processzek gráf topológiába való rendezése? Mi a csomópontoknak és az éleknek a megfelelıje? 2.) Mire vonatkozik az MPI-ban használt gráfok szimmetriája? 3.) Hogyan építünk fel egy gráfot, hogyan kell felparaméterezni egy lerajzolt gráf alapján az MPI_Graph_create függvényt? 4.) Milyen hasonlóság van a cartesian topológiák és a gráf topológiák jellemzóinek lekérdezésére használt függvények között?
Feladatok: 1.) Próbáljuk ki a main9_2.c példaprogramot! 2.) Győjtsünk ötleteket, hogy milyen feladatok megoldását könnyítheti meg gráf topológia alkalmazása!
77
II.10. Egy komolyabb párhuzamos algoritmus önálló megvalósítása A megelızı fejezetekben leírt ismeretek elsajátításával, az ellenırzı kérdések megválaszolásával, valamint a példaprogramok kipróbálásával és végigkövetésével képessé váltunk arra, hogy egy komolyabb párhuzamos algoritmust önállóan leprogramozzunk MPI környezetben. A következıkben két feladatjavaslatot teszünk párhuzamosítható problémákra, melyek közül válasszunk egyet, amit önállóan elkészítünk!
BMP képet módosító párhuzamos program Írjunk egy olyan párhuzamos programot, mely egy 24 bit/pixel színmélységő tetszıleges BMP képen végez mőveleteket. A program tervezéséhez a 2.2. fejezetben fogalmaztunk meg javaslatokat. Az 1. mellékletben – segítségképp – már elkészítettük a feladatot sorosan megoldó programot, hogy a fájlmőveletek megvalósításával és a BMP specifikáció megismerésével ne kelljen foglalkozni, hanem csak a párhuzamosítandó feladatra lehessen koncentrálni.
Autópálya forgalmát szimuláló párhuzamos program Írjunk egy olyan párhuzamos programot, mely a Nagel és Schreckenberg által megalkotott autópálya modellben [13] az autók helyét, sebességét és ezzel a forgalmi dugók kialakulását és megszőnését szimulálja. Az elkészült programot módosítva vegyük fel az autópályán kialakuló állandósult összsebesség grafikonját az autók sőrőségének függvényében! A Nagel-Schreckenberg modellben az autók az álló helyzetet leszámítva öt különbözı sebességet vehetnek fel, amelyeket 0-tól 5-ig egész számokkal jelölünk. Egy a következıkben ismertetet algoritmus szerint minden idıpillanatban kiszámítjuk az autók sebességét és aszerint léptetjük ıket. Az algoritmust a 20. ábrán követhetjük végig:
20. ábra
78
Érdemes a feladatot úgy megoldani, hogy az egysávos autópályát mint tömböt szétdaraboljuk és az egyes darabokat processzekhez rendeljük. Továbbá érdemes master-slave modellt alkalmazni, melyben a master kezdetben legyártja az adathalmazt, szétosztja a slave processzek között, azok egymással kommunikálva kiszámítják az autópálya állapotát az adott pillanatban, majd visszaküldik az autópályarészletület a masternek, aki a visszakapott állapotot fájlban rögzíti, miközben a slave-ek már a következı idıpillanat számításába kezdenek. A 34. és 35. mellékletekben a Nagel-Schreckenberg autópályamodellt szimuláló feladatra mutatunk be mintamegoldást.
79
III. Továbbfejlesztési lehetıségek Az MPI ezen szakdolgozat keretein belül bemutatott mélységő ismerete képessé teszi a mérnökhallgatókat, hogy bármely párhuzamosítható tudományos problémát megoldjanak. Az MPI egy napjainkban is dinamikusan fejlıdı standard, melynek rengeteg implementációja létezik [14], így a szakdolgozat sokirányú továbblépésre ad lehetıséget. A szakdolgozatban az MPI elsı verziója által definiált technológiák zömét fedtem le, melyek így is rendkívül gazdag eszköztárat bocsátanak rendelkezésünkre. Az MPI elsı verziójának határain belül maradva például a hibakezelésre lehetne még kitérni. Az MPI második verziója további hasznos technológiákkal bıvíti a palettát, mint például a párhuzamos fájlkezelés és az egyoldalas kommunikáció. Az MPI függvényeknek léteznek a C++ programozási nyelvbe illeszkedı formái is, valamint igénybe vehetjük a párhuzamos matematikai könyvtárak szolgáltatásait is. A tematika továbbfejlesztésére irányuló törkevések közül a legfontosabbnak az oktatás során megfogalmazódó visszajelzéseket tartom, hiszen a cél a mérnökhallgatókat addig a pontig elvezetni, ahonnan már érdeklıdésbıl és önszorgalomból folytatják a párhuzamos programozás mélyebb megismerését.
IV. Összefogalás Összegezve a munkámat, és visszatekintve a kezdeti célokra véleményem szerint sikerült olyan oktatási anyagot készítenem, mely alkalmas a párhuzamos programokban való gondolkodás tanulására és tanítására, valamint kellıen precíz és részletes ahhoz, hogy ne kelljen a tanulás során más forrást használni; ugyanakkor kellıen lényegre törı és struktúrált is ahhoz, hogy könnyen áttekinthetı legyen. Az ellenırzı kérdésekkel és a példaprogramokkal a tananyag laboratóriumi foglalkozásokon való oktatását is megfelelıen elıkészítettem. Bízom benne, hogy munkámat eredménnyel használják majd hallgatók és oktatók egyaránt.
80
V. Irodalomjegyzék [1]
Páhuzamos algoritmusok nemlineáris peremérték-feladatok megoldására, szerz. SZEBERÉNYI Imre, kiadó: Budapesti Mőszaki és Gazdaságtudományi Egyetem, 2003.
[2]
Introduction to Parallel Computing, 2nd Edition, szerz. Ananth GRAMA, Anshul GUPTA, George KARYPIS, Vipin KUMAR, kiadó: Addison-Wesley, 2003.
[3]
High Performance Computing, Second Edition, szerz. Charles SEVERANCE, Kelvin DOWD, kiadó: O’Reilly Media, 1998.
[4]
http://ci-tutor.ncsa.illinois.edu/login.php, kiadó: National Science Foundation Office of Cyberinfrastructure, 2006.
[5]
Some computer organizations and their e_ectiveness, szerz. Michael J. FLYNN, kiadó: IEEE Transactions on Computers C-21, 1972.
[6]
Számítógép architektúrák, szerz. NÉMETH Gábor, HORVÁTH László, kiadó: Akadémiai Kiadó, 1992.
[7]
Symmetric Multi-Processing (SMP) systems on top of contemporary Intel appliances, szerz. Jiri HLUSI, kiadó: University of Tampere Department of Computer and Information Sciences, 2002.
[8]
MPI: The Complete Reference, Volume 1, The MPI Core, Second Edition, szerz. Marc SNIR, Steve OTTO, Steven HUSS-LEDERMAN, David WALKER, Jack DONGARRA, kiadó: MIT Press, 1998.
[9]
PVM - A Users' Guide and Tutorial for Networked Parallel Computing, szerz. Al GEIST, Adam BEGUELIN, Jack DONGARRA, WEICHENG Jiang, Robert MANCHEK, Vaidyalingam S. SUNDERAM, kiadó: MIT Press, 1994.
[10] A Practical Programming Model for the Multi-Core Era, szerk. Barbara CHAPMAN, WEIMIN Zheng, Guang R. GAO, Mitsuhisa SATO, Eduard AYGUADÉ, DONGSHENG Wang, kiadó: Springer, 2008. [11] http://www.fing.edu.uy/if/cursos/fiscomp/extras/fortran/uliverpoolf90/HTMLHPFCourseSlides.html, kiadó: University of Liverpool, 1997. [12] http://www.lam-mpi.org/, kiadó: LAM Team, Indiana University, 2009. [13] http://de.wikipedia.org/wiki/Nagel-Schreckenberg-Modell, kiadó: Wikipedia, 2009. [14] http://www.mcs.anl.gov/research/projects/mpi/implementations.html, kiadó: Mathematics and Computer Science Division, Argonne National Laboratory, 2009.
81
VI. Mellékletek Az oktatási anyaghoz készült példaprogramok a CD mellékleten találhatóak.
82
