openMP - niezadowalające przyśpieszenie - merge sort

Odpowiedz Nowy wątek
sq
2012-05-27 22:15
sq
0

Cześć,
próbuję zrównoleglić merge sorta używając open MP. Zamysł jest taki że dzielę pierwotną tablicę na tyle tablic ile chce wykorzystać wątków i na tych podtablicach w kazdym watku juz klasyczny mergesort - no i potem scalam. Nie ważne czy to wydajna metoda czy nie - ale nie w tym rzecz. Wyłączam nawet dla testów końcowe scalanie. A więc w rzeczywistości na kilku wątków jest mniej roboty (bo nie scalą ostatniej iteracji) niż dla wątku jednego.
Poniżej interesujący kawałek


         double* divTab;
     #pragma omp parallel private(divTab)
          {
            int left = omp_get_thread_num()*(size/threadNum);
            int right = omp_get_thread_num() == threadNum - 1 ? size-1 : (omp_get_thread_num()+1)*size/threadNum)-1;

            divTab = copy(tab, left, right);

            mergesort(divTab, 0, right-left);
            // mergesort(tab, left, right);
          }

Ale w czym jest problem.
Jeśli uruchamiam na 8 wątkach (8 rdzeni) jest niewielkie przyśpieszczenie w stosunku do 1 wątku.
Co ciekawe dla 1 wątku:
-przez pierwsze kilkanascie sekund jest obciążenie procka 100% (a więc jeden rdzenie zużywany na całego)
-przez kolejne kilkanascie sekund jest obciążenie procka 80->50 %
Dla 8 wątków
-przez pierwsze kilka! sekund jest obciążenie procka 350-500 % (może nie na maksa ale widać że rdzenie "pracują")
-przez kolejne naście sekund obciążenie procka jest 50->20 %

Co jescze bardziej ciekawe:
jak uruchomie programik na lapku - 2 dość słabe rdzenie
To różnica między czasem na 1 wątku a na 2 wątkach jest już hmmm... akceptowalna

Nie rozumiem tego ogromnego spadku wydajności pracy do nawet 20% ? PRzecież tam nie ma żadnej synchronizacji. Nic na nic nie powinno czekać.

Będę wdzieczny za jakieś podpowiedzi czemu się tak dzieje

Pozostało 580 znaków

2012-05-28 10:41

Rejestracja: 16 lat temu

Ostatnio: 7 lat temu

0

Wątki mogą działać nierówno. Dlatego powinieneś podzielić tablicę na kilkukrotnie więcej części niż jest wątków i jeśli jakiś wątek skończy to powinien wziąć kolejną niezrobioną część.

edytowany 1x, ostatnio: adf88, 2012-05-28 10:44

Pozostało 580 znaków

2012-05-28 11:09

Rejestracja: 14 lat temu

Ostatnio: 4 dni temu

0

Spróbuję łopatologicznie wytłumaczyć czemu @adf88 ma racje.
Jeżeli działasz w jednym wątku to masz czas wykonania:
X/ŚredniaSzybkośćWątkuDlaOkresuCzasu,
jak działasz na N wątkach to czas wykonania:
Nmax((X/N)/ŚredniaSzybkośćWątkuDlaOkresuCzasu(1),..., (X/N) /ŚredniaSzybkośćWątkuDlaOkresuCzasu(N))
co można przekształcić do: N
(X/N)max(...)
lub do X
max(1/ŚredniaSzybkośćWątkuDlaOkresuCzasu(1),...,1/ŚredniaSzybkośćWątkuDlaOkresuCzasu(N))
jeżeli porównamy te dwa równania to X jest po obu stronach więc nie wpływa na porównanie, treba jedynie określić co jest większe:
średnia szybkość wątku w okresie czasu X
czy:
minimalna szybkość z N wątków w okresie czasu X/N
?
Chyba odpowiedź jest jasna :D


Wykonuję programy na zamówienie, pisać na Priv.
Asm/C/C++/Pascal/Delphi/Java/C#/PHP/JS oraz inne języki.
edytowany 3x, ostatnio: _13th_Dragon, 2012-05-28 11:10

Pozostało 580 znaków

sq
2012-05-28 21:36
sq
0

No nie przeczę że to co przedstawiłem jest optymalne ale mimo to dziwne wydaje mi się że dla 8 wątków czas jest 1.1 razy lepszy niż na 1 wątku ;/
Ale przetestuje to co mówicie. Jak sensownie w openMP można dla 8 wątków rozdzielić to na więcej tasków? Bo samo #pragma omp parallel dzieli na tyle co jest wątkow, a podzielenie na #pragma omp section nie mogę (lub mi się tak wydaje) zamknąć w jakies pętli

Pozostało 580 znaków

Odpowiedz

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0