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×nX r1 s1 r2 s2
– prohození prvků (r1,s1) a (r2,s2), přičemž souřadnice se číslují od 0 do n-1E
– 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.