CYFROWY BARON • PROGRAMOWANIE • Zobacz wątek - Open MP - Zrównoleglenie zagnieżdżonej pętli.

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

dział ogólny

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

Nowy postprzez Cyfrowy Baron » środa, 12 grudnia 2012, 23:58

No to z tego, że nie ma żadnego przyspieszenia z tego tytułu, że wątek jest wykonywany w oddzielnym procesie.
Avatar użytkownika
Cyfrowy Baron
Administrator
Administrator
 
Posty: 4719
Dołączył(a): niedziela, 13 lipca 2008, 15:17
Podziękował : 12
Otrzymał podziękowań: 442
System operacyjny: Windows 7 x64 SP1
Kompilator: Embarcadero RAD Studio XE2
C++ Builder XE2 Update 4
SKYPE: cyfbar
Gadu Gadu: 0
    Windows XPFirefox

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

Nowy postprzez polymorphism » czwartek, 13 grudnia 2012, 11:25

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.
C++ Reference - opis wszystkich klas STL-a i funkcji C.
Avatar użytkownika
polymorphism
Doświadczony Programista ● Moderator
Doświadczony Programista ● Moderator
 
Posty: 2157
Dołączył(a): piątek, 19 grudnia 2008, 13:04
Podziękował : 0
Otrzymał podziękowań: 200
System operacyjny: Windows 8.1
Windows 10
Linux Mint 19
Kompilator: Visual Studio
Visual Studio Code
MSYS2 (MinGW, clang)
g++
clang
Gadu Gadu: 0
    Windows XPFirefox

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

Nowy postprzez Giewont » poniedziałek, 7 stycznia 2013, 13:33

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  
#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  
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.
Avatar użytkownika
Giewont
Bladawiec
Bladawiec
 
Posty: 10
Dołączył(a): niedziela, 23 stycznia 2011, 11:37
Podziękował : 0
Otrzymał podziękowań: 0
System operacyjny: Windows 7
Kompilator: Borland C++ Builder 6
Gadu Gadu: 0
    Windows 7Firefox

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

Nowy postprzez polymorphism » poniedziałek, 7 stycznia 2013, 19:07

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  
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.
C++ Reference - opis wszystkich klas STL-a i funkcji C.
Avatar użytkownika
polymorphism
Doświadczony Programista ● Moderator
Doświadczony Programista ● Moderator
 
Posty: 2157
Dołączył(a): piątek, 19 grudnia 2008, 13:04
Podziękował : 0
Otrzymał podziękowań: 200
System operacyjny: Windows 8.1
Windows 10
Linux Mint 19
Kompilator: Visual Studio
Visual Studio Code
MSYS2 (MinGW, clang)
g++
clang
Gadu Gadu: 0
    Windows XPFirefox

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

Nowy postprzez Cyfrowy Baron » wtorek, 8 stycznia 2013, 09:42

polymorphism napisał(a):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.

Cyfrowy Baron napisał(a):Nie pasuje do tego konkretnego przypadku, gdyż pętle muszą być wykonane po kolei.

Cyfrowy Baron napisał(a):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...
Avatar użytkownika
Cyfrowy Baron
Administrator
Administrator
 
Posty: 4719
Dołączył(a): niedziela, 13 lipca 2008, 15:17
Podziękował : 12
Otrzymał podziękowań: 442
System operacyjny: Windows 7 x64 SP1
Kompilator: Embarcadero RAD Studio XE2
C++ Builder XE2 Update 4
SKYPE: cyfbar
Gadu Gadu: 0
    Windows XPFirefox

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

Nowy postprzez polymorphism » wtorek, 8 stycznia 2013, 11:19

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.
C++ Reference - opis wszystkich klas STL-a i funkcji C.
Avatar użytkownika
polymorphism
Doświadczony Programista ● Moderator
Doświadczony Programista ● Moderator
 
Posty: 2157
Dołączył(a): piątek, 19 grudnia 2008, 13:04
Podziękował : 0
Otrzymał podziękowań: 200
System operacyjny: Windows 8.1
Windows 10
Linux Mint 19
Kompilator: Visual Studio
Visual Studio Code
MSYS2 (MinGW, clang)
g++
clang
Gadu Gadu: 0
    Windows XPFirefox

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

Nowy postprzez Cyfrowy Baron » wtorek, 8 stycznia 2013, 11:22

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.
Avatar użytkownika
Cyfrowy Baron
Administrator
Administrator
 
Posty: 4719
Dołączył(a): niedziela, 13 lipca 2008, 15:17
Podziękował : 12
Otrzymał podziękowań: 442
System operacyjny: Windows 7 x64 SP1
Kompilator: Embarcadero RAD Studio XE2
C++ Builder XE2 Update 4
SKYPE: cyfbar
Gadu Gadu: 0
    Windows XPFirefox

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

Nowy postprzez polymorphism » wtorek, 8 stycznia 2013, 12:36

Ale tu nie o zagnieżdżenie pętli chodzi, tylko o (niezsynchronizowany) dostęp do zmiennych.
C++ Reference - opis wszystkich klas STL-a i funkcji C.
Avatar użytkownika
polymorphism
Doświadczony Programista ● Moderator
Doświadczony Programista ● Moderator
 
Posty: 2157
Dołączył(a): piątek, 19 grudnia 2008, 13:04
Podziękował : 0
Otrzymał podziękowań: 200
System operacyjny: Windows 8.1
Windows 10
Linux Mint 19
Kompilator: Visual Studio
Visual Studio Code
MSYS2 (MinGW, clang)
g++
clang
Gadu Gadu: 0
    Windows XPFirefox

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

Nowy postprzez Cyfrowy Baron » wtorek, 8 stycznia 2013, 12:48

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.
Avatar użytkownika
Cyfrowy Baron
Administrator
Administrator
 
Posty: 4719
Dołączył(a): niedziela, 13 lipca 2008, 15:17
Podziękował : 12
Otrzymał podziękowań: 442
System operacyjny: Windows 7 x64 SP1
Kompilator: Embarcadero RAD Studio XE2
C++ Builder XE2 Update 4
SKYPE: cyfbar
Gadu Gadu: 0
    Windows XPFirefox

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

Nowy postprzez polymorphism » wtorek, 8 stycznia 2013, 13:09

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.
C++ Reference - opis wszystkich klas STL-a i funkcji C.
Avatar użytkownika
polymorphism
Doświadczony Programista ● Moderator
Doświadczony Programista ● Moderator
 
Posty: 2157
Dołączył(a): piątek, 19 grudnia 2008, 13:04
Podziękował : 0
Otrzymał podziękowań: 200
System operacyjny: Windows 8.1
Windows 10
Linux Mint 19
Kompilator: Visual Studio
Visual Studio Code
MSYS2 (MinGW, clang)
g++
clang
Gadu Gadu: 0
    Windows XPFirefox

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

Nowy postprzez Giewont » środa, 9 stycznia 2013, 18:57

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ć :(
Avatar użytkownika
Giewont
Bladawiec
Bladawiec
 
Posty: 10
Dołączył(a): niedziela, 23 stycznia 2011, 11:37
Podziękował : 0
Otrzymał podziękowań: 0
System operacyjny: Windows 7
Kompilator: Borland C++ Builder 6
Gadu Gadu: 0
    Windows 7Firefox

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

Nowy postprzez polymorphism » środa, 9 stycznia 2013, 19:21

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

p.s. o jakich wielkościach n tu mowa?
C++ Reference - opis wszystkich klas STL-a i funkcji C.
Avatar użytkownika
polymorphism
Doświadczony Programista ● Moderator
Doświadczony Programista ● Moderator
 
Posty: 2157
Dołączył(a): piątek, 19 grudnia 2008, 13:04
Podziękował : 0
Otrzymał podziękowań: 200
System operacyjny: Windows 8.1
Windows 10
Linux Mint 19
Kompilator: Visual Studio
Visual Studio Code
MSYS2 (MinGW, clang)
g++
clang
Gadu Gadu: 0
    Windows XPFirefox

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

Nowy postprzez Giewont » piątek, 11 stycznia 2013, 20:04

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 :(
Avatar użytkownika
Giewont
Bladawiec
Bladawiec
 
Posty: 10
Dołączył(a): niedziela, 23 stycznia 2011, 11:37
Podziękował : 0
Otrzymał podziękowań: 0
System operacyjny: Windows 7
Kompilator: Borland C++ Builder 6
Gadu Gadu: 0
    Windows 7Firefox

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

Nowy postprzez polymorphism » piątek, 11 stycznia 2013, 21:36

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.
C++ Reference - opis wszystkich klas STL-a i funkcji C.
Avatar użytkownika
polymorphism
Doświadczony Programista ● Moderator
Doświadczony Programista ● Moderator
 
Posty: 2157
Dołączył(a): piątek, 19 grudnia 2008, 13:04
Podziękował : 0
Otrzymał podziękowań: 200
System operacyjny: Windows 8.1
Windows 10
Linux Mint 19
Kompilator: Visual Studio
Visual Studio Code
MSYS2 (MinGW, clang)
g++
clang
Gadu Gadu: 0
    Windows XPFirefox

Poprzednia strona

  • Podobne tematy
    Odpowiedzi
    Wyświetlone
    Ostatni post

Powrót do Ogólne problemy z programowaniem

Kto przegląda forum

Użytkownicy przeglądający ten dział: Brak zalogowanych użytkowników i 6 gości

cron