Unified Parallel C
From Centrum Komputerów Dużej Mocy, ICM Uniwersytet Warszawski
| Poradnik |
|---|
| Konto użytkownika • Poczta elektroniczna • Korzystanie z SSH • Systemy kolejkowe: PBS (Klaster halo2), LoadLeveler (BlueGene/P notos) |
| Programowanie |
| Kompilatory: C/C++, Fortran • Programowanie równoległe: OpenMP, MPI, UPC, CAF, SHMEM, pthreads • Biblioteki numeryczne: BLAS, LAPACK, FFTW |
| Optymalizacja |
| Uruchamianie i optymalizacja kodów na architekturze Blue Gene/P • Uruchamianie i optymalizacja kodów na halo2 |
| Krok po kroku |
| Logowanie do ICM (Windows) • Logowanie do ICM (UNIX) • MPI (Klaster halo2) • MPI (BlueGene/P notos) |
| Wszystkie "Krok po kroku" |
| Dokumentacja |
Contents |
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 o pamięci fizycznie rozproszonej, logicznie współdzielonej (modele programowania równoległago opisane zostały przez Łukasza Bolikowskiego w Biuletynie 3). Podobnie jak CAF dla Fortranu (biblioteka opisana w artykule Michała Łopuszyńskiego z Biuletynu 4), UPC to niewielkie i bardzo wygodne w użyciu narzędzie pozwalające tworzyć wydajne programy.
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:
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.
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:
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.
Dostępność UPC
Wspierane platformy. Jak zdobyć UPC?
UPC jest wspierane przez kompilatory na niektórych komputerach firmy Cray ale również HP, SGI czy Sun. Dostępne są również pewne darmowe implementacje, dokumentacje i przykłady:
- Michigan Technological University
- George Washington University
- Berkeley Unified Parallel C (UPC) Project
UPC w ICM
Z biblioteki UPC można korzystać w ICM na komputerze Cray X1e (tornado). Przy kompilacji powinniśmy dodać opcję -h upc, np:
cc -h upc program_upc.c
