Studentská grantová soutěž - předchozí roky

Zpracování a analýza rozsáhlých dat s využitím GPU

SP2012/58

Platoš Jan prof. Ing., Ph.D.

01. 01. 2012 - 31. 12. 2012

V dnešní době existuje velké množství systémů, které uchovávají velké objemy dat. Ať už se jedná o databáze autorů a jejich článků, databáze telefonních hovorů, informace o produkci menších i větších průmyslových celků a jiné, velmi často dochází jen k jejich uchování, bez dalšího využití. Přitom v těchto datech se dají nacházet různé souvislosti, vzory, případně lze tato data použít pro předpovídání budoucích dějů. Pro datovou analýzu existuje mnoho metod, avšak většina z nich je schopna v přijatelném čase pracovat jen s malými objemy dat, a proto je nelze použít pro velmi rozsáhlá data. Jednou z možností, jak rozsáhlá data zpracovat, je využití více-jádrových počítačů anebo masivně paralelních procesorů grafických karet (GPU). GPU poskytuje řádově stovky jader a i na běžném počítači dovoluje provádět velmi složité výpočty. Využití GPU pro analýzu dat a jiná zpracování časově velmi náročných úkolů je dnes nastupujícím trendem, neboť umožňuje provádět dříve nepředstavitelné úlohy na běžných počítačích a v dostupném čase. S tím souvisí i trend zapojování těchto procesorů do největších superpočítačů světa. Předmětem výzkumu bude návrh a implementace metod redukce dimenze, shlukové analýzy, hledání vzorů, analýzy obrazu a dalších na GPU a jejich využití při analýze dat z oblastí: predikce hodnot na základě historických dat v průmyslových celcích, analýza sociálních sítí a komunit a predikce jejich chování, detekce zájmových oblastí v obrazových datech, podobnost obrázků a dokumentů, zpracování signálů mozku a jejich využití v rozhraní člověk-stroj, a dalších. Detailní popis projektu: Metody analýzy dat jsou čím dál častěji aplikovány v nejrůznějších oblastech lidského konání. Většina metod, které se běžně aplikuji, má několik nevýhod. Nemožnost zpracovávat velké množství dat v reálném nebo velice krátkém čase je nejvýznamnější z nich. Pojem reálný čas je velmi nekonkrétní a závisí na řešené problematice a s tím souvisejícím objemu dat. Při analýze obrazu jde většinou o zpracování v řádu milisekund, naopak při hledání pravidel a vzorů v datech jde o minuty až hodiny. Ve všech případech lze vylepšit efektivitu algoritmů pomocí využití grafických procesorů. Některé algoritmy analýzy dat mohou být přirozeně a snadno urychleny masivním paralelismem pomocí GPU, jiné potřebují důkladnější přepracování, avšak ve většině případů lze pomocí GPU dosáhnout významného zrychlení. Proto lze hlavní cíle výzkumu shrnout do následujících: - Návrh a efektivní implementace metod pro analýzy rozsáhlých dat s ohledem na využití GPU. - Testování, ladění parametrů a porovnání implementovaných metod při experimentech nad reálnými daty (rozsáhlých datových kolekcích, které jsou výsledkem předchozího publikovaného výzkumu na našem pracovišti nebo které budou získány jako výsledek výzkumných aktivit v rámci navrhovaného projektu). - Publikační činnost jako výsledek shrnující metodiky a výsledky experimentů. Metody analýzy dat, které budou předmětem výzkumu a vývoje budou náležet do následujících oblastí: - metody redukce dimenze - Singular Value Dekomposition, Non-negative matrix factorization, Non-negative Tensor decomposition, Principal Component analysis aj. - shlukovací metody – Self Organizing Maps, Topology preserving SOM, K-means, Mean-shift, aj. - další metody z oblastí hledání vzorů, metody podobnosti, grafové algoritmy a také soft-computing algoritmů, které mohou zjednodušit řešení komplexních problémů. Výše jmenované metody budou aplikovány v různých oblastech. V následujícím textu budou popsány ty nejvýznamnější. Analýza sociálních sítí Jedná se o oblast s velkým výzkumným potenciálem. Současné technologie umožňují ukládání velkého množství informací spojeného s přímou nebo nepřímou interakcí mezi lidmi. Mezi velmi intenzivně zkoumané problémy v této oblasti patří zejména dynamika související s vývojem sítě v čase. Jde např. o analýzu šíření informací v síti, detekci komunit a jejich vývoje, identifikace chování a rolí v síti, sledování vývoje obsahu spojeného s interakcemi v síti. Dobrým příkladem aktuálně zkoumané sociální sítě může být například veřejná databáze DBLP, která poskytuje byť neúplné, nicméně vysoce relevantní informace o publikačních aktivitách v oblasti Computer Science. Na našem pracovišti jsou již dva roky zkoumány vlastnosti autorů vyplývající z publikačních aktivit, a to včetně dynamiky a obsahu. Ve spolupráci zaměstnanců a studentů doktorských studií byl vytvořen koncept on-line systému „forcoa.net“, který je neustále vyvíjen a který poskytuje prakticky aplikované výsledky výzkumných aktivit založených na datech z databáze DBLP (síť milionu autorů). Tento systém byl v rámci konferencí prezentován a je využíván na univerzitách ve světě. Jedním z nedostatků tohoto systému je, že poskytuje pouze informace z nejbližšího okolí jednotlivých autorů. To je způsobeno zejména tím, že rozsah sítě nedovoluje jednoduše aplikovat běžné výpočetní metody tak, aby poskytovaly výsledky v rozumném čase. Právě tento projekt poskytne prostředí pro implementaci výpočetních úloh, které mohou být i díky systému „forcoa.net“ prezentovány výzkumné komunitě. Analýza a podobnost obrázků S analýzou obrázků je spojeno mnoho výzkumných výzev z různých aplikačních oblastí. Mezi ně patří například geoinformatika, medicína apod. Mezi tyto výzvy patří mimo jiné detekce rysů a objektů v obrázcích, analýza sémantiky obrázků, měření podobnosti obrázků. Právě v těchto oblastech je prováděn výzkum i na našem pracovišti, který je zaměřen jednak na detekci rysů a jednak na využití těchto rysů jako tzv. deskriptorů. Ty umožňují efektivní popis obrázků využitelný např. pro automatizovanou podporu hledání různých klasifikací a měření podobnosti. U obrázků se vždy jedná o specializované a často velmi rozsáhlé datové kolekce. Jedním z příkladů mohou být letecké snímky. Jejich analýza byla a je předmětem našeho výzkumu a právě časová náročnost výpočetních operací (jak při detekci rysů, tak při hlubší analýze jako je např. shlukování) vyžaduje optimalizaci metod s využitím paralelismů. Předmětem projektu bude návrh a aplikace výpočetních metod s využitím CPU s podporou GPU především do oblasti analýzy leteckých snímků, ale také do oblasti klasifikace rozsáhlých kolekcí obrázků. Analýza EEG signálů Studium EEG signálů, které probíhá již řadu let, nabývá v dnešní době na novém významu, a to především z pohledu využití analyzovaných dat v interdisciplinárních oblastech. Může se jednat například o bezdotykové ovládání mechanických zařízení (vozidlo, invalidní vozík, umělé končetiny, apod.). Důvodem takovéhoto rozšiřování je i fakt, že k samotnému vyhodnocování signálů v reálném času dnes postačí běžně dostupná hardwarová vybavení. V našem případě budeme hovořit o využití GPU. Jedním z cílů projektu je tedy vytvořit dostatečnou softwarovou základnu pro experimenty s EEG signály na grafických procesorech. V současné době rovněž disponujeme EEG senzory (headsety), které budou u případných experimentů využity. Segmentace obrazu Segmentace obrazu je jednou z metod digitálního zpracování obrazu a je využívána pro hledání zájmových oblastí v obrazech. Metoda je využívána v analýze lékařských snímků, kamerových záznamů, satelitních snímků a dalších. V rámci projektu budou řešeny pokročilé segmentační techniky založené na využití jádrových odhadů, řešení rovnice difúze a na difúzním spektrálním shlukování. Analýza a předvídaní v systémech se senzory Tato oblast je velmi široká, neboť zahrnuje praktický všechny provozy, které využívají měření senzorů. Patří mezi ně výrobní linky, na který je možné předvídat kvalitu produktu již v průběhu výroby. U solárních a větrných elektráren je možné předvídat jejich výkon na základě předpovědi počasí, řízení elektrických motorů na základě vstupních parametru apod. Ve všech podobných systémech je velké množství údajů, které může být využito pro predikci hodnot, hledání podobných stavů, vyvozování pravidel apod. Tabulka publikační činnost řešitelského týmu: Jméno Počet bodů (Jimp,P,F,D, Jneimp,BC) Eduard Sojka 58,272 Jan Gaura 50,367 Pavel Krömer 306,198 Michal Radecký 48,169 Petr Gajdoš 48,025 Tomáš Fabián 31,620 Miloš Kudělka 83,032 Václav Snášel 877,520 Jan Platoš 290,479 Ajith Abraham 672,769 Donald Davendra 72,802 Michal Krumnikl 67,758 Celkem (s duplicitami) 2607,011 Celkem (odhad bez duplicit) 1577,267 Minimálně 6 studentů doktorského studia v kombinované formě: Martin Radvanský, Šárka Zehnalová, Zdeněk Horák, Tomáš Novosád, Pavel Bobrov, Pavel Polyakov Minimálně 11 studentů doktorského studia v prezenční formě: Jan Navrátil, Jonáš Krutil, Karel Mozdřeň, Lukáš Zaorálek, Michael Holuša, Michal Prílepok, Milan Šurkala, Ondřej Koběrský, Pavel Dohnálek, Petr Berek, Radovan Fusek a další. Minimálně 2 studenti magisterské formy studia: Jan Janoušek, Petr Tomala a další. Historie řešitelského týmu: Akademičtí pracovníci podílející se na řešení projektu se již řadu let věnují výzkumu v oblastech, které jsou i předmětem tohoto projektu. Jedná se zejména o analýzu a dolování dat, zpracování obrazu, metody optimalizace, predikce dat apod. Mohou tedy kvalifikovaně vést studenty doktorského i magisterského studia a pomohou jim při řešení popsaných problémů a převodu získaných výsledků do publikací. V seznamu publikací na konci popisu jsou vypsány některé související publikace. Finanční náklady na řešení: Náklady na řešení jsou navrženy tak, aby prostředky byly vynaloženy především na studenty formou stipendií a realizaci cest na zahraniční i lokální konference. Pro cestovné předpokládáme náklady cca 30 tis. Kč na jednu zahraniční konferenci. Dále jsou alokovány peníze na nákup nových grafických akcelerátorů, případně notebooků nebo úložiště dat pro možnost provádění experimentů. Literatura [1] A. Frolov, D. Husek, and P. Polyakov. Estimation of Boolean Factor Ana-lysis Performance by Informational Gain. In ADVANCES IN INTEL-LIGENT WEB MASTERING-2, PROCEEDINGS, volume 67 of Advances in Intelligent and Soft Computing, pages 83–94, SPRINGER-VERLAG BERLIN. 6th Atlantic Web Intelligence Conference, Charles Univ, Fac Math & Phys, Prague, CZECH REPUBLIC, SEP, 2009. [2] Z. Horak, M. Kudelka, and V. Snasel. Fca as a tool for inaccuracy detection in content-based image analysis. In Granular Computing (GrC), 2010 IEEE International Conference on, pages 223–228. IEEE, 2010. [3] Z. Horak, M. Kudelka, and V. Snasel. Feature clustering for orthopho-tomap analysis. In Systems, Man, and Cybernetics (SMC), 2011 IEEE International Conference on, pages 307–312. IEEE, 2011. [4] Z. Horak, M. Kudelka, V. Snasel, A. Abraham, V. FEI, and H. Rezankova. Forcoa .net: An interactive tool for exploring the significance of authorship networks in dblp data. [5] P. Kroemer, J. Platos, and V. Snasel. Fast Dimension Reduction Based on NMF. In Cai, ZH and Hu, CY and Kang, Z and Liu, Y, editor, ADVAN-CES IN COMPUTATION AND INTELLIGENCE, volume 6382 of Lecture Notes in Computer Science, pages 424–433. China Univ Geosciences, 2010. 5th International Symposium on Intelligence Computation and Applications, Wuhan, PEOPLES R CHINA, OCT 22-24, 2010. [6] P. Kroemer, V. Snasel, and J. Platos. Learning Patterns from Data by an Evolutionary-Fuzzy Approach. In SOFT COMPUTING MODELS IN INDUSTRIAL AND ENVIRONMENTAL APPLICATIONS, 6TH INTERNATIONAL CONFERENCE SOCO 2011, volume 87 of Advances in Intelligent and Soft Computing, pages 127–135. 6th International Conference on Soft Com-puting Models in Industrial and Environmental Applications, Salamanca, SPAIN, APR, 2011. [7] P. Kroemer, V. Snasel, J. Platos, and A. Abraham. Evolving Fuzzy Clas-sifier for Data Mining - an Information Retrieval Approach. In COMPUTATIO-NAL INTELLIGENCE IN SECURITY FOR INFORMATION SYSTEMS 2010, volume 85 of Advances in Intelligent and Soft Computing, pages 25– 32, 3rd International Conference on Com-putational Intelligence in Security for Information Systems, Leon, SPAIN, NOV 11-12, 2010. [8] M. Kudelka, Z. Horak, V. Snasel, and A. Abraham. Social network re-duction based on stability. In Computational Aspects of Social Networks (CASoN), 2010 International Conference on, pages 509–514. IEEE, 2010. [9] M. Kudelka, Z. Horak, V. Snasel, and A. Abraham. Weighted co-authorship network based on forgetting. Future Information Technology, pages 72–79, 2011. [10] M. Kudělka, Z. Horák, V. Snášel, P. Krömer, J. Platoš, and A. Abraham. Social and swarm aspects of co-authorship network. Logic Journal of IGPL, 2011. [11] J. Platos, P. Gajdos, P. Kroemer, and V. Snasel. Non-negative Matrix Factorization on GPU. In NETWORKED DIGITAL TECHNOLOGIES, PT 1, volume 87 of Communications in Computer and Information Science, pages 21–30. Springer, 2010. 2nd International Conference on Networked Digital Technologies, Charles Univ, Prague, CZECH REPUBLIC, JUL 07-09, 2010. [12] J. Schreiber, E. Sojka, L. Licev, P. Sknourilova, J. Gaura, and D. Skoloudik. A new method for the detection of brain stem in transcranial ultrasound images. In BIOSIGNALS 2008: PRO-CEEDINGS OF THE FIRST INTERNATIONAL CONFERENCE ON BIO-INSPIRED SYSTEMS AND SIGNAL PROCESSING, VOL II, pages 478–483, 2008. 1st International Conference on Bio-Inspired Systems and Signal Processing, Funchal, PORTUGAL, JAN 28-31, 2008. [13] V. Snášel, Z. Horák, and M. Kudelka. Social network analysis in community-built databases. Community-Built Databases, page 51, 2011. [14] V. Snasel, Z. Horak, M. Kudelka, and A. Abraham. Fuzzy signatures orga-nized using s-tree. In Systems, Man, and Cybernetics (SMC), 2011 IEEE International Conference on, pages 633 –637, oct. 2011. [15] V. Snasel, P. Kroemer, J. Platos, and A. Abraham. The Evolution of Fuzzy Classifier for Data Mining with Applications. In SIMULATED EVOLUTION AND LEARNING, volume 6457 of Lecture Notes in Computer Science, pages 349–358. 2010. 8th International Conference of Simulated Evolution and Learning, Indian Inst Technol Kanpur, Kanpur, INDIA, DEC 01-04, 2010. [16] V. Snasel, P. Kroemer, J. Platos, M. Kudelka, Z. Horak, and K. Wegrzyn-Wolska. Two New Methods for Network Analysis: Ant Colony Optimization and Reduction by Forgetting. In ADVANCES IN INTELLIGENT WEB MASTERING 3, volume 86 of Advances in Intelligent and Soft Computing, pages 225–234, 2011. 7th Atlantic Web Intelligence Conference, Univ Appl Sci Fribourg, Fribourg, SWITZERLAND, JAN 26-28, 2011. [17] V. Snášel, P. Krömer, J. Platoš, M. Kudelka, Z. Horák, and K. Wegrzyn-Wolska. Two new methods for network analysis: Ant colony optimization and reduction by forgetting. [18] E. Sojka, J. Gaura, T. Fabian, and M. Krumnikl. Active Contours without Edges and without Reinitialisation. In Abraham, A and Herrera, F and Carvalho, A and Pai, V, editor, 2009 WORLD CONGRESS ON NATURE & BIOLOGICALLY INSPIRED COMPUTING (NABIC 2009), pages 913– 916, 2009. World Congress on Nature and Biologically Inspired Computing, Coimbatore, INDIA, DEC 09-12, 2009. [19] E. Sojka, J. Gaura, T. Fabian, and M. Krumnikl. Fast Mean Shift Algori-thm Based on Discretisation and Interpolation. In ADVANCED CONCEPTS FOR INTELLIGENT VISION SYSTEMS, PT I, volume 6474 of Lecture Notes in Computer Science, pages 402–413. CSIRO; 12th International Conference on Advanced Concepts for In-telligent Vision Systems, Sydney, AUSTRALIA, DEC 13-16, 2010. [20] E. Sojka, J. Gaura, S. Srubar, T. Fabian, and M. Krumnikl. Blurring Mean-Shift with a Restricted Data-Set Modification for Applications in Image Processing. In ADVANCES IN VISUAL COMPU-TING, PT III, volume 6455 of Lecture Notes in Computer Science, pages 310–319. 6th International Symposium on Visual Computing, Las Vegas, NV, NOV 29-DEC 01, 2010.

Ing. Michal Radecký, Ph.D., MBA
Mgr. Ing. Michal Krumnikl, Ph.D.
prof. Ing. Pavel Krömer, Ph.D.
doc. Ing. Petr Gajdoš, Ph.D.
doc. Dr. Ing. Eduard Sojka
prof. RNDr. Václav Snášel, CSc.
Ing. Tomáš Fabián, Ph.D.
Ing. Jan Gaura, Ph.D.
doc. Mgr. Miloš Kudělka, Ph.D.
doc. MSc. Donald David Davendra, Ph.D.
Ajith Abraham Padath, PhD.
prof. Ing. Jan Platoš, Ph.D.
Mgr. Zdeněk Horák, Ph.D.
Ing. Milan Šurkala
Ing. Karel Mozdřeň
Ing. Radovan Fusek, Ph.D.
Ing. Michal Prílepok, Ph.D.
Dipl.Ing. Pavel Dmitrievitch Bobrov
Mgr. Tomáš Novosád, Ph.D.
RNDr. Ing. Martin Radvanský, Ph.D.
Ing. Pavel Polyakov
Ing. Ondřej Koběrský
Ing. Lukáš Zaorálek
Ing. Petr Berek
Mgr. Šárka Zehnalová
Ing. Jonáš Krutil
Ing. Michael Holuša, Ph.D.
Ing. Pavel Dohnálek, Ph.D.
Ing. Jan Navrátil
Ing. Jan Janoušek
Bc. Petr Tomala

Cílem projektu je výzkum v oblasti efektivních metod pro zpracování rozsáhlých dat za pomocí klasických procesorů a grafických akcelerátorů a vytvořit knihovnu algoritmů a funkcí pro zjednodušení experimentů a analýzy dat. V projektu bude pracovat několik týmů na různých aspektech problematiky, zejména pak na analýze reálných dat a vývoji souvisejících algoritmů, ve kterých najdou studenti doktorského i magisterského studia velké uplatnění, neboť jim to pomůže zapojit se do řešení reálných problémů a pracovat na jasně specifikovaných částech systému. Tím budou přirozeně zapojeni do výzkumu a vývoje, a to i v dlouhodobém horizontu.

Projekt je koncipovaný jako víceletý (s celkovým odhadem dva až tři roky). Cíle prvního roku lze formulovat takto:
- Zmapování základních metod pro zpracování dat dle zmíněných oblastí.
- Implementace těchto metod, algoritmů a potřebných datových struktur na CPU a na GPU a jejich vzájemné porovnání.
- Provádění experimentů s různými typy dat z různých oblastí reálného výzkumu.
- Publikování výsledků na konferencích ISI a v časopisech s impaktním faktorem.
- Navázání spolupráce se zahraničními pracovišti.