Sind die heutigen massiven Parallelverarbeitungseinheiten in der Lage, zellulare Automaten effizient zu betreiben?

Ich frage mich, ob die massiv parallelen Recheneinheiten, die heutzutage in Grafikkarten zur Verfügung stehen (eine , die zum Beispiel in OpenCL programmierbar ist ), gut genug sind, um 1D-Zellularautomaten (oder vielleicht 2D-Zellularautomaten?) Effizient zu simulieren.

Wenn wir ein endliches Gitter wählen, das in den Speicher des Chips passt, können wir dann erwarten, dass ein Übergang eines auf diesem Gitter definierten zellularen Automaten in (quasi) konstanter Zeit berechnet wird?

Ich gehe davon aus, dass 2D-Zellularautomaten mehr Bandbreite für die Kommunikation zwischen den verschiedenen Teilen der Chips benötigen als 1D-Automaten.

Dieselbe Frage würde mich auch im Fall von FPGA-Programmierung oder kundenspezifischen Chips interessieren.

Hervorragende Frage. Ich glaube die Antwort ist ja.

Die Entwicklung eines zellularen Automaten entspricht im Wesentlichen der Durchführung einer Schablonenberechnung. Auf einigen 1D-, 2D- oder 3D-Gittern werden aufeinanderfolgende Werte von Punkten (oder Zellen) basierend auf dem letzten Wert der Nachbarschaft des Punkts berechnet. In einer einfachen 1D-Zertifizierungsstelle kann diese Nachbarschaft die Zelle und die beiden Zellen links und rechts sein. Es gibt viele Beispiele für Schablonenberechnungen, die mit GPUs durchgeführt werden. Die SHOC-Benchmark-Suite von ORNL für OpenCL / CUDA enthält beispielsweise ein 2D-Schablonenbeispiel.

Die Grundidee ist, dass jeder Thread eine lokale Kopie der Nachbarschaft für mehrere Punkte abruft und dann die nächsten Werte für Punkte berechnet, die von dieser Nachbarschaft bestimmt werden. Durch geeignete Verwendung der Speicherhierarchie in z. B. CUDA (Register, gemeinsam genutzte, konstante, Textur- und globale Speicher) und des SIMT-Verarbeitungsmodells (z. B. durch geeignete Berechnung der Übergangsfunktion ohne Einführung einer übermäßigen Warp-Divergenz) kann eine gute Leistung erzielt werden.

Diese Antwort wäre viel besser, wenn ich ein Beispiel geben würde, aber ich bin zu beschäftigt, um gerade Code zu schreiben ... Aber theoretisch sollte es machbar sein, CAs auf GPUs effizient zu simulieren, indem man sie nach der Schablone modelliert Berechnungen. Viele Überlegungen fließen jedoch in die Erstellung einer guten Schablonenberechnung für GPUs ein.

Was auch immer Sie tun, die Berechnung des nächsten Zustands für einen zellularen Automaten erfordert so viele Berechnungen, wie Zellen im Automaten vorhanden sind. Um eine konstante Zeit zu erhalten, benötigen Sie also so viele Rechenkerne, wie Zellen vorhanden sind.

Die Anzahl dieser in der GPU sind derzeit höchstens einige Tausend, während die Berechnung des nächsten Zustands so einfach ist, dass ich erwarte, dass das Ergebnis IO-gebunden ist, dh Sie können eine sehr gute Annäherung an die benötigte Zeit erhalten, indem Sie nur die berücksichtigen Datenverschiebung erforderlich (und wenn es keine gute Annäherung ist, hat entweder die Implementierung eine Ineffizienz oder die Architektur ist nicht geeignet, aber das wäre sehr überraschend).

Für FPGA ist die Frage schwieriger und hängt wahrscheinlich von der Mischung der verfügbaren Speicher- und Recheneinheiten ab. Wenn ich nicht zu weit weg bin, haben Sie nicht genug Speicher, um alle Einheiten beschäftigt zu halten, und wenn Sie sich auf externen Speicher verlassen, befinden Sie sich am selben Platz wie die GPU. Die Speicherbandbreite ist der begrenzende Faktor, und ich würde nicht Seien Sie überrascht, wenn die Schlussfolgerung lautet, dass es keinen Vorteil gegenüber der GPU gibt. (Beachten Sie, dass es, obwohl ich vor Jahren mit FPGA gearbeitet habe, jetzt möglicherweise FPGA-Modelle mit einer richtigen Mischung gibt.)

ASIC bietet mehr Flexibilität. Sie können leicht eine Implementierung haben, die systolisch ist (bei einem bidirektionalen Datenfluss ist jedoch ein Teil der systolischen Daten normalerweise auf einen unidirektionalen Datenfluss beschränkt). Jede physische Zelle ist eine logische Zelle: ein Speicherbit und die für die Berechnung des nächsten Zustands erforderliche Logik damit es ein physischer Nachbar ist, ist es ein logischer. Sie befinden sich offensichtlich in einem konstanten Zeitbereich. Je nachdem, über welche harten Makros Sie verfügen, ist es möglicherweise besser, ein bisschen weniger offensichtlich zu sein und physische Zellen zu haben, die mehrere logische umgruppieren. Das Ziel ist es, das zu maximieren, was in einem Chip getan wird, mit anderen Worten, die Kommunikation mit der Außenseite des Chips zu minimieren, sobald Ihre Kommunikationsanforderungen proportional zur Anzahl der Zellen sind, ist die Bandbreite begrenzt. Ja, das heißt, wenn Sie für jeden Schritt alle Zellen anzeigen müssen, Sie sind wahrscheinlich nicht viel besser als mit GPU. (Full Custom würde nur eine bessere Integration ermöglichen, dh mehr Zellen pro Chip).

Zusammenfassung: - Wenn Sie alle Zwischenzustände betrachten möchten, ist die GPU der effektivste Ansatz. - Wenn Sie dies nicht tun, benötigen Sie das Volumen, um einen ASIC zu rechtfertigen, damit er etwas Besseres bietet. Wenn dies der Fall ist, bietet der FPGA wahrscheinlich nicht genügend Vorteile irgendwelche haben.

Ich frage mich, ob die massiv parallelen Recheneinheiten in Grafikkarten heutzutage gut genug sind, um 1D-Zellularautomaten (oder vielleicht 2D-Zellularautomaten?) Effizient zu simulieren.

Im Allgemeinen ist GPU-Computing die beste Alternative für Standardhardware, die für jedermann verfügbar ist.

Ausführlicher; Nach dem PRAM-Modell sind die Kosten pro Zeitschritt theoretisch in der Tat , das wissen Sie bereits. Die GPU unterscheidet sich jedoch ein wenig von PRAM, da der Speicherzugriff mehr kostet und in verschiedene Hierarchien unterteilt ist (für eine genauere theoretische Analyse sollte man das PMH-Modell berücksichtigen). Darüber hinaus funktionieren Threads in Gruppen oder Warps . Dies sind Lockstep-Berechnungen, die auf SIMD-Weise durchgeführt werden. Das Programmiermodell der GPU arbeitet mit dem Konzept von Grid (CUDA) oder Workspacen ≤ P n P O ( 1 $O(1)$(OpenCL), die praktisch eine 1-zu-1-Abbildung auf den Rechenraum der zellularen Automaten ist. Dies ist das Schlüsselmerkmal, um zu erkennen und zu erkennen, dass GPUs CA-freundlich sind. Technische Details: Wenn die Warp-Divergenz korrekt behandelt wird (wobei if-else-Bedingungen durch geschlossene mathematische Ausdrücke ersetzt werden), werden Speicherzugriffe zusammengefasst und ( Zellen und Prozessoren), dann könnte man sagen, dass die rechnerische Komplexität ist eine Art .$n \le P$$n$$P$$O(1)$

Auf der FPGA- und ASIC-Seite weiß ich, dass es Forschungen zum Aufbau einer physischen Zertifizierungsstelle als Gitter von Logikgattern mit Zuständen gibt, die alle durch ihre Nachbarn verbunden sind. dh systolische Arrays . Die Idee wäre, keinen globalen Speicher mehr zu verwenden, sondern sich auf die Zustände der einzelnen Knoten im Grid zu verlassen. Eine Maschine dieses Typs wäre revolutionär, da wir nicht mehr über einen Computer sprechen könnten, der eine Zertifizierungsstelle simuliert, sondern über eine Zertifizierungsstelle, die als Computer ausgeführt wird (einige Zertifizierungsstellen sind derzeit vollständig).