Search
The English version of the homework assignment is available in the English subject pages structure (there).
Představte si situaci, že jste zaměstnancem počítačové firmy a jste členem týmu, který vyvíjí editor obrázků (Photoshop, Gimp apod.). Aby editor našel své zákazníky musí být dostatečně rychlý a přehledný - jinak neuspěje v konkurenčním boji. Vám byl přidělen úkol implementovat operaci konvoluce do jádra programu. Konvoluce je jednou z nejdůležitějších operací při zpracování digitálního obrazu. Je to ve své podstatě algoritmus, který počítá výsledné pixely jako vážené součty pixelů v jejich okolí. Výpočet se provádí pro každou barevnou složku zvlášť. Vašim dalším úkolem je výpočet histogramu.
Jak funguje konvoluce se můžete podívat i zde: http://setosa.io/ev/image-kernels/
Úkol se odevzdává přes BRUTE.
Vašim domácím úkolem bude implementovat pouze níže uvedenou konvoluční masku pro ostření obrazu, přičemž je žádoucí optimalizovat práci s pamětí a to jakýmkoliv způsobem. Zaměřte se na efektivní práci s cache při použití právě níže uvedené masky.
Pixely na okraji obrázku pouze překopírujte z původního obrázku (=situace kdy konvoluční jádro přesahuje původní obrázek).
Dále pak spočítejte a zapište do souboru histogram zaostřeného obrázku ve stupních šedi. Pro konverzi z RGB do grayscale použijte model pro výpočet jasu: Y = round(0.2126*R + 0.7152*G + 0.0722*B)
Histogram spočítejte pro zleva uzavřený, zprava otevřený interval < i*L/N; (i+1)*L/N ) vyjma posledního intervalu kdy je i zprava uzavřený; pro i=0…N-1, kde L=255 a N=5 je počet intervalů; Jinýmy slovy, interval <0; 255> rozdělte na tyto části:
Vstupní obrázek bude v binárně kódovaném formátu portable pixmap format (PPM). Obrázek uložený v tomto formátu má vždy na začátku souboru uvedeno P6, za kterým následují údaje o šířce a výšce obrázku. Dále konstanta 255 (maximální hodnota intenzity dané složky pixelu) a pak samotná data - jednotlivé RGB složky pro každý pixel. Každá složka pixelu (RGB) zabírá právě jeden Byte.
vit_small.zip vit_normal.zip
Jméno vstupního souboru bude předáno z příkazové řádky – viz parametry funkce main(int argc, char * *argv).
Výstupem Vašeho programu bude zaostřený obrázek v souboru output.ppm a histogram (četnosti jasu oddělené mezerou) v souboru output.txt.
Program, který odevzdáte bude hodnocen z pohledu celkového počtu dotazů do datové L1 cache, do instrukční L1 cache, společné L2 cache (intrukce+data), a především počtu missů na úrovni L1 (datová i instrukční cache) a úrovni L2. Předpokládejte oddělenou instrukční a datovou L1 cache, každá o velikosti 32 KB, 8-cestně asociativní, velikost bloku 64B. Pro L2 cache předpokládejte velikost 1 MB, 16-cetně asociativní, velikost bloku 64B. Algoritmus nahrazování je LRU. L2 cache je inkluzivní (obsahy obou L1 caches jsou i v L2 cache). Váš program by měl být schopen parametry cache detekovat (a přizpůsobovat se jim), nicméně pro účely domácího úkolu je plně postačující optimalizovat Váš program pouze pro výše uváděné hodnoty.
Hodnocení:
Efektivita používáni cache bude hodnocena na základě výkonnosti Vašeho programu.
Cost = AMAT_i*I_refs + AMAT_d*D_refs,
kde
Následně se určí počet bodů za efektivitu dle vztahu:
Body_efektivita = 13*(Cost_Max-Cost)/(Cost_Max - Cost_Min), kde Cost_Min = 1,0 s Cost_Max = 5,0 s.
Pokud by měl získat někdo záporný počet bodů, bude mu za efektivitu přiděleno 0 bodů. Pokud naopak někdo přesáhne 13 bodů, bude mu uděleno právě 13 bodů. Váš program bude testován nad několika různými obrázky (každý o jiné velikosti).
Celkem tedy student může získat 14 bodů za domácí úkol.
Program s algoritmem musí být vytvořený v jazyce C nebo C++ bez použití externích knihoven. Formát obrázku je zvolený tak, aby i jeho načítání bylo možné snadno implementovat na několika řádkách kódu. Program může být optimalizovaný pro překlad na 32 a 64-bitovou architekturu Intel x86. Kompilace a test bude probíhat v podobné prostředí pod OS GNU/Linux, jako je k dispozici v laboratoři na cvičeních.
Odevzdávání domácího úkolu probíhá pomocí upload systému: http://cw.felk.cvut.cz/upload/
Odevzdávejte zazipovaný (z technických důvodů není na upload systému možné odevzdat přímo zdrojový soubor v textové podobě) soubor main.c (v případě, že je vaše řešení v jazyku C), nebo main.cpp (v případě, že je vaše řešení v jazyku C++).
main.c
main.cpp
gcc -mssse3 -g -O1 -Wall -Werror -std=c99 -o main main.c -lm
g++ -mssse3 -g -O1 -Wall -Werror -std=gnu++11 -o main main.cpp -lm
Všechny odevzdané úkoly budou kontrolovány na plagiátorství (všichni zúčastnění budou postiženi stejně, bez rozdílu).
Upozorňení: Soubor output.txt musí obsahovat přesně 5 dekadických čísel. Oddělovačem je mezera. Za posledním číslem nesmí být žádný další znak (ani odřádkování).
Prostředí: debian stretch, gcc 6.3, g++ 6.3, valgrind 3.12
Cena (Cost), ze které vychází hodnocení Vašeho úkolu se velmi dobře odráží v rychlosti běhu Vašeho programu (čím rychlejší program, tím nižší cena). Měřením času tedy můžete velmi snadno zjistit jak je Váš přístup efektivní - jak z pohledu práce s pamětí tak z pohledu algoritmu. Čas lze změrit níže uvedeným způsobem:
#define _POSIX_C_SOURCE 202001L #include <unistd.h> #include <stdio.h> #include <time.h> ... struct timespec start, stop; clock_gettime( CLOCK_REALTIME, &start); ... clock_gettime( CLOCK_REALTIME, &stop); double accum = ( stop.tv_sec - start.tv_sec )*1000.0 + ( stop.tv_nsec - start.tv_nsec )/ 1000000.0; printf( "Time: %.6lf ms\n", accum );
Poznámka: Při kompilaci nezapomeňte -lrt. Příklad: g + + main.cpp -g -lrt
Vyhodnotit jak program pracuje s cahce lze pomocí nástroje cachegrind. Nezapomeňte nastavit parametry cache (–I1=… –D1=… –LL=…), jinak se použijí defaultní hodnoty (nebo hodnoty Vašeho procesoru).
valgrind --tool=cachegrind --I1=32768,8,64 --D1=32768,8,64 --LL=1048576,16,64 ./a.out
Tím získáte základní představu o celkovém chování Vašeho programu. Pokud chcete program analyzovat detailněji, můžete využít nástroje cg_annotate. Příklad:
cg_annotate <filename> ~/domaci_ukol/main.cpp
cg_annotate --auto=yes <filename>
Testovací obrázek 10 x 8