Unified Parallel C

(Przekierowano z UPC)
Dostęp do zasobów ICM
Konto użytkownika
Grant obliczeniowy
Uruchamianie obliczeń
Oprogramowanie
Pomoc
Poradniki różne

Spis treści

Wstęp

Unified Parallel C (UPC) to bardzo wygodne w użyciu rozszerzenie języka C służące do programowania równoległego. Oparte jest ono na modelu programowania równoległego PGAS (Partitioned Global Address Space), czyli modelu, w którym pamięć jest fizycznie rozproszona, a logicznie współdzielona (modele programowania równoległego opisane zostały przez Łukasza Bolikowskiego w Biuletynie 3). Podobnie jak CAF dla Fortranu (rozszerzenie opisane w artykule Michała Łopuszyńskiego w Biuletynie 4), UPC to bardzo wygodne w użyciu narzędzie pozwalające tworzyć wydajne programy.

Najbardziej popularną implementacją UPC jest Berkeley UPC rozwijane w ramach wspólnego projektu przez University of California, Berkeley oraz Lawrence Berkeley National Laboratories. Berkeley UPC jest stale rozwijane i może być używane na wielu architekturach (m.in. klastry x86, systemy IBM-a, w tym Blue Gene/P oraz /Q oraz systemy firmy Cray).

Pierwszy program w UPC

Nasz pierwszy program wypisywać będzie komunikaty Hello World z każdego procesora (wraz z numerami procesów oraz liczbą tych procesów). Zaprogramowanie takiego zadania w UPC jest bardzo proste:

1:      #include <upc_relaxed.h>
2:      #include <stdio.h>
3:
4:      void main(){
5:              printf("Hello World from THREAD %d (of %d THREADS)\n",MYTHREAD,THREADS);
6:      }

Każdy procesor (tutaj nazywany wątkiem - THREAD) uruchamia równolegle własną kopię powyższego programu. Pierwsza linia kodu, poprzez dołączenie pliku nagłówkowego upc_relaxed.h, specyfikuje sposób korzystania z pamięci. W UPC sposoby obsługi pamięci są dwa:

  • upc_relaxed.h - procesy mogą odczytywać zmienne współdzielone dowolnie w każdej chwili. Korzystanie z tego sposobu jest preferowane

, gdyż umożliwia kompilatorom lepszą optymalizację.

  • upc_strict.h - współdzielone zmienne i dane synchronizowane są za każdym razem przed dostępem do nich. Oznacza to, że jeśli współdzielona zmienna jest aktualnie modyfikowana przez jeden proces, pozostałe procesy będą czekać aż do synchronizacji przed odczytaniem jej wartości.

Dalsza część powyższego programu jest zwykłym kodem języka C. Do wypisania komunikatu używamy funkcji printf. Korzystamy jednak z dwóch zmiennych dostępnych dzięki załączeniu pliku nagłówkowego UPC:

  • THREADS - oznacza liczbę procesów, które uczestniczą w aktualnym uruchomieniu programu
  • MYTHREAD - oznacza numer procesu aktualnie uruchomionego

Dla lepszego wyjaśnienia znaczenia zmiennych THREADS i MYTHREAD prześledźmy następujący przykład:

1:      #include <upc_relaxed.h>
2:      #include <stdio.h>
3:
4:      void main(){
5:              if(MYTHREAD==0){
6:                      printf("Starting execution at THREAD %d\n",MYTHREAD);
7:              }
8:              printf("Hello World from THREAD %d (of %d THREADS)\n",MYTHREAD,THREADS);
9:      }

Program ten jest bardzo podobny do wcześniejszego, z tą różnicą, że warunek zawarty w instrukcji if specyfikuje, iż proces o numerze 0 dodatkowo wywoła funkcję printf wypisując na standardowe wyjście komunikat "Starting execution at THREAD 0".

Równoległe pętle for - upc_forall

W UPC mamy mozliwość implementacji pętli, których kolejne iteracje uruchamiane będą przez różne procesy. Struktura wywołania takiej pętli jest następująca:

upc_forall( wyrażenie; wyrażenie; wyrażenie; wskazanie)

Czwarty parametr pętli upc_forall może być albo liczbą naturalną tłumaczoną na (liczba % THREADS); lub adresem który wskazuje na konkretny proces do którego adres ten jest przypisany. Oto dwa krótkie przykłady użycia upc_forall:

upc_forall(i=0;i<N;i++;i) {
        printf("THREAD %d (of %d THREADS) performing iteration %d\n",MYTHREAD,THREADS,i);
}

Powyższa pętla wypisze numery procesów wraz z liczbą reprezentującą numer iteracji przez te procesy wykonywanej. Iteracja o numerze i będzie wykonywana przez proces o numerze i % THREADS . W drugim przykładzie widzimy, iż proces który ma wykonywać daną iterację może zostać również wskazany przez adres pamięci do niego przydzielony:

1:      #include <upc_relaxed.h>
2:      #include <stdio.h>
3:      #define N 10
4:      shared [2] int arr[10];
5:
6:      int main() {
7:              int i=0;
8:              upc_forall(i=0;i<N;i++;&arr[i]) {
9:                      printf("THREAD %d (of %d THREADS) performing iteration %d\n",MYTHREAD,THREADS,i);
10:             }
11:             return 0;
12:     }

Linijka:

4:      shared [2] int arr[10];

definiuje tablicę liczb typu integer o wymiarze 10. Pamięć ta rozdzielona jest pomiędzy procesy, po 2 elementy tablicy dla każdego procesu cyklicznie. W deklaracji tej tablicy kluczowe jest użycie słówka shared. W dalszej części artykułu można przeczytać o nim trochę więcej. Czwarty parametr pętli upc_forall to adres kolejnych elementów tablicy arr. Adres ten tłumaczony jest na identyfikator procesu któremu dany adres jest przypisany. Wybrany proces realizuje następnie kod przypisany dla danej iteracji. Oznacza to, że iteracja i wykonywana jest przez proces do którego przypisany jest adres &arr[i].

Zmienne współdzielone - wyrażenie shared

Aby zrozumieć wszystkie oznaczenia związane z wyrażeniem shared należy skomentować krótko pomysł, który kryje się za modelem pamięci fizycznie rozproszonej, logicznie współdzielonej. Otóż przestrzeń pamięciowa w UPC dzieli się na prywatną i współdzieloną. Każdy proces ma swoją własną przestrzeń prywatną oraz porcję przestrzeni współdzielonej. Prywatna pamięć obsługiwana jest tak jak w zwykłym języku C. Cała przestrzeń współdzielona podzielona jest na części, z których każda przypisana jest logicznie do przestrzeni pamięciowej jednego z procesów. Widać to na poniższym rysunku:

Pamięć współdzielona i prywatna.
Rys.1. Pamięć współdzielona i prywatna.


W dalszej części będę opisywał przykłady tablic współdzielonych logicznie rozdystrybuowanych w blokach po procesach. Oznacza to tak naprawdę tyle, iż tablica taka jest widziana przez wszystkie procesy, natomiast fizycznie przechowywana jest w pamięci przypisanej do jednego z procesów. Aby zdefiniować współdzieloną pamięć musimy użyć słówka kluczowego shared. Mamy do dyspozycji sporo kombinacji:

1:     int local_counter;                  //prywatna zmienna 
2:     shared int global_counter;          //współdzielona zmienna
3:     shared int array1[N];               //współdzielona tablica
4:     shared [N/THREADS] int array2[N];   //współdzielona tablica
5:     shared [] int array3[N];            //współdzielona tablica
6:     shared int *ptr_a;                  //prywatny wskaźnik do współdzialonej pamięci
7:     shared int *shared ptr_c;           //współdzielony wskaźnik do współdzielonej pamięci

Komentarza wymaga różnica pomiędzy trzema zdefiniowanymi tablicami array1, array2, array3. Zwykle polecenie shared ma następującą formę:

shared [rozmiar_bloku] typ nazwa_zmiennej

Powyższy zapis należy czytać w następujący sposób: zmienna o nazwie nazwa_zmiennej o typie typ jest współdzielona pomiędzy wszystkimi procesami i zostaje rozdystrybuowana cyklicznie pomiędzy wszystkimi procesami w blokach wielkości rozmiar_bloku. Jeśli wielkość bloku nie jest podana wówczas przyjmowana jest wielkość 1. Nieskończoną wielkość bloku oznaczamy []. Na kolejnych trzech szkicach pokazany jest sposób rozdystrybuowania pamięci pomiędzy procesami dla tablic array1, array2, array3.

Rozłożenie elementów tablicy array1 po procesach z rozmiarem bloku równym 1 dla N=9 oraz THREADS=3.
Rys.2. Rozłożenie elementów tablicy array1 po procesach z rozmiarem bloku równym 1 dla N=9 oraz THREADS=3.


Rozłożenie elementów tablicy array2 po procesach z rozmiarem bloku równym N/THREADS dla N=10 oraz THREADS=3.
Rys.3. Rozłożenie elementów tablicy array2 po procesach z rozmiarem bloku równym N/THREADS dla N=10 oraz THREADS=3.


Rozłożenie elementów tablicy array3 po procesach z nieskończonym rozmiarem bloku dla N=10 oraz THREADS=3.
Rys.4. Rozłożenie elementów tablicy array3 po procesach z nieskończonym rozmiarem bloku [] dla N=10 oraz THREADS=3.

Synchronizacja procesów i dostępu do pamięci w UPC

Bariery upc_barrier

Polecenie upc_barrier służy do synchronizacji procesów. Umieszczenie go w kodzie oznacza tak naprawdę postawienie bariery w kodzie, tzn. żaden proces nie ma prawa przekroczyć bariery (linii w kodzie) dopóki wszystkie procesy do niej nie dotrą. Bariery wykorzystywane są najczęściej gdy występuje zależność danych pomiędzy procesami. Oto prosty przykład:

1:      #include <upc_relaxed.h>
2:      #include <stdio.h>
3:
4:      shared int a=0;
5:      int b;
6:
7:      int computation(int temp) {
8:              return temp+5;
9:      }
10:
11:     int main(){
12:             int result=0, i=0;
13:             do {
14:                     if(MYTHREAD==0) {
15:                             result=computation(a);
16:                             a=result*THREADS;
17:                     }
18:                     upc_barrier;
19:                     b=a;
20:                     printf("THREAD %d: b=%d\n",MYTHREAD,b);
21:                     i++;
22:             } while(i<4);
23:             return 0;
24:     }

W linii 16 powyższego kodu procesor o numerze 0 uaktualnia wartość zmiennej a, współdzielonej przez wszystkie procesy. W linii 19 wszystkie procesy dokonują uaktualnienia swojej prywatnej zmiennej b przypisując im aktualną wartość zmiennej a. Zauważmy, że gdybyśmy nie umieścili bariery w linii 18 wówczas nie mielibyśmy gwarancji, że wszystkie prywatne zmienne b zostały uaktualnione najnowszą wartością zmiennej a.

Blokowanie dostępu do zmiennej - upc_lock/upc_unlock

Dzięki użyciu blokad upc_lock/upc_unlock możemy uzyskać gwarancję, że pewna zmienna nie będzie czytana przez proces jeśli jest w danej chwili uaktualniana przez inny proces. Składnia oraz sposób użycia blokad zobrazowany jest w przykładzie w następnej sekcji.

No dobrze, ale jak to wszystko wykorzystać? Prosty przykład

Aby nawiązać do artykułu o CAF zaprezentuję implementację tego samego algorytmu, tzn. algorytmu obliczającego liczbę Pi ze wzoru: \pi = 4 \int_0^1 \frac{1}{1+x^2} i całkowania numerycznego metodą prostokątów.

Wersja szeregowa takiego programu wygląda następująco:

//Przyklad szeregowy - calkowanie numeryczne
//Obliczanie liczby Pi
#include<math.h>
#define N 1000000
#define f(x) (1.0/(1.0+x*x))

float pi=0.0;
void main(void)
{
        int i;

        for(i=0;i<N;i++)
                pi+=(float) f( (0.5+i)/(N) );
        pi*=(float)(4.0/N);

        printf("PI=%f\n",pi);
}

Wersja równoległa zaimplementowana przy pomocy UPC wygląda tak:

//Przyklad UPC - calkowanie numeryczne
//Obliczanie liczby Pi
#include<upc_relaxed.h>
#include<math.h>
#define N 1000000
#define f(x) (1.0/(1.0+x*x))

upc_lock_t *l;
shared float pi=0.0;
void main(void)
{
        float local_pi=0.0;
        int i;
        l=upc_all_lock_alloc();

        upc_forall(i=0;i<N;i++;i)
                local_pi+=(float) f( (0.5+i)/(N) );
        local_pi*=(float)(4.0/N);

        upc_lock(l);
        pi+=local_pi;
        upc_unlock(l);

        upc_barrier;
        if(MYTHREAD==0) printf("PI=%f\n",pi);
        if(MYTHREAD==0) upc_lock_free(l);
}

Przykład ten jest bardzo fajny, gdyż widać tutaj zarówno użycie bariery upc_barrier jak i zabezpieczenia upc_lock . Przed równoczesnym dostępem z więcej niż jednego procesora zabezpieczona jest współdzielona zmienna pi.

UPC w ICM

W przeszłości UPC w ICM dostępne było na systemach firmy Cray (m.in. na tornado czyli systemie Cray X1e). Cray nadal wspiera UPC i razem z systemami obliczeniowymi dostarcza własne kompilatory języka UPC.

Obecnie UPC dostępny jest w ICM na systemach Boreasz, Nostromo oraz Hydra.

Korzystanie z UPC na Nostromo

Aby skorzystać z UPC na systemie Nostromo należy w pierwszej kolejności załadować odpowiedni moduł:

module load upc


Po załadowaniu modułu dostępne są m.in. narzędzia upcc oraz upcrun, wraz ze swoimi stronami man.

Aby skompilować kod napisany w języku UPC wywołujemy n.p.:

upcc program.upc -o program.x

Uruchomienie binarki następuje poprzez odpowiednie wywołanie narzędzia upcrun, n.p.:

upcrun -N 2 -n 32 ./program.x

Powyższa komenda uruchomi program.x za pomocą 32 wątków UPC rozrzuconych równomiernie na dwóch węzłach. Oczywiście, musimy najpierw zapewnić sobie dostępność węzłów obliczeniowych.

Korzystanie z UPC na Boreasz-u

Aby skorzystać z UPC na systemie Boreasz należy w pierwszej kolejności załadować odpowiedni moduł:

module load upc

Po załadowaniu modułu dostępne są m.in. narzędzia upcc oraz upcrun, wraz ze swoimi stronami man.

Aby skompilować kod napisany w języku UPC wywołujemy n.p.:

upcc program.upc -o program.x

Uruchomienie binarki następuje poprzez odpowiednie wywołanie narzędzia upcrun, n.p.:

upcrun -N 2 -n 32 ./program.x

Powyższa komenda uruchomi program.x za pomocą 32 wątków UPC rozrzuconych równomiernie na dwóch węzłach. Oczywiście, musimy najpierw zapewnić sobie dostępność węzłów obliczeniowych. Można to zrobić np. przy użyciu następującego skryptu kolejkowego:

#@ job_name = upc_test
#@ output = upc.out
#@ error = upc.err
#@ account_no = GRANT
#@ class = kdm
#@ node = 2
#@ tasks_per_node = 32
#@ wall_clock_limit = 00:25:00
#@ network.MPI = sn_all,not_shared,US,HIGH
#@ environment = COPY_ALL
#@ job_type = parallel
#@ queue
module load upc
upcrun -n 64 ./program.x

Korzystanie z UPC na Hydrze

Aby skorzystać z UPC na systemie Hydrze należy w pierwszej kolejności załadować odpowiedni moduł:

module load upc

Po załadowaniu modułu dostępne są m.in. narzędzia upcc oraz upcrun, wraz ze swoimi stronami man.

Aby skompilować kod napisany w języku UPC wywołujemy n.p.:

upcc program.upc -o program.x

Uruchomienie binarki następuje poprzez odpowiednie wywołanie narzędzia upcrun, n.p.:

upcrun -N 2 -n 12 ./program.x

Powyższa komenda uruchomi program.x za pomocą 32 wątków UPC rozrzuconych równomiernie na dwóch węzłach. Oczywiście, musimy najpierw zapewnić sobie dostępność węzłów obliczeniowych. Można to zrobić np. poprzez otwarcie interaktywnej konsoli na węzłach obliczeniowych:

$ srun -A GRANT --nodes 2 --tasks-per-node 12 -C ib --pty bash -l
srun: job JOBID queued and waiting for resources
srun: job JOBID has been allocated resources
$ module load upc
$ upcrun -N 2 -c 12 -n 24 ./program.x

Więcej informacji

Więcej informacji i przykładów wykorzystania UPC można odnaleźć na stronach: