Dr. habil. Maróti György

TÁMOP-4.2.2.C-11/1/KONV-2012-0004 Nemzeti kutatóközpont fejlett infokommunikációs technológiák kidolgozására és piaci bevezetésére

III.8. MÓDSZER KIDOLGOZÁSA ALGORITMUSOK ÁTÜLTETÉSÉRE KIS SZÁMÍTÁSI TELJESÍTMÉNYŰ ESZKÖZÖKBŐL ÁLLÓ NÉPES HETEROGÉN INFRASTRUKTÚRA

Dr. habil. Maróti György [email protected]

TÁMOP-4.2.2.C-11/1/KONV-2012-0004 Nemzeti kutatóközpont fejlett infokommunikációs technológiák kidolgozására és piaci bevezetésére

A CSAPAT

Munkatárs

Feladat

Imreh Csanád

1. A lokális kereső és a korlátozás és szétválasztáson alapul algoritmusok párhuzamosítási technikáinak áttekintése 2. Új lokális kereső és/vagy korlátozás és szétválasztáson alapuló párhuzamosított algoritmus fejlesztése heterogén rendszerre

Vinkó Tamás

1. A genetikus és egyéb populáció alapú algoritmusok párhuzamosítási technikáinak áttekintése 2. Új genetikus és/vagy egyéb populáció alapú párhuzamosított algoritmus fejlesztése heterogén rendszerre

Dwornik Marek

1. Boinc rendszer megismerése. A rendszer felkészítése a tervezett algoritmusok implementálására. 2. A fejlesztett algoritmusok implementálása

Szint 100% 80%

100% 80%

100% 20% 2

KORLÁTOZÁS ÉS SZÉTVÁLASZTÁS 1.

TÁMOP-4.2.2.C-11/1/KONV-2012-0004 Nemzeti kutatóközpont fejlett infokommunikációs technológiák kidolgozására és piaci bevezetésére

3

KORLÁTOZÁS ÉS SZÉTVÁLASZTÁS 2.

TÁMOP-4.2.2.C-11/1/KONV-2012-0004 Nemzeti kutatóközpont fejlett infokommunikációs technológiák kidolgozására és piaci bevezetésére

4

KORLÁTOZÁS ÉS SZÉTVÁLASZTÁS 3.

TÁMOP-4.2.2.C-11/1/KONV-2012-0004 Nemzeti kutatóközpont fejlett infokommunikációs technológiák kidolgozására és piaci bevezetésére

 Nem a teljes megoldástért járjuk be, hanem bizonyos részfákat kizárunk.  Azokat a részfákat zárhatjuk ki, amelyekre egy korlátozó függvény segítségével (ami alsó korlátot ad az ottani megoldások értékére) tudjuk, hogy nincs bennük jobb megoldás az eddig ismert legjobbnál.  Egy részfa bejárása a gyökér megvizsgálása után az alatta levő szinten elhelyezkedő részfák bejárására vezetődik vissza.

5

KORLÁTOZÁS ÉS SZÉTVÁLASZTÁS PÁHUZAMOSÍTÁSA

TÁMOP-4.2.2.C-11/1/KONV-2012-0004 Nemzeti kutatóközpont fejlett infokommunikációs technológiák kidolgozására és piaci bevezetésére

Különböző részfákat egyszerre is bejárhatunk párhuzamos szálakon. A korlátozó függvény számításához is használhatunk párhuzamosított algoritmusokat.

Amennyiben párhuzamosan járjuk be a részfákat, akkor alapvető kérdés miként osztjuk ki a feladatokat  a párhuzamos szálak egy listából választanak vagy  minden szálnak saját listája van. 6

TÁMOP-4.2.2.C-11/1/KONV-2012-0004

GENETIKUS ALGORITMUS 1.

Nemzeti kutatóközpont fejlett infokommunikációs technológiák kidolgozására és piaci bevezetésére

 1. generáció = 0  2. kezdő populáció létrehozása  Véletlen kiválasztás

 3. mindaddig, amíg a megállási feltétel nem teljesül  (a) generáció = generáció + 1  (b) fitnessz kiszámítása  (c) szelekció  Szelekciós operátor kiválaszt néhány egyedet  (d) keresztezés(psz)  A kiválasztott egyedekből keresztezéssel új populáció  (e) mutáció(pm)  Véletlenszerűen javít vagy ront a populáción 7

TÁMOP-4.2.2.C-11/1/KONV-2012-0004

GENETIKUS ALGORITMUS 2.

Nemzeti kutatóközpont fejlett infokommunikációs technológiák kidolgozására és piaci bevezetésére

 A genetikus algoritmus minden iterációs lépésben megoldások egy populációját tartja nyilván.  Egy populációból elsőként ki kell választani mely elemeket használjuk a következő populáció elkészítésére, általában egy fitnesz függvény alapján.

 Kereszteződéssel új utódokat képzünk.  Ezeket esetleg megváltoztatjuk a mutáció operátorral.  Az így kapott elemekből és esetleg néhány régebbi elemből képezzük az új populációt. 8

GENETIKUS TÍPUSÚ ALGORITMUSOK PÁRHUZAMOSÍTÁSA

TÁMOP-4.2.2.C-11/1/KONV-2012-0004 Nemzeti kutatóközpont fejlett infokommunikációs technológiák kidolgozására és piaci bevezetésére

 Fitnesz függvény párhuzamos számítása.

 Mutációk párhuzamos számolása.  A sziget modellben különböző alpopulációk vannak, amelyek között lehet elemeket cserélni, és ezeket kezelhetjük párhuzamosan.  Lehetséges különböző genetikus szabályok alapján futó algoritmusokat futtatni az egyes alpopulációkon.

9

TÁMOP-4.2.2.C-11/1/KONV-2012-0004

FŐ CÉLKITŰZÉSEK

Nemzeti kutatóközpont fejlett infokommunikációs technológiák kidolgozására és piaci bevezetésére

 Nehéz feladatok megoldása során, a kifejlesztett algoritmusok párhuzamosítása és több processzoron vagy eszközön való futtatása jelentő hatékonyság növeléssel járhat.  Általában homogén rendszereket vizsgálnak, ahol egyforma eszközökön hasonló algoritmusok futnak.  A téma célja az, hogy olyan algoritmusokat fejlesszünk, melyek figyelembe veszik a párhuzamosan dolgozó eszközök heterogenitását.

12

TÁMOP-4.2.2.C-11/1/KONV-2012-0004

ÚJ HIBRID ALGORITMUS

Nemzeti kutatóközpont fejlett infokommunikációs technológiák kidolgozására és piaci bevezetésére

 A különböző szálakon más típusú eljárások futnak.

 Egyszerre futtatunk egy egzakt megoldó korlátozás és szétválasztás alapú algoritmust és egy heurisztikát.  A heurisztika által kapott megoldás használható a korlátozásnál a megoldástér hatékonyabb vágására.  A korlátozás és szétválasztásnál kapott aktuális megoldásokból indíthat keresést egy lokális kereső szál.

14

TÁMOP-4.2.2.C-11/1/KONV-2012-0004

A BOINC RENDSZER

Nemzeti kutatóközpont fejlett infokommunikációs technológiák kidolgozására és piaci bevezetésére

 Az algoritmusok tesztelésére a Boinc rendszert tervezzük használni.  Ez egy Berkeley-n fejlesztett szerver-kliens alapú nyílt forráskódú rendszer.  A szoftverrendszer segítségével összeköthetőek különböző eszközök (például számítógépek és androidos telefonok) így a rendszer jól használható heterogén számítási eszközökre tervezett algoritmusok elemzésére.

15

TÁMOP-4.2.2.C-11/1/KONV-2012-0004

EREDMÉNYEK, TERVEK







Nemzeti kutatóközpont fejlett infokommunikációs technológiák kidolgozására és piaci bevezetésére

Ami elkészült 

B&B Szakirodalom áttekintése, összefoglalása (13 oldal)



GA Szakirodalom áttekintése, összefoglalása (13 oldal)



A BOINC rendszer ismertetése (10 oldal)

Ami folyamatban van 

Algoritmusok kidolgozása

január 20



Implementáció

január 31

További feladatok 

Szimulációk, tesztek futtatása



Futási eredmények kiértékelése, dokumentálása 16

TÁMOP-4.2.2.C-11/1/KONV-2012-0004 Nemzeti kutatóközpont fejlett infokommunikációs technológiák kidolgozására és piaci bevezetésére

KÖSZÖNÖM A FIGYELMET!