Maksymalne przyspieszenie programu równoległego

0

Czy jest możliwe uzyskanie przyspieszenia algorytmu równoległego takiego że wraz ze wzrostem liczby procesorów n razy, czas wykonywania algorytmu maleje prawie n^2 razy?
Wyszło mi takie cudo w moim programie że na jednym procesorze wykonuje się np. w 20 sekund a na dwóch w około 5,5sek czyli prawie 4 razy krócej. Ten algorytm ma złożoność obliczeniową n^2 i z jednej strony można pomyśleć że jak będzie miał 2 razy mniej danych do przerobienia (bo 2 razy zwiększy się liczba procesorów) to czas zmaleje 4 razy.
Z drugiej strony nigdy nie słyszałem o takim speedup'ie. Dla upewnienia się, zrównolegliłem (korzystając z MPI) dwie zagnieżdżone pętle for i efekt jest taki że jak liczba core'ów rośnie n razy, to liczy się to w prawie n razy krótszym czasie (a nie n^2).

Biorę pod uwagę to że gdzieś w moim programie jest bug którego znacznie zmniejsza się wraz z liczbą procesorów na których chodzi algorytm. Nie wiem czy to możliwe ale jak inaczej to wytłumaczyć.

0

Nie bardzo rozumiem jaki masz problem. Masz algorytm który ma złożoność O(n^2). Licząc go dla wejścia masz czas X. Licząc go dla połowy danych masz X/4
Licząc go dla połowy danych na dwóch procesorach masz X/4 + Y gdzie Y jest czasem na "złożenie" wyniku.
Wynika z tego że skoro X = 20 sekund, to wersja równoległa powinna trwać 5 + Y sekund
Czyli tyle ile trwała.

0

cuda raczej się nie zdarzają :) wątpię, abyś nagle dobrał się do drugiego rdzenia w procku, więc pozostaje inne wytłumaczenie :) wyłączyłeś kilka programów działających w tle lub jak wolisz uruchomiłeś twój program raz na kompie z procesorem jednordzeniowym, drugi, na lepszym :)
Zresztą czcze gadanie, ani kodu nie przedstawiłeś, ani pomysłu. @Shalom ma rację - bez istotnej zmiany w algorytmie i sposobie wykorzystywania zasobów nie powinno się uzyskać wzrostu wydajności większej niż 5-12% :)

0

Jeśli masz ponadliniowe przyspieszenie to prawie na pewno masz buga.

Skoro na dwóch prockach masz 4 x wyższą prędkość to zrób podobny trik na jednym procesorze - podziel zadanie na dwie części i policz je osobno :P Będziesz miał dwukrotne przyspieszenie bez użycia dodatkowych rdzeni :P

0

@Wibowit nie wiem czy wiesz, ale takie podejście nazywa sie "dziel i zwyciężaj" i dzięki niemu można sortować czy liczyć transformatę fouriera w O(nlogn) zamiast O(n^2)
Skoro autor jest w stanie podzielić sobie dane na pół i liczyć sobie to oddzielnie to najpewniej to jego O(n^2) da się zamienić na O(nlogn).

0

@Shalom - zgadza się. Miałem mały błąd w tym drugim programie testującym o którym pisałem (2 zagnieżdżone for'y) i dlatego nie wychodziło tak jak powinno. Teraz jest dobrze czyli speedup prawie n^2. Dzięki!

Pozostałym Panom dziękuję za "starania". Nikt nie powiedział że uruchamiam to na swoim 2/4 rdzeniowym procesorze. Do odpowiedzi na to pytanie, nie był potrzebny gram kodu.

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