Open MP - Zrównoleglenie zagnieżdżonej pętli.

[Cyfrowy Baron]

No to z tego, że nie ma żadnego przyspieszenia z tego tytułu, że wątek jest wykonywany w oddzielnym procesie.

[polymorphism]

A gdzie ja piszę o jakichś procesach?! Nie bardzo rozumiem, o co Ci chodzi. Wydawało mi się, że diagram, jaki przedstawiłem, w miarę wyjaśniał koncepcję paralelizacji pętli.

[Giewont]

Przebudowałem trochę potrzebny mi algorytm (chodzi o operacje na macierzach), teraz całość wygląda w ten sposób (poprzednio podawałem tylko najistotniejszy fragment):

KOD cpp:   �  UKRYJ  �

KOD cpp:   �  POKAŻ  �

#pragma omp parallel for private(k, i, j) shared(a, q, r, n)
for (k=0; k<n; k++)
{
      r[k][k]=0;
      for (i=0; i<n; i++)
          r[k][k] = r[k][k] + a[i][k] * a[i][k];
      r[k][k] = sqrt(r[k][k]);  // ||a||
     
     for (i=0; i<n; i++)
      {
          q[i][k] = a[i][k]/r[k][k];
      }

     for(j=k+1; j<n; j++)
     {
        r[k][j]=0;
        for(i=0; i<n; i++)
                        r[k][j] += q[i][k] * a[i][j];
        for (i=0; i<n; i++)
                        a[i][j] = a[i][j] - r[k][j]*q[i][k];
      }
}
 

Niestety wersja zrównoleglona nadal działa źle - wyniki są liczbowo zupełnie inne niż w wersji sekwencyjnej (która na pewno liczy poprawnie).
Udało mi się "wyłapać", że problematycznym fragmentem jest:

KOD cpp:   �  UKRYJ  �

KOD cpp:   �  POKAŻ  �

for (i=0; i<n; i++)
 {     
          q[i][k] = a[i][k]/r[k][k];
 }

Padało pytanie o sens zrównoleglania w tym konkretnym przypadku. Takie jest zadanie na uczelnię, nie mam więc wpływu na jego treść...

Jeśli ktoś rozumie w czym tkwi błąd i potrafi mi to wyjaśnić / poprawić kod to bardzo proszę o pomoc.

[polymorphism]

O ile każdy wątek działa na swoim k, tzn. zapisuje pod indeksem k, to według mnie problem pojawia się przy zmianach wartości tablicy a.

KOD cpp:   �  UKRYJ  �

KOD cpp:   �  POKAŻ  �

for (i = 0; i < n; i++)
        ... + a[i ][k] * a[i ][k]; // <--- odczyt !!!

...

for(j = k + 1; j < n; j++)
{
        ...
       
        for (i = 0; i < n; i++)
                a[i ][j] = ...; // <--- zapis!!!
}

Pamiętaj, że te iteracje mogą się wykonywać na raz, a Ty nie masz zsynchronizowanego dostępu do a. Z drugiej strony synchronizacja spowoduje, że ideę paralelizacji pętli szlag trafi - wyliczenie k + 1 jest uzależnione od wyniku obliczeń k, zatem iteracje i tak musiałyby być wykonywane sekwencyjnie.

[Cyfrowy Baron]

Ty nie masz zsynchronizowanego dostępu do a. Z drugiej strony synchronizacja spowoduje, że ideę paralelizacji pętli szlag trafi [...] iteracje i tak musiałyby być wykonywane sekwencyjnie.

I to jest właśnie to o co sprzeczałem się wcześniej z polymorphism.

Nie pasuje do tego konkretnego przypadku, gdyż pętle muszą być wykonane po kolei.

Skoro w tym przypadku pętle muszą czekać, to wielowątkowość nie ma sensu, gdyż pętle i tak muszą być wykonane po kolei

Tylko może nie ująłem tego tak fachowo...

[polymorphism]

Chwila, spór był w kontekście innej pętli, gdzie poszczególne iteracje nie były od siebie zależne, to znaczy nie zmieniały stanu wspólnych danych (ot, klasyczny problem wielowątkowości). Pętla, którą teraz przedstawił, to zupełnie inna bajka.

[Cyfrowy Baron]

Tam były pętle zagnieżdżone wewnątrz innej pętli, ale ja wciąż dostrzegam tam zależność między tymi pętlami, więc z mojego punktu widzenia to podobny przypadek.

[polymorphism]

Ale tu nie o zagnieżdżenie pętli chodzi, tylko o (niezsynchronizowany) dostęp do zmiennych.

[Cyfrowy Baron]

Tak, tak mi dokładnie o to samo, zwróciłem tylko uwagę na to, że te pętle są zagnieżdżone, dlatego pętle wyższe muszą czekać na te wykonujące się niżej i dlatego wielowątkowość w tym przypadku nie ma sensu.

[polymorphism]

W przypadku pętli z pierwszego postu sens jest, bo tam synchronizować nic nie musisz - wspólne komórki pamięci są tylko odczytywane (A i Q), a te, które są zmieniane, czyli R[][iteracja/wątek], "należą" tylko do konkretnej iteracji/wątku. Wynik działania jednej iteracji nie ma wpływu na pozostałe.

[Giewont]

Czy w takim razie - skoro ten kod nie ma sensu w wersji równoległej (rozumiem, że musiałbym zamknąć część jako sekcję krytyczną) - ktoś z Was ma może pomysł jak przerobić całą tą "wielką pętlę" na równoważny, poprawny i sensowny kod równoległy ?

Szukam pomocy na wielu forach, ale jak na razie wszyscy są bezsilni, ja sam tym bardziej nie mam już pomysłów co z tym wszystkim zrobić

[polymorphism]

No a próbowałeś sparalelizować te trzy wewnętrzne pętle?

p.s. o jakich wielkościach n tu mowa?

[Giewont]

Próbowałem - zrównoleglanie samych wewnętrznych pętli nic nie daje, wręcz czas wykonania się wydłuża ... (też nie rozumiem za bardzo czemu :/).

Mowa o wielkościach "takich, które dają zauważalne różnice w czasie wykonania", ja na swoim sprzęcie testuję dla np. n=30. Oprócz tego fragmentu kodu musiałem też zrównoleglić mnożenie macierzy - z tym nie było żadnego problemu i faktycznie całość wykonywała się sporo szybciej.

Pozostaje więc tylko to "ustrojstwo" cały czas

[polymorphism]

wręcz czas wykonania się wydłuża ... (też nie rozumiem za bardzo czemu :/).

Mnie to nie dziwi, bo podejrzewam, że przy tak małych wartościach n zainicjowanie wątków trwa dłużej niż samo wykonanie pętli.

--- zmienione ---

Wcześniej podałem kod z paralelizacją wybranych sekcji, ale zauważyłem, że jednak będzie źle działał. Wydaje mi się, że pętla w tej formie nie da się rozbić na kilka wątków. Być może musisz znaleźć inną metodę obliczania tego, co teraz ta pętla oblicza, lub dać sobie spokój.