Welches Rechenmodell ist „das Beste“?

41

1937 beschrieb Turing eine Turingmaschine. Seitdem wurden viele Berechnungsmodelle beschrieben, um ein Modell zu finden, das einem echten Computer ähnelt, aber dennoch einfach genug ist, um Algorithmen zu entwerfen und zu analysieren.

Als Ergebnis haben wir Dutzende von Algorithmen für z. B. das SORT-Problem für verschiedene Rechenmodelle. Leider können wir nicht einmal sicher sein, dass eine Implementierung eines Algorithmus mit der Laufzeit O (n) in einem Wort-RAM mit zulässigen Bitvektoroperationen schneller abläuft als eine Implementierung eines Algorithmus mit der Laufzeit O (n⋅logn) in ein Wort RAM (ich spreche natürlich nur von "guten" Implementierungen).

Ich möchte also verstehen, welches der vorhandenen Modelle "das Beste" für die Entwicklung von Algorithmen ist, und ich suche nach einer aktuellen und detaillierten Übersicht über Rechenmodelle, die Vor- und Nachteile von Modellen und deren Realitätsnähe aufzeigt.

Tatiana Starikovskaya
quelle
1
Cross-posted auf MathOverflow ( mathoverflow.net/questions/44558/… ), obwohl hier umgeleitet.
Dave Clarke
@Tatiana, Gute Frage, Was meinst du mit "der Beste"? Meinen Sie ein Modell mit theoretischer Laufzeit, die in der Nähe der "realen" Laufzeit liegt?
Mohammad Al-Turkistany
8
Wenn Sie "echte" Laufzeiten genau modellieren möchten, scheint es wichtig zu sein, Caches genau zu modellieren. Insbesondere verfügt modernes Computing über viele Cache-Ebenen (CPU, RAM, Festplatte usw.), wobei einige Ebenen um Größenordnungen langsamer sind als andere. Es ist nicht ausgeschlossen, dass die "echte" Laufzeit eines Algorithmus durch die Anzahl der Cache-Fehlschläge bestimmt wird. Anekdotisch habe ich gehört, dass ein Grund dafür, dass Barrieremethoden in der linearen Programmierung trotz ihrer schlechten theoretischen Garantien so gut funktionieren, darin besteht, dass sie oftmals ziemlich Cache-effizient sind.
mhum
4
Soweit ich das beurteilen kann, ergeben sich die größten Abweichungen zwischen den prognostizierten Laufzeiten im Wort RAM-Modell und den tatsächlichen Laufzeiten im Allgemeinen aufgrund des Datenabrufs ... die falschen Variablen befinden sich im Cache-Speicher und der Abruf verlangsamt sich aus diesem Grund enorm nach unten. Es gab eine Reihe von Versuchen, dies mit einem theoretischen hierarchischen Speichermodell zu modellieren, und ich glaube nicht, dass einer dieser Versuche sehr erfolgreich war, da die Modelle am Ende zu kompliziert sind, um leicht damit zu arbeiten.
Peter Shor
2
Wenn Sie einen Algorithmus haben, von dem Sie glauben, dass er in der Praxis nützlich ist, und Sie möchten, dass er tatsächlich verwendet wird, können Sie dies am besten sicherstellen, indem Sie ihn implementieren oder ihn von einer anderen Person implementieren lassen (auch wenn er kein guter Algorithmus ist) genug Implementierung, um in die praktische Software integriert zu werden). Eine Fallstudie hierzu finden Sie in der Historie des LZW-Datenkomprimierungsalgorithmus. Tatsächlich macht es wahrscheinlich keinen Sinn, herauszufinden, wie sich das Zwischenspeichern auf den Algorithmus auswirkt, es sei denn, es ist eines, an dessen Implementierung die Leute interessiert sind. Andernfalls wird niemand auf Ihre Ergebnisse achten.
Peter Shor

Antworten:

30

Ich habe das Standard-Word-RAM-Modell immer als "das Beste" in Ihrem Sinne angesehen. Jeder, der gelernt hat, in einer Sprache wie C zu programmieren (oder lose Entsprechungen wie Java usw.), denkt genau an dieses Modell, wenn er an einen Computer denkt.

Natürlich benötigen Sie manchmal Verallgemeinerungen, abhängig von den Regimen, in denen Sie arbeiten. Das externe Speichermodell ist ein wichtiger Aspekt, den Sie berücksichtigen sollten. Dies gilt nicht nur für die Arbeit mit Datenträgern, sondern auch für das Verständnis des Cache (das Sie dazu zwingt, sich um ihn zu kümmern). Eine zu ernsthafte Behandlung kann natürlich auch zu unsinnigen Ergebnissen führen, da das reine externe Speichermodell keine Berechnung berücksichtigt. Eine andere Verallgemeinerung des Wort-RAM ist die Parallelität, aber da sind wir im Moment alle ein bisschen verwirrt :)

Ein Algorithmus mit einer Laufzeit von wird sicherlich schneller ausgeführt als einer mit einer Laufzeit von . Es ist eine mathematische Tatsache, dass die erstere für große schneller ist :) Ihre Problemgröße ist möglicherweise einfach nicht groß genug, damit dies eine Rolle spielt. Da Sie die Sortierung ansprechen, kann ich Ihnen versichern, dass es sehr schwierig sein wird, die Radix-Sortierung mit einem vergleichsbasierten Algorithmus für vernünftiges zu übertreffen .O ( n lg n ) n nO(n)O(nlgn)nn

Eine abschließende Bemerkung zu Algorithmen und "Realität": Denken Sie immer daran, was Sie erreichen wollen. Wenn wir mit Algorithmen arbeiten, versuchen wir, die schwierigsten Probleme zu lösen (z. B. SAT mit 50 Variablen oder Sortieren von Milliarden Zahlen). Wenn Sie versuchen, 200 Zahlen zu sortieren oder SAT nach 20 Variablen zu lösen, benötigen Sie keinen ausgefallenen Algorithmus. Deshalb sind die meisten Algorithmen in der Realität trivial. Das sagt nichts Schlechtes über algorithmische Forschung aus - wir interessieren uns zufällig für dieses ungewöhnliche 1/1000 der wirklichen Probleme, die zufällig schwierig sind ...

Mihai
quelle
Vielen Dank für Ihre Antwort. Ich möchte verstehen, welche Verallgemeinerungen es wert sind, dem Wort RAM hinzugefügt zu werden. Können wir ein Modell beschreiben, das all diese Tricks wie Bitvektoroperationen, Parallelität, Caches enthält und dennoch einfach ist?
Tatiana Starikovskaya
10

Es gibt kein völlig zufriedenstellendes Rechenmodell, mit dem sich Algorithmen traurigerweise analysieren lassen, selbst wenn man es für eine traditionelle Umgebung hält. Dies setzt voraus, dass alle Daten leicht zugänglich sind und der Arbeitsraum praktisch unbegrenzt ist.

Die Multi-Tape-Turing-Maschine ist sicherlich theoretisch gut spezifiziert und viele Algorithmen wurden im Laufe der Jahre in diesem Modell entworfen und analysiert. Für manche ist es jedoch nicht eng genug, wie echte Computer funktionieren, um ein wirklich gutes Modell für das 21. Jahrhundert zu sein. Andererseits ist das Wort-RAM-Modell populär geworden und scheint die Arbeitsweise moderner Computer genauer zu erfassen (Operationen an Wörtern, nicht Bits, ständiger zeitlicher Zugriff auf Speicherstellen). Es gibt jedoch Aspekte, die nicht ideal sind. Zum Beispiel gibt es kein Ein-Wort-RAM-Modell. Zunächst muss festgelegt werden, welche Operationen an Wörtern in konstanter Zeit zulässig sein sollen. Hierfür gibt es viele Möglichkeiten, ohne dass eine einzige Antwort akzeptiert wird. Zweite, Die Wortgröße w wird normalerweise so eingestellt, dass sie mit der Eingabegröße wächst (dh mindestens so schnell wie log (n)), damit jedes Element im Speicher mit einer konstanten Anzahl von Wörtern adressiert werden kann. Dies bedeutet, dass man sich eine unendliche Klasse von Maschinen vorstellen muss, auf denen Ihr Algorithmus ausgeführt wird, oder noch schlimmer, dass sich die Maschine ändert, wenn Sie mehr Daten einspeisen. Dies ist zumindest für meine Schüler ein beunruhigender Gedanke. Schließlich erhalten Sie mit dem Wort-RAM-Modell etwas überraschende Komplexitätsergebnisse, die möglicherweise nicht mit denen übereinstimmen, die man als Student lernt. Beispielsweise ist die Multiplikation von zwei n-Bit-Zahlen in diesem Modell O (n) -Zeit, und das einfache Einlesen einer n-Bit-Zeichenfolge ist plötzlich eine sublineare Zeitoperation. Dies bedeutet, dass man sich eine unendliche Klasse von Maschinen vorstellen muss, auf denen Ihr Algorithmus ausgeführt wird, oder noch schlimmer, dass sich die Maschine ändert, wenn Sie mehr Daten einspeisen. Dies ist zumindest für meine Schüler ein beunruhigender Gedanke. Schließlich erhalten Sie mit dem Wort-RAM-Modell etwas überraschende Komplexitätsergebnisse, die möglicherweise nicht mit denen übereinstimmen, die man als Student lernt. Beispielsweise ist die Multiplikation von zwei n-Bit-Zahlen in diesem Modell O (n) -Zeit, und das einfache Einlesen einer n-Bit-Zeichenfolge ist plötzlich eine sublineare Zeitoperation. Dies bedeutet, dass man sich eine unendliche Klasse von Maschinen vorstellen muss, auf denen Ihr Algorithmus ausgeführt wird, oder noch schlimmer, dass sich die Maschine ändert, wenn Sie mehr Daten einspeisen. Dies ist zumindest für meine Schüler ein beunruhigender Gedanke. Schließlich erhalten Sie mit dem Wort-RAM-Modell etwas überraschende Komplexitätsergebnisse, die möglicherweise nicht mit denen übereinstimmen, die Sie als Schüler lernen. Beispielsweise ist die Multiplikation von zwei n-Bit-Zahlen in diesem Modell O (n) -Zeit, und das einfache Einlesen einer n-Bit-Zeichenfolge ist plötzlich eine sublineare Zeitoperation.

Abgesehen davon, wenn Sie nur wissen möchten, ob Ihr Algorithmus wahrscheinlich schnell abläuft, ist dies höchstwahrscheinlich der Fall :-)

Raphael
quelle
2
Ich denke, wenn Sie bitweise oder wortweise arithmetische Operationen vermeiden, um das Problem "Maschine wächst mit der Eingabegröße" zu vermeiden, aber dennoch einen kostengünstigen RAM oder eine Zeigermaschine verwenden, dann täuschen Sie sich nur: Diese anderen Modelle haben das gleiche Problem. Wie indizieren sie ihre Eingaben? Die Antwort lautet: Auf echten Computern ist nicht genügend Arbeitsspeicher verfügbar, es ist jedoch immer noch praktischer, Algorithmen für sie zu entwerfen, wenn sie davon ausgehen, dass sie ein RAM sind (oder besser ein Modell verwenden, das die Kosten der Speicherhierarchie berücksichtigt), als wenn sie davon ausgehen, dass sie einen Arbeitsspeicher haben ein DFA.
David Eppstein
4
Ein von Knuth beschriebenes RAM-Modell kostet zum Beispiel w Zeit, um eine Adresse mit w Bits zu suchen, und in ähnlicher Weise w Zeit, um zwei w Bit-Zahlen zu addieren (auf diese Weise erhält er Theta (n log n) für die Zeit, um zwei n zu multiplizieren -Bit-Zahlen in einem RAM-Modell ohne konstante Zeitoperationen für Wörter). Es ist interessant, wie sich die am weitesten verbreiteten Modelle in den letzten 20 Jahren verändert haben und wie viele Modelle überhaupt nicht mehr diskutiert werden.
Raphael
8

Models sind nur Models. Ich würde es nicht zu weit treiben; Sie erzählen etwas über einige Aspekte Ihrer Algorithmen, aber nicht die ganze Wahrheit.

Ich würde vorschlagen, dass Sie einfach das Standardwort-RAM-Modell für Ihre Analyse verwenden und den Algorithmus implementieren und sehen, wie gut er in der Praxis funktioniert.

(Eigentlich sagt Ihnen nur die Implementierung Ihres Algorithmus, ohne ihn jemals auszuführen, viel darüber aus ... Zum einen ist er dann nachweislich implementierbar.)

Jukka Suomela
quelle
3
Nun, ich habe zwei Einwände. Erstens implementieren nicht so viele Theoretiker Algorithmen, und dennoch müssen wir sie irgendwie vergleichen. Zweitens möchte ich verstehen, welche Funktionen eines Computers einem Modell hinzugefügt werden können, ohne dass es an Einfachheit verliert.
Tatiana Starikovskaya
11
Die von David Johnson vorgeschlagene Lösung hierfür ist, dass mehr Leute Algorithmen implementieren. Er startete ALENEX und die DIMACS Challenges, um dies zu beheben. Ich habe auch Erfahrung damit. Mit Ken Clarkson entwickelte ich einen randomisierten konvexen Rumpfalgorithmus, von dem wir dachten, dass er in der Praxis gut funktionieren würde. Clarkson ließ es von einem Sommerstudenten bei Bell Labs umsetzen. Basierend auf dem Versprechen dieser Implementierung wurden die Ideen in das qhull-Programm (geschrieben am Geometry Center) eingearbeitet, aber mit einigen heuristischen Beschleunigungen, was bedeutet, dass der Algorithmus keine theoretische Garantie mehr hat, dass er schnell läuft.
Peter Shor
5

Wenn es bei Ihrer Rechenaufgabe mehr um das Verschieben von Daten als um das Durchführen von (arithmetischen) Operationen geht (die Datenmengen sind riesig, sodass sie nicht einmal in den Hauptspeicher passen), dann das I / O-Modell (1988 von Aggarwal und Vitter eingeführt ). kann sehr genau sein. Für Aufgaben wie das Permutieren einer großen Anzahl von Elementen im Hauptspeicher kann es hilfreich sein, die Algorithmen zu verwenden, die I / O-optimal sind (in einer sorgfältigen Implementierung).

Für moderne Mehrkerncomputer kann die von Arge, Goodrich, Nelson und Sitchinava im Jahr 2008 eingeführte parallele Variante ein genaues Modell sein.

Riko Jacob
quelle
5

Wenn Sie "das beste" Rechenmodell meinen, um Ihr Leben komplizierter zu machen, können Sie Wolframs Universal-Turing-Maschine mit 2 Zuständen und 3 Symbolen verwenden.

PROS : keine außer dem Gefühl, die feine Linie zwischen Vernunft und Verrücktheit zu gehen;

Nachteile : Tonnen ...

:-D (nur ein Witz, ich stimme im Grunde mit den vorherigen Antworten überein ...)

Marzio De Biasi
quelle
1

Eine theoretischere Anmerkung: Der Artikel Ultimative theoretische Modelle von Nanocomputern argumentiert, dass das reversible 3D-Netzmodell das optimale physikalische Rechenmodell ist, in dem Sinne, dass kein anderes physikalisches Modell asymptotisch schneller sein könnte. Physikalische Überlegungen wie die Lichtgeschwindigkeit, das Landauer-Prinzip und die Bekenstein-Grenze werden diskutiert.

Um aus dem Abstract zu zitieren:

Wir stellen fest, dass eine reversible Maschine, die nur einige hundert Schichten von Schaltkreisen enthält, mit der aktuellen Technologie eine bessere Leistung erzielen kann als jede andere Maschine, und dass ein auf Nanotechnologie basierender reversibler Computer nur wenige Mikrometer groß sein muss, um eine mögliche irreversible Technologie zu übertreffen.

Wir argumentieren, dass eine Siliziumimplementierung des reversiblen 3D-Netzes heute wertvoll sein könnte, um bestimmte wissenschaftliche und technische Berechnungen zu beschleunigen, und schlagen vor, dass das Modell ein Schwerpunkt zukünftiger Studien in der Theorie paralleler Algorithmen für eine Vielzahl von Problemen werden sollte.

user76284
quelle