Dystrybucja wektorów i macierzy

Daniel Rychcik
muflon@mat.uni.torun.pl
03-01-2001

1. Wstęp

Dystrybucja to zagadnienie, które pojawia się przy zrównoleglaniu algorytmów operujących na większej ilości danych. Podstawowym problemem na jaki napotykamy jest wtedy określenie miejsca przechowywania danych:

  • Czy każdy proces ma posiadać lokalną kopię wszystkich danych wejściowych?
  • Czy też może natura algorytmu pozwala na przydzielenie każdemu procesowi pewnej porcji danych wystarczającej do wykonania zadania?
  • Możliwe jest również podejście hybrydowe: proces początkowo posiada pewien fragment danych, a w trakcie obliczeń pobiera inne niezbędne elementy komunikując się z innymi procesami.

Najczęściej staramy się (w celu zminimalizowania ogólnych kosztów komunikacji) podzielić dane na jakieś logicznie odrębne fragmenty i przesłać je do właściwych procesów. Różne rodzaje takiego podziału (inaczej: dystrybucji tych danych) są główną treścią tego referatu.

Odrębnym problemem (po ustaleniu rodzaju dystrybucji) jest fizyczna realizacja dostarczania danych do procesów. Większość systemów programowania równoległego dostarcza specjalne narzędzia do tego celu. Aby zminimalizować koszty czasowe stosowane są specjalne algorytmy, takie jak hypercube. Jako przykład podam tutaj specjalizowane funkcje HPF (High Performance Fortran) służące do dystrybucji wektorów i macierzy według zadanych schematów.

2. Dystrybucja wektorów

Mając za zadanie wykonanie pewnych obliczeń na dużych wektorach (np. iloczyn skalarny) możemy podzielić je na kilka sposobów. Pierwszy z nich to

2.1. Dystrybucja blokowa

Jest to najprostszy rodzaj dystrybucji. Polega on na tym, że dla k procesów i wektora długości n obliczamy NB jako część całkowitą z dzielenia n/k i dzielimy wektor na k części, z których pierwsze k-1 ma długość NB, ostatnia zaś może być krótsza (jeżeli reszta z dzielenia jest niezerowa):

Dystrybucja blokowa wektora

Dla uproszczenia rezygnujemy z pozornie lepszej metody, w której "brakujące" elementy są rozdzielane pojedynczo na ostatnich pozycjach w końcowych procesach:

Dystrybucja blokowa wektora - alternatywa

Takie rozwiązanie zapewniłoby lepszy podział pracy, lecz wiązałoby się z dodatkowymi obliczeniami.

System HPF realizuje dstrybucję blokową za pomocą funkcji DISTRIBUTE. Używamy jej w następujący sposób: 

      REAL :: X( N )
!HPF$ PROCESSORS PROC( P )
!HPF$ DISTRIBUTE X( BLOCK( NB ) ) ONTO PROC

Gdzie NB to długość bloku obliczana przez system.

2.2. Dystrybucja cykliczna

Jest to przeciwieństwo dystrybucji blokowej - tutaj dane dla jednego procesu są maksymalnie rozproszone w wektorze wejściowym. Dane dla procesu i są brane z pozycji: i,k+i,2k+i,...,[n/k]*k+i. Zależności widać na poniższym rysunku:

Dystrybucja cykliczna wektora

Najprostsza forma dystrybucji blokowej w HPF jest realizowana następująco: 

      REAL :: X( N )
!HPF$ PROCESSORS PROC( P )
!HPF$ DISTRIBUTE X( CYCLIC ) ONTO PROC

2.3. Dystrybucja blokowo-cykliczna

Jest to połączenie właściwości dwóch omówionych typów. Dane dla jednego procesu są grupowane w bloki o zadanej długości i rozmieszczone w jednakowch odstępach na wektorze. Na rysunku wygląda to następująco:

Dystrybucja blokowo-cykliczna wektora

Dla zadanej długości bloku NB w HPF realizacja dystrybucji blokowo-cyklicznej wygląda następująco: 

      REAL :: X( N )
!HPF$ PROCESSORS PROC( P )
!HPF$ DISTRIBUTE X( CYCLIC( NB ) ) ONTO PROC

W ogólnym przypadku nie musimy zaczynać dystrybucji danych od procesu o numerze 0. Przykładowo poprzedni schemat mógłby mieć następującą postać:

Dystrybucja blokowa wektora - przypadek ogólny

Odpowiedni kod w HPF ma postać: 

      REAL :: X( N )
!HPF$ PROCESSORS PROC( P )
!HPF$ TEMPLATE T( N + P*NB )
!HPF$ DISTRIBUTE T( CYCLIC( NB ) ) ONTO PROC
!HPF$ ALIGN X( I ) WITH T( SRC*NB + I )

3. Dystrybucja macierzy

W przypadku macierzy decyzja o wyborze dystrybucji jest trudniejsza, możemy bowiem rozpatrywać osobno obydwie współrzędne każdego elementu. W praktyce dla macierzy dwuwymiarowych stosuje się najczęściej następujące rodzaje dystrybucji:

3.1. Dystrybucje z podziałem według jednej współrzędnej

W tym przypadku mamy coś w rodzaju "rozciągnięcia" opisanych w punkcie 2. dystrybucji wektorów. Ustalona współrzędna elementu macierzy jednoznacznie wyznacza proces, który tym elementem zarządza, natomiast druga współrzędna może się zmieniać dowolnie w obrębie procesu.

Poniższe schematy obrazują różne rodzaje takiej dystrybucji w której jednostką elementarną przy rozdzielaniu danych są kolumny macierzy. Analogicznie wyglądają schematy dla wierszy - rysunki należy wtedy podać transpozycji.

3.1.1. Dystrybucja blokowa

Dystrybucja blokowa macierzy

3.1.2. Dystrybucja cykliczna

Dystrybucja cykliczna macierzy

3.1.3. Dystrybucja blokowo - cykliczna

Dystrybucja blokowo-cykliczna macierzy

3.2. Przypadek ogólny

W wielu przypadkach istnieje potrzeba bardziej skomplikowanego rozmieszczenia danych. Jako przykład można podać eliminację Gaussa, w której najlepsze zrównoważenie obliczeń wśród procesów zapewnia dystrybucja podwójnie cykliczna (two-dimensional block-cyclic distribution), wyglądająca następująco:

Dystrybucja dwuwymiarowa

W tym przypadku każdy szary kwadrat reprezentuje podmacierz kwadratową o ustalonym (najczęściej niewielkim) wymiarze. Każdy proces otrzymuje pewien fragment macierzy wejściowej, lecz fragmenty te są równomiernie rozproszone po jej całym obszarze.

HPF zapewnia realizację dowolnych kombinacji dystrybucji blokowych i cyklicznych przez podanie odpowiednich parametrów do polecenia DISTRIBUTE. Przykładowo dla macierzy 17x17 dystrybucja jej elementów blokami wielkości 3x3 pomiędzy 4 procesy ułożone w kwadrat 2x2 jest osiągana w następujący sposób: 

      REAL :: A( 17, 17 )
!HPF$ PROCESSORS PROC( 2, 2 )
!HPF$ DISTRIBUTE A( CYCLIC( 3 ), CYCLIC( 3 ) ) ONTO PROC

Ze składni poleceniai widać, że możemy dowolnie składać ze sobą różne typy dystrybucji (blokowa+cykliczna), jak również uogólnić całą operację na wyższe wymiary - sposób użycia prawie wcale się nie zmienia.

Jak łatwo się domyśleć, nie wszystkie procesy otrzymają taką samą ilość danych. Szczegóły implementacyjne w HPF są przed programistą ukryte, ma on do dyspozycji procedurę NUMROC, która pozwala określiś rozmiar macierzy przekazanej do procesu.

4. Wydajność komunikacji

Odpowiedni dobór dystrybucji danych może w znaczący sposób poprawić (czytaj: zmniejszyć) nakłady na wymianę danych między procesami. Weźmy jako przykład obliczenia w problemie różnic skończonych na siatce dwuwymiarowej. Natura problemu jest taka, że naturalny podział zadań można sobie wyobrazić następująco:

FDP - przykład pierwszy

Jak łatwo policzyć, wymiana danych w obrębie kwadratu o wymiarach np. 4x4 wymaga wysłania 64 pakietów danych, każdy z użyciem osobnego komunikatu. Po przeorganizowaniu siatki tak, aby w jednym miejscu zgromadzić dane (i wykonywać obliczenia) dla całego kwadratu, mamy zyski dwojakiego rodzaju:

  • Odpadają nam koszty komunikacji "wewnątrz" kwadratu
  • Komunikacja na zewnątrz odbywa się 4-elementowymi pakietami, zamiast pojedynczych pakietów, co w oczywisty sposób zwiększa wydajność.
Ulepszony schemat jest przedstawiony na kolejnym rysunku:

FDP - przykład drugi

5. Algorytmy

Istnieją algorytmy, które narzucają z góry wybór dystrybucji danych między procesy. Jako przykład wybrałem algorytm transpozycji macierzy wymiaru n (gdzie n - potęga dwójki) o złożoności O(log(n)). Polega on na rekurencyjnym dzieleniu macierzy na równe części i transpozycji tych części. Schemat działania algorytmu obrazuje rysunek:

algorytm transpozycji macierzy

Jak widać, narzucającym się tu rodzajem dystrybucji jest podział blokowy w jednej osi (i to najlepiej dla bloków rozmiaru 1). Po zejściu z podmacierzami do wymiaru pojedynczego bloku możemy je transponować już "ręcznie", w obrębie jednego procesu.

6. Literatura