Szakdolgozat
Miskolci Egyetem
Operációkutatási eszközök párhuzamosítása I.
Készítette: Tancsák Tamás Ádám Programtervező informatikus hallgató Témavezető: Dr. Olajos Péter
Miskolc, 2016
Miskolci Egyetem Gépészmérnöki és Informatikai Kar Alkalmazott Matematikai Tanszék
Szám:
Szakdolgozat Feladat Tancsák Tamás Ádám (RQHXAH) programtervező informatikus jelölt részére. A szakdolgozat tárgyköre: Párhuzamosítás A szakdolgozat címe: Operációkutatási eszközök párhuzamosítása I. A feladat részletezése: Matematikai rész: Az operációkutatás alapvető eszközeinek, módszereinek párhuzamosítása, ahol az hatékony számítási előnyt jelent. Ennek során pl. a Gauss-, a Gauss-Jordan-, rangszámítási és pivotálási módszereket vesszük górcső alá és vizsgáljuk meg azok egyszerű párhuzamosítási technikák esetén történő, futásidőben megvalósuló változásait. Ekkor nemcsak a javuló lépésszámot, hanem a forrásfelhasználást is vizsgáljuk, keressük az előnyös párhuzamosítási programrészeket és döntünk annak létjogosultsága mellett vagy elvetjük őket. Programozási rész: A C nyelv és az ahhoz kötődő párhuzamos eszközöket támogató csomagok ismerete és használata szükséges a feladatok elvégzéséhez. Ezek segítségével egy C nyelven elkészített program készül, amely Windows és/vagy Linux környezetben is egyaránt jól használható.
Témavezető(k): Dr. Olajos Péter egyetemi docens Konzulens(ek): A feladat kiadásának ideje: 2015.09.21
................................. szakfelelős 2
Eredetiségi Nyilatkozat
Alulírott . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ; Neptun-kód: . . . . . . . . . . . . . . . . . . . a Miskolci Egyetem Gépészmérnöki és Informatikai Karának végzős . . . . . . . . . . . . . . . . . . . szakos hallgatója ezennel büntetőjogi és fegyelmi felelősségem tudatában nyilatkozom és aláírásommal igazolom, hogy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . című szakdolgozatom/diplomatervem saját, önálló munkám; az abban hivatkozott szakirodalom felhasználása a forráskezelés szabályai szerint történt. Tudomásul veszem, hogy szakdolgozat esetén plágiumnak számít: • szószerinti idézet közlése idézőjel és hivatkozás megjelölése nélkül; • tartalmi idézet hivatkozás megjelölése nélkül; • más publikált gondolatainak saját gondolatként való feltüntetése. Alulírott kijelentem, hogy a plágium fogalmát megismertem, és tudomásul veszem, hogy plágium esetén szakdolgozatom visszautasításra kerül.
Miskolc, . . . . . . . . . . . .év . . . . . . . . . . . .hó . . . . . . . . . . . .nap
................................. Hallgató
3
1. szükséges (módosítás külön lapon) A szakdolgozat feladat módosítása nem szükséges ......................
...........................
dátum
témavezető(k)
2. A feladat kidolgozását ellenőriztem: témavezető (dátum, aláírás):
konzulens (dátum, aláírás):
..............
.............
..............
.............
..............
.............
3. A szakdolgozat beadható: ......................
...........................
dátum
témavezető(k)
4. A szakdolgozat . . . . . . . . . . . . . . . . . . . szövegoldalt . . . . . . . . . . . . . . . . . . . program protokollt (listát, felhasználói leírást) . . . . . . . . . . . . . . . . . . . elektronikus adathordozót (részletezve) ................... . . . . . . . . . . . . . . . . . . . egyéb mellékletet (részletezve) ................... tartalmaz. ......................
...........................
dátum
témavezető(k)
5. bocsátható A szakdolgozat bírálatra nem bocsátható A bíráló neve: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ......................
...........................
dátum
szakfelelős
6. A szakdolgozat osztályzata a témavezető javaslata:
................
a bíráló javaslata:
................
a szakdolgozat végleges eredménye: . . . . . . . . . . . . . . . . Miskolc, . . . . . . . . . . . . . . . . . . . . . . . .
................................. a Záróvizsga Bizottság Elnöke 4
Tartalomjegyzék 1. Bevezetés
7
2. Téma elméleti kifejtése 2.1. Alapfogalmak . . . . . . . . . . . . . . . . . . . . . . . 2.1.1. Mátrix . . . . . . . . . . . . . . . . . . . . . . . 2.1.2. Főátlóbeli elem . . . . . . . . . . . . . . . . . . 2.1.3. Diagonális mátrix . . . . . . . . . . . . . . . . . 2.1.4. Lineáris egyenletrendszer . . . . . . . . . . . . . 2.1.5. Elemek inverziója . . . . . . . . . . . . . . . . . 2.2. Lineáris egyenletrendszer megoldása Gauss módszerrel 2.2.1. Gauss-elimináció . . . . . . . . . . . . . . . . . 2.2.2. Téglalap módszer . . . . . . . . . . . . . . . . . 2.3. Lineáris egyenletrendszer megoldása Gauss-Jordan módszerrel . . . . . . . . . . . . . . . . . 2.3.1. Gauss-Jordan elimináció . . . . . . . . . . . . . 2.3.2. Téglalap módszer . . . . . . . . . . . . . . . . . 2.4. Determináns kiszámítása . . . . . . . . . . . . . . . . . 2.4.1. Determináns kiszámítása definíció szerint . . . . 2.4.2. Determináns kiszámítása kifejtési tétellel . . . . 2.5. Felhasznált technológiák . . . . . . . . . . . . . . . . . 2.5.1. C nyelv . . . . . . . . . . . . . . . . . . . . . . 2.5.2. OpenMP . . . . . . . . . . . . . . . . . . . . . . 2.5.3. R nyelv . . . . . . . . . . . . . . . . . . . . . . 3. Fejlesztői dokumentáció 3.1. Gauss elimináció sor és oszlopcserével . . . . . 3.1.1. A program működése (G-RC.c) . . . . 3.2. Gauss elimináció téglalap módszerrel . . . . . 3.2.1. A program működése (G-Rectangle.c) . 3.3. Gauss-Jordan elimináció sor és oszlopcserével 3.3.1. A program működése (GJ-RC.c) . . . . 3.4. Gauss-Jordan elimináció téglalap módszerrel . 3.4.1. A program működése (GJ-Rectangle.c) 3.5. Determináns meghatározása definíció szerint . 3.5.1. A program működése (D-D.c) . . . . . 3.6. Determináns meghatározása kifejtési tétellel . 3.6.1. A program működése (D-Laplace.c) . . 3.7. Grafikus felhasználói felület . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
8 8 8 8 8 9 9 9 9 10
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
11 11 11 12 12 13 14 14 15 15
. . . . . . . . . . . . .
17 17 17 21 21 26 26 31 31 35 35 40 40 44
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
5
3.7.1. A program működése (Gui.cpp) . . . . . . . . . . . . . . . . . .
44
4. Összefoglalás
47
Irodalomjegyzék
48
Adathordozó használati útmutató
49
6
1. fejezet Bevezetés A párhuzamos feldolgozás azon az elgondoláson alapul, hogy a program futásának felgyorsítása érdekében a program kódját több részre bontjuk, és ezeket egyidejűleg külön-külön processzor segítségével futtatjuk. Régebben a több processzoros párhuzamos futtatást egy speciálisan arra tervezett gépen lehetett futtatni ami nagyon költséges volt, csak nagyon kevesen férhettek hozzá. A mai számítógépek legtöbbjének már több magos processzoruk van, ami lehetővé teszi, hogy bárki párhuzamosan futó programokat készíthessen. Ennek köszönehtően a párhuzamosítás nagyon fontos szerepet játszik manapság a programozásban.1 Programjaink a párhuzamosítás által sokkal gyorsabban futhatnak mintha csak egy szálon futtatnánk őket. Persze ez nem mindig igaz, noha a processzorok számának növelésével a feldolgozás felgyorsítható, nagyon sok program nem tudja kihasználni a párhuzamosításból származó előnyöket. A párhuzamosítástól akkor várhatunk eredményt, illetve akkor érdemes foglalkozni vele, ha a program jól párhuzamosítható, tehát vannak benne olyan részek amik egymástól függetlenül több processzoron futtathatóak. Például legyen 100 darab összeadás amik nem összefüggőek. Ezeket 4 részre osztva 4 processzorral elméletileg négyszer olyan gyorsan is fel tudjuk dolgozni. Gyakorlatilag viszont egyéb tényezők is közrejátszanak, például időt veszíthetünk a szálak létrehozásával. A választásom azért esett erre a témára, mert az informatika területén legjobban a számítógépes programok párhuzamosítása iránt érdeklődöm. Először a „Párhuzamos eszközök programozása” tárgy keretein belül találkoztam a párhuzamosítással. Amikor megírtam az első párhuzamos programomat elképesztő volt látni, hogy mire képes a több processzor, mennyivel gyorsabb így a futási idő mint egy egyszerű szekvenciális program futtatása esetén. Kíváncsi vagyok, vajon milyen eredményeket fogunk elérni a szakdolgozati témában szereplő algoritmusokkal, vajon sikerül-e ott is nagymértékű sebesség növekedést elérni.
1
A bemutatott kutató munka a TÁMOP-4.2.1.B-10/2/KONV-2010-0001 jelű projekt részeként az Európai Unió támogatásával, az Európai Szociális Alap társfinanszírozásával valósul meg
7
2. fejezet Téma elméleti kifejtése 2.1. Alapfogalmak 2.1.1. Mátrix A mátrix vízszintes vonalban elhelyezkedő elemei sorokat, függőleges vonalban elhelyezkedő elemei oszlopokat alkotnak. Egy m sorból és n oszlopból álló mátrixot m-szer n-es mátrixnak neveznek (írva: m × n), az m és n pozitív egész számok a mátrix dimenziói (lásd [1]). A mátrix dimenzióit mindig először a sorok számával, majd azt követően az oszlopok számával adják meg. A mátrixnak az i-edik sorában és j-edik oszlopában lévő elemét a mátrix i,j-edik elemének nevezik, jelölése A[i, j]. Mindig először a sorszám, majd az oszlopszám szerepel. Az A mátrix jelölése: a11 a12 a13 . . . a1n a21 a22 a23 . . . a2n A = a31 a32 a33 . . . a3n . .. .. .. ... .. . . . am1 am2 am3 . . . amn
2.1.2. Főátlóbeli elem Egy mátrixban az olyan elemeket, amelyeknek a vízszintes és függőleges indexe megegyezik főátlóbeli elemeknek nevezzük.
2.1.3. Diagonális mátrix Olyan négyzetes mátrix, amelynek minden főátlón kívüli eleme nulla.
8
2.2. Lineáris egyenletrendszer megoldása Gauss módszerrel
2.1.4. Lineáris egyenletrendszer A lineáris egyenletrendszer olyan többismeretlenes egyenletrendszer, ahol minden ismeretlen elsőfokon (azaz első hatványon) szerepel (lásd [2]). Egy m egyenletből álló és n ismeretlent tartalmazó lineáris egyenletrendszer: a11 x1 + a12 x2 + . . . + a1n xn = b1 a21 x1 + a22 x2 + . . . + a2n xn = b2 .. . am1 x1 + am2 x2 + . . . + amn xn = bm
2.1.5. Elemek inverziója Az 1, 2, . . . , n rendezhető elemek egy (i1 , i2 , . . . , im ) permutációjában az ij és ik elemeket inverzióban lévőnek mondjuk, ha j < k és ij > ik , vagyis a két elem nem követi egymást monoton növekvő sorrendben (lásd [3]).
2.2. Lineáris egyenletrendszer megoldása Gauss módszerrel 2.2.1. Gauss-elimináció Története A Gauss-elimináció a lineáris algebra egy lineáris egyenletrendszerek megoldására használatos algoritmusa. Az eljárás Carl Friedrich Gauss nevét viseli, aki maga is leírta a lineáris egyenletrendszerek megoldására szolgáló általános eljárást, azonban ez az eljárás már Gauss előtt is ismert volt. Az eljárás leírása A lineáris egyenletrendszereket rendezzük úgy, hogy bal oldalon rögzített sorrendben legyenek az együtthatók és az ismeretlenek, a jobb oldalon pedig a konstansok. A bal oldal együtthatóiból és a jobb oldal konstansaiból létrehozhatjuk a kibővített együtthatómátrixot. Ezt követően következik a Gauss-elimináció, aminek a segítségével egy felső háromszög vagy trapéz alakú mátrixot hozunk létre. Megnézzük, hogy a főátlóbeli elem sorának hányszorosát kell hozzáadni a többi sorhoz, hogy a főátlóbeli elem alatti elemek kinullázódjanak. Elvégezzük az összeadásokat, majd kiválasztjuk a következő sorban is a főátlóbeli elemet. Addig ismételjük a fentebbi lépéseket, amíg felső háromszög vagy trapéz alakú mátrixot nem kapunk. A Gauss-elimináció szerint az egyenletrendszert a következő lépésekkel lehet megoldani: • két egyenlet felcserélése, • egyenlet számmal szorzása, • egyik egyenlethez a másik skalárszorosának hozzáadása. 9
2.3. Lineáris egyenletrendszer megoldása Gauss-Jordan módszerrel Megoldások kiszámítása Ha az ismeretlenek száma megegyezik az egyenletek számával, akkor felső háromszög alakú mátrix jöhet létre és könnyen leolvasható a megoldás. A legalsó egyenletben egyetlen ismeretlen és konstans van amivel meghatározhatjuk az ismeretlent. Egy sorral fentebb, ha behelyettesítjük a már kiszámolt ismeretleneket, akkor ismét egy darab ismeretlent és konstansokat kapunk, amiből újra ki tudunk számolni egy ismeretlent. Ezt addig folytatjuk amíg a legfelső sorban is megkapjuk az utolsó ismeretlen értékét. Ha több ismeretlen van, mint egyenlet akkor egy trapéz alakú mátrix jön létre aminek végtelen számú megoldása van. Ezeket a következőképpen lehet megkapni: a téglalap alakú részt átvisszük a jobb oldalra, ezek lesznek a szabad ismeretlenek, amiknek bármi lehet az értéke. A bal oldalon maradó háromszög alakú rész ismeretlenjei lesznek a kötött ismeretlenek. Ezeket egyértelműen meghatározhatjuk a fenti módszer segítségével.
2.2.2. Téglalap módszer Az eljárás leírása A lineáris egyenletrendszereket rendezzük úgy, hogy bal oldalon rögzített sorrendben legyenek az együtthatók és az ismeretlenek, a jobb oldalon pedig a konstansok. A bal oldal együtthatóiból és a jobb oldal konstansaiból létrehozhatjuk a kibővített együtthatómátrixot. Ezt követően következik a téglalap módszer aminek segítségével kiszámíthatjuk az ismeretlenek értékét. Első lépésként kiválasztjuk az első főátlóbeli elemet. Ezt az elemet nevezhetjük pivotelemnek is. A pivotelem sorát végigosztjuk a pivotelemmel. A pivotelem oszlopát végigosztjuk a pivotelem (−1)-szeresével és a pivotelem alatti elemeket kinullázzuk. A többi elemet a téglalap módszerrel számítjuk a következőképpen: Legyen a kiszámítandó elem „b”, a pivotelem „a” a téglalap másik 2 sarka pedig „c” és képlettel megkapjuk a kívánt elem értékét. „d”. Ekkor a b − c·d a Ha minden elemet kiszámoltunk, kiválasztjuk az új pivotelemet. Ha kiválasztottuk, akkor a fenti módszerrel újra kiszámoljuk az összes többi elemet, és újra választunk egy pivot elemet. Addig ismételjük a fentebbi lépéseket, amíg felső háromszög vagy trapéz alakú mátrixot nem kapunk. Megoldások kiszámítása Ha az ismeretlenek száma megegyezik az egyenletek számával, akkor felső háromszög alakú mátrix jöhet létre és egyértelműen leolvasható a megoldás. Ha több ismeretlen van mint egyenlet, akkor egy trapéz alakú mátrix jön létre, aminek végtelen számú megoldása van. Ezeket a következőképpen lehet megkapni: A téglalap alakú részt átvisszük a jobb oldalra, ezek lesznek a szabad ismeretlenek, amiknek bármi lehet az értéke. A bal oldalon maradó háromszög alakú rész ismeretlenjei lesznek a kötött ismeretlenek. Ezeket egyértelműen meghatározhatjuk a fenti módszer segítségével.
10
2.3. Lineáris egyenletrendszer megoldása Gauss-Jordan módszerrel
2.3. Lineáris egyenletrendszer megoldása Gauss-Jordan módszerrel 2.3.1. Gauss-Jordan elimináció Az eljárás leírása Az eljárás nagyon hasonlít a Gauss-eliminációra, csak annyi az eltérés, hogy az adott oszlop kinullázása mind a főátló alatti, mind a főátló feletti elemeket érinti. Ennek köszönhetően nem kell az eljárás végén behelyettesíteni az egyenletekbe, a megoldás egyértelmű lesz. A lineáris egyenletrendszereket rendezzük úgy, hogy bal oldalon rögzített sorrendben legyenek az együtthatók és az ismeretlenek, a jobb oldalon pedig a konstansok. A bal oldal együtthatóiból és a jobb oldal konstansaiból létrehozhatjuk a kibővített együtthatómátrixot. Ezt követően következik a Gauss-elimináció aminek a segítségével egy felső háromszög vagy trapéz alakú mátrixot hozunk létre. Megnézzük, hogy a főátlóbeli elem sorának hányszorosát kell hozzáadni a többi sorhoz, hogy a főátlóbeli elem alatti elemek kinullázódjanak. Elvégezzük az összeadásokat, majd kiválasztjuk a következő sorban is a főátlóbeli elemet. Addig ismételjük a fentebbi lépéseket, amíg felső háromszög vagy trapéz alakú mátrixot nem kapunk. Ha megvan a felső háromszög alak, akkor a sorokat végigosztjuk a főátlóbeli elmekkel és a főátló felett található elemeket kezdjük el kinullázni. Megnézzük, hogy a főátlóbeli elem sorának hányszorosát kell hozzáadni a többi sorhoz, hogy a főátlóbeli elem feletti elemek kinullázódjanak. Elvégezzük az összeadásokat majd kiválasztjuk a következő sorban is a főátlóbeli elemet. Addig ismételjük a fentebbi lépéseket amíg diagonális vagy trapéz alakú mátrixot nem kapunk. Megoldások kiszámítása Ha diagonális mátrixot kaptunk, akkor a megoldás egyértelműen leolvasható. Ha trapéz alakú mátrixot kapunk, akkor végtelen számú megoldásunk van. Ezeket a következőképpen lehet megkapni: a téglalap alakú részt átvisszük a jobb oldalra, ezek lesznek a szabad ismeretlenek, amiknek bármi lehet az értéke. A bal oldalon maradó diagonális mátrix ismeretlenjei lesznek a kötött ismeretlenek. Ezeket egyértelműen meghatározhatjuk.
2.3.2. Téglalap módszer Az eljárás leírása Az eljárás nagyon hasonlít a Gauss-eliminációra téglalap módszerére, csak annyi az eltérés, hogy az adott oszlop kinullázása mind a főátló alatti, mind a főátló feletti elemeket érinti. Ennek köszönhetően nem kell az eljárás végén behelyettesíteni az egyenletekbe,
11
2.4. Determináns kiszámítása a megoldás egyértelmű lesz. A lineáris egyenletrendszereket rendezzük úgy, hogy bal oldalon rögzített sorrendben legyenek az együtthatók és az ismeretlenek, a jobb oldalon pedig a konstansok. A bal oldal együtthatóiból és a jobb oldal konstansaiból létrehozhatjuk a kibővített együtthatómátrixot. Ezt követően következik a téglalap módszer, aminek segítségével kiszámíthatjuk az ismeretlenek értékét. Első lépésként kiválasztjuk az első főátlóbeli elemet. Ezt az elemet nevezhetjük pivotelemnek is. A pivotelem sorát végigosztjuk a pivotelemmel. A pivotelem oszlopát végigosztjuk a pivotelem (−1)-szeresével és a pivotelem alatti elemeket kinullázzuk. A többi elemet a téglalap módszerrel számítjuk a következőképpen: Legyen a kiszámítandó elem „b”, a pivotelem „a” a téglalap másik 2 sarka pedig „c” és képlettel megkapjuk a kívánt elem értékét. „d”. Ekkor a b − c·d a Ha megvan a felső háromszög alak, akkor a főátló felett található elemeket kezdjük el kinullázni. Kiválasztjuk az első főátlóbeli elemet. Ezt az elemet nevezhetjük pivotelemnek is. A pivotelem sorát végigosztjuk a pivotelemmel. A pivotelem oszlopát végigosztjuk a pivotelem (−1)-szeresével és a pivotelem feletti elemeket kinullázzuk. A többi elemet a téglalap módszerrel számítjuk a következőképpen: Legyen a kiszámítandó elem „b”, a pivotelem „a” a téglalap másik 2 sarka pedig „c” és „d”. Ekkor a b − c·d a képlettel megkapjuk a kívánt elem értékét. Ha minden elemet kiszámoltunk, kiválasztjuk az új pivotelemet. Ha kiválasztottuk, akkor a fenti módszerrel újra kiszámoljuk az összes többi elemet, és újra választunk egy pivot elemet. Addig ismételjük a fentebbi lépéseket, amíg diagonális vagy trapéz alakú mátrixot nem kapunk. Megoldások kiszámítása Ha diagonális mátrixot kaptunk, akkor a megoldás egyértelműen leolvasható. Ha trapéz alakú mátrixot kapunk, akkor végtelen számú megoldásunk van. Ezeket a következőképpen lehet megkapni: a téglalap alakú részt átvisszük a jobb oldalra, ezek lesznek a szabad ismeretlenek, amiknek bármi lehet az értéke. A bal oldalon maradó diagonális mátrix ismeretlenjei lesznek a kötött ismeretlenek. Ezeket egyértelműen meghatározhatjuk.
2.4. Determináns kiszámítása 2.4.1. Determináns kiszámítása definíció szerint Definíció Determinánson egy négyzetes mátrixhoz rendelt számot értünk. Ha egy A n×n-es négyzetes mátrix elemei az aij számok, akkor a determináns a következő képlettel kapható meg: X Dn := (−1I(i1 ,i2 ,...,in ) )α1i1 . . . αnin , (i1 ,...,in )∈Pn
12
2.4. Determináns kiszámítása ahol az összegzés az (1, 2, . . . , n) összes permutációjára történik és I(i1 , i2 , . . . , in ) jelöli az (i1 , i2 , . . . in ) permutációban lévő inverziók számát (lásd [3]). Az eljárás leírása Adott egy n × n-es mátrix. Felírjuk az n szám összes permutációját. Pl: P3 = {(1, 2, 3); (1, 3, 2), . . .} Ha felírtuk akkor behelyettesíthetünk a fentebb található képletbe. Az összeadás együtthatói a következőképpen néznek ki: a (−1) az adott inverzió értékének hatványára van emelve, és ez meg van szorozva a mátrix n darab elemével amelyek indexeinek első számai sorban haladnak (1, 2, 3, . . .) második indexeinek száma az adott permutációtól függenek. Pl: (−1)I(1,3,2) α11 α23 α32 = (−1)1 α11 α23 α32
2.4.2. Determináns kiszámítása kifejtési tétellel A determináns fenti definíciója természetesen nagyon nehezen kezelhető, hiszen bár D2 -re és D3 -ra léteznek egyszerű kiszámítási módok, a magasabb rendűekre még nem találtak ilyet, a közvetlen definícióból történő kiszámítás pedig már n = 4-re is 24 tagot eredményez, n = 6 esetben pedig már 200-nál is többet. Ezért jön jól a determináns kiszámítására a kifejtési tétel. Az eljárás leírása Vegyünk egy n × n-es mátrixot. Ha elhagyjuk az i-edik sorát és j-edik oszlopát, akkor egy (n − 1) × (n − 1)-es mátrix keletkezik. Az említett sor és oszlop metszéspontjában található elemhez tartozó előjeles aldetermináns nem más mint a keletkezett (n − 1) × (n − 1)-es részmátrix determinánsának (−1)i+j -szerese. Az aldeterminánsokat a megfelelő előjellel és a megfelelő elemmel összeszorozva és összegezve kapjuk a mátrix determinánsát. A (−1)i+j kifejezés −1 vagy +1 értéke megadja, hogy az aldetermináns átfordul-e az ellentetjére vagy sem. Könnyű megjegyezni: A bal felső sarokban lévő elem esetén mindig +1, és utána sakktáblaszerűen váltakozva következik a −1 és a +1 Például 5 × 5-ös esetben: + − + − + − + − + − + − + − + − + − + − + − + − + Tehát a determináns képlete a kifejtési tétel szerint: |A| =
n X
αik Aik
k=1
13
2.5. Felhasznált technológiák Az Ak aldetermináns a következőképpen α 11 . . . . ... .. i+j αi−1,1 . . . Ak = (−1) αi+1,1 . . . . .. .. . αn1 . . .
néz ki: α1,j−1 .. .
α1,j+1 .. .
... ...
αi−1,j−1 αi−1,j+1 . . . αi+1,j−1 αi+1,j+1 . . . .. .. .. . . . αn,j−1
αn,j+1
...
αi−1,n αi+1,n .. . αnn α1n .. .
2.5. Felhasznált technológiák 2.5.1. C nyelv Története A C egy általános célú programozási nyelv, melyet Dennis Ritchie fejlesztett ki Ken Thompson segítségével 1969 és 1973 között a UNIX rendszerekre AT&T Bell Labsnál. Idővel jóformán minden operációs rendszerre készítettek C fordítóprogramot, és az egyik legnépszerűbb programozási nyelvek egyikévé vált. Rendszerprogramozáshoz és felhasználói programok készítéséhez egyaránt jól használható. Az oktatásban és a számítógép-tudományban is jelentős szerepe van. A C minden idők legszélesebb körben használt programozási nyelve, és a C fordítók elérhetők a ma elérhető számítógép-architektúrák és operációs rendszerek többségére. Ismertető Egy C program tartalmaz függvényeket és változókat. A C függvények hasonlítanak a FORTRAN függvényeire és alrutinjaira, vagy a Pascal függvényeire és eljárásaira. A main() egy speciális függvény, ahol a C program elkezdődik, tehát minden C programnak tartalmaznia kell egy main() függvényt. Általában a main() meghív más függvényeket a feladatok elvégzésére. Ezek a függvények vagy az adott program részei, vagy egy külső könyvtárból (library) származnak. A külső függvények elérhetősége fejléc-állományokra (header) hivatkozással biztosítható az előfordító (preprocessor) #include direktívájával. Bizonyos könyvtári függvényeket, mint például a printf (), a C szabvány definiál, ezek a szabvány könyvtárban megtalálható függvények. Nem minden C implementációban található meg minden szabvány könyvtári függvény. A függvény adhat vissza értéket az őt meghívó környezetnek. Emellett a cím szerint kapott paramétereket szintén meg tudja változtatni. (lásd [4])
14
2.5. Felhasznált technológiák
2.5.2. OpenMP Története Az OpenMP Architecture Review Board (ARB) cég az első API specifikációját 1997 októberében adta ki OpenMP for Fortran 1.0 néven. A következő év októberében kiadták a C és C++ szabványt is. Jelenleg a 4.0-ás verziónál tartanak amit 2013 júliusában adtak ki. Ismertető Az OpenMP a fő informatikai cégek által definiált interfész, hordozható, skálázható eszközt nyújt a fejlesztők számára elosztott-memória modellel. Az API C/C++ és Fortran nyelveket támogatja számos architektúrán: többek között UNIX és Windows. Nagy előnye, hogy pragmákat használ és ezek használatához nem kell nagy mértékben módosítani a szekvenciális program kódját. A pragma hatóköre egy struktúrális blokk: {. . .} Tehát ha a program csak egy részét szeretnénk párhuzamosítani az is megoldható. Hátránya, hogy olyan compiler kell hozzá, ami támogatja az OpenMP-t. Hiányzik egy megbízható hibakezelő belőle. Megvan az esélye, hogy nehezen javítható szinkronizációs hibák és versenyhelyzetek alakuljanak ki. Az OpenMP egy API amely többszálú, osztott-memória modellre épül. Három alapvető komponenst tartalmaz: • Fordítónak szóló direktívák. • Futtatási környezethez könyvtárak. • Környezeti változók. Az OpenMP a Fork-Join modell szerint működik. Minden program a főszálon indul el. Ez szekvenciális programvégrehajtást jelent az első párhuzamos régióig. FORK: A főszál párhuzamosan futó szálakat hoz létre. JOIN: Ha a párhuzamos rész összes szála befejezte a tevékenységét a befejező szinkronizációs pontnál, akkor csak a főszál fut tovább. A párhuzamos blokkokat dinamikus vagy statikus módon is végre lehet hajtani. A dinamikus mód az alapértelmezett, ekkor a létrehozott szálak száma dinamikusan változik, statikus mód esetén mindig annyi szál van, amennyit a programozó beállított. Beágyazott újabb párhuzamos szálak indítása implementáció függő. A dinamikus szálkezelés szintén implementáció függő. (lásd [5])
2.5.3. R nyelv Története Az R programozási nyelv, amit időnként „GNU S”-ként is emlegetnek, egy szakterületspecifikus programozási nyelv és szoftverkörnyezet statisztikai számításokhoz és ábrázoláshoz. Az első változatát Ross Ihaka és Robert Gentleman készítették (innen az „R” 15
2.5. Felhasznált technológiák név) az Auckland-i Egyetemen, Új-Zélandon; azóta egy kisebb fejlesztői csoport a világ minden tájáról közös erőfeszítésekkel folyamatosan fejleszti tovább. (lásd [6]) Ismertető Az R egy szabad, nyílt forráskódú, professzionális és folyamatos fejlesztés alatt álló, statisztikai szoftvercsomag, amelyben hihetetlen gazdagságban állnak rendelkezésre a már kidolgozott eljárásokat tartalmazó függvények és munkakörnyezetek. Ezen szoftverkörnyezet csomagjainak a száma napról-napra növekszik, amelyet a CRAN hálózat tömörít magában. Bár többek szerint az R nehezen tanulható és programozási képességeket is kíván, annak sikerét és mára elterjedt használatát jól fémjelzi, hogy a New York Times nemrégiben az adatelemzés „lingua franca”-jáként az R-t említette. (lásd [7]) A szakdolgozatban arra használom a programot, hogy grafikonokon ábrázoljam vele a futási időket szekvenciális, illetve párhuzamos futások esetén. Ezáltal még jobban tudjuk szemléltetni a futási időbeni eltéréseket.
16
3. fejezet Fejlesztői dokumentáció 3.1. Gauss elimináció sor és oszlopcserével A program először bekéri, hogy szekvenciálisan vagy párhuzamosan szeretnénk futtatni a programot. Ezután a felhasználónak már nincs más dolga, a program kiszámítja az egyenletrendszerek megoldását további beavatkozás nélkül. A program több egyenletrendszer megoldását is kiszámítja, mindig egyre nagyobb mátrixokat használva, hogy jobban szemléltethessük a párhuzamosítással elérhető gyorsulást.
3.1.1. A program működése (G-RC.c) A program egy ismeretlen kiszámításával kezdődik, majd ha megtalálta a megoldást, akkor egy kétszer akkora mátrixszal kezd el dolgozni. Ez egészen addig tart, amíg el nem érünk az 1024 ismeretlenes mátrixhoz. while(n<=1024) { . . . n=n*2; } A kibővített együttható mátrix beolvasása automatikusan történik véletlen módon választott (random) számokat használva. printf("Ismeretlenek: %d \t",n); for(i=1; i<=n; i++) { for(j=1; j<=n+1; j++) { A[i][j]=5-rand()%11; } } Ha a mátrix mérete 4 vagy kisebb, akkor kiírja a kiinduló mátrixot.
17
3.1. Gauss elimináció sor és oszlopcserével if(n<=4) { for(i=1; i<=n; i++) { for(j=1; j<=n+1; j++) { if(j
3.1. Gauss elimináció sor és oszlopcserével for(j=1; j
i) { szorzo=A[k][i]/A[i][i]; { for(j=1; j<=n+1; j++) { A[k][j]=A[k][j]-szorzo*A[i][j]; } } } } A felső háromszög mátrixból kiszámítja a megoldásokat egy új tömbbe. X[n]=A[n][n+1]/A[n][n]; for(i=n-1; i>=1; i--) { sum=0; for(j=i+1; j<=n; j++) { sum=sum+A[i][j]*X[j]; } X[i]=(A[i][n+1]-sum)/A[i][i]; }
19
3.1. Gauss elimináció sor és oszlopcserével Újra megnézi az időt a program futása végén. end=omp_get_wtime(); Kiírja a megoldást és kiszámítja a futási időt. printf("Megoldas: \n"); for(i=1; i<=n; i++) { printf("x%d = %lf \n",i,X[i]); } t=end-start; printf("Futasi ido: %lf \n",t); Ha bekapcsoltuk a párhuzamos futást, akkor a program a következő pragmával fogja elvégezni a Gauss-eliminációt. #pragma omp parallel if(parhuzamos==1), private(j,k,szorzo), num_threads(4) { #pragma omp for schedule(static) for(k=1; k<=n; k++) { if(k>i) { szorzo=A[k][i]/A[i][i]; { for(j=1; j<=n+1; j++) { A[k][j]=A[k][j]-szorzo*A[i][j]; } } } } #pragma omp barrier } A párhuzamosítással 4 szál esetén, a futási idő nagyobb mátrixok esetén feleződik.
20
3.2. Gauss elimináció téglalap módszerrel
G−RC Eredmények 2.0 1.8 1.6
Idö (mp)
1.4 1.2 1.0 0.8 0.6 0.4 0.2 0.0 0
100 200 300 400 500 600 700 800 900 1000
Mátrix mérete Szekvenciális imp.
Párhuzamos imp.
3.2. Gauss elimináció téglalap módszerrel A program először bekéri, hogy szekvenciálisan vagy párhuzamosan szeretnénk futtatni a programot. Ezután a felhasználónak már nincs más dolga, a program kiszámítja az egyenletrendszerek megoldását további beavatkozás nélkül. A program több egyenletrendszer megoldását is kiszámítja, mindig egyre nagyobb mátrixokat használva, hogy jobban szemléltethessük a párhuzamosítással elérhető gyorsulást.
3.2.1. A program működése (G-Rectangle.c) A program egy ismeretlen kiszámításával kezdődik, majd ha megtalálta a megoldást akkor egy kétszer akkora mátrixszal kezd el dolgozni. Ez egészen addig tart, amíg el nem érünk az 1024 ismeretlenes mátrixhoz. while(n<=1024) { . . . n=n*2; } A kibővített együttható mátrix beolvasása automatikusan történik random számokat használva. printf("Ismeretlenek: %d \t",n); 21
3.2. Gauss elimináció téglalap módszerrel for(i=1; i<=n; i++) { for(j=1; j<=n+1; j++) { A[i][j]=5-rand()%11; } } Ha a mátrix mérete 4 vagy kisebb, akkor kiírja a kiinduló mátrixot. if(n<=4) { for(i=1; i<=n; i++) { for(j=1; j<=n+1; j++) { if(j
3.2. Gauss elimináció téglalap módszerrel } x++; } Oszlopcsere: Ha a főátlóbeli elem nulla, akkor oszlopcserével keres egy megfelelő elemet; ha nem talál, akkor továbbmegy a hibaüzenet részre. while(A[i][i]==0 && i
23
3.2. Gauss elimináció téglalap módszerrel A pivot elem oszlopában a pivot elem feletti elemeket végigosztja a pivot elem (−1)szeresével, a pivot elem alatti elemeket kinullázza. Ezután folytatódik a külső for ciklus. for(j=1; j<=n; j++) { if(i>j) { A[j][i]=A[j][i]/(-pivot); } if(i<j) { A[j][i]=0; } } Újra megnézi az időt a program futása végén. end=omp_get_wtime(); Kiírja a megoldást és kiszámítja a futási időt. printf("Megoldas: \n"); for(i=1; i<=n; i++) { printf("x%d = %lf \n",i,A[i][n+1]); } t=end-start; printf("Futasi ido: %lf \n",t); Ha bekapcsoltuk a párhuzamos futást, akkor a program a következő pragmákkal fogja elvégezni a téglalap módszert. Az omp for pragmák után található ciklusokat négy szálon hajtja végre. Az omp barrier pragmával a szálak bevárják egymást a for ciklusok végén. #pragma omp parallel if(parhuzamos==1), private(k,l), num_threads(4) { #pragma omp for schedule(static) for(k=1; k<=n; k++) { for(l=1; l<=n+1; l++) { if(k!=i && l!=i){ A[k][l]=A[k][l]-((A[i][l]*A[k][i])/pivot); } } } 24
3.2. Gauss elimináció téglalap módszerrel #pragma omp barrier #pragma omp for schedule(static) for(j=1; j<=n+1; j++) { A[i][j]=A[i][j]/pivot; } #pragma omp barrier #pragma omp for schedule(static) for(j=1; j<=n; j++) { if(i>j) { A[j][i]=A[j][i]/(-pivot); } if(i<j) { A[j][i]=0; } } #pragma omp barrier } A párhuzamosítással 4 szál esetén, a futási idő nagyobb mátrixok esetén több mint kétszer olyan gyors lesz mint szekvenciális esetben.
25
3.3. Gauss-Jordan elimináció sor és oszlopcserével
G−Rectangle Eredmények 6
Idö (mp)
5 4 3 2 1 0 0
100 200 300 400 500 600 700 800 900 1000
Mátrix mérete Szekvenciális imp.
Párhuzamos imp.
3.3. Gauss-Jordan elimináció sor és oszlopcserével A program először bekéri, hogy szekvenciálisan vagy párhuzamosan szeretnénk futtatni a programot. Ezután a felhasználónak már nincs más dolga, a program kiszámítja az egyenletrendszerek megoldását további beavatkozás nélkül. A program több egyenletrendszer megoldását is kiszámítja, mindig egyre nagyobb mátrixokat használva, hogy jobban szemléltethessük a párhuzamosítással elérhető gyorsulást.
3.3.1. A program működése (GJ-RC.c) A program egy ismeretlen kiszámításával kezdődik, majd ha megtalálta a megoldást akkor egy kétszer akkora mátrixszal kezd el dolgozni. Ez egészen addig tart, amíg el nem érünk az 1024 ismeretlenes mátrixhoz. while(n<=1024) { . . . n=n*2; } A kibővített együttható mátrix beolvasása automatikusan történik random számokat használva. printf("Ismeretlenek: %d \t",n); 26
3.3. Gauss-Jordan elimináció sor és oszlopcserével for(i=1; i<=n; i++) { for(j=1; j<=n+1; j++) { A[i][j]=5-rand()%11; } } Ha a mátrix mérete 4 vagy kisebb akkor kiírja a kiinduló mátrixot. if(n<=4) { for(i=1; i<=n; i++) { for(j=1; j<=n+1; j++) { if(j
3.3. Gauss-Jordan elimináció sor és oszlopcserével } x++; } Oszlopcsere: Ha a főátlóbeli elem nulla, akkor oszlopcserével keres egy megfelelő elemet; ha nem talál, akkor továbbmegy a hibaüzenet részre. while(A[i][i]==0 && ii) { szorzo=A[k][i]/A[i][i]; for(j=1; j<=n+1; j++) { A[k][j]=A[k][j]-szorzo*A[i][j]; } } } Az aktuális főátlóbeli elem feletti sorokat számítja ki a Gauss-Jordan módszerrel. Ha kiszámította akkor folytatódik a külső for ciklus.
28
3.3. Gauss-Jordan elimináció sor és oszlopcserével for(k=1; k<=n; k++) { if(ki) { szorzo=A[k][i]/A[i][i]; 29
3.4. Gauss-Jordan elimináció téglalap módszerrel for(j=1; j<=n+1; j++) { A[k][j]=A[k][j]-szorzo*A[i][j]; } } } #pragma omp barrier #pragma omp for schedule(static) for(k=1; k<=n; k++) { if(k
GJ−RC Eredmények 4.0 3.5
Idö (mp)
3.0 2.5 2.0 1.5 1.0 0.5 0.0 0
100 200 300 400 500 600 700 800 900 1000
Mátrix mérete Szekvenciális imp.
Párhuzamos imp.
30
3.4. Gauss-Jordan elimináció téglalap módszerrel
3.4. Gauss-Jordan elimináció téglalap módszerrel A program először bekéri, hogy szekvenciálisan vagy párhuzamosan szeretnénk futtatni a programot. Ezután a felhasználónak már nincs más dolga, a program kiszámítja az egyenletrendszerek megoldását további beavatkozás nélkül. A program több egyenletrendszer megoldását is kiszámítja, mindig egyre nagyobb mátrixokat használva, hogy jobban szemléltethessük a párhuzamosítással elérhető gyorsulást.
3.4.1. A program működése (GJ-Rectangle.c) A program egy ismeretlen kiszámításával kezdődik, majd ha megtalálta a megoldást, akkor egy kétszer akkora mátrixszal kezd el dolgozni. Ez egészen addig tart amíg el nem érünk az 1024 ismeretlenes mátrixhoz. while(n<=1024) { . . . n=n*2; } A kibővített együttható mátrix beolvasása automatikusan történik random számokat használva. printf("Ismeretlenek: %d \t",n); for(i=1; i<=n; i++) { for(j=1; j<=n+1; j++) { A[i][j]=5-rand()%11; } } Ha a mátrix mérete 4 vagy kisebb akkor kiírja a kiinduló mátrixot. if(n<=4) { for(i=1; i<=n; i++) { for(j=1; j<=n+1; j++) { if(j
3.4. Gauss-Jordan elimináció téglalap módszerrel } } } } A futási időt az OpenMP egyik függvényével méri. Mielőtt elkezdődne az egyenletrendszer megoldása megnézi az időt. start=omp_get_wtime(); Szekvenciális futás esetén a külső for ciklus végig megy a sorokon. Ha a ciklus véget ért az azt jelenti, hogy megvan a felső háromszög mátrix, amiből majd a megoldásokat fogja számolni. Először minden sorban megvizsgálja, hogy a főátlóbeli elem nulla-e. Sorcsere: Ha a főátlóbeli elem nulla, akkor sorcserével keres egy megfelelő elemet; ha nem talál, akkor továbbmegy az oszlopcsere részre. while(A[i][i]==0 && i
32
3.4. Gauss-Jordan elimináció téglalap módszerrel if(A[i][i]==0) { printf("A matrix determinansa 0, ezert nincs megoldas \n"); system("PAUSE"); return 0; } Ha a pivot elem (főátlóbeli elem) nem nulla, akkor először a téglalap módszerrel kiszámítja azokat az elemeket, amelyek nem a pivot elem sorában vagy oszlopában vannak. for(k=1; k<=n; k++) { for(l=1; l<=n+1; l++) { if(k!=i && l!=i){ A[k][l]=A[k][l]-((A[i][l]*A[k][i])/pivot); } } } A pivot elem sorának elemeit végigosztja a pivot elemmel. for(j=1; j<=n+1; j++) { A[i][j]=A[i][j]/pivot; } A pivot elem oszlopában a pivot elem kivételével minden elemet kinulláz. Ezután folytatódik a külső for ciklus. for(j=1; j<=n; j++) { if(i!=j) { A[j][i]=0; } } Újra megnézi az időt a program futása végén. end=omp_get_wtime(); Kiírja a megoldást és kiszámítja a futási időt. printf("Megoldas: \n"); for(i=1; i<=n; i++) { 33
3.4. Gauss-Jordan elimináció téglalap módszerrel printf("x%d = %lf \n",i,A[i][n+1]); } t=end-start; printf("Futasi ido: %lf \n",t); Ha bekapcsoltuk a párhuzamos futást, akkor a program a következő pragmákkal fogja elvégezni a téglalap módszert. Az omp for pragmák után található ciklusokat négy szálon hajtja végre. Az omp barrier pragmával a szálak bevárják egymást a for ciklusok végén. #pragma omp parallel if(parhuzamos==1), private(k,l), num_threads(4) { #pragma omp for schedule(static) for(k=1; k<=n; k++) { for(l=1; l<=n+1; l++) { if(k!=i && l!=i){ A[k][l]=A[k][l]-((A[i][l]*A[k][i])/pivot); } } } #pragma omp barrier #pragma omp for schedule(static) for(j=1; j<=n+1; j++) { A[i][j]=A[i][j]/pivot; } #pragma omp barrier #pragma omp for schedule(static) for(j=1; j<=n; j++) { if(i!=j) { A[j][i]=0; } } #pragma omp barrier } A párhuzamosítással 4 szál esetén, a futási idő nagyobb mátrixok esetén több mint kétszer olyan gyors lesz mint szekvenciális esetben.
34
3.5. Determináns meghatározása definíció szerint
GJ−Rectangle Eredmények 6
Idö (mp)
5 4 3 2 1 0 0
100 200 300 400 500 600 700 800 900 1000
Mátrix mérete Szekvenciális imp.
Párhuzamos imp.
3.5. Determináns meghatározása definíció szerint A program először bekéri, hogy szekvenciálisan vagy párhuzamosan szeretnénk futtatni a programot. Ezután a felhasználónak már nincs más dolga, a program kiszámítja a determinánst további beavatkozás nélkül. A program több mátrix determinánsát is kiszámítja, mindig egyre nagyobb mátrixokat használva, hogy jobban szemléltethessük a párhuzamosítással elérhető gyorsulást.
3.5.1. A program működése (D-D.c) A program egy nagyságú tömb determinánsának kiszámításával kezdődik, majd ha kiszámította akkor egy eggyel nagyobb mátrixszal kezd el dolgozni. Ez egészen addig tart amíg el nem érünk a 10 nagyságú mátrixhoz. while(n<=10) { . . . n=n++; } Az együttható mátrix beolvasása automatikusan történik random számokat használva. printf("Ismeretlenek: %d \t",n); for(i=1; i<=n; i++) 35
3.5. Determináns meghatározása definíció szerint { for(j=1; j<=n; j++) { A[i][j]=5-rand()%11; } } Ha a mátrix mérete 4 vagy annál kisebb, akkor kiírja a kiinduló mátrixot. if(n<=4) { for(i=1; i<=n; i++) { for(j=1; j<=n; j++) { printf("A[%d][%d]: %d \t",i,j,A[i][j]); } printf("\n"); } } A futási időt az OpenMP egyik függvényével méri. Mielőtt elkezdődne a determináns kiszámítása megnézi az időt. start=omp_get_wtime(); Feltölt egy tömböt a permutációkhoz. for(i=1; i<=n; i++) { B[i]=i; } Meghatározza a permutációk számát. for(i=1; i<=n; i++) { szam=szam*i; } A Ptolt() függvény elkezdi feltölteni azt a tömböt amiben a permutációkat fogjuk eltárolni. void Ptolt(int n) { int i;
36
3.5. Determináns meghatározása definíció szerint for(i=1; i<=n; i++) { P[i+(tolt*n)]=B[i]; } tolt++; } A kovPerm() függvény előállítja a lehetséges permutációkat. Egészen addig hívja meg újra és újra, amíg van még fel nem használt permutáció. A csere() függvény segít létrehozni az újabb permutációkat. Mielőtt újra meghívná a függvényt, átadja az új permutációt a Ptolt() függvénynek. int kovPerm(int n) { int i=n-1; int j=n; int x, y; while(B[i]>B[i+1]) { i--; } if(i==0) { return 0; } while(B[i]>B[j]) { j--; } csere(i,j); x = n; y = i+1; while(x>y) { csere(x,y); x--; y++; } Ptolt(n); return 1; }
37
3.5. Determináns meghatározása definíció szerint void csere(int i, int j) { int temp; temp=B[i]; B[i]=B[j]; B[j]=temp; } Ha megvan az összes lehetséges permutáció, akkor egy új tömbbe előállítja a definícióban szereplő képlethez az összeadandó elemeket. A kódban még 2 függvényt találunk, amelyek működése lentebb lesz ismertetve. for(i=1; i<=szam; i++) { X[i]=pow(-1,inverzio(n,(i-1)))*szorzas(n,(i-1)); } Az inverzio() függvény meghatározza, hogy az adott permutációban hány darab inverzió van. A visszatérési érték hatással lesz az adott összeadandó elem előjelére. int inverzio(int n, int z) { int x,y,inverziok=0; for(x=1; x<=n; x++) { for(y=x; yP[y+z*n+1]) { inverziok++; } } } return inverziok; } A szorzas() függvény meghatározza definícióban szereplő képlethez az aktuális összeadandó elemet. int szorzas(int n, int z) { int i,j,szorzat=1; for(i=1; i<=n; i++) 38
3.5. Determináns meghatározása definíció szerint { szorzat=szorzat*A[i][P[i+(n*z)]]; } return szorzat; } A következő for ciklus összeadja a megoldás tömbben lévő elemeket, ezáltal meghatározva a determinánst. Azért kellett egy külön tömb, hogy a párhuzamosításnál ne legyenek gondok. for(i=1; i<=szam; i++) { D=D+X[i]; } Újra megnézi az időt a program futása végén. end=omp_get_wtime(); Kiírja a determinánst és kiszámítja a futási időt. printf("Determinans: %d \t", D); t=end-start; printf("Futasi ido: %lf \n",t); Ha bekapcsoltuk a párhuzamos futást akkor a program a következő pragmával fogja elvégezni a determináns kiszámítását. Az omp for pragmák után található ciklusokat négy szálon hajtja végre. #pragma omp parallel if(parhuzamos==1), private(i), num_threads(4) { #pragma omp for schedule(static) for(i=1; i<=szam; i++) { X[i]=pow(-1,inverzio(n,(i-1)))*szorzas(n,(i-1)); } } A párhuzamosítással 4 szál esetén, a futási idő nagyobb mátrixok esetén kétszer olyan gyors lesz mint szekvenciális esetben.
39
3.6. Determináns meghatározása kifejtési tétellel
D−D Eredmények 2.2 2.0 1.8
Idö (mp)
1.6 1.4 1.2 1.0 0.8 0.6 0.4 0.2 0.0 2
4
6
8
10
Mátrix mérete Szekvenciális imp.
Párhuzamos imp.
3.6. Determináns meghatározása kifejtési tétellel A program először bekéri, hogy szekvenciálisan vagy párhuzamosan szeretnénk futtatni a programot. Ezután a felhasználónak már nincs más dolga, a program kiszámítja a determinánst további beavatkozás nélkül. A program több mátrix determinánsát is kiszámítja, mindig egyre nagyobb mátrixokat használva, hogy jobban szemléltethessük a párhuzamosítással elérhető gyorsulást.
3.6.1. A program működése (D-Laplace.c) A program egy 1 × 1-es tömb determinánsának kiszámításával kezdődik, majd ha kiszámította, akkor egy eggyel nagyobb méretű mátrixszal kezd el dolgozni. Ez egészen addig tart, amíg el nem érünk a 10 × 10-es mátrixhoz. while(n<=10) { . . . n=n++; } Az együttható mátrix beolvasása automatikusan történik random számokat használva. printf("Ismeretlenek: %d \t",n); for(i=1; i<=n; i++) 40
3.6. Determináns meghatározása kifejtési tétellel { for(j=1; j<=n; j++) { A[i][j]=5-rand()%11; } } Ha a mátrix mérete 4 vagy annál kisebb akkor kiírja a kiinduló mátrixot. if(n<=4) { for(i=1; i<=n; i++) { for(j=1; j<=n; j++) { printf("A[%d][%d]: %d \t",i,j,A[i][j]); } printf("\n"); } } A futási időt az OpenMP egyik függvényével méri. Mielőtt elkezdődne a determináns kiszámítása megnézi az időt. start=omp_get_wtime(); A tényleges számításokat a kifejt() függvény végzi el, ez egy rekurzív függvény ami a nagyobb mátrixokból csinál kisebbeket a kifejtési tétel segítségével. Ha elég kicsik a mátrixok akkor már könnyű kiszámolni a determinánst. Miután visszatért a függvény kiírja a megoldást. printf("Determinans: %d \n", kifejt(A,n)); A következő részben a kifejt() függvény lesz ismertetve. Ha a mátrix 1 × 1-es akkor egyszerűen visszaadja azt az egy elemet megoldásként. if(n==1) { D=A[1][1]; return D; } Ha a mátrix 2 × 2-es akkor ezzel az egyszerű képlettel számítja ki a determinánst. if(n==2) { D=0; 41
3.6. Determináns meghatározása kifejtési tétellel D=(A[1][1]*A[2][2])-(A[1][2]*A[2][1]); return D; } Ha a mátrix 3 × 3-as vagy nagyobb akkor elindul egy for ciklus ami végigmegy a tömb első során. A lentebb található kódrészlet az előbb említett külső for ciklusban található. Végigmegy a tömb elemein, és előállítja az n darab aldeterminánst. int r=1, c=1; for(x=1; x<=n; x++) { for(y=1; y<=n; y++) { if(x!=1 && y!=j) { B[r][c]=A[x][y]; c++; if(c>n-1) { r++; c=1; } } } } A következő kódrészlet még mindig a fentebb említett külső for ciklusban található. Meghatározza az aldeterminánsok előjelét. for(z=1, elojel=1; z<=(1+j); z++) { elojel=(-1)*elojel; } A következő kódrészlet még mindig a fentebb említett külső for ciklusban található. Egy tömbbe kiszámítja az aktuális előjeles aldeterminánst, valamint ha még túl nagyok a mátrixok, akkor itt hívja meg saját magát. Ha ez a rész is lefutott, akkor folytatódik a külső for ciklus. C[j]=elojel*kifejt(B,n-1); Miután véget ért a rekurzió egy külön tömbbe kiszámítja az összeadandó elemeket a kifejtési tétel szerint.
42
3.6. Determináns meghatározása kifejtési tétellel for(j=1; j<=n; j++) { X[j]=(A[1][j]*C[j]); } A következő for ciklus összeadja a megoldás tömbben lévő elemeket, ezáltal meghatározva a determinánst. Azért kellett egy külön tömb, hogy a párhuzamosításnál ne legyenek gondok. for(j=1; j<=n; j++) { D=D+X[j]; } Újra megnézi az időt a program futása végén. end=omp_get_wtime(); Kiszámítja a futási időt. t=end-start; printf("Futasi ido: %lf \n",t); Ha bekapcsoltuk a párhuzamos futást, akkor a program a következő pragmával fogja elvégezni a determináns kiszámítását. Az omp for pragmák után található ciklusokat négy szálon hajtja végre. #pragma omp parallel if(parhuzamos==1), private(j), num_threads(4) { #pragma omp for schedule(static) for(j=1; j<=n; j++) { X[j]=(A[1][j]*C[j]); } } Ennél a programnál párhuzamosítással nem érünk el gyorsabb futást, valószínűleg a program rekurzív működése miatt.
43
3.7. Grafikus felhasználói felület
D−Laplace Eredmények 1.4 1.2
Idö (mp)
1.0 0.8 0.6 0.4 0.2 0.0 2
4
6
8
10
Mátrix mérete Szekvenciális imp.
Párhuzamos imp.
3.7. Grafikus felhasználói felület A programot megnyitva egy kis ablakot kapunk, amelyben hat gomb áll a rendelkezésünkre. Mindegyik gomb elindít egyet a fentebb ismertetett programok közül.
3.7.1. A program működése (Gui.cpp) Meghatározza a gombok méretét és elhelyezi őket az ablakon. grc=CreateWindow("button", "G-RC", WS_VISIBLE|WS_CHILD,20,50,140,50,hwnd,(HMENU) 1,NULL,NULL); grectangle=CreateWindow("button", "G-Rectangle", WS_VISIBLE|WS_CHILD,160,50,140,50,hwnd,(HMENU) 2,NULL,NULL); gjrc=CreateWindow("button", "GJ-RC", WS_VISIBLE|WS_CHILD,20,100,140,50,hwnd,(HMENU) 3,NULL,NULL); gjrectangle=CreateWindow("button", "GJ-Rectangle", WS_VISIBLE|WS_CHILD,160,100,140,50,hwnd,(HMENU) 4,NULL,NULL);
44
3.7. Grafikus felhasználói felület dd=CreateWindow("button", "D-D", WS_VISIBLE|WS_CHILD,20,150,140,50,hwnd,(HMENU) 5,NULL,NULL); dlaplace=CreateWindow("button", "D-Laplace", WS_VISIBLE|WS_CHILD,160,150,140,50,hwnd,(HMENU) 6,NULL,NULL); Ha rákattintunk az egyik gombra akkor megkeresi és futtatja az adott programot. case 1: { std::string path = "start system(path.c_str()); break; } case 2: { std::string path = "start system(path.c_str()); break; } case 3: { std::string path = "start system(path.c_str()); break; } case 4: { std::string path = "start system(path.c_str()); break; } case 5: { std::string path = "start system(path.c_str()); break; } case 6: { std::string path = "start system(path.c_str()); break; }
"+ExePath()+"\\G-RC.exe";
"+ExePath()+"\\G-Rectangle.exe";
"+ExePath()+"\\GJ-RC.exe";
"+ExePath()+"\\GJ-Rectangle.exe";
"+ExePath()+"\\D-D.exe";
"+ExePath()+"\\D-Laplace.exe";
Az ExePath() függvény megkeresi a programok elérési újtát, így bárhonnan futtathat45
3.7. Grafikus felhasználói felület juk őket. std::string ExePath() { char buffer[MAX_PATH]; GetModuleFileName( NULL, buffer, MAX_PATH ); std::string::size_type pos=std::string(buffer).find_last_of("\\/"); return std::string( buffer ).substr( 0, pos); } Így néz ki a grafikus felhasználói felület, ha elindítjuk.
46
4. fejezet Összefoglalás Szakdolgozatomban az operációkutatás néhány alapvető módszerét vizsgáltam meg, valamint azok egyszerű párhuzamosítási technikák esetén történő, futásidőben megvalósuló változásait. A szakdolgozat készítés első félévében a téma elméleti részének kidolgozása volt a feladat. Ezek alapján kellett a későbbiekben megírni a programokat. Először a négy egyenletrendszer megoldásával kapcsolatos téma került kidolgozásra, utána a két determináns számító módszer. A második félévben a hat darab program elkészítése volt a cél, ezek mind el is készültek, mindegyik egy-egy operációkutatási módszer implementációja. A programok tartalmaznak egy szekvenciális és egy párhuzamos futási módot is, így könnyen összehasonlíthatjuk a futási időket. A hat programból öt esetén kiváló eredmények születtek a szekvenciális futáshoz képest amikor párhuzamosan futtattam őket. Mindegyiknél kétszer vagy még annál is jobb volt a futási sebesség. Ráadásul a tesztgép nem egy erős konfiguráció, erősebb gépeken, több szálat használva elérhető háromszoros vagy akár négyszeres gyorsulás is. Csak a kifejtési tételt szimuláló programnál nem sikerült gyorsulást elérni, ez a program rekurzív alapú működése miatt van, nem igazán lehetett a nagyobb számításokat párhuzamosítani, a kis számítást igénylő részeken pedig nem lehetett jelentős gyorsulást elérni, sőt a sok szál létrehozása miatt inkább romlott a futási idő. A szakdolgozatban említett előnyök mellett szerintem az OpenMP ideális választás lehet a programok párhuzamosításához. Bárki könnyedén elsajátíthatja a használatát és viszonylag kevés módosítással jelentős futási idő csökkenést érhetünk el.
47
Irodalomjegyzék [1] https://hu.wikipedia.org/wiki/Mátrix_(matematika) [2] https://hu.wikipedia.org/wiki/Lineáris_egyenletrendszer [3] https://hu.wikipedia.org/wiki/Determináns [4] https://hu.wikipedia.org/wiki/C_(programozási_nyelv) [5] http://nyelvek.inf.elte.hu/leirasok/FORTRAN/index.php?chapter=8 [6] https://hu.wikipedia.org/wiki/R_(programozási_nyelv) [7] http://r-projekt.hu
48
Adathordozó használati útmutató A CD-t megnyitva három mappát talál a felhasználó. A Dolgozat mappában található egy mappa és három fájl. Ezek közül a szakd_TTA.pdf maga a teljes szakdolgozat pdf formátumban. A másik kettő a feladat kiírását valamint az összefoglalást tartalmazza. A szakd_TTA mappában találhatóak a szakdolgozat forrásfájljai. A szakdolgozat Latex-ben íródott, a szakd_TTA.tex fájl az ami összefogja az egészet egy dokumentummá. Ha a felhasználó le akarja fordítani a forrás dokumentumot akkor ezt a fájlt kell átadni a fordítónak. Az itt található többi mappában találhatóak a szakdolgozat egyes részei. A forrásfájlok a Forraskodok mappában találhatóak. A felhasználó itt találja közvetlenül a grafikus felület (Gui.cpp) forráskódját. Ezen kívül van még hat almappa a hat elkészült programhoz. Mindegyik mappában megtalálja az adott program forráskódját, valamint a tesztgépen készült futási eredményeket és az ezekből készült grafikonokat előállító R forrásfájlokat. A Programok mappában találja a felhasználó a lefordított, futásra kész programokat. Jómagam Windows párti vagyok, ezért a programok mind Windows-os használatra lettek fordítva. A programok külön-külön is futtathatóak, de egy grafikus felület (Gui.exe) is rendelkezésre áll, amely összefogja őket. Bárhonnan futtathatóak, egyetlen kikötés, ha a felhasználó a grafikus felülettel szeretné futtatni őket, akkor olyan helyre tegye, ahol az elérési címben nincs szóköz.
49
