Algoritmy a jejich implementace - cvičení

V akademickém roce 2018/2019 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

Dotazy a připomínky směřujte na adresu "aim@regn" "arg\x2ecz" (čtěte jako Cčkový stringový literál).

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ódTermínMax.
bodů
Zadání
test0Na této úloze si můžete vyzkoušet odevzdávání praktických úloh. Napište program, který na výstup vypíše Hello world!.
eras9.4.15 Implementujte Eratosthenovo síto: napište program, který jako parametr příkazového řádku obdrží kladné celé číslo N a na standardní výstup vypíše počet prvočísel menších nebo rovných N. N se vejde do 32-bitového int-u.
popcnt9.4.5 Teoretický úkol. 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í.
rot907.5.15 Implementujte v rámci aim-kitu funkci pro otočení obrázku o 90° doprava. Podrobnější pokyny pro zacházení s aim-kitem najdete v jeho README. 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.
prot907.5.14.5.15 Paralelní verze předchozí úlohy: můžete použít více vláken. Všechny vstupy jsou čtvercové o straně, která je násobkem 1024, ale nemusí být mocninou dvojky.
sort25.9.15 Implementujte v rámci frameworku aim-sort funkci pro třídění 32-bitových int-ů. Odevzdává se jen soubor exercise.c s funkcí exercise. Výstup uložte do pole, ve kterém jste dostali vstup. Nepoužívejte vlákna. Velikost pole nemusí být mocnina dvojky ani násobek žádného hezkého čísla.
psort25.9.15 Paralelní verze předchozí úlohy. Liší se pouze dovolením používat vlákna a přísnějším bodováním.

Získané body

StudentÚlohyCelkem
aktivita eras popcnt prot90 psort rot90 sort test
ML 8 0 (OK) 8
user-1 5 5
meggy 4 3 7
user11 2 0 (OK) 2
martin 15 (22) 10 15 40
hrubon 2 15 (18) 17
vasek 4 15 (23) 7 15 (17) 15 (34) 56
dac 15 (67) 13 15 (30) 43
pali 3 15 (19) 3 11 15 0 (OK) 47
user4 2 2
rzikm 2 15 (19) 5 15 (16) 15 (32) 52

Co se dělo na cvičení

TýdenDatumObsah
120.2.Cvičení se nekoná, začínáme až 2. týden.
227.2.Jazyk C: aritmetické a bitové operátory, konverze číselných typů.
36.3.Jazyk C: preprocesor.
413.3.Jazyk C: standardní knihovna, atributy, rozšíření.
520.3.Bitové triky: násobení, dělení, zaokrouhlování na mocniny dvojky, absolutní hodnota, signum, nejpravější jedničkový bit, hrátky s XORem.
627.3.Hrátky s disassemblerem: jaký kód vygeneruje překladač pro jednoduché programy? Jak disassemblovat a jak číst disassemblovaný kód. Různé optimalizace a volby překladače a jejich vliv na vygenerovaný kód. Příklady. Webový disassembler.
73.4.Disassembler: řešení hádanek z minula. Zajímavé optimalizace: dělení pomocí násobení, common subexpression ellimination, loop-invariant code motion, převod smyček na smyčky s podmínkou na konci, udržování mezivýsledků v registrech. Perf: základní použití, zajímavé události, počítání cache misses na různých úrovních cache. Příklad se součtem matice po řádcích a po sloupcích.
1315.5.Vektorové instrukce - úvod. Odkazy: x86 and amd64 instruction reference, gcc built-ins (hledejte ve stránce '-msse' a '-mavx'), Intel intrinsics

Kdy a kde je cvičení?

Letos cvičení probíhá každou středu v 17:20 v učebně SU1.

Co od Vás očekáváme?

Předpokládáme, že máte účet v labu a již jste někdy viděli UNIXovou příkazovou řádku. Zbytek vás zkusíme naučit.

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

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 testování a vyhodnocování vašich řešení slouží stroj aim.kam.mff.cuni.cz přístupný pomocí SSH. Uživatelské jméno je vaše příjmení (malými písmeny, bez diakritiky), heslo jste obdrželi 23.3. na e-mail, který máte uvedený v SISu. Pokud máte problém s přihlášením, ozvěte se nám mailem nebo osobně na cvičení.

Informace o hardwaru testovacího stroje.

Pokud jste to již neudělali, změňte si své heslo pomocí příkazu passwd. Pro větší pohodlí doporučujeme nahrát si na server SSH klíč, ale i v takovém případě heslo změňte.

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.