Cviceni z implementace algoritmu

Ve skolnim roce 2010/2011 vedu cviceni z predmetu Algoritmy a jejich implementace (NDMI074). Tady najdete podminky pro zapocet, seznam domacich ukolu, i vice ci mene detailni zpravodajstvi ze cviceni a odkazy souvisejici s tim, o cem budeme zrovna mluvit. Budete-li mit jakekoliv dotazy ci pripominky, nevahejte nam poslat mail nebo s nami promluvit osobne.

Kdy cviceni bude? Cviceni ma dve paralelky - kazdou stredu od 10:40 v SU1 a nasledne kazde pondeli od 17:20 v SU1. Na cviceni se zapisujte v SISu.

Co od Vas ocekavame? Predpokladame, ze mate ucet v u-labu, umite alespon zaklady C, jiz jste nekdy videli UNIXovou prikazovou radku a snad si i nejaky Cckogram v UNIXu prelozili a spustili.

O cem cviceni bude? Podivejte se na plan nize. Budeme se soustredit na prakticke vyzkouseni si a zvladnuti zakladnich technik souvisejicich s implementaci vypocetne narocnych programu - bezne neefektivni a efektivni programatorske obraty ve vnitrnich smyckach, zkoumani moznosti optimalizace prekladacem, zpusoby a moznosti profilovani, ruzne moznosti paralelizace a zaklady programovani na (skutecnem) GPU; mozna dojde i na uvod do programovani FPGA.

A co zapocet? Dostanete jej za hrstku domacich ukolu a hlavne zapoctovy program. Na zapocet nebude mit vliv dochazka na cviceni (prestoze vrele doporucena).

Za domaci ukoly byste meli nasbirat behem semestru alespon 20 bodu. Ulohy budou spocivat v co nejefektivnejsi implementaci ruznych drobnejsich algoritmu. Presny zpusob bodovani ukolu viz nize. Preteceni ci nedosazeni celkove bodove hranice bude mit vliv na pozadovany rozsah zapoctaku.

Hlavni podminkou zapoctu je zapoctovy program. Ten by mel spocivat v ukazce efektivni zoptimalizovane implementace nejakeho konkretniho algoritmu; inspiraci muzete hledat napriklad na strance predlonske prednasky. Nestaci jen ukazat zdrojak, budeme chtit i komentar o tom, na kterych mistech program travi nejvice casu (a proc), jak jste se pokusili uzka hrdla odstranit a proc si myslite, ze rychleji to jiz nepujde; dalsi mensi diskuse nad zapoctakem bude (krome dotazu na probranou latku) i soucasti zkousky.

Tema zapoctoveho programu byste si meli vybrat do pulky semestru, ocekavam, ze postupne zacnete jeste behem semestru pracovat i na implementaci. Tvrda deadline na odevzdani prvni verze zapoctaku bude zacatek zari, odevzdat finalni verzi zapoctaku byste meli nejpozdeji tyden pred zkouskou, abychom meli dostatecne casove buffery. Pocitejte s tim, ze v prubehu srpna budu mozna na mailu pomerne zridka.

Domaci ukoly

Za ukol mate (zhruba) do 14 dnu od zadani co nejefektivneji naimplementovat v jazyce C reseni daneho problemu. Vase reseni musi jednak spravne odpovedet na nekolik testovacich vstupu, druhak bezet dostatecne rychle. Pro kazdy ukol je v systemu schovana rozumne implementovana (ale neprilis zoptimalizovana) referencni implementace; pobezite-li stejne rychle, dostanete 5b, pobezite-li pomaleji/rychleji, dostanete od 1b do 15b:

score = min(floor(5 * reftime/yourtime), 15)

[an error occurred while processing this directive]

Reseni posilejte na e-mailovou adresu aim@kam.mff.cuni.cz; v subjectu uvedte pouze identifikator ukolu a v tele mailu pouze kod reseni. Napriklad v UNIXu prikazem cat zdrojak.c | mail -s kod aim@kam.mff.cuni.cz (s ruznymi privesky, ktere muze generovat treba Vas webmail, se zatim nevyrovname, klidne to z nej vsak alespon zkuste).

Do nekolika minut byste meli dostat zpet informaci o vysledcich. Zatim je nas vyhodnocovaci robot spise v testovacim provozu, takze kdyz se Vam nebude neco zdat, nevahejte se ozvat na aim@ucw.cz (to ctou skutecni lide).

Vase reseni budeme merit prelozene gcc-4.4.5 -O3 -march=native -std=gnu99 na 6x AMD Phenom(tm) II X6 1090T.

Reseni uzavrenych ukolu. (Pokud zatim v adresari reseni daneho ukolu zadne neni, muzete stale ziskavat body!)

Aktualni vysledky:

StudentPrikladyBodu
"Adam Juraszek" <juraszea@...> eras(15:6.50) lone(15:0.39975) 30
"Dominik Taborsky" <taborskd@...> eras(9) wave(12) 21
"Jakub Hajic" <j.hajic@...> eras(15:5.53) wave(11) 26
"Jan Benes" <benej5am@...> lone(10) wave(15:0.2295) 25
"Jan Tomasek" <tomasek.jan@...> eras(15:6.31) lone(2) wave(15:0.20075) 32
"Petr Fejfar" <fejfarp@...> eras(11) 11
"Roman Kucera" <kucer6am@...> eras(15:5.45) lone(15:0.362) pixr(14) wave(4) 48
"Stepan Havranek" <havranek.stepan@...> eras(15:6.58) 15
"Vaclav Obrazek" <obrazev@...> eras(14) lone(6) wave(2) 22
=?ISO-8859-1?Q?KarelKr=E1l?= <kralkareliv@...> eras(15:5.13) pixr(3) wave(4) 22
=?UTF-8?Q?Ond=C5=99ejMajerech?= <oxyd.oxyd@...> eras(13) 13
Martin Pelikan <pelikan@...> pixr(12) 12
Ondrej Majerech <oxyd.oxyd@...> pixr(7) 7
Petr Baudis <pasky@...> eras(6) ir90(5) lone(8) pixr(7) wave(8) 34
pasky@... wave(4) 4
tauferp@... eras(15:5.04) lone(15:0.31525) wave(15:0.1945) 45

Zapoctak jiz zdarne odevzdali: Kuba Marek, Martin Liska, David Slaby, Petr Junos, Jindrich Ivanek, Jitka Novotna, Petr Babicka.

Novinky ze cviceni

Plan predbezny, mozna neco pribude, neco mozna zase zmizi, prehodime poradi, ... Body kursivou nemuseji 1:1 odpovidat jednotlivym tydnum.

  1. Propojeni prvnich dvou prednasek - povidani o tajuplnych zakoutich C.
  2. Prakticke osvezeni jazyka C (Erastothenovo sito). Hratky s preprocesorem (tvorba praktickych maker).
  3. Rozjimani nad binarni reprezentaci cisel; bitove masky, efektivni zjistovani zajimavych vlastnosti.
  4. Bitmapove obrazky, predstaveni AIM kitu (test16384), benchmarkovaci minimum.
  5. Trapeni se s assemblerem.
  6. Kratky navrat k assembleru. Hledani obrysu v obrazku. Prvni zkoumani efektu ruznych switchiku.
  7. Uvod do profilovani a profile-driven optimalizaci (ondrej-eras.c, wave-pasky.c). -fprofile-generate + -fprofile-use, -ggdb3, -pg + gprof, valgrind --tool=callgrind + kcachegrind, oprof_start + opreport/opannotate, perf record + perf report/annotate.
  8. Profilovani v praxi, experimenty s Erastothenovym sitem. Rotace obrazku, strategie pristupu do pameti vzhledem ke cachim.
  9. Rotace obrazku; strategie pristupu do pameti podruhe, trocha paralelizace.
  10. Hammingova vzdalenost: Vektorizace, paralelizace. (noise1024.pbm, noise16384.pbm; explicitne zvektorizovano - ale stale neoptimalni)
  11. Pocitani na GPU, OpenCL. kostricka.
  12. Mezihra (bonus na rektorsky den) - fraktaly, principy a/v ditheringu; barevny AIM kit, interaktivni AIM kit.
  13. libucw, diskuse o probrane latce, pokracovani pocitani na GPU.

Edituje Petr Baudis. No counters, no frames, no syntax errors. Design borrowed from MJ.