Rastislav Krivoš-Belluš

PDS1 - Paralelné a distribuované systémy

MPI

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.
  1. [Patrícia Szepesiová] 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.
  2. [Patrik Bak] 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).
  3. [Michaela Linková] 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.
  4. [Matej Perejda] Implementujte algoritmus ShellSort - preusporiadanie vybranej podpostupnosti, s rôznymi postupnosťami krokov.
  5. [Dávid Varga] Paralelne vypočítajte viacfarebnú verziu fraktálu Mandelbort - farba závisí od počtu potrebných iterácií.
  6. [Antónia Matisová] Paralelné násobenie dvoch matíc reálnych čísel.
  7. [Marián Kozák] 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.
  8. [Milan Chrastina] Implementujte hru bingo - na začiatku master pošle rozmery hracej plochy a každý proces si vygeneruje vlastný tiket (na jednom tikety 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).
  9. [Peter Chomič] Implementujte paralelný Jacobiho algoritmus na riešenie sústavy rovníc.
  10. [Martina Pivarníková] Implementujte riešenie hry sudoku. Skúšajte iba možnosti skúšajúce všetci kombinácie čísel nepoužitých v danom riadku.