Comenius University > Faculty of Mathematics, Physics and Informatics > Department of Computer Science
Tomas Plachetka

Research Teaching Publications Contact

Paralelne architektury a programovanie Prednaska a praktikum: Pondelok 10:40-14:00 M-201 (2. poschodie, nad studijnym oddelenim), v obdobi vymeny okien M-125 (1.poschodie, nad akvariami) Hodnotenie Nutnou podmienkou uspesneho absolvovania kurzu je priebezna implementacia niekolkych projektov, ktore budu zadane v priebehu semestra. Dalsou castou hodnotenia (s rovnakou vahou) je ustna skuska v skuskovom obdobi. Projekty Ak mate vlastny napad pre projekt, na ktorom by ste radi robili, najskor ho prosim konzultujte so mnou. Projekt LIFE je implementacia animacie LIFE, v Occam2.1. Procesy su kanalmi spojene do 2D-torusu ("mriezka bez okrajov", t.j. mriezka zacyklena po riadkoch aj stlpcoch). Velkost torusu je parameter. Animacia bezi v nekonecnom cykle. Deadline: 31.10. SPRINGERPROBLEM. Alternativou k projektu LIFE (pre zdatnych programatorov) je implementacia programu v Occam2.1, ktory najde vsetky riesenia SPRINGERPROBLEM pre stvorcove sachovnice do 7x7. Velkost sachovnice je parameter, ("VAL BOARDSIZE IS 5 niekde na zaciatku zdrojoveho kodu). Implementovat treba kompletne prehladavanie, bez kombinatorickych optimalizacii. Policko sachovnice je proces, spojeny kanalmi so svojimi "konskymi susedmi". Deadline: 31.10. Vystupom z kazdeho OCCAMoveho projektu je subor s nazvom [project_name].zip, ktory obsahuje subory README (Meno a Priezvisko, specifikacia projektu, poznamky k zaujimavych miestam v implementacii), Makefile, [prog_name].occ. Program musi byt skompilovatelny a spustitelny na pocitaci cvika.dcs.fmph.uniba.sk standardnym KROC kompilatorom (verzia 1.0.3beta). Projekty treba odovzdat cez email mne. Pre nastavenie prostredia na pocitaci cvika treba vlozit do ~/.profile nasledujuce riadky: export KROC_HOME=~plachetk/pub/KROC source ~plachetk/pub/KROC/setup.sh Inspirovat sa da projektami v ~plachetk/pub/OCCAM. Projekt ACP je implementacia programu, ktory simuluje zjednoduseny dvojfazovy Atomic-Commit-Protocol (2ACP), distribuovany (decentralizovany, dvojkolovy) variant. Tento variant je popisany napriklad v tejto knihe, konkretne v kapitole 7, str. 237-238. Zjednodusenie spociva v tom, ze commit kazdej transakcie sa tyka vsetkych N procesov, v systeme nie su vypadky. Kazdy uzol sa chova nasledujucim sposobom: v nahodnych casovych intervaloch [0, START] sekund generuje novu instanciu ACP (bez cakania na ukoncenie predoslych instancii). Po vygenerovani instancie ACP nahodne hlasuje YES s pravdepodobnostou CPROB (inak hlasuje NO). Takto vygenerovany hlas broadcastuje ostatnym procesom. Ostatne procesy po obdrzani spravy YES tiez generuju svoje YES s pravdepodobnostou CPROB a broadcastuju svoj hlas ostatnym procesom. Po obdrzani sprav o hlasovani od vsetkych ostatnych procesov sa proces rozhodne pre COMMIT resp. ABORT (COMMIT rozhodne prave vtedy, ak vsetky hlasy boli YES) a instancia ACP konci. Kedze subezne (nezavisle) bezi viacero instancii ACP, je potrebne ich vediet vzajomne odlisit (tip: kazda sprava je identifikovana dvojicou [rank, counter], kde rank je identifikator procesu, ktory instanciu startuje; counter je lokalna premenna, ktoru ten proces inkrementuje po vygenerovani instancie). Cely program konci vtedy, ked kazdy proces vygeneruje a ukonci NACP instancii ACP. Program ma tesne pred ukoncenim vypisat nasledujuce statistiky (v jednom riadku): N, NACP, START, CPROB, nr_committed, total_time. Reportovat treba (najma) statistiky pre N=1, 2, 4, 8, 16, 32; NACP=1, 10, 100, 1000, 10000, 100000; START=0 (suvisle generovanie instancii ACP, bez pauzy); CPROB=1 (vsetky hlasy vzdy YES). Projekt ACP doporucujem implementovat na pocitaci cvika s pouzitim kniznice CH, ktora je v ~plachetk/pub/CH. Priklady v directory examples demonstruju, ako sa tato kniznica pouziva (konzistentne s prednaskou). Pred pouzitim treba do suboru ~/.profile pridat riadok "export CH_HOME=~plachetk/pub/CH" (bez tych uvodzoviek). Odovzdat treba implementaciu (vratane Makefile) a kratky report s horeuvedenymi statistikami (vratane vhodnych grafov). Pre implementaciu mozete zvolit aj ine prostredie - avsak vtedy nie som ochotny konzultovat ci akceptovat Vase pripadne potiaze s implementaciou (ani v pripade, ze chyba nie je na Vasej strane). Prednaska OCCAM a Transputery. OCCAM je programovaci jazyk navrhnuty ako "takmer-assembler" k procesoru, ktory sa volal Transputer (T414, T800, ...). Transputery sa uz niekolko rokov nevyrabaju, preto ten minuly cas. Mnohe myslienky su vsak dodnes aktualne a neprekonane. Ako doplnujuce citanie k prednaske doporucujem velmi pekny tutorial OCCAMu (Fred Barnes), OCCAM-PI Quick Reference (Peter Welch) a slajdy k prednaske o OCCAM-PI v Kent (Peter Welch). Na programovanie budeme pouzivat KROC (cisty OCCAM 2.1, bez OCCAM-PI rozsireni) na pocitaci cvika. Na vstup a vystup doporucujem pouzit INMOS kniznice. (Niektore funkcie, najma tie na citanie vstupu, nefunguju tak ako sa pise v manualoch; ale sme predsa trosku hackeri a malichernosti vieme obist. Doporucujem jednoduchy workaround: vstupne funkcie vobec nepouzivat, namiesto toho "zadrotovat" vstup priamo do programu, napr. do nejakeho pola, ktore sa inicializuje kdesi na zaciatku programu.) Thready (POSIX). Doplnkovy material. Clanok o kanalovom a point-to-point modeli (Sofsem 2006). Slajdy k clanku. Clanok o load balancing (ITAT 2010). Slajdy k clanku. Dalsie studijne materialy PVM, Parallel Virtual Machine je komunikacna kniznica, ktora bezi pod mnohymi systemami. PVM book sa dobre cita (PDF verzia sa da najst kdekade). Tu je ukazka tutorialu k PVM. MPI, Message Passing Interface je tiez komunikacna kniznica, ktora bezi pod mnohymi systemami. V sucasnosti je podporovana kadejakymi firmami a univerzitami. Aktualna je specifikacia MPI-2.2, lahsie pochopitelna je verzia MPI-1.3. Vyberte si. Za referencnu implementaciu sa povazuje MPICH (Free Portable Implementation of MPI). Hromada tutorialov sa da lahko najst na WWW. Linky INMOS library documentation OCCAM2.1 reference manual KROC: The Kent Retargetable OCCAM Compiler PVM: Parallel Virtual Machine Message Passing Interface (MPI) Forum MPICH (Free Portable Implementation of MPI) Global Grid Forum Updated by Tomas Plachetka, Nov/27/2014