# Kratek uvod v vzporedno programiranje

Za programiranje vzporednih nalog uporabljamo dva načina:

1. MPI (Message Passing Interface)
2. OpenMP (Open Multi Processing)

Osnovno pravilo vzporednega programiranja je, da mora biti rezultat zaporednega in vzporednega programa enak. Z OpenMP je to zelo enstavno preverljivo. Težave lahko nastopijo le pri programih, ki uporabljajo generator naključnih števil (Monte Carlo metode).

## OpenMP

OpenMP programi se izvajajo le na enem vozlišču z porazdelitvijo na več vzporednih niti (threads). Za izdelavo niti skrbi prevajalnik sam. Kako naj se program razdeli na več niti se napiše v komentarje programa. To pa pomeni, da vzporedni program ni nič drugačen od zaporednega. Program lahko celo testiramo tako, da ga enkrat prevedemo brez OpenMP in dobimo zaporeden program. Nato pa ga prevedemo še z OpenMP in dobimo vzporeden program, ki se hkrati izvaja na večih jedrih enega vozlišča.

Vzporedne niti OpenMP programa imajo skupne spremenljivke do katerih morajo usklajeno dostopati da ne pride do težav s hkratnim branjem in pisanjem iste spremenljivke. Za postavitev _semaforjev_ skrbi prevajalnik sam, vendar je potrebno skupne spremenljivke pri katerih lahko pride do takšne težave prijaviti prevajalniku. Najbolje za vzporedne programe je, da imajo čim manj skupnih spremenljivk (**_shared_**) ali pa da so spremenljivke neodvisne (**_private_**) . Če se je rezultat večih vzporednih delov ena sama številka, ki prispeva k rezultatu (funkcional) je bolje, da se delni rezultati poračunajo na koncu in ne sproti. Taki operaciji, ki je dokaj pogosta (integriranje po delih, sumacija) pravimo **redukcija**.

Prednost programov z deljenim spominom (_Shared Memory Programming -_ SMP) je prav v hitrem dostopu do podatkov, saj jih ni potrebno tako kot pri MPI prenašati preko mrežnega dela. Slabost OpenMP pa je v omejitvi števila procesorjev saj programi praviloma delujejo le na enem vozlišču in je tako program omejen na max 16 procesorskih jeder. Razširitve na več jeder omogočajo posebne rešitve kot je npr GPU  (_Graphics Processor Unit)_ od katerih je najbolj znana CUDA. Nekateri prevajalniki omogočajo tudi tako imenovani ClusterMP, ki OpenMP program na nivoju predprocesorja opremijo z MPI za komunikacijo med vozliči.

## Primer paralelizacije z OpenMP

Naslednji primer v katerem računamo površino enotskega kroga z integracijo v zanki.

#include <stdio.h>
#include <math.h>
#define N 100000

int main()
{
  double area = 0.0;
#pragma omp parallel for reduction(+:area)
  for(int i = 0; i < N; i++)
    {
      double x = (i+0.5)/N;
      area += sqrt(1.0 - x*x);
    }
  printf("Površina : %g\n", 4.0*area/N);
  return 0;
}

Program prevedemo z

cc -std=c99 -o pi-openmp -fopenmp -O2 pi-omp.c -lm

Lahko pa ga prededemo tudi brez OpenMP direktive in tako dobimo zaporeden program. S <tt>#pragma</tt> komentarjem prevajalniku ukažemo, da razdeli zanko na vse razpoložljive procesorje, ki v večih nitih vsak izračuna le del intervalov. Za pravilno razdelitev intervalov zanke na niti skrbi prevajalnik. OpenMP program, ki se zažene se izvaja le v enem procesu. Po končani zanki se z redukcijo seštejejo delne vsote _area_ in izpiše rezultat 3.14159

Zagon programa lahko izvedemo na vozlišču z ukazom:

<pre>bsub -a openmp -n 12 -R "span[hosts=1]" ./pi-openmp
</pre>

Rezultat dobimo v pošni nabiralnik. Lažje pa je program pognati z ukazom interaktivnem načinu

## MPI

Za razliko od OpenMP so vzporedni deli MPI programa samostojni procesi, ki si med sabo ne delijo spomina. Tako pri MPI ne more priti do težav s hkratnim dostopanjem do spremenljivk, saj so vse spremenljivke v ločenih spominih lastni procesom. Za skupne spremenljivke je potrebno sprogramirati s knjižnico MPI pošiljanje podatkov preko mrežnega sloja. Tak način komuniciranja velja tudi za več procesov na istem vozlišču, vendar je hitrost komunikacije hitrejša med procesi enega vozlišča, kot pa med procesi različnih vozlišč. Programi MPI niso omejeni po številu vzporednih procesov. Omejitev lahko predstavlja aplikacija sama s količino komunikacije. Zato je potrebno za dobro delovanje MPI programov zagotoviti čim hitrejšo mrežo med vozlišči (npr z Infinibandom) ali pa program izdelati tako, da komunikacija ne predstavlja ozkega grla ob večanju števila procesov. Za zmanjšanje komunikacije in s tem pohitritev lahko uporabimo tudi kombinacijo MPI in OpenMP. MPI skrbi za komunikacijo med vozlišči, OpenMP pa za komunikacijo v vozlišču. Načeloma je takšna rešitev najboljša, vendar pa v novejših jedernih procesorjih obstaja tudi možnost, da lahko manjše število jeder deluje celo [hitreje od osnovne frekvence](http://www.intel.com/technology/turboboost "Turbo Boost") na račun ostalih jeder.

## Primer paralelizacije z MPI

Računanje površine razdelimo na  več procesov. Pri OpenMP je za pravilno razdelitev števca _i_ na niti zanke skrbel prevajalnik. Pri MPI pa odgovornost programerja, da razdeli naloge na procese. Ob zagonu programa se naredi zahtevano število istih programom in vsak teče na svojem procesorju. Številko procesa in skupno število procesov se pridobi z ustreznim klicem MPI_ funkcij. V naslednjem primeru se je zanka razdelila z metodo _leapfrog_, ki omogoča enakomerno razporeditev celoštevilčnega intervala na poljubno število procesov.

#include <mpi.h>
#include <stdio.h>
#include <math.h>
#define N 100000

int main(int argc, char *argv[])
{
  int id; 		// številka procesa
  int procesov; 	// število vseh procesov
  double area = 0.0;

  MPI_Init(&argc, &argv);
  MPI_Comm_rank(MPI_COMM_WORLD, &id);
  MPI_Comm_size(MPI_COMM_WORLD, &procesov);

  for(int i = id; i < N; i += procesov)
    {
      double x = (i+0.5)/N;
      area += sqrt(1.0 - x*x);
    }
  double skupno;
  MPI_Reduce(&area, &skupno, 1, MPI_DOUBLE, MPI_SUM, 0, MPI_COMM_WORLD);
  if (id == 0)
     printf("Površina : %g\n", 4.0*skupno/N);
  MPI_Finalize();
  return 0;
}

Program prevedemo z in poženemo na 48 procesih z ukazi

module load OpenMPI
mpicc -std=c99 -o pi-mpi pi-mpi.c
srun -n 48 --mem=0 pi-mpi

Rezultat preberemo s poštnim programom mail

###### tags: `HPCFS`