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 8:10-11:20 M218 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 Na pocitaci cvika pribudol subor ~plachetk/pub/proj.txt s poznamkami, ktore som si robil pri citani projektov. Opakujuce sa chyby som komentoval na prednaske, ale mozete sa pozriet ako som komentoval konkretne Vas projekt. Vystupom z kazdeho pthreadoveho 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. Projekty treba odovzdat cez email mne. GOSSIP_ACK. Je N paralelnych procesov, kazdy pozostava z 2 threadov, TS a TR. Kazdy proces (thread TS) posiela M sprav (tzv. PING spravy) dlzky L vsetkym ostatnym procesom (na obsahu sprav nezalezi). Sucasne, proces (thread TR) odpoveda na tieto spravy, ktore priebezne prijal, spravami ACK dlzky L. Sucasne, proces (thread TR) zbiera od ostatnych procesov odpovede ACK. Po tom, co proces poslal a pozbieral vsetky spravy, skonci. Kazdy proces ma jeden vstupny kanal, podobne ako v projekte GOSSIP_SHA. Command-line argumenty: N: argv[1] M: argv[2]; ak M=0, tak procesy posielaju spravy PING bez ohranicenia, az kym nepride nejaky znak z interaktivneho terminalu. Po precitani znaku vsetky procesy musia niekedy skoncit (pricom nie je dolezite aby poslali/precitali rovnaky pocet sprav). Kedze nechceme zahltit system, v pripade M=0 a zaroven T=0 je vhodne "brzdit" procesy v posielani sprav pomocou sleep ci podobnej funkcie. Treba dbat na korektne ukoncenie (proces konci ked uz neposle ziadnu spravu a ked ziadny iny proces neposle spravu do jeho vstupneho kanala). L: argv[3] T: argv[4]: throttle, t.j. horne ohranicenie na rozdiel v pocte odoslanych sprav PING a prijatych odpovedi ACK medzi kazdou dvojicou procesov. Ked sa maximum dosiahne, proces nesmie poslat dalsiu spravu PING (kym neprecita nejaku spravu resp. spravy ACK); ak T=0, proces nie je brzdeny v posielani PING sprav. Deadline: 9.12. (soft), 11.12. (hard) GOSSIP_THR. Tento projekt ma robit presne to, co GOSSIP_OCC, avsak s pouzitim POSIXovej kniznice pthreads (len tej kniznice, plus stdio a stdlib). Deadline: 18.11. (soft), 20.11. (hard) Vystupom z kazdeho CHANoveho 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. Projekty treba odovzdat cez email mne. Pre nastavenie prostredia na pocitaci cvika treba vlozit do ~/.profile nasledujuci riadok: source ~plachetk/pub/CHAN/setup.bash Inspirovat sa da projektami v ~plachetk/pub/CHAN/examples. GOSSIP_OCC. Je N paralelnych procesov. V prvej faze kazdy proces posiela M sprav dlzky L vsetkym ostatnym procesom (na obsahu sprav nezalezi), v druhej faze cita vsetky prichadzajuce spravy, potom skonci. Procesy su spojene kanalmi, ktore sa pouzivaju ako kanaly v OCCAMe (na jednom konci prave jeden proces zapisuje, na druhom konci prave jeden proces cita). Command-line argumenty: N: argv[1] M: argv[2] L: argv[3] Deadline: 8.11. (soft), 13.11. (hard) GOSSIP_SHA. Specifikacia sa zhoduje s GOSSIP_OCC. Rozdiel je v tom, ze kazdy proces ma len jeden vstupny kanal, do ktoreho vsetky ostatne procesy zapisuju. Deadline: 8.11. (soft), 13.11. (hard) 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. OCCAM_LIFE1D_N1. Je N paralelnych procesov zapojenych kanalmi do 1D-torusu ("obojsmerna zacyklena usecka"), kazdy ma pociatocnu hodnotu 0 alebo 1. Program donekonecna bezi iteracie. V kazdej iteracii kazdy z procesov precita hodnoty svojich dvoch susedov a nastavi svoju hodnotu na majoritnu hodnotu zo svojej povodnej hodnoty a tych dvoch susednych hodnot (t.j. vyberie median spomedzi tych 3 cisiel). Deadline: 18.10. (soft), 25.10. (hard) OCCAM_LIFE1D_N2. Je N paralelnych procesov zapojenych kanalmi do 1D-torusu ("obojsmerna zacyklena usecka"), kazdy ma pociatocnu hodnotu 0 alebo 1. Program donekonecna bezi iteracie. V kazdej iteracii kazdy z procesov precita hodnoty svojich 4 susedov (dvoch lavych a dvoch pravych) a nastavi svoju hodnotu na majoritnu hodnotu zo svojej povodnej hodnoty a tych 4 susednych hodnot (t.j. vyberie median spomedzi tych 5 cisiel). Deadline: 18.10. (soft), 25.10. (hard) OCCAM_LIFE2D_N1. Je N paralelnych procesov zapojenych kanalmi do 2D-torusu ("mriezka, obojsmerne zacyklena po riadkoch aj po stlpcoch"), kazdy ma pociatocnu hodnotu 0 alebo 1. Program donekonecna bezi iteracie. V kazdej iteracii kazdy z procesov precita hodnoty svojich 4 susedov (laveho, praveho, horneho a dolneho) a nastavi svoju hodnotu na majoritnu hodnotu zo svojej povodnej hodnoty a tych 4 susednych hodnot (t.j. vyberie median spomedzi tych 5 cisiel). Deadline: 18.10. (soft), 25.10. (hard) Prednaska OCCAM a Transputery. OCCAM je (archaicky) 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, bez 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 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, Dec/10/2013