AIM - cvičení

V akademickém roce 2024/2025 vede cvičení z předmětu Martina Mareše Algoritmy a jejich implementace (NDMI074) David Čepelík. Tady najdete podmínky pro zápočet, seznam domácích úkolů a seznam probrané látky.

Cvičení je každou středu od 14:00 v SW1.

Cvičícího můžete kontaktovat e-mailem na adrese d@dcepelik.cz. Konzultace je možno domluvit kdykoli osobně nebo e-mailem.

Zadané úkoly

Kód	Zadáno	Termín	Max. bodů	Zadání
bits	31.3.	–	15	Implementujte všechny bitové triky ze cvičení. Odezvdejte prosím e-mailem (d@dcepelik.cz).
eras	31.3.	30.4. 14.5.	15 30	Implementujte Eratosthenovo síto: napište program, který na standardním vstupu obdrží celé kladné číslo N a na standardní výstup vypíše počet prvočísel menších nebo rovných N. N se vejde do 64-bitového int-u. Referenční řešení je silně optimalizované a získá 30 bodů.
mandel	30.4.	30.5.	20	Napište program, který vykreslí Mandelbrotovu množinu. Program dostane poziční argumenty r0 i0 w h step iter a na stdout vypíše PBM (P4) obrázek o šířce w a výšce h, kde pixel na pozici (i, j) je černý tehdy a jen tehdy, když číslo (r0 + i * step) + (i0 - j * step)i patří do Mandelbrotovy množiny. Jinými slovy: r0 + i0i je levý horní roh a obrázek je snímek Mandelbrotovy množiny s hrubostí rastru step. iter je maximální počet iterací posloupnosti; pokud se během iter iterací neprokáže, že poslopunost pro příslušný bod diverguje, pak ji považujeme za konvergentní. w je dělitelné 64. Hint: základní snímek je možno získat s parametry -2 1 2048 1600 0.00125 90. Referenční řešení je přímočará implementace a získá 3 body. 5 bodů. Čas strávený čtením vstupu a výstupu není součástí benchmarku; použijte prosím main.c.
rot90	30.4.	30.5.	20	Napište program, který otočí obrázek o 90 stupňů doprava. Program dostane argumenty in a out, kde in je název vstupního souboru a out je název výstupního souboru. Vstup i výstup jsou ve formátu PBM (P4). Obrázek je čtvercový o straně dělitelné 64. Referenční řešení je naivní a získá 3 body. 5 bodů. Čas strávený čtením vstupu a výstupu není součástí benchmarku; použijte prosím main.c.
sort	30.4.	30.5. 14.6.	20	Napište program, který setřídí posloupnost bezznaménkových 32-bitových čísel. Program dostane argumenty in a out, kde in je název vstupního souboru a out je název výstupního souboru. Referenční řešení je qsort ze standardní knihovny. (Počet bodů referenčního řešení je TBD.) Čas strávený čtením vstupu a výstupu není součástí benchmarku; použijte prosím main.c.

Způsob odezvdávání je popsán níže.

Co se dělo na cvičení

Týden	Datum	Obsah	Materiály, odkazy
1	19.2.	Přednáška na cviku (rychlokurz céčka). Přednáší Martin Mareš.	Medvědův průvodce po Céčku, záznamy z roku 2021
2	26.2.	Přednáška na cviku (rychlokurz céčka). Přednáší Martin Mareš.	Medvědův průvodce po Céčku, záznamy z roku 2021
3	5.3.	Zbytky z rychlokurzu céčka (GNU rozšíření). Užitečné flagy pro kompilátor, Makefile. Valgrind, GDB a asan. Jak odladit crash v GDB, debuginfo. Sekce ELFu. Čtení jednoduchého programu přeloženého s různými flagy (default, -O1, -02, -fomit-frame-pointer, -funroll-loops).	Překládaný program.
4	12.3.	Přednáška místo cvičení. Cvičení si nahradíme 26.3., kdy naopak odpadne přednáška.	Web přednášky
5	19.3.	Cvičení i přednáška odpadá.
6	26.3.	Dvě cvičení v SW1, přednáška odpadá. Dvojkový doplněk. (Signed) přetečení a __builtin_<op>_overflow v GCC, calloc, reallocarray. Šest způsobů, jak spočítat popcount. Který je nejrychleší, kdy a proč? Benchmarkování pomocí clock_gettime(2), na co si dát pozor.	popcnt.c Godbolt Compiler explorer
7	2.4.	Eratosthenovo síto. Naivní iplementace a postupné zrychlování (samostatná práce). Rozmysleli jsme si: Stačí škrtat jen násobky čísel <= ceil(sqrt(n)), není potřeba škrtat tím, co je už škrtnuté. Síto reprezentovat pomocí bitů. Nereprezentovat sudá čísla (tečka tečka). Pracovat v blocích tak, aby aktuálně používaná část síta zůstávala v keši. Pro počítání prvočísel se může hodit jeden bitový trik, který už známe. Použití perf stat -d.	perf-stat(1)
8	9.4.	Zrychlujeme Eratosthenovo síto.
9	16.4.	Vektorová rozšíření. Rychlá orientace. Zrychlujeme naivní programy pomocí ruční vektorizace. Porovnáváme výsledky s naivní verzí a autovektorizací. Zadání úloh.	přehled vektorových instrukcí s obrázky, vektorové typy v gcc, gcc builtins, Intel Intrinsics Guide,
10	23.4.	Kreslení Mandelbrotovy množiny. Individuální pomoc se zrychlováním Eratosthenova síta.	Mandelbrot Set, Netpbm
11	30.4.	Individuální pomoc se zrychlováním domácích úkolů.
12	7.5.	Cvičení odpadá.
13	14.5.	Individuální pomoc se zrychlováním domácích úkolů.

Způsob odevzdání domácích úkolů

• Všem přihlášeným studentům byl vytvořen účet na stroji aim.kam.mff.cuni.cz. K tomuto stroji se můžete připojit pomocí SSH následovně:

  ssh $login@aim.kam.mff.cuni.cz

  Pro přihlášení prosím použijte heslo, které jste obdrželi e-mailem. Poté si heslo změňte a nastavte si key-based authentication.

• Systém pro vyhodnocování úloh je velmi jednoduchý a předpokládá, že ~/submission-repo je Gitový repozitář (může, ale nemusí být bare).

• Systém dále předpokládá, že pro úkol pojmenovaný t existuje adresář ~/submission-repo/t a že spuštění make(1) v tomto adresáři vytvoří spustitelný soubor stejného názvu.

• Příklad: pro odevzdání úkolu eras je zapotřebí vytvořit Gitový repozitář ~/submission-repo/t a commitnout/pushnout do něj řešení v aresáři eras. Adresář musí obsahovat Makefile, např.:

   ~% ssh cepelikd@aim.kam.mff.cuni.cz
   cepelikd@aim:~$ cd submission-repo/
   cepelikd@aim:~/submission-repo$ git status
   On branch master
   nothing to commit, working tree clean
   cepelikd@aim:~/submission-repo$ cd eras
   cepelikd@aim:~/submission-repo/eras$ ls -l
   total 36
   -rw-r--r-- 1 cepelikd cepelikd   190 Apr  9 09:56 Makefile
   -rwx------ 1 cepelikd cepelikd 16416 Apr  9 09:56 eras
   -rw-r--r-- 1 cepelikd cepelikd 11060 Apr  9 09:54 eras.c
   cepelikd@aim:~/submission-repo/eras$ make
   cc -O3 -Wall -march=native -std=c11  -o eras eras.c -lm

• Pro vyhodnocení úkolu stačí zavolat:

   cepelikd@aim:~$ aim eras
   [1/3] Build succeeded
   [2/3] Checks passed
   [3/3] Benchmark executed successfully
   Your mean time was 3.8468996951400003 s
   Your awarded/real score is 30/30 pts

• Počítá se průměrný čas z pěti běhů. Zajímají-li vás detaily, přectěte si prosím, co dělá skript aim.

• Každa úloha má maximální skóre a referenční čas. Skóre se počítá jako:

  score = int((reftime * maxscore + time/2) / time)
  capped_score = int(min(score, maxscore))

  a za řešení, které doběhne, je přiděleno capped_score bodů.

• Pro získání zápočtu stačí v součtu nasbírat 65 % bodů ze všech zadaných úkolů.

• Zatím chybí: systém spustí každou noc vyhodnocování všech odevzdaných úkolů a do ~/submission-repo pushne nové body pro každý odevzdaný task, kterému nevypršel deadline. Pokud jsou pro nějaký úkol body nižší než při předchozím vyhodnocení, ponechá přidělené původní body.

O čem cvičení bude?

Budeme se soustředit na praktické vyzkoušení si a zvládnutí základních technik souvisejících s implementací výpočetně náročných programů - běžné neefektivní a efektivní programátorské obraty ve vnitřních smyčkách, zkoumání možnosti optimalizace překladačem, způsoby a možnosti profilování, různé možnosti paralelizace a možná něco navíc. Snad se dozvíte i pár programátorských zajímavostí.

Zápočet

• Zápočet bude udělen za vypracování domácích úkolů, které budou postupně zadávány.

• Pro získání zápočtu stačí v součtu nasbírat 65 % bodů ze všech zadaných úkolů.

• Protože na začátku semestru jsme se věnovali céčku a následně dvě cvičení odpadla (a budou částečně nahrazena později), s úkoly v tomto akademickém roce začneme o něco později než v minulých letech. Na úlohy bude dostatek času. První úloze byl zrušen deadline a lze ji tedy použít pro dohnání bodů.

• Pokud se na něčem zaseknete nebo nebudete úkoly zvládat nebo stíhat, prosím, ozvěte se.

• Práce na domácích úkolech je individuální, ale diskuse nad řešeními ostatních je vítána. V žádném případě však nepoužívejte cizí kód. Pokud použijete kód, který jste nenapsali, viditelně ho prosím označte.