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.	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.

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,

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.