Jak w Delphi zrealizować obliczenia równoległe przy zastosowaniu wielowątkowości ?

Problem jest typowy dla dziedziny Parallel Grid Computation. Mamy tablicę wartości liczbowych na której działamy w pętli. Obliczenia w każdej komórce tablicy zależą od wartości sąsiednich komórek z poprzedniej iteracji. Pytanie brzmi: jak najefektywniej zrealizować takie zagadnienie w Delphi z zastosowaniem obliczeń równoległych ?

Najprostszy pomysł to wykorzystanie wielowątkowości. Tablice dzielę na kilka możliwie równych części (np. na tyle ile mam dostępnych w sytemie rdzeni). Następnie dla każdego fragmentu tablicy tworzę nowy wątek obliczeniowy. Po każdekj iteracji muszę złożyć tablicę w całość - czyli poczekać aż wszystkie wątki dokończą daną iterację i przejść do następnej.

Problem jest właśnie w tym czekaniu, które w wielu przypadkach może trwać dłużej niż same obliczenia. Oczywiście jest wiele technik i algorytmów, które mają na celu ograniczenie konieczności synchronizacji wątków do absolutnego minimum ale to zagadnienie na razie pomijam.

Mój pomysł na poradzenie sobie z tym problem wygląda następująco:

W wątku głównym tworzę kilka wątków obliczeniowych, które przechowuje w tablicy:

TablicaWatkow: array [0..7] of TMojThread;

Każdy wątek w ramach konstruktora otrzymuje swój unikalny numer (nr) odpowiadający jego indeksowi w tablicy:

for i := 0 to 7 do
 TablicaWatkow[i]:=TMojThread.Create(i);

Utworzyłem również w wątku głównym tablicę zdarzeń (TEvent) w celu określenia czy wszystkie wątki wykonały daną pętle:

TablicaZdarzen: array [0..7] of TEvent;
TablicaUchwytowZdarzen: array [0..7] of THandle;

Po wykonaniu danej pętli każdy wątek czeka na wykonanie się pętli w wątkach równoległych:

procedure TMojThread.Execute;
...
begin
  for i := 0 to liczba_petli  //główna pętla obliczeniowa
  begin
    WaitForMultipleObjects(8, @Watek_glowny.TablicaUchwytowZdarzen, True, INFINITE);

    Watek_glowny.TablicaZdarzen[nr].ResetEvent;

    ... //właściwe obliczenia na tablicy

    Watek_glowny.TablicaZdarzen[nr].SetEvent;
  end;
end;

czas na pytanie :) Czy taka metoda synchronizacji wątków (poprzez wykorzystanie instrukcji WaitForMultipleObjects dla kilku zdarzeń odpowiadających poszczególnym wątkom) jest najbardziej efektywna ? Czy można to jakoś przyspieszyć ? Chciałbym również wykorzystać instrukcję WaitForMultipleObjects(8, @TablicaUchwytow, True, INFINITE) w wątku głównym do sprawdzenia czy wszystkie wątki obliczeniowe zakończyły się, niesty jej dodanie powoduje zatrzymanie wszystkich wątków (łącznie z głównym) - nic się nie dzieje. Jakieś pomysły dlaczego tak jest ?

Pozdrawiam i z góry dziękuje za pomoc.

Ehh... czyżby nikt nie mógł mi pomóc ? No nic spróbuje bardziej konkretnie.

• po pierwsze czy ktoś wie w jaki sposób w profesjonalnych systemach realizowane są takie obliczenia równoległe ?
• czy zastosowanie wielu wątków obliczeniowych to najlepszy (jedyny) pomysł ?
• wiem, że istnieją takie protokoły jak Message Passing Interface (MPI) do obliczeń równoległych na systemach klastrowych i superkomputerach, ale z tego co się orientuję odpowiadają one głównie za warstwę komunikacyjną. Czy w przypadku obliczeń lokalnych (na poszczególnych rdzeniach, jednego lub dwóch procesorów) jest sens bawić się w coś takiego jak MPI ?
  -Jak najefektywniej przesyłać dane pomiędzy wątkami ?
  -Zaproponowana powyżej metoda synchronizacji wątków bazuje na http://docs.embarcadero.com/products/rad_studio/delphiAndcpp2009/HelpUpdate2/EN/html/devwin32/win32_mthreadwaitforthreads_xml.html z tą różnicą, że zastosowałem śledzenie wielu obiektów TEvent odpowiadającym poszczególnym wątkom. Mam jednak spore wątpliwość czy jest to rozwiązanie efektywne :/ Przy przypisaniu wątków do poszczególnych rdzeni (Affinity Mask) jestem w stanie obciążyć je przy sprzyjających wiatrach do 70-80% (co jak sądzę wiąże się właśnie z synchronizacją), a więc nie korzystam z całej dostępnej mocy obliczeniowej. Można coś z tym zrobić ?

Jak ktoś coś wie niech powie ;)

-Jak najefektywniej przesyłać dane pomiędzy wątkami ?

Shared Memory

• czy zastosowanie wielu wątków obliczeniowych to najlepszy (jedyny) pomysł ?

• w ramach jednego procesu tak. możesz też stworzyć wiele jedno- lub dwuwątkowych (drugi wątek do kontroli stanu pierwszego wątka) procesów i uruchamiać ich tyle, ile masz rdzeni + komputerów. afaik synchronizacja wątków działa nieco efektywniej niż procesów.

• wiem, że istnieją takie protokoły jak Message Passing Interface (MPI) do obliczeń równoległych na systemach klastrowych i superkomputerach, ale z tego co się orientuję odpowiadają one głównie za warstwę komunikacyjną. Czy w przypadku obliczeń lokalnych (na poszczególnych rdzeniach, jednego lub dwóch procesorów) jest sens bawić się w coś takiego jak MPI ?

• nie mam zielonego pojęcia. jednak o ile nie dysponujesz klastrem/chmurą, to możesz użyć "zwykłego" IPC. z doświadczenia wiem, że IPC nie przeszkadza w całkowitym obciążeniu obliczeniami wszystkich rdzeni.

-Jak najefektywniej przesyłać dane pomiędzy wątkami ?

• tak jak w odpowiedzi wyżej - pamięć współdzielona, a do synchronizacji muteks lub semafor.

-Zaproponowana powyżej metoda synchronizacji wątków bazuje na http://docs.embarcadero.com/products/rad_studio/delphiAndcpp2009/HelpUpdate2/EN/html/devwin32/win32_mthreadwaitforthreads_xml.html z tą różnicą, że zastosowałem śledzenie wielu obiektów TEvent odpowiadającym poszczególnym wątkom. Mam jednak spore wątpliwość czy jest to rozwiązanie efektywne :/ Przy przypisaniu wątków do poszczególnych rdzeni (Affinity Mask) jestem w stanie obciążyć je przy sprzyjających wiatrach do 70-80% (co jak sądzę wiąże się właśnie z synchronizacją), a więc nie korzystam z całej dostępnej mocy obliczeniowej. Można coś z tym zrobić ?
*spróbuj sprawdzić, czy problem na pewno wiąże się z MPI. obstawiam, że zbyt agresywnie napisałeś synchronizację i wątki muszą na siebie zbyt długo czekać. zastanawia mnie sens przypisywania wątków do rdzeni. myślę, że nie będzie różnicy, skoro na każdym rdzeniu działa tak czy inaczej taki sam wątek, a różnice są tylko w danych, przy czym L2 zdaje się jest współdzielone między rdzeniami, jedyna różnica może być w L1 (możesz to łatwo sprawdzić). inną sprawą jest to, czy system jest skonfigurowany tak, żeby pozwolić w pełni obciążyć CPU - może mieć ustawiony priorytet dla usług, może gwarantować kilkanaście i więcej procent mocy CPU dla obsługi kart sieciowych... to też możesz łatwo sprawdzić, napisać krótki program-toster z ośmioma wątkami roboczymi bez żadnej synchronizacji.

Panowie dzięki wielkie za pomoc i konkretne wskazówki !

-Co do pamięci współdzielonej to oczywiście sprawie się przyjże :)
-O MPI pytam jedynie z ciekawości bo sam wolałbym tego uniknąć (przede wszystkim dlatego, że się na tym kompletnie nie znam). Jeżeli wystarcza IPC to tym lepiej.
-Jeżeli chodzi o obciążenie procesora to tu sprawa jest bardziej skomplikowana. Już wcześniej przygotowałem taki program testowy (bez synchronizacji operujący na zmiennych globalnych) i zarówno w przypadku rozdzielenia wątków na rdzenie jak i bez takiego rozdziału, CPU jest obciążone na 100%. Stąd zgadzam się z opinią, że problem tkwi w synchronizacji. Wątki synchronizuję tak jak w pierwszym poście - flaga TEvent dla każdego wątku i WaitForMultipleObjects. Ponieważ muszę zsynchronizować wątki po każdej iteracji (a tych iteracji jest naprawdę sporo) zdecydowałem się na takie rozwiązanie. wygląda jednak na to, że za dużo czasu spędzam na "czekaniu" przez co procesor jest obciążony tylko częściowo. Nie mam pojęcia jak w moim przypadku wykorzystać do synchronizacji np. semafory czy muteksy? Jakieś pomysły na zoptymalizowanie przedstawionej powyżej procedury procedure TMojThread.Execute; ?

MichałSz napisał(a)

... jestem w stanie obciążyć je przy sprzyjających wiatrach do 70-80% (co jak sądzę wiąże się właśnie z synchronizacją), a więc nie korzystam z całej dostępnej mocy obliczeniowej. Można coś z tym zrobić ?

Jak ktoś coś wie niech powie ;)

Jeśli między iteracjami część wątków się nudzi czekając na zakończenie pozostałych to taki IMHO powinien być właśnie efekt. Powinieneś dążyć do idealnego rozdziału pracy między wątki, tak aby zminimalizować różnice w czasach działania każdego z nich.

b

MichałSz napisał(a)

Chciałbym również wykorzystać instrukcję WaitForMultipleObjects(8, @TablicaUchwytow, True, INFINITE) w wątku głównym do sprawdzenia czy wszystkie wątki obliczeniowe zakończyły się, niesty jej dodanie powoduje zatrzymanie wszystkich wątków (łącznie z głównym) - nic się nie dzieje. Jakieś pomysły dlaczego tak jest ?

Spróbuj użyć PWOHandleArray, z tego co pamiętam, jest też limit na ile wątków jednocześnie można czekać.

b

Gdzieś słyszałem że jakieś nowe wersje kompilatorów mają specjalne instrukcje do generowania kodu maszynowego, które pozwalają systemowi operacyjnemu na przesłanie poleceń do poszczególnych rdzeni procesora (podział zadań). Nie znam szczegółów dla Delphi. Używa się poleceń takich jak cobegin i coend.
http://wazniak.mimuw.edu.pl/index.php?title=Programowanie_wsp%C3%B3%C5%82bie%C5%BCne_i_rozproszone/PWR_Wyk%C5%82ad_1

b0bik i Mariusz dzięki ! przyjrzę się zarówno PWOHandleArray jak i cobegin, coend (chociaż cobegin i coend to dla mnie czarna magia i nie mam zielonego pojęcia z czym to się je).
Zabrałem się natomiast za współdzielenie pamięci i uświadomiłem sobie nagle, że przecież wątki, w przeciwieństwie do procesów z założenia współdzielą ten sam obszar pamięci. Czy jest więc sens tworzenia odrębnych mechanizmów współdzielenia pamięci ? Czy nie wystarczy, że wątki korzystają z zestawu tych samych zmiennych globalnych ? Czy odwoływanie się z wątków obliczeniowych do zmiennych globalnych wątku głównego nie wpływa negatywnie na wydajność ?

Nadal pozostał problem nie wykorzystanej mocy obliczeniowej procesora... może ktoś w wolnej chwili (jak mu się bardzo nudzi ;) ) mógłby spróbować zrobić coś takiego albo doradzić jak to efektywnie zaprogramować :

• zadeklarować dwie dwuwymiarowe tablice np. Tab_nowa, Tab_stara składające się z elementów typu double
• Tab_nowa podzielić np na cztery równe części i dla każdej z nich stworzyć nowy wątek
• Wątek ma operować na swojej części w pętli (np. 1000000 iteracji)i wykonać np takie zadanie Tab_nowa[i,j]:=ABS(sqrt(Tab_stara[i,j]/2)+sqr(Tab_stara[i,j])-100) //działanie nie ma na razie znaczenia chodzi tylko o to żeby się chwilę liczyło
• po każdej iteracji czekamy aż wszystkie wątki skończą obliczenia i przepisujemy tablice Tab_stara := Tab_nowa i przechodzimy do kolejnej pętli.

Ja zrobiłem to tak jak to przedstawiłem w pierwszym poście, ale chyba nie jest to najlepszy pomysł.

Jak zawsze będę wdzięczny za każdy pomysł czy podpowiedź.

MichałSz napisał(a)

Czy jest więc sens tworzenia odrębnych mechanizmów współdzielnia pamięci ? Czy nie wystarczy, że wątki korzystają z zestawu tych samych zmiennych globalnych ? Czy odwoływanie się z wątków obliczeniowych do zmiennych globalnych wątku głównego nie wpływa negatywnie na wydajność ?

No właśnie takie odwoływania musisz synchronizować (używać Synchronize()), co wpływa na wydajność, no ale coś za coś (jest jeszcze threadvar i TLS, ale to trochu coś innego). Można też inaczej, np komunikatami. Zależy co potrzebujesz osiągnąć. Są też muteksy, sekcje krytyczne, semafory ... zależy od zastosowania.

b

Chyba nie do końca jasno się wyraziłem. Oczywiście znam mechanizmy synchronizacji wątków w Delphi (semafory, mutexy, sekcje krytyczne itp.) ale mam wrażenie (chyba, że się mylę), że w moim przypadku raczej nie znajdą zastosowania. Synchronizacja w Delphi (a bardziej ogólnie w Windows) ma na celu zabezpieczenie się przed dostępem kilku wątków do tego samego obiektu poprzez ich wzajemne blokowanie, mnie natomiast interesuje sytuacja dokładnie odwrotna... w jaki sposób zmusić wątki aby wykonywały pewne czynności synchronicznie ?
Dla przykładu... jeżeli np. w każdym z trzech wątków jest pętla, a wszystkie trzy wątki wystartowały jednocześnie (i robią to samo) to i tak po jakimś czasie okaże się, że wątek_1 wykonał: 7200 iteracji wątek_2: 6800, a wątek_3 np. 7000. Mnie interesuje synchronizacja w sensie potocznym, czyli zgranie w czasie operacji wykonywanych w wątkach, a więc w dowolnej chwili każdy z trzech wątków będzie wykonywał tą samą iterację.
Pozostaje tylko jedno pytanie... jak to zrobić, żeby się nie okazało, że czekanie trwa więcej niż liczenie ??

Są jeszcze włókna : ) Wtedy możesz sterować wywłaszczaniem we własnym zakresie. Ale generalnie ciężko będzie chyba osiągnąć to żeby wszystko szło idealnie równolegle. Nie zapanujesz nad tym ile czasu przydziela Ci system. Można jeszcze manipulować priorytetami.

IMHO jak podzielisz robotę po równo - to będzie dobrze. Czyli aby każdy wątek miał tyle samo do zrobienia, tak samo trudnych rzeczy.

b

Ale Fiber to jak wątki w wersji light. Raczej przydają się do lżejszych i prostszych prac.