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