Warning
This page is located in archive. Go to the latest version of this course pages. Go the latest version of this page.

Semestrálka: Implementace vybraného algoritmu

Obecné požadavky

Všechny odevzdané práce musí obsahovat implementaci alespoň dvou algoritmů, které lze mezi sebou porovnat! Vzájemné porovnání dvou nebo více algoritmů je nutnou podmínkou pro úspěšné odevzdání tohoto typu semestrální práce.

Dvěma algoritmy rozumíme dva různé algoritmy, které řeší vybranou úlohu, tj. například Kruskalův a Borůvkův algoritmus pro hledání minimální kostry grafu apod. Porovnat lze i algoritmus s jeho paralelní verzí (vyžaduje implementaci algoritmu s více vlákny).

Práce tedy musí obsahovat

  • Implementace dvou vybraných algoritmů, resp. implementaci algoritmu a jeho verze s více vlákny. Za implementaci s více vlákny jsou body navíc (až 10 bodů).
  • Vzájemné srovnání vytvořených implementací.
    • Mezi oběma implementacemi jde volit pomocí přepínače na příkazové řádce.
    • 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 - musí se jednat o dva nezávislé algoritmy (funkce).
  • 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)
Téma semestrální práce je nutné sdělit svému cvičícímu prostřednictvím emailu. Ve zprávě uvádějte dva algoritmy, které budete srovnávat. Cvičící musí téma semestrální práce schválit!

Ukázka

Připravili jsme pro vás i ukázku zjednodušenné1) 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 Visibility2) 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).

Rady

Kompilace programů používající vlákna

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.

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

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 <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";
}

Vzájemné srovnání algoritmů

Po implementaci vybraných algoritmů je nutné jejich vzájemné srovnání. Kromě obecně známých informací o odhadu složitosti jednotlivých algoritmů je vyžadováno spustění a ověření programu na datech různé velikosti. Toto srovnání může vypadat následovně:

Měření proběhlo vůči kódu v commitu 3b11aea8, na 4 jádrovém i5-6600K CPU taktovaném na 3.5 GHz a s vypnutým HT. Pro měření jsem vygeneroval různě dlouhá pole celých čísel z intervalu <0..10000>. Ta jsem použil pro vstup jednotlivých algoritmů, výsledky dokumentuje tabulka. Údaje uvádím v sekundách.
Délka pole Lomuto partition Hoare partition
100 0,0 0,0
500 0,00099921 0,00199866
1000 0,00300288 0,00199914
5000 0,01797986 0,01798939
10000 0,03796839 0,03796839
15000 0,05896711 0,05994868
20000 0,07994461 0,07995605
100000 0,48772454 0,48171043
200000 1,20131588 1,09439635
300000 1,72402358 1,86994743
400000 2,47061443 2,42162227
500000 3,36009430 2,89037346
600000 4,38851475 3,54099583
700000 4,91222858 4,51444339
800000 5,62383914 5,19805741
900000 7,69166803 5,82771778
1000000 7,73164129 6,54229474
2000000 19,29710865 13,09317827
3000000 34,51442599 21,1949904
4000000 49,58403111 29,57823801
5000000 72,67411804 37,41981435
6000000 94,05696487 45,6716814
7000000 123,5082402 52,14940238
8000000 152,3045919 59,92702675
9000000 198,8918958 74,84251451
10000000 229,5724194 78,05080032

Výsledky jsou znázorněny v grafu:

 Srovnávací graf

Pro posloupnosti s délkou menší než milión prvků nezáleží na použíté partícii. Pro delší posloupnosti se ukazuje výhodnější využít Hoare partície, výsledky jsou minimálně o polovinu lepší.

Vybraná vstupní data (cca 5-10 příkladů vstupních dat) je nutné připojit k odevzdávanému projektu pro kontrolu.

Checklist pro odevzdá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?
  * Obsahuje váš kód implementaci optimalizovanou pro jedno vlákno?
  * Je implementována nápověda (argument programu --help)?
* Práce s vlákny pro vyšší bodové hodnocení
  * Používá váš kód více vláken když má k dispozici více jader?
  * Nepoužívá váš kód rozšíření jazyka? (Například OpenMP, VLA)
  * Nepoužívá váš kód nepřenosné knihovny (Například POSIX, Win32, filesystem)
* 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í?

Před odevzdáním práce si pozorně projděte Checklist. Odevzdáním práce se dílo považuje za hotové a jeho delší opravy za účelem většího bodového zisku či z jiných důvodů jsou možné pouze po svolení cvičícího.

Šuplíkové 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 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.


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

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


Barvení grafů

Barvení grafů se stalo známým hlavně problémem minimálního obarvování politických map, který se dlouho nedařilo vyřešit. Poměrně snadno se povedlo ukázat, že na obarvení libovolné politické mapy tak, aby žádné dva sousedící státy nebyly obarveny stejnou barvou postačuje pět barev. Dnes je dokázáno, že stačí pouze čtyři barvy. Pro barvení grafů lze využít nejrůznější algoritmy, některé z nich využívají i paralelní přístup.


Problém obchodního cestujícího

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 (clustering)

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.

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


Výpočet obsahu mnohoúhelníku

Planární triangulace umožňuje rozdělit mnohoúhelník na trojúhelníky, jejichž obsah dokážeme vypočíst pomocí vektorového součinu.

Kombinatorické problémy

Knapsack Problem solver

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

Práce s dlouhými řetězci

Vyhledání podřetězce v řetězci

Když se pokusíme o vyhledání dlouhého řetězce (10000 a víc znaků) v dlouhém řetězce pomocí knihovní funkce std::find(), operace chvilku trvá. Proces lze urychlit využitím vhodného algoritmu. V roce 1976 byl představen https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm}Knuth-Morris-Pratt algoritmus, který díky vhodnému předzpracování dokáže proces vyhledání podřetězců urychlit.


Komprese řetězců

Řetězce jsou standardně ukládány po jednotlivých znacích - bajtech. Pokud chceme šetřit pamětí, lze podle typu řetězce a znaků, které se v řetězci vyskytují, omezit počet bitů potřebných na uložení řetězce. Například pokud se řetězec skládá pouze ze znaků a a b, lze na uložení každého znaku využít pouze 1 bit - jeho hodnota bude 0 pro znak a a 1 pro znak b. Na to slouží Huffmanovo kódování. Vytvoření kódu umožní řetězec zakódovat a uložit v komprimované podobě a také ho zpětně dekódovat a zprávu si přečíst.

1)
Takto triviální zadání bychom nepřijali.
2)
Settings → General → Permissions
courses/b6b36pcc/ukoly/sem_tvoralgr.txt · Last modified: 2023/12/13 14:50 by nagyoing