ITAT 2013 Proceedings, CEUR Workshop Proceedings Vol. 1003, pp. 75–81 http://ceur-ws.org/Vol-1003, Series ISSN 1613-0073, c 2013 Z. Falt, M. Kruliš, J. Yaghob Bobolang – jazyk pro systém Bobox Zbyněk Falt, Martin Kruliš, Jakub Yaghob∗ Univerzita Karlova, Praha, Česká republika, {falt,krulis,yaghob}@ksi.mff.cuni.cz Abstrakt: Paralelní zpracování dat je v současné době C# apod.), pro specifikaci exekučního plánu se tyto ja- velmi aktuální téma. Jeden z používaných postupů je pře- zyky příliš nehodí. Exekuční plán totiž odpovídá oriento- vod vstupních dat na datové proudy a zpracování těchto vanému grafu, tj. je zadán seznamem vrcholů a hran. To proudů pomocí operátorů, které mohou být vyhodnoco- sice lze snadno vyjádřit v běžných programovacích jazy- vány paralelně. Protože pro specifikaci vzájemného propo- cích, ale takový kód je obtížně čitelný a modifikovatelný. jení operátorů jsou běžné programovací jazyky nevhodné, Proto vznikají jazyky, které vytváření exekučního plánu vznikla pro tento účel celá řada doménově specifických usnadňují, at’ už speciální syntaxí, nebo grafickou vizuali- jazyků. Jazyk Bobolang je jedním z nich. Kromě běžných zací plánu. vlastností, ale přidává navíc některé syntaktické a séman- Bobolang se zaměřuje na druhou fázi vývoje. Kromě či- tické prvky, které značně usnadňují intra-operátorovou pa- telné syntaxe se ale snaží i o pomoc při intra-operátorové ralelizaci. Díky tomu je možné snadno vytvářet vysoce paralelizaci, kdy provádí některé transformace zvyšující škálovatelné aplikace zpracovávající proudová data. paralelismus exekučního plánu automaticky. Tím se odli- šuje od ostatních podobných jazyků. Zbytek článku je rozdělen následovně: Kapitola 2 před- 1 Úvod stavuje používané jazyky určené pro systémy zpraco- vání proudových dat, kapitola 3 popisuje systém Bobox, Paralelní systémy jsou v dnešní době téměř standardem. pro který vznikla pilotní implementace jazyka Bobolang. Z tohoto důvodu se neustále hledají nové cesty jak co nej- V kapitole 4 rozebíráme možnosti a postupy paralelizace efektivněji využít tyto prostředky. Bohužel, vývoj para- operátorů. Stručný popis jazyku Bobolang je uveden v ka- lelních aplikací je náročný a náchylný k chybám. Proto pitole 5 a několik příkladů jeho použití uvádíme v kapi- vznikají různé knihovny, nástroje, systémy a metody, jak tole 6. Celý článek pak shrnujeme v kapitole 7. tuto činnost maximálně usnadnit a zefektivnit. Některé tyto nástroje se snaží být co nejobecnější, tzn. programá- torovi pomáhají s vytvářením a synchronizací vláken [5], 2 Související práce některé poskytují množství knihovních funkcí pro snazší paralelizaci některých typů algoritmů [19], některé rozši- Současné jazyky zaměřující se na proudové zpracování dat řují samotný jazyk o direktivy určené pro snazší vývoj [7]. se dají rozdělit do několika skupin podle jejich zaměření. Kromě toho existují doménově specifické nástroje, které Brook [3, 4], StreaMIT [20] a StreamC [9] se zaměřují jsou určeny pro konkrétní druhy aplikací. Systémy pro na vývoj vysoce výkonných aplikací pracujících převážně zpracování proudových dat jsou jedním z nich [20, 18, 21, s multimediální daty (kodeky, filtry, transformace apod.). 8, 4, 17, 2]. Tyto jazyky jsou založeny na syntaxi jazyka C/C++ a po- Tyto systémy pracují s tzv. datovými proudy, tj. v pod- krývají jak fázi implementace jednotlivých operátorů, tak statě s posloupnostmi n-tic. Tyto proudy jsou průběžně jejich vzájemné propojení ve výsledné aplikaci. Překla- (tj. tak jak n-tice přichází) zpracovávány operátory, které dače těchto jazyků provádějí některé optimalizace, které transformují vstupní proudy na výstupní. Vývoj aplikací zvyšují výkon nebo nebo mapují operátory na určité vý- pro takové systémy se skládá ze dvou fází: početní jednotky systému (CPU, GPU, FPGA1 ). Lucid [1] je další jazyk určený pro programování prou- 1. Implementace potřebné množiny operátorů, tj. jak dových aplikací. Tento jazyk sám o sobě není určen přetransformovat vstupní proud/proudy na výstupní pro paralelní aplikace, proto vznikl jazyk Granular Lucid proud/proudy. (GLU) [16], který umožňuje do plánu zařadit operátory 2. Vytvoření exekučního plánu, tj. pospojování ope- implementované v jazyku C, které mohou být pouštěny rátorů orientovanými hranami, které určují datové paralelně. proudy mezi nimi. Jazyk X-Language [14] je moderní jazyk vyvinutý pro systém Auto-Pipe [6]. Tento jazyk slouží pro vzájemné Zatímco implementaci operátorů lze provést v téměř li- propojení již připravených operátorů. Svým charakterem bovolném běžném programovacím jazyku (C/C++, Java, je tedy podobný jazyku GLU, ale propojení operátorů ∗ Článek byl podporován Grantovou agenturou Univerzity Karlovy, projekt č. 277911, Grantovou agenturou ČR GACR P103/13/08195S a grantem SVV-2013-267312. 1 Field-programmable gate array 76 Z. Falt, M. Kruliš, J. Yaghob vyjádřeno explicitněji (syntaxe je podobná jazyku Bobo- • Programátor operátorů nemusí řešit synchronizaci lang). Podporuje rovněž vytváření operátorů z již existu- vláken, takže vývoj operátorů je značně usnadněn. jících operátorů. Na rozdíl od Bobolangu ale nedochází k automatické modifikaci plánu za účelem zvýšení parale- • Pro zpracování jedné obálky nelze použít více než lismu. jedno vlákno, což zdánlivě omezuje možnosti para- lelizace. 3 Bobox Ale i přes jednovláknovost operátorů, je možné dosáh- nout paralelního vyhodnocování exekučního plánu, nebot’ Systém Bobox je jedna z implementací systému pro zpra- nezávislé operátory mohou být spouštěny paralelně. Roz- cování proudových dat. Bobox poskytuje běhové prostředí lišujeme tři typy paralelismů [15]: pro vyhodnocování exekučních plánů v paralelním pro- středí. Systém podporuje jak acyklické exekuční plány, tak • pipelinový paralelismus – zdroj datového proudu pra- i plány obsahující cykly. Protože jazyk Bobolang je na- cuje paralelně s jeho konzumentem vržen právě pro Bobox a využívá některé jeho vlastnosti, uvádíme v této kapitole některé technické detaily tohoto • taskový paralelismus – nezávislé datové proudy jsou systému. zpracovávány paralelně Datové proudy v Boboxu jsou reprezentované jako proud tzv. datových obálek. Každá obálka obsahuje se- • datový paralelismus – nezávislé části jednoho proudu znam tzv. datový sloupců. Tyto datové sloupce obsahují mohou být zpracovány paralelně samotná data. Každý sloupec musí obsahovat data pouze jednoho typu, ale jedna obálka může obsahovat sloupce Taskový paralelismus je pevně zakódovaný v exekuč- různých typů. Dále platí, že všechny sloupce v jedné ním plánu, takže přináší pouze omezenou škálovatelnost. obálce mají vždy stejnou délku, takže se můžeme na Datový a pipelinový paralelismus lze ale za určitých okol- obálku dívat jako na posloupnost n-tic. Kromě datových ností zvýšit a tím zvýšit škálovatelnost celého systému. obálek existují tzv. otrávené obálky, jejichž úkolem je sig- nalizovat konec datového proudu. V současné době podporuje Bobox pouze shared- 4 Intra-operátorový paralelismus memory systémy, takže operátory si mohou vzájemně posílat pouze ukazatele na obálky. Tato implementace Pipelinový paralelismus můžeme zvýšit (resp. zavést) tím, značně urychluje operátory jako např. broadcast (viz ka- že určitý operátor rozdělíme na posloupnost dílčích operá- pitola 4), nebot’ data nejsou nijak klonována a v paměti se torů, kde každý vykoná nad proudem část práce (viz Ob- nacházejí pouze v jedné instanci. Navíc je celkový počet rázek 1). Bohužel ne všechny operátory lze takto dekom- řádků v obálce je zvolen s ohledem na velikost vyrovnáva- ponovat a u těch, u kterých to lze, to může být nevýhodné cích pamětí v procesoru, tak aby komunikace mezi operá- z důvodu zvýšení režie nutné pro přenos datového proudu. tory probíhala bez nutnosti přístupu do hlavní paměti. Každý exekuční plán, musí obsahovat dva speciální operator operátory: op1 op2 op3 op4 • init – tento operátor je vždy první v topologickém uspořádání exekučního plánu. Jeho úkolem je nastar- Obrázek 1: Rozklad operátoru pro zvýšení pipelinového tovat výpočet tím, že na svůj výstup odešle otrávenou paralelismu. obálku. • term – tento operátor je vždy poslední v topolo- Datový paralelismus můžeme do plánu zavést tak, že gickém uspořádání. Ve chvíli, kdy přijme na svém vstupní proud rozdělíme na několik dílčích proudů, ty vstupu otrávenou obálku, oznámí systému, že exe- zpracujeme paralelně a poté je opět spojíme do výsledného kuční plán byl vyhodnocen. proudu. V následujících dvou podkapitolách rozebereme dva postupy, jak toho dosáhnout. Důležitou součástí systému je plánovač, jehož úko- lem je přidělovat výpočetní čas jednotlivým operátorům. Obecně se plánovač řídí dostupností datových obálek na 4.1 Bezestavové operátory vstupech operátorů, tj. pokud má operátor neprázdnou frontu vstupních obálek, je vložen do fronty operátorů při- Bezestavové operátory si neudržují vnitřní stav. To zna- pravených ke spuštění. Na základě různých kritérií [13] mená, že zpracování jedné n-tice je zcela nezávislé na vybírá plánovač z této fronty operátory a spouští jejich kód ostatních. Typickou ukázkou je např. operátor filter, v některém z připravených vláken. Důležité je, že jeden který z proudu n-tic odstraní ty, které nesplňují určitou operátor může být spuštěn v nejvýše jednom vlákně. Toto podmínku, nebot’ vyhodnocení podmínky pro jednu n-tici omezení má dva důsledky: nezávisí na jiných n-ticích. Bobolang—jazyk pro systém Bobox 77 Protože zpracování jedné n-tice nezávisí na ostatních, V tuto chvíli se operátory střídají ve zpracování vstup- nezávisí ani zpracování celé obálky na ostatních obál- ních dat, takže pro paralelizaci můžeme použít schéma kách. Můžeme tedy použít schéma naznačené na Ob- znázorněné na Obrázku 3. Efektivita paralelizace závisí rázku 2. Operátor rr_dispatch jednoduše přeposílá na složitosti aktualizace stavu. Je zřejmé, že by měla být vstupní obálky na své výstupy metodou round-robin, ope- alespoň N-krát rychlejší než zpracování dat. Problém na- rátor rr_consolidate metodou round-robin odebírá vý- stává, pokud je aktualizace stavu netriviální, nebot’ v tako- sledné obálky z jednotlivých operátorů a vytváří tak vý- vém případě se počítá N-krát totéž. Řešením je dedikovat sledný proud. samostatný operátor pro aktualizaci stavu, který by všem ostatním posílal aktuální stav. stateless[0] operator[0] stateless[1] rr_dispatch rr_consolidate operator[1] stateless[2] broadcast rr_consolidate operator[2] stateless[3] operator[3] Obrázek 2: Paralelizace bezestavového operátoru. Obrázek 3: Paralelizace paralelizovatelného operátoru. Protože rr_dispatch a rr_consolidate pouze ma- nipulují se ukazateli na obálky (viz kapitola 3), pracují oba operátory velmi rychle a celý výpočet zpomalují pouze za- Ukázka paralelizovatelného operátoru Velmi jednodu- nedbatelně. chý příklad operátoru, který lze paralelizovat schématem popsaným v části 4.2 je defragmentace obálek. Některé 4.2 Paralelizovatelné operátory operátory generují obálky mnohem menší než doporučené velikosti. To má za následek snížení výkonu systému, ne- Se stavovými operátory je situace složitější, nebot’ bot’ příliš malé obálky zvyšují celkovou režii potřebnou na abychom zpracovali jednu obálku, musíme znát stav od- plánování operátorů. vozený z obsahu předchozích obálek. U některých ope- Má-li obálka doporučenou velikost L n-tic, je základní rátorů můžeme použít postup naznačený v této podkapi- algoritmus následující: tole. Předpokládejme, že tělo stavového operátoru vypadá while not konec do obecně takto: překopíruj a přeskoč L n-tic do výstupní obálky S ← iniciální stav end while while not konec do Podle výše uvedeného postupu, můžeme kód operátoru zpracuj vstupní data pomocí S a zároveň aktualizuj S upravit do následující podoby: end while fáze ← 0 Občas ale lze toto schéma upravit do následující podoby: while not konec do S ← iniciální stav if fáze mod N = PID then while not konec do překopíruj L n-tic do výstupní obálky zpracuj vstupní data pomocí S end if aktualizuj S přeskoč L n-tic end while fáze ← fáze + 1 Pokud je aktualizace stavu S rychlejší než zpracování end while dat, můžeme vytvořit N paralelních operátorů a očíslovat Protože přeskakování n-tic je velmi rychlá operace (mů- je čísly 0 až N − 1 (toto číslo budeme v dalším textu ozna- žeme přeskakovat celé obálky nebo jejich části), je tato pa- čovat jako PID – Parallel ID). Každý operátor pak bude ralelizace velmi účinná. pracovat následujícím způsobem: S ← inciální stav 5 Bobolang fáze ← 0 while not konec do 5.1 Úvod if fáze mod N = PID then zpracuj část vstupu pomocí S Jazyk Bobolang vznikl pro účely pohodlnějšího zápisu end if exekučních plánů. Tomu odpovídá syntaxe, kdy progra- aktualizuj S mátor vyrobí instance operátorů (podobně jako se vytváří fáze ← fáze + 1 proměnné v jazycích C/C++) a poté je pomocí operátoru end while -> vzájemně pospojuje. 78 Z. Falt, M. Kruliš, J. Yaghob Pomocí jazyka je rovněž možné z množiny hotových main operátorů (naimplementovaných v jazyku C++ nebo v ja- process zyku Bobolang) poskládat samostatný operátor, který lze init source pre post sink term poté použít v exekučním plánu. K tomu slouží následující syntaxe: Obrázek 4: Ukázka plně instanciovaného exekučního o p e r a t o r p r o c e s s ( i n t ) − >( i n t ) plánu. { p r e p r o p c e s s ( i n t ) − >( i n t ) p r e ; p o s t p r o c e s s ( i n t ) − >( i n t ) p o s t ; navíc musí rozeslat otrávenou obálku z operátoru init do operátorů source (viz Obrázek 5). i n p u t −> p r e ; o p e r a t o r main ( ) − > ( ) p r e −> p o s t ; { p o s t −> o u t p u t ; broadcast () − >() ,() bcast ; } s o u r c e () − >( i n t ) s r c 1 , s r c 2 ; merge ( i n t ) , ( i n t ) − >( i n t ) merge ; Řádek operator process(int)->(int) říká, že s i n k ( i n t ) − >() s i n k ; chceme vytvořit operátor se jménem process, který trans- formuje proud celých čísel na proud celých čísel. Ná- i n p u t −> b c a s t ; sleduje tělo operátoru, které se skládá z instancí operá- b c a s t [ 0 ] −> s r c 1 −> [ 0 ] merge ; torů preprocess a postprocess. Kromě explicitně uve- b c a s t [ 1 ] −> s r c 2 −> [ 1 ] merge ; dených instancí operátorů (pre a post), obsahuje každé merge −> s i n k ; tělo implicitně operátory input a output. Ty reprezen- s i n k −> o u t p u t ; tují vstup/výstup celého operátoru. Takže řádek input -> } pre říká, že vstup operátoru process je přeposílán na vstup operátoru pre. Podobně funguje operátor output. Exekuční plán se specifikuje stejnou syntaxí. Jak bylo main uvedeno v kapitole 3, exekuční plán se skládá ze dvou spe- src2 ciálních operátorů init a term a těla exekučního plánu. init bcast merge sink term src1 Na tělo exekučního plánu se tedy můžeme dívat jako na operátor, který má jeden vstup (k němu je připojen ope- rátor init) a jeden výstup (k němu je připojen operátor Obrázek 5: Ukázka práce s operátory, které mají více vstu- term). pů/výstupů. Aby interpretr jazyka poznal, který operátor reprezen- tuje exekuční plán, musí být vždy pojmenován jako main. Pokud bychom chtěli vyrobit aplikaci, která zpracovává 5.2 Násobnost vstupů/výstupů posloupnost celých čísel, napíšeme následující kód: Každý operátor může mít libovolný nenulový počet vstupů o p e r a t o r main ( ) − > ( ) a výstupů. Kromě toho ale může být každý vstup/výstup { tzv. násobný. Implicitně je každý vstup/výstup jednoná- s o u r c e () − >( i n t ) s o u r c e ; sobný, násobnost se musí zapisovat explicitně, tj. např.: p r o c e s s ( i n t ) − >( i n t ) op ; s i n k ( i n t ) − >() s i n k ; b r o a d c a s t ( ) − > ( ) {N} b c a s t ; i n p u t −> s o u r c e ; kde N značí násobnost. N může být bud’ přirozené číslo s o u r c e −> op ; nebo znak *. Číslo N přesně určuje násobnost vstupu/vý- op −> s i n k ; stupu, zatímco * nechává toto rozhodnutí na Bobolangu, s i n k −> o u t p u t ; který dosadí vhodné číslo (v pilotní implementaci shodné } s počtem vláken v systému). Bobolang umožňuje vzájemně propojit výstup libo- Pokud předáme systému Bobox tento kód, interpretr volné násobnosti na vstup libovolné násobnosti, pokud ta- Bobolangu instanciuje operátor main, vytvoří operátory ková operace nevede k logické chybě. init a term a vytvoří exekuční plán, který je znázorněný Pokud je připojen vícenásobný výstup na jednonásobný na Obrázku 4. vstup, dojde k automatické replikaci cílového operátoru Pokud má operátor více vstupů/výstupů, jsou tyto ope- podle násobnosti výstupu a připojení výstupů na jednotlivé rátory číslovány od nuly a číslo vstupu/výstupu musí být vstupy replikovaných operátorů. uvedeno. Pokud má vstup/výstup pouze jeden, nemusí být Spojení jednonásobného výstupu s jednonásobným toto číslo uvedeno. Viz např. použití operátoru merge, kdy vstupem způsobí, že cílový operátor je replikovaný právě Bobolang—jazyk pro systém Bobox 79 tolikrát, kolikrát je replikovaný zdrojový operátor a jed- s o r t ( i n t , i n t ) − >( i n t , i n t ) notlivé výstupy jsou napojeny na jednotlivé vstupy. dosadí se za T typ (int,int), tj. dvojice celých čísel. Aby spojení jednonásobného výstupu na vícenásobný Pokud by vstupní a výstupní typ byl různý, dojde k chybě vstup bylo korektní, musí být zdrojový operátor repliko- při vyhodnocování. vaný. Pokud je tato podmínka splněna, je vytvořena jedna instance cílového operátoru a jednotlivé výstupy jsou při- pojeny na vstup tohoto operátoru. 5.4 Intra-operátorová paralelizace Spojení vícenásobného výstupu a vícenásobného vstupu Zápis intra-operátorové paralelizace je nyní snadný. Po- je rovněž povoleno, pokud je zdrojový operátor repliko- kud máme bezestavový operátor, stačí zapouzdřit jej ná- vaný. V takovém případě je cílový operátor replikovaný sledovně: tolikrát, kolikrát je replikovaný zdrojový operátor. V pří- padě operátoru -> je 1. operátor napojen na 1. podvstup operator p a r a l l e l _ s t a t e l e s s cílových operátorů, 2. operátor na 2. podvstup, atd. ( typename T) − >( typename U) Následující zdrojový kód, který pokrývá všechny uve- { dené možnosti, bude interpretován tak, jak je znázorněno r r _ d i s p a t c h ( T) − >(T ) { ∗ } d i s p ; na Obrázku 6. s t a t e l e s s _ o p e r a t o r ( T) − >(U) op ; r r _ c o n s o l i d a t e (U){∗} − >(U) c o n s ; o p e r a t o r main ( ) − > ( ) { i n p u t −> d i s p −> op ; op ( ) − > ( ) { ∗ } op1 ; op −> c o n s −> o u t p u t ; op ( ) − > ( ) op2 ; } op ( ) − > ( ) { ∗ } op3 ; op ( ) { ∗ } − > ( ) op4 ; Instanciací operátoru dostaneme stejné schéma jako op ( ) { ∗ } − > ( ) op5 ; v podkapitole 4.1 (viz Obrázek 2). Paralelizovatelný operátor má identické schéma, je- i n p u t −> op1 −> op2 −> op3 ; nom místo operátoru rr_dispatch, použijeme operátor op3 −> op4 −> op5 −> o u t p u t ; broadcast. Aby programátor nemusel bezestavové a pa- } ralelizovatelné operátory takto paralelizovat ručně, pro- vádí tuto úpravu Bobolang sám. Stačí označit operátor jako bezestavový (klíčovým slovem stateless) nebo pa- main op2[3] op3[3] op4[3] ralelizovatelný (klíčovým slovem parallel). V ostatních případech se žádná modifikace neprovádí. init op1 op2[2] op3[2] op4[2] op5 term Pokud se jedná o komplexnější paralelizaci operátoru, je op2[1] op3[1] op4[1] nutné zapsat schéma operátoru ručně, nicméně Bobolang op2[0] op3[0] op4[0] tuto činnost značně usnadňuje, viz kapitola 6. Obrázek 6: Ukázka exekučního plánu s násobnými vstu- 6 Příklady aplikací py/výstupy. 6.1 Nested-loops join Nested-loops join je velmi snadný algoritmus pro parale- 5.3 Klíčové slovo typename lizaci. Máme-li naimplementovaný operátor, který vyko- Aby bylo možné vytvářet znovupoužitelné operátory nává nested-loops join nad vstupními daty, můžeme para- (např. operátor třídící celá a desetinná čísla bude mít prav- lelizovat operátor tak, že vytvoříme N instancí toho ope- děpodobně identickou vnitřní strukturu), obsahuje Bobo- rátoru a do jednoho vstupu operátorů přepošleme celý lang klíčové slovo typename. To je inspirované stejným první vstup, zatímco do druhého pouze jednu N-tinu dru- slovem v jazyku C++ a je možné jej použít v deklaraci hého vstupu (N-tiny musí být samozřejmě disjunktní). Vý- operátoru např. v případě třídění takto: sledný proud pak získáme jako sjednocení výsledku repli- kovaných operátorů. o p e r a t o r s o r t ( typename T) − >(T ) V Bobolangu tento algoritmus zapíšeme následujícím { způsobem (dispatch má z úkol rozdělit proud na N částí, s o m e _ o p e r a t o r ( T) − >(T ) op ; union spojit N proudů do jednoho) ... operator p a r a l l e l _ j o i n } ( typename L ) , ( typename R ) V těle operátoru pak můžeme používat typ T, jako jaký- −> ( typename T ) koliv jiný běžný typ. Pokud instanciujeme tento operátor { např. následujícím způsobem: b r o a d c a s t ( L) − >(L ) { ∗ } b c a s t ; 80 Z. Falt, M. Kruliš, J. Yaghob r r _ d i s p a t c h ( R) − >(R) { ∗ } d i s p ; 6.3 Merge join n e s t e d _ l o o p s _ j o i n ( L ) , ( R) − >(T ) j o i n ; u n i o n ( T){∗} − >(T ) u n i o n ; Základní myšlenkou paralelního merge joinu pro systém Bobox je modifikovat a vzájemně párovat vstupní obálky i n p u t [ 0 ] −> b c a s t −> [ 0 ] j o i n ; tak, aby bylo možné spojovat tyto páry paralelně. To vede i n p u t [ 1 ] −> d i s p −> [ 1 ] j o i n ; k následujícímu schématu: j o i n −> u n i o n −> o u t p u t ; operator p a r a l l e l _ j o i n } ( typename L ) , ( typename R ) −> ( typename T ) Instanciovaný operátor je zobrazen na Obrázku 7. Více { detailů včetně experimentů lze nalézt v článku [10]. p r e p r o c e s s ( L ) , ( R) − >(L ) , ( R ) p r e p ; p a r a l l e l j o i n ( L ) , ( R) − >(T ) j o i n ; parallel_join join[3] i n p u t [ 0 ] −> [ 0 ] p r e p [ 0 ] −> [ 0 ] j o i n ; i n p u t [ 1 ] −> [ 1 ] p r e p [ 1 ] −> [ 1 ] j o i n ; disp join[2] j o i n −> o u t p u t ; union bcast join[1] } Instanciovaný operátor je znázorněn na Obrázku 9. join[0] Bližší podrobnosti včetně detailní implementace operátoru preprocess a join lze nalézt v článku [12]. Obrázek 7: Paralelizovaný nested-loops join. parallel_join join[3] broadcast join[2] 6.2 Třídění prep rr_consolidate broadcast join[1] Problémem třídění v systémech proudového zpracování join[0] dat jsme se zabývali v předchozí práci [11]. Základní ideou algoritmu je rozdělit vstupní proud na několik podproudů, ty setřídit paralelně a tyto setříděné podproudy paralelně Obrázek 9: Paralelizovaný merge join. slít. Tato myšlenka vede k následujícímu kódu: o p e r a t o r p a r a l l e l _ s o r t ( typename T) − >(T ) { 7 Závěr a budoucí práce r r _ d i s p a t c h ( T) − >(T ) { ∗ } d i s p ; s o r t ( T) − >(T ) s o r t ; V tomto článku jsme představili jazyk Bobolang, který je p a r a l l e l merge ( T){∗} − >(T ) merge ; určený pro použití v systémech pro zpracování proudo- i n p u t −> d i s p −> s o r t ; vých dat. Kromě specifikace exekučních plánů má vlast- s o r t −> merge −> o u t p u t ; nosti, které umožňují snadno popsat vnitřní strukturu para- } lelizovaných operátorů. Interpret jazyka na základě těchto popisů instanciuje exekuční plán tak, aby při jeho vyhod- Protože je merge označen jako parallel, vloží nocování v paralelním prostředí k maximálnímu využití se před tento operátor automaticky broadcast a za hardwarových prostředků. Uvedli jsme i několik příkladů něj rr_consolidate. Pokud použijeme operátor jeho reálných aplikací. parallel_sort v exekučním plánu, rozvine se do tvaru Do budoucna plánujeme rozšířit Bobolang tak, aby pod- znázorněného na Obrázku 8. poroval rovněž distribuované systémy. Bude tedy možné parallel_sort snadno specifikovat, jak rozdistribuovat exekuční plán sort[3] broadcast[3] merge[3] mezi více uzlů, případně nechat interpret jazyka rozdis- tribuovat plán automaticky. sort[2] broadcast[2] merge[2] disp rr_consolidate sort[1] broadcast[1] merge[1] sort[0] broadcast[0] merge[0] Reference [1] E.A. Ashcroft, A.A. Faustini, R. Jagannathan, and W.W. Obrázek 8: Paralelizovaný třídicí operátor. Wadge. Multidimensional programming. Oxford Univer- sity Press, 1995. Bobolang—jazyk pro systém Bobox 81 [2] David Bednarek, Jiri Dokulil, Jakub Yaghob, and Filip Za- Glu: A high-level system for granular data-parallel progra- voral. Bobox: Parallelization Framework for Data Proces- mming. Concurrency - Practice and Experience, 9(1):63– sing. In Advances in Information Technology and Applied 83, 1997. Computing, 2012. [17] Ujval J. Kapasi, William J. Dally, Scott Rixner, John D. [3] Ian Buck. Brook: A streaming programming language, Owens, and Brucek Khailany. Programmable stream pro- 2001. cessors. IEEE Computer, 36:282–288, 2003. [4] Ian Buck, Tim Foley, Daniel Horn, Jeremy Sugerman, Ka- [18] William R. Mark, R. Steven, Glanville Kurt, Akeley Mark, yvon Fatahalian, Mike Houston, and Pat Hanrahan. Brook and J. Kilgard. Cg: A system for programming graphics for GPUs: Stream Computing on Graphics Hardware. ACM hardware in a c-like language. ACM Transactions on Gra- Transactions on Graphics. phics, 22:896–907, 2003. [5] David R Butenhof. Programming with POSIX threads. [19] J. Reinders. Intel threading building blocks. O’Reilly, Addison-Wesley Professional, 1997. 2007. [6] Roger D Chamberlain, Mark A Franklin, Eric J Tyson, Ja- [20] William Thies, Michal Karczmarek, and Saman Amara- mes H Buckley, Jeremy Buhler, Greg Galloway, Saurabh singhe. StreamIt: A language for streaming applications. Gayen, Michael Hall, EFBerkley Shands, and Naveen Sin- In Compiler Construction, pages 179–196. Springer, 2002. gla. Auto-pipe: Streaming applications on architecturally [21] Dan Zhang, Zeng zhi Li, Hong Song, and Long Liu. A diverse systems. Computer, 43(3):42–49, 2010. programming model for an embedded media processing ar- [7] R. Chandra. Parallel programming in OpenMP. Morgan chitecture. In SAMOS, pages 251–261, 2005. Kaufmann, 2001. [8] Charles Consel, Hedi Hamdi, Laurent Réveillère, Lenin Singaravelu, Haiyan Yu, and Calton Pu. Spidle: A DSL approach to specifying streaming applications. In Pro- ceedings of the 2nd international conference on Genera- tive programming and component engineering, GPCE ’03, pages 1–17, New York, NY, USA, 2003. Springer-Verlag New York, Inc. [9] Abhishek Das, William J. Dally, and Peter Mattson. Com- piling for stream processing. In Proceedings of the 15th in- ternational conference on Parallel architectures and com- pilation techniques, PACT ’06, pages 33–42, New York, NY, USA, 2006. ACM. [10] Zbynek Falt, David Bednarek, Miroslav Cermak, and Fi- lip Zavoral. On Parallel Evaluation of SPARQL Queries. In DBKDA 2012, The Fourth International Conference on Advances in Databases, Knowledge, and Data Applicati- ons, pages 97–102. IARIA, 2012. [11] Zbynek Falt, Jan Bulanek, and Jakub Yaghob. On Paral- lel Sorting of Data Streams. In ADBIS 2012 - 16th East European Conference in Advances in Databases and Infor- mation Systems, 2012. [12] Zbynek Falt, Miroslav Cermak, and Filip Zavoral. Highly Scalable Sort-Merge Join Algorithm for RDF Querying. In The Second International Conference on Data Manage- ment Technologies and Applications, 2013. [accepted]. [13] Zbynek Falt and Jakub Yaghob. Task scheduling in data stream processing. In Proceedings of the Dateso 2011 Workshop, pages 85–96. Citeseer, 2011. [14] M.A. Franklin, E.J. Tyson, J. Buckley, P. Crowley, and J. Maschmeyer. Auto-pipe and the X language: A pipeline design tool and description language. In Parallel and Dis- tributed Processing Symposium, 2006. IPDPS 2006. 20th International. IEEE, 2006. [15] Michael I. Gordon, William Thies, and Saman Amara- singhe. Exploiting coarse-grained task, data, and pipeline parallelism in stream programs. In Proceedings of the 12th international conference on Architectural support for pro- gramming languages and operating systems, ASPLOS-XII, pages 151–162, New York, NY, USA, 2006. ACM. [16] Rangaswamy Jagannathan, Chris Dodd, and Iskender Agi.