Game Boy Supercomputer

Mit einer Geschwindigkeit von über 1 Milliarde Bildern pro Sekunde ist dies wohl der schnellste der 8-Bit-Konsolencluster der Welt.


Distributed Tetris (1989)

Wie baue ich einen solchen Computer?

Rezept

Nehmen Sie eine Handvoll Silizium, wenden Sie Verstärkungstraining an, machen Sie Erfahrung mit Supercomputern, einer Leidenschaft für Computerarchitektur, fügen Sie Schweiß und Tränen hinzu, rühren Sie 1000 Stunden lang, bis es kocht - und voila.

Warum sollte jemand einen solchen Computer brauchen?

Kurz gesagt: Auf dem Weg zur Verbesserung der künstlichen Intelligenz.


Eine von 48 IBM Neural Computer-Karten, die für Experimente verwendet wurden

Und hier ist eine detailliertere Version

2016 Jahr. Deep Learning ist allgegenwärtig. Die Bilderkennung kann dank gefalteter neuronaler Netze als gelöste Aufgabe angesehen werden, und meine Forschungsinteressen streben nach neuronalen Netzen mit Gedächtnis und verstärktem Lernen.



Insbesondere in der Arbeit der Autoren von Google Deepmind wurde gezeigt, dass es möglich ist, das Niveau einer Person in verschiedenen Spielen für den Atari 2600 (Heimspielkonsole, veröffentlicht 1977) zu erreichen oder sogar zu übertreffen, indem ein einfacher Lernalgorithmus verwendet wird, der von Deep Q-Neural Network unterstützt wird. Und das alles einfach beim Betrachten des Gameplays. Es erregte meine Aufmerksamkeit.


Eines der Spiele mit dem Atari 2600, Breakout. Die Maschine wurde unter Verwendung eines einfachen Verstärkungslernalgorithmus trainiert. Nach Millionen von Iterationen begann der Computer besser zu spielen als Menschen.

Ich habe angefangen, mit Atari 2600-Spielen zu experimentieren. Breakout ist zwar beeindruckend, kann aber nicht als kompliziert bezeichnet werden. Der Schwierigkeitsgrad kann anhand des Schwierigkeitsgrades in Übereinstimmung mit Ihren Aktionen (Joystick) und Ihren Ergebnissen (Punkten) bestimmt werden. Das Problem tritt auf, wenn der Effekt lange warten muss.


Illustration eines Problems am Beispiel komplexerer Spiele. Links - Ausbruch (ATARI 2600) [Der Autor hat sich geirrt, dies ist ein Pong-Spiel / ca. trans.] mit einer sehr schnellen Antwort und einem schnellen Feedback. Richtig - Mario Land (Nintendo Game Boy) liefert keine sofortigen Informationen über die Auswirkungen der Aktion. Zwischen zwei wichtigen Ereignissen können lange Zeiträume irrelevanter Beobachtungen auftreten.

Um das Lernen effektiver zu gestalten, kann man sich Versuche vorstellen, einen Teil des Wissens aus einfacheren Spielen zu übertragen. Diese Aufgabe bleibt ungelöst und ist ein aktives Forschungsthema. Eine kürzlich veröffentlichte Aufgabe von OpenAI versucht genau das zu messen.

Die Fähigkeit, Wissen zu übertragen, würde nicht nur das Training beschleunigen - ich glaube, dass einige Lernprobleme ohne Grundwissen überhaupt nicht gelöst werden können. Wir brauchen Dateneffizienz. Nehmen Sie das Spiel Prince of Persia:



Es gibt keine offensichtlichen Punkte darin.
Es dauert 60 Minuten, um das Spiel zu beenden.



Ist es möglich, denselben Ansatz anzuwenden, der beim Schreiben der Arbeit am Atari 2600 verwendet wurde? Wie wahrscheinlich ist es, dass Sie durch Drücken von Zufallstasten zum Ende gelangen?

Diese Frage veranlasste mich, einen Beitrag zur Community zu leisten, die darin besteht, dieses Problem zu lösen. Tatsächlich haben wir die Aufgabe von Hühnchen und Eiern - wir brauchen einen besseren Algorithmus, mit dem wir eine Nachricht übertragen können. Dies erfordert jedoch Forschung, und Experimente sind zeitaufwändig, da wir keinen effizienteren Algorithmus haben.


Ein Beispiel für Wissenstransfer: Stellen Sie sich vor, wir haben zuerst gelernt, ein einfaches Spiel wie das linke zu spielen. Dann speichern wir Konzepte wie „Rennen“, „Auto“, „Strecke“, „Gewinnen“ und lernen Farben oder dreidimensionale Modelle. Wir argumentieren, dass gemeinsame Konzepte zwischen Spielen „übertragen“ werden können. Die Ähnlichkeit von Spielen kann durch die Anzahl der zwischen ihnen übertragenen Kenntnisse bestimmt werden. Zum Beispiel werden die Spiele Tetris und F1 nicht ähnlich sein.

Aus diesem Grund habe ich mich für den zweiten idealen Ansatz entschieden, um die anfängliche Verlangsamung zu vermeiden und das System drastisch zu beschleunigen. Meine Ziele waren:
- beschleunigte Umgebung (stellen Sie sich vor, dass Prince of Persia 100-mal schneller abgeschlossen werden kann) und gleichzeitiger Start von 100.000 Spielen.
- eine Umgebung, die besser für die Forschung geeignet ist (wir konzentrieren uns auf Aufgaben, aber nicht auf vorläufige Berechnungen, wir haben Zugang zu verschiedenen Spielen).

Anfangs dachte ich, dass der Leistungsengpass irgendwie von der Komplexität des Emulatorcodes abhängen könnte (zum Beispiel ist die Stella-Codebasis groß und basiert auf C ++ - Abstraktionen - nicht die beste Wahl für Emulatoren).

Konsolen

Insgesamt habe ich auf mehreren Plattformen gearbeitet, angefangen mit einem der ersten Spiele, die jemals erstellt wurden (zusammen mit dem Pong-Spiel) - den Arcade Space Invaders, Atari 2600, NES und Game Boy. Und das alles wurde in C geschrieben.

Ich habe es geschafft, eine maximale Bildrate von 2000-3000 pro Sekunde zu erreichen. Um die Ergebnisse von Experimenten zu erhalten, benötigen wir Millionen oder Milliarden von Frames, daher war die Lücke riesig.


Space Invaders arbeiten im FPGA - Debugging-Modus mit niedriger Geschwindigkeit. Der FPGA-Zähler zeigt die Anzahl der verstrichenen Taktzyklen an.

Und dann dachte ich - was wäre, wenn wir mit Eisen die richtige Umgebung beschleunigen könnten. Zum Beispiel gingen die ursprünglichen Space Invaders mit einer Frequenz von 1 MHz an die 8080-CPU. Ich habe es geschafft, eine 8080 40 MHz CPU auf einem 3 GHz Xeon Prozessor zu emulieren. Nicht schlecht, aber nachdem ich das alles in das FPGA gesteckt hatte, stieg die Frequenz auf 400 MHz. Das bedeutete 24.000 FPS aus einem Stream - das entspricht einem 30-GHz-Xeon! Habe ich erwähnt, dass Sie 100 8080-Prozessoren in ein durchschnittliches FPGA packen können? Dies ergibt bereits 2,4 Millionen FPS.


Space Invaders mit 100 MHz Hardwarebeschleunigung, ein Viertel der vollen Geschwindigkeit


Mehr als hundert Kerne im Xilinx Kintex 7045 FPGA (angezeigt durch helle Farben; der blaue Fleck in der Mitte ist die allgemeine Logik für die Demonstration).


Ungleichmäßiger Ausführungspfad

Sie fragen sich vielleicht, was ist mit der GPU? Kurz gesagt, wir brauchen Parallelität wie MIMD , nicht SIMD . Als Student habe ich einige Zeit an der Implementierung einer Monte-Carlo-Baumsuche auf einer GPU gearbeitet (eine solche Suche wurde in AlphaGo verwendet).

Zu dieser Zeit habe ich unzählige Stunden damit verbracht, die GPU und andere Hardwarekomponenten nach dem SIMD-Prinzip (IBM Cell, Xeon Phi, AVX-CPU) zum Ausführen eines solchen Codes zum Laufen zu bringen, und es wurde nichts daraus. Vor einigen Jahren begann ich zu denken, dass es schön wäre, unabhängig Hardware entwickeln zu können, die speziell für die Lösung von Problemen im Zusammenhang mit dem Verstärkungstraining entwickelt wurde.




MIMD-Parallelität

ATARI 2600, NES oder Game Boy?

Bei 8080 implementierte ich Space Invaders, NES, 2600 und Game Boy. Und hier sind einige Fakten über sie und die Vorteile von jedem von ihnen.


NES Pacman

Space Invaders waren nur ein Aufwärmen. Wir haben es geschafft, sie zum Laufen zu bringen, aber es war nur ein Spiel, daher war das Ergebnis nicht sehr nützlich.

Der Atari 2600 ist tatsächlich der Standard in der Forschung zum verstärkten Lernen. Der MOS 6507-Prozessor ist eine vereinfachte Version des berühmten 6502, sein Design ist eleganter und effizienter als der des 8080. Ich habe mich für 2600 entschieden, nicht nur wegen bestimmter Einschränkungen in Bezug auf Spiele und deren Grafik.

Ich habe auch NES (Nintendo Entertainment System) implementiert, das die CPU mit 2600 teilt. Es gibt Spiele, die viel besser als 2600 sind. Beide Konsolen leiden jedoch unter einer übermäßig komplexen Grafikverarbeitungspipeline und mehreren Kassettenformaten, die unterstützt werden müssen.

In der Zwischenzeit habe ich den Nintendo Game Boy wiederentdeckt. Und das war es, wonach ich gesucht habe.

Warum ist der Game Boy so cool?

1049 klassische Spiele und 576 Spiele für Game Boy Color

Insgesamt mehr als 1000 Spiele, eine sehr große Vielfalt, hohe Qualität, einige davon sind recht komplex (Prince), Spiele können gruppiert und komplexiert werden, um den Wissenstransfer und das Training zu erforschen (zum Beispiel gibt es Optionen für Tetris, Rennspiele, Mario). Um das Spiel Prince of Persia zu lösen, müssen Sie möglicherweise Wissen aus einem anderen ähnlichen Spiel übertragen, in dem Punkte klar angegeben sind (in Prince ist dies nicht der Fall).


Nintendo Game Boy ist meine Lieblingsforschungsplattform für Wissenstransfer. In der Grafik habe ich versucht, die Spiele nach Komplexität (subjektiv) und Ähnlichkeit zu gruppieren (Konzepte wie Rennen, Springen, Schießen, verschiedene Spiele wie Tetris; hat jemand HATRIS gespielt?).

Der klassische Game Boy verfügt über einen sehr einfachen Bildschirm (160 x 144, 2-Bit-Farbe), sodass die Vorverarbeitung einfach wird und Sie sich auf wichtige Dinge konzentrieren können. Bei 2600 haben sogar einfache Spiele viele Farben. Darüber hinaus werden Objekte in Game Boy viel besser dargestellt, ohne zu blinken und ohne dass maximal zwei aufeinanderfolgende Frames benötigt werden.



Kein verrücktes Speicherlayout wie NES oder 2600. Die meisten Spiele können mit 2-3 Mappern verwendet werden.

Kompakter Code - Ich habe es geschafft, den gesamten Emulator in C in nicht mehr als 700 Codezeilen einzupassen, und meine Verilog-Implementierung passt in 500 Zeilen.

Es gibt dieselbe einfache Version von Space Invaders wie in der Spielhalle.



Und hier ist er, mein 1989er Dot-Matrix-Game Boy und die FPGA-Version, die über HDMI auf einem 4K-Bildschirm funktioniert.



Und hier ist, was mein alter Game Boy nicht kann:


Tetris beschleunigt mit Eisen - Aufnahme vom Bildschirm in Echtzeit, die Geschwindigkeit beträgt 1/4 des Maximums.

Gibt es einen wirklichen Vorteil dafür?

Ja, gibt es. Bisher habe ich das System unter einfachen Bedingungen mit einem externen Netzwerk von Regeln getestet, die mit einzelnen Game Boys interagieren. Insbesondere habe ich den A3C-Algorithmus (Advantage Actor Critic) verwendet und möchte ihn in einem separaten Beitrag beschreiben. Mein Kollege hat es über FPGA mit dem Faltungsnetzwerk verbunden, und es funktioniert.


Wie FGPA mit einem neuronalen Netzwerk kommuniziert


Verteiltes A3C


Mario Land: Ausgangszustand. Ein zufälliger Tastendruck bringt uns nicht weit. Die obere rechte Ecke zeigt die verbleibende Zeit. Wenn wir Glück haben, beenden wir das Spiel schnell, nachdem wir die Gumba berührt haben. Wenn nicht, dauert es 400 Sekunden, um zu „verlieren“.


Mario Land: Nach einer Stunde Spiel lernte Mario laufen, springen und öffnete sogar einen geheimen Raum, der in eine Pfeife krabbelte.


Pac Man: Nach ungefähr einer Stunde Training konnte das neuronale Netzwerk das ganze Spiel sogar einmal beenden (indem es alle Punkte verzehrte).

Fazit

Ich würde gerne glauben, dass das nächste Jahrzehnt die Zeit sein wird, in der Supercomputing und KI sich finden. Ich hätte gerne Hardware, mit der ich mich auf ein bestimmtes Niveau einstellen kann, um mich an den gewünschten AI-Algorithmus anzupassen.


Nächstes Jahrzehnt

Code für Game Boy in C.

Debuggen

Die Leute fragen mich oft: Was war am schwierigsten? Das war's - das ganze Projekt war ziemlich schmerzhaft. Für den Anfang gibt es keine Spezifikation für einen Game Boy. Alles, was wir gelernt haben, haben wir dank Reverse Engineering erhalten, dh wir haben eine Zwischenaufgabe wie ein Spiel gestartet und beobachtet, wie es ausgeführt wird. Dies unterscheidet sich stark vom Standard-Software-Debugging, da hier die Hardware debuggt, auf der die Programme ausgeführt werden. Ich musste mir verschiedene Wege einfallen lassen, um dies zu erreichen. Und ich habe darüber gesprochen, wie schwierig es ist, einen Prozess zu überwachen, wenn er mit einer Frequenz von 100 MHz läuft. Oh, und da ist kein Druck.


Ein Ansatz zur Implementierung einer CPU besteht darin, Anweisungen zu ihren Funktionen zu gruppieren. Mit 6502 ist es viel einfacher. LR35092 hat viel von allem „zufälligen“ Unsinn vollgestopft und es gibt viele Ausnahmen. Ich habe diese Tabelle bei der Arbeit mit dem CPU Game Boy verwendet. Ich habe eine gierige Strategie angewendet - ich habe die größte Anweisung genommen, sie implementiert, gelöscht und dann wiederholt. 1/4 der Anweisungen ist ALU, 1/4 ist das Laden von Registern, was ziemlich schnell implementiert werden kann. Auf der anderen Seite des Spektrums gibt es alle möglichen Dinge, wie zum Beispiel „Upload von HL nach SP mit einem Vorzeichen“, die separat verarbeitet werden mussten.


Debugging: Führen Sie den Code auf der Hardware aus, die Sie debuggen, schreiben Sie ein Protokoll Ihrer Implementierung und zusätzliche Informationen (hier wird ein Vergleich des Verilog-Codes links mit meinem C-Emulator rechts angezeigt). Führen Sie dann diff für die Protokolle aus, um Inkonsistenzen zu finden (blau). Einer der Gründe für die Verwendung der Automatisierung ist, dass ich in vielen Fällen nach Millionen von Ausführungszyklen Probleme fand, als ein einzelnes CPU-Flag einen Schneeballeffekt verursachte. Ich habe verschiedene Ansätze ausprobiert, und dieser erwies sich als der effektivste.


Sie brauchen viel Kaffee!


Diese Bücher sind 40 Jahre alt. Es war erstaunlich, sie zu durchsuchen und die Welt der Computer mit den Augen dieser Benutzer zu betrachten - ich fühlte mich wie ein Gast aus der Zukunft.

OpenAI-Forschungsanfrage

Zuerst wollte ich mit Spielen in Bezug auf das Gedächtnis arbeiten, wie in einem Beitrag von OpenAI beschrieben.

Überraschenderweise war es unerwartet schwierig, Q-Learning für Eingaben, die Speicherzustände darstellen, zum Laufen zu bringen.

Dieses Projekt hat möglicherweise keine Lösung. Es wäre unerwartet herauszufinden, dass Q-Learning in Atari niemals erfolgreich mit dem Gedächtnis arbeiten wird, aber es besteht die Möglichkeit, dass diese Aufgabe ziemlich schwierig wird.

Angesichts der Tatsache, dass die Spiele auf Atari nur 128 b Speicher verwendeten, schien es sehr attraktiv, diese 128 b anstelle von Vollbildrahmen zu verarbeiten. Ich habe gemischte Ergebnisse erzielt und angefangen, es herauszufinden.

Und obwohl ich nicht beweisen kann, dass es unmöglich ist, aus dem Gedächtnis zu lernen, kann ich zeigen, dass die Annahme, dass das Gedächtnis den vollen Zustand des Spiels widerspiegelt, falsch ist. Die Atari 2600-CPU (6507) verwendet 128 b Speicher, hat jedoch weiterhin Zugriff auf zusätzliche Register, die sich auf einem separaten Schaltkreis befinden (TIA, Adapter für ein Fernsehgerät, so etwas wie eine GPU). Diese Register werden zum Speichern und Verarbeiten von Informationen über Objekte (Schläger, Rakete, Ball, Kollision) verwendet. Mit anderen Worten, sie sind nicht zugänglich, wenn wir nur die Erinnerung betrachten. NES und Game Boy verfügen außerdem über zusätzliche Register, mit denen Sie den Bildschirm steuern und scrollen können. Nur ein Speicher gibt nicht den vollständigen Status des Spiels wieder.

Nur der 8080 speichert Daten direkt im Videospeicher, sodass Sie den vollständigen Status des Spiels extrahieren können. In anderen Fällen sind die "GPU" -Register außerhalb des RAM zwischen der CPU und dem Bildschirmpuffer verbunden.



Eine interessante Tatsache: Wenn Sie die Geschichte der GPU untersuchen, ist der 8080 möglicherweise der erste „Grafikbeschleuniger“ - er verfügt über ein externes Schieberegister, mit dem Sie Space Invaders mit einem einzigen Befehl verschieben können, wodurch die CPU entlastet wird.




Eof