Table of Contents

Semestrální práce

Termín odevzdání Nejlépe před 17.05.2024@23:59 CEST
Nejpozději 19.05.2024@23:59 CEST
Základní implementace 10b
Extra funkcionality až 10 bodů
Bonusové funkcionality až 10 bodů
Minimální počet bodů na zápočet 10
Počet uploadů 1 finální verze + případné opravy dle uvážení cvičícího (hodnotitele)
Výchozí implementace b3b36prg-sem.zip včetně referečního řešení obou aplikací
Podpora Video tutoriál k ovládací aplikaci (180 min),
Hints
Při včasném odevzdání (první termín) lze řešit případné nedodělky do termínu finálního odevzdání. Detaily dohodněte se svým cvičícím.
Specifikum práce s pojmenovanou rourou je, že při otevření souboru (roury) pro zápis musí být roura otevřena pro čtení, aby bylo kam případně ukládat data. Proto je volání io_open_write() blokované. Řešením je tak například spustit program výpočetního modulu ./bin/prgsem-comp_module nebo vyčítání roury programem tail -f /tmp/computational_module.in.
Zdůvodu problémů s binární staticky linkovanou spustitelnou aplikací prgsem-main-ref je použita dynamicky linkovaná binárka, která vyžaduje nainstalované knihovny 
linux_vdso.so.1
libSDL2-2.0.so.0
libSDL2_image-2.0.so.0
libc.so.6
libm.so.6
libdl.so.2
libpthread.so.0
librt.so.1
/lib64/ld-linux-x86-64.so.2

— Jan Faigl 2018/05/16 07:26 CEST Aktualizace: Linux binární spustitelný soubor

— Jan Faigl 2017/05/16 05:11 AKDT Aktualizace: Oprava výpočtu RGB složek barevného obrázku.

— Jan Faigl 2017/05/16 09:43 AKDT Aktualizace: Přidána dynamicky linkovaný binárka prgsem-main.dynamic.Linux

— Jan Faigl 2017/05/23 10:43 CEST Aktualizace: Linux verze dynamicky linkovaná na systémové knihovny prgsem-main.Linux, přidání ikony aplikace a funkce pro vyprázdnění fronty zpráv grafického rozhraní.

Podporu používané knihovny SDL nainstalujte ideálně v rámci OS, např. apt install libsdl2-dev libsdl2-image-dev.

Semestrální práce navazuje na implementaci vícevláknové aplikace z cvičení lab09 a 8. a 9. přednášky, kterou rozšiřuje o výpočet fraktálu, který mapuje dynamický systém v části komplexní roviny do 2D obrázku. Konkrétně se jedná o výpočet Juliovy množiny, který je dán rekurzivní rovnicí: $$z_{i+1}= z_i^2 + c,$$ pro kterou vyšetřujeme, zdali pro nějaké zvolené komplexní číslo $c$ posloupnost čísel $z_i$ diverguje či nikoliv. Pro příslušný bod $z_0\in\mathbb{C}$ tak dostáváme posloupnosti hodnot $z_1, z_2, \ldots,z_n$ a říkáme, že bod $z_0$ patří do Juliovy množiny, pokud je posloupnost hodnot $z_1, z_2, \ldots,z_n$ omezená, tj. nediverguje. Test divergence posloupnosti můžeme imperativně otestovat pro zvolený počet prvků posloupnosti $n$ tak, že ověříme, že platí $|z_i|< 2$ pro $0 < i \le n$. Tedy v případě, že absolutní hodnota libovolného komplexního čísla $z_i$ z posloupnosti $z_i\in{z_1, z_n,\ldots, n}$ je větší nebo rovna 2 posloupnost diverguje a bod $z_0$ leží vně Juliovy množiny. Přesnost určení zdali $z_0\in\mathbb{C}$ patří nebo nepatří do Juliovy množiny záleží na počtu testovaných prvků posloupnosti ${z_1, z_2, \ldots, z_n}$. Pro větší hodnoty $n$ může být výpočet náročnější, hodnota ale bude přesnější. Dále můžeme využít hodnotu prvního konkrétního kroku $z_k$, $0<k\le n$, pro který není splněna podmína $|z_k|<2$ využít k obarvení odpovídajícího bodu komplexní roviny a vytvořit tak barevný obrázek Juliovy množiny např.

Uvedený obrázek odpovídá zobrazení části komplexní roviny definované intervaly mezi body $-1.6-1.1j$ a $1.6+1.1j$ na obrázek o rozměru 640$\times$480 pro $c=-0.4 +0.6j$ a $n=60$. Body patřící do Juliovy množiny jsou zobrazeny černě a body, které do množiny nepatří, jsou označeny barvou podle příslušné hodnoty $k$, při které bylo poprvé detekováno, že bod $z_0$ do množiny nepatří, tj. $|z_k|>2$ pro konkrétní $z_0$. Barva je vypočtena po složkách RGB podle

kde $t$ je podíl $k/n$, tj. číslo od 0 do 1.

Nejzajímavější části Juliovy množiny jsou tak její okraje a zmenšením části komplexní roviny, ze které vybíráme komplexní čísla $z_0$ můžeme přibližit okraj např.

Například pro obdélníkový výřez komplexní roviny definovaný body $a,b\in\mathbb{C}$ mapovaný do obrázku s rozlišením $320\times 240$ získáme:

$a=-0.5-0.5j$, $b=0.5+0.5j$ $a=0.01+0.2j$, $b=0.05+0.25j$

V našem případě rozdělíme vlastní výpočet a zobrazení nebo ovládání výpočetu na dvě samostatné aplikace, které spolu komunikují prostřednictvím tzv. pojmenované roury, což je kominkace v podstatě indetická k přesměrovanéhmu standardnímu vstup a výstupu.

Komunikační protokol

Program výpočetního modulu (dále jen Modul) počítá konkrétní část fraktálu podle zadaných parametrů, které jsou zasílány z ovládací aplikace. Vlastní výpočet probíhá tak, že řídicí aplikace zašle zprávu MSG_COMPUTE, která specifikuje část výpočtu tzv. chunk ID (cid). Výchozím bodem obdélníkového výřezu pro výpočet je dán komplexním číslem $re + im j$ a počtem hodnot (sloupců) na reálné ose (z leva do prava) a počtem hodnot (řádku) na imaginární ose (zhora dolů). Krok sloupce a řádku, spolu s hodnotou komplexního čísla $c$ a počtem kroků je součástí zprávy MSG_SET_COMPUTE. Definice jednotlivých zpráv odpovídá definici složeného typu struct message v souboru message.h 

// Definition of the communication messages
typedef enum {
   MSG_OK,               // ack of the received message
   MSG_ERROR,            // report error on the previously received command
   MSG_ABORT,            // abort - from user button or from serial port
   MSG_DONE,             // report the requested work has been done
   MSG_GET_VERSION,      // request version of the firmware
   MSG_VERSION,          // send version of the firmware as major,minor, patch level, e.g., 1.0p1
   MSG_STARTUP,          // init message (id, up to 9 bytes long string, cksum)
   MSG_SET_COMPUTE,      // set computation parameters
   MSG_COMPUTE,          // request computation of a batch of tasks (chunk_id, nbr_tasks)
   MSG_COMPUTE_DATA,     // computed result (chunk_id, result)
   MSG_NBR
} message_type;
 
#define STARTUP_MSG_LEN 9
 
typedef struct {
   uint8_t major;
   uint8_t minor;
   uint8_t patch;
} msg_version;
 
typedef struct {
   uint8_t message[STARTUP_MSG_LEN];
} msg_startup;
 
typedef struct {
   double c_re;  // re (x) part of the c constant in recursive equation
   double c_im;  // im (y) part of the c constant in recursive equation
   double d_re;  // increment in the x-coords
   double d_im;  // increment in the y-coords
   uint8_t n;    // number of iterations per each pixel
} msg_set_compute;
 
typedef struct {
    uint8_t cid; // chunk id
    double re;    // start of the x-coords (real)
    double im;    // start of the y-coords (imaginary)
    uint8_t n_re; // number of cells in x-coords
    uint8_t n_im; // number of cells in y-coords
} msg_compute;
 
typedef struct {
   uint8_t cid;  // chunk id
   uint8_t i_re; // x-coords 
   uint8_t i_im; // y-coords
   uint8_t iter; // number of iterations
} msg_compute_data;
 
typedef struct {
   uint8_t type;   // message type
   union {
      msg_version version;
      msg_startup startup;
      msg_set_compute set_compute;
      msg_compute compute;
      msg_compute_data compute_data;
   } data;
   uint8_t cksum; // message command
} message;

Inicializační zpráva MSG_STARTUP může být například definována jako 

message msg = { .data.startup.message =  { 'P', 'R', 'G', '-', 'S', 'E', 'M', '-', '1' } };
vhodnější je však například zakódovat do zprávy identifikaci autora, např. ČVUT username.

Výměna zpráv a průběh komunikace

V případě zaslání zprávy MSG_SET_COMPUTE nebo i MSG_COMPUTE jsou nastaveny nové hodnoty a výpočet pokračuje podle posledně zadaných hodnot. Kdykoliv (i v případě běžícího výpočtu) je možné si vyžádat verzi firmware Modul zasláním zprávy MSG_GET_VERSION, na kterou Modul promptně odpovídá MSG_VERSION.

Typický průběh komunikace mezi ovládací aplikací (OA) a Modulem může vypadat například následovně:

Z definice zpráv je nutné uvažovat omezený rozsah n_re a n_im zprávy MSG_SET_COMPUTE, který spolu s bajtovou reprezentací c_id udává, jak je možné organizovat výpočet a jak velké obrázky (rozlišení) je možné aplikací počítat. Dále je omezen počet kroků $n$ v rozsahu 8-mi bitového celého kladného čísla (typ uint8_t). Pragmaticky však nemá příliš smysl výpočet pro hodnoty $n$ vyšší než 200.

Výpočetní aplikace

Implementaci výpočetní aplikace lze přímo založit na příkladu vícevláknové aplikace z přednášky, kterou rozšíříme o reakci na zprávu MSG_SET_COMPUTE a MSG_COMPUTE spolu s funkcí pro výpočet části fraktálu pro jednoduchost v základní implementaci realizované jako posloupnost dílčích výpočtů jednotlivých pixelů, které jsou po jednom odesílány zprávami MSG_COMPUTE_DATA.

Ovládací aplikace

Implementaci ovládací aplikace lze také založit na kódu z přednášky b3b36prg-lec09-codes.zip. Aplikace vyčítá hodnoty stiknutých kláves a příslušně reaguje. Výpis stavu aplikace lze jednoduše realizovat textovým výpisem (pro základní implementací semestrální práce). Způsob ovládání není striktně předepsán a záleží na invenci řešení. Může například reagovat na stisk následujících kláves:

V průběhu běhu aplikce může program vypisovat dílčí stavy a události na standardní (chybový) výstup s nějakým jednoduchým rozlišením kategorie typu výpisu např. INFO, DEBUG, WARN, ERROR: 

"ERROR: Cannot open serial port %s\n", serial
"INFO: Create thread '%s' %s\n", threads_names[i], ( r == 0 ? "OK" : "FAIL") 
"INFO: Get version requested\n"
"INFO: Set new computation resolution %dx%d no. of chunks: %d\n", ...
"WARN: New computation parameters requested but it is discarded due to on ongoing computation\n"
"INFO: Set new computation resolution %dx%d no. of chunks: %d\n", ..
"INFO: New computation chunk id: %d for part %d x %d\n", msg.data.compute.cid, msg.data.compute.n_re, msg.data.compute.n_im
"WARN: New computation requested but it is discarded due on ongoing computation\n"
"INFO: Chunk reset request\n"
"WARN: Chunk reset request discarded, it is currently computing\n"
"WARN: Abort requested but it is not computing\n"
"WARN: received grid results is out of range of the current grid"
"ERROR: send_message() does not send all bytes of the message!\n"
"INFO: Module restarted - '%s'\n", str
"INFO: Receive ok from Module\n"
"INFO: Module firmware ver. %d.%d-p%d\n", msg->data.version.major, msg->data.version.minor, msg->data.version.patch
"INFO: Module firmware ver. %d.%d\n", msg->data.version.major, msg->data.version.minor
"WARN: Receive error from Module\n"
"INFO: Abort from Module\n"
"DEBUG: received results %d\n", computation.grid[idx]
"WARN: received grid results is out of range of the current grid"
"WARN: received compute data has cid %d which is different from cid %d - cannot align data to the grid properly\x0a", msg->data.compute_data.cid, computation.cid
"WARN: Module sends new data without computing \n"
"INFO: Module reports the computation is done computing: %d\n", computation.computing
"INFO: Prepare new chunk of data cid: %d\n", msg_send.data.compute.cid
"ERROR: send_message() does not send all bytes of the message!\n"
"INFO: Call join to the thread %s\n", threads_names[i]
"INFO: Joining the thread %s has been %s\n", threads_names[i], (r == 0 ? "OK" : "FAIL")
"INFO: Exit input thread %p\n", pthread_self()
"ERROR: Unknown message type has been received 0x%x\n - '%c'", c, c
"ERROR: Cannot parse message type %d\n", msg_buf[0]
"WARN: the packet has not been received discard what has been read\n"
"ERROR: Cannot receive data from the serial port\n"
"INFO: Exit serial_rx_thread %p\n", pthread_self()
"DEBUG: Write message: "

Vizualizace

Vlastní zobrazení fraktálu lze realizovat s využitím knihovny SDL a pro jednoduchost například s využitím modulu xwin_sdl.zip, který obsahuje pouze tři funkce:

S ohledem na rychlost komunikace je doporučeno v základní implementaci počítat pouze malý obrázek, např. $320\times 240$, pro který může vedle terminálového vstupu okno aplikace vypadat například

Knihovna SDL

Knihovnu SDL je doporučeno použít ve verzi 2, tj. např. sdl2-2.0.5 a potřebné adresáře s hlavičkovými soubory a knihovnami pro linkování přidat prostřednictvím nástroje sdl2-config např. přidat do Makefile: 

CFLAGS+=$(shell sdl2-config --cflags)
LDFLAGS+=$(shell sdl2-config --libs)

Hodnocení

Hodnocení implementace obou částí zadání semestrální práce je složeno ze tří kategorií funkcionalit: základních, dodatečných (extra) a bonusových. Všechny zdrojové kódy je nutné nahrát do odevzdávacího systému BRUTE a to nejpozději k termínu odevzdání. Funkčnost aplikace bude hodnocena na základě uploadovaných souborů. Kromě vlastních funkcionalit je součástí hodnocení také prokázání orientace v kódu. Hodnocení bude provedeno dle časových dispozic hodnotitele a autora/ky semestrální práce, což by ideálně mělo proběhnout v průběhu semestru, nejpozději v posledním výukovém týdnu semestru. Dle časových a prostorových dispozic může dojít k vlastnímu hodnocení až v průběhu zkouškového, proto je pro termín odevzdání rozhodující datum uploadu všech souborů do odevzdávacího systému.

Základní implementace

Základní implementace zahrnuje zejména ovládací aplikaci. Extra funkcionality, například BURST zpráva, vyžaduje úpravu výpočetního modulu (aplikace).

Zvláště hodnocené (extra) funkcionality

Zvláště hodnocené funkcionality podstatným způsobem rozšiřují možnosti aplikace a uživatelského komfortu. Níže uvedený výčet je indikativní spolu s možným bodovým ziskem a představuje vodítko jakým směrem lze aplikaci rozšířit s využitím funkcí a knihoven, které jsou nutné pro realizaci základní verze aplikace. 

// Definice zprávy ''MSG_COMPUTE_DATA_BURST'' může například vypadat
typedef struct {
   uint8_t chunk_id;
   uint16_t length; // number of pixels in the data message
   uint8_t *iters;  // pointer to the array of the compute number of iterations 
                    // particular values of the array are transmitted; thus, 
                    // marshaling and unmarshaling have to be properly handled
                    // together with the proper memory managing
} msg_compute_data_burst; 
 

Maximální počet bodů za povedené dodatečné funkcionality může hodnotitel v odůvodněných případech navýšit v rámci bonusových funkcionalit.

Bonusové funkcionality

Bonusové funkcionality představují významné rozšíření aplikace, které vyžaduje využití dodatečných knihoven nebo mnohem náročnější implementaci a testování než v případě zvláště hodnocených (extra) funkcionalit. Možnostem rozšíření se omezení nekladou, je však nutné zvolit vhodný kompromis mezi nápadem na rozšíření a jeho odpovídající implementací a otestováním, tj. zajímavé nápady, které se nepodaří implementovat a dostatečně otestovat pro uspokojivou uživatelskou zkušenost s aplikací nebudou ohodnoceny tak jako méně ambiciozní, ale za to propracovanější rozšíření.

Příklady možných rozšíření o bonusové funkcionality mohou být následující.