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

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

StudentÚlohyCelkem
aktivita gsort popcnt
unique_nickname_42 2 5 7
Jidáš 3 5 8
jirikalvoda 3 3 6 12
user30938 3 3 4 10
tea 3 5 8
Yongaron 1 3 5 9
user32244 1 3 5 9
user21693 1 1
= ^ - ^ = 3 5 8

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. Plán: 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

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

K odevzdávání slouží skript aim-submit. Bez parametrů vypíše nápovědu a úlohy, které lze odevzdat. Také je k dispozici skript aim-test, který spustí pár testů a odhadne počet obdržených bodů. Slouží jen pro orientaci. Kdyby dával řádově špatné výsledky, dejte vědět.

Úlohy odevzdané pomocí aim-submit se vyhodnocují v 5:00 ráno automaticky. Všechny uživatelské procesy jsou zabity, takže si na serveru nenechávejte nic důležitého běžet. Vaše řešení bude zkompilováno dle zadání úlohy a spuštěno samostatně. Počet pokusů o odevzdání není omezen.

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.