Datové struktury I - 4. úkol

Termín odevzdání: 11. prosince 2016.
Způsob odevzdání: Odevzdáním na stránce https://kam.mff.cuni.cz/~ds1/.
Obecná pravidla: Prečtěte si je důkladně

Popis problému

Naprogramujte triviální a efektivní cache-oblivious algoritmy pro transpozici čtvercové matice N×N, jejíž prvky jsou 32bitová čísla. Změřte dobu běhu obou algoritmů na svém počítači a poté použijte náš simulátor idealizované cache k určení počtu výpadků stránek v modelu probíraném na přednášce.

Jak zjistíte z naměřených hodnot, cache-oblivious algoritmus pro transpozici matic má na reálných počítačích pro matice velikosti mocniny dvojky trochu jiné chování než pro obecně velikosti a cílem úkol je pozorovat i tento vliv. Proto vaše implementace cache-oblivious algoritmu musí umět transponovat matice, jejíž velikost není mocninou dvojky. Zároveň nejsou dovoleny žádné triky, které by velikosti matic převedli na mocniny dvojky. Matice musí být uložena jako souvislý blok paměti délky N*N. Transponujte zadanou matici bez použití dalších pomocných matic.

Rekurzivní funkci transponující danou matici lze napsat na zhruba 10 řádků, takže tento úkol může být nejjednodušším, pokud si sami úkol zbytečně nezkomplikujete.

Simulátor cache

Upravte svůj program tak, aby místo prohazování prvků vypisoval na výstup, které prvky se chystá prohodit. Tento výstup pak předejte našemu simulátoru cache, který vám řekne, jak se algoritmus bude chovat pro idealizovanou cache daných parametrů (předpokládáme plnou asociativitu a vyhazování bloků poctivým LRU).

Stáhněte si simulátor a spusťte ho s následujícími parametry:

B – velikost bloku cache;
C – počet bloků cache.

Na standardním vstupu simulátor očekává posloupnost řádků, které popisují průběh transponování matice. Řádky mají následující tvar:

N n – inicializace pro matici n×n
X r₁ s₁ r₂ s₂ – prohození prvků (r₁,s₁) a (r₂,s₂), přičemž souřadnice se číslují od 0 do n-1
E – konec pokusu

Výstupem generátoru bude textový soubor popisující výsledky pokusu:

Elements: počet prvků matice
Accesses: počet přístupů do paměti
Misses: počet bloků načtených z hlavní paměti do cache
Missed-bytes: počet bytů načtených z hlavní paměti do cache

Použijte následující parametry cache:

Velikost bloku [B]	Počet bloků	Velikost cache [B]
64	64	4096
64	1024	65536
64	4096	262144
512	512	262144
4096	64	262144

Simulátor předpokládá, že matice je uložena po řádcích a první řádek začíná na začátku bloku.

Výsledné grafy

Změřte čas na jednu transpozici pro matice NxN, kde N=floor(2^{k/9}) pro k >= 54, 55, 56, ... dokud vám nedojde paměť RAM (v případě simulátoru můžete skončit, když se naměřené hodnoty přestanou výrazně měnit). Měření času na reálném počítači provádějte opakovaně, abyste dostali spolehlivý výsledek.

Ve zprávě:

Srovnejte dobu běhu triviálního a cache-oblivious algoritmu na reálném počítači. Nezapomeňte uvést parametry stroje, na kterém jste měřili (typ procesoru a velikost cache).
Analyzujte, jakým způsobem parametry idealizované cache ovlivňují počet výpadků stránek obou algoritmů na simulátoru idealizované cache. Deset křivek naměřených na simulátoru nakreslete přehledným způsobem.

Všechny grafy by měli znázorňovat průměrnou dobu (počet načtěných bloků) prohození dvou prvků matice v závislosti na velikosti matice, což znamená, že na horizontální ose má být velikost N a na vertikální ose průměrný čas (počet načtěných bloků) na prohození dvou prvků matice.