Datové struktury I - NTIN066 - ZS 2015/2016 - 4. úkol

Termín odevzdání: 22. prosince 2015.
Způsob odevzdání: Odesláním v příloze emailem na ds1@kam.mff.cuni.cz.

Pravidla

Popis problému

Naprogramujte efektivní cache-oblivious algoritmus pro transpozici čtvercové matice N×N, jejíž prvky jsou 32bitová čísla.

Změřte čas na jednu transpozici pro N=64, 69, 75, 80, 87, 92, 101, 109, 119, 128, 139, 150, 161, 174, 189, 203, 220, 237, 256, 280, 300, 322, 352, 378, 406, 442. 476, 512, 552, 598, 645, 705, 760, 812, 878, 960, 1024. Srovnejte s tím, jak dlouho trvá přímočará transpozice podle definice. (Měření provádějte opakovaně tak, abyste dostali spolehlivý výsledek.)

Sepište zprávu, v níž bude:

Odevzdáni

Pošlete e-mail s předmětem tvaru 'HW4-55973318' (t.j. HW4-studentské číslo) s těmito přílohami:

Tělo e-mailu nechť obsahuje údaje podle tohoto vzoru:

Jmeno: Martin Mareš
Pseudonym pro vysledky na webu: Babočka Admirál
Cviceni: pondeli-12:20-lichy

Nepovinné rozšíření úlohy

Pokud vás cache-oblivious algoritmy zaujaly, nabízíme nepovinné pokračování úlohy. 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:

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:

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

Doporučujeme vyzkoušet pro každou velikost matice následující parametry cache:

Velikost bloku [B]Počet blokůVelikost cache [B]
64644096
64102465536
644096262144
512512262144
409664262144

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