Jak zmniejszyć równoległe wyniki złożoności do stale wielu rdzeni?

Miałem problemy z zaakceptowaniem złożonego poglądu teoretycznego na „efektywnie rozwiązany algorytm równoległy”, który podaje klasa NC :

NC klasa problemów, które mogą zostać rozwiązane przez algorytm równoległym w czasie o procesory . $O(\log^cn)$ $p(n) \in O(n^k)$ $c,k \in \mathbb{N}$

Możemy założyć PRAM .

Mój problem polega na tym, że wydaje się, że nie mówi to wiele o „prawdziwych” maszynach, czyli maszynach o skończonej liczbie procesorów. Teraz powiedziano mi, że „jest to znany”, że może „skutecznie” symulować algorytm procesora na procesorów. $O(n^k)$ $p \in \mathbb{N}$

Co oznacza tutaj „efektywnie”? Czy ten folklor, czy też istnieje rygorystyczne twierdzenie, które kwantyfikuje koszty ogólne spowodowane symulacją?

Obawiam się, że tak się dzieje, że mam problem z sekwencyjnym algorytmem , a także „wydajnym” algorytmem równoległym, który, gdy jest symulowany na procesorach , zajmuje również czas (co jest wszystkim tego można się spodziewać na tym poziomie szczegółowości analizy, jeśli algorytm sekwencyjny jest optymalny asymptotycznie). W tym przypadku, o ile nam wiadomo, nie ma przyspieszenia; w rzeczywistości symulowany algorytm równoległy może być wolniejszy niż algorytm sekwencyjny. To znaczy, tak naprawdę szukam stwierdzeń bardziej precyzyjnych niż bounds (lub deklaracji braku takich wyników). $O(n^k)$ $p$ $O(n^k)$ $O$

complexity-theory reference-request parallel-computing Raphael
źródło

Twierdzenie Brenta?

Cic

Czy masz na myśli

? Jeśli tak, ma to zastosowanie (afaik) tylko w niektórych okolicznościach, a także nie pozwala od razu tłumaczyć środowiska wykonawczego. A jeśli tak, proszę wyjaśnić odpowiedź.

T_{p} < \frac{W}{p} + D

$T_p < \frac{W}{p} + D$

Raphael

NC odpowiada na pytanie „czy można wymienić więcej sprzętu na krótszy czas pracy?” Możesz ograniczyć się do stałego sprzętu, a to jest podobne do ograniczania się do stałej pamięci, lepszego modelowania niektórych problemów. W celu praktycznego zastosowania zobacz addhead lookhead adders, więcej sprzętu, dzięki czemu dodawanie

bitów odbywa się w

N

$N$

O (N)

$O(N)$

AProgrammer

Odpowiedzi:

Jeśli założymy, że liczba procesorów jest ograniczona stałą, to masz rację, że problem z NC nie znaczy wiele w praktyce. Ponieważ dowolny algorytm w pamięci PRAM z k procesorami it czasem równoległym t może być symulowany za pomocą jednoprocesorowej pamięci RAM w czasie O ( kt ), czas równoległy i czas sekwencyjny mogą różnić się tylko stałym współczynnikiem, jeżeli k jest stałą.

Jeśli jednak założysz, że możesz przygotować komputer z większą liczbą procesorów w miarę wzrostu wielkości wejściowej, problem z NC oznacza, że tak długo, jak możesz przygotować więcej procesorów, czas działania będzie „bardzo krótki”, a ściślej polilogarytmiczny w wielkości wejściowej. Jeśli uważasz, że to założenie jest nierealne, porównaj je z założeniem nieograniczonej pamięci: rzeczywiste komputery mają tylko skończoną ilość miejsca, ale w badaniu algorytmów i złożoności prawie zawsze zakładamy, że urządzenie obliczeniowe nie ma stałej górnej związany z przestrzenią. W praktyce oznacza to, że możemy przygotować komputer z większą pamięcią w miarę wzrostu wielkości wejściowej, i tak zwykle używamy komputerów w prawdziwym świecie. NC modeluje analogiczną sytuację w obliczeniach równoległych.

Tsuyoshi Ito
źródło

O

$O$

k

$k$

k / 2

$k/2$

k - 1

$k-1$

n \leq 20

$n \leq 20$

Raphael

@Raphael: Pytanie, czy jakiś problem należy do NC, czy nie, nie modeluje twojego pytania. Nie twierdzę, że twoje pytanie jest nieciekawe; Mówię tylko, że NC nie jest odpowiednią klasą złożoności do modelowania tego.

Tsuyoshi Ito

Cieszę się, że to słyszę; ktoś jednak twierdzi inaczej. Niekoniecznie z NC, ale ogólnie z teoretycznymi wynikami złożoności. Jak to jest z innymi klasami?

Raphael

O (\sqrt{n})

$O(\sqrt{n})$

O (\log n)

$O(\log n)$

@JeffE: To nie jest poprawka. Napisałem tylko „przygotuj więcej procesorów”, nie nadając mu rygorystycznego znaczenia (ponieważ myślałem, że zrobienie tego może zaciemnić sens).

Tsuyoshi Ito

$NC$

$p = 1$ $NC$

Ale czekaj, jest więcej.

$NC$

$P$ $O(n^\epsilon), 0 < \epsilon < 1$ $NC$ $n$ $n$ $\sqrt n < \lg^3 n$ $n \leq 0.5 \times 10^9$ $NC$

W jednej z odpowiedzi zaobserwowano, że „W praktyce oznacza to, że możemy przygotować komputer z większą pamięcią w miarę wzrostu wielkości wejściowej, i tak zwykle używamy komputerów w prawdziwym świecie. NC modeluje analogiczną sytuację w obliczenia równoległe ".

Częściowo zgadzam się z tym punktem widzenia. Kupujemy nowy komputer równoległy z większą pamięcią, gdy starszy superkomputer jest wycofywany z eksploatacji również dlatego, że układy DRAM są tańsze w czasie i nieco równoważą komputer równoległy w odniesieniu do jego głównych komponentów (procesorów, pamięci, połączeń itp.).

$p$ $n$ $p$

Dlatego coraz ważniejsze jest projektowanie skalowalnych algorytmów równoległych pamięci, ponieważ są one praktyczne w przypadku dużych problemów.

$n^3$ $n$

Massimo Cafaro
źródło