Programowanie równoległe

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

Spis treści

Podstawy

Wstęp

Programowanie równoległe polega na napisaniu programu tak, aby można go było uruchomić na wielu procesorach równocześnie. Dokonuje się tego zazwyczaj przez modyfikację istniejącego kodu przeznaczonego pierwotnie na jeden procesor (mówimy wtedy o zrównoleglaniu kodu).

Zrównoleglając program należy szukać fragmentów, które mogą wykonywać się niezależnie od siebie. W przypadku obliczeń numerycznych, tego rodzaju równoległość związana jest zazwyczaj z występującymi w kodzie pętlami (DO w Fortranie, for w C).

Zrównoleglanie pętli

Przeanalizujmy dwa proste przykłady. W pierwszej pętli:

 DO I = 2, N-1
   TNEW(I) = 0.5*TOLD(I) + 0.25*TOLD(I-1) +0.25*TOLD(I+1)
 END DO

każda iteracja może być policzona niezależnie od pozostałych. Przykładowo, obliczenia dla iteracji I=5 nie zależą w żaden sposób od wyników obliczeń pozostałych iteracji, ani nie wpływają na wyniki obliczeń innych iteracji.

Taka pętla może więc być wspólnie liczona przez wiele procesorów: każdy procesor otrzyma pewien zakres iteracji do policzenia.

Druga pętla:

 F(1) = 1
 F(2) = 1
 DO I = 3, N
   F(I) = F(I-1) + F(I-2)
 END DO

nie może być niestety zrównoleglona w taki sposób, jak pierwsza. Iteracje muszą być obliczane jedna po drugiej, ponieważ np. obliczenia w iteracji I=5 zależą od wyników obliczeń iteracji I=3 i I=4. Wniosek: nie każdą pętlę można zrównoleglić.

Wiele programów z prawdziwego zdarzenia wykonujących obliczenia na siatkach dwu- lub trójwymiarowych zawiera fragment analogiczny do poniższego:

 TOLD(1:N, 1:M) = T(1:N, 1:M)
 DO I = 1, M
   DO J = 1, N
     ! tu obliczenia dla punktu TNEW(I, J)
     ! korzystajace z wartosci w punktach: TOLD(I, J),
     ! TOLD(I-1, J), TOLD(I+1, J), TOLD(I, J-1), TOLD(I, J+1)
   END DO
 END DO
 T(1:N, 1:M) = TNEW(1:N, 1:M)

Tego typu kod zrównolegla się z reguły w ten sposób, że siatkę dzieli się na podobszary (prostokąty lub równoległościany) i przydziela te podobszary procesorom.

Pamięć współdzielona i rozproszona

Bardzo ważnym czynnikiem wpływającym na konstrukcję programu równoległego jest budowa komputera, a dokładniej: sposób połączenia procesorów z pamięcią operacyjną. Omówmy więc w skrócie dwie najprostsze architektury wieloprocesorowe. Wybrane przykłady są nieco uproszczone, ich celem jest jedynie przedstawienie istoty sprawy. Proszę pamiętać, że w rzeczywistości sposób połączenia procesorów z pamięcią jest bardziej złożony.

Poniższa ilustracja przedstawia schematycznie dwie najbardziej typowe architektury komputerowe.

Połączenia procesorów z pamięcią

Pamięć rozproszona

Po lewej stronie przedstawiony jest przykład architektury o pamięci rozproszonej (distributed memory architecture), czyli architektury gdzie pamięć jest podzielona na fragmenty zarządzane przez poszczególne procesory (lub grupy procesorów).

Przykładem takiej architektury jest klaster Sun Blade 6048 (halo2). Klaster składa się w większości z węzłów wyposażonych w cztery czterordzeniowe procesory typu AMD Opteron (architektura x86_64, nazwa kodowa Barcelona) i 16 lub 32 GB pamięci operacyjnej. Warto sobie zdać sprawę, że klaster to wiele fizycznie odseparowanych komputerów połączonych jedynie wspólną siecią. Procesor w węźle X nie może więc bezpośrednio korzystać z pamięci umieszczonej w węźle Y. Zamiast tego, może on poprosić procesor z węzła Y o przesłanie mu fragmentu "swojej" pamięci (używając np. pary funkcji MPI_Send() i MPI_Recv() z biblioteki MPI).

Pamięć współdzielona

Schemat po prawej stronie to przykład maszyny o pamięci współdzielonej (shared memory architecture). W takich komputerach, jak sama nazwa wskazuje, wszystkie procesory współdzielą jedną i tę samą pamięć.

Pamięć fizycznie rozproszona, logicznie współdzielona

Ponadto, można spotkać superkomputery (np. Cray X1e), które choć posiadają cechy architektur o pamięci rozproszonej, są znacznie bardziej zespolone niż typowy klaster. Podstawowa różnica to globalne adresowanie pamięci, pozwalające na sięganie do odległej pamięci (należącej do innego procesora) bez konieczności absorbowania "właściciela". Bardziej wyrafinowane narzędzia, takie jak SHMEM, CAF czy UPC potrafią korzystać z tej możliwości. Mówi się, że pamięć w tych maszynach jest fizycznie rozproszona, logicznie współdzielona.

Inne możliwości

Możliwe są bardziej złożone sposoby łączenia procesorów i pamięci, np. rozwiązania hybrydowe, mające w sobie zarówno cechy pamięci współdzielonej, jak i rozproszonej. Przykładem takiej architektury jest Cray X1e.

Wpływ architektury na zrównoleglanie

Aby zilustrować wpływ architektury na sposób zrównoleglania kodu, powróćmy na chwilę do ostatniej przykładowej pętli. Wyobraźmy sobie, że liczymy taki problem na siatce 16x12, korzystając z 12 procesorów. Załóżmy, że zdecydowaliśmy się podzielić obszar pomiędzy procesory w następujący sposób:

Podział obszaru pomiędzy procesory

Każdy procesor uaktualnia przydzielone mu węzły siatki. Przykładowo, procesor nr 6 uaktualnia węzły zaznaczone na fioletowo. Jednak w trakcie uaktualniania, musi on korzystać z węzłów "należących" do sąsiednich procesorów - na rysunku zaznaczonych kolorem błękitnym. Tę otoczkę, obszar z którego korzystamy, a który należy do sąsiednich procesorów, nazywany jest w programowaniu równoległym halo.

Tutaj dochodzimy do sedna sprawy: jeśli pracujemy na architekturze o pamięci rozproszonej, będąc procesorem, musimy poprosić sąsiednie procesory o przesłanie nam odpowiednich fragmentów "ich" pamięci, a także sami musimy reagować na żądania przesłania pamięci skierowane do nas od przez inne procesory. Co więcej, musimy wykonywać operacje wysyłania i odbierania w odpowiedniej kolejności, aby nie doszło do tzw. zakleszczenia: sytuacji w której procesor X czeka na dane od procesora Y, a procesor Y czeka na dane od procesora X. Dopuszczenie do takiej sytuacji jest bardzo poważnym błędem programistycznym.

Jeśli natomiast pracujemy na architekturze o pamięci współdzielonej, problem wymiany halo praktycznie nie istnieje: każdy proceror ma dostęp do całej pamięci i może bez problemu pobrać potrzebne mu wartości. Należy tylko uważać, aby pobierać wartości interesujących pól zanim sąsiedni procesor je uaktualni.

Podsumowanie

Jak widać, architektura komputera wieloprocesorowego, a dokładniej: sposób dostępu do pamięci operacyjnej przez poszczególne procesory wpływa na sposób zrównoleglania programu.

Pamięć współdzielona jest łatwiejsza w programowaniu i zazwyczaj pozwala na lepszą komunikację pomiędzy procesorami. Jest to jednak rozwiązanie drogie, a na dodatek liczba procesorów, które można połączyć wspólną jest bardzo ograniczona (maks. kilkudziesiąt).

Architektury oparte o pamięć rozproszoną są natomiast stosunkowo tańsze i pozwalają łączyć ze sobą do kilku tysięcy procesorów. Komunikacja między procesorami jest jednak zazwyczaj wolniejsza, a programowanie trudniejsze, niż w przypadku pamięci współdzielonej.


Narzędzia

Jest to jedynie pobieżny przegląd dostępnych narzędzi - bibliotek i języków - służących do zrównoleglania kodu.

OpenMP

Główny artykuł: OpenMP

OpenMP jest zbiorem tzw. dyrektyw służących do zrównoleglania kodu. Dyrektywy to fragmenty kodu wyglądające jak komentarze, jednak "wtajemniczone" kompilatory nie traktują ich jako komentarze, lecz jako wskazówki jak zrównoleglić następujący po nich fragment kodu (z reguły pętlę). Dyrektywy OpenMP stosuje się wyłącznie dla architektur o pamięci współdzielonej.

W ICM przy pomocy OpenMP można programować na:

  • halo2 (ze względu na architekturę można uruchamiać na maks. 16 lub maks. 64)
  • hydra (maks. 12 lub maks. 48 lub maks. 64)
  • boreasz (maks. 32)
  • notos (maks. 4 (SPM) lub maks. 8 (DUAL) lub maks 16 (VN))
  • nostromo (maks. 16)

Zobacz także:

MPI

Główny artykuł: MPI

MPI, czyli Message Passing Interface, to bardzo popularna biblioteka służąca do zrównoleglania kodów dla architektur o pamięci rozproszonej (m.in. klastrów). Można też używać biblioteki MPI na architekturach o pamięci współdzielonej, ale z reguły nie jest to najefektywniejsze rozwiązanie.

Dwie najważniejsze funkcje tej biblioteki to MPI_Send i MPI_Recv. Pierwsza wysyła określony fragment pamięci do określonego procesora, druga odbiera dane od określonego procesora i zapisuje w określonym miejscu w pamięci.

Mówi się, że do programowania przy użyciu MPI wystarcza w zupełności znajomość 6 funkcji: trzech inicjalizacyjnych (wywływanych raz na początku programu), jednej finalizującej (wywoływanej raz przy kończeniu programu), oraz MPI_Send i MPI_Recv. Dla tych, którym to nie wystarcza, standard MPI oferuje ponad 100 różnych bardziej wyspecjalizowanych funkcji.

W ICM przy pomocy MPI można programować na:

  • halo2 (system kolejkowy pozwala uruchomić na maks. 512 CPU)
  • hydra
  • boreasz (system kolejkowy pozwala uruchomić na maks. 2432 CPU)
  • notos (system kolejkowy pozwala uruchomić na maks. 2048 CPU)
  • nostromo

Zobacz także:

SHMEM

Główny artykuł: SHMEM

SHMEM to rozwiązanie stosowane przez firmy Cray i SGI, opracowane z myślą o architekturach rozproszonych. Jej celem jest zapewnienie programiście komfortu znanego z architektur o pamięci współdzielonej. Można o niej myśleć jako o swego rodzaju "emulacji" architektury współdzielonej (stąd nieco myląca nazwa: SHared MEMory).

Dwie bardzo ważne funkcje SHMEM to shmem_get i shmem_put. Podstawowa różnica w stosunku do znanych z MPI MPI_Send i MPI_Recv polega na tym, że w przypadku SHMEM są to funkcje jednokierunkowe. Oznacza to, że wywołaniu shmem_get (pobierz dane z odległej pamięci) nie musi odpowiadać żadna "funkcja wysyłająca" na procesorze będącym "właścicielem" tej odległej pamięci. Podobnie, wywołaniu shmem_put (umieść dane w odległej pamięci) nie musi towarzyszyć "funkcja odbierająca".

Biblioteka SHMEM bardzo silnie korzysta ze specyficznych własności architektur superkomputerów Cray i SGI, nie jest więc dostępna na innych platformach. Co ważne, biblioteka SHMEM jest znacznie szybsza niż MPI, szczególnie na Cray X1e (tornado)!

W ICM przy pomocy SHMEM można programować na:


Zobacz także:

  • man intro_shmem na maszynach, gdzie SHMEM jest dostępny

Co-Array Fortran

Główny artykuł: Co-Array Fortran

Co-Array Fortran, lub w skrócie CAF, to rozszerzenie języka Fortran o dodatkowe konstrukcje pozwalające na łatwe zrównoleglanie programów. CAF powstał z myślą o architekturach rozproszonych. Najlepsze rezulataty uzyskuje się w przypadku architektur fizycznie rozproszonych, logicznie współdzielonych, takich jak Cray X1e.

Jest to zdecydowanie najbardziej efektywny sposób zrównoleglania programów. Generowany kod jest znacznie wydajniejszy niż w przypadku stosowania MPI czy SHMEM. Jednocześnie CAF jest znacznie łatwiejszy w użyciu, programy są znacznie bardziej czytelne niż np. w przypadku używania MPI.

Wprawdzie CAF obecnie nie jest jeszcze zbyt popularny, bo dostępny jest praktycznie tylko na nowszych superkomputerach Cray, ale planuje się, aby rozszerzenia CAF stały się częścią następnego standardu Fortranu (roboczo: Fortran 2008).

W ICM przy pomocy CAF można programować na:


Zobacz też:

Unified Parallel C

Główny artykuł: Unified Parallel C

Unified Parallel C, lub w skrócie UPC, to rozszerzenie języka C o dodatkowe konstrukcje pozwalające na łatwe zrównoleglanie programów. Jest on bardzo podobny do rozszerzeń Co-Array Fortran, choć powstaje niezależnie. Podobnie jak CAF, jest to rozwiązanie dla architektur o pamięci rozproszonej.

W ICM przy pomocy UPC można programować na:


Zobacz też: