Friday, July 5, 2019

Programare paralela openMP 1

Guide into OpenMP: Easy multithreading programming for C++

By Joel Yliluoma, September 2007; last update in June 2016 for OpenMP 4.5

Abstract


    Preface: Importance of multithreading

    As CPU speeds no longer improve as significantly as they did before, multicore systems are becoming more popular.To harness that power, it is becoming important for programmers to be knowledgeable in parallel programming — making a program execute multiple things simultaneously.
    This document attempts to give a quick introduction to OpenMP, a simple C/C++/Fortran compiler extension that allows to add parallelism into existing source code without significantly having to entirely rewrite it.

    Support in different compilers

    • GCC (GNU Compiler Collection) supports OpenMP 4.5 since version 6.1, OpenMP 4.0 since version 4.9, OpenMP 3.1 since version 4.7, OpenMP 3.0 since version 4.4, and OpenMP 2.5 since version 4.2. Add the commandline option -fopenmp to enable it. OpenMP offloading is supported for Intel MIC targets only (Intel Xeon Phi KNL + emulation) since version 5.1, and to NVidia (NVPTX) targets since version 7 or so.
    • Clang++ supports OpenMP 4.5 since version 3.9 (without offloading), OpenMP 4.0 since version 3.8 (for some parts), and OpenMP 3.1 since version 3.7. Add the commandline option -fopenmp to enable it.
    • Solaris Studio supports OpenMP 4.0 since version 12.4, and OpenMP 3.1 since version 12.3. Add the commandline option -xopenmp to enable it.
    • Intel C Compiler (icc) supports Openmp 4.5 since version 17.0, OpenMP 4.0 since version 15.0, OpenMP 3.1 since version 12.1, OpenMP 3.0 since version 11.0, and OpenMP 2.5 since version 10.1. Add the commandline option -openmp to enable it. Add the -openmp-stubs option instead to enable the library without actual parallel execution.
    • Microsoft Visual C++ (cl) supports OpenMP 2.0 since version 2005. Add the commandline option /openmp to enable it.
    Note: If your GCC complains that "-fopenmp" is valid for D but not for C++ when you try to use it, or does not recognize the option at all, your GCC version is too old. If your linker complains about missing GOMP functions, you forgot to specify "-fopenmp" in the linking.
    More information: http://openmp.org/wp/openmp-compilers/

    Introduction to OpenMP in C++

    OpenMP consists of a set of compiler #pragmas that control how the program works. The pragmas are designed so that even if the compiler does not support them, the program will still yield correct behavior, but without any parallelism.Here are two simple example programs demonstrating OpenMP.
    You can compile them like this:
      g++ tmp.cpp -fopenmp
    

    Example: Initializing a table in parallel (multiple threads)

    This code divides the table initialization into multiple threads, which are run simultaneously. Each thread initializes a portion of the table.
      #include <cmath>
      int main()
      {
        const int size = 256;
        double sinTable[size];
        
        #pragma omp parallel for
        for(int n=0; n<size; ++n)
          sinTable[n] = std::sin(2 * M_PI * n / size);
      
        // the table is now initialized
      }

    Example: Initializing a table in parallel (single thread, SIMD)

    This version requires compiler support for at least OpenMP 4.0, and the use of a parallel floating point library such as AMD ACML or Intel SVML (which can be used in GCC with e.g. ‑mveclibabi=svml).
      #include <cmath>
      int main()
      {
        const int size = 256;
        double sinTable[size];
        
        #pragma omp simd
        for(int n=0; n<size; ++n)
          sinTable[n] = std::sin(2 * M_PI * n / size);
      
        // the table is now initialized
      }

    Example: Initializing a table in parallel (multiple threads on another device)

    OpenMP 4.0 added support for offloading code to different devices, such as a GPU. Therefore there can be three layers of parallelism in a single program: Single thread processing multiple data; multiple threads running simultaneously; and multiple devices running same program simultaneously.
      #include <cmath>
      int main()
      {
        const int size = 256;
        double sinTable[size];
        
        #pragma omp target teams distribute parallel for map(from:sinTable[0:256])
        for(int n=0; n<size; ++n)
          sinTable[n] = std::sin(2 * M_PI * n / size);
    
        // the table is now initialized
      }

    Example: Calculating the Mandelbrot fractal in parallel (host computer)

    This program calculates the classic Mandelbrot fractal at a low resolution and renders it with ASCII characters, calculating multiple pixels in parallel.
     #include <complex>
     #include <cstdio>
     
     typedef std::complex<double> complex;
     
     int MandelbrotCalculate(complex c, int maxiter)
     {
         // iterates z = z + c until |z| >= 2 or maxiter is reached,
         // returns the number of iterations.
         complex z = c;
         int n=0;
         for(; n<maxiter; ++n)
         {
             if( std::abs(z) >= 2.0) break;
             z = z*z + c;
         }
         return n;
     }
     int main()
     {
         const int width = 78, height = 44, num_pixels = width*height;
         
         const complex center(-.7, 0), span(2.7, -(4/3.0)*2.7*height/width);
         const complex begin = center-span/2.0;//, end = center+span/2.0;
         const int maxiter = 100000;
       
       #pragma omp parallel for ordered schedule(dynamic)
         for(int pix=0; pix<num_pixels; ++pix)
         {
             const int x = pix%width, y = pix/width;
             
             complex c = begin + complex(x * span.real() / (width +1.0),
                                         y * span.imag() / (height+1.0));
             
             int n = MandelbrotCalculate(c, maxiter);
             if(n == maxiter) n = 0;
             
           #pragma omp ordered
             {
               char c = ' ';
               if(n > 0)
               {
                   static const char charset[] = ".,c8M@jawrpogOQEPGJ";
                   c = charset[n % (sizeof(charset)-1)];
               }
               std::putchar(c);
               if(x+1 == width) std::puts("|");
             }
         }
     }
    This program can be improved in many different ways, but it is left simple for the sake of an introductory example.

    Discussion

    As you can see, there is very little in the program that indicates that it runs in parallel. If you remove the #pragma lines, the result is still a valid C++ program that runs and does the expected thing.Only when the compiler interprets those #pragma lines, it becomes a parallel program. It really does calculate N values simultaneously where N is the number of threads. In GCC, libgomp determines that from the number of processors.
    By C and C++ standards, if the compiler encounters a #pragma that it does not support, it will ignore it. So adding the OMP statements can be done safely[1] without breaking compatibility with legacy compilers.
    There is also a runtime library that can be accessed through omp.h, but it is less often needed. If you need it, you can check the #define _OPENMP for conditional compilation in case of compilers that don't support OpenMP.
    [1]: Within the usual parallel programming issues (concurrency, mutual exclusion) of course.

    programare paralela exercitii

    APD - Lab1
    2007

    programare (impartire problema in subprobleme)
    Firele de executie se creeaza in cadrul unui proces si se creeaza mai repede decat procesele.

    Algoritmi paraleli si distribuiti, curs an 5
    Corina Stratan: corina@cs.pub.ro
    Limbaje pentru prelucrare paralela: SR, Paralaxis, biblioteci pentru programe C
    Ex:
    - OpenMP: creare de fire de executie; OpenMP e portabil (pthreads din C e specific Linux)
    - MPI: message passing interface: pe sisteme distribuite, intre care se schimba mesaje
    - Java: suporta nativ fire de executie
    Comunicarea se poare face:
    - In fire de executie separate, cu resurse partajate
    Prin mesaje, intre procese, eventual chiar intre
    masini separate
    -
    Open MP
    Compilator: Omni Open MP
    Comanda: ompcc (similar gcc): ex "ompcc -o program program.c"
    De inclus header: #include <omp.h>
    De setat o variabila de mediu: "export OMPC_NUM_PROCS = 5"
    Numarul de fire de executie nu trebuie sa fie fix, depinzand
    de masina pe care ruleaza. Open MP incearca sa aloce
    automat firele de executie.
    Program OpenMP: fork-join
    Pretate la cicluri mari.
    Fork la creare de fire, join la terminarea calculelor.
    Directive pragma: pentru compilator, optiuni specifice date de programator; compilatorul ce nu
    recunoaste pragma-urile le ignora
    Directivele actioneaza asupra unei regiuni de cod, intre {}.
    Pentru o linie de cod sau o singura instructiune compusa nu e nevoie de {}.
    #pragma omp <directiva> [clauze]
    Directiva de creare a unei regiuni paralele:
    #pragma omp parallel
    //cod
    {
    }
    #pragma omp parallel num_threads(5)
    Sau:
    Apelata inaintea crearii regiunii paralele. La directiva parallel se creeaza automat 5
    threaduri.
    omp_set_num_threads(5);
    1: dinamic, 0: static
    Setarea din variabila de mediu il face sa considere automat ca are atatea procesoare cate
    s-au specificat, nu mai e nevoie de dynamic
    omp_set_dynamic(0);
    Cate threaduri sunt in mod curent
    Rulat in regiune paralela, arata cate threaduri ruleaza acolo; in afara regiunii paralele (ar
    trebui sa arate) numarul definit la set_num_threads()
    int omp_get_num_threads();
    Ce id are thradul curent
    int omp_get_thread_num();
    Program OpenMP de adunare a doi vectori:
    Primul thread aduna primele x elemente, al doilea urmatoarele y, etc… vectorul A+B=C
    #pragma omp parallel
    Int id, I, Nthreads, istart, iend; //indici intre care ruleaza fiecare thread
    Id = omp_get_thread_num();
    Nthreads = omp_get_num_threads();
    Istart = id * N / Nthreads;
    Iend = (id+1) * N / Nthreads;
    c[i]=a[i]+b[i];
    For(i=istart, i<iend;i++)
    {
    }
    Clauze: optiuni la directive
    Va incepe sa execute in paralel cu toate threadurile
    disponibile zona de cod.
    Forteaza 5 threaduri.
    De fapt va aloca atatea threaduri cate procesoare are, deci
    poate sa aloca mai putine (5 e un maxim).
    a
    b
    c
    N elemente
    Pot fi impartite
    in mod egal intre
    threaduri
    istart iend
    A
    Alta directiva, for, generaaza threadurile automat:
    #pragma omp parallel
    #pragma omp for
    c[i]=a[i]+b[i];
    For(i=0, i<N, i++)
    Race condition: rezultat nedeterminist
    Diferenta fata de cod in afara "parallel": executata de mai multe
    threaduri, dar nu simultan
    Codul din afara "parallel" este executat o singura data doar de
    threadul master.
    Regiune critica: secventa de cod care nu poate fi executata la un
    moment dat decat de un singur thread
    La sfarsitul regiunii paralele este o bariera implicita; nu se iese din
    directiva parallel sau for pana cand n-au ajuns toate threadurile
    acolo
    Bariera: punct In program la care se asteapta toate threadurile sa
    ajunga inainte de a se trece mai departe
    #pragma omp critical
    {
    {
    #pragma omp barrier
    {
    }
    Obs:
    #pragma omp parallel for
    Iterativ:
    #include<stdio.h>
    #include<stdlib.h>
    #include <omp.h>
    static long num_steps = 10000;
    double step;
    void main()
    int I;
    double x,pi,sum=0.0;
    step = 1.0/(double)num_steps;
    for(i=1;i<num_steps;i++)
    x=(i-0.5)*step;
    sum=sum+4.0/(1.0+x*x);
    {
    }
    pi=step*sum;
    {
    }
    pentru paralelizare, s-ar putea pune sum= intr-o regiune critica
    altfel,
    un vector de sume si fiecare thread calculeaza suma lui
    sau,
    ce operatie se face la reducere (adunare) si cu ce variabila (sum)
    #pragma parallel for reduction(+:sum)
    Reducere = operatia de reunire a threadurilor
    Paralelizare:
    (in shell: ) export OMPC_NUM_PROCS=4
    (fara export-ul de mai sus, programul da eroare la rulare
    spunand ca nu poate aloca 4 threaduri, conform lui
    opm_set_num_threads(), ci doar unul)
    #include<stdio.h>
    #include<stdlib.h>
    #include <omp.h>
    static long num_steps = 10000;
    double step;
    int main()
    int i;
    double x,pi,sum=0.0;
    step = 1.0/(double)num_steps;
    omp_set_num_threads(4)
    {
    #pragma omp parallel for reduction (+:sum)
    for(i=1;i<num_steps;i++)
    x=(i-0.5)*step;
    sum=sum+4.0/(1.0+x*x);
    {
    }
    {
    pi=step*sum;
    }
    }


    ....................................





    Salut, am nevoie de putin ajutor cu un program in C. Am scris varianta secventiala si acum vreau sa il fac in paralel cu openmp. Codul arata ceva de genul.Am nevoie de o marire dependenta de numarul de threaduri, spre ex pt 2 threaduri sa ruleze de 2 ori mai repede,cum e si normal. Aceasta este doar bucata de cod din main care conteaza , mai sus am doar declaratii si citire din fisier. Daca se pricepe cineva si ma poate ajuta cu scrierea lui corecta, nu ma pricep asa bine cu openmp.Thx

    Cod:
    int an_curent=1;
    #pragma omp parallel shared(resurse,preturi,buget,cost_minim,costres_minim) private(i,j,k,l)
     while(an_curent <= nr_ani){
      //resetare valori ce tin costul,contorii resurselor
      for(i=0;i<nr_ani;i++){
        resurseA[i]=0;
        resurseB[i]=0;
        pretmaxA[i]=0;
        pretmaxB[i]=0;
      }
     
      for(i=0;i<n;i++)
       for(j=0;j<n;j++){
        cost_minim[i][j]=50000;
        costres_minim[i][j]=50000;
       }
      //activitati anuale
    #pragma omp for 
      for(i=0;i<n;i++)
       for(j=0;j<n;j++){
        //int cost_minim=100; //pastrez costul cel mai mic al resurselor complementare gasite
        int cost_curent=0; //costul resursei gasite la pasul curent
        int resursa_complement;
        if(resurse[i][j] == 0)
         resursa_complement=1;
        if(resurse[i][j] == 1)
         resursa_complement=0;
        //caut printre colonisti cine are resursa de tipul resursa_complement
        for(k=0;k<n;k++)
         for(l=0;l<n;l++){
          //caut cost complementar minim
          if(resurse[k][l] == resursa_complement){ //am gasit un colonist cu resursa necesara
           cost_curent=preturi[k][l] + dist(i,k,j,l);
           if(cost_curent < cost_minim[i][j]){
            //printf("fost cost=%d,nou cost=%d\n",cost_minim,cost_curent);
            cost_minim[i][j]=cost_curent;
           }
          }
          //caut costRes minim
          if(resurse[k][l] ==(1- resursa_complement)){ //am gasit un colonist cu resursa necesara
           cost_curent=preturi[k][l] + dist(i,k,j,l);
           if(cost_curent < costres_minim[i][j]){
            //printf("fost cost=%d,nou cost=%d\n",cost_minim,cost_curent);
            costres_minim[i][j]=cost_curent;
           }
          }
         }//end for k    
       }//end for i
    
      //verific cost vs buget pentru colonistul curent
    #pragma omp for
      for(i=0;i<n;i++)
       for(j=0;j<n;j++){
        int buget_curent=buget[i][j];
        if(cost_minim[i][j] > buget_curent){
         preturi[i][j]=preturi[i][j]+cost_minim[i][j] - buget[i][j];
         buget[i][j]=cost_minim[i][j];
         if(preturi[i][j] > pmax){
          resurse[i][j]=1-resurse[i][j];
          buget[i][j]=pmax;
          preturi[i][j]=(pmin + pmax)/2;
         }
        }
        if(cost_minim[i][j] < buget_curent){
         preturi[i][j]+=(cost_minim[i][j]-buget[i][j])/2;
         buget[i][j]=cost_minim[i][j];
         if(preturi[i][j] < pmin)
          preturi[i][j] = pmin;
         
         
        }
        if(cost_minim[i][j] == buget_curent){
         preturi[i][j]=costres_minim[i][j]+1;
         if(preturi[i][j] > pmax){
          resurse[i][j]=1-resurse[i][j];
          buget[i][j]=pmax;
          preturi[i][j]=(pmin + pmax)/2;
         } 
        }
       }
      //numar colonistii cu resurseA ,resp resurseB
    #pragma omp for
      for(i=0;i<n;i++)
       for(j=0;j<n;j++){
        if(resurse[i][j] == 0){
    #pragma omp atomic
         resurseA[an_curent-1]+=1;
        }
        if(resurse[i][j] == 1)
    #pragma omp atomic
         resurseB[an_curent-1]+=1;
       }
      //caut pretul maxim al resursei A resp al resurseiB
    #pragma omp for
      for(i=0;i<n;i++)
       for(j=0;j<n;j++){
        if(resurse[i][j] == 0){
         if(preturi[i][j] > pretmaxA[an_curent-1])
          pretmaxA[an_curent-1]=preturi[i][j];
        }
        if(resurse[i][j] == 1){
         if(preturi[i][j] > pretmaxB[an_curent-1])
          pretmaxB[an_curent-1]=preturi[i][j];
        } 
       }
      char line[128];
      sprintf(line,"%d %d %d %d\n",resurseA[an_curent-1],pretmaxA[an_curent-1],resurseB[an_curent-1],pretmaxB[an_curent-1]);
      writeToFile(out,line);
      if(an_curent==nr_ani)
    #pragma omp for
       for(i=0;i<n;i++){
        for(j=0;j<n;j++){
         sprintf(line,"(%d,%d,%d) ",resurse[i][j],preturi[i][j],buget[i][j]);
         writeToFile(out,line);
        }
        writeToFile(out,"\n");
       }
      an_curent++;
     }
    ansin este deconectat
    Răspunde cu citat Top
    Necitit 03.11.2012, 22:45#2
    Avatarul lui Caesar
    Senior Member
    Locație: Iasi
    Posturi: 430
    Putere Rep: 12 
    Reputație: 351
    Caesar are multe de care să fie mândruCaesar are multe de care să fie mândruCaesar are multe de care să fie mândruCaesar are multe de care să fie mândru
    Nou
    Ok, să-ți scriu câteva idei. Începem cu începutul, și anume:

    1. Executarea în paralel a unui set de operații pe n thread-uri nu va fi niciodată de n ori mai rapidă; aceasta findcă crearea acestor thread-uri consumă și ea timp. Astfel, un spor de performanță se poate observa doar pentru thread-uri cu un număr mare/foarte mare de pași. În cazul în care se crează tread-uri separate pentru un număr mic de operații, se vor înregistra scăderi de performanță.

    2. Codul de mai sus... nu e foarte ordonat; iar variabilele nu au nume foarte sugestive. Încearcă, în primul rând, să-l grupezi în câteva funcții separate; e destul de greu datorită operațiilor și for-urilor paralele, dar măcar pașii principali ai algoritmului.

    3. Strâns legat de (2), cred că tu scrii cod C, iar în exemplul tău ai câteva artificii care sunt permise doar în C++, și anume declararea unor variabile locale în corpul funcției, dar nu la începutul acesteia.

    4. Ne-ar ajuta enunțul problemei (cel puțin pentru a înțelege denumirile variabilelor).

    De obicei funcționează varianta cu rezolvarea problemei inițial secvențial și-apoi modificare în paralel.

    1. Nu prea ajută creare de operații paralele în interiorul altor operații paralele; trebuie ținut oarecum cont și de faptul că un procesor are un număr limitat de nuclee și thread-uri (fizice). Astfel un număr foarte mare de thread-uri în paralel nu prea ajută; mai mult, trebuiesc evitate operațiile de creare și distrugere ale acestora.
    Ca și obiectiv/mod de rezolvare: atunci când ai un număr de câteva for-uri (sau alte instrucțiuni repetitive) imbricate, trebuie să-ncerci să faci paralel doar for-ul de la exterior (sau cât mai la exterior posibil, în funcție de algoritm).

    2. Trebuiesc identificate resursele (variabilele) folosite în operațiile executate în paralel și clasificarea acestora în funcție de modul în care acestea sunt folosite:
    - resurse folosite individual (private) pe fiecare thread în parte, de exemplu contorii (i, j) folositi pentru parcurgerea unui tablou;
    - resurse comune (de obicei shared) pe mai multe thread-uri, de exemplu un tablou parcurs în paralel.

    3. Se pune întrebarea: rezultatele obținute pe un thread sunt direct influențabile de operațiile executate pe alt thread? Se pot obține astfel rezultate false?
    Mi-e greu să fac această întrebare clară. Ține în primul rând de variabilele shared; dacă acestea sunt modificate pe un thread, rezultatele calculelor efectuate pe un al doilea thread vor mai fi corecte, presupunând că acesta a luat valorile modificate?
    În plus, dacă nu se specifică (prin niște directive mai pompoase) ordinea în care se vor executa thread-urile, aceasta va fi aleatoare/necunoscută.

    * De menționat că este de preferat folosirea #parallel for în locul unui simplu #parallel, acolo unde este posibil; în cazul #parallel for, contorul din interiorul forului este implicit variabilă private.


    Sunt sigur că am menționat mai multe lucruri pe care, de voie, de nevoie, le știai deja, dar e bine să le ai notate undeva, să fie clare, să nu le uiți.
    __________________
    HARDWARE = Parte a unui calculator pe care o lovesti cand apar probleme de software.

    Thursday, July 4, 2019

    Punctaj

    Punctaj curs 15.10.2018 Algoritmi paraleli si distribuiti •
    Nota: 10 = 3 (Laborator) + 3 (Teme) + 4 (Examen)
    Laborator+Teme >= 3 
    Examen >= 2 
    Prez. Lab. >= 7
    Laborator: activitate(2) + verificare (1)
    Teme: 3 teme (1/per tema)

    Obiectiv Însușirea competentelor necesare pentru rezolvarea problemelor prin solutii paralele sau distribuite
    Ce este calculul paralel ? Dar distribuit ? 
    • Calcul paralel = executia simultana (concurenta) a mai multor parti ale unui program/aplicatii
    • Calcul distribuit = executia in sisteme diferite (cu resurse diferite) a partilor unui program/aplicatii

     Calculul paralel 
    • abordarea serială:

    https://acs.curs.pub.ro/2018/mod/folder/view.php?id=5427 
     APD_CA_CC.zip 
     APD_CB.zip

    Elena Apostol