Programowanie równoległe w Erlangu

22.07.2010 - Marek Materzok
TrudnośćTrudność

Przykład: liczby pierwsze

Jednym z problemów, dla których istnieje bardzo ciekawe rozwiązanie równoległe, jest problem obliczania liczb pierwszych. Następujący algorytm, nauczany w szkołach, nazywany jest sitem Eratostenesa:

  1. Zapisz wszystkie liczby naturalne od 2 do wybranej wartości n.
  2. Wybierz pierwszą nie wykreśloną, nie wypisaną liczbę. Wypisz ją, po czym wykreśl wszystkie jej wielokrotności.
  3. Powtarzaj krok 2, dopóki jest to możliwe.

Na podstawie powyższego algorytmu opracujemy podobny, ale wykorzystujący programowanie równoległe, i zaimplementujemy go w Erlangu. Zastanówmy się, jak podzielić powyższy algorytm na podzadania, które można by wykonywać równolegle? Dobrym pomysłem wydaje się, żeby pojedynczy proces usuwał wielokrotności wybranej liczby pierwszej. Zorganizujemy więc nasz program w taki sposób, że będziemy mieli dwa rodzaje procesów. Jeden proces będzie zajmował się tylko wysyłaniem za pomocą komunikatów kolejnych liczb naturalnych od 1 do wybranego n. Pozostałe procesy będą zaś działać według takiego schematu:

  1. Odbierz komunikat - liczbę k.
  2. Wypisz liczbę k na ekran.
  3. Utwórz nowy proces tego samego rodzaju.
  4. Odbierz komunikat - liczbę l. Jeśli l nie jest podzielna przez k, wyślij ją komunikatem do utworzonego wcześniej procesu.
  5. Powtarzaj punkt 4.
Ilustracja

Dodatkowo, potrzebujemy wprowadzić mechanizm, który zatrzyma program, gdy wszystkie żądane liczby zostaną już wypisane. Problem rozwiążemy tak, że proces "wyliczający" po zakończeniu wyliczania wyśle komunikat będący poleceniem zamknięcia. Ostatni z procesów "filtrujących" odeśle do procesu "wyliczającego" komunikat oznajmiający, że wszystkie procesy zostały zatrzymane.

Zacznijmy od procesu "wyliczającego":

talk(N) ->
    % Uruchom pierwszy proces "filtrujący"
    Pid = spawn(fun () -> check() end),
    % Rozpocznij wyliczanie od liczby 2
    talk(Pid, 2, N).

talk(Pid, K, N) when K =< N ->
    % Wyślij kolejną liczbę k
    Pid ! K,
    % Kontynuuj
    talk(Pid, K+1, N);
talk(Pid, _, _) ->
    % Wyślij polecenie zamknięcia
    Pid ! {ok, self()},
    % Czekaj na potwierdzenie
    receive ok -> ok end.

Proces "filtrujący" jest równie mało skomplikowany:

check() ->
    % Odbierz pierwszy komunikat
    receive
        % Polecenie zamknięcia; jesteśmy ostatni, odsyłamy
        {ok, TPid} -> TPid ! ok;
        % Liczba
        K ->
            % Wypisz liczbę na ekran
            io:fwrite("~B~n", [K]),
            % Utwórz nowy proces "filtrujący"
            Pid = spawn(fun () -> check() end),
            % Zacznij pracować jako filtr
            check(Pid, K)
    end.

check(Pid, K) ->
    % Odbierz kolejny komunikat 
    receive
        % Polecenie zamknięcia; wyślij następnemu i zakończ działanie
        {ok, TPid} ->
            Pid ! {ok, TPid};
        % Liczba nie podzielna przez k; prześlij dalej
        L when L rem K /= 0 ->
            Pid ! L,
            check(Pid, K);
        % Liczba podzielna; zignoruj
        _ ->
            check(Pid, K)
    end.

Aby uruchomić powyższy program, należy wywołać funkcję talk z parametrem oznaczającym maksymalną wartość szukanych liczb. Można wypróbować program w działaniu poniżej.

Snippet icon Wpisz na przykład: talk(10). (z kropką na końcu!)

Osoby posiadające komputer z wieloma procesorami lub procesorem wielordzeniowym zachęcam do uruchomienia powyższego programu z opcją -smp enable oraz -smp disable i porównanie czasu działania. Na moim dwuprocesorowym komputerze przy wykorzystaniu obu procesorów program działa 70% szybciej, niż na jednym procesorze!

Podsumowanie

Erlang pozwala na bardzo łatwe pisanie programów równoległych. Oczywiście, omówiony przeze mnie fragment języka nie pokazuje wszystkich jego możliwości - zupełnie pominąłem między innymi obsługę błędów, rozproszenie i wymianę kodu w trakcie pracy - jednak jest to zestaw wystarczający, żeby zacząć samodzielnie eksperymentować z Erlangiem, do czego gorąco zachęcam.

Druga część artykułu opowiada o wyjątkach, wymianie kodu w czasie pracy programu i rozproszeniu obliczeń.

4.666665
Twoja ocena: Brak Ocena: 4.7 (3 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com