AIM - cvičení

V akademickém roce 2020/2021 vede cvičení z předmětu Martina Mareše Algoritmy a jejich implementace (NDMI074) Filip Štědronský. Tady najdete podmínky pro zápočet, seznam domácích úkolů, i více či méně detailní zpravodajství ze cvičení a odkazy související s tím, o čem budeme zrovna mluvit.

Kontakt

Cvičícího můžete kontaktovat e-mailem na adrese "aim@regn" "arg\056cz" (čtěte jako Céčkový stringový literál). Sem směřujte řešení teoretických domácích úkolů, libovolné otázky a připomínky ke cvičení a probírané látce, případně žádosti o konzultace.

Zadané úkoly

Obecné informace o domácích úkolech, jejich odevzdávání, bodování a podmínkách zápočtu naleznete níže.

Kód Zadáno Termín Max. bodů Zadání
popcnt 23.3. 5.4. 5 Implementujte pomocí bitových triků na co nejméně instrukcí operaci, která spočítá počet jedniček v binárním zápisu čísla. Počet instrukcí může záviset na šířce slova, popište obecné schéma a ukažte řešení (C/pseudokód) např. pro 64bitová čísla. Pokud jste nebyli na cvičení s bitovými triky, řekněte/napište si o podrobnější vysvětlení.
gsort 23.3. 5.4. 3 Na procvičení Céčka a preprocesoru. Implementujte hlavičkový soubor, který vám při includování vyrobí třídící funkci parametrizovanou pomocí následujících maker, která uživatel definuje před includováním: SORT_TYPE - datový typ položek, které se třídí, SORT_KEY(x) pro danou položku x vrátí klíč, podle kterého se bude třídit, nebo SORT_CMP(x,y), který porovná dvě položky a vrátí -1, 0, 1, pokud x<y, x=y, resp. x>y, SORT_PREFIX - prefix názvu výsledné funkce (bude se jmenovat <prefix>_sort). Vždy bude definované právě jedno z maker SORT_CMP a SORT_KEY. Viz příklad použití. Váš hlavičkový soubor by měl fungovat s tímto příkladem beze změny. Můžete použít libovolně hloupý třídící algoritmus, např. InsertSort. Nepředpokládejte nic o tom, jakého typu může být hodnota SORT_KEY(x).
mystery 27.4. 10.5. 17.5. 4 Teoretický úkol: objasněte, co dělá kousek záhadného assembleru. Popište význam jednotlivých registrů, přepište program do ekvivalentního C či pseudokódu, naznačte, které části kódu odpovídají kterým instrukcím assembleru. Program obsahoval chybu, zadání opraveno 11.5. Termín prodloužen do 17.5..
eras 27.4. 17.5. 15 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.
rot90 27.4. 24.5. 15 Implementujte funkci pro otočení obrázku o 90° doprava. Všechny vstupy jsou čtvercové o straně velikosti mocniny dvojky (alespoň 64). Pro přístup k datům obrázku nemusíte (a pravděpodobně nechcete) používat poskytnuté funkce image_getpixel a image_putpixel. Ty slouží hlavně pro ukázku, jinak můžete k paměti obsahující obrázek přistupovat libovolnými prostředky.
life 1.6. 30.9. 15 Implementujte Conwayovu Game of Life na toroidním poli (cyklickém v obou osách – tedy první buňka řádku sousedí s poslední, analogicky pro sloupce). Implementujte funkci exercise, která jako parametr dostane PBM obrázek (stejná struktura jako u rot90) a jako druhý parametr počet generací hry. Výsledek (koncový stav hry po daném počtu generací) zapište in-place do původního obrázku. Pixely s hodnotu 1 (černé) reprezenují živé buňky, s hodnotou 0 (bílé) mrtvé buňky. Můžete použít pouze jedno vlákno/proces.
sort 1.6. 30.9. 15 Implementujte třídění celých čísel z rozsahu 0..2^31-1. Výstup zapište do stejného pole jako vstup. Referenční řešení používá knihovní qsort. Můžete použít pouze jedno vlákno/proces.

Pokud není uvedeno jinak, termín odevzdání úkolů je ve 29:00 (tedy v pět ráno následujícího dne).

Získané body

Přezdívka aktivita eras gsort life mystery popcnt rot90 sort Celkem
= ^ - ^ = 1 12 3 5 21
Jidáš 9 3 4 5 11 15 47
Yongaron 1 15 3 15 5 15 54
jirikalvoda 7 15 3 5 6 15 15 66
tea 15 3 4 5 6 15 48
unique_nickname_42 3 15 5 5 15 43
user21693 2 2
user30938 6 3 3 4 16
user32244 6 15 3 5 5 11 45

Co se dělo na cvičení

Týden Datum Obsah Materiály, odkazy
1 2.3. Cvičení se nekoná, začínáme až 2. týden.
2 9.3. Pokračování výkladu o jazyce C z přednášky: Vedlejší efekty a synchronizační body. Aritmetika s ukazateli. Jak číst deklarace, kvalifikátory (const, volatile, restrict) a třídy uložení (static a spol.). Funkce a jejich deklarace. záznam, tabule
3 16.3. Bitové triky. tabule: PDF, XOPP
4 23.3. Řešení úloh s bitovými triky (doplněno do tabule z minulého cvičení). Jak si pustit disassembler (objdump, jeho parametry a výstup) a jak číst jeho výstup. Ukázky překladu jednoduchých programů. ukázkové programy (na test. stroji: /usr/local/share/aim/asm), online disassembler, syntax highlighter pro vim
5 30.3. Pokračování ve zkoumání assemblerových výstupů překladače. Různé úrovně optimalizace: -O2, -O3 -fno-tree-vectorize (-O3 bez vektorových instrukcí), -funroll-loops. příklady z minula
6 6.4. Optimalizace s ohledem na cache. Měření rychlosti programů. Řešení domácích úkolů popcnt a gsort. příklad s kontrolou zobecněného Sudoku
7 13.4. Pokračování v měření: perf record/report/annotate, cachegrind a další.
8 20.4. Úvod do paralelního programování, základy použití forku, pthreads atp. v Céčku. Několik jednoduchých příkladů.
9 27.4. Domácí úkoly a používání odevzdávacího systému. Drobnosti k paralelismu: debugování deadlocků, overhead atomických instrukcí a synchronizačních primitiv, použití podmínkových proměnných. Okénko pro zajímavost: optimalizace kódu pro čínský stmívač LED pásků.
10 4.5. Trasování a profilování pomocí bpftrace. příklady ze cvičení, referenční příručka, README, one-linery, ukázkové nástroje z bpftrace distribuce
11 11.5. Vektorové instrukce: úvod. přehled vektorových instrukcí s obrázky, vektorové typy v gcc, gcc builtins, Intel Intrinsics Guide, příklady ze cvičení, tabule
12 18.5. Řešení domácího úkolu eras. Vektorové instrukce - pokračování. Maticové násobení.
13 25.5. Řešení domácího úkolu rot90 a mystery. Maticové násobení - pokračování. maticové násobení - kostra

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

Logistika cvičení

Cvičení bude v úterý od 15:40 online na Zoomu (tedy hned po přednášce). Odkaz vám přišel v úvodním e-mailu, ale pokud ho nemáte, ozvěte se.

Většinu praktických věcí si budete zkoušet vzdáleně na testovacím stroji.

Testovací stroj

Účastníci cvičení budou mít k dispozici testovací stroj aim.kam.mff.cuni.cz. Ten bude sloužit hned několika účelům:

Server je přístupný pomocí SSH. Uživatelské jméno je vaše příjmení (malými písmeny, bez diakritiky), heslo brzy obdržíte e-mailem.

Informace o hardwaru testovacího stroje.

Pokud používáte libovolnou rozumnou linuxovou distribuci, SSH klienta pravděpodobně máte nainstalovaného a připojíte se příkazem ssh <jméno>@aim.kam.mff.cuni.cz.

Poznámky pro uživatele Windows

SSH

Pokud používáte Windows, je mnoho způsobů, jak si pořídit SSH klienta. Já osobně doporučuji nainstalovat MSYS2, pustit si MSYS2 terminál, v něm nainstalovat SSH příkazem pacman -S ssh a potom už ho lze používat úplně stejně jako v Linuxu. Alternativou může být nativní OpenSSH klient ve Windows 10, případně program PuTTy.

Pokud potřebujete přenést zdrojové soubory ze svého počítače na AIM server, můžete použít řádkové příkazy scp nebo rsync, případně GUI program WinSCP.

Lokální céčkový kompilátor

MSYS2 se dá použít taky k tomu, abyste si mohli zkompilovat a spustit Céčkové programy lokálně na svém počítači. Kompilátor nainstalujete příkazem:

pacman -S --needed base-devel mingw-w64-x86_64-toolchain

Pak můžete používat příkaz gcc úplně stejně jako na Linuxu.

Podmínky zápočtu

Zápočet bude udělen za získání 40 bodů z domácích úkolů. Podrobněji o úkolech níže.

Pokud nezíská student dostatečný počet bodů, bude mu zadána samostatná práce formou dodatečných úkolů a/nebo zápočtového programu (prakticky efektivní impementace nějakého algoritmu/datové struktury či zefektivnění nějaké existující implementace), rozsahem úměrná množství chybějících bodů. Téma a forma práce je přemětem domluvy mezi studentem a cvičícím.

Účast na cvičení není povinná, ale možná tam občas půjde získat pár bonusových bodů za aktivitu (které se připočítávají k bodům za domácí úkoly, ale k získání zápočtu určitě nebudou potřeba).

Domácí úkoly

Zadání všech domácích úkolů se budou objevovat tady na webu. O každém zadaném úkolu budete infromováni e-mailem. Na řešení každého úkolu bude minimálně 14 dní, ale může být zadáno víc úkolů najednou.

Praktické úkoly

Většina úkolů bude praktická – vaším úkolem je co nejefektivněji naimplementovat v jazyce C řešení daného problému.

Odevzdávací systém

Úkoly se odevzdávají prostřednictvím odevzdávacího systému na testovacím stroji. Začněte tím, že si příkazem aim skeleton <kód-úlohy> vygenerujete kostru řešení. Ta se postará o načtení vstupu a výstupu ve správném formátu a na vás bude jen dopsat samotný výpočet.

Součástí kostry je i Makefile. Můžete tedy příkazem make své řešení zkompilovat. Dále si můžete příkazem make test nechat řešení otestovat v odevzdávacím systému nebo příkazem make submit odevzdat. Řešení se testuje na několika různých testovacích vstupech, některé jsou veřejné (máte je k dispozici v adresáři inputs ve vygenerované kostře, k nim obvykle i odpovídající vzorové výstupy), jiné tajné. Bodování se typicky počítá podle výkonu na posledním (největším) tajném vstupu.

Needitujte žádné soubory kromě <kód-úlohy>.c. U ostatních souborů (Makefile, pomocné .c a .h soubory) použije odevzdávací systém při vyhodnocování vlastní verze a vaše změny bude ignorovat. Pokud máte pocit, že by vašemu řešení výrazně pomohlo nechat ho přeložit s jinými parametry překladače, než jsou výchozí, napište mi.

Většina úloh má omezení na jedno vlákno/proces, pokud není v zadání uvedeno jinak.

Hodnocení

Vaše řešení musí jednak správně odpovědět na několik testovacích vstupů, druhak běžet dostatečně rychle. Každý úkol má zadaný maximální počet bodů, typicky 15. Pro každý úkol též existuje referenční řešení (rozumné, ale nepříliš optiomalizované). Pokud váš program bude stejně rychlý jako referenční řešení, obdrží třetinu maximálního počtu bodů (typicky 5b). Obecně se počet bodů řídí vzorečkem:

score = min(floor(max_score/3 * reftime/yourtime), max_score)

Výsledky obdržíte mailem, veřejná tabulka s body bude k dispozici na této stránce, kde bude každý uveden pod přezdívkou. Ta je zpočátku náhodně vygenerovaná a najdete ji v souboru ~/.nickname na vyhodnocovacím stroji, kde si ji můžete taky změnit (na něco rozumného a unikátního, prosím). Nápověda: <script>while (1) alert('pwned');</script> není vhodná přezdívka ;-).

E-maily z vyhodnocovátka obdržíte na username@aim.kam.mff.cuni.cz. Funguje zde obvyklé doručování e-mailů, takže lze do souboru ~/.forward umístit alternativní adresu, na kterou se maily budou přeposílat. Na začátku máte v tomto souboru svůj e-mail ze SISu.

Odevzdávací systém není ještě úplně stabilní a odladěný. Pokud najdete způsob, jak jej rozbít, oceníme, pokud nám o něm řeknete dříve, než to uděláte :)

Maximální počet bodů za všechny praktické úkoly dohromady bude alespoň 105 (to odpovídá 7 úkolům po 15 bodech, ale možná to bude méně úkolů za víc bodů). Relativně přímočarou aplikací znalostí z přednášky a cvičení by mělo jít získat za většinu úkolů alespoň cca 2/3 bodů, tedy celkem 70.

Teoretické úkoly

Mohou se objevit i doplňkové teoretické úkoly, bodování bude popsáno u jednotlivých úkolů. Teoretické úkoly odevzdávejte e-mailem cvičícímu.