```
]
- U slučaju da pri kompajliranju nije navedeno ime izvršne datoteke, ona će se podrazumevano zvati a.out.
---
## Zadatak 1: Računanje vrednosti broja π
.message.is-info[
.message-header[
Zadatak
]
.message-body[
- Korišćenjem samo parallel konstrukcije, paralelizovati program koji računa vrednost integrala
$$ \int_{0}^{1} \frac{4}{(1+x^{2})} $$
- Sekvencijalna implementacija programa u C programskom jeziku je data u direktorijumu zadaci. Rezultat integraljenja bi trebalo da bude jednak broju π. Potrebno je dodati parallel konstrukciju bez daljih modifikacija sekvencijalnog programa.
- Šta se dešava sa rezultatom?
]
]
--
.message.is-success[
.message-header[
Odgovor
]
.message-body[
- Funkcija `parallel_code_incorrect` ☛ rešenja/`pi.c`
]
]
---
## Tipovi promenljivih
- **Deljene**, odnosno **globalne** - Prostor za ove promenljive se
zauzima na hipu, kome pristupaju sve niti.
- *Potencijalni kandidati za štetno preplitanje*!
- U deljene promenljive se ubrajaju:
- statičke promenljive i
- promenljive alocirane izvan paralelnog regiona (na primer promenljiva sum iz zadatka 1)
- **Privatne**, odnosno **lokalne** - Vidljive samo u okviru niti u kojoj su deklarisane. Prostor za ove promenljive se zauzima na `steku niti`.
- U privatne promenljive se ubrajaju:
- promenljive deklarisane unutar paralelnog regiona (x)
- promenljive promenljive deklarisane unutar funkcije koja je pozvana iz paralelnog regiona i
- brojačke promenljive u `for` petlji prvog nivoa
- `OMP_STACKSIZE` za upravljanje veličinom steka niti
---
## Zadatak 2: Računanje vrednosti broja π
.message.is-info[
.message-header[
Zadatak
]
.message-body[
- Modifikovati rešenje prethodnog zadatka tako da se ukloni štetno preplitanje.
]
]
--
.message.is-success[
.message-header[
Odgovor
]
.message-body[
- Funkcija `parallel_code` ☛ rešenja/`pi.c`
]
]
---
## Zadatak 3*: Računanje vrednosti broja π
.message.is-info[
.message-header[
Zadatak
]
.message-body[
- Paralelno rešenje zadatka 2 eliminiše problem štetnog preplitanja, ali uvodi problem lažnog deljenja (eng. *false sharing*) pri pristupu nizovnoj promenljivoj `sum`.
- Izmeniti rešenje tako se otkloni lažno deljenje.
]
]
--
.message.is-warning[
.message-header[
Info
]
.message-body[
- Razmisliti o tome koliko se elemenata niza prenosi u keš procesora kada se pristupa jednom elementu.
]
]
--
.message.is-success[
.message-header[
Odgovor
]
.message-body[
- Funkcija `parallel_code_no_false_sharing` ☛ rešenja/`pi.c`
]
]
---
## Sinhronizacioni konstrukti
- Sinhronizacija visokog nivoa apstrakcije:
- barrier construct - definiše tačku u kodu do koje sve aktivne niti moraju da se zaustave dok do te tačke ne stigne i poslednja nit, nakon čega sve niti mogu nastaviti dalje izvršavanje. `#pragma omp barrier`
- `critical construct` - samo jedna nit može u jednom trenutku biti u kritičnoj sekciji.
```c
#pragma omp critical
strukturirani-blok
```
- `atomic construct` - hardverski podržan isključiv pristup ažuriranju vrednosti proste promenljive. Ukoliko nema hardverske podrške, ova konstrukcija se ponaša kao i `critical`. `#pragma omp atomic`
---
## Zadatak 4: Računanje vrednosti broja pi
.message.is-info[
.message-header[
Zadatak
]
.message-body[
- Doraditi rešenje zadatka 2 tako da se štetno preplitanje ukloni odgovarajućim sinhronizacionim mehanizmom.
]
]
--
.message.is-success[
.message-header[
Odgovor
]
.message-body[
- Funkcija `parallel_code_synchronization` ☛ rešenja/`pi.c`
]
]
---
## Konstrukcije za podelu posla
- eng. *worksharing constructs*
- `loop` konstrukcija (eng. *loop construct*)
- `sections/section` konstrukcija (eng. *sections/section construct*)
- `single` konstrukcija (eng. *single construct*)
- Na kraju bloka koda koji se izvršava u sklopu neke od konstrukcija za podelu posla podrazumevano postoji `implicitna barijerna sinhronizacija`.
- Podrazumevano ponašanje se može promeniti navođenjem `nowait` klauze u okviru direktiva za podelu posla (primer kasnije).
---
## Implicitna barijerna sinhronizacija
- Implicitna barijerna sinhronizacija se takođe podrazumevano nalazi i na kraju paralelnog regiona, ali je za razliku od konstrukcija za podelu posla, nije moguće odatle ukloniti.
- Zašto?
---
name: loop
class: center, middle, inverse
layout: false
# loop konstrukcija
---
layout: true
.section[[loop konstrukcija](#sadrzaj)]
---
## loop konstrukcija
- Sintaksa:
```c
#pragma omp for [clause[ [,] clause] ... ]
for-petlje
```
- Problemi u računarstvu visokih performansi se često svode na rad sa velikim nizovima! To znači da često postoji iteriranje kroz nizove...
- Taj posao može da se podeli na više niti! Svaka nit u paraleli može obraditi parče niza.
- Ovaj način raspodele podataka ste već implementirali u zadatku 2, ali ste sami morali da specificirate granice niza nad kojima radi svaka pojedinačna nit.
---
## Primer 2: `loop` konstrukcija
.message.is-dark[
.message-header[
Primer
]
.message-body[
- Primer upotrebe `for` direktive
```c
#pragma omp parallel
{
int sum = 0;
#pragma omp for
for (int i = 0; i < N; i++)
sum += A[i];
}
```
- Korišćenjem kombinovane konstrukcije:
```c
#pragma omp parallel for
{
int sum = 0;
for (int i = 0; i < N; i++)
sum += A[i];
}
```
]
]
---
## loop konstrukcija: raspoređivanje
- **Kako će iteracije petlje biti dodeljene nitima?**
- OpenMP podržava više strategija raspoređivanja koje se mogu specificirati schedule klauzom.
```c
#pragma omp for schedule(tip [,velicina_bloka])
```
---
## loop konstrukcija: raspoređivanje
- **Kako će iteracije petlje biti dodeljene nitima?**
- `static` - blokovi iteracija se dodeljuju nitima u vreme kompajliranja po `round-robin` principu
- `dynamic` - blokovi iteracija se dodeljuju nitima u vreme izvršavanja tako da opterećenje niti bude optimalno
- `guided` - modifikacija dinamičkog raspoređivanja gde je svaki naredni blok dodeljen niti manji od prethodnog
- `auto` - kompajler određuje tip raspoređivanja koji misli da je najbolji za problem
- `runtime` - moguće je "spolja" uticati na tip raspoređivanja preko `OMP_SCHEDULE` promenljive okruženja
---
name: redukcije
class: center, middle, inverse
layout: false
# Redukcije
---
layout: true
.section[[Redukcije](#sadrzaj)]
---
## Redukcije
- Prisetimo se nepotpunog paralelnog sabiranja elemenata niza iz primera 2
```c
#pragma omp parallel for
{
int sum = 0;
for (int i = 0; i < N; i++) {
sum += A[i];
}
}
/* saberi parcijalne sume */
```
- Da bi program bio potpuno funkcionalan, potrebno je posabirati parcijalne sume koje sračunaju niti.
---
## Redukcije
- Može da se uradi ovako:
```C
int sum = 0;
#pragma omp parallel for
{
for (int i = 0; i < N; i++) {
#pragma omp critical
sum += A[i];
}
}
```
- I u deljenoj promenljivoj sum će biti konačan rezultat.
- Ali ovo je **MNOGO** neefikasno!
---
## Redukcije
- A može i ovako:
```c
int sum = 0;
#pragma omp parallel for reduction(+:sum)
{
for (int i = 0; i < N; i++) {
sum += A[i];
}
}
```
- Šta zapravo znači `reduction(+:sum)?`
---
## Redukcije
.message.is-warning[
.message-header[
Info
]
.message-body[
1. Za svaku nit u paralelnom regionu napravi po jednu privatnu
instancu promenljive `sum` i inicijalizuj je na vrednost neutralnu
za navedeni redukcioni operator (u slučaju sabiranja je to 0).
2. Svaka nit menja svoju kopiju promenljive `sum.`
3. Na kraju petlje, rezultati se kombinuju upotrebom redukcionog
operatora u deljenu promenljivu `sum.`
]
]
---
## Redukcije
- Opšti format redukcije:
```c
reduction(redukcioni_operator : lista_promenljivih)
```
- Ugrađeni redukcioni operatori za C/C++:
.center-table.small[
| **Operacija** | **Vrednost** |
|:-------------:|:----------------------:|
| + | 0 |
| * | 1 |
| - | 0 |
| min | najveći pozitivan broj |
| max | najveći negativan broj |
| & | ~0 |
| I | 0 |
| ˆ | 0 |
| && | 1 |
| II | 0 |
]
---
## Zadatak 5: Računanje vrednosti broja pi
.message.is-info[
.message-header[
Zadatak
]
.message-body[
- Implementirati paralelno rešenje računanja vrednosti broja pi uz
korišćenje `for` direktive i reduction klauze.
]
]
--
.message.is-success[
.message-header[
Odgovor
]
.message-body[
- Funkcija `parallel_code_for_construct` ☛ rešenja/`pi.c`
]
]
---
name: vs
class: center, middle, inverse
layout: false
# Implicitna vs. eksplicitna barijera
---
layout: true
.section[[Implicitna vs. eksplicitna barijera](#sadrzaj)]
---
## Implicitna vs. eksplicitna barijera
- Eksplicitna barijera je zadata `#pragma omp barrier direktivom`.
- Implicitna barijera je barijera već uključena u neku konstrukciju (npr. `for` konstrukciju).
---
## Implicitna vs. eksplicitna barijera
.message.is-info[
.message-header[
Zadatak
]
.message-body[
- U kojem delu koda će se niti sinhronizovati?
```c
#pragma omp parallel
{
/* prvi blok naredbi */
#pragma omp barrier
/* drugi blok naredbi */
}
```
]
]
--
.message.is-success[
.message-header[
Odgovor
]
.message-body[
- Na barrier direktivi (eksplicitna barijerna sinhronizacija).
]
]
---
## Implicitna vs. eksplicitna barijera
.message.is-info[
.message-header[
Zadatak
]
.message-body[
- U kojem delu koda će se niti sinhronizovati?
```c
#pragma omp parallel for
for (i = 0; i < N; i++)
/* prvi blok naredbi */
/* drugi blok naredbi */
```
]
]
--
.message.is-success[
.message-header[
Odgovor
]
.message-body[
- Na kraju prvog bloka naredbi. Sve niti moraju da završe svoje iteracije petlje da bi mogle da nastave sa drugim blokom naredbi, jer podrazumevano `loop` konstrukcija ima ugrađenu implicitnu barijeru.
]
]
---
## Implicitna vs. eksplicitna barijera
.message.is-info[
.message-header[
Zadatak
]
.message-body[
- U kojem delu koda će se niti sinhronizovati?
```c
#pragma omp parallel for nowait
for (i = 0; i < N; i++)
/* prvi blok naredbi */
/* drugi blok naredbi */
```
]
]
---
## Implicitna vs. eksplicitna barijera
.message.is-info[
.message-header[
Zadatak
]
.message-body[
- U kojem delu koda će se niti sinhronizovati?
```c
#pragma omp parallel for nowait
for (i = 0; i < N; i++)
/* prvi blok naredbi */
/* drugi blok naredbi */
```
]
]
--
.message.is-success[
.message-header[
Odgovor
]
.message-body[
- Na kraju paralelnog regiona. Implicitna barijera loop konstrukcije je onemogućena upotrebom `nowait` klauze.
]
]
---
name: ss
class: center, middle, inverse
layout: false
# sections/section konstrukcija
---
layout: true
.section[[sections/section konstrukcija](#sadrzaj)]
---
## sections/section konstrukcija
- Svaka nit unutar sections konstrukcije izvršava jedan blok koda koji pripada sekciji.
- Sintaksa:
```c
#pragma omp sections [clause[ [,] clause] ... ]
{
[ #pragma omp section ]
strukturirani-blok
[ #pragma omp section
strukturirani-blok ]
...
}
```
---
## Primer 3: sections/section konstrukcija
.message.is-dark[
.message-header[
Primer
]
.message-body[
```c
#pragma omp parallel
{
#pragma omp sections
{
#pragma omp section
x_calculation();
#pragma omp section
y_calculation();
#pragma omp section
z_calculation();
}
}
```
]
]
---
## single konstrukcija
- Sintaksa:
```c
#pragma omp single [clause[ [,] clause] ... ]
strukturirani-blok
```
- Blok naredbi izvršava samo nit koja prva uđe u strukturirani blok.
```c
#pragma omp parallel
{
do_many_things();
#pragma omp single
{ exchange_boundaries(); }
#pragma omp barrier
do_many_other_things();
}
```
---
## master konstrukcija
- Sintaksa:
```c
#pragma omp master
strukturirani-blok
```
- Blok naredbi izvršava samo master nit.
```c
#pragma omp parallel
{
do_many_things();
#pragma omp master
{ exchange_boundaries(); }
#pragma omp barrier
do_many_other_things();
}
```
- Nema implicitne sinhronizacije.
---
## Sihnronizacioni mehanizmi: lock
- Pripada mehanizmima niskog nivoa sinhronizacije.
- Analogni pojam propusnici iz C++11 višenitnog okruženja.
- `critical` direktiva u pozadini koristi `lock`.
- Zašto biste onda ikada želeli da direktno koristite ovu direktivu?
- Nema problema, ako na primer, ograničavate pristup jednoj celobrojnoj promenljivoj kroz kritičnu sekciju.
- Ali šta će se desiti ako kroz kritičnu sekciju ograničite pristup elementima nekog niza?
---
## Primer 3: histogram

.center[
`int` histogram[255];
]
---
## Primer 4: histogram
```C
#pragma omp parallel for
for (i = 0; i < NBUCKETS; i+) {
omp_init_lock(&hist_locks[i]);
hist[i] = 0;
}
#pragma omp parallel for
for (i = 0; i < NVALS; i++) {
ival = (int) sample(arr[i]);
omp_set_lock(&hist_locks[ival]);
hist[ival]++;
omp_unset_lock(&hist_locks[ival]);
}
for (i = 0; i < NBUCKETS; i++) {
omp_destroy_lock(&hist_locks[i]);
}
```
---
## Klauze za rad sa podacima
- `shared`()
- `private`()
- `firstprivate`()
- `lastprivate`()
- `default( private | shared | none )` - Ako se ništa ne navede za ovu klauzu, podrazumevana vrednost u C i C++ programskim jezicima je `shared.`
---
## Primer 5: Klauze za rad sa podacima
.message.is-info[
.message-header[
Zadatak
]
.message-body[
```c
void dummy() {
int tmp = 0;
#pragma omp parallel for private(tmp)
for (int j = 0; j < 5; j++)
tmp += j;
printf("%d\n", tmp);
}
```
- Koja vrednost će biti ispisana na standardni izlaz?
]
]
--
.message.is-success[
.message-header[
Odgovor
]
.message-body[
- Na standardni izlaz će biti ispisana vrednost 0.
- **Objašnjenje**:
Kako je promenljiva tmp proglašena privatnom, svaka nit će imati svoju instancu ove promenljive. Po završetku petlje, lokalne promenljive će biti uništene, a deljena promenljiva `tmp` će zadržati svoj u inicijalnu vrednost.
]
]
---
## Primer 5: Klauze za rad sa podacima
.message.is-info[
.message-header[
Zadatak
]
.message-body[
```c
void dummy() {
int tmp = 0;
#pragma omp parallel for private(tmp)
for (int j = 0; j < 5; j++)
tmp += j;
printf("%d\n", tmp);
}
```
- Koja je inicijalna vrednost privatnih verzija promenljive `tmp`?
]
]
--
.message.is-success[
.message-header[
Odgovor
]
.message-body[
- Inicijalna vrednost privatnih promenljivih tmp je nepoznata.
- **Objašnjenje**:
Klauza private`(tmp)` kaže kompajleru da treba da alocira prostor za promenljivu tmp na steku. Kompajler ne mora inicijalizovati zauzetu lokaciju.
]
]
---
## Primer 5: Klauze za rad sa podacima
.message.is-info[
.message-header[
Zadatak
]
.message-body[
```c
void dummy() {
int tmp = 0;
#pragma omp parallel for private(tmp)
for (int j = 0; j < 5; j++)
tmp += j;
printf("%d\n", tmp);
}
```
- Kojom klauzom je potrebno zameniti private klauzu da bi lokalne
instance promenljive tmp dobile inicijalnu vrednost globalne
promenljive `tmp`?
]
]
--
.message.is-success[
.message-header[
Odgovor
]
.message-body[
- `firstprivate`
]
]
---
## Zadatak 6: Mandelbrotov set
.message.is-info[
.message-header[
Zadatak
]
.message-body[
- Data je datoteka `mandelbrot.c.` Datoteka sadrži paralelno OpenMP rešenje koje određuje Mandelbrotov set.
- Rešenje ima par problema vezanih za korišćenje klauza za rad sa podacima i poneko štetno preplitanje. Pronađite i ispravite greške.
]
]
--
.message.is-success[
.message-header[
Odgovor
]
.message-body[
- ☛ rešenja/`mandelbrot.c`
]
]
---
## Kako paralelizovati `while` i rekurziju?
- Inicijalno, OpenMP je zamišljen tako da je moguće paralelizovati
probleme za koje se unapred zna broj potrebnih iteracija za njihovo
rešavanje!
--
.message.is-danger[
.message-header[
Problem
]
.message-body[
- Kako primeniti OpenMP u drugim tipovima petlji u kojima se ne zna unapred broj iteracija? Ili u slučaju rekurzije?
]
]
---
## Kako paralelizovati `while` i rekurziju?
- Inicijalno, OpenMP je zamišljen tako da je moguće paralelizovati
probleme za koje se unapred zna broj potrebnih iteracija za njihovo
rešavanje!
.message.is-danger[
.message-header[
Problem
]
.message-body[
- Kako primeniti OpenMP u drugim tipovima petlji u kojima se ne zna unapred broj iteracija? Ili u slučaju rekurzije?
]
]
.message.is-warning[
.message-header[
Info
]
.message-body[
- Opcije:
- Problem transformisati u formu `for` petlje ako je to moguće
- Koristiti `task` konstrukciju (od OpenMP 3.0)
]
]
---
## Primer 6: Paralelizacija obrade čvorova liste
.lcol[
```c
// petlja koju
// treba paralelizovati
while (p != NULL) {
processwork(p);
p = p->next;
}
```
]
.rcol[
```c
// 1. odrediti broj cvorova
while (p != NULL) {
nelems++; p = p->next;
}
...
// 2. zapamtiti adrese cvorova
p = head;
for (i = 0; i < nelems; i++) {
ptrs[i] = p;
p = p->next;
}
...
// 3. pokrenuti paralelnu obradu
#pragma omp parallel for
for (i = 0; i < nelems; i++)
processwork(ptrs[i]);
```
]
---
## task konstrukcija
- Sintaksa:
```c
#pragma omp task[clause[ [,] clause] ... ]
strukturirani-blok
```
- Može se posmatrati kao nezavisna jedinica posla.
- Čine ga:
- Kod koji zadatak izvršava
- Podaci (privatne i deljene promenljive)
- `Internal Control Variables (ICV)` (npr. indikator da li zadatak može da bude dodeljen različitim nitima, vrsta raspoređivanja, broj niti u paralelnom regionu itd.)
---
## Primer 7: Kreiranje zadataka
.message.is-dark[
.message-header[
Primer
]
.message-body[
- `task i single` konstrukcije se često koriste zajedno:
- jedna nit pravi zadatke koji se uvezuju u red zadataka odakle sve niti mogu da uzimaju zadatke.
```c
#pragma omp parallel
{
#pragma omp single
{
#pragma omp task
y = f(x)
#pragma omp task
z = g(x)
}
}
```
]
]
---
## Zadatak 7: Modifikacija liste
.message.is-info[
.message-header[
Zadatak
]
.message-body[
- Data je sekvencijalna implementacija liste `(linked.c)` u kojoj svaki element sadrži po jedan Fibonačijev broj dobijen funkcijom `processwork`.
- Napraviti OpenMP paralelni program korišćenjem `task` konstrukcije.
]
]
--
.message.is-success[
.message-header[
Odgovor
]
.message-body[
- ☛ rešenja/`linkedlist.c`
]
]
---
## Konstrukti za sinhronizaciju izvršavanja zadataka
- `taskwait` - sinhronizacija samo zadataka istog nivoa
```c
#pragma omp taskwait
```
- `taskgroup` - sinhronizuje i podzadatke
```c
#pragma omp taskgroup
strukturirani-block
```
- `depend` - task klauza
```c
depend(in | out | inout : lista)
```
---
## Primer 8: Sinhronizacija zavisnih zadataka
```c
int y, z;
#pragma omp parallel
{
#pragma omp single
{
#pragma omp task
y = f(x)
#pragma omp taskwait
#pragma omp task
z = g(y)
}
}
```
---
## Primer 8: Sinhronizacija zavisnih zadataka
```c
#pragma omp parallel
{
int y, z;
#pragma omp single
{
#pragma omp task depend(out:y)
y = f(x)
#pragma omp task depend(in:y)
z = g(y)
}
}
```
---
## Zadatak 8*: Množenje matrice i vektora
.message.is-info[
.message-header[
Zadatak
]
.message-body[
- Implementirati sekvencijalni program za množenje nekvadratne matrice i vektora u C programskom jeziku.
- Nakon što se uverite da program daje očekivane rezultate, implementirani OpenMP paralelni algoritam na osnovu sekvencijalnog programa.
]
]
--
.message.is-warning[
.message-header[
Info
]
.message-body[
- **Napomene**: Svaka od dimenzija matrice treba da bude makar 1000. Za potrebe testiranja programa dimenzije matrice mogu da budu i manje.
Meriti izvršavanje programa funkcijom `omp_get_wtime()`.
]
]
---
## Zadatak 9*: Množenje matrica - domaći
.message.is-info[
.message-header[
Zadatak
]
.message-body[
- Implementirati sekvencijalni program za množenje dve nekvadratne
matrice u C programskom jeziku.
- Nakon što se uverite da program daje očekivane rezultate,
implementirati OpenMP paralelni program na osnovu
sekvencijalnog programa.
]
]
--
.message.is-warning[
.message-header[
Info
]
.message-body[
- **Napomene**: Korektan sekvencijalni program testirati na velikim matricama (oko 1000 po dimenziji, modifikovati zavisno od karakteristika računara na kojem radite zadatak).
Za potrebe testiranja, dimenzije matrica mogu da budu i manje.
Meriti izvršavanje programa funkcijom `omp_get_wtime()`.
]
]
---
## Zadatak 10*: Akumuliranje vrednosti čvorova stabla
.message.is-info[
.message-header[
Zadatak
]
.message-body[
- Napraviti sekvencijalnu implementaciju stabla u C programskom jeziku.
- Svaki čvor stabla sadrži jedan razlomljeni broj u jednostrukoj preciznosti.
- Potrebno je implementirati minimalni skup funkcionalnosti (kreiranje stabla, sabiranje vrednosti čvorova stabla i uništavanje stabla).
- Nakon što se uverite da program daje očekivane rezultate implementirati OpenMP paralelni program na osnovu sekvencijalnog programa
]
]
--
.message.is-warning[
.message-header[
Info
]
.message-body[
- **Napomene**:
Paralelni program implementirati korišćenjem task konstrukcije.
Meriti izvršavanje programa funkcijom `omp_get_wtime()`.
]
]
---
name: end
class: center, middle, inverse
layout: false
# Nastaviće se...
---
## Korišćeni materijali
- Dokumentacija sa OpenMP sajta, videti `www.openmp.org`
- `"Introduction to OpenMP", Tim Mattson`, dostupno na [ovom linku](https://www.youtube.com/playlist?list=PLLX-Q6B8xqZ8n8bwjGdzBJ25X2utwnoEG)
- [`"Introduction to OpenMP"`, prateća prezentacija](https://www.openmp.org/wp-content/uploads/Intro_To_OpenMP_Mattson.pdf)
- `"Parallel Computing Book"`, Victor Eijkhout, elektronska verzija knjige je dostupna na [ovom linku](http://pages.tacc.utexas.edu/~eijkhout/pcse/html/omp-basics.html)
--
class: center, middle, theend, hide-text
layout: false
background-image: url(../theend.gif)