AIM - cvičení

V akademickém roce 2022/2023 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.

Úkoly označené (T) jsou teoretické a odevzdávají se e-mailem.

Kód Zadáno Termín Max. bodů Zadání
popcnt (T) 9.3. 22.3. 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, bez použití podmínek a smyček. 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.
abs (T) 9.3. 22.3. 4 Implementujte pomocí bitových triků na co nejméně instrukcí operaci, která spočítá absolutní hodnotu čísla, bez použití podmínek, smyček a porovnávacích operátorů. 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. Předpokládejte reprezentaci ve dvojkovém doplňku a signed shift doprava je aritmetický (kopíruje nejvyšší bit).
gsort (T) 9.3. 22.3. 4 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í záporné číslo, 0, kladné číslo, 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 (T) 9.3. 22.3. 5 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.
eras 30.3. 20.4. 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 30.3. 20.4. 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 27.4. 18.5. 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 27.4. 18.5. 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.

Získané body

Přezdívka abs aktivita eras gsort life mystery popcnt rot90 sort Celkem
44 4 15 4 15 5 5 15 15 78
Bankai 4 11 4 5 5 9 15 53
LEdoian 4 5 11 4 5 5 7 41
máslo 4 3 4 5 5.5 15 4 40.5
skipy 4 5 5 4.5 15 5 6 44.5
tom 4 2 15 5 8 15 49
user0719 6 15 15 15 5 56
user1389 4 5 9
user1592 4 12 2 5 5 15 43
user2186 4 2 2 5 5 18
user2821 4 1 15 5 5 15 45
user2916 4 1 15 4 5 5 15 49
user6818 4 3 14 4 5 5 6 41
user8191 4 1 15 5 5 15 45
user9119 6 6

Co se dělo na cvičení

Týden Datum Obsah Materiály, odkazy
1 16.2. Pokračování přednášky o jazyce C: Výrazy a operátory. Typové konverze. Vedlejší efekty a synchronizační body. Jak číst deklarace: typy, kvalifikátory, incializátory. Medvědův průvodce po Céčku, předloňské záznamy
2 23.2. Pokračování přednášky o jazyce C: Třídy uložení (static a spol.). Funkce a jejich deklarace. Příkazy. Preprocesor a pravidla nahrazování maker. Standardní knihovna. GCCčková rozšíření jazyka. Medvědův průvodce po Céčku, předloňské záznamy
3 2.3. Bitové triky. poznámky
4 9.3. 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, Programování s ohledem na HW (Medvědův úvod do x86), referenční příručka x86 instrukcí
5 16.3. Čtení disassemblovaných programů - pokračování.
6 23.3. Měření rychlosti programů: time, clock_gettime, perf a kdy mu (ne)věřit. příklad s kontrolou zobecněného Sudoku, StackOverflow - stalled cycles, perf tutorial, clock_gettime, pomocné funkce na měření času, generátor cache-missů
7 30.3. Opakování a pokračování z minula. Cachegrind.
8 6.4. Vektorové instrukce: úvod. přehled vektorových instrukcí s obrázky, vektorové typy v gcc, gcc builtins, Intel Intrinsics Guide, aim-measure.h
9 13.4. Vektorové instrukce - opakování a pokračování.
10 20.4. Rešení domácích úkolů. Vzorová řešení vektorových cvičení. vzorová řešení vektorových cvičení
11 27.4. SMP prakticky: vlákna, procesy, fork, sdílená paměť, synchronizační primitiva. příklad fork + sdílená paměť + meziprocesový mutex
12 4.5. SMP prakticky: podmínkové proměnné, atomické operace. Profilování a trasování pomocí bpftrace. referenční příručka atomických operací v C11 bpftrace: příklady ze cvičení, referenční příručka, README, one-linery, ukázkové nástroje z bpftrace distribuce
13 11.5. Plán: dokončení bpftrace, procvičení SMP. Možná něco málo k I/O. generátor grafu
14 18.5. Cvičení odpadá.

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 ve čtvrtek od 17:20 v SW1 (tedy hned po přednášce).

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 ~/.nick 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.