Zrównoleglanie trudnych pętli w OpenMP
Jest to pierwszy mój wpis związany z moimi studiami. Ostatnio na uczelni mamy sporo programowania równoległego i rozproszonego. Wykorzystujemy przy tym różne technologie, rozwiązania i języki programowania. Na szczególną uwagę zasługuje OpenMP. Biblioteka ta umożliwia łatwy sposób na zrównoleglenie swojego kodu.
Twórcy standardu wyszli z założenia, że najlepiej jest zrównoleglać pętle poprzez podział iteracji między wątki. Na tym głownie polega praca z OpenMP. Nie musimy się przejmować komunikacją między poszczególnymi wątkami, wszystko za nas robi biblioteka. Co więcej, nie musimy od razu tworzyć skomplikowanych algorytmów równoległych. Piszemy najpierw program sekwencyjny, a dopiero później go zrównoleglamy. Taka kolejność pracy redukuje ilość błędów podczas pisania oprogramowania.
Problemy zaczynają się, przy trudnych pętlach. Jeżeli w ciele pętli odwołujemy się do elementów z poprzedniej iteracji, innym indeksie niż aktualny w pętli, lub przy wielokrotnie zagnieżdżonych pętlach. Takie właśnie zadanie dostaliśmy ostatnio na uczelni do rozwiązania. Pozwolę sobie przedstawić niektóre ciekawsze sposoby na poradzenie sobie z tymi problemami. Pewnie nie są one optymalne, ale dają przyśpieszenie kodu o blisko 50% dla procesora dwurdzeniowego.
Pierwszy przykład:
int size = 20000000;
int size2 = 5000;
for ( int i = 1; i < size; i++ ) {
if ( ( x[ i - 1 ] < 0.001 ) && ( x[ i - 1 ] > 2.0 ) ) x[ i ] = 1.0;
else x[ i ] = exp( - x[ i - 1 ] * 0.99999 ) + sin( x[ i - 1 ] ) + cos( x[ i - 1 ] * 0.1 ) ;
if ( ( y[ i - 1 ] < 0.001 ) && ( y[ i - 1 ] > 2.0 ) ) y[ i ] = 1.0;
else y[ i ] = exp( - y[ i - 1 ] * 0.99999 ) + cos( y[ i - 1 ] ) + sin( y[ i - 1 ] * 0.1 );
z[ i ] = ( x[ i - 1 ] + y[ i - 1 ] ) * 0.999999999;
}
Jak widać zrównolenie tej pętli korzystając z dyrektyw openmp (parallel for) jest praktycznie niemożliwe. Elementy tablicy odwołują się do indeksów z poprzedniej iteracji jednocześnie uniemożliwiając prace wielowątkową. Jedynym rozwiązaniem jest podział na trzy pętle. Dwie pierwsze będą wykonywać warunki, trzecia będzie odpowiedzialna za przypisanie do tablicy z[]. Pierwsze pętlę będą przydzielone do sekcji, gdzie każdą z sekcji będzie wykonywał jeden wątek:
#pragma omp parallel sections num_threads(2) private(i) shared(size)
{
#pragma omp section
{
for ( i = 1; i < size; i++ ) {
if ( ( x[ i - 1 ] < 0.001 ) && ( x[ i - 1 ] > 2.0 ) ) x[ i ] = 1.0;
else x[ i ] = exp( - x[ i - 1 ] * 0.99999 ) + sin( x[ i - 1 ] ) + cos( x[ i - 1 ] * 0.1 ) ;
}
}
#pragma omp section
{
for ( i = 1; i < size; i++ ) {
if ( ( y[ i - 1 ] < 0.001 ) && ( y[ i - 1 ] > 2.0 ) ) y[ i ] = 1.0;
else y[ i ] = exp( - y[ i - 1 ] * 0.99999 ) + cos( y[ i - 1 ] ) + sin( y[ i - 1 ] * 0.1 );
}
}
}
#pragma omp parallel for private(i) shared(size,z) schedule(dynamic, 100000)
for ( i = 1; i < size; i++ ) {
z[ i ] = ( x[ i - 1 ] + y[ i - 1 ] ) * 0.999999999;
}
Pewnie zastanawiacie się, po co rozdzielać jedną pętle na, aż trzy. Przecież to trzy razy więcej iteracji i trzy razy więcej pracy. Jest to prawda, ale ta praca jest wykonywana równolegle, dzięki czemu cały fragment kodu wykonuje się o kilkadziesiąt procent szybciej.
Innym przykładem trudnej pętli jest:
for ( int l = 0; l < 3; l++ )
for ( int k = 0; k < 5; k++ )
for ( int i = 0; i < size2; i++ )
for ( int j = 0; j < i; j++ )
z[ i ] += sin( x[ j ] ) + cos( y[ j ] );
Zewnętrzne pętle mają stosunkowo mało iteracji. Na dodatek te iteracje są nieparzyste przez co nie można je podzielić optymalnie na parzystą ilość rdzeni. W wyniku czego, jeden z wątków po wykonaniu swojej pracy zawsze będzie czekał i marnował czas.
Co więcej w najbardziej zagnieżdżonej pętli odwołujemy się w warunku z pętli wyżej. Jednym z sposobów na poradzenie sobie z takim problemem jest:
int max, maxv, j;
maxv=size2*15;
#pragma omp parallel for private(i,j) shared(z, maxv, max) schedule(static, 9375) ordered
for ( i = 0; i < maxv; i++ ) {
max = i%size2;
for ( j = 0; j < max; j++ )
z[ i%size2 ] += sin( x[ j ] ) + cos( y[ j ] );
}
Zewnętrzne pętle złączyliśmy razem, dzięki czemu otrzymaliśmy jedną pętlę. Taką, którą lubi openMP – najbardziej zewnętrzna z największą liczbą iteracji. Co więcej wątki otrzymują stały przydział po 9375 iteracji pętli. Dzięki czemu mają równe obciążenie, a szansa, że skończą pracę w tym samym czasie jest większa.
Ostatnim przykładem będzie zrównoleglanie pętli nie będącej pętlą for:
do {
do {
sum1 += exp( - x[ counter ] * y[ counter ] );
sum2 += y[ counter ] * z[ counter ];
sum3 += exp( - z[ counter ] * x[ counter ] ) ;
counter ++;
} while ( counter < size );
counter = counter2;
} while ( counter2++ < 5 );
Tutaj nie ma innego wyjścia, jak przerobienie tych pętli na pętle for. Jak widać wcale to nie jest takie proste i wymaga dłuższego przemyślenia, po to by wynik był jak najbardziej zbliżony do oryginalnego. Dodatkowo widzimy sporo operacji dodawania. Wykorzystamy tą informacje wstawiając redukcje dla tej operacji.
double sum1, sum2, sum3;
sum1 = sum2 = sum3 = 0.0;
int counter = 0;
int counter2 = 0;
for(;counter2<5;counter2++) {
#pragma omp parallel for private(counter) shared(size) reduction(+:sum1, sum2, sum3) schedule(static, 10000) ordered
for(counter=counter2;counter<size; counter++)
{
sum1 += exp( - x[ counter ] * y[ counter ] );
sum2 += y[ counter ] * z[ counter ];
sum3 += exp( - z[ counter ] * x[ counter ] ) ;
}
}
#pragma omp parallel for private(counter) shared(size) reduction(+:sum1, sum2, sum3) schedule(static, 10000) ordered
for(counter=0;counter<size; counter++)
{
sum1 += exp( - x[ counter ] * y[ counter ] );
sum2 += y[ counter ] * z[ counter ];
sum3 += exp( - z[ counter ] * x[ counter ] ) ;
}
Jak widać czasami opłaca się rozdzielić pętle na kilka części, czasami złączyć kilka pętli w jedną a jeszcze innym razem przerobić pętle na tradycyjnego for’a. Powyższe fragmenty kodu, dają przyspieszenie pracy pomiędzy 40-50% dla procesora dwurdzeniowego z dokładnością wyniku sięgającej 10 cyfr znaczących. Przy większej liczbie rdzeni (wątków), trzeba zmienić przydziały iteracji dla każdego wątku po to by wyniki był jak najbardziej zbliżony do oryginalnego. W kolejnych postach (jak tylko znajdę chwilę czasu) postaram się częściowo omówić podstawowe sposoby na IPC oraz MPI. Później przejdę do programowania wielowątkowego w Javie.
