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:
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
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:
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 pokusuVý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
Doporučujeme vyzkoušet pro každou velikost matice 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ředpokladá, že matice je uložena po řádcích a první řádek začíná na začátku bloku.