Zmniejszenie złożoności dzięki równoległości

Czy jest możliwe (ukośnik, czy możesz podać przykład) zmniejszenie złożoności obliczeniowej problemu za pomocą algorytmu równoległego, który nie wymaga wielu procesorów w stosunku do wielkości wejściowej?

Jeśli chodzi o procesory O (1), to nie, złożoność obliczeń nie może zostać zmniejszona.

Po prostu dopasuj pracę wykonaną przez każdy procesor i zrób to na jednym. Jeśli martwisz się synchronizacją, jeden procesor może to łatwo emulować.

Pojawia się dziedzina algorytmów gruboziarnistych równoległych, w których czas działania (i inne zużycie zasobów obliczeniowych) jest uważany za funkcję niezależnych parametrów n (wielkość wejściowa) ip (liczba procesorów), często przy naturalnym założeniu n >> s .

Dobrym punktem wyjścia jest wyszukanie w Google „równoległości masowo-synchronicznej”.

Ten artykuł może Cię zainteresować:

Wydajność superliniowa w równoległych obliczeniach w czasie rzeczywistym autorstwa Selima Akl.

Podaje przykłady problemów obliczeniowych, w których „rozwiązanie sekwencyjne jest ponad razy wolniejsze niż rozwiązanie równoległe n- procesora”; odbywa się to poprzez twórczą interpretację pojęcia „problemu obliczeniowego”.$n$$n$

$p$$p$

$O(f(n)/p) \rightarrow O((1/p)f(n)) \rightarrow O(cf(n)) \rightarrow O(f(n))$$c=1/p$

$T$$T/p + SomeMoreTime$

Ale NIE zmienia się złożoność.

„nie można go obliczyć za pomocą 1 procesora, ale można obliczyć za pomocą 2.”

Nie jest to możliwe, zakładając, że oba procesory są bazami TM lub mniej wydajnym modelem. Z wikipedii, dla maszyn z wieloma taśmami:

Model ten intuicyjnie wydaje się o wiele potężniejszy niż model z jedną taśmą, ale każda maszyna z wieloma taśmami, bez względu na to, jak duże jest k, może być symulowana przez maszynę z jedną taśmą, wykorzystując tylko kwadratowo więcej czasu obliczeniowego (Papadimitriou 1994, Thrm 2.1)

Także dla maszyn wielogłowicowych, z „Symulacji w czasie liniowym maszyn wielogłowicowych z głowicami - skoki od głowy do głowy” Waltera J. Savitcha i Paula MB Vitányi:

Główny wynik tego artykułu pokazuje, że mając maszynę Turinga z kilkoma głowicami do odczytu i zapisu na taśmę i która ma dodatkową operację przesunięcia jednym ruchem „przesuń daną głowicę do pozycji innej danej głowy”, można skutecznie skonstruować wielowarstwowa maszyna Turinga z pojedynczą głowicą do odczytu i zapisu na taśmę, która symuluje ją w czasie liniowym; tzn. jeśli oryginalna maszyna działa w czasie T (n), wówczas maszyna symulująca będzie działać w czasie cT (n), dla pewnej stałej c.

Być może „równoległe lub” (biorąc pod uwagę dwie funkcje zwracające wartość logiczną, powiedz, czy jedna z nich zwraca wartość prawda, biorąc pod uwagę, że jedna z nich, ale nie obie, mogą się nie kończyć) może być tym, o czym mówisz: nie możesz obliczyć z 1 procesorem, ale może obliczyć z 2.

Jednak to wszystko zależy od tego, jakiego modelu obliczeniowego będziesz używać, niezależnie od tego, czy otrzymujesz procesy jako czarne skrzynki, czy jako ich opis, który możesz zinterpretować sam itp.