Zrób to równolegle

Jak przerobić program z otwartym kodem źródłowym tak, aby działał przynajmniej zauważalnie szybciej? Wystarczy użyć narzędzi do programowania równoległego i odpowiedniego kompilatora.

Procesory dwurdzeniowe trafiły do domowych komputerów, ale wciąż wiele aplikacji nie wykorzystuje ich możliwości. A gdyby tak samodzielnie przerobić programy z otwartym kodem źródłowym (open source) na wersje wykorzystujące możliwości dwóch rdzeni? Zadanie takie w wielu wypadkach jest zaskakująco łatwe i nie wymaga olbrzymiej wiedzy programistycznej. Programowanie równoległe to temat złożony i obszerny, próba przedstawienia go w krótkim artykule musi być skazana na porażkę. Zajmiemy się przedstawieniem popularnych narzędzi do programowania równoległego i pokażemy w praktyce, jak można przerobić program sekwencyjny na wersję równoległą, wykorzystującą kilka procesorów (w naszych testach używaliśmy po prostu procesora dwurdzeniowego).

Jak działa taki program? Obliczenia wykonywane w naszym prostym przykładzie można podzielić na cztery etapy:

1. Uruchamiany jest główny program - zarządca.
2. Program dzieli zadanie obliczeniowe na podzadania i do każdego z nich uruchamia oddzielny proces. Liczba procesów zależy nie tylko od liczby procesorów, aleteż od możliwości systemu operacyjnego.
3. Równolegle działające procesy wykonują obliczenia i sygnalizują zakończenie pracy programowi głównemu.
4. Program główny łączy wyniki obliczeń i zwraca wynik.

Skompilowanie za pomocą Intel C++ Compiler 9.0 programu napisanego w środowisku Microsoft Visual C++ wymaga odpowiedniego połączenia obu narzędzi. Kluczowe znaczenie ma opcja Tools|Intel C++ Compiler Selection Tool.Podział na kilka równolegle działających procesów nie zawsze jest prosty, niektóre zadania obliczeniowe bardzo trudno podzielić na niezależne części. Co więcej, równolegle działające procesy najczęściej nie są zupełnie niezależne i muszą się ze sobą komunikować. To, że obliczenia wykonywane przez jeden z procesów zależne są od obliczeń wykonywanych przez inne procesy, może się stać źródłem wielu problemów. Załóżmy, że procesy A i B po wykonaniu części obliczeń sprawdzają wartość zmiennej X używanej do komunikacji między procesami. Jeśli X jest równe 0 (i tylko wtedy), proces zmienia wartość X na 1. W czasie równoległego wykonywania procesów A i B sytuacja jest następująca:

X =0
A odczytuje wartość X
B odczytuje wartość X
A zapisuje wartość X=1
Co powinien zrobić proces B?

Problemy mogą się pojawić także wtedy, gdy procesy nie wykorzystują współdzielonej pamięci. Załóżmy, że proces A czeka na wynik przesłany z procesu B. Proces B mozolnie wykonuje obliczenia, ale w pewnym momencie musi otrzymać wartość obliczeń procesu C. Niestety, dokończenie obliczeń przez proces C zależy od wyniku procesu A. Mamy tu klasyczny przykład zakleszczenia: powiązane siecią zależności procesy nie mogą kontynuować obliczeń.

Czy programista próbujący opracować równoległe rozwiązanie zadania musi się martwić takimi problemami? I tak, i nie. Tak, bo prawidłowo zaprojektowany algorytm równoległy zapewnia prawidłową pracę programu i pozwala maksymalnie wykorzystać możliwości kilku procesorów. Powodów do zmartwień nie ma jednak wiele, bo jest sporo narzędzi programistycznych upraszczających tworzenie programów wykorzystujących możliwości kilku procesorów. Począwszy od bibliotek upraszczających uruchamianie równoległych obliczeń i usprawniających komunikację między procesami, a skończywszy na zaawansowanych debugerach i programach do optymalizacji kodu.

OpenMP

OpenMP to biblioteki i dyrektywy kompilatora języków C/C++ i Fortran. Pozwalają na stosunkowo proste wzbogacenie aplikacji o możliwości, jakie daje przetwarzanie równoległe.OpenMP to biblioteka programistyczna obsługiwana przez niektóre kompilatory języków C/C++ i Fortran (m.in. Microsoft Visual C++ 2005, Intel C++ Compiler 9.0 i najprawdopodobniej GCC w oczekiwanej wersji 4.2). Równoległe wykonywanie operacji jest wprowadzane przez specjalne oznaczenia w kodzie programu. Można w ten sposób "zmusić do równoległości" programy napisane z myślą o wykonywaniu sekwencyjnym. Równoległe wykonywanie operacji z użyciem OpenMP dotyczy przede wszystkim niezależnych od siebie bloków programu, które bez zmian można wykonywać w dowolnej kolejności (a więc i równolegle). OpenMP pozwala też podzielić na równoległe części zwykłe pętle (np. pętlę for w języku C). Za pomocą OpenMP łatwo przerobić sekwencyjne rozwiązania na programy wykorzystujące np. możliwości procesorów wielordzeniowych. Wśród tych zalet kryje się też pewne zagrożenie. Przerabiane w ten sposób programy często nie wykorzystują wszystkich możliwości programowania równoległego i w dużej mierze pozostają sekwencyjne mimo równoległego wykonywania kilku fragmentów.

Informacje http://www.openmp.org
MPI i Open-MPI

Najprostszy program wykorzystujący bibliotekę OpenMP. Używamy dwóch niezależnych wątków, aby przyśpieszyć przeglądanie tablicy.MPI, czyli Message Passing Interface, nie jest narzędziem do przerabiania progamów sekwencyjnych na równoległe, lecz biblioteką funkcji służących do komunikacji między procesami. Program korzystający z MPI musi więc być od początku napisany z myślą o obliczeniach równoległych, a MPI "tylko" udostępnia narzędzia do sprawnej komunikacji między równolegle działającymi procesami. W przeciwieństwie do OpenMP, programu napisanego z użyciem MPI najprawdopodobniej nie będzie można poprawnie uruchomić w środowisku z jednym procesorem, a najpewniej nawet nie zostanie skompilowany przez kompilator nieobsługujący MPI. Natomiast jeśli tworzysz program z założenia wykonujący obliczenia równolegle, biblioteka MPI (lub dostępna na licencji BSD biblioteka Open-MPI) staje się potężnym narzędziem do zapewnienia dobrej komunikacji między procesami.

Informacje http://www.mpi-forum.org , http://www.open-mpi.org
Równoległość w dwóch wierszach

Zastosujmy w praktyce bibliotekę OpenMP do napisania prostej aplikacji, demonstrującej możliwości programowania równoległego. W tym celu użyliśmy kompilatora Intel C++ Compiler 9.0 oraz stareńkiego środowiska programistycznego Microsoft Visual C++ 6.0. Oba narzędzia można łatwo połączyć i kompilować programy tworzone w Visual C++ za pomocą kompilatora C++. Należy pamiętać o użyciu przełącznika /Qopenmp w opcjach projektu, w przeciwnym wypadku konstrukcje odpowiedzialne za "zrównoleglenie" programu za pomocą OpenMP nie będą poprawnie rozpoznawane.

Uruchomienie obliczeń równoległych za pomocą OpenMP sprowadza się do użycia specjalnych konstrukcji rozpoczynających się od #pragma omp. Pierwsza taka konstrukcja w naszym programie ma postać:

#pragma omp parallel num_threads(2)

Oznacza ona początek bloku, który będzie wykonany z użyciem kilku wątków. Parametr num_threads() określa liczbę równolegle wykonywanych wątków, w tym wy padku 2.

Konstrukcja:

#pragma omp for

Możliwości biblioteki OpenMP przetestowaliśmy, modyfikując Whetstones, słynny test wydajności obliczeń zmiennopozycyjnych procesora.oznacza, że wykonanie następującej po niej pętli for będzie podzielone między uruchomione wątki.

double t[100000];
double suma;
int i;
srand(0);
//wypełnij tablicę
//losowymi wartościami
for(i=0;i<100000;i++)
t[i] = rand()%100;

//uruchamiamy równoległe
//wykonywanie obliczeń
//(2 wątki)

#pragma omp parallel num_threads(2)
{
//dzielimy wykonanie
//pętli pomiędzy wątki
#pragma omp for
for(i=0;i<100000;i++)
suma += t[i];
#pragma omp barrier
#pragma omp master
printf("Czas pracy: %d", clock());
}

W wypadku tak krótkiego i prostego programu trudno liczyć na to, że równoległe wykonanie części obliczeń przyśpieszy działanie aplikacji. Dodatkowe operacje związane z obsługą wątków mogą je wręcz wydłużyć. Aby przekonać się, czy użycie OpenMP do rozdzielenia obliczeń wykonywanych przez program na dwa wątki może dać pozytywny rezultat, należy przygotować bardziej złożony algorytm. Takim algorytmem jest znany test wydajności procesora, opracowany jeszcze w latach 80. ubiegłego wieku test Whetstones, badający wydajność obliczeń zmiennopozycyjnych. Wykorzystaliśmy to i zastosowaliśmy konstrukcje OpenMP w Whetstones. Optymalizacja testu na potrzeby procesora dwurdzeniowego nie była specjalnie wymyślna. Test składa się z ośmiu etapów, z których każdy zestaw obliczeń wykonywany jest w pętli. Użyliśmy konstrukcji:

#pragma omp for

do rozdzielenia każdej z pętli na dwa niezależne wątki. Następnie porównaliśmy wyniki uzyskane przez zwykły i "równoległy" benchmark. Okazuje się, że kolejne testy w wersji z prostą optymalizacją trwały o niemal jedną czwartą krócej. Jedynym wyjątkiem był test polegający na wielokrotnym wywoływaniu funkcji - tutaj wersja jednowątkowa, niezoptymalizowana sprawdziła się znacznie lepiej.