Rastislav Krivoš-Belluš
PDS1 - Paralelné a distribuované systémy
1. cvičenie
2. cvičenie
3.-4. cvičenie
CUDA
5. cvičenie
- codes
- TASK: Create program which computes minimum and also maximum in parallel. Every process computes its extremes. Print the intermediate results for each process.
Main process should generate at least 100 four-digit numbers. You can use queue / sublist as argument / map / ...
6. cvičenie
- Cython, Numba - code
- TASK: Measure the time of execution and compute speed-ups:
- primes in Python/Cython
- mandelbrot in Python/Numba
- arraysum in Python/Numba
MPI
- tutorial, python (Win)
- Ďalšie materiály: MPI course material, Parallel Programming in MPI and OpenMP
- Úlohy
- Základné operácie s MPI v Pythone - kód, master-worker
- Implementujte riešenie naplnenia batoha (0-1 Knapsack problem) - generovanie
Domáca úloha (do 29.4.) - generovanie prefixov u Mastera a spracovanie jedného prefixu u Workera a vrátenie medzivýsledku zo všetkých prijatých prefixov. Doplňte riešenie aj o výpis naplnenia batoha pre nájdené maximum. Hodnotenie:
- 2 body za nájdenie maximálnej ceny naplnenia batoha
- 2 body za vypísanie riešenia s maximálnou cenou naplnenia batoha (buď ďalšou komunikáciou so všetkými Workermi, alebo pomocou MAXLOC s INT2)
- 1 bod za spustenie vašej implementácie na clustri zo servera 158.197.31.206 (pds_run | tee du.out)
- Projekty
Vytvorte projekt podľa jedného zadania nižšie. Vaše riešenie musí byť škálovateľné pre rôzne počty procesorov na ktorých bude bežať. Snažte sa o efektívnu komunikáciu - posielať čo najmenší počet správ (a najmenšie množstvo dát). Každé riešenie by malo obsahovať niečo navyše oproti cvičeniu - ďalšie typy komunikácie (Scather, Gather,...), vlastné funkcie (User_function, Op), atď. Majte pripravený popis komunikácie a činností mastera/workera.
- Vyriešte úlohu Ťažisko aj pre dlhšie slová. Otestujte slová prichádzajúce v úvahu, spočítajte ich maximálne vzdialenosti a nájdite minimum s prislúchajúcim slovom.
- Vypočítajte totient čísla, t.j. počet menších s ním nesúdeliteľných čísel. Zároveň vypíšte najmenšie (≥ 2) a najväčšie takéto číslo. Riešenie musí fungovať minimálne pre 18-ciferné čísla (v desiatkovej sústave).
- Simulujte výpočet najkratšej cesty z jedného vrcholu do všetkých ostatných Dijkstrovým algoritmom. Každý worker si pamätá iba časť grafu. Paralelná komunikácia má vybrať ďalší vrchol. Na konci vypíšte spočítané vzdialenosti.
- Implementujte algoritmus ShellSort - preusporiadanie vybranej podpostupnosti, s rôznymi postupnosťami krokov.
- Implementujte základné operácie nad riadkami a stĺpcami matice (súčet, minimum, maximum, počet nenulových) pomocou novo vytvorených komunikátorov - každý proces má len jeden prvok pôvodnej matice.
- Implementujte hru bingo - na začiatku master pošle rozmery hracej plochy a každý proces si vygeneruje vlastný tiket (na jednom tikete sú navzájom rôzne čísla). Následne master generuje čísla a ostatní si škrtajú dané číslo na tikete. Akonáhle niekto má v tikete vyškrtnutý riadok alebo stĺpec zahlási BINGO a hra končí. Master môže priebežne vypisovať počty vyškrtaných čísel, na konci vypísať zoznam výhercov (v prípade viacerých víťazov v danom kole).
© 2023 Rastislav Krivoš-Belluš