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

Research Teaching Publications Contact

Paralelne architektury a programovanie Zima 2006/2007: Utorok 9:00, III (resp. M218) OCCAM a Transputery Zdielana pamat a synchronizacia threadov (concurrent programming) Message passing: Clanok, Slides Loadbalancing (chunking a farming): Clanok, Slides Ciel projektov Cielom projektu je implementovat a experimentalne otestovat niektoru work-stealing strategiu pre paralelny vypocet konecneho daneho poctu nezavislych uloh (tento pocet oznacme W). To znamena implementovat niektoru verziu work stealing, urobit merania a napisat o tom vsetkom kratky report. Work stealing Casove komplexity taskov je vhodne vygenerovat podla normalneho (gaussovho) rozdelenia N(μ, σ), pricom stredna hodnota a odchylka su dane. Takto vygenerovane komplexity treba ulozit do suboru (a z nich urcit zakladne statistiky, napr. Tmax a Tmin). Striktne algoritmy (chunking, factoring) su popisane v clanku T. Plachetka, Tuning of Algorithms for Independent Task Placement in the Context of Demand-Driven Parallel Ray Tracing. Treba implementovat work-stealing algoritmus, ktory bol popisany na prednaske. Jednoduchsia verzia work-stealing sa robi tak, ze proces ktory nema pracu, robi broadcast na ostatne procesy a od kazdeho dostane 1/N poctu zatial nevypocitanych taskov. Implementacia sa moze spoliehat na znalost W (pocet taskov), N (pocet worker procesov), nesmie sa vsak spoliehat na znalost Tmax a Tmin (a tiez nie μ a σ) v ziadnom z procesov. Latenciu L treba merat priebezne. Vysledok experimentov pozostava z nasledujucich merani: Latencia: priemer, odchylka, minimum a maximum (Lavg, Lstddev, Lmin, Lmax) Efficiency graf pre N={1,2,4,8,16} s funkciami: minimalny ocakavany (teoreticky) makespan Min pre algoritmy chunking, factoring a work-stealing maximalny ocakavany (teoreticky) makespan Mmax pre algoritmy chunking, factoring a work-stealing experimentalne namerany makespan Mexp pre work-stealing Takmer funkcna implementacia work-stealing je v ~plachetk/pub/MPS/src/WORKSTEALING. Nie je v nej korektne urobena synchronizacia threadov a ukoncenie. Tento program doporucujem pouzit ako inspiraciu, avsak vlastnu implementaciu doporucujem napisat od zaciatku. Interface work-stealing programu Command-line parametre programu: <nr_procs> <file> Input file <file>: NR_TASKS MU SIGMA t1 t2 ... tW Output file <file>.<nr_procs>: ALG_NAME N W t_avg t_dev t_min t_max t_cnt L_avg L_dev L_min L_max L_cnt Jazyk a systemy Implementaciu (kodovanie a ladenie) treba robit v jazyku C (nie C++), bud na Parsytec Multicluster, ktory je pripojeny k pocitacu caissa (architektura PARIXT8) a/alebo na PCx86 (architektura LINUX). Architektura PARIXT8 je obzvlast dolezita, lebo v Parsytec Multicluster je 20 procesorov, ktore su vylucne k dispozicii jednej beziacej aplikacii. Toto moze byt problem pre architekturu LINUX (treba k tomu cluster 20 PC s LINUX, ktory je rezervovany vylucne pre jednu beziacu aplikaciu, inak mozu byt experimenty ovplyvnene inymi beziacimi aplikaciami). Experimenty treba urobit pre architekturu PARIXT8. Popis modulov TPL a threads V header file ~plachetk/pub/MPS/include/tpl.h. Work V header file ~plachetk/pub/MPS/include/work.h. Stats V header file ~plachetk/pub/MPS/include/stats.h. Grafy Na kreslenie efficiency grafov doporucujem program GNUPLOT (gnuplot). Tento program predpoklada, ze data su nejakym pravidelnym sposobom organizovane v subore. Ak nemate skusenosti s GNUPLOT, tak pouzite napriklad MS Excel alebo nejaky iny program ktory vie kreslit grafy. Linky Paralelne architektury a programovanie, Zima 2003/2004 (Rastislav Kralovic). 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/12/2007