Wykładnicze przyspieszenie w pamięci zewnętrznej

tło

Pamięć zewnętrzna lub model DAM określa koszt algorytmu na podstawie liczby operacji we / wy, które wykonuje (w zasadzie liczby braków pamięci podręcznej). Te czasy działania są na ogół podawane w kategoriach , wielkości pamięci i , liczby słów, które można jednocześnie przenieść do pamięci. Czasami i są używane dla $M$ $B$ $L$ $Z$ $B$ i odpowiednio. $M$

Na przykład sortowanie wymaga kosztu a naiwne mnożenie macierzy wymaga $\Theta(N/B\log_{M/B} N/B)$ . $\Theta(n^3/B\sqrt{M})$

Model ten jest wykorzystywany do analizy „Cache-niepomny algorytmy”, które nie mają wiedzy na temat lub . Zasadniczo celem jest optymalne działanie algorytmu ignorującego pamięć podręczną w modelu pamięci zewnętrznej; nie zawsze jest to możliwe, jak na przykład w przypadku problemu permutacji (pokazane w Brodal, Faderberg 2003 ). Zobacz ten artykuł Erika Demaine'a, aby uzyskać dodatkowe wyjaśnienie algorytmów nieobjętych pamięcią podręczną, w tym omówienie sortowania i mnożenia macierzy. $B$ $M$

Widzimy to zmieniające się $M$ powoduje przyspieszenie logarytmiczne do sortowania i przyspieszenie wielomianowe do mnożenia macierzy. (Ten wynik pochodzi z Hongkongu, Kung 1981 i faktycznie wyprzedza zarówno pamięć podręczną, jak i formalizację modelu pamięci zewnętrznej).

Moje pytanie brzmi:

Czy jest jakiś przypadek, w którym przyspieszenie jest wykładnicze w ? Czas działania będzie taki jak $M$ $f(N,B)/2^{O(M)}$ . Szczególnie interesuje mnie algorytm lub struktura danych nieobsługująca pamięci podręcznej, która pasuje do tego opisu, ale byłbym zadowolony z algorytmu / struktury danych obsługującej pamięć podręczną lub nawet najlepiej znanej dolnej granicy.

Ogólnie w większości modeli przyjmuje się, że rozmiar słowa jeśli jest rozmiarem wejściowym i wyraźnie . Następnie przyspieszenie od daje wielomianu przyspieszenie w . To sprawia, że wierzę, że jeśli problem, którego szukam, istnieje, nie jest on wielomianem. (W przeciwnym razie możemy zmienić rozmiar pamięci podręcznej o stałą, aby uzyskać stałą liczbę operacji we / wy, co wydaje się mało prawdopodobne). $w = \Omega(\log N)$ $N$ $M > w$ $2^M$ $N$

ds.algorithms ds.data-structures cache-oblivious SamM
źródło

zgaduję, ale

? znalazłeś przypadek podany jako przyspieszenie

, wystarczający?

N =

$N=$

B^{p o l y l o g (B)}

$B^{\rm{polylog}(B)}$

vzn

Niestety dla moich celów musi to być litera

Byłbym zainteresowany referencją.

M

$M$

SamM

wikipedia o pamięci podręcznej algorytmów nieświadomych . fyi w tej notacji pól jest trochę subtelności. p7 przypis Demaine mówi w tym obszarze, że

jest rozmiarem problemu, a czasami

gdzie

jest liczbą bloków, „ale notacja z małą literą wydaje się wypadać z łaski”. używasz

powyżej i alternatywnie

najwyraźniej oba jako rozmiar wejściowy. myślę, że powinieneś przynajmniej ujednolicić swoje pytanie.

N

$N$

n = N / B

$n = N/B$

n

$n$

n

$n$

N

$N$

vzn

Zredagowałem to dla zachowania spójności.

jest rozmiarem danych wejściowych, a

służy tylko do mnożenia macierzy, ponieważ czas działania tego problemu jest ogólnie definiowany w kategoriach macierzy

(tj.

)

N

$N$

n

$n$

n \times n

$n\times n$

N = n^{2}

$N = n^2$

SamM

nie widzę takich przypadków po zeskanowaniu literatury. może nie ma takiego ref? może jest jakiś przypadek, aby uzasadnić, że każdy taki algorytm może być złożony, a zatem trudny do teoretycznej analizy w celu uzyskania takiego przyspieszenia ...? a może trzeba to wymyślić ...? a może nie jest to możliwe? czy może być pomysł, że losowy dostęp do pamięci jest najgorszym możliwym przypadkiem? wygląda na to, że wzrost prędkości jest liniowy w

w tym przypadku ...? a może jakaś fraktalna struktura dostępu do pamięci jest najgorszym przypadkiem? ten kierunek studiów ma niewiele ponad dziesięć lat ...

M

$M$

dniu

Odpowiedzi:

Nie jestem pewien, czy zrozumiałem pytanie. Wydaje mi się jednak, że przy założeniu, że zawiera problemy wymagające czasu wykładniczego, takie problemy spełniłyby twoje wymagania, ponieważ jeśli to , potrzebujesz wykładniczej liczby operacji we / wy ( ponieważ nie można „pozostać” w tym samym bloku pamięci o rozmiarze więcej niż wielomianową liczbę kroków bez wchodzenia w cykl) i jeśli $PSPACE$ $M$ $O(\log N)$ $O( \log N)$ $M=N$ potrzebujesz tylko liniowej liczby operacji we / wy. Także w odniesieniu do twojej obserwacji, że taki problem nie może należeć do $P$ , poprawne jest, czy przyspieszenie musi utrzymać wartości które są (ponieważ oznaczałoby to, że mamy wykładniczą liczbę operacji). Ale jeśli przyspieszenie dotyczy tylko mniejszych wartości , intuicyjnie uważam, że nie jest to prawdą, ponieważ uważam, że powinno być możliwe zaprojektowanie problemu, który w rzeczywistości jest połączeniem mniejszych problemów o rozmiarze których każdy wymaga wykładniczego czas we własnym rozmiarze i wykładnicza liczba operacji we / wy (to znaczy $M$ $\Omega(N)$ $M$ $O(\log N)$ , ponieważ jest wykładniczy w ). W praktyce wierzę $poly (N)$ $poly(N)$ $O(\log N)$ kompletne problemy, takie jak spełniają twój warunek. $PSPACE$ $TQBF$

użytkownik8477
źródło

Obawiam się, że nie podążam za niektórymi z twoich argumentów. Jeśli

, każdy problem w pamięci zewnętrznej jest trywialny. Jak wspomniałem,

jest nieco głupie, ponieważ oznacza to, że pamięć ma tylko stałą liczbę słów (możliwe, ale nie sposób, w jaki pamięć zewnętrzna jest ogólnie badana). Widzę, co mówisz, że był wykładniczy wzrost, ale to nic nie mówi o wartościach pośrednich. Na przykład optymalna partycja w pamięci zewnętrznej to min dwóch terminów (zasadniczo, jeśli wszystko mieści się w pamięci, robimy coś zupełnie innego, niż jeśli nie). Czy możesz to wykluczyć?

M = Ω (N)

$M= \Omega(N)$

M = O (\log N)

$M = O(\log N)$

SamM

Nie rozumiem, dlaczego jakikolwiek problem w pamięci zewnętrznej jest trywialny, jeśli

. Jeśli

i algorytm zajmuje, wykładniczy czas, możesz być zmuszony do zamiany tam iz powrotem pomiędzy (niejako mówiąc) wykładniczymi liczbami dwie połówki pamięci.

M = Ω (N)

$M = \Omega(N)$

M = N / 2

$M=N/2$

user8477

Ach, oczywiście masz rację, że stały czynnik jest ważny. To ma sens; to z pewnością dobry punkt wyjścia.

SamM

M = ω (\log N)

$M=\omega(\log N)$

T (N) / 2^{M}

$T(N)/2^M$

T (N)

$T(N)$

dawałby

-4

pytanie to wydaje się zmieniać na terra incognita, tj. niezbadane terytorium. po kilku przemyśleniach i recenzjach, oto kilka myśli / pomysłów na to pozornie bardzo trudne / subtelne pytanie, które, mam nadzieję, będzie inteligentne, ale nie ma być ostateczne.

Demain, kogo cytujesz, pisze: „główna idea [algorytmów nieświadomych z pamięci podręcznej] jest prosta: projektuj algorytmy pamięci zewnętrznej bez wiedzy $B$ i $M$ . Ale ten prosty pomysł ma kilka zaskakująco potężnych konsekwencji ”.

wydaje się również mieć zaskakująco subtelne implikacje. analiza tego modelu pod kątem ekstremalnych zachowań wydaje się trudna i wydaje się, że do tej pory nikt tego nie zrobił. jest kilka ankiet i wydaje się, że do tej pory badali całą dziedzinę. nie jest to zaskakujące, biorąc pod uwagę, że pole ma zaledwie ~ 1 dekadę.

wydaje się, że model nie został jeszcze przetłumaczony na maszyny Turinga, gdzie możliwa jest bardziej rygorystyczna / formalna / teoretyczna / ogólna / standardowa analiza. cała koncepcja notacji Big-Oh oraz jej implikacje i intuicje, takie jak nieistotność stałych, niekoniecznie automatycznie zawiera się w tym obszarze algorytmów pamięci podręcznej. na przykład model wydaje się już działać ze stałymi $B,M$ które dokładnie mierzą rozmiary pamięci. wydaje się, że pole nie ma do tej pory zestawu podstawowych aksjomatów jego dynamiki.
TM zostały wynalezione w 1936 roku przez Turinga i Hartmanis-Stearns twierdzeń czas / przestrzeń hierarchii (które są nieco nawiązując do tego pytania) zostały odkryte w 1965 roku ów niezwykły ~ 3 dziesięcioleci jeszcze twierdzenia czas / przestrzeń hierarchii są uważane za nieco elementarne i prowadzone w klasach licencjackich. wydaje się, że nie istnieją jeszcze odpowiednie twierdzenia dotyczące hierarchii ustanowione w tym modelu, a jak to zrobić, nie jest trywialnym problemem. model ten wydaje się mieć więcej „ruchomych części” niż standardowa maszyna Turinga (która ma już dość diabelnie złożoną dynamikę), tj. jest jak rozszerzona maszyna Turinga.
innym pomysłem jest jakoś przekonwertowanie tego modelu pamięci zewnętrznej na bazy TM, co ponownie nie wydaje się pojawiać w literaturze / badaniach na temat algorytmów pamięci podręcznej i może zobaczyć, jak mogłyby się tłumaczyć twierdzenia hierarchii Hartmanisa-Stearnsa. wydaje się, że odnosi się do dwóch taśm TM, gdzie jedna taśma ma rozmiar „M”, a druga taśma jest nieskończona, a bloki są przenoszone do „M” w rozmiarach „B”. ale trudność polega na tym, że jest to raczej model pamięci RAM niż model Turinga, który korzysta z sekwencyjnego dostępu do taśmy. z drugiej strony może to wpaść w subtelności związane z konwersjami między TM pojedynczymi a wielopasmowymi .
zasugeruj empirycznie zaatakowanie tego problemu za pomocą symulacji, na których literatura zwykle się koncentruje, np. jak w tej wielkiej ankiecie Kumara na temat algorytmów pamięci podręcznej w (2003). istnieje wiele programów i dokumentów online do symulacji pamięci podręcznej i można by odpowiedzieć na twoje pytanie bez dużej ilości kodu, stosując pewne uproszczenia. jedną podstawową ideą jest stworzenie algorytmów probabilistycznych, które uzyskują dostęp do „pobliskich” obszarów pamięci w oparciu o prawdopodobieństwa. „pobliski” tutaj niekoniecznie jest ciągłą pamięcią, ale zamiast tego algorytm wybiera losowe strony pamięci (bloki) w oparciu o śledzenie własnych ostatnio odwiedzanych stron. zasugeruj użycie prawa mocy celu ustalenia prawdopodobieństwa wybrania „bliskich” stron z listy „ostatnio odwiedzanych”. wydaje się, że jest to kluczowy aspekt związany z poprawą wydajności opartej na pamięci podręcznej.
Oto szorstki argument oparty na „M”, który jest w zasadzie miarą „pamięci rdzeniowej” w porównaniu z pamięcią dyskową. w przypadku algorytmu można oczekiwać, że wraz ze wzrostem pamięci rdzenia zbliża się tylko [asymptotycznie] do liniowej poprawy prędkości algorytmu, a dodanie „pamięci rdzenia” w celu uzyskania jakiegokolwiek nieliniowego wzrostu prędkości algorytmu wydaje się intuicyjnie prawie jak przekroczenie prędkości limit i „zdobywanie czegoś za nic”. nie chwytaj jednak modelu wystarczająco dobrze, aby to udowodnić [ale najwyraźniej nikt inny też go nie ma, w tym władze / założyciele / eksperci].
ta literatura dotycząca algorytmów niepamięci podręcznej koncentrowała się na algorytmach P i jak dotąd nie spotkała się z żadną analizą algorytmu innego niż P i być może żaden z nich nie istnieje. może to być spowodowane tym, że analiza jest zbyt trudna! w takim przypadku pytania dotyczące ekstremalnych zachowań mogą pozostać bez odpowiedzi w tej dziedzinie w perspektywie długoterminowej.
nie wydaje się nawet intuicyjnie jasne, ani być może w ogóle jeszcze zbadane, o tym, jak zachowują się w tym modelu algorytmy „małej” złożoności, takie jak w L, lub „duże”, takie jak non-P (np. Expspace itp.). model mierzy lokalizację pamięci, która wydaje się zasadniczo inna, ale spleciona z hierarchią czasu i przestrzeni.
istnieje nieco niejasny pomiar złożoności maszyny Turinga, zwany „złożonością odwracalną”, z pewnymi badaniami, wynikami i dokumentami, które mogą być ze sobą powiązane. Zasadniczo TM może obejmować pewną ilość czasu i przestrzeni, ale odwrócenia są dość niezależnym pomiarem głowicy taśmy podczas obliczeń. wydaje się, że „wysokie odwrócenie” może być związane z „lokalizacją wysokiej pamięci”, ponieważ w obu przypadkach głowica taśmy ma tendencję do pozostawania w „mniejszym” regionie w porównaniu do przemieszczania się w większe regiony.
to pytanie i model przypomina mi prawo Amdahlsa i podejrzewam, że w tym obszarze może obowiązywać lub obowiązywać jakiś nieodkryty jeszcze podobny przepis związany ze zmniejszającymi się zwrotami lub saldami / kompromisami. zgrubne rozumowanie: teoria algorytmów nieświadomych w pamięci podręcznej szuka równowagi / kompromisu między skończoną „lokalną” pamięcią a zewnętrznym „nieskończonym” dyskiem opartym na kosztach. są to w zasadzie dwa zasoby, które zachowują się „równolegle” i prawdopodobnie istnieje pewien rodzaj optymalnego kompromisu między nimi.

vzn
źródło

W twoim pierwszym punkcie, co oznaczałoby „bardziej teoretyczna analiza”? TM nie ma

k

$k$ -poziom hierarchii pamięci. Model z idealną pamięcią podręczną jest łatwy i naturalny w pracy, a eksperymentalnie udowodniono, że jest użytecznym modelem w odniesieniu do zachowania pamięci w prawdziwych systemach.

Juho,

model TM jest podstawowym modelem TCS i „pomostem thms” między jego hierarchią złożoności (czas / przestrzeń, podstawowe klasy złożoności, takie jak P / NP itp.) z algorytmami niewidocznymi dla pamięci podręcznej, które najwyraźniej pozostają do zmapowania. modele pamięci zewnętrznej i powiązane, nieświadome modele pamięci podręcznej zasadniczo próbują modelować rzeczywiste parametry wydajności, a literatura nie jest do tej pory zainteresowana większymi abstrakcjami teoretycznymi, takimi jak zadawane przez pytanie.

vzn