Programowanie Równoległe i Rozproszone

III rok Informatyka WSZiB

Message Passing Interface (MPI) - Czę¶ć 2: Komunikacja miedzy procesami MPI

  1. Minimalny zestaw funkcji, które pozwalaj± na konstrukcję sporej ilo¶ci aplikacji równoległych:


  2. Komunikacja w MPI

    3. Terminy: komunikator, grupa procesów, rozmiar komunikatora, MPI_COMM_WORLD
    (MPI_Comm_size, MPI_Comm_rank, MPI_Comm_group, MPI_Comm_free, MPI_Comm_create, MPI_Comm_free, MPI_Comm_split),

    • komunikacja punkt-punkt (MPI_Send, MPI_Ssend, MPI_Isend, MPI_Recv),
    • komunikacja kolektywna (MPI_Bcast, MPI_Scatter, MPI_Reduce),
    • komunikacja blokuj±ca vs. nieblokuj±ca (MPI_Isend, ...Irecv, ...Issend),
    • komunikacja synchroniczna (MPI_Ssend),

    • Wykorzystujac komunikaty MPI_Send i MPI_Recv, rozbudowac prosty program licytacja.c o nastepujaca funkcjonalnosc:
      • w licytacji bierze udzial dowolna liczba procesow
      • jeden proces startuje licytacje wysylajac stawke o wartosci 0 do nastepnego
      • nastepny proces moze podbic stawke o 1 jesli wylosowana przez niego na poczatku liczba jest wieksza od tej stawki - podbicie polega na przeslaniu nastepnemu procesowi stawki powiekszonej o 1
      • jesli wylosowana liczba jest mniejsza lub rowna stawce, proces przesyla dalej liczbe ktora otrzymal
      • w momencie kiedy proces otrzyma stawke ktora przeslal, konczy licytacje jako zwyciezca
      • komunikacja przebiega "w kolko" od pierwszego procesu do ostatniego, ostatni wysyla do pierwszego

      • Przyklad rozwiazania

  3. Operacje globalne (dotycz±ce wszystkich procesów)

    • Barrier - synchronizuje procesy
    • Broadcast - wysyła komunikat z jednego do wszystkich procesów
    • Gather - zbiera dane ze wszystkich procesów do jednego
    • Scatter - rozdziela dane z jednego do wszystkich procesów
    • Reduce - sumuje, mnoży, etc. dane rozproszone pomiędzy procesy


    Przyklady wykorzystania:

  4. Zadanie: Zrównoleglenie algorytmu Gry LIFE w MPI.
    • Zasady gry:
      • 1 lub mniej sąsiadów - komórka obumiera "z samotności"
      • 4 i więcej sąsiadów - komórka obumiera "z przeludnienia"
      • 2 lub 3 sąsiadów - komórka przeżywa
      • Nowa żywa komórka powstaje jeśli jest wyłącznie 3 sąsiadów
    • Sekwencyjna wersja algorytmu slife.c.
      • Parametry:
        • rozmiar: 1..n - wielkosc pola
        • prawdopodobienstwo: 0..1 - prawdopodobienstwo wylosowania 1 w komórce, liczby z zakresu 0 do 1 np. 0.5
        • pokolen:1..n - ilość pokoleń do obliczenia
          •
      • Kompilacja i uruchomienie
        • gcc slife.c -o slife
        • ./slife 10 0.3 2
    • Implementacja wersji MPI krok po kroku:
      1. Dodać do programu wywołania MPI_Init, MPI_Finalize oraz włączyć plik nagłówkowy mpi.h
      2. Każdy proces MPI alokuje pole (macierz) o rozmiarze (N / psize) x N, gdzie N jest rozmiarem pola pobieranym z linii komend a psize jest ilością procesów MPI. Pozostala czesc macierzy jest rozdzielana po jednym wierszu do procesu.
      3. Sąsiednie procesy wymieniają się skrajnymi wierszami, pierwszym i ostatnim tzw. zakładkami przy pomocy sekwencji funkcji: Isend-Recv-Wait,Irecv-Send-Wait lub MPI_Sendrecv
      4. Proces 0 wypisuje sumaryczną ilość jedynek w całym polu zbierając ją funkcją MPI_Reduce


    Marcin Radecki, Tomasz Szepieniec, Joanna Kocot