Cvičení
Napište implementaci Mandelbrotova generátoru s pevným bodem.
a.
Zjistíte, že výkon je nekonzistentní mezi různými pixely a různými snímky. Proč tomu tak je?
b.
Jaká je aritmetická náročnost nejvnitřnějšího těla smyčky v operacích na jeden bajt přístupný z paměti? Jaká je odpovídající hranice výkonu pro váš procesor ARM? Jak se srovnává s vaším pozorovaným výkonem?
c.
Změřte následující výkonnostní metriky pro nejvnitřnější tělo smyčky:
▪
instrukce na iteraci
▪
instrukce na operaci
▪
CPI
▪
cache miss rate
d.
Použijte inline assembler k implementaci nejvnitřnějšího těla smyčky a změřte dopad na výkon s ohledem na metriky z části c. Jaké je zrychlení ve srovnání s kódem generovaným kompilátorem?
Paralelizujte generátor Mandelbrotovy množiny pomocí OpenMP. Použijte direktivu parallel-for na nejvzdálenější (řádkovou) smyčku.
a.
Změřte průměrný počet cyklů potřebných pro každou iteraci nejvnitřnější smyčky (k vyhodnocení polynomu) pro jedno vlákno a dvě vlákna pro počáteční rámec. Pomocí těchto měření vypočítejte zrychlení, vyjádřeno počtem pixelů za sekundu, dvou vláken oproti jednomu vláknu.
b.
Změřte dobu výpočtu všech pixelů v prvním snímku při použití dynamického plánu ve srovnání se statickým plánem.
Co ztěžuje použití operace SIMD pro generátor Mandelbrotovy množiny? Jaký je nejefektivnější způsob použití operace SIMD pro generátor Mandelbrotovy množiny?
Změřte efektivní propustnost zápisu pro linuxový Framebuffer. Je ekvivalentní propustnosti zápisu pro paměťové pole alokované z haldy?
Vypočítejte aritmetickou náročnost programu pro transformaci obrazu v operacích na pixel. Jaká je její výkonnostní hranice vzhledem k efektivní paměťové propustnosti vašeho procesoru ARM? Jak se srovnává s vaším pozorovaným výkonem?
Pomocí OpenMP přidejte do programu pro transformaci obrazu s pevným bodem podporu více jader. K tomu použijte paralelní pragma for na nejvzdálenější (řádkovou) smyčku.
Změřte jeho výkon na čtyřjádrovém procesoru ARM. Jak se měří jeho výkon při provádění s jedním, dvěma, třemi a čtyřmi vlákny?
Pomocí intrinsics přidejte do verze programu pro transformaci obrazu s pevným bodem podporu NEON SIMD. Použijte čtyřcestné operace k výpočtu následujících výpočtů pro skupinu čtyř pixelů: umístění zdrojového pixelu, extrakce zlomku a výpočet váhy. Do jaké míry to zvýší výkonnost?
Program Mandelbrotova generátoru nemůžeme snadno optimalizovat pomocí instrukcí SIMD, protože sousední pixely mohou vyžadovat různý počet vyhodnocení polynomu a každá iterace polynomu je závislá na předchozím vyhodnocení. Alternativním přístupem je implementovat smyčku v inline assembleru, rozbalit ji alespoň po čtyřech a poté použít softwarové pipeliningové propojení ke zlepšení CPI smyčky. V tomto případě bychom se měli vyhnout podmíněným větvením uvnitř unrolované smyčky. Vzhledem k tomu, že rozbíhavé hodnoty c se budou rozbíhat i při dalších vyhodnoceních, můžeme s kontrolou podmínky ukončení smyčky počkat po každé skupině čtyř iterací. Provádění dalších vyhodnocení polynomu po potenciální divergenci Pc() mimo kruh o poloměru 2 však bude vyžadovat, abychom zohlednili dodatečné požadavky na rozsah našeho formátu s pevným bodem. Přepočítejte požadavky na rozsah pevného bodu pro tuto optimalizaci a určete, do jaké míry to sníží maximální úroveň zvětšení.
Zásadními výhodami pevného bodu jsou snížení latence operací a možnost vyhnout se typovým konverzím v určitých typech grafických kódů. Kapitola 2 upozorňuje na příklad programu, jehož výkon je citlivý na latenci operací, Hornerovu metodu. Za předpokladu, že v našem kódu Hornerovy metody můžeme tolerovat omezení rozsahu pevné řádové čárky, zvýšil by se jeho převod na pevnou řádovou čárku výkon? Vysvětlete svou odpověď.
V kapitole 3.6.5 byly ukázány dvě různé implementace zobecněného makra preprocesoru pro sčítání v pevné řádové čárce. První byla vygenerována pomocí gcc při maximální optimalizaci, druhá byla ručně nakódována pomocí inline assembleru. Obě implementace vyžadovaly přibližně stejný počet instrukcí.
a.
Uveďte závislosti dat při čtení a zápisu v obou implementacích. Za předpokladu, že procesor používá jedinou instrukci, v pořadí vydání, a za předpokladu, že latence všech celočíselných aritmetických operací je čtyři cykly, kolik porovnejte počet cyklů zdržení dat potřebných pro obě implementace.
b.
Přepište inline verzi makra pro sčítání v pevné řádové čárce v assembleru tak, aby byly instrukce rozvrženy co nejvíce od sebe. Do jaké míry se sníží prostoje za předpokladu latence uvedené v části a?
c.
Napište kód, který ukáže, jak lze charakterizovat výkonnost všech tří implementací (generované kompilátorem, inline assemblerem a naplánované inline assemblerem).
V této otázce zkoumáme implementaci zobecněného násobení s pevnou řádovou čárkou v inline assembleru popsanou v části 3.6.6.
a.
Jak je na tom z hlediska počtu instrukcí a výkonu za běhu ve srovnání s ekvivalentním kódem generovaným kompilátorem pro:
res = (((long long)op1 * (long long)op2) >> (rp1>rp2?rp1:rp2)) +(rp1>rp2 ? ((((long long)op1 * (long long)op2) >> (rp1-1))&1) :
((((long long)op1 * (long long)op2) >> (rp2-1))&1));
Při kompilaci pomocí gcc nezapomeňte použít přepínače „-O3“ a „-marm“.
b.
Naplánujte instrukce inline verze makra násobení v assembleru tak, abyste minimalizovali zdržení v závislosti na datech. Změřte její výkonnost ve srovnání s verzí uvedenou v části 3.6.6.
c.
Jakého většího výkonu v celé implementaci inline assembleru dosáhneme, pokud ji změníme tak, že pozice radixových bodů budou pevné, a ne proměnné jako v kódu? Pro tuto otázku použijte jak počet instrukcí, tak skutečné chování za běhu. 6.
Výpočet hodnot pixelů pro Mandelbrotovu množinu vyžaduje funkci pro převod počtu iterací na barevné kanály R, G a B.
Vypočítejte hodnoty pixelů pro Mandelbrotovu množinu. Nastavení všech tří kanálů na stejnou hodnotu vytvoří šedý obraz, takže sklon funkce každého barevného kanálu by měl být jedinečný a podle toho, který sklon je největší, se určí odstín obrazu.
Jak je popsáno v části 3.8.1, počet vyhodnocení polynomu může překročit hodnotu, která přesahuje rozsah barevného kanálu. Abyste se vyhnuli možnému přetečení, musíte při výpočtu každé hodnoty pixelu použít sytící aritmetiku. Tímto způsobem, pokud vypočtená hodnota překročí maximální povolenou hodnotu, nastavte ji na maximální hodnotu.
Napište makro jazyka C, které provede 8bitové nepodepsané saturované násobení. Funkce přijme dva 8bitové operandy a vytvoří 8bitový součin nastavený na hodnotu 255, pokud součin překročí hodnotu 255. Makro nesmí obsahovat instrukce větvení a musí být naplánováno na datové závislosti.
Toto cvičení bude zkoumat zvýšení přesnosti typů s pevným bodem pro Mandelbrotův generátor na 64 bitů.
a.
Při použití zvětšení 1,5zoomu, na jakou úroveň lze snímek zvětšit, než se překročí tato přesnost?
b.
Nadefinujte v jazyce C makro pro sčítání dvou (64,56) hodnot s pevným bodem. Makro může provést 128bitové sčítání pomocí čtyř 32bitových sčítanců a použít příznak carry pro implementaci carry z každé 32bitové skupiny do následující nejvýznamnější 32bitové skupiny.
c.
Definice makra v jazyce C pro násobení dvou (64,56) hodnot s pevným bodem. Toto makro sestavte nad makrem 64bitového sčítání z části b.
Jak ukazuje obrázek 3.6, jednoduchý způsob, jak provést 64bitové násobení, je provést sérii čtyř 32bitových operací násobení/posunu/akumulace, z nichž každá dává 64bitový výsledek.
Obrázek 3.6. Osmibitová násobička realizovaná pomocí čtyřbitových násobičů.
Na obrázku jsou dvě čtyřbitové hodnoty A a B držící hodnoty 1110 a 1410 rozděleny každá na dvě dvoubitové horní a dolní části, pojmenované A1, A0 a B1 a B0. Za předpokladu, že součin je 4bitový, vypočítá se 8bitový součin jako (A1*B1) ≪ 4 + (A1*B0) ≪ 2 + (A0*B1) ≪ 2 + (A0*B0).
Chceme-li tento postup použít pro 64bitové násobení, musí být každá ze dvou 64bitových hodnot uložena ve dvou 32bitových registrech. Každé násobení generuje 64bitový výsledek, což umožňuje získat 128bitový konečný součin.
d.
Pomocí těchto maker implementujte 64bitový generátor Mandelbrotovy množiny a změřte výsledný rozdíl ve výkonu.
e.
Implementujte obě makra v inline assembleru a změřte zrychlení výsledku generátoru Mandelbrotovy množiny ve srovnání s výsledkem části d.