Többmagos processzorok programozhatósága Vágó Gergely. Programtervezı Matematikus szak nappali tagozat. Témavezetı: Dr

Eötvös Loránd Tudományegyetem Informatikai Kar Programozási Nyelvek és Fordítóprogramok

Többmagos processzorok programozhatósága Vágó Gergely Programtervezı Matematikus szak nappali tagozat Témavezetı: Dr. Horváth Zoltán

2009/2010 ıszi félév Budapest, 2009.01.12.

A Diplomamunka önálló szellemi munkám eredménye, mely korábban sehol nem került publikálásra

Többmagos processzorok programozhatósága

Vágó Gergely

TARTALOMJEGYZÉK 1. Bevezetés ...............................................................................................................................6 1.1 A dolgozat témája ..........................................................................................................6 2. Áttekintés ..............................................................................................................................8 2.1 Alapfogalmak - architektúrák ........................................................................................8 2.1.1 A számítógép teljesítményét meghatározó tényezık...............................................8 2.1.2 A számítógépek teljesítményének mérése ...............................................................8 2.1.3 A számítógéprendszerek osztályozása.....................................................................9 2.1.4 A számítógépek csoportosítása a feldolgozott utasítás- és adatfolyamok száma szerint.........................................................................................................9 2.1.5 CISC és RISC architektúrájú processzorok ...........................................................11 2.2 Az újabb lépcsıfok – többmagos processzorok...........................................................13 2.2.1 A többmagos processzorok megjelenése ...............................................................13 2.2.2 Multi- architektúrák ...............................................................................................15 2.2.3 A többmagos processzorok felépítése....................................................................19 2.2.4 További többmagos processzorok és rendszerek...................................................20 2.2.4.1 PowerPc (XBox 360) .......................................................................................20 2.2.4.2.Cell (Playstation 3) ..........................................................................................21 2.2.4.3 Cuda .................................................................................................................21 2.2.4.4 Larrabee ...........................................................................................................22 2.2.4.5 Szuperszámítógépek ........................................................................................23 2.3 Párhuzamosság.............................................................................................................23 2.3.1 Alapfogalmak.........................................................................................................23 2.3.2 Amdahl törvénye....................................................................................................25 2.4 Párhuzamos programozás alapjai.................................................................................28 2.4.1 Párhuzamos programozás szabályai többmagos rendszerek esetén ......................28 2.4.2 Párhuzamos programozás nehézségei (munkamegosztás, holtidı, kritikus szakasz, kölcsönös kizárás) ..........................29 2.4.3 További nehézségek (versenyhelyzet, holtpont) .....................................................................................32 2.4.4 Párhuzamos programozási modellek .....................................................................33 2.4.5 Párhuzamos programozási paradigmák .................................................................35

-3-


Vágó Gergely

3. Nyelvi eszközök ..................................................................................................................38 3.1 Osztályozási szempontok.............................................................................................38 3.1.1 Általános nyelvi tulajdonságok..............................................................................38 3.1.2 Párhuzamos nyelvi tulajdonságok .........................................................................40 3.2 C++: Pthreads ..............................................................................................................41 3.2.1 Ismertetés ...............................................................................................................41 3.2.2 Összefoglalás .........................................................................................................44 3.3 C++: Boost...................................................................................................................45 3.3.1 Ismertetés ...............................................................................................................45 3.3.2 Összefoglalás .........................................................................................................47 3.4 C++: RAII....................................................................................................................48 3.4.1 Ismertetés ...............................................................................................................48 3.4.2 Összefoglalás .........................................................................................................50 3.5 OpenMP .......................................................................................................................51 3.5.1 Ismertetés ...............................................................................................................51 3.5.2 Összefoglalás .........................................................................................................55 3.6 C#: .NET framework 3.5 .............................................................................................56 3.6.1 Ismertetés ...............................................................................................................56 3.6.1.1 MatrixMultiplication........................................................................................56 3.6.1.2 QuickSort .........................................................................................................62 3.6.2 Összefoglalás .........................................................................................................65 3.7 Haskell .........................................................................................................................66 3.7.1 Ismertetés ...............................................................................................................66 3.7.1.1 Implicit párhuzamosság ...................................................................................68 3.7.1.2 Explicit párhuzamosság (MVars, STM) ..........................................................73 3.7.2 Összefoglalás .........................................................................................................78 3.8 Felmerülı kérdések......................................................................................................80 3.8.1 Közös, vagy saját? .................................................................................................80 3.8.2 Mi legyen a célváltozó? .........................................................................................81 3.8.3 Lock technikák.......................................................................................................82 3.9 A jövı – Stream programning .....................................................................................85 3.9.1 GPU .......................................................................................................................85 3.9.2 CUDA ....................................................................................................................85 3.9.3 OpenCL..................................................................................................................88 -4-


Vágó Gergely

4 Tervezés ...............................................................................................................................89 4.1 Hogyan és hol párhuzamosítsunk .............................................................................89 4.2 Egy tervezési módszertan .........................................................................................90 4.3 Elıre tervezés............................................................................................................92 5. Záró gondolatok.................................................................................................................93 5.1 A jövı ..........................................................................................................................93 5.1.1 A többmagos processzorok jövıje.........................................................................93 5.2 Összegzés.....................................................................................................................94 6. Irodalomjegyzék.................................................................................................................96 7. Köszönetnyilvánítás ...........................................................................................................99

-5-


1. 1.1

Vágó Gergely

Bevezetés

A dolgozat témája

A dolgozat témája a több magon futó párhuzamos programok írását támogató nyelvi eszközök bemutató összehasonlítása. Ezek az eszközök fıleg könyvtári kiegészítések - a világon jelenlévı számtalan párhuzamosságot támogató nyelv közül- konkrét, divatos programozási nyelvekhez (C, C++, C#, Haskell). A diplomamunka egy rövid történelmi áttekintéssel, alapfogalmak ismertetésével kezdıdik (2.1 Alapfogalmak - architektúrák), mely során megismerhetjük a késıbbiek könnyebb megértése érdekében a szükséges alapfogalmakat, háttérismereteket, mint például a teljesítményt meghatározó tényezıket, számítógéprendszerek osztályozását, az egyes architektúrák jellemzıit (SISD, SIMD, MISD, MIMD, CISC, RISC). Ezen ismeretek megszerzésének következtében lesz kellı rálátásunk, hogy megértsük a Moore törvény gyakorlatban tapasztalat hozadékát, hogy a processzor órajelének szimplán növelése már nem feltétlenül járható út: túl nagy az energia felvétel, a melegedés, s egyre jobban nınek a költségek. Röviden bemutatásra kerül a (többmagos-) CPU felépítése, annak legfontosabb jellemzıi (2.2 Az újabb lépcsıfok – többmagos processzorok).A processzorok megtöbbszörözése – átmeneti, drága megoldás -, valamint a processzorokban lévı magok számának duplikálása – többlet-tranzisztorok hasznosítása. A bemutatásra kerülı multi- architektúrák, a többmagos processzorok felépítésének, fejlıdésének, illetve az egyes technológiai változásoknak ismertetése mind-mind azt a célt szolgálják, hogy lássuk, hova jutottunk, hol tartunk most, s hogy milyen rendszerek, hardverinfrastrukturális eszközök állnak rendelkezésünkre, amikor a mai szoftver-fejlesztési versenyben helyt szeretnénk állni, immáron párhuzamos mőködésre is felkészített programjainkkal. Külön érdekesség, ugyanakkor hasznos pontja a dolgozatnak, hogy megismerhetünk további többmagos rendszereket, technológiákat: játékkonzolokban, illetve szuperszámítógépekben használt multi-core-okat. Ezek néhánya meghatározó sikert élt el, s technológiájukat még mind a mai napig használják – gondoljunk például csak a CUDA -ra. Következı pontja a dolgozatnak (2.3 Párhuzamosság) – elsısorban még mindig az elızetes ismeretek tovább bıvítése érdekében - a párhuzamosság alapfogalmainak

-6-


Vágó Gergely

felsorakoztatása, a szál(thread) fogalmának bevezetése és végül, de nem utolsó sorban Amdahl törvényének megfogalmazása. Ez utóbbi a párhuzamos programozás alap axiómájának is tekinthetı, a képlet eredményül szolgál a párhuzamos munkavégzık (magok) és a feladatok számának ismeretében a várható teljesítmény- és sebességnövekedésre. Fontos, hogy képesek legyünk „párhuzamosan gondolkodni”, tisztában legyünk a programozási módszer szabályaival, nehézségeivel, a felmerülı kérdésekkel, hibaforrásokkal(versenyhelyzet, holtpont, szinkronizáció, stb.). Ezzel foglalkozik egy teljes (2.4 Párhuzamos programozás alapjai) fejezet. Csak ezek után térhetünk rá a párhuzamos programozásra (3. Nyelvi eszközök), az egyes nyelvek és azok (könyvtári-) kiegészítései által biztosított, illetve kínált eszközök felhasználásával. Minden fejlesztésnek és fejlesztıi környezetnek megvannak a sajátosságai, követelményei, a rendelkezésre álló erıforrásai, így a megválaszolásra váró felmerülı kérdései is. Ilyen kérdés például egy változó láthatóságának és hozzáférhetıségének eldöntése. Egységes osztályozási szempontokat kialakítva (3.1 Osztályozási szempontok) a fejezetek végén minden egyes eszközön végighaladunk, s annak

ismertetése,

a

szerzett

tapasztalatok

alapján

kiértékeljük

az

egyes

tulajdonságokat. Két szempont szerint közelítjük meg az összegzéseket: az általános szoftver minıségi osztályozás alapján (hatékonyság, megbízhatóság, karbantarthatóság, stb.), valamint egy párhuzamos programozásra jellemzı nézıpontok alapján (párhuzamosság szintje, típusa, megvalósítása, stb.). E fejezet keretein belül betekintést nyerhetünk egy, a jövıben nagy valószínőséggel meghatározó programozási technológia, eszköz kínálta lehetıségekbe. Ez pedig nem más, mint a grafikus kártyák programozása, a CPU és GPU közti megfelelı kommunikáció és munkamegosztás biztosításával, felügyelésével (CUDA, OpenCL). Végül, a párhuzamos programok tervezésével kapcsolatos kérdéseket feszegetünk, módszereket ismertetünk (4. Tervezés), hiszen minden jól mőködı alkalmazás alapja egy jó, megalapozott terv, egy helyes specifikáció, valamint logikusan felbontott önálló modulok megkeresése és azok szinkronizációja. Gondolatébresztı gyanánt (5. Záró gondolatok) pedig a többmagos processzorok jövıjét latolgathatjuk, hiszen számítógépünk gyorsaságának szők keresztmetszete nem csupán a vezérlı egység(ek) gyorsasága, hanem az azt kiszolgáló memória órajele is: Vajon több, mint 16 mag egy processzorban felesleges? Végül egy összegzés zárja a diplomamunkát.

-7-


2. 2.1

Vágó Gergely

Áttekintés

Alapfogalmak - architektúrák

Számítógéprendszer architektúrának a számítógép funkcionális felépítését, a részegységek kommunikációs kapcsolatait, valamint a rendszer specifikációjának együttesét nevezzük. Ebbıl következik, hogy egy számítógép architektúrát a részegységek és funkcióik, valamint ezek kapcsolatát meghatározó interfészprotokollok együttes leírásával jellemezhetünk. Korszerő értelmezés szerint az architektúra fogalma három szempontot fog össze: •

a számítási modellt

•

az értelmezés szintjét (a hardver hierarchikus leírásának megfelelıen)

•

a leírás irányultságát (logikai és fizikai architektúra)

2.1.1

A számítógép teljesítményét meghatározó tényezık

[1] [2]

A számítógéprendszerek teljesítményét egy adott feladat elvégzéséhez szükséges idıvel hasonlíthatjuk össze. Ha egy feladat végrehajtási idejét V-el jelöljük, akkor •

V = N * T * M, ahol

•

N = az egy utasításra esı átlagos ciklusszám

•

T = az egy ciklushoz szükséges idı

•

M = a feladat-végrehajtáshoz szükséges utasítás szám

Ezt figyelembe véve egy számítógéprendszer teljesítményét a következı módon növelhetjük: M csökkentése : Hatékony programozással és fordítóprogrammal T csökkentése : Magasabb órajel frekvenciával, ez áramköri fejlesztést jelent N csökkentése : Párhuzamosítás az utasítás-végrehajtásban, azaz az architektúra fejlesztése 2.1.2

A számítógépek teljesítményének mérése

[1] [2]

A számítógépek teljesítményének mértékegysége az idıegység alatt végrehajtott utasítások átlagos száma, azaz a millió mővelet/másodperc, rövidítve MIPS (Million Instructions per Second). (Ezt egyes esetekben MOPS = Million Operation per Second mutatóval jelölik, melynek értelmezése azonos a MIPS-el.) Egy másik hasonló

-8-


Vágó Gergely

mértékegység a MFLOPS, azaz Millions of Floating Point Operations per Second, ami a másodpercenként végrehajtott lebegıpontos utasítások számát jelenti. A számítógéprendszerek teljesítményérıl összetettebb képet adnak a speciális teljesítménymérı programokkal elıállított mutatók a „Benchmark”-ok. 2.1.3

A számítógéprendszerek osztályozása

[1] [2]

A számítógéprendszereket különbözı szempontok szerint csoportosíthatjuk. Ezek közül a legfontosabbak: •

Teljesítmény szerint: mikro- (kis-), közép- és nagyszámítógépek

•

Az utasítás- és adatfolyamok száma szerint: SISD (egy utasítás-, egy adatfolyam), SIMD (egy utasítás-, több adatfolyam), MISD (több utasítás-, egy adatfolyam) és MIMD (több utasítás-, több adatfolyam) gépek

•

Az utasításkészlet szerint: komplex és egyszerősített utasításkészlető gépek (CISC és RISC)

•

A számítógép mőködési elve szerint: Neumann és nem Neumann elvő architektúrák.

A következı fejezetekben csak a diplomamunka témájához kapcsolódó osztályozási formákkal foglalkozunk, tehát a fenti csoportosításból az elsı és utolsó szemponttal nem. 2.1.4

A számítógépek csoportosítása a feldolgozott utasítás- és adatfolyamok száma szerint

[1] [2]

Az utasítás- és adatfolyam definíciója: •

Utasításfolyam: az utasítások egymás utáni sorozata, amelyeket egy program lefuttatása során hajt végre a számítógép. (Az utasításfolyam nem azonos a programutasítások sorozatával. Például a ciklusok utasításai a programban csak egyszer szerepelnek, az utasításfolyamban viszont annyiszor ahányszor azokat a számítógép végrehajtja - ciklusváltozó.)

•

Adatfolyam: Az utasításfolyam utasításai mindig meghatározott adatokra hivatkoznak, amelyekkel a mőveleteket el kell végezni. Ezek egymásutániságát, amilyen sorrendben rendelkezésre kell állniuk, nevezzük adatfolyamnak.

Ez az osztályozás azért hasznos, mert segítségével könnyebb megérteni a bonyolultabb számítógép architektúrák (SISD, SIMD, MISD, MIMD) mőködésének lényegét.

-9-


Vágó Gergely

SISD architektúrájú számítógépek A

SISD

(Single

Instruction Stream Single Data

Stream)

típusú

számítógép egyetlen utasításfolyammal egyetlen adatfolyamot dolgoz fel. Példák SISD architektúrájú gépekre: •

A Neumann elvő gépek

•

A PC-k központi feldolgozó egysége (CPU = Central Processing Unit), azaz processzora, a Pentium MMX-ig.

SIMD architektúrájú számítógépek A

SIMD

(Single

Instruction Multiple

Stream Data

Stream)

típusú számítógép egyetlen utasításfolyammal többszörös

adatfolyamot

dolgoz fel. Ezek a számítógépek több párhuzamos, egyidejő mőködésre képes mőveletvégzı egységet (ALU) tartalmaznak. Vektormőveleteket képesek végrehajtani, gépi utasítás szinten (például a Pentium III processzor 3D grafikus utasításai). Két alaptípusuk van: •

a közös tárolójú (Shared Memory) gépek, és

•

az osztott tárolóval (Distributed Memory) rendelkezı gépek.

MISD architektúrájú számítógépek A

MISD

(Multiple

Instruction Stream Single Data

Stream)

számítógép

típusú több

utasításfolyammal egyetlen adatfolyamot dolgoz fel. A gyakorlatban ilyen gépek nem léteznek. Egyes szakértık ide sorolják a pipeline (futószalag) szervezéső processzorokat, illetve a hibatőrı architektúrákat, melyek

- 10 -


Vágó Gergely

többszörösen végzik el a mőveleteket azonos adatokon és az eredményt hibavédelmi célból összehasonlítják. MIMD architektúrájú számítógépek A

MIMD

(Multiple

Instruction

Stream

Multiple Data Stream) számítógéprendszerek több

utasításfolyammal

több

adatfolyamot

dolgoznak fel. Ebbe a kategóriába tartoznak a multiprocesszoros számítógépek (több vezérlıegységgel) és a nem a hagyományos, soros utasítás-végrehajtás elvén mőködı számítógépek (adatvezérelt számítógépek, neurális hálók). 2.1.5

CISC és RISC architektúrájú processzorok

[1] [2]

A Neumann elvő architektúrák lényegi továbbfejlesztését a teljesítménynövelés piaci igénye kényszeríttette ki. A teljesítménynövelésnek alapvetıen két módszere van: nem strukturális és strukturális gyorsítás. Nem strukturális gyorsítás lehetıségei: •

Az órajel frekvenciájának növelése

•

A program optimalizált fordítása (ennek különösen a RISC processzoroknál van jelentısége).

Strukturális gyorsítás formái: •

•

Párhuzamosítás a CPU-n belül o

vektorszámítógépek

o

pipeline feldolgozás

o

szuperskalár processzorok

o

társprocesszorok

o

multiprocesszoros architektúrák (több „hagyományos” CPU-val és ALU-val)

o

többmagos processzorok

Nem hagyományos elven mőködı számítógépek o

neurális hálók

- 11 -


Vágó Gergely

CISC processzorok A szoftverfejlesztık igényeinek megfelelıen kezdetben a gyártók állandóan bıvítették a számítógépek utasításkészletét, amely egyre több és bonyolultabb utasítást tartalmazott. Ezek hardver megvalósítását mikro-programvezérléssel kellett megoldani, azaz egy gépi utasítás végrehajtását több elemi lépésre felbontották, s az ezeket végrehajtó mikro-utasításokat egy, csak olvasható memóriában (ROM = Read Only Memory) tárolták. Így alakultak ki a komplex utasításkészlető számítógépek (CISC = Complex Instruction Set Computer). A CISC processzorok tehát: •

nagy számú utasítást tartalmazó utasításkészlettel rendelkeznek

•

az utasítások szerkezete bonyolult

•

többfajta memóriacímzési módot tesznek lehetıvé

•

az utasítás-végrehajtás mikro-programvezérelt.

Ilyen típusú processzorokra példa a mikroszámítógépek körébıl a korai Pentium és a vele kompatibilis processzorcsalád. A mai modern CISC processzorok, mint a Pentiumok, gyors RISC magokat használnak egy értelmezıvel, mely a mag és a mőveletek közti kommunikációért felel. RISC processzorok A mikro-programvezérelt utasítás-végrehajtás komoly korlátává vált a számítógépteljesítmény növelésének. Ezért olyan architektúrát terveztek, melynél csak a gyakori, „egyszerő” utasítások szerepeltek az utasítás-készletben. Ezzel lehetıvé vált a mikroprogramozás kiküszöbölése, azaz magas szintő programnyelvrıl fordítás lényegében a korábbi mikro-utasítások szintjén történik. Így jöttek létre a RISC processzorok, azaz redukált utasításkészlető számítógépek (Reduced Instruction Set Computer). A RISC processzorok: •

utasításkészlete csökkentett, egyszerősített

•

a memória-hozzáférés csak két utasítással: memóriából való adatbetöltés (LOAD) és memóriába való adatírás (STORE) történhet

•

a mőveleti vezérlés huzalozott (azaz beépített áramkörökkel végrehajtott) vagy horizontális (egyszerősített) mikro-programvezérelt.

A RISC processzorokra példák a SPARC, MIPS, POWER PC különbözı változatai. (Ezeket hétköznapi szóhasználattal sokszor UNIX gépeknek is nevezik.) - 12 -


2.2

Vágó Gergely

Az újabb lépcsıfok – többmagos processzorok

Elérkeztünk a processzor-architektúrák fejlıdésének egy újabb lépcsıfokához, a többmagos processzorokig. A következı fejezetekben megismerjük felépítésüket, mőködésüket, valamint megjelenésük és szükségességük okait. 2.2.1

A többmagos processzorok megjelenése

[2] [8]

A problémakör megvilágítása érdekében kicsit mélyedjünk el abban, hogyan is zajlott le az elmúlt években a processzorok fejlıdése. Adott egyrészt Moore törvénye, ami a tranzisztorok számának növekedését írja le: Moore állítása szerint minden második évben megduplázódik a lapkákra integrált tranzisztorok száma. Vajon ez azt jelenti-e, hogy a processzorok abszolút teljesítménye is hasonló arányban növekszik? Sajnos nem. A processzorok teljesítményének növekedése érdekében két fı irányt követtek a tervezık, melyek kivitelezéséhez folyamatosan szükség volt a tranzisztorok számának növelésére: az egyik sebességnövelı lehetıség a frekvencia emelése volt, a másik pedig a processzormag belsı mőködésének optimalizálása. A 8088-as processzoroktól indulva egészen a Pentium Pro processzorok megjelenéséig elmondható volt, hogy mind a frekvencia növelésébıl, mind a belsı optimalizációból származó teljesítménynövekedés közel tízszeresére nıtt tíz év alatt, ezzel együtt mintegy százszorosára nıtt tízévente a processzorok abszolút sebessége is. Azóta azonban szinte csak az órajel növekedett, ami a trendet tekintve tíz év alatt százszoros frekvencianövekedést jelentett volna, ugyanakkor a magok belsı felépítése csak kicsi pozitív változásokat eredményezett. 2004 tájékán már erısen érezhetı volt, hogy a hardvergyártók számára szinte lehetetlen kihívást jelent a 3,6–4 gigahertzes határ átlépése. Az Intel Pentium 4 alapjait alkotó NetBurst microarchitektúra, ami eredetileg 10 gigahertzig (késıbb ezt a prognózist 5 gigahertzre módosította az Intel) képes lett volna skálázódni, technológiai korlátokba ütközött – túlságosan megnıtt ugyanis a frekvencia növelésével a processzor áramfelvétele és a hıkibocsátása is az egekbe szökött. Hasonló problémával találkoztak az AMD mérnökei is. [8] Az

alábbi

táblázat

szemlélteti

a

processzorok

sebességi

tranzisztorszámának arányait (gondoljunk csak Moore törvényére):

- 13 -

fejlıdésének

és


Vágó Gergely

80486-ig CISC, Pentiumtól felfelé RISC

Az Intel és az AMD szinte egyszerre jutott arra az elhatározásra, hogy ha nem lehet tovább növelni az órajelet, meg kell duplázni a magok, a központi feldolgozóegységek számát. A fejlesztések szinte fej-fej mellett haladtak, végül az AMD lett a befutó: 2005 tavaszán megjelent a pc-s világ elsı kétmagos processzora, a szerverekbe szánt Opteron hónapokkal megelızte az Intel hasonló megoldását. Szemléletesen összefoglalva a multiprocesszorok bevezetése melletti érveket: Egymagos processzorok: Növekvı tranzisztorszám ↔ csökkenı teljesítmény hozadék

↕ Moore szabály: Tranzisztorszám kb. 24 –havonta duplázódik Megoldás: A többlet-tranzisztor hasznosítása: többmagos processzorként Az újdonságok jellemzıen a komolyabb alkalmazások alatt jelentettek elırelépést: tömörítés, renderelés, képszerkesztésbéli munkák közben azonos órajelen akár 60 százalékkal gyorsabbak a kétmagos processzorok egymagos társaikhoz képest, ami elképesztı növekedést jelent: a 3,46 gigaherzes Pentium D esetenként olyan teljesítményt nyújt, mint amit a soha el nem készült 5,5 gigahertzes Pentium 4-es nyújthatott volna. Az AMD kétmagos processzorai egymagos elıdeikhez hasonlóan még erıteljesebbek, mint az Intel chipjei. A csúcsmodell, az Athlon FX–60

- 14 -


Vágó Gergely

teljesítménye a szintén soha el nem készült 6 gigahertzes Pentium 4-esével lenne egyenértékő. A két magból azonban csak olyan alkalmazások tudtak profitálni, amelyeket arra elızıleg felkészítettek (pl. szerverszoftverek). Ha a szoftvert nem úgy írták meg, hogy a párhuzamos adatfeldolgozás meggyorsítsa a folyamatot, akkor a két magból csak az egyik dolgozik, a másik pihen. A kétmagos megoldás azonban nem az elsı próbálkozás a párhuzamos adatfeldolgozásra. Korábban ezt kettı (vagy több) processzorral oldották meg, de két processzort csak a professzionális alaplapok tudtak fogadni. Mivel a kétmagos chipek valójában kétprocesszoros rendszerek – csak ezeket nem külön, hanem egyetlen lapra építve tuszkoljuk a számítógépbe –, a komoly alkalmazások egybıl kihasználták az újítás elınyeit. 2.2.2 A

Multi- architektúrák szál

(thread)

egy

alapvetı

[6] [35] fogalma

a

CPU

erıforrás-kiaknázásának,

programozásának. Röviden, a szálak felelısek programjaink megfelelı futásaiért, míg az operációs rendszer, a kernel elosztja a szőkös erıforrásokat a futó szálak között. Ilyen erıforrás többek között maga a processzor is: magjának száma és sebessége is. Mint az elızı fejezetben már szó esett róla, egy korábbi megoldása a szál-szintő párhuzamos adatfeldolgozásának a fizikai processzorok számának növelése volt. Multiprocesszoros rendszerek valós párhuzamos mőködést eredményeztek. Több szál, illetve folyamat volt képes párhuzamosan futni az egyes processzorokon (1 processzor = 1 folyamat/szál). Ennek nagy ára a jelentısen megnövekedett költség volt. Egymagos processzoroknál is létezı technológia volt már az úgynevezett logikai processzor biztosítása, mely lehetıvé tette, hogy egy magon több thread fusson –közelegy idıben. Ezt a módszert simultaneous multi-threading –nek, vagy

SMT-nek

nevezik. Az Intel saját SMT implementációját Hyper-Threading Technology –nak, vagy HT Technology –nak keresztelte. Ez elrejti a futó szoftver elıl a valódi processzort, s összetett, több logikai processzorként láttatja azt. Ennek következtében az operációs rendszer és a különféle többszálú alkalmazások, úgy érzékelik, mintha multiprocesszor rendszeren futnának. Ez azt jelenti, hogy az egyszerre futó szálakat beoszthatjuk egy menetrendszerő sorrendbe, így osztva ki nekik a véges számú erıforrásokat (szinkronizáció). Ennek pontos mőködéséért felelısek a korábban említett mikroarchitektúrák. Fontos kiemelni, hogy ez lényegében nem valódi párhuzamosság.

- 15 -


Vágó Gergely

Az különbözı processzor architekturák összefoglalása a következı ábrán látható:

Egyszerő összehasonlítása a Single-core, a Multi-processor és a Multi-Core architekturáknak

A következı logikai lépcsı a multi-core (többmagos) processzorok. Csak a végrehajtó magok számát növelték a processzorokban, melyek mindegyikének megvan a saját végrehajtó és architekturális erıforrása. Gyártástól függıen rendelkezhetnek további cache-tárakkal. Az egyes magokat kombinálják az SMT technológiával is, hatékonyan növelve ez által a logikai processzorok számát: minden végrehajtó maghoz kéttı jár. A Multi-Core architektúra különbsége a Hyper-Threading Technology-tól

[35]

A HT Technology-val a processzor egy része megosztásra került a szálak között, míg más része duplikálva van jelen köztük. Az egyik legfontosabb osztott erıforrás az aktuális végrehajtási sor. Ez egyidıben fut minden szálon, végrehajtva annak azon utasításait egy erıforráson, melyet nem használ másik szál. Amikor minden szál fut, a HT Technology összefésüli az egyes instrukciókat a végrehajtási pipeline-ban. Mely utasítások, s mikor illeszthetıek be, az teljes mértékben azon múlik, hogy melyik erıforrás hajtható végre a processzor adott (végrehajtási-) idejében. Sıt, ha egy szál

- 16 -


Vágó Gergely

elfoglalt egy nagyobb adat olvasásával a merevlemezrıl, vagy a felhasználó egy gombnyomására vár, a többi szál átveszi a processzor teljes erıforrását – anélkül, hogy az operációs rendszer taszkot váltana-, mindaddig, míg az elsı szál kész visszatérni a folyamatához. Ez alapján minden szál megkapja a számára maximálisan hozzáférhetı erıforrást, míg a processzor annyira elfoglalt, amennyire csak lehetséges. HT Technology-ban alapvetıen egyetlen végrehajtási mag több fonál között oszlik meg. Ezért a szál-végrehajtás nem párhuzamos. A végrehajtás eredménye pedig nagyban az alkalmazás és a hardverplatform alapján alakul. A HT Technology-val, bizonyos alkalmazások esetén elıfordulhat, hogy átlagban 30-százalékos növekedést érünk el a processzor teljesítményében. Más szóval, egyes esetekben a processzor 1.3-al gyorsabban hajtja végre az utasításokat, ha azok egy szálon futnak. Hogy a végrehajtásban valódi javulást lássunk, az alkalmazásoknak megfelelı módon és arányban kell használniuk a szál-programozott modell és a Hyper-Threading Technology képességeit. A HT Technology végrehajtása függ, hogy mennyi latency hiding (várakozási idı elrejtése) fordul elı az alkalmazásban. Néhány applikációban a fejlesztık minimalizálják, vagy ténylegesen kiküszöbölik a memória lappangási idejét, a cache optimalizálásán keresztül. Ebben az esetben a HT Technology optimalizációja nem nyújt semmilyen teljesítménybeli javulást. Másfelıl a több magból álló processzorok kettı, vagy több független végrehajtási magot ágyaznak be egyetlen processzor-csomagba. Többszörös végrehajtási magok esetén minden utasítás-sornak, vagy szálnak van egy saját hardveres végrehajtási környezete, mely lehetıvé teszi mindegyik szálnak, hogy valóban párhuzamos módon fusson. A HT Technology inkább csak egy lehetıség, melynek segítségével a programozó kihasználhatja a tétlen CPU erıforrásait több feladat végrehajtására. Amikor multi-core technológiával kombináljuk, a HT Technology jelentıs optimalizálást eredményezhet a rendszer teljesítményének nagymértékő növekedésében. Többszálúság Single-Core-on és Multi-Core platformon

[35]

Az egy eljárásban lévı többszálúság fogalma évtizedek óta létezik: a legtöbb modern alkalmazás használ szálakat. Vannak bizonyos tényezık, amikkel kapcsolatban körültekintınek kell lennünk, ha többmagos processzorra írunk alkalmazásokat: Többmagos architectúra esetén optimális alkalmazási teljesítmény érhetı el a szálak megfelelı, effektív elosztásával a szoftver részegységei között. Napjainkban a

- 17 -


Vágó Gergely

legtöbb alkalmazás azért használ szálakat, hogy felhasználói felületek fogékonyságát növeljék egymagos rendszerekben. Különösen akkor, amikor blokkolni kell a felhasználói interfészt (UI), amíg az idıigényes adatbázis-lekérdezésre, vagy merevlemez-hozzáférésre vár. Ekkor az alkalmazás létrehoz egy szálat, mely várja a felhasználó kérését. Ez megengedi az ütemezınek, hogy egyénileg beütemezze a fı vezérlıt, ami megkapja az UI eseményeket, csak úgy, mint az adatot a futó folyamattól, mely az adatbázis-lekérdezést futtatja. Ebben a modellben a fejlesztık egyenes arányú teljesítményjavulásra számítanak. Ez a többszálúság használatának megfelelıje egymagos processzorok esetén. Az egymagos processzorok valójában csak összefésülni képesek az egyes utasításokat, de azokat egyidejőleg futtatni nem, ezért a többszálú alkalmazások futtatása ezen rendszereken eléggé behatároltak. Ezeken a platformokon a szálak általában csak programozói fogások a késleltetési idı elrejtésére. Ez a teljesítmény-korlátozás a többmagos rendszereken eltőnt: a szálaknak nem szükséges várakozniuk az erıforrásokra, sıt, önállóan, függetlenül futhatnak az egyes magokon. A többmagos rendszerek lehetıvé teszik a fejlesztıknek, hogy tovább optimalizálják alkalmazásaikat, elosztva az egyes munkamennyiséget a rendelkezésre álló magok között. Ez pedig hatékonyabb, gyorsabb alkalmazásokat szülhet. Többszálú alkalmazás futtatása többmagos platformon más fejlesztıi eljárásokat, megfontolásokat igényel, mintha egymagos rendszereken futtatnánk azokat. Egymagos rendszereken a fejlesztı dönthet úgy, hogy többszálú alkalmazást ír a hozzá tartozó hibaellenırzéssel. Ez a lehetıség nem adott többmagos rendszereken: ott megfelelı kódot kell írnia. Két terület van, mely rávilágít a különbségekre: memory cahceing (memória cachelés, gyorsítás) és tread priority (szál-prioritás). Minden processzor magnak van saját cache-e. Ezek tartalma bármelyik idıpillanatban eltérhet egy másik maghoz kapcsolódóétól (false sharing probléma). Egymagos rendszereken egy cahce-n osztoznak a szálak, így annak szinkronizációja nem jelent problémát. A szálak priorítása különbözı viselkedést eredményezhetnek single-core és multi-core rendszerek esetén. Gondoljunk csak arra, ha egy egymagos processzoron szeretnék futtatni egy alacsony és egy magas priorítású szálat. Ehhez képest két különálló mag esetén mind a két szál párhuzamosan futhat.

- 18 -

Többmagos processzorok programozhatósága 2.2.3

Vágó Gergely

A többmagos processzorok felépítése

[2]

Elsı szembetőnı tény, hogy a hagyományos, egy mag helyett egy processzoron kettı, vagy több mag foglal helyet. Ezen felül olyan további kérdésekre kellett választ találniuk a mérnéköknek, a gyártóknak a tesztek, s korábbi gyártási eredmények alpaján, mint például: •

•

•

•

Magok kialakítása o

alapfelépítés (szimmetrikus, heterogén)

o

fizikai kialakítás (monolitikus, többlapkás)

o

további jellemzık (vírusvédelem, virtualizáció támogatása, adatvédelem, stb.)

L2 cache kialakítása o

hozzárendelés a magokhoz (privát, közös)

o

befoglalási politika (inkluzív, exkluzív)

o

adat/utasítás tárolási politika (közös, osztott)

o

modularitás (egymodulos, többmodulos)

o

integrálása a processzor lapkára (részleges, teljes)

L3 cache kialakítása (ha van) o

hozzárendelés az L2 cache(k)hez (privát, közös)

o

befoglalási politika (inkluzív, exkluzív)

o

adat/utasítás tárolási politika (közös, osztott)

o

modularitás (egymodulos, többmodulos)

o

integrálása a processzor lapkára (részleges, teljes)

Memória és I/O architektúra kialakítása o

a kapcsolat elve (FSB-n keresztül, M.c. és B.c.-n keresztül)

o

csatolási pont megválasztása (legmagasabb-, ill. két legmagasabb cache szint)

o

M.c. (memória vezérlı) integrálása a processzor lapkára (lakán kívül megvalósított, lapkára integrált)

•

A kapcsoló hálózat(ok) megvalósítása o

a magok és a közös L2 modulok között

o

a privát / közös L2 és közös L3 modulok között

o

a privát/közös L2/L3 modulok és a B.c./M.c. vagy az FSB között

o

lapka-lapka és modul-modul kapcsolat

- 19 -


Vágó Gergely

A fenti tulajdonságok kombinációja, illetve azok értékei jelentısen befolyásolják egy többmagos processzor nem csak szerkezeti felépítését, de (hatékony-) mőködését is. Egy lehetséges, általános felépítés és azok elemei közötti kapcsolódás:

Többmagos processzorok építıelemei

2.2.4

További többmagos processzorok és rendszerek

E fejezet keretein belül kívánok további többmagos processzorokat használó rendszereket, eszközöket bemutatni, melyek nem feltétlenül kapcsolódnak szorosan az asztali számítógépek világához, mégis nagy jelentıséggel bírnak, illetve bírtak a technológia jelen irányú fejlıdésében. 2.2.4.1

PowerPc (XBox 360)

[15]

Az XBox 360 játékkonzol ugyancsak többmagos processzort használ. Elsı kiadása 2005 november 22.-én jelent meg, de azóta már több restauráción átesett (változatai: Arcade, Core, Prenium, Elite.). Az Xbox 360 hardverének alapja egy speciális PowerPC processzor, amely 3,2 GHz-en üzemel és három magot tartalmaz.

A

magok

egyenként

két

utasításszál

párhuzamos végrehajtására képesek és rendelkeznek egy 128 bites vektoros végrehajtóegységgel is. A grafika megjelenítésérıl 500 MHz-es egyedi ATI videochip gondoskodik. Az Xbox 360-ban 512 megabájt GDDR3 memória kapott helyet, amely 700 MHz-es órajelen mőködik. A videochipben további 10 megabájt beágyazott memória található. [15] - 20 -

Többmagos processzorok programozhatósága 2.2.4.2

Vágó Gergely

Cell (Playstation 3)

[14]

Érdemel némi szót ez a (elsısorban játékokra szánt) konzol is a többmagos technológia világából. Minıségi mutatói, paraméterei annak idején szó nélkül felvették a versenyt a két nagy processzor-gyártóval szemben. Ez pedig a Playstation 3. 2006 november 11.-én jelent meg Japánban a Sony újdonsága, a Playstation 3, benne az akkori csodaprocesszorral, a Cellel. A chip olyan teljesítményre volt képes, amit akkoriban elképzelni sem tudtunk, köszönhetıen a nyolc magnak. A Cell bizonyos szempontból már akkor a jövıt idézte: az akkori többmagos rendszerek magjai tökéletesen egyenrangúak voltak, addig a Cellben egy „vezérmag” és hét kisebb „szolgamag” dolgozott együtt. A Cell magjai külön-külön programozhatók egy-egy speciális feladatra, hogy azokat minél hatékonyabban tudják végrehajtani. [14] A

PlayStation

3

lelke az STI (SonyToshiba-IBM) által kifejlesztett névre magos

Cell

hallgató

8

központi

processzor, melybıl egy le van tiltva praktikussági okokból, mivel ha egy mag elromlik egyszerően bekapcsolható a másik. Hatot használhatnak a fejlesztık, a hetedik az operációsrendszeré. Érdekesség, hogy PS3-okat használtak fel szuperszámítógépek felépítéséhez. Az egyes gépeket klaszterben üzemeltetik, rajtuk pedig Linux van telepítve. A PS3 teljesítménye sokszorosan meghaladja a – vele egy kategóriájú - számítógépek teljesítményét. 2.2.4.3

Cuda

[11] [30]

Compute Unified Device Architecture. Az nVidia által kifejlesztett programozási architektúra, mely a cég saját grafikus processzoraiban megtalálható komponensekkel együtt többszörös párhuzamos végrehajtást és ezzel nagy számítási kapacitást biztosít. A CUDA rendszerben írt programok futtatásához nemcsak a megfelelıen írt programkód szükséges, hanem legalább 8-as sorozatú nVidia GPU, melyekben megtalálhatóak a CUDA támogatáshoz szükséges komponensek. Mivel a GPU -k

- 21 -


Vágó Gergely

jelentısen eltérnek a hagyományos processzoroktól és belsı felépítésük sok helyen párhuzamos végrehajtású elemekre épül, gyakorlatilag egy sokmagos architektúrának is tekinthetjük azokat.[11] Az 512 magos vektor processzorok elképzelése nem számított újdonságnak: a kliencvenes években számos szerverbe szánt modell jelent meg. A GPU-val történı számítás azonban egy aránylag új, kevéssé ismert funkció, pedig ezek a processzorok rendszerint rengeteg adattal, számos egymással párhuzamosan futó folyamatot dolgoznak fel, így a bennük rejlı potenciál hatalmas. Egy átlagos asztali többmagos processzorban jelenleg kettı- négy- hat-, esetleg nyolc magot találunk, míg a CUDA architektúra

alapja

nagyon

sok,

512

darab

nagymértékben

leegyszerősített

processzormag. Lényegében egy CUDA magnak nincs saját regisztere vagy elsıszintő gyorsítótára, mint egy hagyományos processzormagnak, valamint nincs számos különféle funkció egységük sem. Mindössze egy pipeline vagyis lépcsıs végrehajtásra optimalizált FPU és integer számítási magjuk van. Ezen felül nincs betöltı/tároló elemük sem a memória közvetlen eléréséhez. A CUDA magok a pixel shader-ekbıl fejlıdtek ki és nagyon egyszerő végrehajtó egységek. Ezek szálanként egy utasítás végrehajtására terveztek, melyek végeztével gyorsan ugrik a következıre. Nem arra lettek optimalizálva, hogy egyenként, egyesével teljesítsenek számos feladatot, hanem többszálú végrehajtásra születtek, melyet tömegben végeznek. [30]

A Cuda felépítése (100+ mag) – bal oldalon egy szimpla Dual Core CPU

2.2.4.4

Larrabee (várható megjelenés: 2010 tavasza)

[20]

A Larrabee egy párhuzamos architektúra, melynek 45 nanométeres implementációja várhatóan 32 módosított x86-os magból épül fel, melyeket körbusz köt össze. Az x86-os magok a szoftveres kompatibilitást és a vezérlést szolgálják, a számításokat az 512 bit széles vektoros végrehajtóegységek végzik, melyek például 16 pixelen tudnak egyszerre manipulációt végrehajtani, vagy 8 darab 64 bites precizitású matematikai számítást elvégezni. Egy-egy mag 32 vektorregiszterrel, gyors hozzáféréső, adat- és utasításcache-

- 22 -


Vágó Gergely

re osztott elsıszintő gyorsítótárral rendelkezik, valamint az egymás közötti kommunikációra pedig a megosztott másodszintő gyorsítótárat használják. Ennek mérete a magok számától függ, magonként 256 kB adódik hozzá.

A Larrabee felépítése (32 mag) – bal oldalon egy szimpla Dual Core CPU

2.2.4.5 •

Szuperszámítógépek

A NASA 10.240 processzorból álló, Columbia elnevezéső szuperszámítógépét 20 Altix-rendszerbıl állították össze, amelyek mindegyike 512 Intel Itanium 2 processzorral mőködik.

•

A Roadrunner egy katonai számítások végzésére létrehozott szuperszámítógép. Helyet kapott benne a hagyományosnak mondható AMD Opteron processzor is, összesen 116.640 processzormag hajthatja meg az új szuperszámítógépet.

•

A Jugene egytrillió darab számítást képes elvégezni másodpercenként, ami ötvenezer hagyományos PC teljesítményének felel meg. A szuperkomputert egy sor különbözı célra használják majd, többek közt idıjárás-elırejelzések elkészítéséhez, a klímaváltozás vizsgálatához, valamint elektromos autókba szánt üzemanyagcellák kifejlesztéséhez és az univerzum eredetét vizsgáló kutatásokhoz.

2.3

Párhuzamosság

E fejezet célja, hogy megismerjük a párhuzamos programozáshoz szükséges alapvetı fogalmakat – mint például Amdahl törvénye, szálak(thread), versenyhelyzet, holtpont, kritikus szakasz, szinkronizálás. Ezen felül elırevetíti mindazt az elınyt és hátrányt, ami a párhuzamos folyamatok programozásával együtt jár. 2.3.1

Alapfogalmak

[1][3][4]

A párhuzamosság kihasználása által nyerhetı maximális teljesítménynövekedés mértéke számos tényezıtıl függ. A legfontosabb azonban az, hogy a lefuttatandó programkód milyen arányban oszlik soros, és párhuzamosítható részekre. A szoftver

- 23 -


Vágó Gergely

sebességének gyorsítását idézheti elı ha képesek vagyunk a párhuzamosítható részeket valóban egy idıben futtatni, több szálon, akár több dedikált processzormagon. Ez ugyanakkor önmagában kevés, hiszen a sebességgyorsítás maximumát minden esetben a soros komponens határozza meg, így ha valóban sok párhuzamos mőködéső processzormagot, vagy szálat feltételezünk, akkor csak úgy tudjuk jelentısen növelni a hatékonyságot, ha a soros tényezıt csökkentjük a párhuzamosíthatóak javára. Ezt konkrétan Amdahl törvénye fogalmazza meg, ami ellentétben Moore tapasztalati és spekulatív alapokon nyugvó megfigyelésével, valóban pontosan meghatározza, adott esetben meddig lehet növelni a teljesítményt. Amdahl törvénye: 1 / (F + (1-F)/N), ahol F:

szekvenciális

tényezı,

N:

párhuzamos

mőveletvégzık(magok)

száma.

Eredménye: maximálisan elérhetı sebességnövekedés-szorzó. Próbáljuk megvilágítani ezt a kérdéskört egy igencsak egyszerő, hétköznapi példa felhasználásával: Tegyük fel, hogy egy kerítést festünk. Az elképzelt kerítésünk pontosan 300 lécbıl áll, és szeretnénk ezt a lehetı leggyorsabban lefesteni. A festés megkezdésekor szükség van 30 perc elıkészítésre, a festés befejezésekor pedig ugyancsak 30 percre, hogy mindent elrámoljunk magunk után (vegyük úgy, hogy ezek alkotják a folyamat soros komponensét). Mondjuk, hogy egy ember egy perc alatt egy léc lefestésére képes. Ebbıl a következı összefüggések adódnak: Festık száma 1 2 10 100 végtelen

Szükséges idı 360 = 30+300+30 210 = 30+150+30 90=30+30+30 63=30+3+30 60 = 30+0+30

Sebesség növekedés 1,0X 1,7X 4,0X 5,7X 6,0X

Hatékonyság 100,0% 85,0% 40,0% 5,7% Nagyon alacsony

Még ez alapján sem könnyő azonban eldönteni, hogy hány festı segítségét kérjük. Nyilvánvalóan látszik, hogy ha két ember dolgozik a festésen, akkor sem lesz kész kétszer gyorsabban a munka, hanem csak 150 percet lehet nyerni. Ha már 100 ember segítségét kérjük, akkor is csak 5,7-szeres sebességnövekedést értünk el. Ha a soros tényezıt képesek volnánk nullára redukálni, akkor valamennyi újabb festı bevonásával ugyanakkora arányban csökkenne a befejezéshez szükséges idı. A valóságban természetesen ez még ennél is bonyolultabb, ugyanis a soros tényezıt gyakran növeli a párhuzamosan dolgozó emberek – vagy számítógép esetében a szálak – összefogása, szinkronizálása. Vegyük például csak azt az egyszerő esetet, hogy

- 24 -


Vágó Gergely

mindössze egyetlen festékes bödönt használ valamennyi munkásunk. Ebben az esetben a festıknek például minden ötödik ecsetvonás után meg kellene várniuk, míg hozzáférnek a festékes bödönhöz. Arra is fokozottan figyelni kell valamilyen folyamatrendszer kialakításával, hogy véletlenül se akarjon egyszerre kettı vagy több festı belenyúlni a festékbe: kritikus szakasz, holtpont fogalmai. 2.3.2

Amdahl törvénye

[35]

Térjünk most vissza egy kicsit Amdahl törvényéhez. A párhuzamos programozás egy alapvetı axiómája ez. Azonban önmagában még kevés, az egyenletbe további változó elemeket kell bevezetni, figyelembe véve többek között az egyes architektúrákat, technológiákat, s nem utolsó sorban alkalmazásaink tulajdonságait. Tehát Amdahl törvénye a következı volt: 1 / (F + (1-F) /N) Ha 1-el helyettesítjük a processzorok számát(kiindulási alap), látható, hogy nincs sebességnövekedés. Ha van egy dual-core rendszerünk, fele munkát végezve az eredmény így módosul: 1 / (0.5F + 0.5F/2) = 1/0.75F = 1.33 Ez 33 százalékos gyorsulás, mivel a futási idı (nevezı) 75 százaléka az eredetinek. 8-magos processzor esetén a következıt kapjuk: 1 / (0.5F + 0.5F/8) = 1/0.562F = 1.78 N = +∞ esetén feltételezve, hogy a legjobb szekvenciális algoritmus 1 egységnyi teljesítményt ad: Speed-up = 1/F lesz az eredmény.

Teljesítménynövekedés ábrázolása Amdahl – törvénye alapján

- 25 -


Vágó Gergely

Ebbıl a viselkedésbıl Amdahl feltételezte, hogy további processzormagok hozzáadása teljes mértékig felesleges. Innen törvényszerően az következik, hogy a maximális haszon - melyet egy program mőködésétıl várhatunk - az egyes kódrészek párhuzamosításával, az korlátozott a kódban szereplı soros hozzáféréső pontok által. Például, figyelembe véve Amdahl törvényét, ha egy alkalmazásnak 10 százaléka fut soros mőködésú kóddal, akkor a maximális sebességjavulás 10x lehet, a magok számát figyelmen kívül hagyva. Tehát a processzor magok végtelen nagyságú növelése kizárólag a nevezı párhuzamos részére hat. Azaz ha egy program csupán 10 százaléka párhuzamosított, a maximális elméleti haszon - melyet a program be tud járni - 90 százaléka a szekvenciális idınek. Levonhatjuk az elsı konzekvenciát Amdahl törvényébıl: processzormagok hozzáadása helyett fontosabb tényezı a soros mőködés hátrányára növelni a párhuzamos részt. Például, ha van egy program, melynek 30 százaléka párhuzamosan fut egy dual-core processzorú rendszeren, a magok megduplázása csökkenti a soros mőködéső futási idıt 85 százalékról 77.5 százalékra, míg ha megduplázzuk a párhuzamos kódú részeket 70 százalékra csökken a futási idı. Ennek illusztrációja látható az ábrán.

Bal oldalt: a magok számát dupláztuk; Jobb oldalt: a párhuzamosság arányát a kódban.

Csak ha már párhuzamosítottuk programunk jelentıs részét, akkor érdemes több processzor hozzáadásával folytatni kódunk további párhuzamosítását. Láthatjuk, erıs határai vannak annak, hogy teljesítménybéli javulást érhessünk el: nem csupán a processzor magok számának növelése, de a kódok párhuzamosítása is a szők keresztmetszet. Hogy Amdahl törvénye reflektálja a multi-core rendszerek valóságát, az elméleti maximum helyett vezessük be a következıt: - 26 -


Vágó Gergely

Speedup = 1 / (F+(1-F) /N + H(N)), ahol H(N) = overhead (többletköltség, többletmunka), valamint ismét tegyük fel, hogy a legjobb soros algoritmus egy idıegység alatt lefut. Meg kell még jegyezni, hogy az overhead nem lineáris egy helyesen mőködı párhuzamos gépen. [35] Amdahl törvényének alkalmazása a Hyper-Threading Technology –ban

[35]

Az elızı részben láthattuk Amdahl törvényének alkalmazását multiprocesszoros és multi-core rendszerekben. A HT Technology (2.2.2 Multi- architektúrák fejezet) behoz még egy tényezıt Amdahl törvényének kódszintő átültetéséhez. HT technológiával rendelkezı processzorokon a tény, hogy egyes processzor-erıforrások megosztásra kerülnek a különbözı futó szálak között, maximális teljesítményjavulást eredményeznek a több szálon futó alkalmazásainkban is. A HT technológiával összefésült végrehajtási környezethez szükségszerő, hogy Amadahl törvényére egy újabb formulát adjunk meg. Fıleg, mivel alkalmazásaink körülbelül 30 százalékos futási javulást mutatnak ezen technológia mellett. Ez a javulás már csupán egy egyszerő processzor esetén is elérhetı. Ha ezen felül egy quad-core rendszert használunk, ez elméletileg akár 4-szeres is lehet, azaz minden egyes mag bevétele további 30-30 százaléknyit javít. A gyakorlatban ez nincs teljesen így, köszönhetıen az overhead-nek, mely nem párhuzamosítható. Nem mellékesen, a HT Technology-val rendelkezı processzorok esetén minden szál sokkal lassabban fut annál, mintha az egész processzor csak az övé volna. Tehát ez a tehcnológia nem válthatja le a multi-core folyamatokat, mivel sok erıforrás osztott. A lassulás mértéke alkalmazásonként eltérı. Egyszerően megközelítve, például minden egyes szál 1/3 –nyival lassabban fut, mintha csak ı uralná az egész processzort. Módosítva Amdahl törvényét a HT Technology-val a következıt kapjuk: SpeedupHTT = 1 / (F+ 0.67((1-F) /N) + H(N)), ahol N = logikai processzorok száma. Ez az összefüggés reprezentálja a tipikus sebességnövekedést HT Technology-val mőködı processzor magok esetén. A H(N) értéke tapasztalati úton változik, alkalmazásoktól függıen. [35]

- 27 -


Vágó Gergely

2.4. Párhuzamos programozás alapjai A következıkben a párhuzamos programozás tervezési alapelveit, szabályait ismerhetjük meg. Párhuzamos programjaink nem-terminális mőködési nehézségeit, futási-, optimalizálási bonyodalmait, jellemzı hibáit. Ezen ismert problémák kiküszöbölésére alkalmazható eljárások, eszközök kerülnek bemutatásra. 2.4.1

Párhuzamos programozás szabályai többmagos rendszerek esetén

[21]

Multi-core rendszerek programozása új kihívásokat okoz, új problémákat vet fel. A következı, többmagos rendszerekre érvényes szabályok megértése és beépítése alkalmazásainkba, hozzásegíthetnek a sikeres multi-core programozáshoz: 1. Párhuzamos gondolkodási mód. Minden problémát párhuzamos szemléletmódon kell megközelíteni. Meg kell érteni, hol, milyen formában fordul elı párhuzamos mőködés. 2. Programozzunk absztrakt módon. Koncentráljunk olyan kód írására, mely kifejezi a párhuzamosságot, ugyanakkor el kell kerülni a szálak és processzor magok okozta bonyodalmakat. Kellıen magas szintő kódot kell írnunk, mely a probléma megoldásáról szól, nem pedig a szálak és magok –egy alacsonyabb szintőirányításáról, mőködtetésérıl. 3. Feladatok (részmunkák) szintjén, ne pedig szálak (magok) szintjén programozzunk. Hagyjuk programunk önálló mőveleteire a feladatok ütemezését: a szálakra, proceszormagokra. Készítsünk annyi taszkot amennyit csak lehet, anélkül, hogy aggódnunk kellene a túlköltekezés miatt. 4. A konkurencia kizárásával tervezzünk. A könnyebb hibakezelés érdekében olyan programokat kell készíteni melyek párhuzamosság nélkül is képesek futni. Így hibakereséskor elıször konkurens módon, majd anélkül futtatva programunk, láthatjuk, hogy helyesen mőködik –e, vagy sem. Hibakeresés sokkal egyszerőbb metódus, ha a program nem-párhuzamos mőködésőként fut, mivel az sokkal közelibb, s jobban támogatott még a mai eszközökkel is. Tudván, hogy valami csak konkurens módban fut helytelenül, leegyszerősíti a hiba okát, illetve annak megtalálását. 5. Kerüljük a lockok használatát. A zárolások lassítják a programokat, csökkentik a skálázhatóságukat, s ezek a párhuzamos programok hibáinak legjellemzıbb forrásai. Készítsünk inkább implicit szinkronizációs megoldást programjainknak. Amikor

- 28 -


Vágó Gergely

mégis szükséges az explicit szinkronizáció, akkor atomi mőveleteket célszerő használni, míg a lock használatára csak legvégsı esetben kerüljön sor. 6. Használjunk párhuzamosságot támogató segédeszközöket (tools) és könyvtári struktúrákat (libraries). 7. Használjunk skálázható memória allokátorokat. Többféle megoldás létezik, melyek mindegyike jobban használható, s mőködı, mint a malloc(). Ilyen memória allokátorok használata gyorsítja alkalmazásainkat a globális torlódási pontok megszüntetésével, memóriaterületek újraosztásával, mely elısegíti a cache gyorsítótárak jobb kihasználását. 8. A munkamennyiséggel arányosan tervezzünk. A program által kezelendı feladatok számának növekelése növeli a ráfordítandó idıt, energiát is. Tervezéskor tartsuk szem elıtt, hogy a processzor magok számának növelésével a program kezelendı feladatainak száma is növekszik. Arra számítunk, hogy számítógépünk évrıl-évre egyre többet- és többet tud. A jövıben a párhuzamos programozásnak is fel kell vennie ezt az ütemet, hogy jobban kihasználhassuk a gyorsasági növekedést. 2.4.2

Párhuzamos programozás nehézségei (munkamegosztás, holtidı, kritikus szakasz, kölcsönös kizárás) [35][3][4] [22][23][39]

A multi-core hozadéka beágyazott rendszerekben erıforrás csökkentés, megtakarítás. Természetesen ez csak akkor valósulhat meg, ha az eddig szekvenciálisan (sorosan) mőködı alkalmazásainkat ezen elınyök kihasználása érdekében effektíven át tudjuk ültetni párhuzamos platformokba. A legtöbb multi-core rendszer a jelenlegi beágyazott rendszerek piacán (ARM, MIPS) 2, illetve 4 magos alkalmazási osztályú processzor, mely teljes körő SMP OP szolgáltatást tartalmaznak, mint például a Linux. Ez lehetıvé teszi a fejlesztıknek, hogy azonnal kihasználhassák a további magok elınyeit, egyszerően azzal, hogy több programot futtatnak egy idıben, míg az operációs rendszer elrejti, s kezeli az adatokat. Hogy az óra frekvenciáját csökkenthessük összetettebb, nagyobb számításokat végzı alkalmazásokban, kódunk újragondolása, tényezıkre bontása szükséges. Az OS belsı, többszálúságot támogató függvényei egyszerőbbé teszik életünket, valamint az APIk, különösen a POSIX Threads (PThreads) lehetıvé teszik, hogy a fejlesztı gyorsan, s egyszerően párhuzamosítsa soros mőködéső kódját. Amint a program különbözı szálakon fut az OS kezelésbe veszi, s elhelyezi azokat futásuk során a rendelkezésre álló magok, mint erıforrások között. Ehhez már nincs szükség a fejlesztı további iterációira.

- 29 -


Vágó Gergely

Alkalmazások nagyobb hányada esik bele az egyszerő, szekventált kategóriába. Egy példa erre a kommunikáció és hálózatkezelés, ahol egy programnak kell gondoskodnia nagy számú, különbözı, egymástól független fél iterációijáról, megfelelı mőködésérıl. A probléma akkor jelentkezik, amikor követhetetlenül sok egymásba ágyazott alkalmazás végrehajtásáról beszélünk, mint például a jel- és média-feldolgozás. Ebben az esetben különösen fontos az erıforrások felhasználásának-, és ennek következtében az egyes magok üresen töltött órajelének a csökkentése. Minél jobban ki kell használni a multi-core adta lehetıségeket, elınyöket. Amikor egy négy magból álló rendszer a célgép, célszerő, ha négy iterációt engedélyezünk egy loopban (ciklus-lépésben), hogy párhuzamosan fussanak. Ekkor egy háromszorosnál valamivel jobb sebességjavulásra számíthatunk. Az elméleti négyszeres lehetetlen a szál-kezelı többletmunkája (overhead) miatt. Ez még egy ok arra, hogy miért létfontosságú a multi-core rendszer számára, hogy a rendelkezésre álló processzorok (magok) ugyanazon mennyiségő munkát végezzenek. Ez azt is jelenti, hogy folyamatainkat szükség esetén fel kell bontani, s meg kell osztani az egyes magok között. A következı implementáció szemlélteti hogyan kellene kinéznie egy párhuzamos kódrésznek, a PThreads –t használva. A fı ciklus PROCESSOR_COUNT-nyi lépésben végighalad a Data-n (négy mag esetén négy lépés). Minden egyes lépésben létrehozzuk szálak egy csoportját, majd mielıtt tovább folytatnák az iterációt, megvárjuk, míg befejezıdik a pthread_join eljárás. A kódot multi-core rendszeren futtatva, a végrehajtási idı jóval kevesbé javult, mint arra számítunk. Valójában, alig hatékonyabb, mint a szekvenciális implementáció esetén. A problémát a thread librare szakszerőtlen használata okozza, vagy egy rossz megközelítése a ciklus párhuzamosításának. void wrapped_process (data_t*pData) { *pData = process(*pData); pthread_exit(NULL); } . . . for (int i=0; i<SET_SIZE; i+=PROCESSOR_COUNT) { int num_threads=(SET_SIZE-i) < PROCESSOR_COUNT ? (SET_SIZE-i): PROCESSOR_COUNT; for (int n=0; n
- 30 -


Vágó Gergely

Három különálló ok lehet a probléma forrása: •

Sok idıt vesz el a szálkezelı- és vezérlı könyvtári elemek meghívása.

•

A felhasználói funkciók aktuális futási ideje drasztikusan megváltozhat a ciklus iterációi között. Azaz a program nem kezeli a data set (adatok csomagja) minden egyes elemét egyenrangúan, s megvan a maga betöltéskori hibája.

•

A betöltés szabályozásának (load balancing) a problémája a súlyosabb: mivel csak négy szál van, amint egy mag végez a számára kijelölt feladat futtatásával, nincs más tennivalója (holtidı).

Az elsı problémára általános megoldás, hogy fix számú dolgozó szálat hozunk létre, így ismerve a thread pool (rendelkezésünkre álló szál-készlet) méretét. Az egzakt, pontos implementáció változói az alkalmazástól függenek, de a szálak alapjába véve továbbra is kooperatívan léteznek és folytatják szerepük folyamataikban, vagy legalábbis egy vezér-szál irányítása alatt állnak, mindaddig, míg egy befejezı, kilépı feltétel (end condition) be nem következik. Ennél a pontnál a szálak mind kilépnek, vagy leállnak, míg a vezér-szál engedélyezi a fıprogram további futását. A második pont, a drasztikus változás a felhasználó funkcióinak futási idejében. Mivel a négy szál eloszlik a négy mag között, az optimalizálatlan eset csupán a ciklus iterációinak 25%-ában következik be. A probléma az, hogy három processzor haszontalanul vár, míg csupán a negyedik végzi a nagyobb munkát. A helyes implementációnak úgy kellene kinéznie, hogy amint végeznek elızı adataikkal az egyes szálak, biztosítani kell ıket arról, hogy hozzáférhessenek a következıhöz, ahelyett, hogy megvárnák a teljes csomag befejezését, kikényszerítve ezt a mőködést pthread_join(...) hívással. A szálak és a magok összeegyeztetése ritkán jó ötlet különbözı okok miatt, például könnyedén betöltés-szabályozási probléma lehet a vége. A legjobb, ha jelentıs számú szálat hozunk létre ahhoz, hogy a processzor kellıen elfoglalt legyen, de ne túl sokat ahhoz, hogy meggátolja a rendszer mőködését. Ebben az esetben az OS ütemezıje meg tud birkózni a terhekkel és a magokat is kellıen lefoglalja. #define THREAD_POOL_SIZE 25 int fetchAndIncrementIndex(void) { int aLocalIndex; pthread_mutex_lock(&DataIndex_mutex); aLocalIndex = gDataIndex++;

- 31 -


Vágó Gergely

pthread_mutex_unlock(&DataIndex_mutex); return aLocalIndex; } void wrapped_process (data_t*pData) { int aIndex; while ((aIndex = fetchAndIncrementIndex()) < SET_SIZE) pDataSet[aIndex] = process(pDataSet[aIndex]); pthread_exit(NULL); }. . . gDataIndex = 0; for (int n=0; n
Változás, hogy az említett ciklus el lett távolítva, s egy másik helyettesíti azt, a wrapped_process(..) függvény. Ez a ciklusváltozó megosztását eredményezte a szálak között: minden egyes szál képes az indexet a következı értékre állítani, illetve felismerni, ha ki kellene lépnie a ciklusból. Mivel most van egy megosztott indexváltozónk, a gDataIndex, szükséges annak biztosítása, hogy egyszerre csak egy szál férhet hozzá, s módosíthatja ennek értékét. Azaz kritikus szakasszá vált ez a kódrész. Tehát kölcsönös kizárást megvalósító változók használatára van szükség: a fetchAndIncrementIndex(...) függvény segítségével. Ezzel elıállt az optimális négyszeres gyorsulás. 2.4.3

További nehézségek (versenyhelyzet, holtpont)

[3][4][35][22][23][39]

Vegyük a következı esetet: a program egy része egy processzoron fut, s értéket ír egy változóba. Ez után egy másik része egy másik processzoron futva olvas abból a változóból. Milyen értéket olvas ki az a folyamat? Minden azon múlik, hogy mikor kísérelte meg az olvasást: az írás elıtt, vagy után. Ez a versenyhelyzet. Visszatekintve újra az elızı kódrészre, biztosítottuk a globális gDataIndex hozzáférhetıségét olyan függvényekkel, melyek eleget tesznek kölcsönös kizárás problémájának orvoslásának. Továbbá bevezetésre kerültek a változó másolatai, melyek módosítása nem hat vissza az eredetire. if (gDataIndex < SOME_LIMIT) return doThis(pData); else return doThat(pData);

Versenyhelyzet kialakulása jelentısen függ az idızítéstıl. Ha ketten versenyeznek az osztott változó hozzáféréséért, elıfordulhat, hogy olyan minimális az idıkülönbség a

- 32 -


Vágó Gergely

változtatások között - mert mondjuk csak kis idıre sajátítja ki magának az egyik szál a változót, vagy mert megváltozik a folyamatok hozzáférésének sorrendje-, hogy észre sem vesszük, s megtörtént a baj. A legjobb védekezés az ilyen típusú problémák ellen, ha veszünk egy módszeres megközelítést a közös, osztott változók felderítésére (data race (versenyhelyzet) detektor képes erre), majd figyelmesen kielemezzük az összefüggéseket, kapcsolatokat, megállapítva, hogy hol szükséges a kódban módosítani, atomi mőveleteket bevezetni a kölcsönös kizárás érdekébe. A másik nagy hibaforrása a szál-programozásnak a holtpont. Ez akkor alakulhat ki, amikor két „szál-biztos” erıforrás egymáshoz kíván hozzáférni. Tehát amikor egy szál eléri a function_in_thread_1 részt elıször, s aktiválja a lockolást, megakadályozva a másik szálnak a function_in_thread_2 programrész futtatását, akkor minden rendben történik: a második szál nem fér hozzá az erıforráshoz, mindaddig, amíg az fel nem szabadul. void function_in_thread_1(void) { . . . pthread_mutex_lock(&Lock1); pthread_mutex_lock(&Lock2); aSharedVariable1 += aSharedVariable2 * 4; pthread_mutex_unlock(&Lock2); pthread_mutex_unlock(&Lock1); . . . } void function_in_thread_2(void) { . . . pthread_mutex_lock(&Lock2); pthread_mutex_lock(&Lock1); aLocalVariable = aSharedVariable1 – aSharedvariable2; pthread_mutex_unlock(&Lock1); pthread_mutex_unlock(&Lock2); . . . }

Amikor a szálak pont egyszerre érik el saját függvényüket, akkor jön a probléma. Mind a két szál elkapja az elsı lockot, de amikor a másodikat is ki szeretnék sajátítani, észreveszik, hogy azt már más használja. Egyik thread sem képes végigfutni, mivel egy más által foglalt erıforrásra vár. Akár új alkalmazás fejlesztésérıl, akár létezı kód átírásáról van szó, a lényeg ugyanaz: a fejlesztınek váltania kell a szekvenciális gondolkodásmódról a párhuzamosra, s a köztük lévı különbség a legfontosabb, amit meg kell tanulnia. Olyan ez mintha egy új programozási nyelvet kellene elsajátítani. Sok nyelvi kiegészítés, könyvtári struktúra vált elérhetıvé azzal a céllal, hogy megelızze a fejlesztık megfeneklését a többszálú programok absztraktabb gondolkodása, kezelése és vezérlése okozta kihívások miatt. - 33 -


Vágó Gergely

Párhuzamos programozási modellek

[41]

Tény, hogy a párhuzamosítással történı teljesítménynövelés érdekében biztosítani kell a sok feldolgozó egység közös cél érdekében történı együttmőködését. A különbözı párhuzamos architektúrákban (elızı fejezetek) a csomópontok összekapcsolásának módja lényegesen eltér, azért a párhuzamos programozás különféle módszerei architektúránként eltérı hatékonyságúak. A fıbb modellek a következık: •

Párhuzamos kódot generáló fordítók Feladata a hagyományos, szekvenciális módon készített programokban fellelhetı implicit párhuzamosságok felderítése, és a párhuzamosan futtatható kód automatikus elkészítése.

•

Párhuzamos nyelvek A párhuzamos nyelvek és fejlesztı környezetek használata –csak úgy mint az elızı modell esetén- szintén erısen közös memóriát használó környezetekhez kapcsolódik. A párhuzamos kódot generáló fordítókhoz képest fı eltérés, hogy itt nem autómatikus a párhuzamosítás, hanem a fejlesztınek explicit módon kell megfogalmaznia a kódrészleteket a nyelvi szerkezetek és kiterjesztések segítségével. Például: ADA, CC++, Fortran M, stb.

•

Üzenetkezelı rendszerek Az elosztott memóriás rendszerek lazán csatolt szemléletét tükrözi. Az üzenetkezelı eljárásokat egy rutinkönyvtár formájában illesztik egy magas nyelvhez. Ilyen például a PVM (Parallel Virtual Machine) és MPI (Message Passing Interface)

könyvtár.

Sikereik

miatt

implementációik

számos

különféle

rendszertípusra elkészültek. Az MPI könyvtárra támaszkodó párhuzamos programok gond nélkül lefordíthatóak és futtathatóak az összes architektúrán. Az üzenetkezelı könyvtárak a párhuzamos alacsony szintő támogatását biztosítják, azaz megteremtik a kommunikáció és a szinkronizálás eszközeit a processzek között, azonban ezek megfelelı alkalmazása a helyes párhuzamos feldolgozás érdekében a programozó feladata. A fejlesztı dolga az adatszerkezetek definiálása, az adatpartícionálás, a vezérlés megtervezése, a kommunikációs struktúra kialakítása és a processzek a feldolgozó egységhez való rendelése is. A könyvtárak használata a sok függvényparaméter miatt nehézkes.

- 34 -

Többmagos processzorok programozhatósága •

Vágó Gergely

Virtuális közös memória modell alapú rendszerek Egyszerőbb, könnyebben használható modell, módszer. A VSM (Virtual Shared Memory) lényege, hogy az elosztott memóriával rendelkezı rendszerekben megvalósítsák a közös memória emulációját, virtuális többszörözését. A közösen használt memória területet a hatékonyság érdekében gyakran minden fél, csomópont részére többszörözik, a példányok szinkronizálásáról a háttér gondoskodik (fejlesztı, nyelvi eszköz, operációs rendszer). A megközelítés elınye, hogy a fejlesztıknek nem kell midnig tudnia, hogy hol találhatóak a szükséges adatok, hanem a rendszer legfrissebb példányához való hozzáférést annak helyétıl függetlenül, automatikusan biztosítja.

•

Objektum orientált párhuzamos programozás Az objektumok jól illeszkednek az üzenet alapú kommunikációs modellhez (gondoljunk csak az elrejtett belsı állapotokra és a külvilág számára látható külsıkre, azok meghívására) és nehézségek nélkül kiegészíthetık az osztott felhasználás

koncepciójával.

Jól

áttekinthetı,

könnyen

fejleszthetı

kódot

eredményezı környezetek. Például: C#, Java. 2.4.5

Párhuzamos programozási paradigmák

[41]

A párhuzamos programok szerkezetük alapján csoportosíthatók és besorolhatók. Minden egyes paradigma egy-egy algoritmus osztályt képvisel, melyben a vezérlı szerkezetek lényegében azonos sémát követnek. Egyes feladatok elvégzésére hibrid megoldások bizonyulhatnak a legjobbnak. Az alább látható képen az elsı négy paradigma tiszta változata látható. •

Mester-szolga (master-slave, task farming) Egy futtató rendszert takar, mely a programot eljuttatja a futtató csomópontokra, és átadja számukra a futtatáshoz szükséges bemeneti adatokat. A futás befejezıdésekor az eredményeket a futtató rendszer összegyőjti és eljuttatja a feladatot elindító felhasználónak. Egyaránt alkalmazható statikus és dinamikus terheléselosztás – kiegyenlítés. Statikus esetben a feladatot a feldolgozó egységek megfelelı számú részekre bontják és párhuzamosan elindítják azokat. Ilyenkor van egy mester, mely szintén részt vesz a számításokban. Ha a taszkok száma nem ismert elıre, illetve ha a végrehajtó egységek (pl. magok) számánál több taszkot kell feldolgozni, elınyösebb a dinamikus módszer alkalmazása. Ilyenkor a mester csak a feladatkiosztás koordinálásával foglalkozik: ha a szolga végzett a neki kiadott

- 35 -


Vágó Gergely

részfeladattal, akkor újat kap. Ez a fajta feladatkiosztás jól alkalmazható változó környezetben, így például eltérı magszámú processzorok esetén. A mester-szolga vezérlési struktúra alkalmazásával jelentıs sebességnövekedés és skálázhatóság érhetı el, amennyiben a megoldandó feladat alkalmas az ilyen szintő párhuzamosításra. Ilyen típusú feladatok többek között például: adatelemzés, kép – és filmszintézis, stb. A paradigma a leghatékonyabb megoldás az elosztott memóriával rendelkezı párhuzamos rendszerek kihasználására, hátránya, hogy általános célú feladatok nem feltétlenül bonthatók fel tökéletesen elkülönítve végrehajtható részekre.

a) mester-szolga, b) adattartomány dekompozíció, c) futószalag, d) „oszd meg és uralkodj” •

Adattartomány dekompozíció Párhuzamos programozásban legelterjedtebben használt paradigma. Lényege, hogy a processzek ugyanazt a kódot futtatják, de más-más adatokon. Számos probléma hátterében egy szabványos struktúra húzódik, ahol az egymástól való függıségek térben korlátozottak. Ez a homogenitás teszi lehetıvé az adatok processzorok, illetve azok magjai közötti olyan elosztását, ahol a azok csak egy-egy térrészre vonatkozó számításokért felelnek és csak közvetlen szomszédaikkal kommunikálnak. Bizonyos esetekben globális szinkronizálásra is szükség lehet. A módszer akkor hatékony, ha a felosztott térrészekhez rendelhetı számítások nagyjából azonos mennyiségőek. Inhomogén számításigény esetén pedig valamilyen terhelés kiegyenlítı algoritmust kell alkalmazni. Hibája: egyetlen tartomány kiesése, meghibásodása a teljes algoritmus leállását eredményezi.

- 36 -


Vágó Gergely

Futószalag elv Funkcionális dekompozíción alapul: a feladat konkurens mőködésre alkalmas részeit szétválasztják, és az egyes részeken külön-külön processzoron, illetve magon futtatják. A paradigma hatékonysága az egy erıforráshoz rendelt fokozatok számításigényeinek kiegyensúlyozottságán múlik. Hibatőrés és terheléskiegyenlítés miatt több lehetséges adat-utat alkalmaznak. A módszert leginkább az adatelemzés és a képfeldolgozás területein használják.

•

„oszd meg és uralkodj” Jól ismert a szekvenciális programozás területén is. Lényege, hogy az alapproblémát több kisebb részre bontjuk, majd a részproblémákat külön-külön megoldjuk, majd a részeredmények összesítésébıl születik a végeredmény. A részproblémák hasonlóan szintén tovább bonthatóak, és így tovább, több iterációs lépésben oldva meg a feladatot. Egyes problémák felbontásuk során saját maguk kisebb változatát adják, lehetıvé téve a rekurzív megoldást. A párhuzamos megvalósítás lényege, hogy a keletkezı részproblémák egymástól függetlenül megoldhatók, vagyis a részegységek nem kommunikálnak egymással. Három alapmővelete: szétosztás, számítás, egyesítés. A mester-szolga paradigma az „oszd meg és uralkodj” egy speciális esetének is tekinthetı, ahol csak egyetlen szétosztási szint keletkezik. A módszer idıben változó, dinamikus módon mőködik.

•

Spekulatív párhuzamosság Akkor érdemes alkalmazni, ha a megoldandó problémában jelenlévı összetett adat vagy funkcionális függıségek akadályozzák az elızı négy paradigma használatát. Ilyen esetekben is érdemes a problémát kisebb részekre bontani és azokat egymással párhuzamosan megoldani, de itt szükség van különféle heurisztikák és optimista futási megközelítések alkalmazására. Azaz olyan részeket kell részproblémákra bontani és párhuzamosan futtatni, ahol feltehetı, hogy a konkurens végrehajtás nem befolyásolja a teljes probléma megoldási konzisztenciáját. Ha ez utólag mégis megsérült, akkor vissza kell nyúlni a még helyes állapotig (rollback). Egy felhasználási lehetıség például amikor egy probléma megoldására több egymástól független algoritmus létezik, de nem lehet elıre tudni, hogy melyik vezet a leggyorsabb, legjobb eredményre. Ilyenkor mindegyik algoritmust párhuzamosan, egyszerre el lehet indítani, s a leggyorsabb adja a végsı megoldást.

- 37 -


3.

Vágó Gergely

Nyelvi eszközök

3.1

Osztályozási szempontok

3.1.1

Általános nyelvi tulajdonságok

[39]

Az egyes programozási eszközök tulajdonságait a hagyományos szoftverminıségi szempontok alapján is csoportosíthatjuk –figyelembe véve, hogy párhuzamos alkalmazások írására szánjuk termékünket. •

Helyesség A program úgy mőködik-e, ahogy azt elvárjuk, megoldja-e a specifikált feladatot. Egy párhuzamos program helyességének belátása jóval nehezebb feladat, mint egy szekvenciálisan mőködıé. Fıleg azért, mert nem triviális, nem determinisztikus a futásuk. Másrészt a párhuzamos programok utólagos helyességbizonyítása, de különösen hibás programok javítása, tesztelése rendkívül idõigényes. A helyesség belátására mégis számos elsısorban metamatikai módszer él, melyekkel a ’Programozási módszertan’ címő tárgy keretein belül foglalkoztunk. Alapelv a pontosan, jól definiált elvárt mőködés.

•

Megbízhatóság Nem várt, kivételes körülmények között is elfogadhatóan mőködik –e a program. Ide tartozik a kivételek lekezelése, a szálak, folyamatok közötti helyes kommunikáció, holtpont megfelelı lekezelése, vagy akár egy mag meghibásoda, kiesése. Ezek mind olyan esetek, melyekre a program specifikáció általában nem tér ki, mégis fel kell készülni rájuk.

•

Hatékonyság Ez az a szempont, ami miatt elıtérbe kerültek a párhuzamos eszközök. Tehát mondhatjuk, ez az egyik legfontosabb tulajdonság.

•

Hordozhatóság Párhuzamos programok esetén problémát jelenthet a fejlesztéssel nem azonos gépi konfiguráció: például több-kevesebb mag, eltérı operációs rendszer. Gondoljunk csak arra, ha kódunkba beleégetjük a szálak számát (thread-pool), melyet hozzá optimalizáltuk a fejlesztıi környezetünkben lévı magok számához. A lehetıség, hogy a szálak számát rugalmasan tudjuk kezelni nagyobb hordozhatósági szintet bitzosít. - 38 -


Vágó Gergely

Tesztelhetıség, áttekinthetıség, egyszerőség Fontos, a megbízhatóságot garantáló szempont. Vannak nyelvek, illetve eszközök, melyek összetettsége, bonyolultsága az átláthatóság rovására megy. Így nehezebben érthetı, tesztelhetı, javítható kódot kaphatunk. Nehéz azt a szintet tartani, hogy egy eszköz megfelelıen sok szabadságot nyújtson a fejlesztı számára, ugyanakkor maradjon az egyszerőség szintjén. Folyamatok kommunikációja magok között, vagy osztott (kritikus) erıforráshoz való hozzáférés helyes, kivételbiztos mőködésének megírása egyes nyelvekben már feszegeti az áttekinthetıség határait.

•

Fejlesztıi környezet Az eszköz használatának a hatékonyságát, használatának egyszerőségét növelheti, ha valamilyen kényelmes felületet biztosít a használatára, vagy a fenti tulajdonságok, problémák megoldásának valamelyikére (pl. grafikus felület)

•

Újrahasznosíthatóság A szoftver azon képessége, hogy egészben, vagy részben újra felhasználhatók egészben, vagy részben új alkalmazásokban. Ehhez az kell, hogy minél általánosabb, környezettıl, illetve magszámtól független kódot tudjunk írni a nyelv kínálta eszközökkel. Mindezt az átláthatóság keretein belül. Ez egy összetett tulajdonság: ötvözi a hordozhatóság és az áttekinthetıség, egyszerőség által megfogalmazott elvárásokat is.

•

Karbantarthatóság, kompatibilitás Párhuzamos programok továbbfejlesztése, modulokra bontása összetettebb feladat. Utólagos módosításuk nem szerencsés, hiszen ilyen alkalmazások tervezése azzal kell kezdıdjön, hogy meghatározzuk a kommunikáció és a közös erıforrás figyelembe vételével az önálló, felbontható részfolyamatokat, modulokat. Ha változik a specifikáció, vagy új modulokat kell hozzávenni a már meglévı kódhoz, akkor elıfordulhat, hogy újra kell tervezni a teljes mőködést.

•

A programozási nyelv jelentısége Nem utolsó szempont, hogy mennyire ismert, s sikeres nyelv kiegészítésérıl beszélünk. Elıfordulhat, hogy adott könyvtári kiegészítés jól megtervezett, s megfelelı lehetıségeket kínál többmagos processzorokon futó párhuzamos programok írására, de maga a nyelv nincs jelen a köztudatban, nem elterjedt.

- 39 -


Vágó Gergely

Párhuzamos nyelvi tulajdonságok

[39]

Egy párhuzamos programozási nyelv eszközeinek viselkedését az alábbi szempontok szerinti csoportosítással is megközelíthetjük: •

Párhuzamosság szintjének megvalósaítása o

Utasításszintő (finom szemcsézettség) Elemi mőveletek esete, pl. két skalár összeadása, szemaforok használata.

o

Ciklus-, vagy kifejezésszintő (közepes szemcsézettség) Az egymást követı iterációk, kifejezések párhuzamos végrehajtása.

o

Eljárásszintő (közepes szemcsézettség) A feladat jellegébıl adódhat. Megosztott globális változók, párhuzamosan futó szálak (thread) használata.

o

Programszintő (durva szemcsézettség) A felhasználók ill. programjai függetlenek egymástól.

•

Párhuzamosság típusa (adat-, vagy folyamat párhuzamosítás) o

Funkcionális (vagy folyamat) párhuzamosságról beszélünk a feladatmegoldás logikájából következı párhuzamosság esetében. Egymással párhuzamosan futó folyamatokat valósítanak meg, melyek közötti kommunikációt és szinkronizációt a programozónak kell megvalósítania.

o

Adatpárhuzamos. Ez a lehetıség a felhasznált adatszerkezetbıl adódik, amennyiben annak elemein a feladat megoldása során párhuzamos mőveletek végezhetıek. Ez csak bizonyos feladatköröknél fordul elı (képfeldolgozás, mérnöki számítások stb.). a programozónak a legegyszerbb esetben semmi beleszólása sincs az elkészül program processzorok közötti elosztásába. A nyelvi elemeket a könnyebb, finomabb szabályozás érdekében kiegészítik.

•

Osztott memóriával, vagy üzenetküldéssel megvalósult párhuzamosság (implicit, vagy explicit) o

Osztott

memória

könnyebben

használata

egyszerőbb,

párhuzamosíthatóak.

Azonban

a

szekvenciális

nehezebb

programok

megvalósítani

a

folyamatok szinkronizációját, kommunikációját. Minél több erıforrás áll a rendelkezésünkre annál nagyobb lehet a teljesítménykiesés a holtidık miatt, míg a szinkronizálás során a szabad maghoz rendeljük a folyamatot, szálat.

- 40 -

Többmagos processzorok programozhatósága o

Vágó Gergely

Üzenetküldés során egy folyamat üzenetet, adat csomagot küld egy másiknak. Nehezebben használható, de hatékonyabb módszer. További csoportosítási módjai: a résztvevık aktivitása szerint (szimmetrikus, aszimetrikus); üzenetek sorrendje szerint (sorrendet megırzı, nem megırzı); folyamatok közti együttmőködés alapján (szinkron, aszinkron). Fontos kérdés az üzenetek szinkronizálása, erre késıbb térünk ki.

•

A kommunikáció típusa, nyelvi eszközei A

szinkronizálást

megvalósító

lehetséges

eszközök:

szemaforokkal,

monitorokkal, aszinkron üzenetküldés, eljáráshívás, randevú, blokkolás, zárolási technikák, osztott adattípus. •

Vannak –e kifejezetten a többmagos programozást támogató eszközök A megszokott párhuzamos programozást támogató nyelvi eszközökön kívül vannak –e olyan speciális funkciók, függvények, melyek segítik a több magra történı párhuzamosítást. Ha igen, mik ezek.

3.2

C++: Pthreads

3.2.1

Ismertetés

[26]

A Pthread reprezentálja az alacsony szintő többszálú koncepciót, mely jelen van a rendszerek jelentıs részében. Egyesekben mint az operációs rendszer speciális szálainak együttese, míg másokban a természetes velejárója. Feltételezzük tudjuk, hogy mit jelen a thread és a mutex kifejezés, most ezekre nem térünk ki, csupán felhasználjuk eddigi ismereteinket róluk. A pthread könyvtár C nyelven íródott, tehát ennek megfelelı kompatibilis módon kell meghívni használatukat C++ környezetben. A következı példa reprezentálja, hogyan lehetséges ez: class threaded_class { public: threaded_class() : m_stoprequested(false), m_running(false) { pthread_mutex_init(&m_mutex); } ~threaded_class() { pthread_mutex_destroy(&m_mutex); } // Szál létrehozása, munka megkezdése void go()

- 41 -

// Megjegyzés 1


Vágó Gergely

{ assert(m_running == false); m_running = true; pthread_create(&m_thread, 0, &threaded_class::start_thread, this); } void stop() // Megjegyzés 2 { assert(m_running == true); m_running = false; m_stoprequested = true; pthread_join(&m_thread, 0); } int get_fibonacci_value(int which) { pthread_mutex_lock(&m_mutex); // Megjegyzés 3 int value = m_fibonacci_values.get(which); // Megjegyzés 4 pthread_mutex_unlock(&m_mutex); return value; } private: volatile bool m_stoprequested; // Megjegyzés 5 volatile bool m_running; std::vector m_fibonacci_values; // Ez a statikus osztály felelıs a C-stílusú pthread-hívásért static void start_thread(void *obj) { //Meghívjuk a do_work() függvényt reinterpret_cast(obj)->do_work(); } int fibonacci_number(int num) { switch(num) { case 0: case 1: return 1; default: return fib(num-2) + fib(num-1); }; } // Kiszámoljuk és lementjük a fibonacci-számokat void do_work() { int iteration = 0; while (!m_stoprequested) { int value = fibonacci_number(iteration); pthread_mutex_lock(&m_mutex); m_fibonacci_values.push_back(value); pthread_mutex_unlock(&m_mutex); // Megjegyzés 6 } } };

- 42 -


Vágó Gergely

Ugyan a kód mőködik, s egy nagyon általános használatát mutatja be a szálak alkalmazásának C++ nyelven, de van némi gyengéje, hátránya, melyek kiderülnek a megjegyzésekbıl. Megjegyzés 1 Mivel szükségünk volt egy C stílusú pointer függvény bevezetésére, a pthread_create •

go()

függvénybe végül 3 funkciót kellett alkalmaznunk:

(a publikus interfész a munka megkezdéséhez) meghívja a

pthread_create()-t, •

start_thread()-t

mely meghívja a

(a C-stílusú interfész a szál megkezdéséhez), mely végül

meghívja a •

do_work()

–t, az objektum-szintő privát belépés a szálba.

Megjegyzés 2 stop()

leállítja a szálat, s meghívja a pthread_join() függvényt, mely addig nem

tér vissza értékkel, míg a szál teljesen le nem áll. Mi történik, ha elfelejtjük meghívni a stopot? Lesz egy nem termináló szálunk, amelyet nincs mód leállítani. Legrosszabb esetben akár össze is omolhat a rendszerünk. Erre akkor kerülhet sor, amikor a threaded_class –t megsemmisíti a végrehajtási fı szál, de a do_work szál továbbra is fut, s az imént destrukált adaton szeretne dolgozni. Megjegyzés 3 pthread_mutex_lock()

akkor kerül használatra, ha kölcsönösen kizáró lockot

szeretnénk alkalmazni a m_mutex változón.. A zárak a get_fibonacci_number és a do_work

függvényeken biztosítják, hogy ha a felhasználó ki szeretné nyerni a

fibonacci értékét, nem próbál meg hozzáférni a m_fibonacci_values –hoz ugyanabban az idıben, amikor a do_work módosítja azt. Ha egy módosításra és olvasásra ugyanabban az idıben kerül sor, az nagy valószínőséggel összeomláshoz vezethet. Ez azért van, mert az std::vector osztály átméretezi magát, amikor egy új adatot adnak hozzá. Megjegyzés 4 Mi történik, ha az int = m_fibonacci_values.get(which) dob egy hibát? Ha ez bekövetkezik, a pthread_mutex_unlock függvény rögtön leáll, mintha le sem futott volna. Ha a zár soha nem oldódik fel, akkor holtpont alakul ki (lásd elızı fejezet). Ekkor egy, vagy több szál leáll, s nem tudnak semmit csinálni, mert nem képesek

- 43 -


Vágó Gergely

hozzáférni a blokkolt, egyébként számukra szükséges erıforráshoz. A fenti kód kivétel dobására hajlamos, ha a fibonacci értékre való hivatkozás, kérés még nem került kiszámításra (= megelızés). Megjegyzés 5 A m_stoprequested a kód helyesség biztosításának érdekében nélkülözhetetlen. Nélküle megvan a lehetıség olyan szituáció elıállására, amikor a szál soha nem lép ki, mivel nem tudja, hogy a m_stoprequested true értéket kapott, mert nem kap jelzést felıle. Megjegyzés 6 Ha megfeledkeznénk a pthread_mutex_unlock(&m_mutex) sorról, ugyanúgy holtpont alakulna ki, mint a Megjegyzés 4 esetén. 3.2.2

Összefoglalás

A Pthreads nyelvi lehetıségen látszik, hogy alacsony, C nyelvi szintre szánták. Ez okozza relatíve egyszerőségét, ugyanakkor a hibaforrások lehetıségét is. Sok apró, szemantikus elemre oda kell figyelni, mely megkövetelt függvényhivások kihagyásával nem várt programhibába ütközhetünk. A könyvtár kifejezetten folyamatok közti (eljárászintő) adatpárhuzamos kommunikáció támogatására íródott, osztott memória használatával. Az eszköz nem nyújt semmi újat többmagos rendszereket támogató függvények terén, a szálak (thread) létrehozása után azok vezérlése átkerül az operációs rendszer irányítása alá, legfeljebb mutex használatával védhetjük, zárolhatjuk változónk hozzáférhetıségét. •

Helyesség: alapjába véve C szintő eszköz révén az eljárások viselkedése jól definiált, azonban támogató eszközök hiányában a helyesség nehezen látható be, a mellékhatások és a rejtett függıségek felderítése nehéz.

•

Megbízhatóság, hatékonyság: a helyes implementáció függvénye. Mivel általában a legtöbb kódot elıször C-re fordítják vissza, így akár mondhatjuk, hatékony, gyors fejlesztés érhetı el használatával. A megbízhatóság rovására megy a már említett probléma: a kötelezıen meghívandó függvények elhagyása nem várt, hibás futáshoz vezethetnek. Ez a C nyelv jellegzetessége: a megbízhatóság rovására megy a hatékonyság a kimaradt futási idejő ellenırzések miatt.

•

Hordozhatóság: mivel a magok számától függetlenül létrehozott szálakat az operációs

rendszer

kezeli,

melyek - 44 -

megvédésérıl,

zárolásáról

helyes


Vágó Gergely

implementáció esetén a fejlesztı gondoskodik, így teljes mértékig hordozható kódot kaphatunk. Ugyanakkor mivel nincs nyelvi lehetıségünk beleszólni a szálak magokhoz való hozzárendeléséhez, így más rendszeren, több magon futó kódunkat nem tudjuk felkészíteni az optimalizált futásra. •

Tesztelhetıség, áttekinthetıség, egyszerőség A C nyelv elsısorban megbízhatóságáról, egyszerőségérıl, gépközeli kódjáról híres. Kritikus szakaszok kezelése nagy odafigyelést igényel, nagy számú folyamat esetén a kód átláthatóságának rovására mehet a sok mutex használata.

•

Fejlesztıi környezet Manapság egyre több fejlesztıi eszköz létezik, melyek ismerik a C, C++ nyelv szintaktikáit, belsı függvényeit. Ezek sokat segítenek a hatékonyabb, egyszerőbb fejlesztésben. Azonban a szemantikus, logikai hibákra, nem várt mellékhatásokra kevés eszköz képes felhívni a figyelmet (data race detektorok).

•

Újrahasznosíthatóság, karbantarthatóság, kompatibilitás A Pthreads szőkös nyelvi lehetıségei végett nem jelentenek problémát a fenti elvárások, mindaddig, amíg nem kell például új kritikus változót bevezetnünk, s felkészíteni az egyes szálakat annak megfelelı használatára.

•

A programozási nyelv jelentısége A C, C++ nyelv jelentıségét nem kell részletezni: komolyabb, rendszerközeli alkalmazások írása mind a mai napig segítségükkel történnek. Hatékony, biztonságos nyelvek.

3.3

C++: Boost

3.3.1

Ismertetés

[26] [29]

A Boost library (http://www.boost.org/) platform-független, nyílt forráskódú, ingyenes könyvtár, mely kibıvíti a C++ funkcióit. Legtöbbjük a Boost Software License védjegye alá tartozik, biztosítva azt mind nyílt-, mind pedig zárt forráskódú fejlesztések használatára. A jelenleg forgalomban lévı Boost körülbelül 80 egyéni könyvtárat tartalmaz,

mint

például

linear

algebra,

pseudorandom

number

generation,

multithreading, image processing, regular expressions, unit testing, string algorithms, converts, thread, mutex, pointers, stb. A legtöbbjük header-alapú, beillesztett függvényeket és sablonokat tartalmaz. [29]

- 45 -


Vágó Gergely

Boost szálak bevezettek néhány hasznos kód-spóroló tulajdonságot, jellemzıt a szálak létrehozásához, de ezek nem annyira fontosak, mint a RAII technológiák mutex vezérlése. Legegyszerőbb, ha az elızı kód átírásával (pthreads helyett boost::threads) ismerjük meg viselkedését: class threaded_class { public: threaded_class() : m_stoprequested(false) { } ~threaded_class() { } // Szál létrehozása, munka megkezdése void go() { assert(!m_thread); m_thread = boost::shared_ptr(new boost::thread(boost::bind(&threaded_class::do_work, this))); } void stop() // Megjegyzés 1 { assert(m_thread); m_stoprequested = true; m_thread->join(); } int get_fibonacci_value(int which) { boost::mutex::scoped_lock l(m_mutex); // Megjegyzés 2 return m_fibonacci_values.get(which); } private: volatile bool m_stoprequested; boost::shared_ptr m_thread; boost::mutex m_mutex; std::vector m_fibonacci_values; int fibonacci_number(int num) { switch(num) { case 0: case 1: return 1; default: return fib(num-2) + fib(num-1); }; } // Kiszámoljuk és lementjük a fibonacci-számokat void do_work() { int iteration = 0;

- 46 -


Vágó Gergely

while (!m_stoprequested) { int value = fibonacci_number(iteration); boost::mutex::scoped_lock l(m_mutex); m_fibonacci_values.push_back(value); } } };

Az elızı pthread-os példához képest az implementáció sorainak a száma 78-ról 64-re csökkent. Ez ebben az egyszerő esetben is 18%-os javulást, megtakarítást jelent. A rövidebb, könnyebben olvasható kód elınye a kevesebb hibalehetıség és a karbantarthatóság. Ezek fontos célok, illetve érvek, fıleg ha ennél összetettebb feladatról, implementációról van szó. Megjegyzés 1 Ebben a verzióban is megvan a probléma, ami az elızıben is: ha megfeledkeznénk a „stop” függvény meghívásáról, az összeomláshoz vezethet. Megjegyzés 2 A boost::mutex::scoped_lock osztály egy kényelmes RAII típusú mutex vezérlést biztosít. A pthread –es verzióban sokkal nagyobb kockázat volt, ha megfeledkeztünk a mutex feloldásáról, melyet korábban zároltunk. Ez a holtpontok felderítését nehezítette. A mostani esetben a kölcsönös kizárás hosszát a scoped_lock objektum élettartama irányítja. Ugyanis a scoped_lock megsemmisül amint kilép a hatáskörébıl. Ez garantálja, hogy soha ne feledkezzünk meg a kizárás feloldásáról. 3.3.2

Összefoglalás

A fentiek alapján mondhatnák azt, hogy ha a pthreats reprezentálná az assembly nyelvben a többszálú programozást, akkor a boost::threads reprezentálná azt a C-ben. Tehát a Boost magasabb, C++ szintő nyelv. Egyszerőbb, átláthatóbb kódot kaptunk, ugyanakkor a hibaforrások lehetısége továbbra is adott. A könyvtár sztinén folyamatok közti (eljárászintő) adatpárhuzamos kommunikáció támogatására készült, osztott memória használatával. Platformfüggetlen, ingyenes eszköz. Sajnos ez az eszköz sem nyújt semmi újat többmagos rendszereket támogató függvények terén, a szálak (boost) létrehozása után azok vezérlése átkerül az operációs rendszer irányítása alá. •

Helyesség: a helyesség belátása támogató eszközök hiányában nehéz. Különösen igaz ez párhuzamos programok esetén.

- 47 -


Vágó Gergely

Megbízhatóság, hatékonyság: A helyes implmenetáció elkészítésében sokat segít az egyszerősödött, olvashatóbb kód –hála a boost::mutex::scoped_lock osztály kínálta mutex vezérlést biztosító lehetıségeknek.

•

Hordozhatóság: Itt is érvényes mindaz, amit a Pthreads esetén már kitárgyaltunk, azaz: mivel a magok számától függetlenül létrehozott szálakat az operációs rendszer kezeli, melyek megvédésérıl, zárolásáról helyes implementáció esetén a fejlesztı gondoskodik, így teljes mértékig hordozható kódot kaphatunk. Ugyanakkor mivel nincs nyelvi lehetıségünk beleszólni a szálak magokhoz való hozzárendeléséhez, így más rendszeren, több magon futó kódunkat nem tudjuk felkészíteni az optimalizált futásra

•

Tesztelhetıség, áttekinthetıség, egyszerőség A C++ nyelv elsısorban hatékonyságáról, megbízhatóságáról híres. A Boost könyvtár mutex kezelése javított a kód egyszerőségén, értelmezhetıségén, így a kritikus szakaszok használata is egyszerősödött.

•

Fejlesztıi környezet Manapság egyre több fejlesztıi eszköz létezik, melyek ismerik a C, C++ nyelv szintaktikáit, belsı függvényeit. Ezek sokat segítenek a hatékonyabb, egyszerőbb fejlesztésben.

•

Újrahasznosíthatóság, karbantarthatóság, kompatibilitás Ismét csak az egyszerőbb, olvashatóbb kódot lehet kiemelni, amit az implementációs sorok számának csökkenése igazol.

•

A programozási nyelv jelentısége A C++ nyelv jelentıségét nem kell részletezni: hatékony, megbízható nyelv.

3.4

C++: RAII

3.4.1

Ismertetés

[26] [27]

A Resource Acquisition Is Initialization - gyakran csak egyszerően RAII-nak (vagy RIIA-nak) rövidítve- népszerő tervminta (design pattern) egyes objektumorientált programozási nyelvben, mint például a C++, D, valamint az Ada esetén. A technika Bjarne Stroustrup nevéhez főzıdik, aki a memória-felszabadítás (deallocation) problémáját szerette volna megoldani C++ -ben. E nyelvben az egyetlen kódrész, mely lefut akkor is, amikor valami kivétel következik be, az a veremben lévı objektumok

- 48 -


Vágó Gergely

destruktora. Ezért az erıforrásokat a megfelelı objektumok élettartamához kell kötni. Ez azt jelenti, hogy inicializáció során ki kell sajátítani, majd ugyanazon objektum destrukálásakor el kell engedni ıket. Így van lehetıség arra, hogy csak akkor kerüljön sor lekötésükre, amikor valóban használatban vannak. A RAII létfontosságú technika kivétel-biztos C++ kód írásához. Éppen ezért gyakran használják kölcsönös kizárás (mutex) kontrollálásához többszálú alkalmazásokban: az erıforrást foglaló objektum feloldja a zárat, amint megsemmisül. Másik tipikus használata a file-kezelés: a megnyitott file bezárása (close) a destruktor lefutásakor. [27] Ha az elızıekhez képest még több RAII utasítást használunk, akkor rövidebb, még átláthatóbb kódot kaphatunk. class threaded_class { public: threaded_class() : m_stoprequested(false), m_thread(boost::bind(&threaded_class::do_work, this)) //Megjegyzés 1 {} ~threaded_class() { m_stoprequested = true; m_thread.join(); // Megjegyzés 2 } int get_fibonacci_value(int which) { boost::mutex::scoped_lock l(m_mutex); return m_fibonacci_values.get(which); } private: volatile bool m_stoprequested; std::vector m_fibonacci_values; boost::mutex m_mutex; boost::thread m_thread; int fibonacci_number(int num) { switch(num) { case 0: case 1: return 1; default: return fib(num-2) + fib(num-1); }; } // Kiszámoljuk és lementjük a fibonacci-számokat void do_work() { int iteration = 0;

- 49 -


Vágó Gergely

while (!m_stoprequested) { int value = fibonacci_number(iteration); boost::mutex::scoped_lock l(m_mutex); m_fibonacci_values.push_back(value); } } };

A RAII módszert használva az elızı boost::threads példához képest további implementáció-csökkenést tapasztalhatunk: 64 sorról 52 sorra csökkent a kód, ez 20%os megtakarítás. Összességében 35%-os csökkenést tapasztaltunk az eredeti pthreads-es verzióhoz képest. Megjegyzés 1 Ebben a verzióban a szálat a "threaded_class" objektum konstruktorában inicializáljuk. Fontos, hogy a m_thread legyen az utolsó objemtum, amit létrehozunk, ez egyszerően azzal biztosítható, hogy utoljára deklaráljuk. Miért is fontos ez? Mert a szál más objektumokat is használ ebbıl az osztályból, így mikor létrehozzuk, szükséges, hogy minden a rendelkezésére álljon. Megjegyzés 2 A destruktorban van egy join mővelet a szálon. Mivel a thread az utolsó dolog, amit létrehozunk, így annak kell lennie az elsınek, amit megsemmisítünk. A join parancs kiadásával elértük, hogy elıbb leálljon, mint a tıle függı objektumok. 3.4.2

Összefoglalás

Az elızı fejezet záró kijelentését követve: ha a boost::threads reprezentálja a C nyelv többszálú programozását, akkor a RAII a C++ nyelvét. A Boost-nál is egyszerőbb, átláthatóbb kódot kaptunk, s a hibaforrások lehetısége is csökkent a destruktorok megfelelı alkalmazása miatt. A nyelv elfedi a programozó elıl a kommunikációs módszereit, egységes felületet biztosítva. Elsısorban sztinén folyamatok közti (eljárászintő) adatpárhuzamos kommunikáció támogatására készült, osztott memória használatával. Viszont létezik egy kiegészítése, az MPI (Message Passing Interface) Ez a programok közötti üzenetek útján való pont-pont közti kommunikáció biztosítását írja le. Sajnos ez az eszköz sem nyújt semmi újat többmagos rendszereket támogató függvények terén. •

Helyesség: a C++ nem támogatja a helyességbizonyítást.

- 50 -


Vágó Gergely

Megbízhatóság, hatékonyság: egy jól használható C++ könyvtári kiegészítés, a nyelv eddigi kellemes tulajdonságaival együtt. A tervmintának köszönhetıen kivételbiztos kódot kaphatunk, a nem várt mellékhatások okozta programhibák így könnyebben elkerülhetıek.

•

Hordozhatóság: Itt is érvényes mindaz, amit az elızı nyelvi eszközök esetén már kitárgyaltunk.

•

Tesztelhetıség, áttekinthetıség, egyszerőség A RAII használatával mégrövidebb, mégegyszerőbb kódot kapunk. Ez tovább növeli az áttekinthetıséget.

•


•

Újrahasznosíthatóság, karbantarthatóság, kompatibilitás Ismét csak az egyszerőbb, olvashatóbb kódot lehet kiemelni, amit az implementációs sorok számának további csökkenése igazol

•

A programozási nyelv jelentısége A C++ nyelv jelentıségét nem kell részletezni: hatékony, megbízható nyelv.

3.5 3.5.1

OpenMP Ismertetés

[28]

Az OpenMP API (alkalmazás-, vagy felhasználói program interfész) a multirendszerek osztott-memóriájú párhuzamos programozását támogató környezet C/C++ és Fortran nyelveken, minden architektúrán, beleértve a Unix– és Windows NT platformokat is. Az OpenMP egy hordozható, alakítható modell lett, mely egyszerő, rugalmas fejlesztıi környezetet, felületet biztosít a programozóknak osztott erıforrású, párhuzamos mőködéső alkalmazások írásához, legyen szó akár asztali-, akár szuperszámítógéprıl. Hibrid modellel épített párhuzamos alkalmazások futtathatók mind OpenMP, mind pedig Message Passing Interface (MPI) számítógépes rendszerek alatt, sıt, az OpenMP kiterjesztéseivel akár egyszerő (nem-parellel) mőködéső gépeken is.

- 51 -


Vágó Gergely

Az OpenMP egy multithreading implementácó, módszer, ahol a „mester” szál fork-ol, létrehoz meghatározott számú „szolga„ szálat, melyek között elosztásra kerül a feladat (task). Ezek utána a szálak konkurens módon futnak, miközben a futást felügyelı környezet kiosztja azokat az egyes processzoroknak, illetve magoknak. Minden szálnak van egy „id”-je, azonosítja, melyet akkor kap, amikor meghívjuk a szükséges függvényt (omp_get_thread_num() C/C++ alatt és OMP_GET_THREAD_NUM() Fortran nyelven). A szálak azonosítója integer típusú, közülük a mesteré a nullás. A párhuzamos kódrész lefutása után a szálak visszacsatlakoznak (join) a mester szálba, mely folytatja feladatait a program futásának befejezéséig. Alapértelmezetten minden egyes szál független módon hajtja végre feladatait a párhuzamos kódrészen belül. Lehetıség van feladatok felosztására a szálak között, így mindegyik a neki kiosztott kódját futtatja. E módon az OpenMP feladat – és adat párhuzamosításra is használható. Ahogy azt az elızı fejezetekben tárgyaltuk, a futási környezet a szerint osztja el a szálakat a processzorok, illetve a magok között, hogy mennyi azok kihasználtsága. [28]

A szálak létrehozásának vázlatos mőködése: Task I-II-III: párhuzamos feladatok; A,B,C,D: szálak

Az OpenMP függvényeit az „omp.h” header file tartalmazza C/C++ nyelvek esetén. Az OpenMP építıelemei Az OpenMP alapvetı elemei

a következık: thread creation, work sharing, data

environment management, thread synchronization, user level runtime routines and environment variables. Azaz sorban: szál létrehozás, munkamegosztás, környezet vezérlés, szinkronizálás, felhasználó-szintő futási rutinok, függvények és környezet változók. Az alábbi kép példákkal kiegészítve szépen összefoglalja ezeket. [28]

- 52 -


Vágó Gergely

Az OpenMP elemei, kiterjesztései

Munkamegosztás Itt került meghatározásra, hogy ruházzuk át az egyes független (rész-)feladatokat egy, vagy akár az összes szálnak. •

omp for, vagy omp do: ciklus iterációinak felosztása a szálak között

•

sections: egymást követı, független kód blokkok elosztása szálak között

•

single: meghatároz egy kód blokkot, mely pontosan egy szálon futhat. barrier-t tartalmaz a végén

•

master: hasonló a single-hez, de a kódrész csak és kizárólag a mesteren futhat. Nincs szükség barrier-re a végén

A következı rövid, egyszerő példaprogramban, az eddigi elemek felhasználásával egy „Hello World” programot írunk, ahol a mester szál (id = 0) csak az alapvetı információkat jeleníti meg, míg a szolga szálak mind kapnak egy-egy rövid idıszeletet, ahol kiírják azonosítójukat. #include #include <stdio.h> #include <stdlib.h> #include int main (int argc, char *argv[]) { int nthreads, tid; /* Szálak csoportjának forkolása, saját másolat-változóikkal */ #pragma omp parallel private(nthreads, tid) { /* Szálak számán meghatározása */ tid = omp_get_thread_num(); printf("Hello World from thread = %d\n", tid); /* Csak a mester szál csinálja ezt */

- 53 -


Vágó Gergely

if (tid == 0) { nthreads = omp_get_num_threads(); printf("Number of threads = %d\n", nthreads); } // Mindenki dolgozik egy kicsit double d; for (int i=0;i<1000000000;i++) { d += sqrt(i); if (i%100000000==0) printf("(%d %d) ",i/100000000,tid); } }

/* Minden szál csatlakozik a mesterhez, s megszünik */

}

Természetesen az OpenMP esetén is szükséges, hogy a kódban lévı változók láthatóságát, hozzáférhetıségét állíthassuk. Sıt, ez különösen fontos, hiszen van, mikor elengedhetetlen, hogy egy globális változóhoz minden szál hozzáférhessen, ugyanakkor más esetekben pedig biztosítani kell ennek épp ellenkezıjét, a privátságot. Ez utóbbi a versenyhelyzetek elkerülése végett különösen fontos. Az alábbiakban a változókhoz rendelhetı láthatósági és szinkronizálási lehetıségek kerülnek részletezésre. [28] Láthatósági tulajdonságok •

shared: az adat a párhuzamos részen belül megosztott, látható, amit annyit jelent, hogy minden szál számára látható és hozzáférhetı egyidejőleg. Alapértelmezetten minden változó shared típusú, kivéve a ciklusváltozók.

•

private: az adat a párhuzamos régión belül privát minden szál számára, azaz minden szálnak van egy saját másolata róla, s átmeneti változóként használja. A párhuzamos részen kívül ez a privát változó nem inicializálódik, így nem látható és nem használható ott. Alapértelmezetten a ciklusváltozók private-k.

•

default: lehetıvé teszi a programozónak, hogy beállítsa az alapértelmezett hatáskört a párhuzamos részen belül, attól függetlenül, hogy shared, vagy nem (C/C++), illetve shared, firstprivate, private, vagy nem (Fortran).

•

firstprivate:mint a private, kivéve, hogy kezdıértéket kap.

•

lastprivate: mint a private, kivéve, hogy kezdıértéket kap a konstruktor után.

•

reduction: a konstruktor utáni join biztonságos módja.

Szinkronizálási lehetıségek •

critical section: a zárolt kódrész csak egy szálon futhat egy idıben, s nincs lehetıség egyidejő, több szálon való futásra. Általában arra használjuk, hogy megvédjük adataink a versenyhelyzettıl.

- 54 -


Vágó Gergely

atomic: hasonló a critical section -höz, de a fordító speciális hardver utasításokat ajánl fel a jobb, eredményesebb futás érdekében. Elıfordulhat, hogy fordító megtagadja a felhasználó ezen javaslatát és critical section –t használ helyette.

•

ordered: a strukturált blokk egy szekvenciális ciklus iterációinak megfelelı sorrendjében hajtódik végre.

•

barrier: minden szál addig vár, míg az összes többi - egy csoporton belül - el nem éri ezt a pontot.

•

nowait: meghatározza, hogy az egyes szálaknak mely, hozzájuk beosztott feladatok elvégzéséhez nem kell megvárniuk társait. Ennek a hiányában a szálak összeakadnak a barrier szinkronizálással a munkamegosztás végén.

Ütemezési lehetıségek •

schedule(type, chunk): Hasznos, ha a munkamegosztás do-loop, vagy for-loop szerkezető. A megosztáson belüli iteráció(k) azon szálakhoz kerülnek beosztásra, melyek összhangban vannak a most definiálandó ütemezı metódusokkal:

1. static: Itt minden szál allokált, mielıtt végrehajtanák a ciklus iterációit. Az egyes mőveletek alapértelmezetten egyenlıen vannak szétosztva a szálak között. Mindemellett lehetıség van egy integer értéknyi (chunk paraméter) összefüggı iterációt kiosztani az egyes szálaknak. 2. dynamic: Ebben az esetben az iterációk egy része kevesebb szálnak van allokálva. Amikor az egyik szál végez a saját mőveletével, visszatér egy újabbért. A paraméter határozza meg, hogy egymás után hány mőveletet végezhet ily módon egy szál. 3. guided: Nagy mennyiségő összefüggı iteráció van hozzárendelve minden egyes szálhoz dinamikusan (mint fentebb). A chunk mérete exponenciálisan csökken minden, egymást követı allokációval, míg el nem éri a minimumként specifikált chunk méretet. További szál összehasonlási lehetıség a más nyelvekben is megszokott if. Lehetıvé teszi, hogy a szálak csak akkor párhuzamosítsák a feladatot, ha teljesül az adott feltétel. Különben a kódrész soros módon fut tovább. 3.5.2

Összefoglalás

Hibrid modellel épített párhuzamos alkalmazások futtathatók, azaz mind funkciónális, mind pedig adatpárhuzamos módon. Tehát a végrehajtás és a feladat független.

- 55 -


Vágó Gergely

Egyszerő, rugalmas fejlesztıi környezetet. Nagy lehetıségeket kínál szálak típusainak, láthatóságainak,

ütemezésének,

valamint

szinkronizálásának

beállításához.

Multiplatform (Linux, Win), „multinyelv” (C, C++, Fortran). Sajnos ez az eszköz sem nyújt semmi újat többmagos rendszereket támogató függvények terén. •

Helyesség:. a helyesség belátása C,C++ nyelvek esetén támogató eszközök hiányában nehéz. Különösen igaz ez párhuzamos programokra.

•

Megbízhatóság, hatékonyság: egy jól használható C, C++ könyvtári kiegészítés, a nyelv eddigi tulajdonságaival együtt. A rendelkezésre álló lehetıségek miatt megbízható, hatékony kódot tudunk írni, minimális módosítással.

•

Hordozhatóság, tesztelhetıség, áttekinthetıség, egyszerőség Minimális kódmódosítással használható, tehát egyszerő, áttekinthetı és annyira hordozható nyelvi eszköz, mint amely környezetben meghívtuk.

•


•

Újrahasznosíthatóság, karbantarthatóság, kompatibilitás Platform – és „nyelvfüggetlenség”.

•

A programozási nyelv jelentısége Több nyelven is használható eszköz - köztük a C, C++ -, ezért ez jelentıs érv mellette.

3.6

C#: .NET framework 3.5

3.6.1

Ismertetés

3.6.1.1

MatrixMultiplication

[34]

A Microsoft a .NET framework 3.5 egy könyvtári kiegészítésével lehetıvé vált, hogy párhuzamos számításokat oszthassunk szét rendszerünkben lévı magok között. E eszközök rendkívül hasznosak, használatuk egyszerő és sok, különféle tulajdonságot biztosít párhuzamos problémáink megoldásához. Vegyük például az alábbi egyszerő nem-párhuzamos kódrészletet, mely összead két mátrixot.

- 56 -


Vágó Gergely

void MatrixMultiplication( double[,] a, double[,] b, double[,] c ) { int s = a.GetLength( 0 ); for ( int i = 0; i < s; i++ ) { for ( int j = 0; j < s; j++ ) { double v = 0; for ( int k = 0; k < s; k++ ) { v += a[i, k] * b[k, j]; } c[i, j] = v; } } }

A fenti kód párhuzamosított változata: void ParalleledMatrixMultiplicationMS( double[,] a, double[,] b, double[,] c ) { int s = a.GetLength( 0 ); System.Threading.Parallel.For( 0, s, delegate( int i ) { // PARALLEL CIKLUS for ( int j = 0; j < s; j++ ) { double v = 0; for ( int k = 0; k < s; k++ ) { v += a[i, k] * b[k, j]; } c[i, j] = v; } } ); }

Nem történt szinte semmi változás, csupán meghívtuk a Microsoft szálkezelı függvényét, a Parallel.For –t, mely elvégzi helyettünk a külsı ciklus megosztását az erıforrások között. Természetesen ennél jóval többet tartalmaz és tud a szóban forgó könyvtári kiegészítés. Azonban semmi sem lehet tökéletes, vannak apróbb hibái: •

Ez a fajta párhuzamos számítási kiegészítés csupán a 3.5 verziótól érhetı el. Ez azért probléma, mert a korábbi framework alkalmazásink nem tudjuk átírni, mert nem feltétlenül kompatibilis felfelé. A 2.0 –s verziójú programjaink nem tudjuk ezzel az eszközzel párhuzamosítani.

•

A standard .NET framework nem tartalmazza ezt a fajta kiegészítést, parancskészletet. Tehát magunknak kell gondoskodni a telepítésérıl, ami okozhat némi problémát (kompatibilitás, megfelelı környezet, beállítások, stb).

•

A Microsoft ezen kiegészítéseit Windows rendszerre szánták. Tehát ha más rendszereken is futó alkalmazásokra szeretnénk fejleszteni, mint amiknek Linuxon

- 57 -


Vágó Gergely

is futniuk kell, például a Mono környezeten, akkor nélkülöznünk kell ezt a lehetıséget. Az AForge.NET 2.0 -tól már tartalmaz Mono támogatást, tehát a .NET alkalmazások már nem csak Windows, de Linux és Mac rendszeren is futhatnak. Továbbá ettıl a verziótól már a Multi- core/CPU kiegészítéseket is magába foglal. [34] Tehát bizonyos környezetek, rendszerek esetén szükség lehet egy általánosabb Parallel.For()

implementációra, mely ugyanúgy használható a korábbi .NET

verziókban, mint például Linux alatt - kisebb DLL változások eszközölése után. Ugyan a példákban csak a párhuzamosított ciklus általánosításáról lesz szó (mely általában a legfontosabb, legsőrőbben használat eleme a kódoknak), de hasonló lehetıségek adottak további programozási elemekre is. Az általánosabb kód A cél tehát egy, a Microsoft -éhoz közel álló általános, könnyen használható implementáció létrehozása. void ParalleledMatrixMultiplicationAForge ( double[,] a, double[,] b, double[,] c ) { int s = a.GetLength( 0 ); AForge.Parallel.For( 0, s, delegate( int i ) { for ( int j = 0; j < s; j++ ) { double v = 0; for ( int k = 0; k < s; k++ ) { v += a[i, k] * b[k, j]; } c[i, j] = v; } } ); }

Szemmel látható különbség a namespace, ahol a Parallel osztály definíciója található: // Microsoft megoldása System.Threading.Parallel.For( 0, s, delegate( int i ) // a mi implementatációnk AForge.Parallel.For( 0, s, delegate( int i ) További különbség, hogy a Microsoft Parallel.For()

definíciója nem csak delegált-,

de lambda kifejezésekre is mőködik. A részletek Párhuzamos implementációnk a System.Threading névtér használatára épül, mely minden .NET verzió része. A parallel for-ciklushoz létre kell hoznunk bizonyos számú - 58 -


Vágó Gergely

szálat, melyek feladata a cikluson belüli iterációk futtatása lesz. Alapértelmezetten annyi szálat fogunk létrehozni, ahány mag van rendszerünkben. Ez a szám természetesen utólag módosítható, például a Microsoft megoldása dualcore esetén is több mint két szálat hoz létre –sıt, a gyakorlat is azt mutatja, hogy kicsivel több szál létrehozása javíthat a hatékonyságon. // Parallel osztály inicializálása, // szálak és szinkronizáló objektumok létrehozása private void Initialize( ) { // események listája, rendelkezésre álló munkákról értesít jobAvailable = new AutoResetEvent[threadsCount]; // események listája, rendelkezésre álló szálakról értesít threadIdle = new ManualResetEvent[threadsCount]; threads = new Thread[threadsCount]; // szálak tömbje for ( int i = 0; i < threadsCount; i++ ) { jobAvailable[i] = new AutoResetEvent( false ); threadIdle[i] = new ManualResetEvent( true ); threads[i] = new Thread( new ParameterizedThreadStart( WorkerThread ) ); threads[i].IsBackground = true; threads[i].Start( i ); } }

A két eseményfigyelı logikája a következı: A threadIdle jelet küld, ha egy thread nem csinál semmit (munkavégzésre alkalmas). A jobAvailable pedig felébreszt egy szálat ha az szabad. Tehát inicializálás után, a threadIdle esemény beállítja a kezdı értékeket, amikor minden szál várja a feladatát (signaled), míg a feladatok pedig nem kerültek még kiosztásra(non-signaled). Nézzük, hogyan kerülnek a munkák ütemezésre: public static void For( int start, int stop, ForLoopBody loopBody ) { lock ( sync ) { // a parallel számítást vezérlı példánya Parallel instance = Instance; instance.currentIndex = start - 1; instance.stopIndex = stop; instance.loopBody = loopBody; //jelzés a szabad munkákról a szálak felé, elfoglaltra állítás for ( int i = 0; i < threadsCount; i++ ) { instance.threadIdle[i].Reset( ); instance.jobAvailable[i].Set( ); } // várakozás, míg minden szál szabad nem lesz for ( int i = 0; i < threadsCount; i++ ) { instance.threadIdle[i].WaitOne( ); } } )

- 59 -


Vágó Gergely

A fenti kódból látszik, hogy a munkák elosztása mennyire egyszerő: elmentjük a ciklus változóit, megjelöljük a dolgozó szálakat (threadIdle[i].Reset( )), a munkákat (jobAvailable[i].Set( )), s megvárjuk amíg újra szabadok lesznek. Az utolsó lépés, a dolgozó szálak mőködésének megvizsgálása: // A dolgozó szál megkezdi parallel mőködését a ciklusban private void WorkerThread( object index ) { int threadIndex = (int) index; int localIndex = 0; while ( true ) { // Vár az új feladatara, amíg nincs dolga jobAvailable[threadIndex].WaitOne( ); // Kilép ha: if ( loopBody == null ) break; while ( true ) { // megkapja a globális ciklusváltozó index-értékét localIndex = Interlocked.Increment( ref currentIndex ); if ( localIndex >= stopIndex ) break; // ciklus törzsének futása loopBody( localIndex ); } // jel a szál rendelkezésre állásáról threadIdle[threadIndex].Set( ); } }

Tehát a dogozó szálak csak várnak, s nem csinálnak semmit, amíg nem kapnak feladatot a jobAvailable eseménytıl. Amint ez a jelzés megérkezik, nekiállnak a munkájuknak: megkapják a ciklus indexváltozójának értékét, amivel biztonságosan tudnak dolgozni, kiszámolni a ciklus törzsében szereplı mőveleteket(egymásba illesztett növelést). Teljesítmény tesztek Nincs más hátra, mint tesztelni a fenti egyszerő, általánosított kódunkat, összehasonlítva Microsoft megoldásával. Ennek módszere a következı technikával fog zajlani: lefuttatjuk a ciklusokat, s megmérjük, mennyi idıt vettek igénybe: // Különbözı számú teszt futtatása for ( int test = 0; test < tests; test++ ) { // test 1 DateTime start = DateTime.Now; for ( int run = 0; run < runs; run++ ) { MatrixMultiplication( a, b, c1 ); } DateTime end = DateTime.Now;

- 60 -


Vágó Gergely

TimeSpan span = end - start; Console.Write( span.TotalMilliseconds.ToString( "F3" ) + "\t | "); test1time += span.TotalMilliseconds; ...

Többször lefuttatjuk a teszteket, így a végén kell kapjunk egy összesítı teljesítményt: // átlag teljesítmény kiiratása test1time /= tests; test2time /= tests; test3time /= tests; Console.WriteLine( "------------------Console.WriteLine( test1time.ToString( test2time.ToString( test3time.ToString(

AVG -------------------" ); "F3" ) + "\t | " + "F3" ) + "\t | " + "F3" ) + "\t | " );

A teszteket egy Intel Core 2 Duo CPU - 2.2 GHz processzoron végeztük: Mátrix mérete: 50, futtatások: 200 Teszt kezdése 2 szálon

Mátrix mérete: 100, futtatások: 100 Teszt kezdése 2 szálon

Clear C# | AForge | MS | 156.250 | 109.37 | 218.750 | 171.875 | 93.750 | 125.000 | 156.250 | 109.375 | 109.375 | 171.875 | 93.750 | 125.000 | 156.250 | 93.750 | 125.000 | ------------------ AVG --------162.500 | 100.000 | 140.625 |

Clear C# | AForge | MS | 687.500 | 390.625 | 515.625 | 718.750 | 390.625 | 406.250 | 703.125 | 390.625 | 406.250 | 687.500 | 390.625 | 406.250 | 734.375 | 390.625 | 406.250 | ------------------- AVG ---------706.250 | 390.625 | 428.125 |



Clear C# | AForge | MS | 4453.125 | 2484.375 | 2593.750 | 4609.375 | 2500.000 | 2500.000 | 4515.625 | 2484.375 | 2500.000 | 4546.875 | 2484.375 | 2500.000 | 4671.875 | 2500.000 | 2500.000 | ------------------ AVG --------4559.375 | 2490.625 | 2518.750 |

Clear C# | AForge | MS | 133078.125| 72406.250| 72531.250 | 134875.000| 72718.750| 72406.250 | 135296.875| 72578.125| 72375.000 | 135484.375| 72531.250| 75062.500 | 136500.000| 72515.625| 72343.750 | ------------------- AVG ---------135046.875| 72550.000| 72943.750 |

A fentiekbıl az derül ki, hogy az implementációnk nem rosszabb –sıt, mi több, jobb eredményeket is mutat-, mint a Microsoft megoldása. Természetesen nincs meg az a fajta flexibilitás, egyszerőség, de a lényeg, hogy a korábbi .NET verziókon is kitőnıen fut –így például a már korábban említett Mono alatt is. Látható továbbá, hogy ahogy csökkentettük a mátrix méretét, úgy a teljesítmény javulása nem annyira nyilvánvaló, mivel a munka mennyisége már túl kevés a párhuzamossághoz. További érdekesség, hogy az MS elsı futásra mindig rosszabb eredményt produkál, míg az AForge megoldás viszonylag egyenleteset. Jól bevált, s hatásos gyakorlat, ha kód optimalizálás elıtt elvégzünk pár tesztet, így késıbb láthatjuk a különbséget. Elıfordulhat akár az is, hogy azt hisszük sokat javítottunk, gyorsítottunk a kódunkon, de az újabb tesztek eredménye pont az

- 61 -


Vágó Gergely

ellenkezıjét mutatják. A párhuzamosítás nem mindig jelent orvosságot a teljesítményre. Tipikus példája ennek, a már fentebb említett eset: ha kevés a párhuzamosítható munka, akkor több idıt vesztünk a szálak szinkronizálásával. Ezt az esetet demonstrálva csökkentsük a mátrix méretét: Mátrix mérete: 10, futtatások: 1000 Teszt kezdése 2 szálon Clear C# | AForge | MS | 0.000 | 46.875 | 156.250 | 15.625 | 15.625 | 46.875 | 0.000 | 15.625 | 46.875 | 0.000 | 15.625 | 46.875 | 0.000 | 15.625 | 31.250 | ------------------- AVG ---------3.125 | 21.875 | 65.625 |

Konklúzió Sikerült készítenünk egy általános, korábbi .NET verziókkal kompatibilis megoldást párhuzamos program írásához, a Parallel.For() implementációval, mely jó teljesítményt mutat. A loop-ciklus párhuzamosításával pedig sok párhuzamos folyamat egyszerően megoldható. 3.6.1.2

QuickSort

A mátrixon alapuló adatpárhuzamos mővelet mellett jó szemléltetı eszközök a rendezı algoritmusok is. A Quicksort egyszerően párhuzamosítható: részfeladatok, részeredmények feldolgozása. A következı példák a Parallel FX könyvtárat használják. Az általános Quicksort függvény így néz ki: private void QSort(int left, int right) { if (right > left) { int pivotIndex = GetPivotIndex(left, right); int pivotNewIndex = Partition(left, right, pivotIndex); QSort(left, pivotNewIndex - 1); QSort(pivotNewIndex + 1, right); } }

Az elsı teszt eset az ismert thread funkciót használja a rendezéshez. Ennek elınyei: •

Nincs szükség további könyvtári eszközökre.

•

Benchmark tesztek jó eredményt mutatnak.

public void SortParallelThreads(T[] array) { this.array = array; int pivotIndex = GetPivotIndexParallel(array); // get pivot index

- 62 -


Vágó Gergely

Thread sort1 = new Thread(new ThreadStart(delegate() { QSort(0, pivotIndex); // az array elsı részének rendezése ((AutoResetEvent)(waitHandles[0])).Set(); // jel: a rendezés kész })); Thread sort2 = new Thread(new ThreadStart(delegate() { QSort(pivotIndex + 1, array.Length - 1); // az array második részének rendezése ((AutoResetEvent)(waitHandles[1])).Set(); })); sort1.Start(); // szálak indítása egymás után sort2.Start(); WaitHandle.WaitAll(waitHandles); // várakozás, míg minden rendezı szál el nem végzi munkáját }

A következı megvalósítás a Microsoft Parallel kiegészítést használja a .NET Framework 3.5. –höz. A Parallel FX elınyei: •

Nincs szükség szálon belüli szinkronizációra (a fı szál gondoskodik róla)

•

Legrövidebb kód.

public void SortParallelFX(T[] array) { this.array = array; int pivotIndex = GetPivotIndexParallel(array); Parallel.Do(delegate() { QSort(0, pivotIndex); }, delegate() { QSort(pivotIndex + 1, array.Length - 1); }); }

Az utolsó eset a ThreadPool osztályt használja a szálak sorbarendezéséhez: public void SortParallelThreadPool(T[] array) { this.array = array; int pivotIndex = GetPivotIndexParallel(array); ThreadPool.QueueUserWorkItem(new WaitCallback(delegate(object x) { QSort(0, pivotIndex); ((AutoResetEvent)(waitHandles[0])).Set(); })); ThreadPool.QueueUserWorkItem(new WaitCallback(delegate(object x) { QSort(pivotIndex + 1, array.Length - 1); ((AutoResetEvent)(waitHandles[1])).Set(); })); WaitHandle.WaitAll(waitHandles); }

- 63 -


Vágó Gergely

Az eredmények összefoglalása: Minden egyes quicksort metódust lefuttatva tíz alkalommal, véletlenszerő számú 10^7 integer tömbön a következıket tapasztalhattuk: A gyors rendezés jelentısen függ a tömb struktúrájától és elemeitıl. Ez ad magyarázatot arra a kérdésre, hogy miért nem kétszer (vagy többször) olyan gyors a párhuzamos teszt, mint a lineáris. Test

1

2

3

4

5

6

7

8

9

10

Avr.

Linear

6.05

5.93

5.91

5.87

5.88

5.94

5.82

5.79

5.77

5.82

5.88

Parallel FX

3.85

5.76

3.85

3.73

4.1

5.91

4.59

3.57

4.24

5.04

4.47

Threads

3.65

5.73

3.68

3.87

4.2

5.84

4.4

3.53

4.15

4.91

4.39

ThreadPool

3.82

5.83

3.85

4.06

4.2

5.96

4.65

3.71

4.34

5.23

4.56

Array.Sort(..)

1.7

1.7

1.7

1.68

1.69

1.7

1.7

1.7

1.68

1.69

1.7

Látható, hogy a beépített, “pure .NET” rendezés, az Array.Sort() minden tesztet megnyert. Ennek oka elsısorban a szálkezelı funkciók meghívásakor a háttérben zajló többletmunka, a feladatok kiosztásával járó elveszett sok idı. Konklúzió A Task Parallel Library (TPL) arra lett kifejlesztve, hogy sokkal egyszerőebben sikerüljön olyan kódot írni, mely automatikusan kihasználja a rendelkezésünkre álló processzorokat, magokat. A könyvtár használatával egyszerően átírható a szekvenciális formában megírt kód párhuzamossá a többlet erıforrások (magok) felhasználásával. Ugyanez a helyzet az általános thread eszközök, valamint a ThreadPool használatával. Azonban a ParallelFX óriási elınye, hogy kihasználja az összes rendelkezésére álló processzort, magot párhuzamos mőveletvégzés céljából. A programozóknak nem kell aggódniuk, hogy a CPU erıforrásai kiaknázatlanul állnak, lehet az akár egymagos, vagy többmagos. Akár a Parallel.For, vagy a Parallel.Do függvényekrıl beszélünk, mind jobb teljesítményt mutat több magú processzorokon (igaz, alkalmazásfüggı, hogy mekkora a gyorsulás), s a legnagyobb elınyük, hogy nincs szükség a kód megváltoztatására. A CPU kihasználtsága a tesztek alatt 100% -os mőködést mutat minden mag esetén.

- 64 -


3.6.2

Vágó Gergely

Összefoglalás

A C#, illetve a .NET elınye mindig is a fejlesztı-barát környezet, függvények biztosítása és megoldása volt. A nyelv lehetıséget kínál az ismertetett kiegészítésekkel mind szintő párhuzamosság megvalósítására: utasításszinttıl (alapvetı mátrixösszeadó mőveletek), az eljárásszinten át (thread) a programszintőig (erre nem volt példa, de nem nehéz elképzelni, hogy egy-egy önálló modul kommunikációját, saját részeredmények kiszámítását). A párhuzamosság típusa megközelítés- és implementáció függı, a lehetıségek adottak, tehát hibrid rendszerrıl beszélhetünk C# esetén. Elsısorban osztott memória használatával folyik az adatok megosztása. A többmagos párhuzamos programozás, annak támogatása és mőködése a fejlesztı elıl rejtve marad, az eszköz az operációs rendszerrel együtt végzi azt. A tesztek alapján pedig látható, hogy jó hatásfokkal. •

Helyesség: A C# erısen objektumorientált nyelv, ezért a helyesség bizonyítása már komolyabb feladat, fıleg ha kombináljuk a párhuzamos programozással. Azonban létezik könyvtári kiegészítés: Code Contracts Library, elı-utófeltételek bevezetésén alapul.

•

Megbízhatóság, hatékonyság: Az objektumok helyesen használt destruktoraival elkerülhetjük a nem várt meglepetéseket, a nyelv kiváló eszközöket nyújt a kivételek kezeléséhez, a tesztek pedig igazolják a hatékonyságot.

•

Hordozhatóság, tesztelhetıség, áttekinthetıség, egyszerőség Az eszköz elrejti a fejlesztı elıl a rendelkezésre álló erıforrásokat, magokat, az operációs rendszerre bízza a szálak kezelését, elosztását a magok között. Így egyszerő kódot kapunk. Ez biztosítja a hordozhatóságot is. Láthattuk továbbá, hogy a szekvenciális kód minimális módosításával hatékony, rugalmas, környezetfüggetlen kódot kaputnk.

•

Fejlesztıi környezet A .NET grafikus fejlesztıi környezete (Microsoft Visual Studio) sok lehetıséget nyújt programjaink helyes mőködésének eléréséhez, hatékony megírásához.

•

Újrahasznosíthatóság, karbantarthatóság, kompatibilitás

- 65 -


Vágó Gergely

Elsısorban Windows platform (System.Threading.Parallel.For), de a bemutatott általánosabb megoldások, kódok Linux környezeten is mőködnek, komolyabb elımunkálatok nélkül. Különbözı rendszerek között pedig a könyvtári eszköz által biztosított, a fejlesztıtı elıtt rejtett belsı funkciók biztosítják a helyes mőködést, kompatibilitást, csak a megfelelı kiegészítés megléte, impotrálása szükséges a legtöbb esetben. •

A programozási nyelv jelentısége Utóbbi idıben egyre nagyobb a Visual Studio sikere, különösen grafikus alkalmazások írása. Ezért fontos, hogy e fejlesztıi környezetre is létezzenek párhuzamosságot támogató könyvtári eszközök.

3.7

Haskell

3.7.1

Ismertetés

[5][24]

A Haskell tisztán funkcionális (deklaratív), lusta kiértékeléső, polimorf típusokat és magasabb rendő függvényeket tartalmazó erısen típusos programozási nyelv, alapja a lambda-kalkulus. A nyelv ezzel meglehetısen különbözik a ma általában használatos nyelvektıl. Haskell Brooks Curry amerikai matematikusról kapta a nevét, aki a matematikai logikában kifejtett munkássága révén hozzájárult a funkcionális nyelvek elméleti alapjainak fejlıdéséhez. A nyelv sajátosságai, valamint az általános strukrált és objektumorientált nyelvekhez képest megkövetelet eltérı gondolkodásmód miatt nehezen érthetı és programozható környezet. Ezek ellenére – vagy éppen pont ezek miatt – egy jól megírt Haskell kód hatékonyabb mőködést biztosíthat a mai divatos nyelveken megírt programokhoz képest. Ettıl függetlenül miért volna érdemes párhuzamos alkalmazásokat készíteni segítségével? Erre rögtön választ kapunk: Haskell és a párhuzamosság – Miért? •

Tisztaság, lustaság, típusosság = több párhuzamosság a kódban

•

Nincs meghatározott végrehajtási sor

•

Kivétel – és párhuzamos biztos

•

Magasszintő

•

Erısen típusos és optimalizált, megbízható teljesítmény

•

Egyedi multi-core futási idı: nagy teljsítményő szálak, mint legfontosabb tényezı

•

Megbízhatóság, hatékonyság: jelentıs könyvtári rendszer

20

évnyi

- 66 -

kód

szintő,

ipari

használat,


Vágó Gergely

Programozás és fordítás Haskell nyelven Fontos, hogy a dolgozat ezen fejezetének nem célja az alapvetı, egyszerő nyelvi elemek ismertetése. Épp ellenkezıleg: erısen támaszkodunk azokra, feltételezzük meglétüket, s kibıvítjük továbbiakkal, melyek hozzásegítenek majd párhuzamos mőködéső Haskell program írásához. Párhuzamos Haskell kód fordítása a –threaded paraméter segítségével: $ ghc -O2 --make -threaded Foo.hs [1 of 1] Compiling Main ( Foo.hs, Foo.o ) Linking Foo …

Annak meghatározása, hogy végrehajtáskor mennyi valós (OS) szál rendelıdjön a Haskell logikai szálaihoz: $ ./A +RTS -N8

Ebben az esetben a „szál” a Haskell logikai szálait jelenti, nem a 8 rendszerszintőt, melyet a korábbi részben ismertettünk. Elıkészületek import import import import

GHC.Conc System.Info Text.Printf Data.Version

main = do printf "Compiled with %s-%s on %s/%s\n" compilerName (showVersion compilerVersion) os arch printf "Running with %d OS threads\n" numCapabilities

Az újabb példakód jelentısége az volt, hogy tudjuk, milyen rendszeren, hány magon futtatjuk kódjainkat:

$ ghc -O2 --make -threaded 01.hs [1 of 1] Compiling Main ( 01.hs, 01.o ) Linking 01 … $ ./01 +RTS -N2 Compiled with ghc-6.10 on linux/x86_64 Running with 2 OS threads

Ez után az általános használatban lévı paraméterek parallel program fordítása és futtatása esetén: •

Fordítás: -threaded –O2

•

Futtatás: +RTS -N2 , vagy +RTS –N4 , . . .

- 67 -


3.7.1.1

Vágó Gergely

Implicit Párhuzamosság

Haskellben

a

mellékhatások,

meglepetések

hiánya

egyszerőbbé

teszi

a

párhuzamosítást. Vegyük a következı kifejezést: f x y = (x * y) + (y ^ 2) Lehetıség van minden rész-kifejezést párhuzamosan kiszámolni. Így a fenti kis mővelet nagyon sok párhuzamos folyamatot hozhat létre. Haskellben a követendı stratégia az, hogy a felhasználó kezébe adjuk az irányítást: eldöntheti, hogy mely kifejezéseket érdemes párhuzamos módon futtatni. Multicore programozás lehetıségei, kulcsszavai nem-explicit esetben: • • •

Threads Locks Communication

Általában igaz, hogy jelentıs gyorsulás érhetı el, csekély erıfeszítésért. A szükséges parallel library importálása (http://hackage.haskell.org/packages/parallel) : $ ghc-pkg list parallel /usr/lib/ghc-6.10.4/./package.conf: parallel-1.1.0.1 import Control.Parallel $ cabal unpack parallel Ships with the Haskell Platform.

A párhuzamosság a `par` kombinátorral kezdıdik: a `par` b Ez sorban a következıket eredményezi: •

Létrehoz egy „indítót” (spark) ’a’-nak

•

Futási idıben ha lehetıség van rá, átkonvertálja azt szállá

•

Ez másik magon való párhuzamos futást eredményezhet

•

’b’ a visszaadott érték

Amit a `par` kínál: •

A `par` nem garantál új Haskell szintő szálat

•

Csupán egy „útmutatás”, hogy jó lehet az argumentumok párhuzamos kiértékelése

•

Futási idıben kerül eldöntésre munkamennyiségtıl függıen az érték költségeitıl függıen

•

Ezzel a `par` egyszerő, olcsó megoldást kínál bárhol, bármikor használhatjuk hogy felülbecsüljük a párhuzamosítást kódunkban - 68 -


Vágó Gergely

Szükségünk van még egy olyan funkcióra, mellyel megszabhatjuk, hogy egy szál mit csináljon elsıként. Ez lesz a pseq: pseq :: a → b → b Ez azt jelenti, hogy „értékeld ki ’a’ –t az aktuális szálban, majd térj vissza ’b’-vel”. Együtt végre lehetıségünk van kifejezések párhuzamosítására: f `par` e `pseq` f + e Azaz: elindul ’f’, majd, szálként lefut. ’e’ pedig kiértékelıdik az aktuális szálban párhuzamosan ’f’ –el. Egy egyszerő spark kód: import Control.Parallel main = a `par` b `par` c `pseq` print (a + b + c) where a = ack 3 10 b = fac 42 c = fib 34 fac 0 = 1 fac n = n * fac (n-1) ack 0 n = n+1 ack m 0 = ack (m-1) 1 ack m n = ack (m-1) (ack m (n-1)) fib 0 = 0 fib 1 = 1 fib n = fib (n-1) + fib (n-2)

Lefutásának eredménye – a fentebb írt fordítási és futtatási módokon: $ ghc-6.11.20090228 02.hs --make -threaded -O2 $ time ./02 1405006117752879898543142606244511569936384000008189 ./02 2.00s user 0.01s system 99% cpu 2.015 total $ time ./02 +RTS -N2 1405006117752879898543142606244511569936384000008189 ./02 +RTS -N2 2.14s user 0.03s system 140% cpu 1.542 total

A cpu jobb kihasználtsága látszódik a második esetben. A -sstderr kapcsoló használatával (./02 +RTS -N2 –sstderr) a következıt kapjuk: . . . SPARKS: 2 (2 converted, 0 pruned) -- tehát csak 2 szálunk volt %GC time 7.9% (10.8% elapsed) Productivity 92.1% of total user, 144.6% of total elapsed

Várhatóan újabb javulást érhetünk el, ha a párhuzamosítást levisszük a rekurzióba: . . . parfib parfib parfib parfib where

:: Int -> Int 0 = 0 1 = 1 n = n1 `par` (n2 `pseq` n1 + n2)

- 69 -


Vágó Gergely

n1 = parfib (n-1) n2 = parfib (n-2)

Az eredmény egy mag esetén: ./03 43 +RTS 22.42s user 0.05s system 97% cpu 23.087 total

Míg alig kapunk jobb eredményt, gyorsabb kódot párhuzamosítva: ./03 43 +RTS -N2 27.21s user 0.27s system 136% cpu 20.072 total

Ez esetben már 116 szálunk volt (rekurziós lépésszám?). Ez borzasztóan sok: SPARKS: 701498971 (116 converted, 447756454 pruned)

Azonban még mindig nem került kihasználásra a rendelkezésünkre álló teljes hardveres erıforrás. Jelen esetben túl sokba került a feleslegesen sok szál: tudni kell, hol a határ. Ismerıs lehet a helyzet, hiszen hasonló problémákon már végigküzdöttük magunkat a korábbi fejezetek során (2.4), akkor sem sikerült az elsı pár próbálkozásra a leghatékonyabb kódot megírnunk. Küszöb használatával a rekurzióban javíthatunk a hatékonyságon, finomíthatunk kódunkon: main = do [arg1,arg2] <- getArgs let n = read arg1 :: Int -- input a nfib részére t = read arg2 :: Int -- threshold, küszöb res = parfib n t putStrLn ("parfib " ++ show n ++ " = " ++ show res) parfib :: Int -> Int -> Int parfib n t | n <= t = nfib n | otherwise = n1 `par` n2 `pseq` n1 + n2 where n1 = parfib (n-1) t n2 = parfib (n-2) t

Az eredmény pedig: ./04 43 17 +RTS -N2 -sstderr 8.05s user 0.03s system 190% cpu 4.239 total

A lustaság (kiértékelés) fontos szerepet játszik a Haskell-ben: lehetıvé teszi, de ugyanakkor zaravja is a párhuzamos mőködést. Ugyanis amikor osztott algoritmust szeretnénk írni, megkövetelt a precizítás, pontosan tudni kell, hol kap értéket egy adat. Ezzel szemben a lusta kiértékelés okozhatja pont ennek az ellenkezıjét. Az NFData osztály feloldja ezt a problémát. class NFData a where -- | Reduces its argument to (head) normal form rnf :: Strategy a

• type Strategy a = a → () • állást kell foglalnunk, hogy szigorítjuk az egyes típusok kiszámítását (garantálva, hogy minden tervezett munka végrehajtódik az adott szálon) instance NFData a => NFData [a] where rnf [] = () rnf (x:xs) = rnf x `seq` rnf xs instance (NFData a, NFData b) => NFData (a,b) where

- 70 -

Többmagos processzorok programozhatósága rnf (x,y) = rnf instance NFData instance NFData instance NFData instance NFData

Vágó Gergely

x `seq` rnf y Int Integer Float Double

Vegyük a következı feladatot: • Számítsunk ki néhány véletlen listát a fı szálban • Párhuzamos rendezés 'n' mélységig • Szekvenciális rendezés utána • Összefésülés import Control.Parallel import Control.Parallel.Strategies (rnf, NFData(..)) import System.Environment (getArgs) import System.Random (StdGen, getStdGen, randoms)

randomInts :: Int -> StdGen -> [Int] randomInts k g = let result = take k (randoms g) in force result

main = do [args, n'] <- getArgs let count | null args = 500000 | otherwise = read args n = read n' input <- randomInts count `fmap` getStdGen let sorted = parSort n input putStrLn $ "Sorted all " ++ show (length sorted) ++ " elements." force xs = rnf xs `seq` xs sort :: (Ord a) => [a] -> [a] sort (x:xs) = lesser ++ x:greater where lesser = sort [y | y <- xs, y < x] greater = sort [y | y <- xs, y >= x] sort _ = []

parSort :: (NFData a, Ord a) => Int -> [a] -> [a] parSort d list@(x:xs) | d <= 0 = sort list | otherwise = force greater `par` (force lesser `pseq` (lesser ++ x:greater)) where lesser = parSort d' [y | y <- xs, y < x] greater = parSort d' [y | y <- xs, y >= x] d' = d - 1 parSort _ _ = []

A teljesítmény teszt a következıt mutatja: ./05 700000 10 +RTS -N2 -sstderr 5.99s user 0.21s system 120% cpu 5.130 total

Gyors, de nem eléggé. Az oka pedig a következı: •

%GC time 47.5% (46.1% elapsed)

- 71 -


Vágó Gergely

•

A GHC szemétgyőjtı (garbage collector) parallel ’megáll a világ’ elven mőködik

•

Ez azt jelenti, hogy nem futnak a szálak addig.

•

Ezt szeretnénk elkerülni, mivel hatékonyság romlást, lassúlást eredményez.

•

Sokat segít a GC statisztikák ellenırzése (-sstderr) és a GC idejének csökkentése az alapértelmezett allokáció javára (-H400M or -A400M).

./05 700000 10 +RTS -N2 -sstderr -A300M 5.67s user 0.61s system 131% cpu 4.762 total

Az eredmény pedig: %GC time 19.6% (21.9% elapsed) Írjuk meg saját párhuzamos Map függvényünket a `par` segítségével: parMap _ [] = [] parMap f (x:xs) = let r = f x in r `par` r : parMap f xs

A lista gerincét párhuzamosíthatjuk, de az elemek szekvenciálisan futnak továbbra is. Egymásba ágyazásra van szükségünk, hogy párhuzamosítjuk az egyes típusokat: parMap _ [] = [] parMap f (x:xs) = let r = f x in forceList r `par` r : parMap f xs

Ez már jó, de nem túl szép megoldás, hiszen nem írhatunk minden típusra saját, önálló függvényt. Próbáljuk meg az NFData stratégia használatát most is, rugalmasságot és modularitást biztosítva használatával. parList :: Strategy a -> Strategy [a] parList strat [] = Done parList strat (x:xs) = strat x `par` parList strat xs

Egy stratégia, mely további stratégiát használ minden párhuzamos lépésben. Így már felépíthetı az általános párhuzamosító eljárásunk: using :: a -> Strategy a -> a using x s = s x `seq` x parMap :: (a -> b) -> [a] -> [b] parMap f xs = map f xs `using` parList rnf

A legfontosabb stratégia párhuzamosításkor is az újrahsználhatóság biztosítása. Feladat: bináris fa létrehozása és bejárása. import import import import import

System Data.Bits Text.Printf Control.Parallel.Strategies Control.Parallel

data Tree = Nil | Node !Int !Tree !Tree minN = 4 io s n t = printf "%s of depth %d\t check: %d\n" s n t main = do n <- getArgs >>= readIO . head let maxN = max (minN + 2) n stretchN = maxN + 1

- 72 -


Vágó Gergely

-- fa a memóriába let c = check (make 0 stretchN) io "stretch tree" stretchN c -- a fa allokálása let !long = make 0 maxN -- allokálása, bejárása, deallokálása a bináris fának let vs = (parMap rnf) (depth' maxN) [minN,minN+2..maxN] mapM_ (\((m,d,i)) -> io (show m ++ "\t trees") d i) vs -- a bináris fa még létezik? io "long lived tree" maxN (check long) -- fák generálása depth' :: Int -> Int -> (Int,Int,Int) depth' m d = (2*n,d,sumT d n 0) where n = 1 `shiftL` (m - d + minN) -- fák allokálása és leellenırzése sumT :: Int -> Int -> Int -> Int sumT d 0 t = t sumT d i t = sumT d (i-1) (t + a + b) where a = check (make i d) b = check (make (-i) d) -- a fa bejárása, levelek megszámlálása check :: Tree -> Int check Nil = 0 check (Node i l r) = i + check l - check r -- fa felépítése make :: Int -> Int -> Tree make i 0 = Node i Nil Nil make i d = Node i (make (i2-1) d2) (make i2 d2) where i2 = 2*i; d2 = d-1

Teljesítménytesztek: ./06 20 52.78s user 0.39s system 98% cpu 54.016 total ./06 20 +RTS -N2 -A500M -sstderr 31.41s user 1.09s system 168% cpu 19.284total

3.7.1.2

Explicit Párhuzamosság

Helyesen, számításainknek megfelelıen mőködı párhuzamos programjainkhoz szükségszerő az explicit szálak használata: önálló kódrészek kiválasztása és futtatása új Haskell szálakon forkIO :: IO () → IO ThreadId

Egyszerő példakód - konkurens programozás szálakkal: import Control.Concurrent import System.Directory main = do forkIO (writeFile "xyz" "szal itt jart") v ← doesFileExist "xyz" print v

- 73 -


Vágó Gergely

Kis összefoglaló, emlékeztetı, amit a szálak programozásáról tudni illik: •

A szálak elıre beütemezettek

•

Nem-determináns ütemezés: véletlenszerőség

•

Amint a fı szál terminál, minden további is (“daemonic threads”)

•

A szálak akár le is állhatnak a memóriafoglalást követıen

•

Kommunikáció: üzenetekkel, vagy osztott memória használatával.

Példakó - asszinkron kivételek: import import import import import

Control.Concurrent Control.OldException Control.Monad Data.Dynamic System.IO

main = do tid <- forkIO (mythread 2) threadDelay (10^6) throwTo tid (DynException (toDyn "Veged")) print "komment" threadDelay (10^6) mythread n = handle messages $ forM_ [1,n..] print where messages (DynException d) | Just s <- fromDynamic d = do putStrLn s putStrLn "Vegem" messages _ = mythread 1

Mint már szó volt róla, szükséges, hogy szálaink képesek legyen kommunikálni egymással valamilyen módon. Egyik egyszerő megoldás az asszinkron üzenetváltás (import Control.Exception): a szálak üzeneteket dobálnak egymásnak, elkapják másét, s különbözı módon reagálnak rájuk. A technika elınye az egyszerősége. Ennél azonban komolyabb kommunikációra van szükségünk. Például egymás eredményére való várakozáshoz. Ilyen jellegő szinkronizációs eljárások megvalósíthatóak az MVars és az STM technikákkal. MVars – osztott memória •

import Control.Concurrent.MVar

•

MVar –t fogjuk fel egyszerő ládaként. Lehet üres és tele. o

putMVar :: MVar a → a → IO ()

o

takeMVar :: MVar a → IO a

•

A “put” egy teli MVar-ra alvásra kényszeríti a szálat addig, míg üres az MVar.

•

A “take” egy üres MVar –ra blokkolja azt addig, míg az tele van.

- 74 -


Vágó Gergely

Tehát akkor ébresztik fel a szálakat, amikor azokra szükség van.

A dolgok dobozba rakása: do box <- newEmptyMVar forkIO (f `pseq` putMVar box f) e `pseq` return () f <- takeMVar box print (e + f)

Egyszerő példakód – fork és kommunikáció: import Control.Concurrent import Control.Concurrent.MVar main = do x <- newEmptyMVar y <- newEmptyMVar z <- newEmptyMVar forkIO $ worker1 x forkIO $ worker2 y forkIO $ worker3 z a <- takeMVar x b <- takeMVar y c <- takeMVar z print (a + b + c) worker1 m = putMVar m $! fac 100 worker2 m = putMVar m $! fib 34 worker3 m = putMVar m $! ack 3 10 ack 0 n = n+1 ack m 0 = ack (m-1) 1 ack m n = ack (m-1) (ack m (n-1)) fac 0 = 1 fac n = n * fac (n-1) fib 0 = 0 fib 1 = 1 fib n = fib (n-1) + fib (n-2)

Alacsonyabb szintő kommunikáció (3.7.1.1 Implicit Párhuzamosság fejezethez képest). ./10 +RTS -N2 -stderr 2.32s user 0.06s system 146% cpu 1.627 total

Amikor költséges IO mővelet van, érdemes egy szálat létrehozni elvégzésére, majd visszaadni a vezérlést a felhasználónak újabb feladatok elvégzése végett. Egyszerő, hatásos technika lemez- és hálózatkezelési funkciók elrejtéséhez. Érdemes minden részfeladatot külön szálnak kiadni, ugyanis azok ’könnyősúlyú’ erıforrások, akár milliónyit is létrehozhatunk. Példakód – üzenetküldés szálak között: import Control.Concurrent import Control.OldException import Control.Monad

- 75 -


Vágó Gergely

import Data.Dynamic import System.IO main = do mv <- newEmptyMVar tid <- forkIO (mythread mv 2) threadDelay (10^6) putMVar mv "Veged" print "komment" threadDelay (10^6) putMVar mv "Nem igazan" threadDelay (10^6) print "Egyszerre leallunk mind" mythread mv n = forM_ [1,n..] $ \n -> do print n b <- isEmptyMVar mv when (not b) $ do s <- takeMVar mv messages s where messages s = do putStrLn s putStrLn "Ne! Nem lehet vegem!" threadDelay (10^6 `div` 2) mythread mv (n^2)

Láthattuk, lehetıség van üzenetek küldésére, s szálak várakoztatására annak megérkeztéig. Ha egyidejőleg több szál várakozik, akkor egy véletlenszerően felébred. Még mindig van pár megoldandó probléma: -

Szeretnénk, ha az üzenetek nem szakítanák meg szálaink cselekedetét.

-

Üzenetek korlátozásának lehetısége

Megoldást jelenthetnek a következık: -

Versenyhelyzet(race-condition) kialakulásakor kivétel dobása.

-

Nem feltétlenül szeretnénk az MVar értékét visszakapni

-

Helyette egy módosított MVar –t használjunk:

-

modifyMVar :: MVar a → (a → IO (a, b)) → IO b

További probléma az MVars –al: Holtpont alakulhat ki, ha egy szál egy másik értékére, eredményére vár, melyet nem kap meg soha. Ez ismerıs jelenség a 2.4.3 fejezetbıl. Azonban a Haskell lehetıséget kínál kizárás-mentes szinkronizálásra a software transactional memory (STM) segítségével. Ez magasabb szintő, biztonságosabb technika mint az MVars, ugyanakkor egy kicsit lassabb is.

- 76 -


Vágó Gergely

STM - Software Transactional Memory Az STM nem csupán a Haskell nyelvi sajátosság, hanem egy technológia, mely párhuzamos alkalmazások hatékony mőködését teszi lehetıvé. Alapjait elıször 1986ban vetette papírra Tom Knight [38], végül 1995 –ben Nir Shavit és Dan Touitou terjesztette ki az ötletet, s vált alapjává a particionált implementálási feladatoknak. Többek között az Intel is foglalkozik C++ nyelvre történı STM fordító írásával. [37] Alapelvei: •

Minden atomi blokk teljesen izoláltan, elkülönülve fut.

•

Futási idıbeli módosítások az osztott változókon láthatóak minden szál számára.

•

Versenyhelyzet esetén a mővelet újraindul.

•

Illúzió: te vagy az egyetlen szál. – ez biztosítja, hogy minden szál úgy lássa, övé a teljes rendszer.

Az STM 2005 –ben került bele a Haskell eszközeinek tárába. Az stm csomag használata: •

http://hackage.haskell.org/packages/stm

•

$ ghc-pkg list stm /usr/lib/ghc-6.10.4/./package.conf: stm-2.1.1.2

•

import Control.Concurrent.STM

•

$ cabal unpack stm

data STM a atomically :: STM a → IO a retry :: STM a orElse :: STM a → STM a → STM a

Az ’STM a’ –t használjuk az atomi blokk felépítéséhez. Minden mővelet ezen atomi részeken belül futhat, így valósítva meg azt az illúziót, hogy nincs más futó szál. A rendszer mindezek mellett különbözı segédeszközöket használ az esetenként kialakuló konfliktusok kezeléséhez: logs, rollback. Az ’orElse’ lehetıséget nyújt a blokkok nagyobb darabbá való összeillesztéséhez. Az atomi blokkokon belül használatos TVars leváltja az elızıleg használt MVars-t: data TVar a newTVar :: a → STM (TVar a) readTVar :: TVar a → STM a writeTVar :: TVar a → a → STM ()

Mint már említettük, nincsenek holtpontok, így minden mővelet végrehajtása sikeres. Egyszerő példakód – atomi banki transzfer: - 77 -


Vágó Gergely

transfer :: TVar Int -> TVar Int -> Int -> IO () transfer from to amount = atomically $ do balance <- readTVar from if balance < amount then retry else do writeTVar from (balance - amount) tobalance <- readTVar to writeTVar to (tobalance + amount

Mivel adott a lehetıség, hogy visszagörgessük a mőveleteket (rollback), ezért az atomi blokkoknak nincs látható mellékhatásuk. Így garantálható az atomi biztonság. Nincs lehetıség IO mőveletekre, csak egyszerő kódrészek (pure code), kivételek, nemterminánsok írására. A végrehajtó folyamat akkor ébreszt fel egy atomi részt, amint változás következik be annak egy mőveleti változójában. Elıfordul, hogy két atomi blokkot szeretnénk összekomponálni (orElse :: STM a → STM a → STM a): ’ha az elsı elbukik, akkor próbáld a másikat’ elven. 3.7.2

Összefoglalás

A függvények kompozíciója asszociatív, így a funkcionális nyelvő programok kiértékelése jól párhuzamosítható. A legfontosabb annak eldöntése, hogy mely részkifejezések kiértékelését célszerő párhuzamos módon elvégezni. Többféle irányvonal létezik: új absztrakt nyelvi elemek bevezetése (Strategy), párhuzamos függvénykiértékelés

létrehozása,

a

kiértékelési

módszerek

módosítása,

vagy

dinamikusan összeszerkesztett kód. A Haskell nyelv lehetıséget kínál mind Explicit, mind pedig Implicit párhuzamosságra, fıleg adatpárhuzamos módon, minden párhuzamosítási szinten megvalósítva. Ez utóbbi meglepı dolog lehet, de elég csak a függvények kompozicíójára gondolni: az eredmény eredményével tovább dolgozhatunk. Lehetıség van spekulatív módon meghatározni, hogy mely részkifejezés kiértékelésére vanszükségünk elıször, hogy amikor késıbb újra szükség lesz annak értékére, akkor normál formája már rendelkezésünkre álljon. A fordításkor és futtatáskor megadható paraméterekkel lehetıség van rugalmasan, s teljesítményorientáltan felkészíteni programjainkat.

Ez

nagy

támogatást

jelent

több

magon

futó

párhuzamos

programjainkhoz. •

Helyesség: bizonyítása nem jelent nagy munkát, ugyanis típusellenırzı rendszere nagyon jól mőködik, másrészt mert a Haskellben való programozás eleve olyan gondolkodásmódot

igényel,

ami

- 78 -

közel

áll

a

módszertanban

tanult


Vágó Gergely

gondolkodásmódhoz, ezért a programok a kezdettıl jobban átgondoltak. Ráadásul a Haskell szintaxisa is olyan, hogy az közel áll a matematikai jelölésekhez, így a programozás során tulajdonképpen elkerülhetetlen, hogy az ember részletes, formalizált specifikációt írjon, az implementációt pedig az esetek nagy részében elvégzi maga a Haskell. Segítséget nyújthatnak még egyes helyességbizonyító

eszközök:

NuSMV

–

modellellenırzés,

Sparkle

–

funkcionális nyelv helyességbizonyító GUI •

Megbízhatóság, hatékonyság: megfelelı ismeretek megléte mellett gyors, hatékony kódot kapunk. Megbízható, rugalmas nyelv.

•

Hordozhatóság: megfelelı módon felparaméterezett, s futtatott kód hordozható, mőködése eltérı rendszeren és magszámú processzoron is hatékony lesz. Például: +RTS -NX, vagy (-H400M or -A400M paraméterek használata.

•

Tesztelhetıség, áttekinthetıség, egyszerőség A funkcionális nyelv sajátossága miatt tiszta, áttekinthetı kódot kapunk, de komoly elıismeretek, matematikai gondolkodásmód megléte szükséges.

•

Fejlesztıi környezet Egyes fejleszıi eszközökbe, környezetekbe beépítették a Haskell nyelv szintaktikai értelmezıjét, de a komolyabb fejlesztések még mindig GHC alatt történnek. Ehhez jó segédeszközök (manual), könyvtári leírások láttak már napvilágot.

•

Újrahasznosíthatóság, karbantarthatóság, kompatibilitás A funkcionális eszközök, a függvények sajátosságai miatt ezek a tulajdonságok mind jelen vannak. Szintén utalnék a paraméterezhetıségre mind fordításkor, mind pedig futtatáskor.

•

A programozási nyelv jelentısége Utóbbi idıben egyre sikeresebb, több figyelmet kap. Bizonyos problémák megoldása sokkal letisztultabb, egyszerőbb a funkcionális nyelvi eszközök segítségével.

- 79 -


3.8

Vágó Gergely

Felmerülı kérdések

Minden fejlesztés során felmerülnek bizonyos kérdések, melyek megválaszolásával állást foglalunk egyik, vagy másik fejlesztési irány, megvalósítási módszer mellett, mely programunk hatékonyságára is hatást gyakorolnak. Egyik legfontosabb kérdés például a változók hozzáférhetıségének eldöntése. 3.8.1

Közös, vagy saját?

[3][4]

Már szó volt róla, hogy mi a különbség a közös, illetve a saját erıforrások, változók használata között, most vizsgáljuk meg, ezt kód-szinten. Tudjuk, hogy közös erıforrásokba lehetıség van beleírni írás-olvasás között. Fontos a kölcsönös kizárás kezelése, vagy annak biztosítása, hogy csak olvasásra férhessen hozzá egy szál az adott változóhoz. void dxSimpleSpace::collide (void *data, dNearCallback *callback) { dAASSERT (callback); lock_count++; cleanGeoms(); bool geomEnabled1 = false;

// KÖZÖS VÁLTOZÓ

#pragma omp parallel for // FORK for (int index1 = 0; index1 < maxGeoms; ++index1) { dxGeom* g1 = geoms[index1]; geomEnabled1 = GEOM_ENABLED(g1) // ÍRÁS if (geomEnabled1) // OLVASÁS { for (int index2=index1+1; index2<maxGeoms; ++index2) { dxGeom* g2 = geoms[index2]; if (GEOM_ENABDLED(g2)) { collideAABBs (g1,g2,data,callback); } } } // JOIN lock_count--; }

Explicit saját változó: void dxSimpleSpace::collide (void *data, dNearCallback *callback) { dAASSERT (callback); lock_count++; cleanGeoms(); bool geomEnabled1 = false;

- 80 -


Vágó Gergely

#pragma omp parallel for private(geomEnabled1) // SAJÁT VÁLTOZÓ for (int index1 = 0; index1 < maxGeoms; ++index1) { dxGeom* g1 = geoms[index1]; geomEnabled1 = GEOM_ENABLED(g1) if (geomEnabled1) { . . . } lock_count--; }

Implicit saját változó: void dxSimpleSpace::collide (void *data, dNearCallback *callback) { dAASSERT (callback); lock_count++; cleanGeoms(); #pragma omp parallel for for (int index1 = 0; index1 < maxGeoms; ++index1) { bool geomEnabled1 = false; // SAJÁT VÁLTOZÓ dxGeom* g1 = geoms[index1]; geomEnabled1 = GEOM_ENABLED(g1) if (geomEnabled1) { . . . } lock_count--; }

Ha például egy tömb összes elemét össze szeretnénk adni, felmerül a kérdés: 3.8.2 •

Mi legyen a célváltozó? Közös, mert meg akarjuk tartani. Cserébe szükséges a kölcsönös kizárás, de az pedig lassú.

•

Saját, mert el szeretnénk kerülni, hogy más is írhasson bele. Ekkor viszont eltőnik amit beleírtunk (lokális változó révén).

Megoldást jelenthet a redukció: void dxSimpleSpace::collide (void *data, dNearCallback *callback) { dAASSERT (callback); lock_count++; cleanGeoms(); unsigned int pairCount = 0;

// KÖZÖS VÁLTOZÓ

#pragma omp parallel for reduction(+:pairCount)// REDUKCIÓ BEKAPCS. for (int index1 = 0; index1 < maxGeoms; ++index1) {

- 81 -


Vágó Gergely

bool geomEnabled1 = false; dxGeom* g1 = geoms[index1]; geomEnabled1 = GEOM_ENABLED(g1) if (geomEnabled1) { for (int index2=index1+1; index2<maxGeoms; ++index2) { dxGeom* g2 = geoms[index2]; if (GEOM_ENABDLED(g2)) { collideAABBs (g1,g2,data,callback); ++pairCount;// EXPLICIT:SAJÁT VÁLTOZÓ } } } // IMPLICIT:SAJÁTOK KÖZÖS lock_count--; }

3.8.3

Lock technikák

[3][4][32]

Fontos, hogy párhuzamosan mőködı, bizonyos közös erıforrásokat megosztó alkalmazásunk helyes, kivétel- és holtpont-biztos legyen. Ehhez különféle lockolási, zárolás technikák állnak rendelkezésünkre. Ezek ismertetésére kerül most sor, különféle példákon keresztül. Az elsı kérdés, amit el kell döntenünk, az talán az, hogy „adathoz, vagy kódhoz” közel lockolunk. Ez nagyjából annyit tesz, hogy konkrét adatokhoz, vagy teljes kódrészekhez való konkurens hozzáférést szeretnénk megtiltani. Elıbbire példa egy változó írása, míg utóbbira amikor valamelyik taszknak a lefutása meg kell hogy elızze a másikat. Lock helyett gyakran használhatunk gurad-ot.. Természetesen private változók esetén nincs lehetıség lockolni, hiszen nincs is mit. Másik eldöntendı kérdés, hogy hol lockoljunk (külsı/belsı). Valamint vannak akik még egy módon különbséget tesznek a zárolások között, mégpedig a mutex : adat aránnyal.(1:1, N:1, 1:N). Hol lockoljunk? CRITICAL_SECTION bulletSection; Bullet** pBullets; void UpdateBullets() { //Végtelen ciklus for(;;) { // LOCK EnterCriticalSection(&bulletSection); for(int i=0; i
- 82 -


Vágó Gergely

//Információk módosítása, felülírása } } LeaveCriticalSection(&bulletSection); // UNLOCK

} } void Render() { EnterCriticalSection(&bulletSection); //Egyéb mőveletek LeaveCriticalSection(&bulletSection); }

Ez egy mőködı megvalósítás. Ugyanakkor vannak hátrányai, mint például: •

nehezen bıvíthetı: Enter/Leave párosok kellenek minden új taszkhoz.

•

nehezen skálázható

Külsı lock Nem igazán járható út, nehezen debugolható. Belsı lock Ez lefedi az esetek 90%-át. Ekkor az osztály magának intézi el a zárolást. Biztonságos, teljesen threadsafe, úgy is mondhatjuk, hogy „idiótabiztos”. Kívülrıl teljesen láthatatlan, azaz bárki használhatja az osztályt. Egy hátránya van, hogy rugalmatlan: annyi lock szükséges, ahány mővelet van. template class cThreadedStack { public: cThreadedStack() : m_iCoun(0) {} void Add(const ObjectType& pInput) { // GUARD boost::lock_guard guard(m_Mutex); m_aObjects[m_iCount++] = pInput; } ObjectType Remove() { // GUARD boost::lock_guard guard(m_Mutex); if (m_iCount) return m_aObjects[--m_iCount]; else return ObjectType(); } private: boost::mutex m_Mutex; static const unsigned int MAXCOUNT = 128; ObjectType m_aObjects[MAXCOUNT]; unsigned int m_iCount; };

- 83 -


Vágó Gergely

Hívó által biztosított Ez lefedi az esetek maradék, 10%-át. A hívónak bizonyítania kell, hogy lockolt. Ez a megoldás nem az igazi –nem véletlen, hogy csak a maradék százalékot teszi ki. Több problémát is okozhat: nehéz eldönteni, hogy kinek a mutex -érıl van szó, s hogy kellıen biztosított –e a lock (mit bizonyít egy lock_guard<mutex>?). template class cThreadedStackEx { public: cThreadedStackEx() : m_iCoun(0) {} void Add(const ObjectType& pInput) { boost::lock_guard guard(m_Mutex); Add(guard, pInput); } //BIZONYÍTÉK void Add(const boost::lock_guard& pMutex, const ObjectType& pInput) { m_aObjects[m_iCount++] = pInput; } ObjectType Remove() {. . .} ObjectType Remove(const boost:lock_guard& pMutex) {. . .} private: boost::mutex m_Mutex; static const unsigned int MAXCOUNT = 128; ObjectType m_aObjects[MAXCOUNT]; unsigned int m_iCount; };

Továbbfejlesztési lehetıségek: •

Típusos lock_guard: Lock_guard, ez fordítási idejő ellenırzést biztosít.

•

Pointeres lock_guard: Lock_guard.m_pOwner, ez pedig futási idejő ellenırzés.

- 84 -


3.9

Vágó Gergely

A jövı – Stream programming

A nem túl távoli jövıben természetesen meg fognak jelenni további technikák, módszerek, illetve eszközök, melyek még inkább megközelítik a számítógépekben rejlı lehetıségek határait. A jelenleginél is több magú processzorok, új felépítés, új programozási nyelv, illetve könyvtár. Ezekre már mind van példa, csak még nem annyira kiforrottak. Elég a processzorokkal párhuzamosan, szintén gyorsan fejlıdı grafikus kártyákra gondolni. 3.9.1

GPU

A GeForce 8800 GT, GTS, illetve GTX családja több, mint 112 magot tartalmazó grafikus gyorsító kártyák, 1500 MHz körüli GPU-, valamint 900+ Mhz-es memória órajelekkel. Elsı körben grafikus alkalmazások gyorsítására, programozására tervezték, de hamar kiderült, hogy nem csak ilyen jellegő programok számítására használható kitőnıen. A GPU (Graphics Processing Unit) a videó kártyák vezérlı egysége, masszívan többszálasított, sok magú központi chip. Az NVIDIA Tesla terméke elérte a több, mint 128 magos skalár processzort, mely képes 12.000 független szálat irányítani. Bizonyos alkalmazásokban, tudományos és mérnöki számítások esetén akár százszoros sebességnövekedés (speedup) érhetı el. 3.9.2 A

CUDA CUDA

[30] skálázható

párhuzamos

programozási

(heterogén)

modell

és

szoftverkörnyezet párhuzamos programozáshoz. Minimális kibıvítése a C/C++ nyelvnek. Nem kívánom a 2.2.4.3 pontban leírtakat megismételni – habár az ott leírtak újraolvasása ajánlott -, e fejezet célja inkább a programozási szempontból ide illı technikák, módszerek ismertetése, bemutatása. Fejlesztıi célok: •

Heterogén rendszerek használatának lehetısége(CPU + GPU). Az egyes, szeparált vezérlı egységek szeparált DRAM-mal.

•

Magok százainak, szálak ezreinek skálázása.

•

Jobb ráfókuszálás biztosítása a programozóknak a párhuzamos algoritmusokra. (C/C++ minimális kibıvítése, nem új mechanizmus)

A CUDA valójában egy soros mőködéső program, párhuzamos kernellel C nyelven: A soros C kód egy „gazda”, mester szálon fut a CPU-ban, míg a párhuzamos C kódú GPU kernelen futnak a szolga egységek független szálai.

- 85 -


Vágó Gergely

A CUDA C-szintő nyelvi kiegészítései (példák): Alapkövetelmény: minimális nyelvi kiegészítéssel jelentıs hatásfok növekedés. Specifikáció deklarálása: __global__void KernelFunc(...);

// kernel function, runs on device

__device__int GlobalVar;

// variable in device memory

__shared__int SharedVar;

// variable in per-block shared memory

Függvényhívások szintaktikájának kiegészítése a parallel kernel indításához: KernelFunc<<<500, 128>>>(...); // launch 500 blocks w/ 128 threads each Speciális változók a kernelbéli szálak azonosításához: dim3 threadIdx;

dim3 blockIdx;

dim3 blockDim; dim3 gridDim;

A lényeg, mely felfedi a speciális mőveleteket a kernel kódban: __syncthreads();// barrier synchronization within kernel Device management: cudaGetDeviceCount(), cudaGetDeviceProperties() Device memory management: cudaMalloc(), cudaFree(), cudaMemcpy() Graphics interoperability: cudaGLMapBufferObject(), cudaD3D9MapResources() Texture management: cudaBindTexture(), cudaBindTextureToArray() Példa: Tömb elemeinek növelése CPU program void increment_cpu(float *a, float b, int N) { for (int idx = 0; idx
CUDA program __global__void increment_gpu(float *a, float b, int N) { int idx = blockdx.x * blockDim.x + threadx.x; if (idx < N) a[idx] = a[idx] + b;

- 86 -

[30]


Vágó Gergely

} void main() { . . . dim3 dimBlock (blocksize); dim3 dimGrid( ceil(N / (float)blodksize) ); increment_gpu<<>(a,b,N); }

A vektor növelése b-vel (mőködési elve): N = 16, blockDim = 4 –> 4 blok:

blockIdx.x = 0

blockIdx.x = 1

blockIdx.x = 2

blockIdx.x = 3

blockDim.x = 4

blockDim.x = 4

blockDim.x = 4

blockDim.x = 4

threadIdx.x=0,1,2,3

threadIdx.x=0,1,2,3

threadIdx.x = 0,1,2,3

threadIdx.x=0,1,2,3

idx = 0,1,2,3

idx = 4,5,6,7

idx = 8,9,10,11

idx = 12,13,14,15

A lokális threadIdx index áttranszformálása globális index-é (általános eljárás): intidx = blockDim.x* blockId.x+ threadIdx.x; A gyakorlatban a blockDim >= 32 kéne lennie, a fenti példa csak az egyszerőség kedvéért nem tett eleget ennek a „kritériumnak” Példa: Mátrixösszeadás

A mőködési elv hasonló, mint az elızı példában, annyival kell kiegészíteni, hogy bejött a képbe egy második index-számláló is: i = blockDim.x* blockId.x+ threadIdx.x; j = blockDim.y* blockId.y+ threadIdx.y;

- 87 -


Vágó Gergely

A CUDA thread - mátrix felépítése ThreadID = adat index Közös memória: Local: blokkon belül Global: grid-en belül Barrier: blokkon belül Kernel: float *pIn, *pOut (stream!) Adat: pIn[threadID] 3.9.3

OpenCL

[31][33]

Voltak törekvések a GPU-programozás könnyítésére (Sh, BrookGPU), de az áttörést az nVidia hozta 2006 végén a CUDA-val. Egyetlen probléma, hogy nem egy platformfüggetlen megoldás, lévén a CUDA csak az nVidia hardvereire van/volt implementálva. Erre a problémára nyújthat megoldást az Apple kezdeményezésébıl született OpenCL (Open Computing Language). Maga az OpenCL tulajdonképpen egy C nyelvre épülı nyílt szabványú programozási környezet, amely széles körben támogatja a mai hardvereket, a bennük megbúvó párhuzamos számítási kapacitás megfelelı kihasználása érdekében. [31] [33]

- 88 -


4.

Vágó Gergely

Tervezés

Az eddig szerzett ismereteinket felhasználva belekezdhetünk párhuzamos programok tervezéséhez.

Mint

minden

szoftverfejlesztésnek,

projektmunkának,

ennek

is

megvannak a maga módszerei, megközelítései. A párhuzamos, illetve elosztott alkalmazások fejlesztése az egyszerő szekvenciális, egyetlen processzoron futó programokhoz képest lényegesen bonyolultabb, hiszen a komponensek megtervezésén és elkészítésén túl meg kell szervezni ezeknek az együttmőködését, szabályozását, valamint a szoftver komponensek és a végrehajtó egységek összerendelését is. 4.1

Hogyan és hol párhuzamosítsunk

[1][2][39]

A párhuzamos algoritmusok fogalmát valahogy úgy definiálhatnánk, hogy olyan mőködési leírás, mely több feldolgozó egység egyidejő, összehangolt mőködtetésével állítja elı az eredményt. Nem újdonság továbbá az sem, hogy az általánosan használt feldolgozó egységek alapvetıen szekvenciális programokkal vezérelhetık, így a párhuzamos algoritmus tulajdonképpen nem más, mint egymással kapcsolatban álló szekvenciális feladatok (taszkok) és azok együttmőködésének leírása – szemléletesen például gráf formájában. Természetesen többféle modell és megközelítés létezik a párhuzamos algoritmusok leírására (Top-Down, Bottom-Up), de mindegyiknek a lényege az, hogy a feladatot adott szempontok alapján egymással kommunikáló részekre bontsuk fel és ezeket optimálisan a rendelkezésre álló feldolgozó egységekhez rendeljük. A párhuzamos algoritmusok tervezéséhez nehéz lépésrıl-lépésre receptet adni, mivel számos intuitív elemet tartalmaznak, de mindenképpen érdemes valamilyen módszertant alkalmazni a tervezésnél, mivel ez megkönnyíti a lehetıségek felmérését, és az alternatívák (ki)értékelését. A fejezet címben foglalt kérdésre válaszolva három fontos pont van, amit szem elıtt kell tartani párhuzamos rendszerek tervezésekor: •

Leglassabb részek keresése Ezek a program kritikus, nagy figyelmet igényelı részei, hiszen nagy valószínőséggel ezek felosztása, párhuzamosítása terminálja alkalmazásunk sebességét, kódunk hatékonyságát.

- 89 -


Vágó Gergely

90/10-es szabály A lokalitás elve: A programok adott (pici) idıintervallumban a címtér viszonylag kis hányadát próbálják meg elérni, azaz az adathozzáférési igények 90%-a a lefoglalt címtartomány 10%-át célozza meg.

•

Független feladatok azonosítása A tervezés elsı lépése, ez alapján tudjuk partícionálni, logikailag összefüggı, önálló kis csoportokra osztani az elvégzendı feladatokat.

4.2

Egy tervezési módszertan

[40]

A legtöbb feladatnak számos párhuzamos megoldása van, melyek közül a legjobbak általában jelentısen különböznek a szekvenciális változat által sugallttól. A következıkben egy olyan tervezési módszertan kerül bemutatásra, mely elıször a gépfüggetlen tulajdonságokat kezeli, felderítve az algoritmusban rejlı párhuzamosítási lehetıségeket, majd ezek után tér csak ki gépfüggı jellemzık meghatározására (lokalitás és egyéb teljesítménnyel kapcsolatos döntések), illetve a konkrét feladatok feldolgozó egységekhez rendelésére. A módszer négy lépésbıl áll, ezek a partícionálás, a kommunikáció, az agglomeráció és a hozzárendelés.

Feladat

Partícionálás

Kommunikáció

Agglomeráció

Összerendelés

A párhuzamos algoritmustervezés folyamata

1.

A partícionálás (skálázás) során elsıdleges cél a megoldandó probléma

felosztása kisebb egymástól független feladatok sokaságára. A felosztás kétféle alapon történhet: a feldolgozandó adatok részekre osztásával, vagy a rajta dolgozó kód

- 90 -


Vágó Gergely

funkcióinak szétválasztásával. A minél finomabb felbontás érdekében célszerő a funkcionális- és az adatpartícionálást együttesen alkalmazni (hibrid felosztás). Ebben a lépésben nem kell törıdni a túl finom felbontás hátrányaival, a késıbbi lépések során fognak majd kialakulni a végleges és ideális taszk méretek. A partícionálás akkor jó, ha a feladatot sikerül minél több (a feldolgozó egységek - magok- számát legalább egy nagyságrenddel meghaladó), hasonló mérető részre felosztani, olyan módon, hogy ugyanazok a mőveletek minél kevésbé ismétlıdjenek az egyes részekben. A független, nem replikált mőveleteket tartalmazó részek a skálázhatóságot, a finom felbontás pedig a következı lépések flexibilitását biztosítja. 2.

A partícionálás során keletkezı taszkok képesek a konkurens futásra, de egymás

eredményeire is építenek. A feladatok közötti függıségek feloldására, valamint sorrendjük meghatározására a kommunikáció szolgál. A kommunikációs struktúra meghatározásánál törekedni kell arra, hogy az egyes taszkok keveset, s ha lehet csak a közvetlen szomszédaikkal kommunikáljanak. Ha egy taszkkal túl sok másik kommunikál, akkor annak funkcióit szét kell választani, illetve ha ez nem megy, mert például egy mindenki által használt adatszerkezetet tartalmaz, akkor a szők keresztmetszetnek számító taszkot meg kell többszörözni. A skálázhatóság érdekében jó, ha a taszkok szabályos struktúrában (háló, fa, hiperkocka), hasonló mennyiségő adatcserét bonyolítanak. 3.

Az agglomerációs fázis feladata, a partícionálás során létrehozott taszkok és a

köztük folyó kommunikáció granularitásának növelése. A megfelelı taszkok összevonásával nagyobb teljesítmény érhetı el, mivel egyrészt csökken a taszkok létrehozásával, megszüntetésével és adminisztrálásával járó többletmunka, másrészt a kommunikációs költség is lecsökken, hiszen egyes taszkközi kommunikációs lépések jóval gyorsabb belsı kommunikációvá alakulnak. Az agglomeráció célja tehát a taszkok számának csökkentése a lokalitás elvének maximális figyelembe vételével. Míg a tervezés elsı két lépése során nem kellett a konkrét futtató környezettel foglalkozni, addig az agglomeráció és az összerendelés a konkrét futtató környezet ismeretében kell, hogy történjen. Fontos, hogy az összevonások után legalább annyi taszk maradjon, mely az adott számú feldolgozó egység között egyenletes terhelést biztosítva szétosztható. Az agglomerációs fázisban kell mérlegelni azt is, hogy egyes számítások vagy adatok replikációjával nem növelhetı-e még tovább a párhuzamosítás hatékonysága. A taszkok végsı számának kialakítási módjánál figyelni kell arra is, hogy az algoritmus a

- 91 -


Vágó Gergely

skálázhatóságát megırizze és a hardver esetleges változása esetén ne legyen szükség a tervezési folyamat megismétlésére. 4.

Az összerendelés feladata az agglomeráció során létrehozott taszkok

futtatásának konkrét végrehajtó egységekhez való hozzárendelése. Az összerendelés végezhetı tervezési idıben, vagy a futás közben dinamikusan is. A statikus összerendelésnek leginkább akkor van létjogosultsága, ha a taszkok felosztása adatpartícionálással történt. Ilyenkor természetes módon adódik, hogy a legnagyobb hatékonyság úgy érhetı el, ha az agglomeráció során annyi taszkok készítünk, ahány feldolgozó egységünk van, és miden feldolgozó egységhez egyforma nagyságú, összefüggı adattartományt rendelünk. Mivel ebben az esetben minden feldolgozó egységhez pontosan egy taszkot kell hozzárendelni, ez elıre is elvégezhetı. Az osztott memóriát használó multiprocesszoros rendszerekben az összerendelés feladatát általában az operációs rendszer taszk ütemezıje végzi, a futásra kész taszkok szabad processzorokhoz – vagy maghoz - való hozzárendelésével. A bemutatott párhuzamos tervezési lépesek látszólag egymásra építve szekvenciálisan végezhetık, valójában azonban a tervezés lépései általában párhuzamosan zajlanak. Az egyes lépések lehetıségeinek megvizsgálása után gyakran az elızı lépések során kialakult eredményeket is újra át kell gondolni. A tervezési lépések eredményeinek kiértékeléséhez fontos, hogy rendelkezzünk a felhasznált futási környezet megfelelı minıségő teljesítmény modelljével, ami lehetıvé teszi algoritmusokkal szemben támasztott, gyakran ellentmondó követelmények súlyozott kiértékelését. 4.3

Elıre tervezés

Tervezés során nem elhanyagolandó, ha elıre is képesek vagyunk gondolkodni, felkészülni az esetleges jövıbeli felhasználói igényekre, technikai változásokra, fejlıdésekre. Ezek azok a szempontok, amik szoftverünk idıtállóságát biztosíthatják. Nézzük, párhuzamos program esetén mik azok a kérdések, amikre nem árt figyelni: •

Milyen új funkciók lehetnek? Mit kellene tudnia egy év múlva?

•

Milyen új adatok lehetnek? Több, más?

•

Merre fejlıdik a hardver? Több mag (lásd GPU-k). SIMD, SIMT architektúrák

- 92 -


Vágó Gergely

5. Záró gondolatok 5.1 5.1.1

A jövı A több magos processzorok jövıje (több mint 16 mag felesleges?)

[9] [25]

A processzorok terén az utóbbi évek nagy kérdései a chip-en való feldolgozás sávszélességérıl és a memória korlátokról szóltak. Egyes felmérések szerint a memória kérdés sokkal nagyobb problémát jelenthet számunkra a jövıben, mint azt elıször gondoltuk volna. A "memória korlátozás" problémája nem új fogalom a számítástechnikában, már jóval a többmagos processzorok elıtt is létezett. A probléma abból adódik, hogy egy foglalat feldolgozási sávszélességét (vagyis a felhalmozott másodpercenkénti utasítás szálanként / az összes szál, a program figyelembe vételével), a számára elérhetı memória sávszélesség korlátozza. Ahogy nı a feldolgozási sávszélesség - mondjuk a processzorok órajelének növekedésével, vagy mert több magot tartalmaz egy processzor - a memória sávszélességének is növekednie kell, hogy lépést tudjon tartani vele. Vagyis hiába zsúfolunk több magot egy processzorba, ha a magokat képtelenek vagyunk ellátni adattal. A gond az, hogy a memória sávszélessége nem tud lépést tartani ezzel a fejlıdéssel. A memória-busz sávszélessége (késleltetés és/vagy átvitel) nem fejlıdött olyan lépésben, ahogy azt a Moore törvény megkívánná. Ez azzal fog járni, hogy a processzor majd csak vár és vár, hogy megkaphassa a feldolgozandó adatot. Ez egy klasszikus probléma, s pont emiatt nıttek meg a processzorokra épített másodlagos gyorsítótárak méretei az utóbbi idıben. Minél több processzor magot használunk, annál több memóriára van szükségünk és annál nagyobb másodlagos gyorsítótárat kell beépíteni, hogy ellensúlyozzuk a memória-korlátozás problémáját. Tulajdonképpen a legmodernebb processzorok nem mások mint nagyon gyors memória egységek, amelyek tetejére feldolgozó-egységet építettek (vagy fordítva). Azaz, ez a memória korlát nagyban befolyásolja majd a többmagos processzorok sikerét a jövıben. [25] Egy felmérés szerint (Sandia National Laboratories) 8 magos rendszerek körül kezdıdnek a problémák. Itt már teljesítménybeli visszaesés is észlelhetı bizonyos tudományos és mérnöki számítások terén. 16 mag esetében a teljesítmény fele annyi szintjére esik vissza és ez rohamosan tovább romlik a magok számának növelésével.

- 93 -


Vágó Gergely

Több mag chipenként lelassíthatja néhány program mőködését(piros), hacsak nincs kellı nagyságú/sávszélességő memória-támogatás(sárga) [25]

5.2

Összegzés

A többmagos processzorok életpályája is rövid idın belül szép ívet járt be, csak úgy, mint az egymagosoké. A felgyorsult világban azonban ez a technológia is kevés lehet. Már nem csak a tervezıknek, gyártóknak kell felvenni a versenyt a kielégíthetetlen sebesség iránti igényekkel szemben, de a fejlesztıknek, programozóknak is be kellett szállniuk a harcba: megfelelıen megírt szoftver nélkül nem ér semmit többmagos processzorunk. Erre nyújtanak segítséget diplomamunkámban ismertetett különbözı nyelvek kiegészítései, könyvtárai: nem csak a szintaktikailag, de szemantikailag is helyes példakódok formájában. A dolgozatban elıforduló kódok az érthetıség kedvéért többnyire egyszerőek, de a célnak megfelelnek, ugyanis általános igazság, hogy minden bonyolultabb probléma nála egyszerőbb részfeladatokra vezethetı vissza. Diplomamunkám fı célja az volt, hogy általános képet kapjunk a jelen, illetve a jövı hardveres- és fejlesztıi problémáiról, kihívásairól. Képesek legyünk párhuzamos módon gondolkodva át-, vagy újraírni egyszerő, soros mőködéső programjainkat, illetve végül de nem utolsó sorban -, tudjuk, hogy milyen (nyelvi-)eszközök, megoldási lehetıségek állnak rendelkezésünkre. Ebben nyújtott segítséget a különbözı sokmagos architektúrák elınyeinek, hátrányainak kielemzése mellett az egyes nyelvi elemek bemutatása,

- 94 -


Vágó Gergely

ismertetése, s az egységes csoportosítási szempontok alapján történt összehasonlítása,

tulajdonságaik

bemutatása.

Megtudhattuk,

hogy

kiértékelı napjaink

legsikeresebb, legmegbízhatóbb (C, C++, C#) és feltörekvı (Haskell) nyelvei milyen eszközökkel, kiegészítésekkel támogatják, s milyen lehetıségeket kínálnak a többmagos processzorok párhuzamos eléréséhez. Láthattuk, többségükre jellemzı tulajdonság, hogy egy párhuzamos megosztást elısegítı függvény meghívásakor a háttérben futó funkciók az operációs rendszer segítségével önállóan, a fejlesztı elıl elrejtve, munkáját egyszerősítve kezelik a magok közötti szál- illetve feladatmegosztást. Nem is gond, hiszen egy programozási nyelv akkor jó, ha a hatékonyság mellett megırzi az egyszerőségét is. Bonyolult, nehezen érthetı, ugyanakkor nagy fokú szabadságot biztosító megoldásokkal (például konkrét magokhoz való szálrendelés lehetısége) elveszíthetjük többek között az egyszerőség, az átláthatóság, az újrahasznosíthatóság, hordozhatóság, a kompatibilitás elınyeit. Erre is láthattunk példát a Stream programozás fejezetében, amikor a blokk indexek függvényében kellett a lokális indexeket áttranszformálni globálisokká. Ennél a Haskell nyújtotta lehetıségek egyszerőbbek: az állítható fordítási- és futtatási paramétereinek segítségével. Véleményem szerint a dolgozat egy jól használható alap ahhoz, ha mélyebben elmélyednénk a témában, akkor tudjuk, milyen nyelv esetén melyik eszköz, könyvtári kiegészítés használatához kell nyúlni, milyen címszavak alatt kell választ keresnünk további felmerülı kérdéseinkre, nem futva bele az ismert hibákba.

- 95 -


6.

Vágó Gergely

Irodalomjegyzék

Architektúrák, folyamatok, szálak alapfogalmai [1] Balogh Ádám, Lırentey Károly: Operációs rendszerek „elıadás jegyzet” Számítógép felépítése (cpu,memória,architektúrák,operációs rendszerek) [2] Dr. Istenes Zoltán: Számítógépes alapismeretek, „jegyzet” Párhuzamosság alapfogalmai, megközelítése, általános parallel algoritmusok [3] Iványi Antal: Párhuzamos algoritmusok, 2003, [336], ISBN: 9634635903 [4] Nancy Ann, Lynch: Osztott algoritmusok, 2002, [782], ISBN: 9639301034 Funkciónális programozás „jegyzet” [5] Hal Daume III: Yet Another Haskell Tutorial, 2002-2006, [182] Intel Multi-Core Programming [35] Shameem Akhter,Jason Roberts: Multi-Core Programming (Increasing Performance through Software Multi-threading), 2006, [336], ISBN: 0-9764832-4-6 Programozási nyelvek [39] Nyékyné Gaizler Judit: Programozási nyelvek, 2003, [759], ISBN: 963 9301 477 Párhuzamos programok tervezése [40] Ian T. Foster: Designing and Building Parallel Programs, Addison-Wesley Inc., USA, 1995. http://www.mcs.anl.gov/dbpp/ (2009-11-14) Intel - a cég processzorairól információk, ismertetık, képek, stb; párhuzamosság alapjai [6] www.intel.hu (2009-09-01) AMD – a cég processzorairól információk, ismertetık, képek, stb. [7] www.amd.hu (2009-09-01) Antennamagazin – többmagos processzor ismertetı [8] http://www.antennamagazin.hu/2006-01/11-csiptuning.html (2009-10-03) Beszeljukmac – többmagos processzorok és a jövı [9] http://beszeljukmac.com/ (2009-11-06) ITextreme – többmagos processzorok és a jövı – mobiltelefonok; CUDA leírás [10] http://www.itextreme.hu/index.php?q=hirek/3743 (2009-11-05) [11] http://www.itextreme.hu/index.php?q=hirek/3674 (2009-09-13) Machines – CPU felépítése, leírások, képek, stb. [12]http://www.machines.hu/adatok/processzorok/cpufelepites/cpufelepites.htm (2009-09-30)

- 96 -


Vágó Gergely

Oprendszer.elte – architektúrák ismertetık [13] http://oprendszer.elte.hu/architekturak (2009-06-18) Playstation – Playstation 3 leírás, ismertetı [14] http://www.us.playstation.com/PS3 (2009-09-08) HWSW – Xbox 360 leírás, ismertetı [15] http://www.hwsw.hu/cikk.php?id=28923 (2009-09-08) Prohardver – CPU architektúrák, technológiák [16]http://prohardver.hu/teszt/fokuszban_az_amd_k10_architektura/nyomtatobarat/tel jes.html (2009-10-22) HOC – Intel Platinum ismertetı [17]http://www.hoc.hu/teszt/271-msi-p35-platinum--megerkezett-hozzank-az-elsointel-bearlake/2-technologiai-hatter.html (2009-09-11) Gamechannel – AMD Athlon 64X2 ismertetı [18] http://www.gamechannel.hu/cikk/hardverzona/athlon64x2 (2009-09-03) MobilArena – többmagos processzorok mobilokba [19]http://mobilarena.hu/hir/tobbmagos_cortex-a9_processzorok_mobilokba.html (2009-11-08) HWSW – Larrabee technológia [20]http://www.hwsw.hu/hirek/38593/intel-larrabee-grafikus-piac-gpu-jovo-ev-elejenerkezik-larrabee-intel-nagyteljesitmenyu-grafikus-chipje.html (2009-09-13) DDJ – Multi-core programming [21] http://www.ddj.com/hpc-high-performance-computing/201804248 (2009-11-05) EDN – Multi-core programming (easy/difficult) [22] http://www.edn.com/article/CA6646279.html (2009-11-06) TechnologyReview – Multi-core Programming (simpler) [23] http://www.technologyreview.com/infotech/18597/?a=f (2009-11-08) Donsbot – Multi-core programming; Haskell [24] http://donsbot.wordpress.com (2009-12-08) Spectrum.ieee – többmagos processzorok és a jövı [25]http://spectrum.ieee.org/computing/hardware/multi-core-is-bad-news-forsupercomputers (2009-11-06) EmptyCreate Software – Pthreads, Boost Threads, RAII [26] http://blog.emptycrate.com/taxonomy/term/38,33,31 (2009-11-20) HackCraft – RAII - 97 -


Vágó Gergely

[27] http://www.hackcraft.net/raii/ (2009-11-22) OpenMP – OpenMP [28] http://openmp.org/wp/ (2009-11-22) Boost - Boost libraries [29] http://www.boost.org/ (2009-11-22) Cyril Zeller(nVidia): „CUDA Tutorial” [30]http://people.maths.ox.ac.uk/~gilesm/hpc/NVIDIA/NVIDIA_CUDA_Tutorial_No _NDA_Apr08.pdf (2009-11-23) Khronos Group: OpenCL [31] http://www.khronos.org/opencl/ (2009-11-23) Geoff Langdale: „Lock-Free Programming” [32] http://www.cs.cmu.edu/~410-s05/lectures/L31_LockFree.pdf (2009-11-23) ProHardver – OpenCl szabvány bemutatása [33] http://prohardver.hu/hir/elkeszult_az_opencl_szabvany.html (2009-11-25) AForge.NET – AForge.NET framework, multi-core support, AForge.Parallel [34] http://www.aforgenet.com/framework/v2.html (2009-11-26) Heterogén processzorok, NUMA [36] http://www.sigops.org/sosp/sosp09/slides/nightingale-slides-sosp09.pdf (2010-01-07) Intel C++ STM Compiler 3.0 [37]http://software.intel.com/en-us/articles/intel-c-stm-compiler-prototype-edition-20/ (2010-01-07) Tom Knight. An architecture for mostly functional languages. Proceedings of the 1986 ACM conference on LISP and functional programming [38] http://web.mit.edu/mmt/Public/Knight86.pdf (2010-01-07) Párhuzamos programozási modellek [41] R. Buyya: High Performance Cluster Computing: Architectures and Systems, Vulme 1, Programming and Applications, Vulme 2, 1999

- 98 -


Vágó Gergely

7. Köszönetnyilvánítás Szeretnék

köszönetet

mondani

konzulensemnek,

Dr.

Horváth

Zoltánnak,

diplomamunkám elkészítésében nyújtott segítségéért. Köszönöm az egyetem tanárainak, oktatóinak, munkatársainak, hogy szakmailag felkészítettek, s úgy léphetek be az önálló, nagybetıs élet kapuján, mint egy érett gondolkodású, felnıtt ember, aki nem csak a matematika és programozás világában, de számos más területen is képes lesz helytállni. Szeretném megköszönni szüleimnek, barátaimnak a sok türelmet, megértést és bíztatást, míg eljutottam idáig.

- 99 -

Többmagos processzorok programozhatósága Vágó Gergely. Programtervezı Matematikus szak nappali tagozat. Témavezetı: Dr

Recommend Documents