Paralelné programovanie

Harmonogram

1. Úvod
2. ―
3. Konzultácie, odovzdávanie zadania 1
4. ―
5. Odovzdávanie zadaní 2, 3
6. ―
7. Konzultácie
8. Odovzdávanie zadaní 5, 6
9. ―
10. Odovzdávanie zadania 7
11. Dodatočné odovzdávanie (v kancelárii cvičiaceho)

Zdroje

• Kniha Metódy a prostriedky pre výkonné paralelné výpočty
• MPI Tutorial
• Nové údajové typy
• API dokumentácia
• Užitočné poznámky k práci s maticami v C

Inštalácia OpenMPI

OpenMPI je implementáciou štandardu MPI určeného pre posielanie správ medzi uzlami paralelného výpočtového systému.

GNU/Linux

Inštalácia OpenMPI je možná pomocou správcu balíkov podľa typu distribúcie, napríklad:

dnf install openmpi openmpi-devel             # Fedora
apt-get install openmpi-bin libopenmpi-dev    # Debian/Ubuntu

V distribúcií Fedora je potrebné pred použitím MPI zadať príkaz, ktorý nastaví cesty k spustiteľným súborom:

module load mpi

Windows

OpenMPI a ďalšie nástroje potrebné pre preklad a spustenie programov môžete nainštalovať pomocou Cygwin. Pri inštalácii Cygwin zvoľte nasledovné doplňujúce balíky:

• libopenmpi-devel
• openmpi
• libopenmpi
• gcc-core

Po inštalácii budete môcť používať Cygwin terminál, v ktorom sú k dispozícii bežné unixové príkazy a tiež príkazy OpenMPI. Adresára systému Windows sú dostupné pod adresárom /cygdrive/, napríklad C:\ je /cygdrive/c/.

Prípadne môžete nainštalovať implementáciu MPI od Microsoft podľa videonávodu.

Kompilácia a spustenie

Kompilácia programu sample1.c:

    mpicc -o sample1 sample1.c

Spustenie programu:

    mpirun -v -np 3 sample1

Príklad

Program pre výpočet priemeru veľkého poľa čísel v klastri neobmedzenej veľkosti.

• Riešenie pomocou priamej komunikácie medzi procesmi
• Riešenie pomocou skupinovej komunikácie
• Príklad zoznamu čísel (prvý riadok je počet záznamov): numbers.txt

Zadania

Špecifikácia formy odovzdávania zadaní. Spracované dáta sa musia čítať zo súboru, zo štandardného vstupu, aleby byť generované. Veľkosť vstupných dát nesmie byť obmedzená. Predpokládajte, že váš program bude spracovávať obrovské množstva údajov (rádov milióny alebo miliárdy). Program má vedieť v maximálnej miere využiť všetky uzly klastra, ktoré má k dispozícií.

Hodnotenie

• 16 bodov: zadania 1, 2, 3, 5/6
• 20 bodov: zadania 1, 2, 3, 5 a 6
• 25 bodov: zadania 1, 2, 3, 5, 6 a 7
• 30 bodov: vysoká kvalita zadaní

1. Paralelné hľadanie maxima čísel

Vstupom programu je rozsiahly zoznam čísel, výstupom maximálna hodnota zo zoznamu.

2. Paralelné transponovanie matice

Pred operáciou transponovania matica musí byť rozdelená medzi viacero procesov tak, že každý proces má k dispozícii niekoľko jej riadkov ▤. Úlohou je dosiahnuť to, aby každý proces mal niekoľko riadkov transponovanej matice (predpokladáme, že ich potrebujú pre ďalšie výpočty).

Časti originálnej matice môžete načítať alebo generovať priamo v jednotlivých procesoch.

3. Paralelné násobenie matíc

Vstupom programu sú dve matice a výstupom je nová matica, ktorá vznikla ich násobením. Veľkosti vstupných matíc musia byť také, aby bolo možné realizovať násobenie.

4. Paralelné vyhľadanie reťazca v neutriedenej tabuľke

Vynechané

5. Paralelné asociatívne ukladanie reťazca do tabuľky

Vstupom je rozsiahla množina dvojíc (kľúč, hodnota). Kľúč aj hodnota sú reťazce. Tieto údaje sa musia uložiť v klastri tak, aby bolo možné neskôr efektívne vyberať hodnoty podľa kľúča. Paralelizujte ukladanie údajov do takejto hash tabuľky.

6. Paralelné vyhľadanie osôb v intervale mien a veku

Programu načíta zo súboru rozsiahlu tabuľku dvojíc: meno, vek. Zo štandardného vstupu sa číta rozsah mien a veku (A–C, 18–25) a výstupom je zoznam vyhovujúcich položiek tabuľky.

7. Paralelné spracovanie dát

Program má realizovať projekciu dát z niektorej z voľne dostupných databáz. Parametre projekcie by sa mali zadávať dynamicky počas behu programu.