Game Boy Supercomputer

À des vitesses de plus d'un milliard d'images par seconde, c'est sans doute le plus rapide des clusters de consoles 8 bits au monde.


Distribué Tetris (1989)

Comment construire un tel ordinateur?

Recette

Prenez une poignée de silicium, appliquez une formation renforcée, une expérience avec les superordinateurs, une passion pour l'architecture informatique, ajoutez de la sueur et des larmes, remuez 1000 heures jusqu'à ébullition - et le tour est joué.

Pourquoi aurait-on besoin d'un tel ordinateur?

En bref: évoluer vers l'amélioration de l'intelligence artificielle.


L'une des 48 cartes IBM Neural Computer utilisées pour les expériences

Et voici une version plus détaillée

2016 année. L'apprentissage en profondeur est omniprésent. La reconnaissance d'images peut être considérée comme une tâche résolue grâce aux réseaux de neurones convolutifs, et mes intérêts de recherche sont à la recherche de réseaux de neurones avec mémoire et apprentissage renforcé.



Plus précisément, dans le travail d'auteur de Google Deepmind, il a été montré qu'il est possible d'atteindre le niveau d'une personne ou même de le dépasser dans divers jeux pour l'Atari 2600 (console de jeu à domicile, publiée en 1977), en utilisant un algorithme d'apprentissage simple pris en charge par Deep Q-Neural Network. Et tout cela se produit simplement lors de la visualisation du gameplay. Cela a attiré mon attention.


L'un des jeux avec l'Atari 2600, Breakout. La machine a été formée à l'aide d'un algorithme d'apprentissage par renforcement simple. Après des millions d'itérations, l'ordinateur a commencé à jouer mieux que les humains.

J'ai commencé à expérimenter avec les jeux Atari 2600. Breakout, bien qu'impressionnant, ne peut pas être qualifié de compliqué. La difficulté peut être déterminée par le degré de difficulté en fonction de vos actions (joystick) et de vos résultats (points). Le problème apparaît lorsque l'effet doit attendre longtemps.


Illustration d'un problème utilisant des jeux plus complexes comme exemple. Gauche - Breakout (ATARI 2600) [l'auteur s'est trompé, c'est un jeu de Pong / env. trans.] avec une réponse très rapide et un retour rapide. Droite - Mario Land (Nintendo Game Boy) ne fournit pas d'informations instantanées sur les effets de l'action; de longues périodes d'observations non pertinentes peuvent apparaître entre deux événements importants.

Pour rendre l'apprentissage plus efficace, on peut imaginer des tentatives de transfert d'une partie des connaissances de jeux plus simples. Cette tâche n'est toujours pas résolue et constitue un sujet de recherche actif. Une tâche récemment publiée par OpenAI tente de mesurer exactement cela.

La capacité de transférer des connaissances n'accélérerait pas seulement la formation - je pense que certains problèmes d'apprentissage ne peuvent pas être résolus du tout en l'absence de connaissances de base. Nous avons besoin de l'efficacité des données. Prenez le jeu Prince of Persia:



Il n'y a pas de points évidents en elle.
Il faut 60 minutes pour terminer le jeu.



Est-il possible d'appliquer la même approche que celle utilisée lors de l'écriture du travail sur l'Atari 2600? Quelle est la probabilité que vous puissiez arriver à la fin en appuyant sur des touches aléatoires?

Cette question m'a incité à contribuer à la communauté, qui consiste à tenter de résoudre ce problème. En fait, nous avons la tâche du poulet et des œufs - nous avons besoin d'un meilleur algorithme qui nous permettra de transmettre un message, cependant, cela nécessite des recherches et les expériences prennent du temps, car nous n'avons pas d'algorithme plus efficace.


Un exemple de transfert de connaissances: imaginez que nous avons d'abord appris à jouer à un jeu simple, comme celui de gauche. Ensuite, nous enregistrons des concepts tels que «course», «voiture», «piste», «gagner» et apprendre des couleurs ou des modèles en trois dimensions. Nous soutenons que des concepts communs peuvent être «reportés» entre les jeux. La similitude des jeux peut être déterminée par le nombre de connaissances transférées entre eux. Par exemple, les jeux Tetris et F1 ne seront pas similaires.

Par conséquent, j'ai décidé d'utiliser la deuxième approche idéale, en évitant le ralentissement initial, en accélérant considérablement le système. Mes objectifs étaient:
- environnement accéléré (imaginez que Prince of Persia peut être complété 100 fois plus vite) et lancement simultané de 100 000 jeux.
- un environnement plus adapté à la recherche (nous nous concentrons sur les tâches, mais pas sur les calculs préliminaires, nous avons accès à différents jeux).

Au départ, je pensais que le goulot d'étranglement des performances pouvait en quelque sorte dépendre de la complexité du code de l'émulateur (par exemple, la base de code Stella est grande et elle repose sur des abstractions C ++ - pas le meilleur choix pour les émulateurs).

Consoles

Au total, j'ai travaillé sur plusieurs plateformes, à commencer par l'un des tout premiers jeux jamais créés (avec le jeu Pong) - les Arcade Space Invaders, Atari 2600, NES et Game Boy. Et tout cela a été écrit en C.

J'ai réussi à atteindre une fréquence d'images maximale de 2000-3000 par seconde. Pour commencer à obtenir les résultats des expériences, nous avons besoin de millions ou de milliards d'images, donc l'écart était énorme.


Space Invaders travaillant en FPGA - mode de débogage à faible vitesse. Le compteur FPGA indique le nombre de cycles d'horloge qui se sont écoulés.

Et puis j'ai pensé - et si nous pouvions accélérer le bon environnement avec du fer. Par exemple, les Space Invaders d'origine sont allés au processeur 8080 avec une fréquence de 1 MHz. J'ai réussi à émuler un processeur 8080 40 MHz sur un processeur Xeon 3 GHz. Pas mal, mais après avoir mis tout cela à l'intérieur du FPGA, la fréquence est montée à 400 MHz. Cela signifiait 24 000 FPS à partir d'un seul flux - l'équivalent d'un Xeon à 30 GHz! Ai-je mentionné que vous pouvez entasser 100 processeurs 8080 dans un FPGA moyen? Cela donne déjà 2,4 millions de FPS.


Space Invaders avec accélération matérielle de 100 MHz, un quart de la pleine vitesse


Plus d'une centaine de cœurs à l'intérieur du FPGA Xilinx Kintex 7045 (indiqué par des couleurs vives; la tache bleue au milieu est la logique générale de la démonstration).


Chemin d'exécution inégal

Vous pouvez demander, qu'en est-il du GPU? En bref, nous avons besoin de la concurrence comme MIMD , pas SIMD . En tant qu'étudiant, j'ai travaillé pendant un certain temps sur la mise en œuvre d'une recherche d'arbre Monte Carlo sur un GPU (une telle recherche a été utilisée dans AlphaGo).

À ce moment-là, j'ai passé d'innombrables heures à essayer de faire fonctionner le GPU et d'autres éléments matériels sur le principe de SIMD (IBM Cell, Xeon Phi, CPU AVX) pour exécuter un code similaire, et rien n'en est sorti. Il y a quelques années, j'ai commencé à penser que ce serait bien de pouvoir développer indépendamment du matériel spécialement conçu pour résoudre les problèmes liés à la formation de renforcement.




Accès simultané MIMD

ATARI 2600, NES ou Game Boy?

À 8080, j'ai implémenté Space Invaders, NES, 2600 et Game Boy. Et voici quelques faits à leur sujet et les avantages de chacun d'eux.


NES Pacman

Les Space Invaders n'étaient qu'un échauffement. Nous avons réussi à les faire travailler, mais ce n'était qu'un jeu, donc le résultat n'était pas très utile.

L'Atari 2600 est en fait la norme en matière de recherche d'apprentissage par renforcement. Le processeur MOS 6507 est une version simplifiée du célèbre 6502, son design est plus élégant et plus efficace que celui du 8080. J'ai choisi le 2600 non seulement à cause de certaines restrictions liées aux jeux et à leurs graphismes.

J'ai également implémenté NES (Nintendo Entertainment System), il partage le processeur avec 2600. Les jeux sont bien meilleurs que 2600. Mais les deux consoles souffrent d'un pipeline de traitement graphique trop complexe et de plusieurs formats de cartouche qui doivent être pris en charge.

Pendant ce temps, j'ai redécouvert le Nintendo Game Boy. Et c'est ce que je cherchais.

Pourquoi le Game Boy est-il si cool?

1049 jeux classiques et 576 jeux pour Game Boy Color

Au total, plus de 1000 jeux, une très grande variété, de haute qualité, certains d'entre eux sont assez complexes (Prince), les jeux peuvent être regroupés et assignés à la complexité pour la recherche sur le transfert de connaissances et de formation (par exemple, il existe des options pour Tetris, jeux de course, Mario). Pour résoudre le jeu Prince of Persia, vous devrez peut-être transférer les connaissances d'un autre jeu similaire dans lequel les points sont clairement indiqués (dans Prince, ce n'est pas le cas).


Nintendo Game Boy est ma plateforme de recherche de transfert de connaissances préférée. Sur le graphique, j'ai essayé de regrouper les jeux en fonction de la complexité (subjective) et de la similitude (concepts tels que la course, le saut, le tir, divers jeux comme Tetris; est-ce que quelqu'un a joué à HATRIS?).

Le Game Boy classique a un écran très simple (160x144, couleur 2 bits), donc le prétraitement devient simple, et vous pouvez vous concentrer sur des choses importantes. À 2600, même les jeux simples ont de nombreuses couleurs. De plus, sur Game Boy les objets sont bien mieux démontrés, sans clignoter et sans avoir besoin de prendre au maximum deux images consécutives.



Aucune disposition de mémoire folle, comme le NES ou le 2600. La plupart des jeux peuvent être conçus pour fonctionner avec 2-3 cartographes.

Code compact - J'ai réussi à adapter l'ensemble de l'émulateur en C dans pas plus de 700 lignes de code, et mon implémentation Verilog tient dans 500 lignes.

Il existe la même version simple de Space Invaders que dans l'arcade.



Et le voici, mon Game Boy à matrice de points de 1989 et la version FPGA qui fonctionne via HDMI sur un écran 4K.



Et voici ce que mon ancien Game Boy ne peut pas:


Tetris accéléré avec du fer - enregistrement de l'écran en temps réel, la vitesse est 1/4 du maximum.

Y a-t-il un réel avantage à cela?

Oui. Jusqu'à présent, j'ai testé le système dans des conditions simples, avec un réseau externe de règles qui interagit avec des Game Boys individuels. Plus précisément, j'ai utilisé l'algorithme A3C (Advantage Actor Critic), et je prévois de le décrire dans un article séparé. Mon collègue l'a connecté au réseau convolutionnel sur FPGA, et cela fonctionne.


Comment FGPA communique avec un réseau de neurones


A3C distribué


Mario land: état initial. Une frappe aléatoire ne nous mènera pas loin. Le coin supérieur droit indique le temps restant. Si nous avons de la chance, nous mettrons rapidement fin au jeu après avoir touché la gumba. Sinon, il faudra 400 secondes pour «perdre».


Mario land: après une heure de jeu, Mario a appris à courir, à sauter et a même ouvert une pièce secrète, rampant dans une pipe.


Pac Man: après environ une heure d'entraînement, le réseau de neurones a même pu terminer le jeu une fois (en mangeant tous les points).

Conclusion

J'aimerais penser que la prochaine décennie sera la période où le supercalcul et l'IA se rencontreront. J'aimerais avoir du matériel qui me permette de me mettre à un certain niveau afin de m'adapter à l'algorithme AI souhaité.


Prochaine décennie

Code pour Game Boy en C.

Débogage

Les gens me demandent souvent: qu'est-ce qui a été le plus difficile? C'est tout - l'ensemble du projet a été assez douloureux. Pour commencer, il n'y a pas de spécification pour un Game Boy. Tout ce que nous avons appris, nous l'avons obtenu grâce à la rétro-ingénierie, c'est-à-dire que nous avons lancé une tâche intermédiaire, comme un jeu, et regardé comment il était exécuté. Ceci est très différent du débogage logiciel standard, car ici nous déboguons le matériel qui exécute les programmes. J'ai dû trouver différentes façons d'y parvenir. Et j'ai parlé de la difficulté de surveiller un processus lorsqu'il s'exécute à une fréquence de 100 MHz? Oh, et il n'y a pas d'impression ici.


Une approche pour implémenter un processeur consiste à regrouper les instructions sur leurs fonctions. Avec 6502, c'est beaucoup plus facile. Le LR35092 a rempli beaucoup de bêtises «aléatoires» et il y a de nombreuses exceptions. J'ai utilisé cette table lorsque je travaillais avec le CPU Game Boy. J'ai utilisé une stratégie gourmande - j'ai pris le plus gros morceau d'instructions, les ai implémentées et supprimées, puis les ai répétées. 1/4 des instructions est ALU, 1/4 est le chargement du registre, qui peut être implémenté assez rapidement. De l'autre côté du spectre, il y a toutes sortes de choses distinctes, telles que «le téléchargement de HL vers SP avec un signe», qui devaient être traitées séparément.


Débogage: exécutez le code sur le matériel que vous déboguez, notez le journal de votre implémentation et des informations supplémentaires (cela montre une comparaison du code Verilog à gauche avec mon émulateur C à droite). Exécutez ensuite diff pour que les journaux détectent les incohérences (bleu). L'une des raisons de l'utilisation de l'automatisation est que, dans de nombreux cas, j'ai rencontré des problèmes après des millions de cycles d'exécution lorsqu'un seul indicateur de processeur a provoqué un effet boule de neige. J'ai essayé plusieurs approches, et celle-ci s'est avérée la plus efficace.


Vous aurez besoin de beaucoup de café!


Ces livres ont 40 ans. C'était incroyable de les fouiller et de regarder le monde des ordinateurs à travers les yeux de ces utilisateurs à cette époque - je me sentais comme un invité du futur.

Demande de recherche OpenAI

Au début, je voulais travailler avec des jeux en termes de mémoire, comme décrit dans un article d'OpenAI.

Étonnamment, il a été difficile de faire en sorte que Q-learning fonctionne correctement sur des entrées représentant des états de mémoire.

Ce projet peut ne pas avoir de solution. Il serait inattendu de découvrir que Q-learning ne réussira jamais à travailler avec la mémoire dans Atari, mais il y a des chances que cette tâche soit assez difficile.

Étant donné que les jeux sur Atari n'utilisaient que 128 milliards de mémoire, il semblait très intéressant de traiter ces 128 milliards au lieu de trames plein écran. J'ai obtenu des résultats mitigés, alors j'ai commencé à le comprendre.

Et bien que je ne puisse pas prouver qu'il est impossible d'apprendre de la mémoire, je peux montrer que l'hypothèse selon laquelle la mémoire reflète l'état complet du jeu est fausse. Le CPU Atari 2600 (6507) utilise 128 b de mémoire, mais il a toujours accès à des registres supplémentaires vivant sur un circuit séparé (TIA, adaptateur pour un téléviseur, quelque chose comme un GPU). Ces registres sont utilisés pour stocker et traiter des informations sur des objets (raquette, fusée, balle, collision). En d'autres termes, ils seront inaccessibles si l'on ne considère que la mémoire. NES et Game Boy ont également des registres supplémentaires qui sont utilisés pour contrôler l'écran et faire défiler. Une seule mémoire ne reflète pas l'état complet du jeu.

Seul le 8080 stocke directement les données dans la mémoire vidéo, ce qui vous permet d'extraire l'état complet du jeu. Dans d'autres cas, les registres "GPU" sont connectés entre le CPU et le tampon d'écran, alors qu'ils sont en dehors de la RAM.



Un fait intéressant: si vous effectuez des recherches sur l'histoire du GPU, le 8080 peut être le premier "accélérateur graphique" - il a un registre à décalage externe qui vous permet de déplacer les envahisseurs spatiaux avec une seule commande, ce qui décharge le processeur.




Eof