Stahnete si z webu prednasky nastroj machinfo a spustte si ho na svem pocitaci a treba nekolika ruznych pocitacich v labu. Jak jsou radove velke jednotlive caches? Rozumite, jak funguji cache-lines? Co je to cacheline a jak byva velka? Co znamena, kdyz je cache 4-way, a k cemu je to programatorovi dobre? (i) Vymyslete, jak zmerit latenci jednotlivych urovni cache oproti latenci pameti. Zmerte. (ii) Naprogramujte v ramci aim-kitu rotaci obrazku o 90 stupnu. Trivialni implementace je trivialni, pro kazdy pixel v radku je vsak treba pristoupit na jeden bit ve sloupecku, pro zapis (dostatecne sirokeho obrazku) tedy budeme potrebovat tolik cachelines, kolik mame pixelu, coz je dost hrozne. Vymyslete algoritmus, ktery bude pro zapis potrebovat stejne cache missu jako pro cteni. (iii) Rozsirte (ii) tak, aby fungovalo dobre s libovolne velkou cache. Reseni si schovejte, na popristim cviceni jej jeste zparalelizujeme a stane se z nej domaci ukol. :-) Procesor dokaze predikovat, jakou dalsi pamet budeme potrebovat, alespon pokud pamet prochazime sekvencne - provadi pak tzv. prefetching, aby nedochazelo ke zbytecnym cache missum. Prefetching muzeme provadet i manualne pomoci specialnich instrukci - bud pokud do pameti pristupujeme nahodne, nebo treba chceme-li prefetchovat i pres hranici stranky (i kdyz toto pouziti muze byt v praxi ponekud sporne). Jak pouzit onu instrukci? Bud muzeme pouzit gcc builtin, pro moderni instrukce vsak take existuje o neco standardizovanejsi mechanismus (funguje treba i v MSVC++) tzv. "Intel intrinsics". Vice si o nich povime v souvislosti s vektorizaci, kratky recept zde je #include _mm_prefetch(adresa, temporalni_lokalita) (temporalni_lokalita udava, jestli data budeme potrebovat jednorazove, nebo se maji v cache drzet vehementneji, anzto se k nim budeme vracet.) Dalsi otazka je, jestli vubec pro zapisovani radku obrazku plytvat cache, vzhledem k tomu, ze se k datum nebudeme dale vracet. Muzeme pouzit intrinsic _mm_stream_si32() pro tzv. "streamed move", ktery caches obchazi. Pozor, adresa musi byt zarovnana a meli bychom zapisovat sekvencne velke kusy dat. Kdyz uz se bavime o zarovnani - je treba dat pozor, zda bitmapa obrazku je zarovnana na hranici cacheline, jinak se nam chovani vzhledem ke caches znacne zhorsi. Potiz je, ze treba alokace pomoci funkce malloc() _na hranici cacheline nezarovnava_! malloc() si vyzada pamet od operacniho systemu, ktera je pekne zarovnana, pak ale na jeji zacatek vlozi dva pointery (pro interni bookkeeping) a vrati pointer az na ne, takze je cely blok pameti s bitmapou posunuty o 8 resp. 16 bajtu. Je treba v takovych pripadech tedy pouzit radeji funkci posix_memalign(), od ktere si muzeme vyzadat zarovnani, ktere potrebujeme. ---- Hinty a reseni (i) Trva-li pristup do L1 cache 1ns, L2 cache bude okolo 5ns a pristup do hlavni pameti 100ns. (ii) Mohli bychom rozdelit vstupni i vystupni obrazek na dlazdice, ktere se vejdou do L1 cache. Zapis do takovych dlazdic probiha rychle i pri stupidnim kopirovani jednotlivych pixelu. (iii) Co takhle rozdelovat dlazdice na ctvrtiny rekurzivne, od celeho obrazku az po nejakou rozumnou spodni hladinu (treba velikost cacheline)?