CYFROWY BARON • PROGRAMOWANIE

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

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.

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):



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:



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.

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.


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.

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...

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.

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.

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

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.

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.

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ć

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

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

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

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.