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

Automaticky paralelizující nástroj postavený na Petriho sítích

SP2011/25

Böhm Ada Ing., Ph.D.

prof. RNDr. Petr Jančar, CSc.

01. 01. 2011 - 31. 12. 2011

Řešitelé navrhovaného projektu se podílejí na vývoji nástroje určeného pro generování paralelních aplikací. Nástroj umožňuje modelování a implementaci paralelních algoritmů na abstraktní úrovni. Pomocí specifické varianty barevné Petriho sítě je modelován datový tok, komunikace a paralelnost algoritmu. Výsledný model je pak možné simulovat s vizuální odezvou. Hlavní rozdíl vůči existujícím nástrojům je možnost z modelu vygenerovat samostatný program, využívájící standardní paralelizační knihovny (například MPI). V současné době je nástroj ve stadiu funkčního prototypu, který byl vytvořen hlavním řešitelem projektu (S. Böhm). Prototyp je dostupný ze školní sítě na adrese: http://verif.cs.vsb.cz/kaira/. Vytvoření prototypu bylo mj. motivováno podaným projektem GAČR P202/11/0340, jehož hlavní řešitel (prof. P. Jančar) je školitel předkládáného SGS projektu. V projektu GAČR se předpokládá spolupráce s katedrou aplikované matematiky, kde jsou vyvíjeny nástroje v C++. Proto také prototyp generuje C++ kód a je možné do modelu paralelního algoritmu integrovat libovolné C++ knihovny. Pro řešení praktických problémů je C++ v kombinaci s MPI vhodnou volbou. Avšak pro jiné oblasti, například při vývoji nových paralelních algoritmů, mohou existovat výhodnější prostředí. Hlavním cílem překládáného projektu je umožnit rozšiřovat nástroj o další programovací jazyky a cílové platformy. Nejde nám jen o konkrétní platformu, ale o celou koncepci jak přidat další cílové prostředí. Uživatel by tak získal možnost upravit nástroj podle svých potřeb. Přidání dalších cílových platforem na úrovni programovacích jazyků nebo přistupu k paralelizaci může také otevřít nové pohledy na modelování paralelních algoritmů pomocí Petriho sítí. Aktuálně se nám atraktivně jeví možnost použít jako cílovou platformu Glasgow Distributed Haskell. Zde se mj. předpokládá zapojení studenta magisterského studia. Tato platforma je vhodná jako demostrance jak rozšířit náš nástroj o prostředí se značně rozdílnou filozofií (vůči C++ a MPI). Alternativou mohou být řešení postavené na moderních dynamicky typovaných jazycích (například Python). Vyjádření ke kritériím pro hodnocení: - Počtu bodů řešitelského týmu v RIV 2010 (za roky 2005-2009) - Počet bodů získán z neoficiálních výsledků RIV 2010, prosinec 2010 (10 záznamů). prof. Petr Jančar: 189.232. Body získány mj. následujícími publikacemi v impaktovaných časopisech: Zdeněk Sawa and Petr Jančar. 2009. Hardness of equivalence checking for composed finite-state systems. Acta Inf. 46, 3 (April 2009), 169-191. DOI=10.1007/s00236-008-0088-x http://dx.doi.org/10.1007/s00236-008-0088-x Petr Jančar. 2008. Bouziane's transformation of the Petri net reachability problem and incorrectness of the related algorithm. Inf. Comput. 206, 11 (November 2008), 1259-1263. DOI=10.1016/j.ic.2008.06.003 http://dx.doi.org/10.1016/j.ic.2008.06.003 Javier Esparza, Petr Jančar, and Alexander Miller. 2008. On the Complexity of Consistency and Complete State Coding for Signal Transition Graphs. Fundam. Inf. 86, 3 (August 2008), 227-253. Jančar, P., Srba Jiří: Undecidability of bisimilarity by Defender's forcing. In Journal of the ACM. 2008. 55: 1. p. 5:1-5:26 Jančar, P., Kučera Antonín: Equivalence-checking on infinite-state systems: Techniques and results. In journal Theory and Practice of Logic Programming. 2006. 6: 3. 227-264 - Podílu pracovníků s podstatným výkonem v RIV 2010 na řešení projektu. * prof. Petr Jančar se nepodílí na návrhu jiného SGS projektu. - Poměru cena/výkon projektu, kde cena je tvořena náklady projektu, výkon je součet bodů klíčových osob řešitelského týmu v RIV 2010 - * 148800 / 189.232 = 786.3 - Významné publikace členů řešitelského v roce 2010: * Impaktované časopisy: - Jancar, Petr, Martin Kot and Zdenek Sawa. Complexity of deciding bisimilarity between normed BPA and normed BPP. INFORMATION AND COMPUTATION, 208(10, Sp. Iss. SI):1193-1205, 2010. - Froeschle S., Jancar P., Lasota S., Sawa Z.: Noninterleaving bisimulation equivalences on basic parallel processes; in journal Information and Computation Volume 208, Issue 1, January 2010, Pages 42-62 * Konference: - Böhm, S., Stefan Göller, Jančar, P.: Bisimilarity of One-Counter Processes Is PSPACE-Complete. In CONCUR 2010 Concurrency Theory, 21th International Conference, 2010, 177-191, 978-3-642-15374-7 - Behalek, Marek and Petr Saloun. Usage of Embedded Process Functional Language as a Modeling Tool for Embedded Systems Development. UKSIM-AMSS FIRST INTERNATIONAL CONFERENCE ON INTELLIGENT SYSTEMS, MODELLING AND SIMULATION, pages 116-121. - Porubaen, Jaroslav, Michal Forgac, Miroslav Sabo and Marek Behalek. Annotation Based Parser Generator. COMPUTER SCIENCE AND INFORMATION SYSTEMS, 7(2, Sp. Iss. SI):291-307, 2010. - Nikdo z řešitelského týmu se nepodílí na řešení jiného SGS projektu.

Ing. Marek Běhálek, Ph.D.
Ing. Martin Šurkovský, Ph.D.
Ing. Ondřej Garncarz
Ing. Ondřej Meca, Ph.D.
Ing. Ada Böhm, Ph.D.
prof. RNDr. Petr Jančar, CSc.

Hlavní cíle podávaného projektu lze zhrnout v těchto bodech.
- Nálezt zajímavá paradigmata programování a paralelizace, která mohou obohatit vyvíjený nástroj.
- Upravit struktrutu nástroje a začlenit další cílové platformy.
- Na základě získaných zkušeností upravit používaný přístup k modelování paralelních algoritmů.
- Při řešení bychom také chtěli prozkoumat související teoretické problémy. Jedná se především o oblast Petriho sítí a behaviorálních ekvivalencí. Konstrukce využity v nástroji mají formální základy a proto lze přinést i teoretické výsledky.

Výstupy projektu:
- Vyvíjený nástroj rozšířený o možnosti zmíněné v předmětu výzkumu. Dále chceme připravit sadu ukázkových úloh a dokumentaci jak s nástrojem zacházet a jak jej rozšiřovat. Výsledný program chceme zveřejnit jako volně dostupný projekt pod licencí GPL.
- V průběhu řešení projektu předpokládáme publikace týkající se nástroje, zejména se chceme soustředit na konference (indexované WoS). Vzhledem k řešené problematice se chceme zaměřit především na vědecké konference zabývající se tématikou paralelizací, Petriho sítí a funkcionalního programovaní. Chceme také připravit časopisecký článek s teoretickými výsledky.