Skoči na vsebino

Vzporedenje zank

Zelo veliko računsko intenzivnih programov večino izvajanja opravi v zankah, zato je pomembno, da znamo računanje v zankah razdeliti med posamezne niti tako, da enakomerno obremenimo procesorje, jedra in strojne niti.

Vzporedenje ene zanke

Najprej se lotimo enostavnega primera zanke, katere posamezni obrati so povsem neodvisni med seboj: napišimo torej program, ki izpiše števila od 1 do n v poljubnem vrstnem redu, pri tem pa seveda želimo uporabiti nitenje. To najlažje dosežemo s for zanko, katere vzporedenje znotraj nitenja dosežemo z ukazom #pragma omp for. Ta direktiva zahtreva, da ji sledi for zanka, povzroči pa, da se posamezni obrati zanke enakomerno porazdelijo med niti. Enako kot niti pri ukazu #pragma omp parallel se posamezni obrati zanke izvajajo povsem neodvisno, niti pa se na koncu for stavka sinhronizirajo ob implicitni sinhronizacijski pregradi.

Ob predpostavki, da posamezni obrati for zanke zahtrevajo (približno) enako mnogo računanja, je s tem celotno računanje, ki ga mora opraviti for zanka, (približno) enakomerno porazdeljeno.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
#include <stdio.h>
#include <omp.h>

int main (int argc, char *argv[]) {
  int n; sscanf (argv[1], "%d", &n);
  #pragma omp parallel
  {
    #pragma omp for
      for (int i = 1; i <= n; i++) {
        printf ("[%d:%d] ", omp_get_thread_num (), i);
      }
  }
  printf ("\n");
  return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
#include <stdio.h>
#include <omp.h>

int main (int argc, char *argv[]) {
  int n; sscanf (argv[1], "%d", &n);
  #pragma omp parallel for
    for (int i = 1; i <= n; i++)
      printf ("[%d:%d] ", omp_get_thread_num (), i);
  printf ("\n");
  return 0;
}

Če se v nitenem delu kode izvede le for zanka, potem lahko oba ukaza, #pragma omp parallel in #pragma omp for združimo v en sam ukaz #pragma omp parallel loop, kot je to narejeno v programu nums-2.c.

Vaja

Program nums-1.c je koristno zagnati večkrat in pri tem uporabiti različno število strojnih in programskih niti za različne vrednosti n. Storite to.

Vaja

Kaj se zgodi, če v 6. vrstici programa nums-2.c izpustimo for? Zakaj?
(Najprej premislite in odgovorite, šele nato preverite.)

Vaja

Prepišite program nums-2.c tako, da izpustite for v 6. vrstici, delovanje programa pa ostane enako.

Vaja

Napišite programa za množenje skalarja z vektorem in za seštevanje vektorjev.

Vzporedenje večih gnezdenih zank

Gnezdenje zank je zelo pogosto, zato na hitro poglejmo nekaj dodatnih možnosti za porazdelitev obratov posameznih zank med niti. Prikazali bomo vzporedenje dveh gnezdenih zank, kar zadošča za razlago vseh idej, ki so potrebne tudi za primere z več kot dvema gnezdenima zankama.

Vzporedenje zgolj ene gnezdene zanke

Namesto izpisa vseh števil od 1 do n izpišimo vse pare od (1,1) do (n,n) v poljubnem vrstnem redu. To seveda naredimo z dvema gnezdenima zankama, za začetek pa porazdelimo bodisi obrate zunanje zanke (program pairs-1.c) bodisi obrate notranje zanke (program pairs-2.c).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
#include <stdio.h>
#include <omp.h>

int main (int argc, char *argv[]) {
  int n; sscanf (argv[1], "%d", &n);
  #pragma omp parallel for
    for (int i = 1; i <= n; i++)
      for (int j = 1; j <= n; j++)
        printf ("%d: (%d,%d)\n", omp_get_thread_num (), i, j);
  return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
#include <stdio.h>
#include <omp.h>

int main (int argc, char *argv[]) {
  int n; sscanf (argv[1], "%d", &n);
  for (int i = 1; i <= n; i++)
    #pragma omp parallel for
      for (int j = 1; j <= n; j++)
        printf ("%d: (%d,%d)\n", omp_get_thread_num (), i, j);
  return 0;
}

Nitenje programov pairs-1.c in pairs-2.c prikazujeta sliki 8 in 9.

Slika 8: Nitenje programa pairs-1.c.

Slika 9: Nitenje programa pairs-2.c.

Vaja

Brez zagona programov pairs-1.c in pairs-2.c napovejte njun izpis.
Svoji napovedi preverite z zagonom programov.

Vzporedenje gnezdenih zank ločeno

Ukaz #pragma omp parallel for lahko uporabimo tudi nad obema zankama hkrati:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
#include <stdio.h>
#include <omp.h>

int main (int argc, char *argv[]) {
  int n; sscanf (argv[1], "%d", &n);
  omp_set_nested (1);
  #pragma omp parallel for
    for (int i = 1; i <= n; i++) {
      #pragma omp parallel for
        for (int j = 1; j <= n; j++) {
          printf ("%d/%d: (%d,%d)\n",
                  omp_get_thread_num (),
                  omp_get_ancestor_thread_num (1),
                  i, j);
        }
    }
  return 0;
}

V tem primeru se med izvajanjem vzporedenje zunanje zanke izvede enkrat, vzporedenje notranje zanke pa se izvede v vsakem obratu zunanje zanke. To pomeni, da se najprej ustravi določeno število niti za izvajanje obratov zunanje zanke, vsaka od teh niti pa se naprej razdeli na več niti za izvajanje notranje zanke. To je prikazano na sliki 10.

Slika 10: Nitenje programa pairs-3.c.

V programu pairs-3.c bodimo pozorni na nekaj podrobnosti:

  • Če želimo hkrati vzporediti zunanjo in notranjo zanko, moramo to posebej omogočiti. To lahko naredimo s klicem funkcije omp_set_nested (kot je prikazano v programu pairs-3.c), lahko pa bi ta klic tudi izpustili, v ukazni lupini pa bi nastavili spremenljivko OMP_NESTED na vrednost true.
  • Število niti, med katere se bodo porazdelili obrati posamezne vzporedene zanke, lahko določimo za vsako zanko posebej s tremi pristopi, ki smo jih opisali pri nitenju programa z ukazom #pragma omp parallel, tu dodajmo le, da v ukazni lupini lahko na primer uporabimo nastavitev OMP_NUM_THREADS=3,4.
  • Funkcija omp_get_thread_num vrne oznako niti znotraj nazadnje ustvarjene skupine niti. V programu pairs-3.c zato vrne oznako niti notranje zanke. Da dobimo oznako niti zunanje zanke, moramo uporabiti funkcijo omp_get_ancestor_thread_num.

Vaja

Brez zagona programa pairs-3.c napovejte njegov izpis (in ne goljufajte spet, prosim).
Svojo napoved preverite z zagonom programa.

Vaja

Poženite program pairs-3.c tako, da se bo zunanja zanka izvedla s 4 nitmi, notranja pa s 3 nitmi.

Vaja

Spremenite program pairs-3.c tako, da se bo zunanja zanka izvedla s toliki nitmi, kot določa spremenljivka OMP_NUM_THREADS, vsak obrat notranje zanke pa se bo izvedel i-krat (kjer je i indeks zunanje zanke).

Vaja

Prepišite program iz prejšnje vaje tako, da namesto ukazov #pragma omp parallel for uporabite le ukaz #pragma omp parallel.

Vzporedenje gnezdenih zank skupaj

Z določilom collapsed lahko določimo, koliko naslednjih zank naj program izvede vzporedno z eno samo skupino niti. Če tako določilo uporabimo pri izpisu parov števil tako, kot je prikazano v programu pairs-4.c, se bo vseh n * n obratov notranje zanke, za vse i in j od 1 do n, v enem koraku nitenja porazdelilo med niti ene skupine. Nitenje programa pairs-4.c je zato enako nitenju programa [hello-world-1.c], ki ga prikazuje slika 5.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
#include <stdio.h>
#include <omp.h>

int main (int argc, char *argv[]) {
  int n; sscanf (argv[1], "%d", &n);
  #pragma omp parallel for collapse(2)
    for (int i = 1; i <= n; i++)
      for (int j = 1; j <= n; j++)
        printf ("%d: (%d,%d)\n", omp_get_thread_num (), i, j);
  return 0;
}

Vaja

Brez zagona programa pairs-3.c napovejte njegov izpis (ok, vdam se).
Svojo napoved preverite z zagonom programa.

Vaja

Prepišite program pairs-4.c, da namesto ukaza #pragma omp parallel for uporabite le ukaz #pragma omp parallel.

Primerjava različnih načinov vzporedenja gnezdenih zank

Vsak od različnih načinov vzporedenja gnezdenih zank pride kdaj prav, zato je nujno ne le, da jih poznamo, pač pa da jih tudi razlikujemo.

Razliko si oglejmo na primeru izpisa parov. Naj velja n=6 in OMP_NUM_THREADS=4 (in OMP_NESTED=true):

  • Program pairs-1.c z vzporedno zunanjo zanko razdeli vseh 36 parov med niti tako, kot je prikazano na sliki 11 (levo). Delitev je precej neenakomerna, res pa je, da se s povečevanjem n-ja (oziroma razmerjem med n-jem in številom niti) razlika med bolj in manj obremenjenimi nitmi sorazmerno zmanjšuje.
  • Program pairs-3.c, v katerem sta obe gnezdeni zanki ločeno vzporedeni, razdeli vseh 36 parov med niti tako, kot je prikazano na sliki 11. V primerjavi s prejšnjim načinom je razmerje med obremenjenostjo niti zunanje zanke enako, le da je tu na delu večje število niti.
  • Program pairs-4.c, v katerem sta obe gnezdeni zanki vzporedeni skupaj, je delitev bolj enakomerna.

Slika 11: Različna delitev obratov notranje zanke med niti.

Ob tem moramo še enkrat poudariti, da veljajo zgoraj navedene ugotovitve glede obremenjenosti posameznih niti le ob predpostavki, da je računska zahtevnost posameznih obratov notranje zanke vsaj približno enaka.

Vaja

Kakšna je slika razdelitve parov po nitih za program pairs-2.c?

Projekt

John Horton Conway je izumil Igro življenja. Igra zahteva ravnino n * m kvadratnih celic. Vsaka celica je bodisi živa bodisi mrtva. Na začetku je dana prva generacija celic, za katero je natančno določeno, katera celica je živa in katera je mrtva. Pri prehodu iz ene v drugo generacijo veljajo naslednja pravila:

  • Živa celica z manj kot dvema živima sosedoma umre od koronske depresije.
  • Živa celica z več kot tremi živimi sosedi umre zaradi neupoštevanja socialne distance.
  • Mrtva celica s tremi živimi sosedi od čiste radovednosti kar oživi.

Vsaka celica ima 8 sosedov (4 po robovih in 4 preko ogljišč).

Napišite program, ki iz začetne generacije izračuna 10, 100, 1000... generacijo in pri tem vse strojne niti, ki so v sistemu na voljo, obremeni kar se da enakomerno.