===== Velká úloha ===== Protože upload systém nepodporuje vlákna (jedno odevzdání má vždy alokováno pouze jedno jádro) a protože bychom od vás rádi viděli větší, samostatně vyrobený program, tento úkol se odevzdává mailem a my ho budeme bodovat manuálně. Deadline k odevzdání je poslední den semestru. [[https://docs.google.com/spreadsheets/d/e/2PACX-1vSS16pDjcA6RxWsAlgk_B2UvAfpy5EtEFGxvG8XA8KPKs1bdC6Fer8wIwJKwaZBXfTCFAOQODq-XLxi/pubhtml?gid=1493556420&single=true|Přehled studentů a vybraných témat]] ==== Zadání ==== Zadání je stanoveno na základě domluvy studenta s cvičícím. Součástí zadání jsou i stručné požadavky na funkcionalitu programu. ==== Obecné požadavky ==== Všechny odevzdané práce musí * Obsahovat implementaci s jedním i více vlákny. * Mezi oběma implementacemi jde volit pomocí přepínače na příkazové řádce. * Porovnat obě implementace. * Implementace používající více vláken musí být rychlejší než implementace s jedním vláknem. * Implementace musí být specializované pro případ běhu s vlákny i bez vláken. * Bez problémů projít kontrolou nástroji jako je Valgrind, Helgrind... ==== Odevzdání, termín a hodnocení ==== Velkou úlohu je nutno odevzdat cvičícímu e-mailem. Tento e-mail musí obsahovat: * zdrojové soubory, * soubory popisující postup stavby programu: ''CMakeLists.txt'', ''Makefile'', nebo projektové soubory IDE (''.vcxproj'', apod.) * průvodní zprávu, která obsahuje: * popis vašeho zadání, * popis vaší implementace, Pokud je potřeba vysvětlit složité součásti návrhu (velká funkce, komplikovaná třída, složitá synchronizace), není nutné psát detaily do e-mailu, raději je pište do komentářů v kódu. Nejzazší termín odevzdání je **poslední den semestru, neděle 15. ledna 2016**. Pozdní odevzdání je možné pouze ve výjimečných případech a po domluvě s cvičícím. Cvičící musí zareagovat do 7 dnů od přijetí odevzdané práce a sdělit studentovi hodnocení. Student může zlepšit svoje hodnocení opakovaným odevzdáním, ale pouze pokud opakované odevzdání proběhne před termínem. Pokud bylo předchozí odevzdání neúspěšné, student může odevzdat i po termínu. Za velkou úlohu je možné získat až 20 bodů, z nichž je potřeba alespoň 10 k získání zápočtu. Za velmi kvalitní práci může cvičící přidat i bonusové body nad 20. ==== Příklady zadání ==== Protože občas může být těžké vymyslet si vlastní zadání, uvádíme několik možných příkladů. Pozor na to, že i pokud si vyberete z následujícího seznamu, zadání vám musí schválit cvičící. === Maticové algoritmy === V závislosti na zvoleném algoritmu či metodě paralelizace můžete (po domluvě) uvažovat vstupní data ve speciálním tvaru (např. pouze čtvercové matice, matice, které mají délku strany mocninu dvou, ...). == Násobení matic == Násobení matic je jedna z výpočetně nejzajímavějších operací v lineární algebře. Zaprvé protože je velmi časté, zadruhé protože je to operace, která dobře naimplementovaná opravdu může dosáhnout limitu výpočetní rychlosti procesoru (narozdíl třeba od sčítání vektorů, které jsou omezeny rychlostí přístupu do paměti). Očekáváme, že naimplementujete něco sofistikovanějšího než 3 for loopy dle definice maticového násobění. == Výpočet determinantu čtvercové matice == Determinant lze jednoduše počítat dle definice nebo Laplaceovou expanzí, v praxi tyto algoritmy ale nejsou vhodné kvůli své časové složitosti. Efektivní implementace jsou založené na [[https://cs.wikipedia.org/wiki/Gaussova_eliminační_metoda|Gaussově eliminační mětodě]] (LU dekompozice). Očekáváme, že váš program bude schopen pracovat s maticemi 1000x1000 v rozumném čase (tj. řádově vteřiny, max. desítky vteřin). Aplikace na vstupu dostane čtvercovou matici, na výstupu vypíše hodnotu jejího determinantu. == Řešení soustav lin. rovnic == Další z velmi důležitých úloh lineární algebry. Aplikace na vstupu dostane rozšířenou matici soustavy a na výstup vypíše vektor jejího řešení, případně zprávu o tom, že řešení neexistuje. Pokud je řešení nekonečně mnoho, program vypíše jedno partikulární řešení a bázi lineárního prostoru řešení přidružené homogenní soustavy. K implementaci je nejvýhodnější použít [[https://cs.wikipedia.org/wiki/Gaussova_eliminační_metoda|Gaussovu eliminaci]] se zpětným dosazením. === Grafové algoritmy === Aplikace načte vstupní graf ze souboru, příp. standardního vstupu v libovolném vámi zvoleném formátu. Doporučujeme použít jednoduchý textový formát, např. 0 ... 1 ... ... Pokud byste si chtěli grafy vizualizovat, je možné použít nástroj ''dot'' z toolkitu [[http://www.graphviz.org/|Graphviz]] nebo C%%++%% knihovnu [[http://www.ogdf.net|OGDF]]. == Minimální kostra (minimum spanning tree) == Minimální kostry mají široké využití - od návrhů tras elektrického vedení, přes vytváření routovacích tabulek v počítačových sítích až po shlukování (clustering) bodů v analýze dat či detekce útvarů v počítačovém vidění. Doporučujeme použít [[https://www.algoritmy.net/article/1396/Boruvkuv-algoritmus|Borůvkův algoritmus]]. Na výstupu programu bude seznam vrcholů minimální kostry a její cena nebo přímo popis celého grafu pro Graphviz, s barevně odlišenými vrcholy v kostře. == Nejkratší cesty mezi všemi vrcholy (shortest paths) == Další z velmi dobře prozkoumaných grafových algoritmů, které mají využití jak ve fyzickém světě, tak ve světě počítačů. Na výstupu je seznam dvojic vrcholů s délkou minimální cesty mezi nimi (pokud existuje) a vypsanou cestou. == Problém obchodního cestujícího == Problém obchodního cestujícího ([[https://en.wikipedia.org/wiki/Travelling_salesman_problem|Travelling salesman problem]]) spočívá v nalezení nejkratší (nejlevnější) hamiltonovské cesty v orientovaném grafu, tj. takové cesty, která obsahuje každý vrchol právě jednou. Je to NP těžký problém, který se při použití metody větví a mezí dobře paralelizuje. Možný algoritmus je popsaný v [[http://math.feld.cvut.cz/demlova/teaching/lgr/text_lgr_2016.pdf|materiálech]] k předmětu Logika a grafy v sekci Hledání nejkratší hamiltonovské cesty. Na výstupu bude posloupnost vrcholů cesty a její cena nebo přímo popis celého grafu pro Graphviz, s barevně zvýrazněnými hranami v cestě. === k-means (clustering) === [[https://cs.wikipedia.org/wiki/K-means|K-means]] je jednoduchý iterativní algoritmus pro shlukování množiny bodů do //k// skupin (kde //k// je známé předem) s jednoduchou paralelizací. Vstupem je množina bodů (standardní vstup nebo soubor) a počet skupin (parametr na příkazové řádce), na výstupu vrací seznam bodů a jejich příslušnost do skupiny. Výsledek je vhodné vizualizovat výstupem do obrázku [[https://cs.wikipedia.org/wiki/Scalable_Vector_Graphics|SVG]]. Pro snadnou vizualizaci doporučujeme pracovat ve 2D. === Výpočetní geometrie (computational geometry) === Úlohy z oblasti výpočetní geometrie se zabývají geometrickými výpočty v rovině a prostoru. Protože náročnost soudobých grafických aplikací stále stoupá, jsou známy dobře paralelizovatelné algoritmy. == Konvexní obal množiny bodů v rovině (convex hull) == Konvexní obal ([[https://en.wikipedia.org/wiki/Convex_hull|convex hull]]) množiny bodů si lze jednoduše představit jako nejmenší konvexní mnohoúhelník, uvnitř kterého leží všechny body množiny. Jako konkrétní algoritmus je možné zvolit třeba [[https://en.wikipedia.org/wiki/Quickhull|Quickhull]]. Vstupem pro aplikaci bude textový soubor se souřadnicemi bodů, výstupem pak bude seznam vrcholů konvexního obalu. Doporučujeme si napsat jednoduchý generátor vstupních dat a program či skript pro převod vstupních a výstupních dat do obrázku [[https://cs.wikipedia.org/wiki/Scalable_Vector_Graphics|SVG]] pro snadnou vizualizaci a ověření správnosti řešení. === Kombinatorické problémy === == Knapsack Problem solver == [[https://en.wikipedia.org/wiki/Knapsack_problem|Knapsack problem]] (též známý jako [[https://cs.wikipedia.org/wiki/Probl%C3%A9m_batohu|problém baťohu]]) je NP-těžký problém z kombinatorické optimalizace, který se ale dá překvapivě dobře paralelizovat. Vstupní data doporučujeme generovat o požadované velikosti, aby bylo možné vyzkoušet různé velikosti problémů. Nezapomeňte, že výstupem by měla být nejenom optimální hodnota baťohu, ale i jeho optimální složení. === Word Count souborů === Typický problém s jednoduchou paralelizací. Na vstupu je sada souborů, na výstupu je seřazený výpis obsažených slov a jejich četnost. Krom slov se dají počítat i tzv. [[https://en.wikipedia.org/wiki/N-gram|n-gramy]]. === Autocorrect === Další častý problém. Uživatel něco napíše a my chceme vědět, jestli to opravdu napsat chtěl, nebo jestli se přehmátl na klávesnici. Samozřejmě, bez technologie pro čtení myšlenek to perfektně nejde, ale můžeme porovnat napsané slovo se slovníkem a pokud v něm není, zkusit najít nějaké [[https://en.wikipedia.org/wiki/Levenshtein_distance|blízké]] slovo. Na vstupu je slovník a slovo, nebo celá sada slov. Na výstupu je buďto samotné slovo, nebo množina nejbližších a tudíž pravděpodobně zamýšlených slov. Slovník můžete mít uložený v arbitrárním formátu. ==== Příklad průvodního mailu ==== V příloze je implementace aproximace π za pomocí Monte Carlo simulace. V jedné iteraci je vygenerován náhodný bod z [0, 1]x[0, 1] a zjistí, jestli ten bod spadá do jednotkového kruhu. Po vygenerování N bodů se dá spočítat π jako 4 * / N. Implementace pro jedno vlákno je triviální, vícevláknová implementace pak vydělí množství iterací množstvím spuštěných vláken a nechá každé vlákno provést implementaci pro jedno vlákno. Množství vláken je určeno dle množství jader počítače, jejich synchronizace je triviální, přes atomickou proměnnou. Množství iterací je předáno jako druhý argument. Pokud druhý argument není předán, pak je použita defaultní hodnota 10M iterací. {{:courses:a7b36pjc:internal:velky_ukol.zip|Příloha}} //Pozor, ukázka v příloze je těsně na úrovni zápočtu, ne-li pod ní.// ===== Rady ===== ==== Kompilace programů používající vlákna na Linuxu ==== Pokud pracujete na Linuxu a vidíte chybu s textem podobným ''undefined reference to `pthread_create''', váš program nepůjde zlinkovat pokud kompilátoru nepředáte ''-pthread'', třeba takto: clang++ -std=c++14 -g -Wall -Wextra -pthread main.cpp ==== Kompilace programů používající vlákna v CLion IDE ==== Clion používá ''CMake'' a ''CMakeLists.txt'' pro kontrolu kompilace. Jako kompilátor ale používá buďto ''%%g++%%'' nebo ''Clang'', a tudíž je mu též potřeba říct, aby linkoval vlákna. Nejjednodušší způsob je v ''CMakeLists.txt'' změnit ''set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -std=c++14")'' na ''set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -std=c++14 -pthread")''. ==== Generátor náhodných čísel ==== Pokud potřebujete generátor náhodných čísel a jeho rychlost není až tak důležitá, doporučujeme [[https://en.wikipedia.org/wiki/Mersenne_Twister|Mersenne Twister]] [[http://en.cppreference.com/w/cpp/numeric/random|ze standardní knihovny]]. Minimální příklad použití pro získání double v range (-1000, 1000): double get_random_double() { static std::mt19937 mt{ std::random_device{}() }; static std::uniform_real_distribution<> dist(-1000, 1000); return dist(mt); } Pokud je rychlost velmi důležitá, budete muset použít něco rychlejšího, například [[http://en.cppreference.com/w/cpp/numeric/random|std::minstd_rand]]. ==== Měření uběhnutého času ==== Součástí zadání je porovnat čas běhu vašeho algoritmu využívajícího více vláken, s časem běhu jednoduchého algoritmu, který vlákna nepoužívá. K tomu vám poslouží hlavička '''', která se používá takto: template std::chrono::milliseconds to_ms(TimePoint tp) { return std::chrono::duration_cast(tp); } int main() { auto start = std::chrono::high_resolution_clock::now(); // do work auto end = std::chrono::high_resolution_clock::now(); std::cout << "Needed " << to_ms(end - start).count() << " ms to finish.\n"; }