Exponentielle Beschleunigung im externen Speicher

Hintergrund

Der externe Speicher oder das DAM-Modell definiert die Kosten eines Algorithmus durch die Anzahl der durchgeführten E / As (im Wesentlichen die Anzahl der Cache-Fehlschläge). Diese Laufzeiten werden im Allgemeinen in Form von $M$ , der Speichergröße und $B$ , der Anzahl der Wörter, die gleichzeitig in den Speicher übertragen werden können, angegeben. Manchmal werden $L$ und $Z$ für $B$ bzw. $M$ verwendet.

Zum Beispiel erfordert das Sortieren Kosten von $\Theta(N/B\log_{M/B} N/B)$ und naive Matrixmultiplikation erfordert . $\Theta(n^3/B\sqrt{M})$

Dieses Modell wird verwendet, um "Cache-vergessene Algorithmen" zu analysieren, bei denen oder nicht bekannt sind . Im Allgemeinen besteht das Ziel darin, dass der Cache-vergessene Algorithmus im externen Speichermodell eine optimale Leistung erbringt. Dies ist nicht immer möglich, wie zum Beispiel im Permutationsproblem (gezeigt in Brodal, Faderberg 2003 ). In diesem Artikel von Erik Demaine finden Sie eine weitere Erläuterung der Cache-vergessenen Algorithmen, einschließlich der Erörterung von Sortierung und Matrixmultiplikation. $B$ $M$

Wir können sehen, dass das Ändern von eine logarithmische Beschleunigung für das Sortieren und eine polynomische Beschleunigung für die Matrixmultiplikation verursacht. (Dieses Ergebnis stammt ursprünglich aus Hong, Kung 1981 und geht tatsächlich sowohl der Unwissenheit des Cache als auch der Formalisierung des externen Speichermodells voraus). $M$

Meine Frage lautet:

Gibt es einen Fall, in dem die Beschleunigung in exponentiell ist ? Die Laufzeit wäre so etwas wie $M$ . Ich interessiere mich insbesondere für einen Algorithmus oder eine Datenstruktur, die für den Cache nicht relevant sind und zu dieser Beschreibung passt, würde mich aber über einen Algorithmus / eine Datenstruktur mit Cache-Unterstützung oder sogar eine bekannteste Untergrenze freuen. $f(N,B)/2^{O(M)}$

In den meisten Modellen wird im Allgemeinen angenommen, dass die Wortgröße wenn die Eingangsgröße ist und eindeutig . Dann wird eine Beschleunigung von ergibt ein Polynom Speedup in . Das lässt mich glauben, dass das gesuchte Problem kein Polynom ist. (Andernfalls können wir die Cache-Größe durch eine Konstante ändern, um eine konstante Anzahl von E / As zu erhalten, was unwahrscheinlich erscheint.) $w = \Omega(\log N)$ $N$ $M > w$ $2^M$ $N$

ds.algorithms ds.data-structures cache-oblivious SamM
quelle

kann raten, aber

? ein Fall gegeben , wie Beschleunigungs Ergebnis

, ausreichend?

N =

$N=$

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

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

vzn

Es muss leider in Bezug auf

für meine Zwecke sein. Ich würde mich allerdings für die Referenz interessieren.

M

$M$

SamM

wikipedia auf Cache vergessen Algorithmen . Zu Ihrer Information gibt es eine gewisse Subtilität in dieser Feldnotation. Die Fußnote 7 von Demaine sagt in diesem Bereich,

ist die Problemgröße und manchmal

wobei

die Anzahl der Blöcke ist, "aber die Kleinschreibung scheint in Ungnade gefallen zu sein". Sie verwenden

oben und alternativ

anscheinend beide als Eingabegröße. denke, du solltest deine Frage zumindest standardisieren.

N

$N$

n = N / B

$n = N/B$

n

$n$

n

$n$

N

$N$

Ich habe es aus Konsistenzgründen bearbeitet.

ist die Größe der Eingabe und

wird nur für die Matrixmultiplikation verwendet, da die Laufzeit für dieses Problem im Allgemeinen in Form einer

Matrix definiert ist (dh

)

N

$N$

n

$n$

n \times n

$n\times n$

N = n^{2}

$N = n^2$

SamM

Sehen Sie keine Fälle davon nach dem Scannen der Literatur. vielleicht gibt es keinen solchen ref? Vielleicht ist es angebracht, einen solchen Algorithmus als komplex und daher theoretisch schwer zu analysieren, um eine solche Beschleunigung zu erzielen ...? oder müsste es vielleicht erfunden werden ...? oder vielleicht ist es nicht möglich? Könnte es eine Idee geben, dass zufälliger Zugriff auf den Speicher der schlechteste mögliche Fall ist? scheint in diesem Fall die Geschwindigkeitszunahme in

linear zu sein ...? oder ist vielleicht ein fraktales Muster für den Zugriff auf den Speicher der schlimmste Fall? Diese Linie der Studie ist nur etwas mehr als ein Jahrzehnt alt ....

M

$M$

vzn

Antworten:

Ich bin nicht sicher, ob ich die Frage verstanden habe. Aber es scheint mir , dass unter der Annahme , dass enthält Probleme erfordern exponentieller Zeit, solche Probleme Ihre Anforderungen erfüllen würde, denn wenn ist Sie würde eine exponentielle Anzahl von I / O - Operationen müssen ( da Sie nicht in demselben Speicherblock der Größe mehr als eine polynomielle Anzahl von Schritten "bleiben" können, ohne in einen Zyklus zu gehen) und wenn $PSPACE$ $M$ $O(\log N)$ $O( \log N)$ $M=N$ Sie würden nur eine lineare Anzahl von I / O-Operationen benötigen. Bezüglich Ihrer Beobachtung, dass ein solches Problem nicht zu gehören kann , ist es auch richtig, wenn die Beschleunigung für Werte von gelten muss , die (da dies bedeuten würde, dass wir eine exponentielle Anzahl von Operationen haben). Wenn die Beschleunigung jedoch nur für kleinere Werte von , ist dies meiner Meinung nach intuitiv nicht der Fall, da es meiner Meinung nach möglich sein sollte, ein Problem zu entwerfen, das in der Tat die Verkettung kleinerer Probleme der Größe jeweils Exponentialwerte erfordern Zeit in seiner eigenen Größe und einer exponentiellen Anzahl von E / A - Operationen (d. h. $P$ $M$ $\Omega(N)$ $M$ $O(\log N)$ , da ist exponentiell in $poly (N)$ $poly(N)$ ). In der Praxis glaube ich, dass -vollständige Probleme wie Ihre Bedingung erfüllen. $O(\log N)$ $PSPACE$ $TQBF$

user8477
quelle

Ich fürchte, ich folge einigen Ihrer Argumente nicht. Wenn

, ist jedes Problem im externen Speicher trivial. Wie ich bereits erwähnte, ist

etwas albern, da das bedeutet, dass der Speicher nur eine konstante Anzahl von Wörtern enthält (möglich, aber nicht, wie der externe Speicher allgemein untersucht wird). Ich verstehe, was Sie sagen, dass es einen exponentiellen Gewinn gab, aber das sagt nichts über Zwischenwerte aus. Zum Beispiel ist eine optimale Partition im externen Speicher das Minimum von zwei Begriffen (im Wesentlichen wenn alles in den Speicher passt, machen wir etwas ganz anderes als wenn es nicht passt). Können Sie das ausschließen?

M = Ω (N)

$M= \Omega(N)$

M = O (\log N)

$M = O(\log N)$

SamM

Ich verstehe nicht, warum ein Problem im externen Speicher trivial ist, wenn

. Wenn

und der Algorithmus eine exponentielle Zeit benötigt, müssen Sie möglicherweise eine exponentielle Anzahl von Malen zwischen den beiden Speicherhälften hin und her tauschen.

M = Ω (N)

$M = \Omega(N)$

M = N / 2

$M=N/2$

User8477

Ah, natürlich hast du Recht, dass der konstante Faktor wichtig ist. Das macht sehr viel Sinn; Dies ist sicherlich ein guter Ausgangspunkt.

SamM

Ich habe kein Argument für Zwischenwerte. Auf einer sehr oberflächlichen Ebene denke ich, dass einige Backtracking-Algorithmen eine exponentielle Abhängigkeit von der Speichergröße haben würden, da I / O-Operationen an Knoten mit geringerer Tiefe im Suchbaum erforderlich wären. Diese Abhängigkeit würde für Zwischenwerte gelten. Dies sagt natürlich nichts über die inhärente Komplexität des Problems aus. Auch wenn Sie

, würde das oben angegebene Argument für das Eintauchen in ein Loch (zyklisch) immer noch eine Verstärkung von

wobei

die zeitliche Komplexität des Problems ist.

M = ω (\log N)

$M=\omega(\log N)$

T (N) / 2^{M}

$T(N)/2^M$

T (N)

$T(N)$

User8477

-4

diese frage scheint in terra incognita, also in unerforschtes gebiet zu verfallen . Nach einigem Nachdenken und Überdenken folgen hier einige Gedanken / Ideen zu dieser anscheinend sehr schwierigen / subtilen Frage, die hoffentlich intelligent sein werden, aber nicht endgültig sein sollen.

Demain, den Sie zitieren, schreibt: "Die Grundidee [von Algorithmen, die den Cache nicht kennen] ist einfach: Entwerfen Sie Algorithmen mit externem Speicher, ohne und . Aber diese einfache Idee hat mehrere überraschend starke Konsequenzen." $B$ $M$

es scheint auch überraschend subtile Implikationen zu haben. Es scheint schwierig zu sein, dieses Modell auf extremes Verhalten zu analysieren, und es scheint, dass dies bisher noch niemand getan hat. Es gibt einige Erhebungen, und sie scheinen bisher das gesamte Gebiet zu erfassen. Dies ist nicht verwunderlich, da das Feld nur etwa ein Jahrzehnt alt ist.

Das Modell scheint noch nicht auf Turing-Maschinen übersetzt worden zu sein, bei denen eine genauere / formale / theoretische / allgemeine / Standardanalyse möglich ist. Das gesamte Konzept der Big-Oh-Notation und ihre Implikationen und Intuitionen, wie die Irrelevanz von Konstanten, trägt in diesem Bereich von Algorithmen, die den Cache nicht kennen, nicht unbedingt automatisch mit sich. Zum Beispiel scheint das Modell bereits mit den Konstanten zu arbeiten die die exakten Speichergrößen messen. es scheint, dass das Feld bisher keine grundlegenden Axiome seiner Dynamik hat. $B,M$
TMs wurden 1936 von Turing erfunden, und die Hartmanis-Stearns- Sätze zur Zeit- / Raumhierarchie (auf die Sie in dieser Frage etwas anspielen) wurden 1965 entdeckt. Das sind bemerkenswerte ~ 3 Jahrzehnte, doch die Sätze zur Zeit- / Raumhierarchie werden jetzt etwas berücksichtigt Grundstufe und in Grundschulklassen unterrichtet. Es scheint noch keine entsprechenden Hierarchiesätze in diesem Modell zu geben, und wie man das macht, ist kein triviales Problem. Dieses Modell scheint tatsächlich mehr "bewegliche Teile" zu haben als die Standard-Turing-Maschine (die bereits eine ziemlich teuflisch komplexe Dynamik aufweist), dh wie eine erweiterte Turing-Maschine.
Eine andere Idee ist, dieses externe Speichermodell auf irgendeine Weise in TMs umzuwandeln, was wiederum nicht in der Literatur / Umfragen zu Cache-vergesslichen Algorithmen auftaucht, und vielleicht zu sehen, wie die Hartmanis-Stearns-Hierarchiesätze übersetzt werden könnten. es scheint sich auf ein Zwei-Band-TM zu beziehen, bei dem ein Band die Größe "M" und das andere Band unendlich hat und Blöcke in den Größen "B" zu "M" übertragen werden. Eine Schwierigkeit dabei ist jedoch, dass es sich eher um ein RAM-Modell als um ein Turing-Modell handelt, das sequentiellen Zugriff auf das Band verwendet. Auf der anderen Seite kann dies zu Feinheiten führen, die mit Konvertierungen zwischen Single- und Multitape-TMs verbunden sind .
schlagen vor, dieses Problem empirisch mit Simulationen anzugreifen, auf die sich die Literatur zum Beispiel in dieser großartigen Umfrage von Kumar on Cache (2003) konzentriert. Es sind viele Programme und Artikel für Cache-Simulationen online, und möglicherweise kann Ihre Frage mit einigen Vereinfachungen ohne viel Code beantwortet werden. Eine Grundidee besteht darin, probabilistische Algorithmen zu erstellen, die auf der Grundlage von Wahrscheinlichkeiten auf "nahe" Speicherbereiche zugreifen. "In der Nähe" ist hier nicht notwendigerweise zusammenhängender Speicher, sondern ein Algorithmus, der zufällige Speicherseiten (Blöcke) auswählt, basierend auf dem Verfolgen seiner eigenen zuletzt aufgerufenen Seiten. Schlagen Sie die Verwendung von Potenzgesetzen vorum die Wahrscheinlichkeit zu bestimmen, dass "nahe" Seiten in der Liste "zuletzt aufgerufen" ausgewählt werden. Dies scheint der Hauptaspekt zu sein, mit dem cachebasierte Leistungsverbesserungen zusammenhängen.
Hier ist ein grobes Argument basierend auf 'M', das im Grunde genommen ein Maß für "Kernspeicher" im Vergleich zum Plattenspeicher ist. Für einen Algorithmus würde man erwarten, dass mit zunehmendem Kernspeicher die Geschwindigkeit des Algorithmus nur annähernd [asymptotisch] linear verbessert wird, und das Hinzufügen von "Kernspeicher", um eine superlineare Erhöhung der Geschwindigkeit des Algorithmus zu erzielen, scheint intuitiv fast so, als würde man die Geschwindigkeit überschreiten begrenzen und "etwas für nichts bekommen". Fassen Sie das Modell jedoch nicht gut genug, um dies zu beweisen [aber anscheinend hat es auch niemand anderes, einschließlich der Behörden / Gründer / Experten].
Diese Cache-vergessene Algorithmusliteratur hat sich auf P-Algorithmen konzentriert und hat bisher keine Analyse eines Nicht-P-Algorithmus gesehen, und vielleicht existiert keine. dies könnte möglicherweise daran liegen, dass die analyse zu schwierig ist! In diesem Fall bleiben Fragen zu extremem Verhalten auf lange Sicht unbeantwortet.
Es scheint nicht einmal intuitiv klar oder möglicherweise überhaupt noch untersucht zu sein, wie sich "kleine" Komplexitätsalgorithmen wie in L oder "große" Algorithmen wie Nicht-P (z. B. Expspace usw.) in diesem Modell verhalten. Das Modell misst die Lokalität des Gedächtnisses, die sich grundlegend zu unterscheiden scheint, aber mit Zeit- und Raumhierarchien verflochten ist.
Es gibt eine etwas undurchsichtige Messung der Turing-Maschinenkomplexität, die als "Umkehrkomplexität" bezeichnet wird, mit einigen Studien, Ergebnissen und Arbeiten, die in Zusammenhang stehen könnten. Grundsätzlich kann der TM eine gewisse Zeit und einen gewissen Raum abdecken, aber Umkehrungen sind eine etwas unabhängige Messung des Bandkopfes während der Berechnung. es scheint, dass "hohe Umkehrungen" mit "hoher Speicherlokalität" zusammenhängen könnten, da in beiden Fällen der Bandkopf dazu neigt, in einer "kleineren" Region zu bleiben, anstatt sich in größere Regionen zu bewegen.
Diese Frage und dieses Modell erinnern mich an das Amdahlsche Gesetz und vermuten eine Art noch unentdecktes ähnliches Gesetz im Zusammenhang mit sinkenden Renditen oder Abwägungen, die in diesem Bereich gelten oder gelten könnten. Grobe Überlegung: In der Theorie des Cache-Vergessens-Algorithmus wird ein Gleichgewicht / Kompromiss zwischen einem endlichen "lokalen" Speicher und einer kostenbasierten externen "unendlichen" Festplatte untersucht. Hierbei handelt es sich im Grunde genommen um zwei Ressourcen, die sich "parallel" verhalten und zwischen denen wahrscheinlich ein optimaler Kompromiss besteht.

vzn
quelle

k

$k$

Juho

Das TM-Modell ist das Basismodell von TCS und "Bridge Thms" zwischen seiner Komplexitätshierarchie (Zeit / Raum, grundlegende Komplexitätsklassen wie P / NP usw.), wobei Algorithmen, die den Cache nicht berücksichtigen, offenbar noch zu ermitteln sind. Die externen Speichermodelle und verwandten Cache-Ahnungslosen-Modelle versuchen im Grunde genommen, reale Leistungsmerkmale zu modellieren. Die Literatur ist bisher nicht an größeren theoretischen Abstraktionen interessiert, wie sie von der Frage gestellt werden.

vzn