# OpenMP #### Lukáš Havrišák #### & #### Tara Stefányi Ing. Eva Chovancová PhD.

#### API špecifikácia pre paralelné programovanie Nezávislé od platformy Note: OpenMP je nie knižnica. Ide o API špecifikáciu, ktorá definuje syntax a sémantiku príkazov pre paralelné programovanie.

#### Konkrétna implementácia je súčasťou alebo rozšírením prekladača C/C++, Fortran Note: Konkrétna implementácia tejto špecifikácie je zvyčajne súčasťou prekladača (alebo nejakého rozšírenia).

### `-fopenmp` `gcc -fopenmp main.c -o main` ## + ### `#include <omp.h>` ##### (hlavne pre OS Windows) Note: My sme naše úlohy riešili v jazyku C, a preto sa budeme zaoberať iba týmto jazykom a prekladačom GCC. Ak chceme zapnúť podporu OpenMP pre náš program, je potrebné pri preklade použiť prepínač `-fopenmp`. Taktiež je potrebné v zdrojových súboroch pridať knižnicu `omp.h`.

#### `#pragma omp parallel [num_threads(n)]` ##### Nasledujúci blok bude vykonaný paralelne v `n` vláknach ``` int main() { #pragma omp parallel num_threads(4) { printf("Hello from thread %d\n", omp_get_thread_num()); } return 0; } ``` Note: V OpenMP namiesto funkcií používame `#pragma omp` konštrukcie (podobne ako `#define` alebo `#include`). Základným príkazom `#pragma omp parallel` vieme definovať paralelné vykonávanie bloku. Na určenie počtu vlákien použijeme nepovinný parameter `num_threads`. V prípade, ak počet vlákien nezadáme, OpenMP zvolí vhodný počet samo (zvyčajne počet jadier). Pozor: Je dôležité, aby otváracia zátvorka bloku bola na novom riadku (nie v riadku, kde sa nachádza `#pragma`).

#### `#pragma omp for` ##### Rozdelí iterácie cyklu medzi vlákna ``` int main() { #pragma omp parallel num_threads(2) { #pragma omp for for (int i = 0; i < 5; i++) { printf("i = %d in thread %d\n", i, omp_get_thread_num()); } } return 0; } ``` Note: Ďalším dôležitým príkazom je `#pragma omp for`, ktorým dosiahneme to, aby sa iterácie nasledujúceho `for` cyklu rozdelili medzi vlákna. Teda nebude každé vlákno vykonávať tento cyklus samostatne. Avšak na to je potrebné, aby sa tento príkaz nachádza vnútri paralelného bloku (ako je možné vidieť na uvedenom fragmente).

#### `#pragma omp parallel for` ``` int main() { #pragma omp parallel for num_threads(2) for (int i = 0; i < 5; i++) { printf("i = %d in thread %d\n", i, omp_get_thread_num()); } return 0; } ``` Note: Výraz `#pragma omp parallel for` je iba skrátený zápis predchádzajúcich dvoch.

#### `#pragma omp parallel private(v)` ##### Každé vlákno si urobí lokálnu kópiu premennej `v`, s ktorou bude pracovať Note: Pomocou prametra `private` spolu s názvom premennej vieme definovať premennú, ktorej kópiu si každé vlákno urobí. Následne bude vlákno pracovať s touto kópiou. Pozor: Skopíruje sa iba deklarácia premennej, nie jej globálna hodnota.

#### `#pragma omp parallel for reduction(o:v)` ##### 1. Každé vlákno si urobí lokálnu kópiu premennej `v` ##### 2. Na konci cyklu sa lokálne kópie atomicky zlúčia do pôvodnej premmennej použitím operácie `o` +, -, *, min, max,... Note: Pomocou parametra `reduction` vieme dosiahnuť podobný efekt ako funkcia `fold` vo funkcionálnych jazykoch. Na začiatku cyklu pralelného bloku si každé vlákno urobí lokálnu kópiu premennej (podobne ako `private`) a inicializuje ju. Na konci cyklu sa lokálne premenné z každého vlákna ATOMICKY zlúčia do pôvodnej premennej použitím zadanej operácie. Ako operáciu možeme použiť napríklad sčítanie, násobenie, ale aj maximum alebo minumum.

``` int factorial(int number) { int fac = 1; #pragma omp parallel for reduction(*:fac) for(int n = 2; n <= number; n++) { fac *= n; } return fac; } ``` Note: V tomto fragmente si môžete všimnúť paralelné vypočítanie faktoriálu čísla pomocou klauzuly `reduction` a operácie násobenia.

#### `#pragma omp critical(name)` ##### Kritická sekcia (blok), ktorú môže v jednom čase vykonávať len jedno vlákno Note: OpenMP ponúka viacero synchronizačných nástrojov. My spomenieme iba ten, ktorý sa používa nejjednoduchšie (a pravdepodobne aj najčastejšie). Ide o kritickú sekciu. Definujeme ju pomocou konštrukcie `#pragma omp critical`, kde môžeme doplniť voliteľný parameter - názov sekcie. Výsledkom bude to, že kritickú sekciu (s týmto názvom) bude môcť v vykonávať iba jedno vlákno. Inou možnosťou ako synchronizovať vlákna sú funkcie `omp_set_lock(&lock)` a `omp_unset_lock(&lock)` z knižnice `omp.h`.

# I ### Násobenie matíc

### IJK algoritmus ``` for (int i = 0; i < dimension; i++) { for (int j = 0; j < dimension; j++) { for (int k = 0; k < dimension; k++) { d[i][j] += f[i][k] * s[k][j]; } } } ``` Note: Tradičný algoritmus násobenia matíc pozostáva z troch vnorených cyklov. Vonkajšie dva cykly určujú pozíciu vo výslednej matici - `i` a `j`. Premenná `k` určuje index prvkov v riadku `i` prvej matice a stĺpci `k` druhej matice, ktoré sa majú vynásobiť.

### IKJ algoritmus ``` for (int i = 0; i < dimension; i++) { for (int k = 0; k < dimension; k++) { for (int j = 0; j < dimension; j++) { d[i][j] += f[i][k] * s[k][j]; } } } ``` Note: My sme použili tzv. IKJ algoritmus. Zmena oproti naivnému algoritmu IKJ je vo vymenenom poradí vnútorných cyklov.

#### `f[i][k]` je konštantné vo vnútornom cykle #### = #### optimalizácia pri preklade Note: Dosiahneme tým to, že prvok `f[i][k]` bude počas behu vnútorného cyklu (j) konštantný. Dôsledkom toho je možné urobiť optimalizáciu čítania tohto prvku z poľa počas prekladu.

# I ### Násobenie matíc #### OpenMP

#### `#pragma omp parallel for num_threads(n)` #### Rozdelíme vonkajší cyklus medzi vlákna a experimentujeme s počtom vlákien Note: Úprava na paralelný algoritmus pomocou OpenMP je priamočiara. Stačí rozdeliť vykonávanie vonkajšieho cyklu medzi vlákna pomocou `#pragma omp parallel for` a nájsť vhodný počet vlákien.

# II ### Výpočet čísla $\pi$ Note: V tejto úlohe sme sa snažili čo najpresnejšie vypočítať hodnotu PI.

\begin{aligned} \pi = \int_{0}^{1}\frac{4}{x^2 + 1}dx \end{aligned} Note: Hodnotu čísla PI vieme vypočítať podľa vzorca na slajde. Na to budeme potrebovať vypočítať určitý intergrál funkcie.

### Interval 0..1 rozdelíme na $N$ častí #### (Približnú) hodnotu $\pi$ potom vypočítame ako: $$ \frac{1}{N} \sum_{i=0}^{N-1} \frac{4}{(\frac{i}{N})^2 + 1} $$ Note: Presnú hodnotu vypočítať nedokážeme, ale vieme sa o to pokúsiť približne. Rozdelíme daný interval 0..1 na niekoľko častí (obdĺžníkov) a spočítame ich obsah.

#### Rozdelením intervalu 0..1 na viac častí získame presnejší výsledok Note: Samozrejme, na čím viac častí rozdelíme tento interval, tým presnejší výsledok dostaneme.

``` double w = 1.0 / N; for (long i = 0; i < N; i++) { x = (i + 0.5) * w; sum += 4.0 / (1.0 + x*x); } double pi = w * sum; ``` Note: Na slajde je možné vidieť podstatu sekvenčného algoritmu.

# II ### Výpočet čísla $\pi$ #### OpenMP

#### `#pragma omp parallel for reduction(+:sum) private(x) num_threads(n)` #### Rozdelíme cyklus medzi vlákna a zlúčime výsledky pomocou operácie sčítania Note: Pri paralelnom algoritme opäť urobíme iba jednoduchú zmenu. Počítanie obsahu obdĺžníkov rozdelíme medzi vlákna a na konci pozbierame výsledky a spočítame. To dosiahneme pomocou klauzuly `reduction`.

# III ### Nájdenie čísla s najväčším počtom deliteľov Note: Poslednou úlohou, ktorú sme riešili bolo nájdenie čísla zo zadaného rozsahu, ktoré má najvačší počet deliteľov.

#### Prejdeme všetky čísla v zadanom rozsahu a pre každé určíme počet jeho deliteľov Note: Postup je jednoduchý. Prejdeme všetky čísla a pre každé zistíme, koľko má deliteľov.

#### Stačí zistiť počet deliteľov po $\sqrt{n}$ ``` int divisors = 0; for (int i = 2; i*i <= n; i++) { if (n % i == 0) { divisors += (i*i == n) ? 1 : 2; } } ``` Note: Pri určovaní deliteľov postačuje ak budeme počitať delitele do druhej odmocniny. Avšak každý musíme započítať dva-krát. Okrem samotnej odmocniny.

# III ### Nájdenie čísla s najväčším počtom deliteľov #### OpenMP

#### `#pragma omp parallel for private(d) num_threads(n)` #### Rozdelíme hlavný cyklus medzi vlákna Note: Paralelne aj túto úlohu vyriešime rozdelením počítania deliteľov čísel z rozsahu medzi vlákna.

# ! #### `#pragma omp critical(UPDATE_MAX)` #### Upraviť maximum môže naraz iba jedno vlákno Note: Avšak je potrebné si uvedomiť, že iba jedno vlákno môže upraviť aktuálne maximum. Preto použijeme kritickú sekciu.