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ě.

Přehled studentů a vybraných témat

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.

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 více vlákny / pouze jedním vláknem.
• Bez problémů projít kontrolou nástroji jako je Valgrind, Helgrind, …
• Program musí být přenositelný napříč architekturami a operačními systémy. Je zakázáno používat rozšíření jazyka podporovaná pouze některými kompilátory. Je zakázáno přímo používat rozhraní WINAPI a POSIX. (Zalinkovat knihovnu `pthread` do programu je povoleno, viz níže.)
• Program poskytuje neinteraktivní rozhraní, tj. přebírá vstupy z příkazové řádky, vstupní data ze souboru či ze standardního vstupu
• Program implementuje přepínač --help – vypíše použití a skončí
• Program neakceptuje neznámé přepínače (vypíše chybu)

Semestrální práce se odevzdává přes GitLab a email cvičícímu. Soubory, které odevzdáváte by měly být všechny na fakultním GitLabu, email pak slouží k notifikaci učitele, že jste připraveni semestrálku odevzdat, a kterou verzi (commit hash nebo tag) semestrálky odevzdáváte.

Váš repozitář na GitLabu pak musí obsahovat:

• zdrojové soubory,
• CMakeLists.txt, dle kterého se dá semestrálka postavit
• vzorová vstupní data (pokud je program přijímá)
• Zpráva k vaší semestrálce v souboru Readme
• Povolené formáty pro zprávu jsou: textový dokument, Markdown nebo rozumné PDF
• popis vašeho zadání,
• popis vaší implementace,
• výsledky běhu programu a naměřené časy při porovnání jedno- a více- vláknové verze

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 readme, raději je pište do komentářů v kódu.

Termín odevzdání je konec 3. zkouškového týdne, neděle 3. února 2019. Odevzdání je možné i 4. týden zkouškového období, ale již bude aplikována penalizace ve výšce poloviny bodů z možného bodového maxima.

Za semestrální práci je možné získat až 20 bodů. K získání zápočtu je potřeba z ní získat alespoň 10 bodů.

Za velmi kvalitní práci můžete získat i bonusové body nad běžných 20 bodů.

Připravili jsme pro vás i ukázku zjednodušenné¹⁾ semestrálky. Najdete ji na fakultní instanci GitLabu, zde.

Odpovídající email by pak vypadal zhruba takto:

Dobrý den,

odevzdávám semestrálku "Odhad Pí za pomoci Monte Carlo simulace".
Kód je na https://gitlab.fel.cvut.cz/horenmar/semestralka-priklad, hash
3993960587ec9f54cec7ca0469a2d1b5f9c7ae60.

...

Pokud forknete ukázkový repozitář a nechcete, aby byl váš kód viditelný světu, nastavte Visibility²⁾ na Internal. Pokud budete chtít z pokročilejších vlastností gitlabu využívat merge requesty, bude muset odstranit vztah se zdrojovým repozitářem (Settings → General → Advanced → Remove fork relationship).

Ukázkový repozitář obsahuje i příklad automatizovaných testů (tzv. Continuous Integration), které můžete (ale nemusíte) využít. Pokud forknete ukázkový repozitář, nemělo by být potřeba nic nastavovat. V případě, že si založíte vlastní projekt, musíte přidat tzv. runner (Settings → CI/CD → Runners → Shared runners → Enable shared runners).

Na některých paltformách (například Linux), je potřeba předat kompilátoru -pthread, abyste mohli používat vlákna. CMake to umí zařídit za vás, stačí přidat pár řádků kódu do vašeho CMakeLists.txt:

set(THREADS_PREFER_PTHREAD_FLAG ON)
find_package(Threads REQUIRED)
target_link_libraries(semestralka Threads::Threads)

Kde semestralka je název vašeho programu.

Pokud potřebujete generátor náhodných čísel a jeho rychlost není až tak důležitá, doporučujeme Mersenne Twister ze standardní knihovny. Minimální příklad použití pro získání double v rozsahu (-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 std::minstd_rand.

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 <chrono>, která se používá takto:

template <typename TimePoint>
std::chrono::milliseconds to_ms(TimePoint tp) {
    return std::chrono::duration_cast<std::chrono::milliseconds>(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";
}

Protože se některé chyby při odevzdávání semestrálních prací často opakují, připravili jsme pro vás checklist, kde si můžete zkontrolovat, jestli jste před odevzdáním na něco nezapomněli.

* Kód
  * Obsahuje váš kód CMakeLists.txt přes který se vaše semestrálka dá postavit?
  * Používá váš kód více vláken když má k dispozici více jader?
  * Obsahuje váš kód implementaci optimalizovanou pro jedno vlákno?
  * Nepoužívá váš kód rozšíření jazyka? (Například OpenMP, VLA)
  * Nepoužívá váš kód nepřenosné knihovny (Například POSIX, Win32)
* Měření
  * Proběhlo měření nad optimalizovaným programem? (Byla binárka zkompilována v "Release" módu?)
  * Vyšel běh využívající více vláken rychlejší?
  * Vyšel běh využívající více vláken stejně jako běh v jednom vlákně?
* Zpráva
  * Obsahuje vaše zpráva hash commitu (nebo tag), vůči kterému byla napsaná?
  * Obsahuje vaše zpráva popis zadání?
  * Obsahuje vaše zpráva popis naměřených výsledků?
  * Obsahuje vaše zpráva popis prostředí, ve kterém jste prováděli měření?

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í.

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 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í.

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 Gaussově eliminační mětodě (LU dekompozice). Očekáváme, že váš program bude schopen pracovat s maticemi 1000×1000 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.

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 Gaussovu eliminaci se zpětným dosazením.

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ř.

<počet-vrcholů> <počet-hran>
0 <počet hran z vrcholu 0> <cílový vrchol 1> <délka 1. hrany> <cílový vrchol 2> <délka 2. hrany> ...
1 <počet hran z vrcholu 1> <cílový vrchol 1> <délka 1. hrany> <cílový vrchol 2> <délka 2. hrany> ...
...

Pokud byste si chtěli grafy vizualizovat, je možné použít nástroj dot z toolkitu Graphviz nebo C++ knihovnu OGDF.

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 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.

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 (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 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 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 SVG. Pro snadnou vizualizaci doporučujeme pracovat ve 2D.

Ú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 (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 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 SVG pro snadnou vizualizaci a ověření správnosti řešení.

Knapsack problem (též známý jako problém batohu) 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 batohu, ale i jeho optimální složení.

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. n-gramy.

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é 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 libovolném formátu.