M A S A R Y K O V A U N I V E R Z I T A F A K U L T A I N F O R M A T I K Y Možnosti využitia súbežného programovania pre vyhľadávanie v textových korpusoch B A K A L Á R S K A P R Á C A Radoslav Rábara Brno, 2014 Prehlásenie Prehlasujem, že táto bakalárska práca je mojím pôvodným autorským dielom, ktoré som vypracoval samostatne. Všetky zdroje, pramene a literatúru, ktoré som pri vypracovaní používal alebo z nich čerpal, v práci riadne citujem s uvedením úplného odkazu na príslušný zdroj. Vedúci práce: Mgr. Pavel Rychlý, Ph.D. ii Poďakovanie Rád by som poďakoval pánovi Mgr. Pavlovi Rychlému, Ph.D. za jeho odborné vedenie, cenné rady a v neposlednom rade za čas, ktorý mi pri tvorbe tejto práce venoval. Ďalej by som rád poďakoval svojej rodine a priateľom za podporu pri písaní tejto práce. iii Zhrnutie Cieľom práce je naštudovanie prístupov k súbežnému spracovaniu a ich aplikovanie na vyhodnocovanie dopytov v systéme Manatee. Súčasťou práce je nielen podrobné vyhodnotenie rýchlosti spracovania rôznych dopytov v závislosti na počte jadier dostupných počas výpočtu, ale aj porovnanie rozsahu novej a pôvodnej implementácie. iv Kľúčové slová súbežnosť, Manatee, Go, vyhodnotenie rýchlosti, analýza kódu v Obsah 1 Úvod 1 2 Program Manatee 3 2.1 O programe 3 2.2 Štruktúra korpusu 3 2.3 FastStream a RangeStream 4 2.3.1 FastStream 4 AddLabel 5 2.3.2 RangeStream 6 2.3.3 Vyhľadávací jazyk CQL (Corpus Query Language) 7 Jednoduché dopyty atribút-hodnota 7 Regulárne výrazy 8 Globálne podmienky 8 Operátor within 8 3 Jazyk Go 9 3.1 Paralelizmus a súbežnosí 10 4 Implementácia 11 4.1 Testovanie návrhu implementácie 11 4.2 Posielanie dát cez kanál 13 4.2.1 Štruktúra posielaných dát 13 4.2.2 Posielanie balíkov dát 15 4.2.3 Operácia fínd 16 4.2.4 Posielanie dát cache friendly prístupom 16 4.2.5 AddLabel 18 4.3 Ukončenie nepotrebných go-rutín 18 5 Vyhodnotenie 20 5.1 Program querybench.sh vyhodnocujúci rýchlosí 20 5.2 Dopyty pre vyhodnotenie rýchlosti 21 5.3 Vyhodnotenie rýchlosti 22 5.4 Vyhodnotenie zmeny dĺžky kódu 24 5.4.1 Analýza zdrojového kódu 24 5.4.2 Počet riadkov kódu 25 6 Záver 27 A Použité testovacie dopyty pre vyhodnotenie rýchlosti 31 B Obsah elektronickej prílohy 33 vi Kapitola 1 Úvod Pre používateľa je rýchlosť dôležitým aspektom mnohých programov. Zvyšuje sa spolu s výkonom procesorov, ktorý každoročne rastie, pričom náročnosť programov sa stále stupňuje. Výrobcovia procesorov vyrábajú viacjadrové procesory pre dosiahnutie väčšieho výkonu pri rovnako dostupnej cene za procesor. Viacjadrové procesory sú bežnou súčasťou elektronických zariadení, dokonca aj v súčasných mobilných telefónoch nachádzame dvojjadrové procesory. Avšak viac jadier procesora nezrychli programy, ktoré nie sú naprogramované pre paralelné vykonávanie výpočtov. Aplikácie nedokážu využiť dostupný výkon ďalších jadier procesora, čím strácajú výhodu, ktorú im dnešné procesory poskytujú. Straty sú v dnešných zariadeniach veľké, pretože už bežný pracovný počítač má dve až štyri jadrá a výkonný server má osem a viac jadier. Cieľom tejto bakalárskej práce je zistiť, či sa oplatí naprogramovať aplikáciu, ktorá rozdelí svoj beh do viacerých súbežných úloh. Návrh a ladenie súbežných úloh sú náročnejšie ako pri bežnom vývoji programu, preto záverečný porovnávací test ukáže, či sa oplatí navrhovať súbežne bežiace aplikácie na viacjadrové procesory. Pri porovnaní sa sústredíme nielen na zmenu rýchlosti, ktorá je dôležitá pre používateľa, ale aj na zmenu dĺžky zdrojového kódu aplikácie. DÍžka zdrojového kódu je dôležitá pre programátora, pretože kratší a prehľadnejší zdrojový kód šetrí jeho pracovný čas, čo vedie k zníženiu nákladov pri tvorbe, testovaní a udržiavaní projektu. V našej práci porovnáme dve implementácie jedného programu, sekvenčne vykonávanú na jednom jadre a paralelnú využívajúcu všetok dostupný výkon. Budeme reimplementovať korpusový manažér Manatee. Korpusový manažér je programový nástroj na spracovanie korpusov, pričom korpus je v tomto kontexte rozsiahly súbor textov v elektronickej podobe [10]. Manatee je veľký projekt, ktorý má za sebou viac ako desať rokov vývoja a je používaný mnohými univerzitami a vedeckými organizáciami zaoberajúcimi sa jazykovednou prácou. Systém vykonáva časovo náročné operácie nad množstvom dát, a preto sa pri behu kladie dôraz na rýchlosť, čím sa stáva vhodným programom pre naše porovnanie rýchlosti. V celej práci sa budeme na pôvodnú verziu odkazovať ako na pôvodnú implementáciu a reimplementovaný systém budeme nazývať novou implementáciou. Ďalšie informácie o tomto programe obsahuje druhá kapitola, ktorá v krátkosti vysvetľuje jeho použitie a popisuje dve hlavné komponenty, ktoré sú kľúčové pre výkon aplikácie. V druhej kapitole sa nachádza i čiastočný popis vyhľadávacieho jazyka C Q L (Corpus Query Language) v takom rozsahu, aby sme pochopili vyhodnocovacie dopyty 1 1. Ú V O D uvedené v piatej kapitole. Tretia kapitola sa v krátkosti venuje programovaciemu jazyku Go, ktorý bol zvolený pre implementáciu paralelnej verzie korpusového manažéra. Venuje sa mu v rozsahu predstavenia jeho špecifickej podpore súbežnosti v podobe kanálov pre komunikáciu a synchronizovaný beh [16], odľahčených procesov pre súbežný beh funkcií [19], a príkazu select pre prácu s kanálmi. Tieto prvky sú relevantné pre našu prácu a odkazujeme sa na ne v kapitole o implementácii. N a jeho vlastnostiach vysvetľuje dôvod výberu tohto jazyka. V závere kapitoly je vysvetlený rozdiel medzi súbežných spracovaním a paralelným behom programu, pretože tieto termíny sú používané v celej našej práci. Štvrtá kapitola obsahuje rozbor implementácie. Prvá časť kapitoly uvádza dôležitý prvok pri súbežnom spracovaní dát, ktorým je výmena údajov medzi samostatne bežiacimi úlohami. Vysvetľuje zmeny, ktoré priniesla komunikácia medzi súbežnými úlohami, a tiež rozdiel medzi modelom výmeny dát, ktorý by sa mal používať v jazyku Go, a jeho zmenou na náš model, ktorý je potrebný pre efektívnu komunikáciu. Druhá časť rozoberá problémy vzniknuté pri návrhu súbežnej aplikácie a tiež problémy, ktoré priniesol samotný programovací jazyk a jeho prvá verzia, a popisuje ich riešenie. Piatu kapitolu tvorí testovanie pôvodnej a novej implementácie z hľadiska rýchlosti a dĺžky kódu. Vysvetľuje spôsob vyhodnocovania, predstavuje použitý nástroj pre vyhodnotenie rýchlosti aplikácie a uvádza vyhodnocovacie dáta, na ktorých boli obe implementácie spustené. Pre novú implementáciu máme viacero výsledkov. Vyhodnocujeme ju najskôr na jednom jadre a postupne pridávame ďalšie jadrá. Tieto výsledky ukazujú vplyv počtu jadier na výslednú rýchlosť. Posledná, šiesta kapitola, sa zaoberá výsledkom vyhodnotenia. Zhŕňa výsledok experimentu a venujeme sa aj tomu, ako výsledky našej práce ovplyvnia samotný vývoj systému Manatee. 2 Kapitola 2 Program Manatee 2.1 O programe Systém Manatee je korpusový manažér, teda programový nástroj na prácu s enormným množstvom textu označovaného ako korpus. Korpusy slúžia k štúdiu slov, ich významov a najčastejších kontextov [10]. Rozsiahle korpusy používajú v praxi najmä lingvisti pri vytváraní slovníkov a na dokazovanie a vytváranie nových jazykovedných teórií. Rozsah textu v korpusoch môže byť až v rádoch miliónov a nad takýmto veľkým množstvom dát korpusový manažér vyhodnocuje komplexné dotazy, filtruje a vizualizuje výsledky a počíta základné štatistiky. Hlavný dôraz sa kladie na rýchlosť vyhod­ nocovania. Po implementačnej stránke je program Manatee postavený na knižnici Finlib [11], ktorá poskytuje funkcie pre indexovanie slov, uloženie korpusu a získanie výskytov slov vo forme prúdov pozícií [10]. N a získanie výskytov slov sa vytvárajú dopyty v jazyku rozširujúcom vyhľadávací jazyk C Q L (Corpus Query Language). Syntaktická analýza1 tohto jazyka je implementovaná pomocou nástroja ANTLR, ktorý umožňuje definovať vlastnú gramatiku a k jej elementom priradiť prislúchajúce akcie [18]. Viac informácií o programe Manatee a korpusových manažéroch sa dočítate v dizertačnej práci [10] Mgr. Pavla Rychlého, Ph.D, tvorcu systém Manatee a pokračujúceho vo vývoji systému v rámci svojej práce pre Centrum spracovania prirodzeného jazyka na Masarykovej univerzite. v 2.2 Štruktúra korpusu V našej práci pracujeme s tzv značkovaným korpusom. Značkované korpusy obsahujú okrem vlastného textu i ďalšie dodatočné informácie. Môžu obsahovať informácie o štruktúre textu (napr. kapitoly, odseky, nadpisy), jazykové javy na úrovni slov (napr. slovný druh, základný tvar slova, popis významu) či viet (napr. vyznačenie vzťahov medzi slovami). K začleneniu týchto informácií do korpusu môžeme použiť pozičné atribúty a štruktúrne značky, označované aj ako štruktúry. [10] Pozičný atribút (ďalej len atribút) umožňuje pridať informáciu pre určité slovo, tj. 1. h t t p : / / c s . w i k i p e d i a . o r g / w / i n d e x . p h p ? t i t l e = S y n t a k t i c k % C 3 % A l _ a n a l % C 3 % BDza&oldid=l0273861 3 2. P R O G R A M M A N A T E E na konkrétnu pozíciu v korpuse. V korpuse si môžeme nadefinovať viacero atribútov, napr. word (označujúci slovo na danej pozícii) a tag (vyjadrujúci slovný druh). Štruktúry sú prvky vložené medzi slová. V korpuse si môžeme nadefinovať štruktúry pre označenie viet, odsekov, či celých dokumentov. 2.3 FastStream a RangeStream FastStream a RangeStream sú rozhrania definujúce funkcie používané pre vyhodnotenie dotazov. Triedy, ktoré ich implementujú, majú na starosti konkrétne operácie. Hlavnou myšlienkou je existencia tried vykonávajúcich jednoduché operácie, ktorých spojením dosiahneme vykonanie zložitých operácií nachádzajúcich sa v komplexnom vyhľadávacom jazyku. Tieto triedy v pôvodnej implementácii fungujú na báze iterátorov. K dispozícii máme vždy jednu, aktuálnu hodnotu. Nasledujúcu hodnotu načítame volaním metódy next. Hodnoty sú vždy načrtávané v vzostupnom poradí. Po prečítaní všetkých hodnôt bude iterátor vracať zarážku, ktorá označuje koniec hodnôt. Čítanie hodnôt je možné len smerom dopredu, čiže ak raz prečítame hodnotu a posunieme iterátor volaním metódy next, tak sa už nedostaneme k predchádzajúcim hodnotám. Iterátor poskytuje aj metódy pre prácu so zvyšnými hodnotami. Metódou f i n d efektívne vyhľadávame v zozname zvyšných hodnôt a metódou peek získame nasledujúcu hodnotu, ktorú vracia volanie metódy next. [10] Špeciálny význam má metóda add.labels, ktorá sprístupňuje funkciu označenia iterátora. Pre aktuálnu pozíciu nám mapuje označenia na pozície. Táto metóda je detailnejšie popísaná v podkapitole AddLabel. FastStream a RangeStream sú hlavným predmetom nášho záujmu, pretože majú kľúčovú úlohu pri vyhodnotení dotazov. V nasledujúcich podkapitolách si v krátkosti predstavíme a vysvetlíme rozdiely medzi rozhraniami FastStream a RangeStream. 2.3.1 FastStream Hodnoty rozhrania FastStream sú prúdy pozícií. K dispozícii máme 7 rôznych tried implementujúcich rozhranie FastStream: • DeltaPosStream - predstavuje pozície vybraného slova v korpuse. Tvorí základ pre ďalšie operácie, pretože ako jediná trieda nespracováva iný FastStream. Bez inštancie tejto triedy nemôžu byť použitá žiadna z ostatných tried implementujúcich rozhranie FastStream, keďže ostatné triedy vykonávajú operácie nad parametrami typu FastStream, a preto vyžadujú takéto objekty ako parametre pri svojej konštrukcii. • AddLabel - je unárna operácia, ktorá priradí danému FastStreamu číselnú značku. Takto označený FastStream môžeme použiť k filtrovaniu výsledku. Viac informácií o tejto operácii poskytuje nasledujúca podkapitola. 4 2. P R O G R A M M A N A T E E • QAndNode - je binárna operácia prieniku (operácia AND), ktorej výsledkom sú spoločné pozície nachádzajúce sa v oboch FastStreamoch. • QOrNode - je binárna operácia spájajúca dva FastStreamy (operácia OR). Vo výslednom prúde sú všetky pozície z oboch FastStreamov bez duplicít. • QNotNode - je unárna operácia negácie (operácia NOT). Vytvorí prúd pozícií začínajúci 0 a končiaci zarážkou. Z prúdu odstráni všetky pozície, ktoré obsahuje FastStream, nad ktorým sa operácia vykonáva. • QOrVNode - je operácia spojenia realizovaná na zozname FastStreamov (operácia OR). Vykonáva rovnakú operáciu ako QOrNode, ktorý je určený pre spojenie dvoch FastStreamov. N a rozdiel od triedy QOrNode, je trieda QOrVNode určená pre efektívne spracovanie zoznamu FastStreamov s veľkosťou i stovky tisíc.Využíva sa napríklad pri vyhodnocovaní regulárneho výrazu, ktorý vznikne spojením všetkých slov vyhovujúce zadanému vzoru. • QMoveNode - je unárna operácia, ktorá posunie všetky pozície daného prúdu o určenú hodnotu. Používa sa pri hľadaní slov nasledujúcich za sebou. Predpokladajme, že hľadáme dve slová, pričom druhé slovo nasleduje hneď za prvým. Najskôr si prevedieme slová na prúdy pozícií pomocou DeltaPosStream. Prúd druhého slova bude obsahovať pozície, ktoré budú o jeden väčšie ako pozície prvého slova. Preto všetky pozície druhého prúdu posunieme o -1, a tým v druhom prúde dostaneme pozície, ktoré sú zhodné s pozíciami v prvom prúde. Následne vykonáme operáciu logického prieniku a vo výsledku dostaneme pozície ukazujúce na miesta v texte, kde sú obe hľadané slová. AddLabel V novej implementácii má operácia AddLabel rozdielnu implementáciu. Z tohto dôvodu si v tejto podkapitole opíšeme, ako táto funkcia pracuje v pôvodnom systéme. V predchádzajúcej podkapitole sme si stručne uviedli základný princíp tejto operácie, ktorým je priradenie číselnej značky danému FastStreamu. Číselná značka je z implementačného hľadiska priradená nie prúdu ako celku, ale každej jeho pozícii. A k napríklad spájame dva prúdy pozícií, tak vo výsledku máme pozície z oboch prúdov. My však musíme vedieť rozlíšiť, ktoré pozície patria do označeného prúdu. Preto metóda add.labels mapuje číselnú značku na aktuálnu pozíciu. Toto mapovanie prebieha len v triede AddLabel. Ostatné triedy delegujú vykonanie tejto funkcie na FastStreamy, nad ktorými vykonávajú danú operáciu. Z hľadiska implementácie sú dôležité dva prvky. Prvým je delegovanie funkcie a druhým je práca s dátovou štruktúrou mapa. N a príklade volania metódy add.label s triedy QAndNode si priblížime prácu tejto operácie i samotnú implementáciu: 5 2. P R O G R A M M A N A T E E //mapovanie číselného označenia na pozíciu type L a b e l s m a p [ i n t ] P o s i t i o n func (q QAndNode) a d d _ l a b e l s ( l a b s Labels) { //delegovanie f u n k c i e s r c l . a d d _ l a b e l s ( l a b s ) ; s r c 2 . a d d _ l a b e l s ( l a b s ) ; } //ak s r c l j e označený F a s t S t r e a m func ( s r c l AddLabel) a d d _ l a b e l s ( l a b s Labels) { l a b s f l a b e l ] = s r c l . p e e k ( ) } //ak src2 n i e j e označený prúd func (src2 DeltaPosStream) a d d _ l a b e l s ( l a b s Labels) { //DeltaPosStream n e d e l e g u j e f u n k c i u , //pretože n e p r a c u j e so žiadnym FastStreamom } O praktickom použití označovania pozícií sa viac dočítate v diele Manatee, Bonito and Word Sketches for Czech [12]. 2.3.2 RangeStream RangeStream je prúd rozsahov. Rozsah je určený dvojicou čísel. Prvé číslo určuje jeho začiatok a druhé číslo ukazuje na prvú pozíciu za rozsahom. V matematickom pojímaní táto dvojica čísel vyjadruje interval zľava uzavretý a sprava otvorený =, väčší ! <= a menší !>= Zátvorky môžeme nechať aj úplne prázdne, čím sa stanú „divokou kartou", ktorá zastupuje akékoľvek slovo v korpuse. Napríklad dopyt "confus . * " [] by vyhľadá postupnosť, v ktorej prvé slovo začína reťazcom „confus", za ktorým je akékoľvek slovo nasledované slovom „by". A k hľadáme sekvenciu s dvomi slovami medzi „confus.*" a „by", tak dopyt zapíšeme ako "confus . * " [] 2 "by". Dopyt "confus. * " [] 0, 3 "by" nájde postupnosti až s tromi slovami a tiež postupnosti bez ďalšie slova medzi slovami „confus.*" a „by". [7] 7 2. P R O G R A M M A N A T E E Regulárne výrazy Regulárne výrazy môžu byť použité pre vyjadrenie hodnoty atribútov Povolenými operátormi regulárnych výrazov sú: • Disjunkcia | • Kleeneho hviezda * • Operátor plus + • Operátor voliteľnosti ? • Inverval {n, k} (ak je k vynechané, tak sa vyhľadáva presne n opakovaní) Výraz v hranatých zátvorkách je vyhodnotený na atribútoch nachádzajúcich sa na danej pozícii v korpuse. Môže obsahovať operátori konjunkcie (&), disjunkcie (|) a negácie (!). Ako bolo uvedené na príklade v predchádzajúcej kapitole, za hranaté zátvorky môžeme uviesť interval alebo operátor, ktorý určuje počet výskytov daného výrazu v hľadanej postupnosti slov. [7] Globálne podmienky Globálne podmienky poskytujú možnosť filtrovania výsledkov dopytu. Musia sa nachádzať na konci dopytu, od ktorého sú oddelené symbolom ampersand &. Aby sme ich mohli použiť, musíme relevantné výrazy prefixovo označiť číselnou značkou. Globálne funkcie môžeme použiť napr. k získaniu všetkých susedných slov, ktoré majú rovnaký atribút tag: 1: [ ] 2 : [ ] & 1. tag = 2 . tag. [7] Operátor within Operátor within slúži k obmedzeniu výsledkov dopytu na tie, ktoré sa nachádzajú v rozsahu výsledkov špecifikovaného dopytu. Ak sa v korpuse nachádzajú vety, paragrafy či iné značky dokumentov zadefinované ako štruktúry, môžeme ich použiť k obmedzeniu výsledkov. Ako príklad uvádzame dopyt pre získanie postupnosti slov, v ktorej prvé slovo začína na reťazec „confus" a nasleduje slovom „by", pričom výsledky obmedzíme len na tie, v ktorých sa postupnosť nachádza v rámci jednej vety: "confus . *by"within . Použili sme štruktúru reprezentujúcu vety v korpuse. [7] 8 Kapitola 3 Jazyk Go Programovací jazyk Go, nazývaný aj golang, vznikol ako projekt spoločnosti Google v roku 2007. Go využíva výkon a bezpečnosť aké ponúkajú kompilované jazyky ako C alebo C++, a snaží sa ich spojiť s možnosťami rýchleho vývoja aké ponúkajú dynamické jazyky ako Python [6]. N a jeho vývoji sa podieľali známy programátori ako Ken Thompson, autor operačného systému Unix [20], Rob Pike, ktorý sa tiež podieľal na vývoji Unixu [21], či Robert Griesemer, ktorý pracoval na virtuálnom stroji Java HotSpot Machine [22]. [19] Tento jazyk sme si vybrali kvôli jeho rýchlosti a zabudovanej podpory súbežnosti. Súbežnosť je jednou z možností ako dosiahnuť paralelizmus. V Go je použitie súbežnosti jednoduché vďaka jednoduchému spúšťaniu súbežne bežiacich funkcií a poskytnutému nástroju pre komunikáciu medzi nimi. [8] Súbežne bežiace funkcie sa nazývajú go-rutiny (z anglického goroutines). Umožňujú ľahké použitie súbežnosti v programoch. Majú menšie operačné a pamäťové nároky ako vlákna, vďaka čomu je ich volanie a správa výhodnejšia. Myšlienkou je spojenie vykonávania funkcií do množiny vlákien. A k sa vykonávanie funkcie zablokuje, čiže zastaví, napríklad kvôli čakaniu na dokončenie systémovej operácie, tak sa zvyšné funkcie presunú do iného vlákna, aby nečakali na dokončenie zablokovanej funkcie. Programátor sa však o nič z tohto nestará. Presúvanie funkcií a alokácia potrebnej pamäte pre každú z nich, sa deje automaticky počas behu programu. [15] Komunikáciu medzi súbežne bežiacimi go-rutinami zabezpečuje dátový typ kanál (z anglického channel). Kanál poskytuje dvom súbežne bežiacim funkciám mechanizmus umožňujúci synchronizáciu behu a výmenu hodnôt dopredu určeného typu [16]. Posielanie a prijímanie skrz kanál zablokuje vykonávanie go-rutiny až kým je druhá strana pripravená na prijímanie alebo posielanie. Go-rutinám to umožňuje synchronizáciu bež explicitného použitia zámkov či podmienených premenných [14]. Kanály môžu byť vytvorené so zásobníkom. A k bude zásobník plný, tak posielanie hodnôt spôsobí čakanie na uvoľnenie miesta v zásobníku. A naopak ak bude zásobník prázdny, tak prijímanie hodnôt spôsobí čakanie na vloženie prvku do zásobníka. [13] Posledným zabudovaným prvkom pre podporu súbežnosti je príkaz select. Syntaxou sa podobá známemu príkazu switch a takisto na základe testovania vyberá procedúru, ktorá sa bude vykonávať. Namiesto porovnávania hodnôt sa testujú kanály a vybraný je prvý kanál pripravený na komunikáciu. [17] 9 3. J A Z Y K G O 3.1 Paralelizmus a súbežnosť Paralelizmus a súbežnosť sú často nerozlišované pojmy. Hoci spolu súvisia, pomenúvajú odlišné myšlienky, a preto je chybou nerozlišovat medzi ich významom a používat ich ako synonymá. Paralelizmus je simultánne vykonávanie viacerých vecí naraz, typicky funkcií, ktoré spolu môžu a nemusia súvisieť. Naproti tomu súbežnosť je riadenie viacerých vecí naraz, pričom slúži aj k vytváraniu sekvenčných programov. Súbežnosť nie je paralelizmus, ale je medzi nimi vzťah, pretože dobrý súbežný návrh umožňuje paralelné vykonávanie úloh. Súbežnosť sa sústredí na štruktúru programu. Myšlienkou je rozdeliť komplexný problém na jednoduché úlohy, ktoré môžu byť vykonávané nezávisle, a koordinovať ich beh cez komunikáciu. S použitím jazyka Go je súbežnosť nástrojom pre vytvorenie zrozumiteľného, efektívneho a škálovateľného programu, ktorý môže byť aj paralelný. Docieľuje to vďaka úsporným go-rutinám, ktorých call stack sa zväčšuje a zmenšuje podľa potreby, a kanálom ako jednoduchého nástroja komunikácie a koordinácie, ktorý nahradzuje použísvanie zložitých mechanizmov synchronizácie ako sú zámky a zdieľanie pamäte pre komunikáciu. [4] Dodatočné informácie a ilustračné príklady nájdete v prezentácii Concurrency is not Parallelism [8]. 10 Kapitola 4 Implementácia Táto kapitola prináša rozbor problémov a ich riešení, ktoré vznikli pri implementovaní súbežného návrhu tried implementujúcich rozhrania FastStream a RangeStream. Na rozdiel od pôvodnej implementácie sú FastChan a RangeChan štruktúry poskytujúce kanál s pozíciami. Štruktúry nemajú žiadnu z pôvodných metód ako next, peek, či f ind, pretože kanál samotný reprezentuje prúd pozícií. Operácia f i n d bola z novej implementácie odstránená, pretože nedochádzalo k jej efektívnemu využívaniu, čo malo za následok spomalenie behu programu. Štruktúry FastChan a RangeChan poskytujú aj dátové štruktúry reprezentujúce operáciu AddLabel a kanál ukončujúci spustené go-rutiny. Mechanizmus bude vysvetlený v samostatnej podkapitole. Operácie tried FastStream a RangeStream sú vytvorené podľa vzoru „generátor" jazyka Go [3]. Podľa neho sú operácie volané ako funkcie, ktoré vytvoria kanál, spustia go-rutinu a vrátia kanál. Go-rutina vykonáva výpočty, ktorých výsledky posiela cez kanál a po skončení výpočtov kanál zavrie. V nasledujúcich kapitolách používame označenie vysielajúca go-rutina, ktorá posiela dáta cez kanál, a prijímajúca go-rutina, ktorá prijíma poslané údaje z kanála. V novej implementácii používame v názvoch sufix „Chan" ako mennú konvenciu pre zdôraznenie používania kanálov ako prostriedku posielania dát v našej implementácii. Rovnako sme premenovali FastStream a RangeStream na FastChan a RangeChan, kde nahradzuje nová prípona pôvodnú príponu „Stream". Aj operácie týchto tried majú zmenený názov pridaním prípony alebo nahradením pôvodnej prípony (napr. QAndNodeChan, QNotNodeChan, DeltaPosChan). 4.1 Testovanie návrhu implementácie Pri implementovaní súbežného návrhu sme skúšali viacero možností implementácie. Porovnávali sme ich meraným doby behu pomocou unixového príkazu time, na jednoduchých testovacích dátach. Najskôr sme používali simulovanú operáciu DeltaPosChan, ktorá nenačítavala prúd pozícií zo súboru uloženého na disku, ale generovala aritmetickú postupnosť pozícií. Pri nastavení počiatočného člena a diferencie sme vedeli ľahko určili veľkosť výsledku a náročnosť operácii s jednotlivými prúdmi. Pre testovanie sme si vybrali operáciu A N D ako jednu zo základných binárnych operácií, na ktorej sme porovnávali jednotlivé návrhy. 11 4. I M P L E M E N T Á C I A Používaním aritmetickej rady odbudlo vykonávanie diskových operácií pre nájdenie zoznamu pozícií na disku a nasledujúcich operácií čítania dát z disku. Tým sme znížili počet volaní systémových funkcií, o ktorých sme sa domnievali, že by nám vytvárali veľké rozdiely medzi meranými časmi pre jednu možnosť implementácie, a tým zhoršili objektivitu pri porovnávaní možností. Simulovanú operáciu DeltaPosChan sme prestali používať od testovania implementácie operácie f i nd. Práve pri tomto testovaní sme nevedeli, či za zhoršenú dobu behu operácie f i n d môžu simulované dáta generované bez časových medzier, a či sa chovanie programu zmení pri náraste vykonávaných operácií, čítaním údajov z disku a dekódovaním dát na pozície. Tým sme zistili potrebu používania reálnych operácií s reálnymi dátami. Vybrali sme päť reálnych testovacích vstupov, s ktorými sme opäť testovali operáciu A N D . Testovacie dáta sú dvojice slov z Britského Národného Korpusu [1] (ďalej len BNC), ktorý predstavuje kolekciu príkladov sto miliónov slov písanej a hovorenej angličtiny [2]. Dvojice slov predstavujú slová nasledujúce za sebou, preto musíme použiť operáciu posunutia QMoveNodeChan na druhé slovo rovnako ako sme vysvetľovali použitie tejto operácie na slovách nasledujúcich za sebou v kapitole FastStream. Základnou myšlienkou testovania je skúšanie rozličnú náročnosť operácie prieniku, ktorej dávame na vstup veľký prúd s veľkým alebo malým prúdom, pričom výsledok operácie bude veľký alebo malý prúd. Pri testovaní nemá zmysel vytvárať operáciu prieniku na dvoch malých prúdoch, pretože program s takýmito testovacími vstupmi by bežal príliš krátko a výsledné doby behu rôznych možností implementácie by boli príliš podobné a ťažko by sa objektívne určovalo, ktorá alternatíva implementácie je lepšia. Testovacie výrazy sú uvedené v tabuľke č.l v syntaxi korpusového opytovacieho jazyka systému Manatee. V tabuľke sa nachádzajú aj počty výskytov prvého a druhého slova a veľkosť výsledku operácie A N D . Druhý testovací dotaz obsahuje prázdne hranaté zátvorky. Tie slúžia ako „divoká karta", za ktorú môžeme dosadiť akékoľvek slovo [7]. Vo finálnej implementácii sa hranaté zátvorky prevedú na prúd pozícií obsahujúce všetky pozície v korpuse. M y sme však pri testovaní neprevádzali divokú kartu na prúd pozícií, ale vykonali sme operáciu A N D na slovách „the" a „of" , pričom sme druhé slovo posunuli operáciu QMoveNodeChan o -2 pozície, čím sme dostali výsledok pre dotaz na prvé slovo nasledujúce akýmkoľvek slovom, za ktorým je druhé slovo. To odpovedá zápisu s divokou kartou. Piaty výraz obsahuje dve hranaté zátvorky odpovedajúce syntaxi [attr=" hodnota" ]. V BNC má každé slovo priradený atribút tag, ktorý slúži k určeniu či je slovo napr. podstatné alebo prídavné meno. Výraz [tag="AT0 " ] predstavuje všetky členy a [tag="NNl" ] reprezentuje všetky všeobecné podstatné mena v jednotnom čísle. V celej kapitole o implementácii sa nachádzajú výsledky testovania programov kompilovaných pomocou kompilátora go verzie 1.1.1. 12 4. I M P L E M E N T Á C I A P.č. Výraz Počet výskytov 1. slova Počet výskytov 2. slova Počet pozícií výsledku operácie A N D 1. "tne" "of " 5,415,473 3,027,293 295 2. "tne" [ ] " o f " 5,415,473 3,027,293 844,966 3. "tne" " C o l l c u t t " 5,415,473 1 0 4. "tne" "name" 5,415,473 25,473 5,854 5. [ tag= [ tag= " A T O " ] " M l " ] 8,663,490 14,281,233 4,499,750 Tabuľka č. 1 - Použité testovacie vstupy s množstvami pozícií pre slová a výsledky. 4.2 Posielanie dát cez kanál 4.2.1 Štruktúra posielaných dát Na začiatku implementovania go-rutín sme narazili na problém so zmenou rýchlosti pri spustení programu na viacerých jadrách. Pri paralelnom behu úloh na viacerých jadrách sme očakávali nárast výkonu premietnutý v kratšom čase behu aplikácie. Naproti očakávaniam boli výsledky horšie, čo mohlo znamenať, že úlohy nebežia paralelne alebo prítomnosť viacerých jadier zhoršuje výkon réžiou úloh bežiacich paralelne. Výsledky ukazuje graf na obrázku č. 4.1. V programe, na ktorom sa testovala zmena rýchlosti pri paralelnom behu, sa nachádzali tri go-rutiny. Aplikácia vykonávala logickú operáciu A N D na dvoch prúdoch simulujúcich operáciu DeltaPosChan. Simulovaná operácia DeltaPosChan nenačítavala prúd pozícií zo súboru uloženého na disku, ale generovala aritmetickú radu pozícií. Takéto simulovanie operácie má výhodu v jednoduchom určení výsledku a náročnosti výpočtov operácie A N D . Program sme testovali na 1 procesore so 4 jadrami. Údaje sú vysielané z DeltaPosChan bez časovej medzery, keďže počítanie ďalšieho prvku aritmetickej rady je jednoduchá operácia. Preto sme vyskúšali simulovanú operáciu nahradiť skutočnou funkciou, ktorá pracovala s reálnymi dátami. Výsledky testovania nášho návrhu s reálnymi dátami takisto vykazovali spomalenie pri behu na viacerých jadrách procesora, a preto sme usúdili, že simulovaná operácia výrazne neovplyvňuje výkon programu. Prijímanie údajov je s minimálnou časovou medzerou, keďže operácia A N D vykonáva jednoduchý cyklus. Porovnáva aktuálne hodnoty a podľa výsledku porovnania vykoná jednu z dvoch možností. Pri rovnosti hodnôt pridá pozíciu na výstup a načíta ďalšie hodnoty z oboch vstupných prúdov. Pri nerovnosti vyberie kanál, z ktorého načítala menšiu hodnotu, a z neho načíta nasledujúcu pozíciu. Pri riešení problému s naším návrhom sme sa zamerali na uvedené operácie posielania a prijímania. Považovali sme ich za úzke miesto, pretože sa snažia preniesť veľké množstvo údajov v čo najkratšom čase, pomocou častého používania kanálov. Avšak pri každej komunikácii cez kanál dochádza k používaniu zámkov pre dosiahnu- 13 4. I M P L E M E N T Á C I A Doba behu Na 1 jadre Na 2 jadrách Na 3 jadrách Na 4 jadrách Obr. 4.1: Graf ukazujúci zhoršenie rýchlosti pri zvyšovaní počtu jadier, na ktorých aplikácia beží. tie synchrónnej komunikácie, čo môže viesť k veľkej réžii pri behu na viacerých proce­ soroch. Naša myšlienka efektívnejšieho prenosu bola v práci s balíkmi dát miesto jednotlivých pozícií. Go-rutiny nebudú posielať a prijímať pozície po jednom, ale pošlú či prijmú odkaz na balík dát v pamäti. Čím väčší je balík dát, tým nižšia je frekvencia posielania dát a menej časté zamykanie kanálu. Práca s balíkmi dát môže takisto zlepšiť výkon načítaním celého alebo časti balíka do vyrovnávacej pamäte pri posielaní či prijí­ maní. Používanie balíkov dát spôsobí väčšie čakanie na prvý balík dát, ktorý musí najskôr vstupná funkcia naplniť a odoslať. Následne však už k čakaniu nedochádza, pretože každá go-rutina pracuje s prijatým balíkom dát. Výsledky upraveného programu, s posielaním balíkov dát miesto jednotlivých pozícií, odpovedajú našim očakávaniam ohľadom zrýchlenia aplikácie pri paralelnom behu. Program vykonáva rovnakú operáciu, ale rýchlosť sa zlepšuje pri spustení na viacerých procesoroch. Výsledky ukazuje graf na obrázku č. 4.2 . Na grafe vidíme zrýchlenie pri prechode z jedného na dve jadrá, čo spôsobila menšia réžia posielania a prijímania dát. N a grafe vidíme, že pri ďalšom pridávaní jadier sa neprejavuje výrazné zrýchlenie. Tento jav odpovedá jednoduchosti testovacieho programu, v ktorom sa nachádzajú dve relatívne rýchle operácie DeltaPosChan a len jedna výpočtovo náročnejšia operácia QAndNode. 14 4. I M P L E M E N T Á C I A Obr. 4.2: Graf ukazujúci zlepšenie rýchlosti pri posielaní dát v balíkoch. 4.2.2 Posielanie balíkov dát Používanie balíkov dát má nevýhodu v opakovaní alokácie a dealokácie pamäte prostredníctvom správcu pamäte (gargbage collector), pretože nový balík dát musí byt vytvorený po každom odoslaní údajov a starý musí byť odstránený po ukončení spracovania balíka. Opakujúce sa priraďovanie a uvoľňovanie pamäte uberá aplikácii na výkone kvôli nadbytočnej réžii zabudovaného správcu pamäte. Tento problém riešime recyklováním troch balíkov. Na začiatku činnosti go-rutiny vytvoríme tri balíky, ktoré striedavo používame pre vysielanie dát. Z trojice používaných balíkov sa vyberie jeden, ktorý najskôr napĺňame pozíciami a neskôr ho odošleme, keď je plný alebo keď je výpočet go-rutiny ukončený. Prenos dát je sprostredkovaný kanálom so zásobníkom pre jeden prvok. Kanál so zásobníkom umožní odoslať údaje bez toho, aby sa vysielajúca go-rutina zablokovala, dokiaľ nie sú údaje prijaté prijímajúcou go-rutinou. Keďže odoslané balíky používame pre ďalší zápis hodnôt, musíme si dať pozor na prepisovanie hodnôt balíka, ktorý je práve spracovávaný prijímajúcou go-rutinou. Náš návrh počíta s touto situáciou a vyhýba sa jej použitím zásobníka so správnou veľkosťou. Prítomnosť zásobníka s veľkosťou pre jeden balík umožňuje naplnený balík odoslať a bez čakania začať napĺňať ďalší balík. A k go-rutina čítajúca posielané balíky prijala 15 4. I M P L E M E N T Á C I A poslaný balík, tak je zásobník kanála opäť prázdny a môžeme odoslať aj druhý balík bez čakania a zapisovať údaje do posledného balíka. A k prijímajúca go-rutina stále pracuje s prvým balíkom, tak v zásobníku kanála sa nachádza druhý balík, čo nám neumožní odoslať tretí balík bez čakania na uvoľnenie zásobníka prijatím balíka. Keď prijímajúca go-rutina spracuje prvý balík, tak prečíta z kanála druhý balík. To uvoľní kanál a umožní vysielajúcej go-rutine odoslať tretí balík a prepisovať prvý balík. Prijímajúca go-rutina už pracuje s druhým balíkom a preto jej výpočet neovplyvní zmena hodnôt v prvom balíku. Tento mechanizmus platí pre prácu so všetkými tromi balíkmi. 4.2.3 Operácia find V pôvodnej implementácii sa nachádza metóda f i n d , ktorá slúži k efektívnemu vyhľadávaniu v zozname zvyšných hodnôt [10]. Z novej implementácie bola táto operácia odstránená, pretože v bežných prípadoch znižovala výkon aplikácie. V pôvodnom sekvenčnom návrhu vstupný prúd vypočíta ďalšiu pozíciu až pri volaní metódy next. Preto je žiaduce znížiť počet volaní metódy next posunutím sa v prúde pozícií na potrebnú pozíciu. A k sa v prúde hľadaná pozícia nenachádza, tak sa posunieme na prvú pozíciu, ktorá je väčšia ako hľadaná pozícia. V novom súbežnom návrhu sme použili kanál f i n d , do ktorého prijímajúca gorutina poslala pozíciu, ktorú chcela vyhľadať v zozname zvyšných hodnôt. Vysielajúca go-rutina použila príkaz s e l e c t pre kontrolu existencie hodnoty v kanáli a preskočila nasledujúce pozície menšie ako prijatá hodnota. Počítali sme so znížením množstva prenesených údajov a zvýšením výkonu. Avšak ani jeden z predpokladov sa nenaplnil. Množstvo prenesených údajov sa neznížilo, pretože takmer v každom prípade sa použitie operácie f i n d skončilo bez preskočenia pozícií. Vyhľadávanie sa neuskutočnilo, pretože v zozname zvyšných hodnôt sa nachádzali len väčšie hodnoty ako bola hľadaná hodnota. Je to dôsledok súbežného návrhu, v ktorom úlohy vykonávajú svoju operáciu po nejaký čas, alebo kým ich nezastaví nástroj synchronizácie, posielanie či prijímanie hodnôt z kanálu. V našom prípade go-rutiny vypočítali veľké množstvo pozícií, a preto operácia už nemala aké pozície preskočiť, pretože buď už hľadané a menšie pozície boli odoslané alebo boli už pridané do balíka. Jediný prípad, kedy operácia f i n d urýchlila výpočet, bolo spojenie veľkého prúdu pozícií s malým prúdom pozícií, v ktorom použitie operácia f i n d preskočilo statisíce pozícií. V ostatných prípadoch však mala implementácia bez operácie f i n d lepšie výsledky, a preto sme operáciu find nezahrnuli do nového návrhu. 4.2.4 Posielanie dát cache friendly prístupom Cache friendly prístup je programovanie s optimálnym využívaním rýchlych vyrovnávacích pamätí (ang. cache) procesora. Prístup do cache pamäte je rýchlejší ako prístup do operačnej pamäte. Údaje sa načítavajú do vyrovnávacích pamätí za účelom zníženia prístupov do operačnej pamäte pri opakovanom použití daných dát. Do cache pamäte sa nenačítajú iba dáta z požadovanej adresy v operačnej pamäti, ale načíta sa aj časť 16 4. I M P L E M E N T Á C I A okolitých dát. Myšlienkou je preniesť do cache pamäte aj pridružené dáta, ktoré bude procesor s veľkou pravdepodobnosťou skoro potrebovať. [5] Tento postup je účinný pre zníženie množstva času, ktorý by procesor čakal na načítanie dát z operačnej pamäte, čím prirodzene dochádza k zrýchleniu vykonávania programu. Optimálne využívanie vyrovnávacej pamäte sa dá dosiahnuť používaním malých dátových štruktúr, ktoré po načítaní do pamäte celé využijeme. Pre implementáciu kanálu prenášajúceho dvojice pozícií v štruktúre RangeChan, sme chceli použiť malú dátovú štruktúru obsahujúcu dve čísla. Predpokladali sme, že ide o cache friendly prístup, pretože spĺňa vyššie uvedený predpoklad o optimálnom využívaní vyrovnávacej pamäte. Náš predpoklad sme verifikovali porovnaním používania jedného a dvoch kanálov. Jeden kanál prenášal obe dvojice v malej štruktúre a dva kanály si rozdelili prenášanie hraníc intervalu. Porovnanie výkonu spočívalo v jednoduchom teste vypisujúceho obe dvojice. Výsledky porovnania vyvrátili náš predpoklad o výhode používania jedného kanálu. Preto vo finálnej implementácii používame dva kanály. Výsledky testu sú zobrazené v grafe na obrázku č. 4.3 . Doba behu 24,2 - i — Najhorší čas Priemerný čas Najlepší čas H Jeden kanál posielajúci dvojicu dát H Dva kanály Obr. 4.3: Graf porovnávajúci posielanie dvojíc dát jedným kanálom a posielanie pozícií dvomi kanálmi. Z grafu je vidieť, že v najlepšom, priemernom i v najhoršom prípade, je variant s dvomi kanálmi, rýchlejší ako variant jedného kanála posielajúceho dvojicu dát, o ktorom sme predpokladali, že je cache friendly. 17 4. I M P L E M E N T Á C I A 4.2.5 AddLabel Funkciu AddLabel sme pre pôvodnú implementáciu uviedli v samostatnej podkapitole. Pre pripomenutie si v rýchlosti uvedieme dva dôležité prvky tejto funkcie: • je postavená na princípe iterátorov • deleguje vrátenie výsledku na prúdy pozícií, s ktorými pracuje Nová implementácia používa kanály miesto iterátorov. Preto nemôžeme použit rovnaký spôsob delegovania výpočtu hodnoty značky ako tomu bolo v pôvodnej implementácii. Miesto toho musíme posielať hodnoty značiek spolu s číselnými pozíciami štruktúr FastChan a RangeChan. Každá značka má svoj vlastný kanál, ktorom sa nachádzajú jej hodnoty. Poradie v kanáli je dané tak, aby odpovedalo pozícii dát v kanáli pozícií. Posielanie spolu s pozíciami v jednom kanáli bolo nevýhodné z hľadiska výkonu rovnako ako to je opísané v kapitole vyššie o cache friendly prístupe. 4.3 Ukončenie nepotrebných go-rutín Pri vyhodnocovaní niektorých dotazov sa program dostane do stavu, keď obsahuje trvalo spiace go-rutiny. Kanály majú zásobník fixnej veľkosti, ktorý po naplnení spôsobí čakanie go-rutiny na odobranie údajov. Prijímajúca go-rutina však môže ukončiť svoj výpočet ešte pred prijatím všetkých údajov od vysielajúcej go-rutiny, čím sa vysielajúca funkcia môže dostať do stavu, keď je jej kanál plný a zároveň chce funkcia odoslať ďalšie údaje. Takáto vysielajúca go-rutina sa bude v pamäti nachádzať až do ukončenia programu. Stav obsahujúci trvalo spiacu go-rutinu sa vyskytuje napríklad pri použití operácie A N D so vstupom takých prúdov, z ktorých jeden prúd vyprodukuje väčšie množstvo dát ako je veľkosť zásobníka aj po odoslaní balíka dát obsahujúci maximum druhého prúdu. To je dôsledok ukončenia výpočtu operácie A N D pri prečítaní všetkých pozícií jedného z dvojice kanálov. Keďže sú pozície zoradené vzostupne, tak posledná pozícia je maximálna pozícia. Preto vieme, že keď druhý kanál odošle balík dát obsahujúci maximálnu pozíciu prvého kanála, tak sa ďalej stane nepotrebným a ďalšie balíky dát tohto kanála nebudú operáciou A N D prečítané. Preto keď si následne stále aktívny kanál zaplní zásobník kanála, tak zostane trvalo spať až do ukončenia programu. Trvalo spiace go-rutiny budú problémom pri uvedení novej implementácie do požadovanej podoby na server, kde bude jeden program vyhodnocovať množstvo požiadaviek. Po čase by dostupnú pamäť zaberalo obrovské množstvo trvalo spiacich go-rutín, ktoré by spôsobili zaplnenie pamäte aplikácie, čo by viedlo k následnému zrúteniu programu. To je dôvod, prečo musíme nepotrebné go-rutiny ukončiť. Jazyk Go neposkytuje žiadnu implicitnú funkciu či spôsob na ukončenie aktívnej gorutiny najmä kvôli problému uvoľnenia jej zdrojov a aktívnych zámkov. Preto si musíme 18 4. I M P L E M E N T Á C I A túto požiadavku na ukončenie go-rutín implementovat samy pomocou vhodného me­ chanizmu. Prostým riešením by bolo modifikovať problémové operácie tak, aby vždy dočítali zostávajúce dáta zo vstupných go-rutín. Ide však o neefektívne riešenie, ktoré má negatívny vplyv na výkon aplikácie. Preto sme potrebný mechanizmus implementovali pomocou dodatočného kanála, ktorý vysielajúcej go-rutine pošle signál pred ukončením výpočtu prijímajúcej go-rutiny. Vysielajúca go-rutina si vždy najskôr overí, či neprišiel signál od prijímajúcej go-rutiny a až potom odošle naplnený balík dát. Prijímajúce go-rutina musí po odoslaní signála ešte prijať jeden balík dát a až potom ukončiť svoju činnosť. Tým predchádzame situácii, keď príde signál o ukončení po kontrole pred poslaním dát do kanála s plným zásobníkom. 19 Kapitola 5 Vyhodnotenie V tejto kapitole sú predstavené vyhodnocovacie techniky a nástroje použité pre porovnanie pôvodnej a novej implementácie z hľadiska rýchlosti a dĺžky kódu. Predstavuje vyhodnocovací program querybench.sh a vyhodnocovacie dáta použité pre určenie rýchlosti implementácií. Taktiež tu sú prezentované výsledky vyhodnocovania. Rýchlosť novej implementácie je určená spustením aplikácie na jednom jadre, ku ktorému sa postupne pridáva po jednom jadre. Vďaka testovaniu s postupným zvyšovaním počtu využívaných jadier sa ukazuje vplyv počtu jadier na zvýšenie rýchlosti aplikácie. 5.1 Program querybench.sh vyhodnocujúci rýchlosť Vyhodnocovací program querybench.sh vytvára správu o rýchlosti vyhodnocovania vstupných dát. Je to skript naprogramovaný pre interpret Bash. Vyhodnocovaciemu programu sú na vstupe predané dva argumenty. Prvým je konfiguračný súbor obsahujúci údaje o korpuse, ktorý bude použitý k vyhodnoteniu daných dát. Druhým argumentom programu je názov textového súboru, v ktorom sa nachádzajú dáta. N a každom riadku sa nachádza príkaz alebo komentár. Príkazy môžu byť dáta pre vyhodnotenie zapísané v opytovacom jazyku alebo to môžu byť príkazy modifikujúci vyhodnocovanie dát, ako nastavenie štandardného atribútu či obmedzenie výsledkov na výskyt v rámci danej štruktúry. Komentáre slúžia len k dokumentácii súboru a sú programom ignorované. Rovnako sú ignorované i prázdne riadky. Dáta sú vyhodnotené programom corpquery, ktorý dáta vyhodnocuje a prezentuje výsledky. Testovací skript spúšťa aplikáciu corpquery s takými parametrami, aby zobrazil výsledky ako číselné pozície. Rozsahy prezentuje len jedným číslom určujúce začiatok intervalu. Vyhodnocovací skript meria dobu získania výsledku. Používa k tomu externý program time. V správe o rýchlosti vyhodnotenia vstupných dát je uvedená trojica časových hodnôt. Prvá je celkový čas (real time) behu od spustenia po ukončenie aplikácie. Ďalšie dva časové údaje určujú čas vykonávania inštrukcií na jadrách procesoru. Druhá hodnota je čas strávený vykonávaním neprivilegovaných príkazov (user time) a posledný údaj udáva čas, ktorý uplynul pri realizovaní systémových funkcií (systém time). Pri behu súbežnej aplikácie na viacerých jadrách sa user a systém time stopuje pre každé jadro. Preto súčet týchto dvoch hodnôt môže byť väčší ako celkový čas behu programu. 20 5. V Y H O D N O T E N I E Doba vyhodnotenia dát je ovplyvňovaná samotným systémom, v ktorom beží variabilný počet procesov, ktoré sa delia o výpočtový čas procesora. Preto skript počíta priemerný čas z predvoleného počtu vyhodnotení dát. Pri porovnaní pôvodnej a novej implementácie sa priemerný čas počíta z desiatich behov. Priemerný čas sa počíta pre každý z trojice časov uvedených v predchádzajúcom odstavci. Vyhodnocovací skript neposkytuje overenie správnosti výsledku porovnaním s očakávaným výsledkom. Avšak zaznamenáva veľkosť výsledku ako počet riadkov, ktoré výsledok zaberá. Veľkosť výsledku vyjadrená počtom riadkov sa používa ku kontrole determinizmu algoritmov, ktoré musia dávať pre jeden vstup vždy rovnaký výstup. Preto program querybench.sh porovnáva veľkosť výsledkov medzi behmi vyhodnocujúce rovnaké dáta. Táto kontrola poslúžila k odhaľovaniu tzv race condition v implementáciách funkcií vytvárajúcich štruktúru FastChan. Race condition je chyba, pri ktorej je výsledok ovplyvnení poradím vykonávania súbežných operácií. [9] Príklad správy vyprodukovanej testovacím programom querybench.sh nájdeme medzi prílohami. Ide o ukážku vyhodnotenia niekoľkých jednoduchých testovacích dát. Pre lepšiu čitateľnosť obsahuje menší počet behov, z ktorých sa počíta priemerný čas. 5.2 Dopyty pre vyhodnotenie rýchlosti Vyhodnotenie oboch implementácií bolo uskutočnené na pripravených vyhodnocovacích dátach. Ide o sadu 15 dát predstavujúcich relatívne zložité a komplexné dopyty pokrývajúce pravidlá syntaktickej analýzy. Často ich vyhodnotením dostaneme veľké množstvo výsledkov, 5-10 % z celého korpusu, a výsledky dokopy pokrývajú skoro celý korpus. Nie sú špecializované na konkrétne slová, ale zameriavajú sa na získavanie slovných druhov (napr. dopyt pre vyhľadanie všetkých podstatných mien, pred ktorými sa nachádza prídavné meno). Tým sú do istej miery extrémne, pretože bežný užívatelia programu Manatee vytvárajú opytovacím jazykom dopyty na konkrétne slovo s nejakými podmienkami, čím dostávajú rádovo menšie výsledky. Dopyty sú zostavené za účelom vyhodnotenia rýchlosti implementácií na BNC. BNC pozostáva z textov reprezentujúcich typické použitie Britskej angličtiny z druhej polovice 20. storočia. Patrí medzi veľké korpusy. Obsahuje okolo sto miliónov slov. [2] Vyhodnotenie dát je modifikované dvomi príkazmi. Prvý príkaz mení predvolený atribút z atribútu word na tag. Druhý príkaz zužuje množinu výsledkov na tie, ktoré sa nachádzajú v rozmedzí jednej vety (pridaním wit hin < s / > za jednotlivé dáta určené k vyhodnoteniu). Výpis všetkých pätnástich vyhodnocovacích dopytov sa nachádza v prílohe A. Celý textový súbor, obsahujúci aj komentáre a vyššie spomenuté modifikačné príkazy, sa nachádza v elektronickej prílohe. 21 5. V Y H O D N O T E N I E 5.3 Vyhodnotenie rýchlosti Vyhodnotenie oboch implementácií prebiehalo na serveri Alba. Je to server Masarykovej univerzity s doménou alba.fi.muni.cz, ktorý disponuje ôsmimi jadrami. Pôvodná implementácia je bez vlákien a súbežného behu, takže využíva vždy len jeden procesor. Nová implementácia je postavená na súbežnom paradigme, využíva go-rutiny a pri vyhodnocovaní môže byť výpočet rozdelený medzi viacero vlákien. Vyhodnotili sme jej rýchlosť najskôr na jednom procesore a postupne sme pridávali po jednom procesore. Pôvodnej implementácii trvalo 4 hodiny, 29 minút a 24 sekúnd, kým vyhodnotila všetky vstupné dopyty. Priemerné časy pre jednotlivé dáta sú zobrazené grafom na obrázku č. 5.1. Graf zobrazuje celkový čas vyhodnotenia (real) daného vstupu. Výsledná správa vyprodukovaná programom querybench.sh sa nachádza v elektronickej prí­ lohe. Doby behu testovacích dopytov v sekundách 250,00 - i 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. Poradové číslo vyhodnocovacích dopytov Obr. 5.1: Graf prezentujúci celkové časy vyhodnotenia testovacích dopytov pôvodnou implementáciou na serveri Alba Nová implementácia spustená na jednom jadre vyhodnotila testovacie dopyty za 2 hodiny, 27 minút a 39 sekúnd. V porovnaní s pôvodnou implementáciou je rýchlejšia približne o 45 %. Priemerné časy vyhodnotenia jednotlivých testovacích dát sú zobrazené na grafe na obrázku č. 5.2 . Správa o vyhodnotení sa nachádza v elektronickej prílohe. 22 5. V Y H O D N O T E N I E Z grafov môžeme vyčítať, že 13 z 15 testovacích dopytov bolo vyhodnotených rýchlejšie novou implementáciou s priemerných zrýchlením o cca. 45 %. Markantné zrýchlenie o 82 % sme zaznamenali u 14. dopytu a naopak najmenšie zlepšenie o 20 % u 2. dopytu. U 2 dopytov sme namerali zhoršenie, a to u 9. dopytu o 116 % a u 11. dopytu o 7 %. Doby behu v sekundách 120,00 Poradové číslo vyhodnocovacích dopytov Obr. 5.2: Graf zobrazujúci celkové časy vyhodnotenia testovacích dopytov novou implementáciou na serveri Alba Vyhodnotenie novej implementácie prebehlo na množine všetkých kombinácií dostupného počtu procesorov, aby sme mohli posúdiť zmenu výkonu s narastajúcim počtom výpočtových jednotiek, na ktorých je nová implementácia spustená. Zmenu výkonu podľa poč-tu procesorov zobrazuje graf na obrázku č. 5.3 . Na grafe je vidieť, že doba behu sa najvýraznejšie zníži pri prechode od jedného na dve jadrá, ktorý urýchlil vyhodnotenie o 43 %. Pridávaním ďalších a ďalších jadier sa zmenšuje časový rozdiel medzi dobami behu. Výnimku tvorí doba behu s využitím všetkých ôsmich dostupných jadier, spôsobí zníženie rýchlosti, a teda nárast doby behu oproti vyhodnoteniu na siedmich a i šiestich jadrách. Vyhodnotením na troch jadrách sa zrýchli výpočet o 24 % oproti vyhodnoteniu na dvoch jadrách a o 57 % v porovnaní s výpočtom na jednom jadre. Doba vyhodnotenia so štyrmi jadrami je rýchlejšia o 18 % v porovnaní s vyhodnotením na troch jadrách a o 65 % v porovnaní s dobou behu na jednom jadre. Pridaním piateho jadra sa zmenší 23 5. V Y H O D N O T E N I E doba vyhodnotenia o 11 % v porovnaní so štyrmi jadrami. Pridávaním ďalších jadier sa rozdiel dostáva pod 5 % oproti dobe behu s počtom jadier o jedna menší. Obr. 5.3: Graf zobrazujúci výkon novej implementácie spustenej na všetkých kombináciách dostupného počtu procesorov serveru Alba 5.4 Vyhodnotenie zmeny dĺžky kódu 5.4.1 Analýza zdrojového kódu Pôvodná implementácia je naprogramovaná v jazyku C++, v ktorom máme súbory rozdelené na hlavičkové súbory a súbory obsahujúce vlastnú implementáciu. Hlavičkové súbory sú špeciálnymi súbormi obsahujúce deklaráciu tried, funkcií či premenných. Spravidla môžu obsahovať aj implementáciu krátkych funkcií. Práca s kódom vyžaduje čítanie oboch súborov, a preto sme pre každú triedu v našom vyhodnotení počítali riadky oboch typov súborov. Nová implementácia naprogramovaná v programovacom jazyku Go má výhodu v absencii hlavičkových súborov a nutnosti explicitne linkovať súbory v rovnakom module (adresári). Naopak dlhší kód spôsobujú striktné syntaktické pravidlá, potreba explicitnej implementácie niektorých dátových štruktúr ako je napr. prioritná fronta, ktorá je v C++ poskytovaná štandardnou knižnicou. Zdrojový kód v novej implementácii zväčšuje i implementácia mechanizmu posielania a prijímania dát v balíkoch, ktoré umožňujú efektívnu paralelnú komunikáciu pri spracovávaní dopytu. C++ má výhodu 24 5. V Y H O D N O T E N I E i v použití inicializačných zoznamov1 , ktoré umožňujú pri konštrukcii objektov skrátiť inicializáciu atribútov na jeden riadok. Striktné syntaktické pravidlá v jazyku Go neumožňujú skrátený zápis tzv jednoriadkových funkcií, či zápis príkazu if bez bloku kódu. Taktiež neumožňujú niektoré bežné zápisy z jazyka C++ ako napr. premenná 1 = premenna2++;. Jednoriadkové funkcie sú funkcie, ktorých zápis spolu s telom sa nachádza na jednom riadku. V jazyku Go musí byť takáto funkcia zapísaná na tri riadky: v prvom je definícia funkcie, jej názov spolu so vstupnými parametrami a návratovou hodnotou, v druhom riadku je príkaz a na poslednom treťom riadku je symbol ukončenia tela fun­ kcie. 5.4.2 Počet riadkov kódu Vyhodnotenie dĺžky kódu oboch implementácií bolo vykonané na vybraných triedach, respektíve štruktúrach a funkciách (keďže v jazyku Go sa nenachádzajú triedy). Nová implementácia zatiaľ nepokrýva všetku funkcionalitu pôvodnej implementácie. Preto sme museli vybrať triedy (resp. štruktúry a funkcie), ktoré poslúžili k určeniu veľkosti zmeny dĺžky kódu medzi implementáciami. Zo zdrojových kódov oboch implementácií sme počítali len neprázdne riadky, ktoré neboli celé komentárom. A k dané súbory obsahovali v pôvodnej implementácii funkcionalitu, ktorá sa v novej implementácii nenachádza, tak sme dané definície a deklarácie vyňali z počítania počtu riadkov. Pre vyhodnotenie sme vybrali triedy, štruktúry, rozhrania a funkcie, ktoré sme rozdelili do dvoch skupín: 1. FastStream (resp. FastChan), RangeStream (resp. RangeChan) a pomocné štruktúry v novej implementácii pre posielanie dát cez kanály vo forme balíkov. Zmena dĺžky kódu ukazuje rozdiel v implementácii sekvenčnou a súbežnou paradigmou. 2. SortedRuns, ReadJbits a WriteJbits, ktorých implementácia bola ovplyvnená len samotnou zmenou programovacieho jazyka, a teda i syntaxe a povolených kon­ štrukcií V prvej skupine sú z pôvodnej implementácie zahrnuté súbory fstream.hh, fstream.cc a fsop.hh pre FastStream a frsop.hh, frstream.hh,frstream.cc a frconcat.cc pre RangeStream. Pre rozhranie FastStream sme vybrali triedy EmptyStream, SequenceStream, QNotNode, QAndNode, QOrNode, QOrVNode, QMoveNode a AddLabel. Pre rozhranie RangeStream sme vybrali triedy Pos2Range, RQinNode, RQoutsideNode, RQcontainNode, RQUnionNode, RQRepeatFSNode, RQRepeatNode, RQConcatLeftEndSorted, RQSortBeg, RQSortEnd, BegOfRStream, EndsOfRStream a RQOptionalNode. Z novej implementácie sme vybrali odpovedajúce funkcie a štruktúry nachádzajúce sa v súboroch fstreamchan.go, fsopchan.go, frstream.go a frconcatchan.go a po- 1. h t t p : / / w w w . c p r o g r a m m i n g . c o m / t u t o r i a l / i n i t i a l i z a t i o n - l i s t s - c + + . h t m l 25 5. V Y H O D N O T E N I E mocné funkcie a štruktúry pre posielanie a prijímanie dát vo forme balíkov, nachádzajúce sa v súboroch fstreamchandata.go a frstreamchandata.go. Do počítania riadkov sme zahrnuli aj funkcie nachádzajúce sa v daných súboroch. Druhú skupinu tvoria triedy (resp. štruktúry) Read-bits a WriteJbits zo súboru bitio.hh (resp. bitio.go) a trieda (resp. štruktúra) SortedRuns spolu s funkciami a pomocnými štruktúrami, ktoré sa nachádzajú v súbore srtruns.hh (resp. srtruns.go). 1400 1200 1000 > 1 800 ' i _ ,S 600 o 400 200 Počet riadkov kódu 1400 1200 1000 > 1 800 ' i _ ,S 600 o 400 200 1400 1200 1000 > 1 800 ' i _ ,S 600 o 400 200 1400 1200 1000 > 1 800 ' i _ ,S 600 o 400 200 1400 1200 1000 > 1 800 ' i _ ,S 600 o 400 200 • C++ 1400 1200 1000 > 1 800 ' i _ ,S 600 o 400 200 834 • Go 1400 1200 1000 > 1 800 ' i _ ,S 600 o 400 200 541 1400 1200 1000 > 1 800 ' i _ ,S 600 o 400 200 1400 1200 1000 > 1 800 ' i _ ,S 600 o 400 200 FastStream (resp. RangeStream (resp. Read_bits a Write_bits SortedRuns FastChan) RangeChan) Obr. 5.4: Graf prezentujúci počet riadkov kódu pre obe implementácie na vybraných triedach (resp. štruktúrach a funkciách) Výsledné počty riadkov sú zobrazené grafom na obrázku č. 5.4 . Z grafu sa dá vyčítať, že sa zmenšil počet riadkov o 21 % pri reimplementovaní FastStream a RangeStream na FastChan a RangeChan, teda pri reimplementovaní algoritmov napísaných sekvenčnou paradigmou na súbežnú paradigmu. V druhej skupine vyhodnotenia prezentujúcej zmenu dĺžky kódu ovplyvnenú len samotnou zmenou programovacieho jazyka, je vidieť, že reimplementovaním Read-bits a WriteJbits sa dĺžka kódu zvýšila. Avšak spolu so SortedRuns došlo k malému zníženiu počtu riadkov o 1 %. Nová implementácia by mohla dosiahnuť väčšiu úsporu počtu riadkov, ak by zvolený programovací jazyk sám riešil problém réžie pri prenose veľkého množstva dát v krátkom časovom úseku, ktorý sme vyriešili používaním balíkov dát. Samotná implementácia balíkov dát má rozsah 252 riadkov kódu, čo tvorí 19 % z celkového množstva riadkov implementácie FastChan a RangeChan. 26 Kapitola 6 Záver Cieľom tejto práce bolo paralelizovať sekvenčný program a vyhodnotiť zmenu v rýchlosti a dĺžke kódu medzi oboma implementáciami. Pre paralelizáciu sme vybrali korpusový manažér Manatee, ktorý umožňuje vyhľadávanie vo veľkom množstve textov. Je to veľký systém, z ktorého sme paralelizovali vyhodnocovanie dopytov na uložené textové dáta. Pôvodná verzia je naprogramovaná v jazyku C++. Označujeme ju ako pôvodnú implementáciu. Systém bol reimplementovaný programovacím jazykom Go, ktorý má zabudované prvky pre podporu súbežnosti. Novú verziu nazývame nová implementácia. Vyhodnotenie dát pôvodnou implementáciou trvalo približne 4.5 hodiny. Vyhodnotenie dát novou implementáciou na jednom jadre procesora trvalo približne 2.5 hodiny. Reimplementáciou sme dosiahli zlepšenie rýchlosti vyhodnotenia približne o 45 %. Novú implementáciu sme ďalej vyhodnocovali na všetkých možných kombináciách počtu jadier na serveri Alba. Zistili sme, že pri paralelnom behu na viacerých jadrách narastá výkon s každým pridaným jadrom v priemere o 15.7 %, pričom najväčší nárast rýchlosti o 43 % vznikne pri prechode z jedného na dve jadrá. Nová implementácia zatiaľ neobsahuje všetky funkcie ako pôvodný systém Manatee. Preto sme vybrali funkčné celky, na ktorých sme porovnali dĺžku kódu oboch implementácií. Počítali sme len neprázdne riadky, ktoré neboli komentárom. Vykonali sme aj analýzu kódu, podľa ktorej je z hľadiska dĺžky kódu nevýhodou jazyka C++ existencia hlavičkových súborov a jazyka Go striktné syntaktické pravidlá a nutnosť implementácie niektorých dátových štruktúr a mechanizmu pre posielanie balíkov dát. Celkovo má pôvodná implementácia vo vybraných funkčných celkov 2027 riadkov kódu a nová implementácia má 1667 riadkov kódu. Vyhodnotenia preukázali, že nová implementácia je lepšia z pohľadu rýchlosti, a aj z pohľadu kratšej dĺžky kódu. Preto plánujeme ďalej pokračovať v reimplementácii systému Manatee a postupne nahradiť pôvodnú sekvenčnú implementáciu novou súbežnou implementáciou. 27 Literatúra [1] ASTON, Guy; BURNARD, Lou. The BNC handbook. Edinburgh: Edinburgh University Press, 1998. s. 256. ISBN 0-7486-1055-3. [2] BURNARD, Lou. What is the BNC? [online]. Jan. 2009 [cit. 18-12-2013] Dostupné z URL: h t t p : / /www. n a t c o r p . ox . ac . uk/corpus / i n d e x . xml. [3] D O L A N , Ryanne. Go Language Patterns: Generators [online], posledná aktualizácia: 11-12-2009 08:34 UTC [cit. 18-12-2013]. Dostupné z URL: h t t p s : / / s i t e s . g o o g l e . c o m / s i t e / g o p a t t e r n s / c o n c u r r e n c y / g e n e r a t o r s . [4] GERRAND, Andrew. Concurrency is not parallelism [online]. Jan. 2013 [cit. 13-12-2013]. Dostupné z U R L : h t t p : / / b l o g . g o l a n g . o r g / c o n c u r r e n c y - i s - n o t - p a r a l l e i i s m . [5] GOTTBRATH, Chris. Cache-Friendly Code: Solving Manycore's Need for Faster Data Access [online]. Nov. 2012 [cit. 07-01- 2014]. Dostupné z U R L : http://www.drdobbs.com/parallel/ c a c h e - f r i e n d l y - c o d e - s o l v i n g - m a n y c o r e s - n e / 2 4 0 0 1 2 7 3 6 . [6] KINCAID, Jason. Google's Go: A New Programming Language That's Python Meets C++, [online]. Nov. 2009 [cit. 18-01-2014]. Dostupné z URL: h t t p : / / techcrunch.com/2009/11/10/google-go-language/. [7] Lexical Computing Ltd. . Corpus Querying: Corpus Query Language (CQL) [online], posledná aktualizácia: 27-02-2014 20:21 U T C [cit. 05-03-2014]. Dostupné z URL: https://www.sketchengine.co.uk/documentation/wiki/ SkE/CorpusQuerying?version=30. [8] PIKE, Rob. Concurrency is not parallelism [online]. Jan. 2012 [cit. 13-12-2013]. Dostupné z URL: h t t p : / / t a l k s . g o l a n g . o r g / 2 0 1 2 / w a z a . s l i d e . [9] ROUSE, Margaret. DEFINITION: race condition [online], posledná aktualizácia: 09- 2005 [cit. 07-01-2014]. Dostupné z URL: h t t p : / / s e a r c h s t o r a g e . t e c h t a r g e t . c o m / d e f i n i t i o n / r a c e - c o n d i t i o n . [10] RYCHLÝ, Pavel. Korpusové manažery a jejich efektívni implementace. Brno, 2000. XIV+128 s. Dizertačná práca. FI M U . 28 6. Z Á V E R [11] RYCHLÝ, Pavel. Manatee/Bonito - A Modular Corpus Manager In 1st Workshop on Recent Advances in Slavonic Natural Language Processing. Brno: Masaryk University, 2007. s. 65-70. ISBN 978-80-210-4471-5. [12] RYCHLÝ, Pavel; SMRŽ, Pavel. Manatee, Bonito and Word Sketches for Czech In Second International Conference on Corpus Linguisitcs. Saint-Petersburg: SaintPetersburg State University Press, 2004. s. 124-132.ISBN 5-288-03531-8. [13] The Go Authors. A Tour of Go: Buffered Channels [online]. The Go programming language [cit. 13-12-2013]. Dostupné z URL: h t t p : / / t o u r . g o l a n g . org/#67. [14] The Go Authors. A Tour of Go: Channels [online]. The Go programming language [cit. 13-12-2013]. Dostupné z URL: h t t p : / / t o u r . g o l a n g . org/# 6 6. [15] The Go Authors. Frequently Asked Questions (FAQ): Why goroutines instead of threads? [online]. The Go programming language [cit. 13-12-2013]. Dostupné z URL: h t t p : / / g o l a n g . o r g / d o c / f a q # g o r o u t i n e s . [16] The Go Authors. The Go Programming Language Specification: Channel types [online]. The Go programming language, Nov. 2013 [cit. 13-12-2013]. Dostupné z URL: h t t p : / / g o l a n g . o r g / r e f / s p e c # C h a n n e l _ t y p e s . [17] The Go Authors. The Go Programming Language Specification: Select statements [online]. The Go programming language, Nov. 2013 [cit. 13-12-2013]. Dostupné z URL: h t t p : / / g o l a n g . o r g / r e f / s p e c # S e l e c t _ s t a t e m e n t s . [18] Wikipedia contributors. ANTLR [online]. Wikipedia, The Free Encyclopedia, posledná aktualizácia: 28-02-2014 15:03 UTC [cit. 03-03-2014]. Dostupné z URL: h t t p : //en.wikipedia.org/w/index.php?title=ANTLR&oldid=597529412. [19] Wikipedia contributors. Go (programming language) [online]. Wikipedia, The Free Encyclopedia, posledná aktualizácia: 21-11-2013 16:31 U T C [cit. 30-11- 2013]. Dostupné z URL: h t t p ://en . w i k i p e d i a . org/w/index . php?t i t le= Go_(programming_language)&oldid=582 68 9902. [20] Wikipedia contributors. Ken Thompson [online]. Wikipedia, The Free Encyclopedia, posledná aktualizácia: 05-04-2014 09:57 U T C [cit. 06-04-2014]. Dostupné z U R L : h t t p ://en . w i k i p e d i a . org/w/index . p h p ? t i t l e = K e n _ Thompson&oldid=602 8 42 711. [21] Wikipedia contributors. Rob Pike [online]. Wikipedia, The Free Encyclopedia, posledná aktualizácia: 16-02-2014 13:14 U T C [cit. 06-04-2014]. Dostupné z URL: h t t p : / / e n . w i k i p e d i a . o r g / w / i n d e x . p h p ? t i t l e = R o b _ P i k e & o l d i d = 595725640. 29 6. Z Á V E R [22] Wikipedia contributors. Robert Griesemer [online]. Wikipedia, The Free Encyclopedia, posledná aktualizácia: 16-07-2013 22:17 U T C [cit. 06-04-2014]. Dostupné z URL: h t t p : / / e n . w i k i p e d i a . o r g / w / i n d e x . p h p ? t i t l e = R o b e r t _ Griesemer&oldid=5 64 57 317 8. 30 Dodatok A Použité testovacie dopyty pre vyhodnotenie rýchlosti P.č. Príkaz určený k vyhodnoteniu 1. 1:"N.." [word=","]{0,1} [word="and"|word="or "|word=","] [tag="AT."|tag="DT."|tag="DPS"|tag="[OC]RD"| tag="AV0" |tag="AJ."|tag="POS"]{0,3} "N.."{0,2} 2:"N..'" [tag!="N.." & tag!="POS"] 2. 1:"VV."[word=","]{0,1} [word="and"|word="or" |word=","] [tag="AV0"|tag="XX."]{0,3} 2:[tag="VV."] & 1 .tag=2.tag 3. 1:"AJ." [word=","]{0,1} [word="and"|word="or í! |word=","]{0,2}[tag="AV0"|tag="XX."]{0,3} 2: [tag="AJ."] & 1.tag=2.tag 4. 1:"VV."[tag="AV0"|tag="XX."]{0,3} [tag="AT." |tag="DPS"|tag="[OC]RD"|tag="AV0"|tag="AJ." |tag="DT." |tag="POS"]{0,3} "N.."{0,2} 2:"N.." [tag!="N . . " & tag!="POS"] 5. 2:"N.." [tag="AV0"|tag="XX."]{0,3} 1:"VVN" 6. 2:"N.." [tag="DTQ"|tag="PNQ"|tag="CJT"]? [tag="AV0"|tag="XX."|tag="V[MH] . "]{0,5} "VB.n [tag="AV0"|tag="XX."]{0,3} 1:"VVN" 7. 2:"N.." [tag="DTQ"|tag="PNQ"|tag="CJT"]? [tag="AV0"|tag="XX."|tag="V[MHB] ,"]{0,6} 1:"VV[DIGZ]" 8. 2:"N.." [tag="DTQ"|tag="PNQ"|tag="CJT"]? [tag="AV0"|tag="XX."|tag="V[MHB]."]{0,6} "VH TI [tag="AV0"|tag="XX."]{0,3} 1:"VVN" 9. 1:"VVN" [tag="AV0"|tag="XX."]{0,3} [word="by "] [tag="AT."|tag="DT."|tag="DPS"|tag="[OC]RD"| tag="AV0" |tag="AJ."|tag="POS"]{0,3} "N.."{0,2} 2:"N..'" [tag!="N.." & tag!="POS"] 10. 1:"N.." [tag="DTQ"|tag="PNQ"|tag="CJT" ] ? [tag="AV0"|tag="XX."|tag="V[MHB],"]{0,6} 2:"AJ. " [tag!="N.."] 31 A . P O U Ž I T É T E S T O V A C I E D O P Y T Y PRE V Y H O D N O T E N I E R Ý C H L O S T I P.č. Príkaz určený k vyhodnoteniu Í L 1:"N.." [tag="DTQ"|tag="PNQ"|tag="CJT"]? [tag="AV0"|tag="XX."|tag="V[MH] . "]{0,5} "VB. " [tag="AV0"|tag="XX."]{0,3} [tag="AT."|tag="DT." |tag="DPS"|tag="[OC]RD"|tag="AV0"|tag="AJ." |tag="POS"]{0,3} "N.."{0,2} 2:"N.." [tag!="N.." & tag!="POS"] 12. 2: "AJ." [tag="A[VJ] . " | word=", "] {0, 3} "N. ."{0,2} 1:"N.." [tag!="N.." & tag!="POS"] 13^ 2 : "N. . " "N. ."{0,3} 1 : "N. . " Tí 2 : "AV0" 1: [tag="AJ. " | tag="VV. "] 15^ 1:"VV." [tag="AV0"|tag="XX."]{0,3} 2:"AV0" [tag!="AV0" & tag!="AJ."] 32 Dodatok B Obsah elektronickej prílohy V archíve záverečnej práce v informačnom systéme Masarykovej univerzity sa nachádza elektronická príloha obsahujúca pomocné materiály: • textový súbor queries.test obsahujúci testovacie dopyty, ktoré sú vstupom pre testovací program querybench.sh • správa vyhodnotenia rýchlosti pôvodnej implementácie programom querybench.sh na serveri Alba v súbore c.txt • správa vyhodnotenia rýchlosti novej implementácie na jednom jadre programom querybench.sh na serveri Alba v súbore gol.text • správa vyhodnotenia rýchlosti novej implementácie na dvoch jadrách programom querybench.sh na serveri Alba v súbore go2.text • správa vyhodnotenia rýchlosti novej implementácie na troch jadrách programom querybench.sh na serveri Alba v súbore go3.text • správa vyhodnotenia rýchlosti novej implementácie na štyroch jadrách programom querybench.sh na serveri Alba v súbore go4.text • správa vyhodnotenia rýchlosti novej implementácie na piatich jadrách programom querybench.sh na serveri Alba v súbore go5.text • správa vyhodnotenia rýchlosti novej implementácie na šiestich jadrách programom querybench.sh na serveri Alba v súbore goó.text • správa vyhodnotenia rýchlosti novej implementácie na siedmich jadrách programom querybench.sh na serveri Alba v súbore go7.text • správa vyhodnotenia rýchlosti novej implementácie na ôsmich jadrách programom querybench.sh na serveri Alba v súbore go8.text 33