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 B , liczby słów, które można jednocześnie przenieść do pamięci. Czasami L i Z są używane dla $M$$B$$L$$Z$$B$ i odpowiednio. $M$

Na przykład sortowanie wymaga kosztu a naiwne mnożenie macierzy wymaga Θ ( n 3 / B $\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 M . 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 f ( N , B ) / 2 O ( M $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 N jest rozmiarem wejściowym i wyraźnie M > w . Następnie przyspieszenie od 2 M daje wielomianu przyspieszenie w N . 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$

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 M to O ( log N ) , potrzebujesz wykładniczej liczby operacji we / wy ( ponieważ nie można „pozostać” w tym samym bloku pamięci o rozmiarze O ( log N ) więcej niż wielomianową liczbę kroków bez wchodzenia w cykl) i jeśli M $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ą Ω ( N ) (ponieważ oznaczałoby to, że mamy wykładniczą liczbę operacji). Ale jeśli przyspieszenie dotyczy tylko mniejszych wartości M , 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 O ( log N ), z których każdy wymaga wykładniczego czas we własnym rozmiarze i wykładnicza liczba operacji we / wy (to znaczy p $M$$\Omega(N)$$M$$O(\log N)$ , ponieważ p o l y ( N ) jest wykładniczy w O ( log N ) ). W praktyce wierzę$poly (N)$$poly(N)$$O(\log N)$ kompletne problemy, takie jak T Q B F, spełniają twój warunek.$PSPACE$$TQBF$

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.