Vzporedenje opravil

Veliko izračunov lahko zapišemo kot zanke, ki so primerne za vzporedenje, ki smo si ga že ogledali. Nekaterih problemov in predvsem algoritmov za reševanje teh problemov pa ne moremo 'naravno' preslikati v zanke, zato potrebujemo drugačen pristop k vzporedenju nekaterih programov. Ta pristop predstavljajo opravila, ki jih lahko ustvarimo in poženemo med izvajanjem programa, da se izvedejo vzporedno z že obstoječimi deli programa.

Ponovno si to oglejmo na primeru seštevanja števil od 1 do n. V programu ints-sum-2.c ustvarimo v ukazni vrstici določeno število opravil in v vsakem opravilu seštejemo podinterval števil v spremenljivko local_sum, nato pa vsoto intervalov seštejemo z uporabo atomarne operacije v spremenljivko sum.

Vsako opravilo posebej ustvarimo z ukazom #pragma omp task. Ustvarjeno opravilo zaživi povsem neodvisno in je dodeljen eni od niti, da ga izvede. Vsa opravila se morajo končati pred izstopom iz območja nitenja, saj po izstopu niti, ki ta opravila izvajajo, ne obstajajo več.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <stdio.h>
#include <unistd.h>
#include <omp.h>

int main (int argc, char *argv[]) {
  int max; sscanf (argv[1], "%d", &max);
  int tasks; sscanf (argv[2], "%d", &tasks);
  if (max % tasks != 0) return 1;
  int sum = 0;
  #pragma omp parallel
    {
      #pragma omp single
        for (int t = 0; t < tasks; t++) {
          #pragma omp task
            {
              sleep (1);
              int local_sum = 0;
              int lo = (max / tasks) * (t + 0) + 1;
              int hi = (max / tasks) * (t + 1) + 0;
              printf ("%d: %d..%d\n", omp_get_thread_num(), lo, hi);
              for (int i = lo; i <= hi; i++)
                local_sum = local_sum + i;
              #pragma omp atomic
                sum = sum + local_sum;
            }
        }
    }
  printf ("%d\n", sum);
  return 0;
}

Sam ukaz #pragma omp task je razmeroma enostaven, bolj je pomembno, v kakšnem vzorcu ga je smiselno uporabiti:

  • Kot lahko vidimo v programu ints-sum-2.c, ge seveda uporabimo znotraj območja nitenja, da se novo ustvarjeno opravilo lahko postavi v vrsto, da ga bo prevzela ena od niti programa.

  • V programu ints-sum-2.c je ustvarjanje novih opravil narejeno s for zanko, ki je zaprta v del programa, ki se izvede v eni sami niti (to določimo z ukazom #pragma omp single). Če bi se ta for zanka izvedla v vseh nitih, bi vse niti ustvarile kopije istih opravil: računanja bi bilo preveč, rezultat pa bi bil napačen.

Vaja

Vsa opravila v programu ints-sum-2.c zahtevajo približno enako časa, da se izvedejo - največji del tega časa prespijo v klicu funkcije sleep, potem pa še malce računajo. Spremenite program ints-sum-2.c tako, da bodo vsa opravila zahtevala različno mnogo časa in opazujte, kako se s tem spremeni čas izvajanja celotnega programa.

Opravila so posebej primerna za vzporedenje algoritmov, ki so v osnovi rekurzivni, podproblemi, na katere taki algoritmi razbijejo osnovni problem, pa so vsaj do neke mere neodvisni. Kot primer si oglejmo vzporedno izvedbo hitrega urejanja.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <omp.h>

int compare (const char *str1, const char *str2) {
  int len1 = strlen (str1);
  int len2 = strlen (str2);
  if (len1 == len2) return strcmp (str1, str2);
  return len1 - len2;
}

void par_qsort (char **data, int lo, int hi,
                int (*compare)(const char *, const char*)) {
  if (lo > hi) return;
  int l = lo;
  int h = hi;
  char *p = data[(hi + lo) / 2];
  while (l <= h) {
    while (compare (data[l], p) < 0) l++;
    while (compare (data[h], p) > 0) h--;
    if (l <= h) {
      char *tmp = data[l]; data[l] = data[h]; data[h] = tmp;
      l++; h--;
    }
  }
  #pragma omp task final(h - lo < 1000)
    par_qsort (data, lo, h, compare);
  #pragma omp task final(hi - l < 1000)
    par_qsort (data, l, hi, compare);
}

int main (int argc, char *argv[]) {
  int seed = 0;
  int num_strings = 100;
  char **strings;
  if (argc > 1) sscanf (argv[1], "%d", &num_strings);
  if (argc > 2) sscanf (argv[2], "%d", &seed);
  srandom (seed);
  strings = (char**)malloc (num_strings * sizeof (char*));
  for (int s = 0; s < num_strings; s++) {
    int len = random() % 64;
    strings[s] = (char*)malloc ((len + 1) * sizeof (char));
    for (int c = 0; c < len; c++)
      strings[s][c] = 'A' + random() % 26;
    strings[s][len] = '\0';
  }
  double t = omp_get_wtime ();
  #pragma omp parallel
    #pragma omp single
      par_qsort (strings, 0, num_strings - 1, compare);
  printf ("TIME: %lf\n", omp_get_wtime () - t);
  return 0;
}

Vaja

Program qsort-1.c za hitro urejanje z uporabo n strojnih niti sploh ne deluje n-krat hitreje. Zakaj?
(Namig: Amdahlov zakon.)

Projekt

Napišite program za izračun Mandelbrotove množice in izriz na pravokotnem delu kompleksne ravnine. Učinkovit program mora predvideti, da je izračun te množice na različnih delih kompleksne ravnine različno zahteven. To lahko rešite z ustreznim razvrščanjem obratov zank, v katerih izračunate barvo posamezne točke v ravnini, med niti programa ali pa z delitvijo pravokotnega dela kompleksne ravnine na pravokotno mrežo, v kateri vsak pravokotnik izračunate z enim opravilom. Poskusite z obema pristopoma.