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. "JÖVŐ INTERNET" TECHNOLÓGIÁK: ELOSZTOTT ÉS FELHŐ SZOLGÁLTATÁSOK, TÁRGYAK INTERNETE
DR. SIMON GYULA
TÁMOP-4.2.2.C-11/1/KONV-2012-0004
TÉMÁK
Nemzeti kutatóközpont fejlett infokommunikációs technológiák kidolgozására és piaci bevezetésére
1. Szenzorhálózatra épülő elosztott felügyeleti rendszer kidolgozása Témavezető: Simon Gyula, PE 2. Smart grid rendszerek kutatása Témavezető: Kovács Lóránt, GAMF 3. Párhuzamos lineáris programozási feladatmegoldó kidolgozása Témavezető: Maros István, PE 4. Feladatfüggő felépítésű pipeline többprocesszoros rendszerek tervezési módszerének kidolgozása és alkalmazása nagy sebességigényű beágyazott célrendszerekben Témavezető: Arató Péter, BME; Brassai Sándor Tihamér, Sapientia 5. Kiloprocesszoros rendszerek logisztikai alkalmazása Témavezető: Szolgay Péter, PPKE 6. Map reduce elvű elosztott feldolgozási algoritmusok és tesztkörnyezet kidolgozása adatbányászati feladatok végrehajtásához Témavezető: Pálvölgyi János, Kürt Zrt. 7. Módszer és tesztkörnyezet kidolgozása kritikus válaszidejű felhő szolgáltatások kialakításához és erőforrás elosztásához Témavezető: Maróti György, PE 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úrára Témavezető: Maróti György, PE 2
TÁMOP-4.2.2.C-11/1/KONV-2012-0004
III.1. TÉMA
Nemzeti kutatóközpont fejlett infokommunikációs technológiák kidolgozására és piaci bevezetésére
1. Szenzorhálózatra épülő elosztott felügyeleti rendszer kidolgozása Témavezető: Simon Gyula, PE 2. Smart grid rendszerek kutatása Témavezető: Kovács Lóránt, GAMF 3. Párhuzamos lineáris programozási feladatmegoldó kidolgozása Témavezető: Maros István, PE 4. Feladatfüggő felépítésű pipeline többprocesszoros rendszerek tervezési módszerének kidolgozása és alkalmazása nagy sebességigényű beágyazott célrendszerekben Témavezető: Arató Péter, BME; Brassai Sándor Tihamér, Sapientia 5. Kiloprocesszoros rendszerek logisztikai alkalmazása Témavezető: Szolgay Péter, PPKE 6. Map reduce elvű elosztott feldolgozási algoritmusok és tesztkörnyezet kidolgozása adatbányászati feladatok végrehajtásához Témavezető: Pálvölgyi János, Kürt Zrt. 7. Módszer és tesztkörnyezet kidolgozása kritikus válaszidejű felhő szolgáltatások kialakításához és erőforrás elosztásához Témavezető: Maróti György, PE 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úrára Témavezető: Maróti György, PE 3
TÁMOP-4.2.2.C-11/1/KONV-2012-0004
CÉLOK
Adatforrások – Szenzorikus források • Szenzorhálózatok • Internet of Things – Multimodális szenzorok Szenzorok adatainak feldolgozása – Intelligens – Öntanuló módon Feldolgozás – Hálózaton belül – Szolgáltató eszközein Kihívások – Kommunikáció – Adattárolás – Feldolgozás
Nemzeti kutatóközpont fejlett infokommunikációs technológiák kidolgozására és piaci bevezetésére
Kutatási területek: •
Szenzorhálózatok és elosztott rendszerek gráfelméleti vizsgálata
•
Szenzorhálózati szolgáltatások kutatása és fejlesztése
•
Képfeldolgozási algoritmusok fejlesztése
•
Szenzorok alkalmazástechnikájának vizsgálata
•
Felhő alapú szolgáltatások vizsgálata
•
Tesztrendszerek fejlesztése
4
TÁMOP-4.2.2.C-11/1/KONV-2012-0004
EREDMÉNYEK
Nemzeti kutatóközpont fejlett infokommunikációs technológiák kidolgozására és piaci bevezetésére
Szenzorhálózatok és elosztott rendszerek gráfelméleti vizsgálata
• • • •
Approximálási eredmények hipergráfok csúcslefogási tulajdonságaira Gráfdominálási paraméterekre vonatkozó eredmények Gráfok minimális összefüggő részeinek vizsgálata Új eredmények tropikus dominálás témakörben, illetve tropikus domináló halmazok approximálhatóságáról • Új eredmények gráfok ún. WORM színezésének témakörében • Új eredmények gyűrű topológiájú hálózatok TDMA ütemezésének témakörben Szenzorhálózati szolgáltatások kutatása és fejlesztése • Energiatakarékos kommunikációs protokollok • TDMA ütemezési algoritmusok • Garantált minőséget biztosító kommunikációs protokollok • Időszinkronizációs protokollok
5
TÁMOP-4.2.2.C-11/1/KONV-2012-0004
EREDMÉNYEK
Nemzeti kutatóközpont fejlett infokommunikációs technológiák kidolgozására és piaci bevezetésére
Képfeldolgozási algoritmusok fejlesztése – Objektumfelismerés és –követés vizsgálatára szolgáló keretrendszer és tesztadatbázis kialakítása – Kernel alapú mozgásdetekciós algoritmusok alkalmazhatóságának vizsgálata mozgó kamera esetén – Bag of Words módszer alkalmazásának vizsgálata – Forgatás invariancia biztosítása globális képi leírók (CEDD) esetén – Képi indexelést és visszakeresést végző szerver bővítése LoCATe leíróval
Szenzorok alkalmazástechnikájának vizsgálata – – – –
Felhő alapú szolgáltatások szenzorhálózatokhoz illesztése Hatékony jelfeldolgozó algoritmusok kidolgozása Új típusú rádióinterferencia-alapú érzékelési eljárások kidolgozása Új típusú beltéri lokalizációs eljárások kidolgozása
6
TÁMOP-4.2.2.C-11/1/KONV-2012-0004
III.2. TÉMA
Nemzeti kutatóközpont fejlett infokommunikációs technológiák kidolgozására és piaci bevezetésére
1. Szenzorhálózatra épülő elosztott felügyeleti rendszer kidolgozása Témavezető: Simon Gyula, PE 2. Smart grid rendszerek kutatása Témavezető: Kovács Lóránt, GAMF 3. Párhuzamos lineáris programozási feladatmegoldó kidolgozása Témavezető: Maros István, PE 4. Feladatfüggő felépítésű pipeline többprocesszoros rendszerek tervezési módszerének kidolgozása és alkalmazása nagy sebességigényű beágyazott célrendszerekben Témavezető: Arató Péter, BME; Brassai Sándor Tihamér, Sapientia 5. Kiloprocesszoros rendszerek logisztikai alkalmazása Témavezető: Szolgay Péter, PPKE 6. Map reduce elvű elosztott feldolgozási algoritmusok és tesztkörnyezet kidolgozása adatbányászati feladatok végrehajtásához Témavezető: Pálvölgyi János, Kürt Zrt. 7. Módszer és tesztkörnyezet kidolgozása kritikus válaszidejű felhő szolgáltatások kialakításához és erőforrás elosztásához Témavezető: Maróti György, PE 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úrára Témavezető: Maróti György, PE 7
TÁMOP-4.2.2.C-11/1/KONV-2012-0004
CÉLOK
Nemzeti kutatóközpont fejlett infokommunikációs technológiák kidolgozására és piaci bevezetésére
Motiváció A smart gridekben (intelligens energiaelosztó hálózatokban) az intelligens mérők tengernyi adatot szolgáltatnak. Kérdés: Mit tudunk ebből az adattömegből és milyen módszerekkel kinyerni? Kutatási területek: • Új jelfeldolgozási eljárások villamos fogyasztási idősorok – szegmentálására (stacioner szakaszok fölismerése JensenShannon divergencia alapján); – osztályba sorolására (klasszifikáció predikció alapú módszerrel)
•
Az intelligens mérők (elosztott) számítási kapacitásának kihasználása elosztott optimalizációs eljárások alkalmazásával.
8
TÁMOP-4.2.2.C-11/1/KONV-2012-0004
EREDMÉNYEK
Nemzeti kutatóközpont fejlett infokommunikációs technológiák kidolgozására és piaci bevezetésére
Statisztikai váltási pont detektálása
Feladat: Fogyasztási idősorban a statisztikai váltási pontok felismerése Megoldás: • Jensen-Shannon divergencia alapján • Rekurzív algoritmus globális (off-line) elemzéshez Jelentőség: egzakt mérték definiálható arra nézve, hogy a szakaszhatár tényleg váltási pont-e statisztikai értelemben. • Mozgóablakos algoritmus lokális (online) elemzéshez, real-time alkalmazáshoz „smart meter”-ben. 9
TÁMOP-4.2.2.C-11/1/KONV-2012-0004
EREDMÉNYEK
Nemzeti kutatóközpont fejlett infokommunikációs technológiák kidolgozására és piaci bevezetésére
Szegmensek osztályba sorolása Feladat: Adott szegmensek milyen osztályba tartoznak?
Megoldás:
• • •
Predikciós alapú módszer A fogyasztási idősor értékei közötti időbeli korreláltság kihasználása Több (NL) prediktor párhuzamos működtetése Legjobb prediktor azonosítja az osztályt A klasszifikációs képességen túl a módszerrel lehetséges – Mérési hibák detekciója – Elektromos fogyasztás becslése
0.5 0.45 0.4 0.35 Detection Error Rate
• •
0.3 0.25
SOM SVNC k-NN Fuzzy NN Seq DM (PrefixSPAN) Prediction
0.2 0.15 0.1 0.05
10
0 Autoregressive
Markovian Process Normalized AR Type of timereries
Normalized Markovian
TÁMOP-4.2.2.C-11/1/KONV-2012-0004
III.3. TÉMA
Nemzeti kutatóközpont fejlett infokommunikációs technológiák kidolgozására és piaci bevezetésére
1. Szenzorhálózatra épülő elosztott felügyeleti rendszer kidolgozása Témavezető: Simon Gyula, PE 2. Smart grid rendszerek kutatása Témavezető: Kovács Lóránt, GAMF 3. Párhuzamos lineáris programozási feladatmegoldó kidolgozása Témavezető: Maros István, PE 4. Feladatfüggő felépítésű pipeline többprocesszoros rendszerek tervezési módszerének kidolgozása és alkalmazása nagy sebességigényű beágyazott célrendszerekben Témavezető: Arató Péter, BME; Brassai Sándor Tihamér, Sapientia 5. Kiloprocesszoros rendszerek logisztikai alkalmazása Témavezető: Szolgay Péter, PPKE 6. Map reduce elvű elosztott feldolgozási algoritmusok és tesztkörnyezet kidolgozása adatbányászati feladatok végrehajtásához Témavezető: Pálvölgyi János, Kürt Zrt. 7. Módszer és tesztkörnyezet kidolgozása kritikus válaszidejű felhő szolgáltatások kialakításához és erőforrás elosztásához Témavezető: Maróti György, PE 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úrára Témavezető: Maróti György, PE 11
TÁMOP-4.2.2.C-11/1/KONV-2012-0004
CÉLOK
•
•
•
Nemzeti kutatóközpont fejlett infokommunikációs technológiák kidolgozására és piaci bevezetésére
Projektünkben egy, a parallel architektúrát kihasználó lineáris programozási megoldó kifejlesztését tűztük ki célul:
•
Széleskörű alkalmazási lehetőségek, a megoldható feladatok körének jelentős kiterjesztése
•
A lineáris programozás más optimalizáló eljárások motorjául szolgál
Napjainkban a piacon kb. egy fél tucat lineáris optimalizáló szoftver érhető el, azonban:
•
Ezek kereskedelmi, vagy nyílt forrású akadémiai rendszerek
•
A nyílt rendszerek rosszul dokumentáltak, kutatási célra nem használhatóak, a kereskedelmi rendszerek fekete dobozként állnak rendelkezésre
A kutatócsoport saját optimalizáló rendszerének kifejlesztése: •
Saját innovatív ötleteink megvalósításához egy modulárisan bővíthető, általunk kezelhető rendszerre van szükségünk
•
Korábbi párhuzamosítási törekvések kevés sikerrel jártak a témában
12
TÁMOP-4.2.2.C-11/1/KONV-2012-0004
EREDMÉNYEK
Nemzeti kutatóközpont fejlett infokommunikációs technológiák kidolgozására és piaci bevezetésére
• A szimplex algoritmus kutatásának eredményei: • A szimplex algoritmushoz egy robosztus párhuzamos keresést támogató keretrendszert készítettünk • Egyedülálló összehasonlító elemzést végeztünk a degeneráció-ellenes stratégiák összehasonlítására, melynek eredményeként azok egyedi kombinációját dolgoztuk ki • Azonosítottuk a szimplex módszer paramétereit melyek hatékony beállítását egy grid infrastruktúrájú paramétervizsgálattal végeztük el
• Az implementációs technikák kutatásának eredményei: •
Teljesítményanalízissel azonosítottuk a lineáris algebrai adatszerkezetek kulcsfontosságú tényezőit
•
Adaptív kiterjesztett pontosságú számítási architektúrát dolgoztunk ki
•
Kidolgoztunk egy stabil összeadási módszert a szimplex algoritmus numerikus stabilizálására
13
TÁMOP-4.2.2.C-11/1/KONV-2012-0004
EREDMÉNYEK
Nemzeti kutatóközpont fejlett infokommunikációs technológiák kidolgozására és piaci bevezetésére
A kidolgozott Pannon Optimizer rendszer •
Új kiemelkedő hatékonyságú lineáris algebrai kernel •
•
•
Elemző szoftver a ritkás adatszerkezetek teljesítményanalízisére
Stabil primál és duál szimplex algoritmus •
Skálázó, előfeldolgozó modulok
•
Párhuzamos keresést és szinkronizálást támogató keretrendszer
•
Numerikus stabilitási eljárások
•
Numerikusan kiemelkedően instabil feladatok megoldásának támogatása
•
Általános célú paraméterezés vizsgáló keretrendszer
•
Grafikus felhasználói felület
•
MPS, LP és kézi formátum támogatása
•
A nyílt forráskódú megoldókkal versenyképes teljesítmény
Számos újszerű modul és eljárás került kidolgozásra és implementálásra
14
TÁMOP-4.2.2.C-11/1/KONV-2012-0004
III.4. TÉMA
Nemzeti kutatóközpont fejlett infokommunikációs technológiák kidolgozására és piaci bevezetésére
1. Szenzorhálózatra épülő elosztott felügyeleti rendszer kidolgozása Témavezető: Simon Gyula, PE 2. Smart grid rendszerek kutatása Témavezető: Kovács Lóránt, GAMF 3. Párhuzamos lineáris programozási feladatmegoldó kidolgozása Témavezető: Maros István, PE 4. Feladatfüggő felépítésű pipeline többprocesszoros rendszerek tervezési módszerének kidolgozása és alkalmazása nagy sebességigényű beágyazott célrendszerekben Témavezetők: Arató Péter, BME; Brassai Sándor Tihamér, Sapientia 5. Kiloprocesszoros rendszerek logisztikai alkalmazása Témavezető: Szolgay Péter, PPKE 6. Map reduce elvű elosztott feldolgozási algoritmusok és tesztkörnyezet kidolgozása adatbányászati feladatok végrehajtásához Témavezető: Pálvölgyi János, Kürt Zrt.
7. Módszer és tesztkörnyezet kidolgozása kritikus válaszidejű felhő szolgáltatások kialakításához és erőforrás elosztásához Témavezető: Maróti György, PE 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úrára Témavezető: Maróti György, PE
15
TÁMOP-4.2.2.C-11/1/KONV-2012-0004
CÉLOK
Háttér: • Igény egyre komplexebb többprocesszoros rendszertechnikai megoldásokra • Rendszerelemek (mikroprocesszorok, FPGA célhardver egységek, DSP, GPU, neurális tömbök) egyre komplexebbek • Feladat dekompozíciója alapvetően meghatározza az eredő rendszer teljesítőképességét • Az ilyen rendszereket feladatfüggő felépítésű többprocesszoros rendszernek (Task-Dependent Multiprocessing System, TDMS) nevezzük
Nemzeti kutatóközpont fejlett infokommunikációs technológiák kidolgozására és piaci bevezetésére
Kutatási cél: •
Új rendszer-szintű tervező eszköz kidolgozása, amely az alábbi támogatásokat nyújtja a TDMS tervezés folyamatában:
•
A megoldandó feladat magas szintű programnyelvi leírásának fogadását.
•
A komponens processzorok közötti feladatmegosztásra olyan új dekompozíciós algoritmus alkalmazását, amely lehetővé teszi célfüggvényében a komponens processzorok fajtájának és darabszámának, valamint a rendszerkövetelményeknek és azok kívánt prioritásának előírását.
•
A magas szintű szintézis (HLS) algoritmusainak felhasználását.
16
TÁMOP-4.2.2.C-11/1/KONV-2012-0004
EREDMÉNYEK
Nemzeti kutatóközpont fejlett infokommunikációs technológiák kidolgozására és piaci bevezetésére
A teljes rendszer által megoldandó feladat C vagy Haskell nyelvű leírásának fogadása A tervező által megadandó követelmények: A komponens processzorokra vonatkozóan - számuk - fajtájuk - kapacitásuk - minimális kitöltöttségük (energafelhasználás) - áruk - működésük párhuzamos feldolgozásra való alkalmasságuk - utasítás-végrehajtási időik Pipeline működés szükségessége - a kívánt újraindítási idő A kommunikációs teher (adatcsere mennyiség), sebesség, ár kívánt prioritási sorrendje az optimalizálás során.
Dekompozíció Módosított HLS tervező eszköz (PIPE)
Eredmények XML file formátumban:
Komponens processzorok (számuk, fajtáik (μP, DSP, FPGA, GPU, célhardware, etc.). Az utasítások hozzárendelése az egyes komponens processzorokhoz. Kommunikációs teher (adatcsere mennyiség).
17
TÁMOP-4.2.2.C-11/1/KONV-2012-0004
EREDMÉNYEK
Nemzeti kutatóközpont fejlett infokommunikációs technológiák kidolgozására és piaci bevezetésére
Új rendszerszintű szintézis módszer és kísérleti tervező eszköz (DECHLS), amely lehetővé teszi a szisztematikus szintézist a magas szintű programnyelven adott feladatleírásból kiindulva az intuitív tervezési lépéseknek a lehető legnagyobb mértékű kiiktatása mellett. Input 1
Input 2
FFT1 P1
FFT2
SC2
SC1
Execution time: 138 ms
Input 4
FFT3
FFT4 P4
P3
P2
Execution time: 138 ms
Input 3
SC3 Execution time: 138 ms
SC4 Execution time: 138 ms
VOTE P5 HT Execution time: 3438 ms Output
R>3438ms
18
R=1613ms
TÁMOP-4.2.2.C-11/1/KONV-2012-0004
KIALAKÍTOTT TESZT HARDVER
Nemzeti kutatóközpont fejlett infokommunikációs technológiák kidolgozására és piaci bevezetésére
• Neuro-fuzzy rendszerek újrakonfigurálható digitális áramkörben való megvalósítása • súlyadaptációs modul párhuzamosan működik a kimenetszámítással (kimenet számítása és a tanítás is mintánként) • gyors hardvereszköz: kimenetszámítás tanítással együtt 0,6 𝜇s alatt • A kialakított architektúra lehetőséget biztosít különböző tanító algoritmusok tesztelésére és valós gyakorlati feladatokban való alkalmazásra.
19
TÁMOP-4.2.2.C-11/1/KONV-2012-0004
III.5. TÉMA
Nemzeti kutatóközpont fejlett infokommunikációs technológiák kidolgozására és piaci bevezetésére
1. Szenzorhálózatra épülő elosztott felügyeleti rendszer kidolgozása Témavezető: Simon Gyula, PE 2. Smart grid rendszerek kutatása Témavezető: Kovács Lóránt, GAMF 3. Párhuzamos lineáris programozási feladatmegoldó kidolgozása Témavezető: Maros István, PE 4. Feladatfüggő felépítésű pipeline többprocesszoros rendszerek tervezési módszerének kidolgozása és alkalmazása nagy sebességigényű beágyazott célrendszerekben Témavezető: Arató Péter, BME; Brassai Sándor Tihamér, Sapientia 5. Kiloprocesszoros rendszerek logisztikai alkalmazása Témavezető: Szolgay Péter, PPKE 6. Map reduce elvű elosztott feldolgozási algoritmusok és tesztkörnyezet kidolgozása adatbányászati feladatok végrehajtásához Témavezető: Pálvölgyi János, Kürt Zrt. 7. Módszer és tesztkörnyezet kidolgozása kritikus válaszidejű felhő szolgáltatások kialakításához és erőforrás elosztásához Témavezető: Maróti György, PE 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úrára Témavezető: Maróti György, PE 20
TÁMOP-4.2.2.C-11/1/KONV-2012-0004
CÉLOK
Nemzeti kutatóközpont fejlett infokommunikációs technológiák kidolgozására és piaci bevezetésére
Motiváció Mega –giga processzor tömbök,
Eddig nem kézben tartható problémák, ahol a jellemzők: • femtosec (10-15 s) • petaflops (1015 flops) • A geometriai közelségnek döntő szerepe van • nincs univerzálisan optimális architektúra Cél • Keresünk egy jó megoldást egy adott probléma osztályhoz • Adott algoritmus leképzése 2D-3D processzortömbre • Optimalizálás a felületre, pontosságra, sebességre, disszipált teljesítményre, sávszélességre Korlátok- megkötések • Virtuális és fizikai processzorok • Memória korlát a chipen • A külső memóriát véges sávszélességen érjük el. 21
TÁMOP-4.2.2.C-11/1/KONV-2012-0004
EREDMÉNYEK
Nemzeti kutatóközpont fejlett infokommunikációs technológiák kidolgozására és piaci bevezetésére
Módszer Strukturált Rácsokra
• A felosztás is legyen strukturált (rács-típusú) • A rács-típusú felosztások közül a feltételeknek megfelelő optimális felosztás meghatározható (mivel ezek száma O(K*ln2(K)), ahol legfeljebb K részre vághatjuk fel a rácsot)
Eredmény • METIS partíciókhoz képest akár 50%-os adatlokalitás javulás is elérhető azonos kommunikációs szükséglettel. • Egy esetben sem adott rosszabb eredményt, nagyobb rácsokra a kommunikációs szükséglet is javult. 22
TÁMOP-4.2.2.C-11/1/KONV-2012-0004
EREDMÉNYEK
Nemzeti kutatóközpont fejlett infokommunikációs technológiák kidolgozására és piaci bevezetésére
Módszer általános esetre • • •
Az adatlokalitás növelése és a processzorközi kommunikáció csökkentése egymással ellentétes célok. Kidolgozásra kerültek módszerek, amelyek az adatlokalitásra fókuszáltak, viszont ezek nem kezelték megfelelően a processzorközi kommunikációt. Mivel a processzorközi kommunikáció csökkentése már régóta kutatott terület jó megoldókkal, így egy METIS-AM1 hibrid módszert dolgoztunk ki, amiben az AM1 rész saját fejlesztés 4.5
Eredmény • A METIS-AM1 hibrid segítségével az adatlokalitás és processzorközi kommunikáció együttesen kezelhető További cél • Olyan megoldó, ami nem egy kommunikációra optimalizált megoldásból indul ki, hanem ténylegesen egyszerre kezeli a két feltételt.
Performance (Million triangle update/s)
4 3.5 3 2.5 2 1.5 1 0.5 0 0
100000
200000
300000
Number of triangles unordered
reordered
400000
23
TÁMOP-4.2.2.C-11/1/KONV-2012-0004
III.6. TÉMA
Nemzeti kutatóközpont fejlett infokommunikációs technológiák kidolgozására és piaci bevezetésére
1. Szenzorhálózatra épülő elosztott felügyeleti rendszer kidolgozása Témavezető: Simon Gyula, PE 2. Smart grid rendszerek kutatása Témavezető: Kovács Lóránt, GAMF 3. Párhuzamos lineáris programozási feladatmegoldó kidolgozása Témavezető: Maros István, PE 4. Feladatfüggő felépítésű pipeline többprocesszoros rendszerek tervezési módszerének kidolgozása és alkalmazása nagy sebességigényű beágyazott célrendszerekben Témavezető: Arató Péter, BME; Brassai Sándor Tihamér, Sapientia 5. Kiloprocesszoros rendszerek logisztikai alkalmazása Témavezető: Szolgay Péter, PPKE 6. Map reduce elvű elosztott feldolgozási algoritmusok és tesztkörnyezet kidolgozása adatbányászati feladatok végrehajtásához Témavezető: Pálvölgyi János, Kürt Zrt. 7. Módszer és tesztkörnyezet kidolgozása kritikus válaszidejű felhő szolgáltatások kialakításához és erőforrás elosztásához Témavezető: Maróti György, PE 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úrára Témavezető: Maróti György, PE 24
TÁMOP-4.2.2.C-11/1/KONV-2012-0004
CÉLOK
Nemzeti kutatóközpont fejlett infokommunikációs technológiák kidolgozására és piaci bevezetésére
Kutatás célja: • Adatbányászati algoritmusok elosztott megvalósításainak vizsgálata Módszer: • Felépítettünk egy általános célú klasztert, ahol vizsgálni lehet elosztott algoritmusokat. – –
5 gép (Teljes kapacitás: 40 CPU mag, 20x500GB disk, 160GB RAM, dedikált hálózat) Hadoop ökoszisztéma: HDFS, Map-Reduce, és Appache Spark
• Többféle algoritmus osztályból vizsgáltunk algoritmusokat, melyek elosztott implementáció szempontjából különböző kihívásokat jelentenek. – –
I/O intenzív algoritmusok skálázódása elosztott rendszereken Deep learning algoritmusok vizsgálata elosztott környezetben
25
TÁMOP-4.2.2.C-11/1/KONV-2012-0004
EREDMÉNYEK
Nemzeti kutatóközpont fejlett infokommunikációs technológiák kidolgozására és piaci bevezetésére
I/O intenzív algoritmusok
• Log normalizálás: –
A HW összes magját kihasználva jelentős sebesség javulás értünk el. A hardware-k közötti IO sebesség eltérés eltűnt, mivel a számítások több időt igényelnek, mint maga az IO művelet.
• Számítások párhuzamosítása: –
Addig releváns, amíg nem érjük el az IO sebességét. Ha a számítás sebessége azonos az IO művelettel,, akkor további sebességnövekedést már csak az együttes párhuzamosítással érhető el (IO és CPU)
• Batch módú feldolgozás 6,83 szoros gyorsulást hozott
26
TÁMOP-4.2.2.C-11/1/KONV-2012-0004
EREDMÉNYEK
Nemzeti kutatóközpont fejlett infokommunikációs technológiák kidolgozására és piaci bevezetésére
Deep learning algoritmus osztály skálázódásának vizsgálata elosztott környezetben • Dropout – –
Első lépésben reprodukáltunk egy újnak számító hatékony tanítási eljárást (dropout) Egy gépes, egy szálas implementációt hoztunk létre, ehhez hasonlítottuk a párhuzamosítási kíséreltek eredményeit.
• Metaparaméter optimalizáció – – –
Több gépes környezetben a meta paraméter optimalizálás lehetőségeit vizsgáltuk (Monte Carlo, Bayes módszer). Arra a megfigyelésre jutottunk, hogy a Bayes módszer nem hatékony a teszthalmazon mért hiba és a tanításra fordított idő optimalizálására. Ezen módszer alkalmazásánál kénytelenek vagyunk konszenzusra jutni, melyik paraméter a fontosabb a klasszifikációs feladat megoldása szempontjából.
27
TÁMOP-4.2.2.C-11/1/KONV-2012-0004
III.7. TÉMA
Nemzeti kutatóközpont fejlett infokommunikációs technológiák kidolgozására és piaci bevezetésére
1. Szenzorhálózatra épülő elosztott felügyeleti rendszer kidolgozása Témavezető: Simon Gyula, PE 2. Smart grid rendszerek kutatása Témavezető: Kovács Lóránt, GAMF 3. Párhuzamos lineáris programozási feladatmegoldó kidolgozása Témavezető: Maros István, PE 4. Feladatfüggő felépítésű pipeline többprocesszoros rendszerek tervezési módszerének kidolgozása és alkalmazása nagy sebességigényű beágyazott célrendszerekben Témavezető: Arató Péter, BME; Brassai Sándor Tihamér, Sapientia 5. Kiloprocesszoros rendszerek logisztikai alkalmazása Témavezető: Szolgay Péter, PPKE 6. Map reduce elvű elosztott feldolgozási algoritmusok és tesztkörnyezet kidolgozása adatbányászati feladatok végrehajtásához Témavezető: Pálvölgyi János, Kürt Zrt. 7. Módszer és tesztkörnyezet kidolgozása kritikus válaszidejű felhő szolgáltatások kialakításához és erőforrás elosztásához Témavezető: Maróti György, PE 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úrára Témavezető: Maróti György, PE 28
TÁMOP-4.2.2.C-11/1/KONV-2012-0004
CÉLOK
Nemzeti kutatóközpont fejlett infokommunikációs technológiák kidolgozására és piaci bevezetésére
Kutatási cél • Kritikus válaszidejű felhő számítási feladat allokációja – matematikai modell megalkotása – különböző algoritmusok fejlesztése, • Szimulációs környezet fejlesztése, tesztelése • Az algoritmusok generált adatokon való futtatása, • A szimuláció során kapott eredményeket értékelése
Feladatok • Allokációs algoritmusok kiválasztása • Adatgenerálás a tesztekhez • Fejlesztési és szimulációs környezet kialakítása 29
TÁMOP-4.2.2.C-11/1/KONV-2012-0004
EREDMÉNYEK
Nemzeti kutatóközpont fejlett infokommunikációs technológiák kidolgozására és piaci bevezetésére
Matematikai modell • Szolgáltató (Cloud Service) –
CS = [ID, VML]
• Virtuális gép (Virtual Machine) –
VM = [ID, P, M, H]
• Kritikus válaszidejű feladat (Task with Critical Response Time) –
CrT = [ID, FR, MR, HR, DL, Pri, IT]
Környezet • Maple • CAS (Computer algerba System) • Erős statisztika csomag (Statistics) • Interpretált nyelv
30
TÁMOP-4.2.2.C-11/1/KONV-2012-0004
EREDMÉNYEK
•
Nemzeti kutatóközpont fejlett infokommunikációs technológiák kidolgozására és piaci bevezetésére
Kihívás: az szimulációs adatok paraméterei – Lee: taszkok nomális és exponenciális eloszlással – Kumar.: érkezési idő Poisson eloszlás, 500 taszk, 0,5<λ<500 – Joshiyara: 700VM-800Taszk, 4000 VM-4000 Taszk, 5000 VM – 6000 Taszk Egyenletes eloszlású CPU-kal Algoritmusok • EDF (Earlieast Deadline First) módszerek – hEDF (heterogén EDF) algoritmus • hEDF off-line • hEDF on-line • Dynamic Voltage Frequency Scaling (DVFS)
hEDF online
31
TÁMOP-4.2.2.C-11/1/KONV-2012-0004
III.8. TÉMA
Nemzeti kutatóközpont fejlett infokommunikációs technológiák kidolgozására és piaci bevezetésére
1. Szenzorhálózatra épülő elosztott felügyeleti rendszer kidolgozása Témavezető: Simon Gyula, PE 2. Smart grid rendszerek kutatása Témavezető: Kovács Lóránt, GAMF 3. Párhuzamos lineáris programozási feladatmegoldó kidolgozása Témavezető: Maros István, PE 4. Feladatfüggő felépítésű pipeline többprocesszoros rendszerek tervezési módszerének kidolgozása és alkalmazása nagy sebességigényű beágyazott célrendszerekben Témavezető: Arató Péter, BME; Brassai Sándor Tihamér, Sapientia 5. Kiloprocesszoros rendszerek logisztikai alkalmazása Témavezető: Szolgay Péter, PPKE 6. Map reduce elvű elosztott feldolgozási algoritmusok és tesztkörnyezet kidolgozása adatbányászati feladatok végrehajtásához Témavezető: Pálvölgyi János, Kürt Zrt. 7. Módszer és tesztkörnyezet kidolgozása kritikus válaszidejű felhő szolgáltatások kialakításához és erőforrás elosztásához Témavezető: Maróti György, PE 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úrára Témavezető: Maróti György, PE 32
TÁMOP-4.2.2.C-11/1/KONV-2012-0004
CÉLOK
Nemzeti kutatóközpont fejlett infokommunikációs technológiák kidolgozására és piaci bevezetésére
Kutatási cél • Heterogén párhuzamosított algoritmusok fejlesztése, ahol az egyes szálakon különböző típusú megoldók futnak • Tesztkörnyezet kialakítása • Módszerek összehasonlítása Tesztkörnyezet • BOINC rendszer – Berkeley-n fejlesztett nyílt forráskódú rendszer – Mester/szolga rendszer: • Kommunikációs modell – A kliensek jelentkeznek feladatért ha van szabad erőforrásuk és visszaadják azt, ha végeztek a megoldással. – A mester nem tud kommunikációt kezdeményezni. 33
TÁMOP-4.2.2.C-11/1/KONV-2012-0004
EREDMÉNYEK Populáció alapú elosztott eljárások • Szerver – Optimalizálási probléma előfeldolgozása, részproblémákra osztása – Részfeladatok szétosztása a kliensek felé – Megoldás előállítása a kliensektől visszakapott részmegoldások alapján • Kliens – Részfeladatot kér a szervertől – Optimalizálási módszer futtatása – Megoldás visszaküldése a szerver felé – Implementált megoldó módszerek: • Genetikus algoritmus • Differential evolution • Particle Swarm Optimization • Szimulált hűtés – Az alkalmazandó módszerről a szerver dönt
Nemzeti kutatóközpont fejlett infokommunikációs technológiák kidolgozására és piaci bevezetésére
Korlátozás és szétválasztás • Egy fában reprezentált megoldástér bejárása helyett azon részfák bejárását kihagyjuk, amik garantáltan nem tartalmaznak optimális megoldást • Egy részfára korlátot ad a benne szereplő legjobb megoldásra, és ha van a korlátnál jobb ismert megoldásunk, akkor a részfát kizárhatjuk • Az algoritmus jól párhuzamosítható, hiszen az egyes részfák párhuzamosan járhatóak be
34
TÁMOP-4.2.2.C-11/1/KONV-2012-0004
EREDMÉNYEK
Nemzeti kutatóközpont fejlett infokommunikációs technológiák kidolgozására és piaci bevezetésére
Tabu keresés • Szomszédsági keresés, amelyben az aktuálisan vizsgált pontból mindig valamely szomszédjába (lehetőleg jobb célfüggvény értékkel rendelkezőbe) megyünk át. • Amennyiben lokális optimumokból kimozdulunk, akkor azokat tabu listára teszi, hogy ne lépjünk oda vissza. • Jól párhuzamosítható: különböző kezdőpontokból párhuzamos keresések
Hibrid módszer • Egyszerre futtat tabu és korlátozás és szétválasztás megoldókat • A tabu kereső szálak által kapott megoldások segítik a korlátozás és szétválasztáson alapuló algoritmust, hiszen egy jobb ismert megoldás több (vagy nagyobb) részfa kizárását teszi lehetővé
Tesztelés • Hátizsák feladat 1000,5000,10000 tárggyal • Tiszta korlátozás és szétválasztás • Tiszta tabu • Hibrid / sűrű korlátozás és szétválasztás • Hibrid / sűrű tabu
Hibrid sűrű tabu
35
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!