Datové struktury 1

Datové struktury 1 - NTIN066 - ZS 2014/2015

4. úkol

Termín odevzdání: 4. ledna 2015.

Způsob odevzdání: odesláním v příloze emailem na ds1@kam.mff.cuni.cz.

Pravidla

Veškerý odevzdaný kód musí být originální tedy vytvořen vámi bez jakékoliv vedlejší "inspirace".
Svůj kód s nikým nesdílejte, aby se váš kód nestal něčí "inspirací". Výjimku tvoří odevzdání kódu.
Úkol a možné postupy řešení můžete probírat s ostatními, avšak respektuje výše uvedené o nesdílení kódu.
Řešení, která nejsou ve shodě s těmito pravidly, nebudou hodnocená.

Popis problému

Napište program na transpozici matice 1-bytových čísel (char/BYTE/...) triviálním algoritmem a "cache-oblivious" algoritmem. Změřte jejich čas na maticích velikosti 100x100 až 20,000x20,000, výsledek zobrazte do grafu, který pošlete jako součást řešení (ve formátu .png). U "cache-oblivious" algoritmu vyzkoušejte efekt zaříznutí/ukončení rekurze na podmaticích různé velikosti. (Při včasném zaříznutí se overhead na rekurzivní volání funkce rozloží na více prvků, rozmyslete si.) U triviálního algoritmu vyzkoušejte též efekt prohození hlavních dvou for-cyklů.

Velikosti matic: Měření proveďte pro matice velikosti 100 * 1.05^i, kde i=0,...108, máte-li dostatek paměti, pak i pro větší matice. Máte-li naopak nedostatek paměti, pak to vyzkoušejte pro matice, co se vejdou do paměti.
Graf: Zobrazujte čas na prvek, tedy celkový čas transpozice dělený počtem prvků v dané matici (v nano-sekundách). Osu x udělejte v logaritmickém měřítku.
Měření: U malých matic bude čas jedné transpozice prakticky nezměřitelný. Proto je potřeba měřit několik hodně transpozic za sebou. Jelikož nás zajímá chování cache, transponujte postupně matice ležící v různých oblastech paměti, aby při po sobě jdoucích transpozicích už matice nebyly načteny v příslušné cache. Například si alokujte blok paměti cca 500MB, ten rozdělte na matice a transponujte jednu po druhé.
Počítač: Použijte svůj oblíbený počítač, máte-li svůj, pak ten. Jeho parametry zašlete zároveň s výsledky (viz níže).
Kompilace: Pokud to lze, zapněte si optimalizaci kódu.
Možné rozšíření 1: Změřte též chování "cache-aware" algoritmu, který matici transponuje po blocích pevně zvolené velikosti.
Možné rozšíření 2: Vyzkoušejte chování algoritmů na maticích velikosti mocniny dvojky.

Náčrt možných grafů

Doprovodný email

Při odeslání emailu s grafem a zdrojovým kódem, uveďte detaily měření dle následujícího vzoru

Jmeno: Michal Koucky
Pocitac: genericky kancelarsky desktop
CPU: Intel(R) Core(TM) i7-3770 CPU @ 3.40GHz
RAM: 16GB
Jazyk: C++
Nastavení kompilátoru: g++ -ansi -Wall -pedantic -lm -O3
Souhlasim se zverejnenim vysledku na webu: ano
Pseudonym pro zverejneni na webu: XYZ

4. úkol

Pravidla

Popis problému

Náčrt možných grafů

Doprovodný email

Výsledky