Главная » Хабрахабр » [Перевод] Суперкомпьютер на основе Game Boy

[Перевод] Суперкомпьютер на основе Game Boy

Со скоростью более 1 млрд кадров в секунду, это, возможно, самый быстрый из 8-битных консольных кластеров в мире.


Распределённый тетрис (1989)

Как построить такой компьютер?

Рецепт

Возьмите горсть кремния, примените обучение с подкреплением, опыт работы с суперкомпьютерами, страсть к компьютерной архитектуре, добавьте пота и слёз, помешивайте 1000 часов, пока не закипит – и вуаля.

Зачем кому-то может понадобиться такой компьютер?

Короче говоря: чтобы двигаться по направлению к усилению искусственного интеллекта.

Одна из 48 плат IBM Neural Computer, использовавшегося для экспериментов

А вот более подробная версия

2016 год. Глубинное обучение повсеместно. Распознавание изображений можно считать решённой задачей благодаря свёрточным нейросетям, и мои исследовательские интересы стремятся к нейросетям с памятью и обучением с подкреплением.

И всё это происходит просто при просмотре игрового процесса. Конкретно, в работе авторства Google Deepmind было показано, что можно достичь уровня человека или даже превзойти его в различных играх для Atari 2600 (домашней игровой консоли, вышедшей в 1977), используя простой алгоритм обучения с подкреплением Deep Q-Neural Network. Это привлекло моё внимание.

Машина натренировалась при помощи простого алгоритма обучения с подкреплением.
Одна из игр с Atari 2600, Breakout. После миллионов итераций компьютер стал играть лучше человека.

Игру Breakout, пусть она и впечатляющая, нельзя назвать сложной. Я начал проводить эксперименты с играми Atari 2600. Проблема появляется тогда, когда эффекта нужно ждать довольно долго. Сложность можно определить степенью сложности в соответствии ваших действий (джойстик) вашим результатам (очкам).

Слева — Breakout (ATARI 2600) [автор ошибся, это игра Pong / прим.
Иллюстрация проблемы на примере более сложных игр. Справа — Mario Land (Nintendo Game Boy) не даёт мгновенной информации о последствиях действия, между двумя важными событиями могут появляться длительные периоды не относящихся к делу наблюдений. перев.] с очень быстрой реакцией и быстрой обратной связью.

Эта задача сейчас остаётся нерешённой, и представляет собой активную тему для исследований. Чтобы сделать обучение более эффективным, можно представить попытки передать часть знаний из более простых игр. Недавно опубликованное задание от OpenAI пытается измерить как раз это.

Нам требуется эффективность данных. Возможность передачи знаний не только ускорила бы тренировку – я считаю, что некоторые проблемы обучения вообще нельзя решить при отсутствии базовых знаний. Возьмём игру Prince of Persia:

В ней нет очевидных очков.
Для того, чтобы пройти игру, требуется 60 минут.

Насколько вероятно, что можно пройти до конца, нажимая случайные клавиши? Можно ли тут применять тот же подход, что использовался при написании работы по Atari 2600?

По сути, у нас есть задача курицы и яйца – нам нужен алгоритм получше, который позволит нам передавать сообщение, однако для этого нужны исследования, а эксперименты отнимают много времени, поскольку у нас нет более эффективного алгоритма. Этот вопрос подвигнул меня на вклад в сообщество, заключающийся в попытке решить эту задачу.

Затем мы сохраняем такие концепции, как «гонка», «машина», «трасса», «выигрыш» и обучаемся цветам или трёхмерным моделям.
Пример передачи знаний: представьте, что сначала мы научились играть в простую игру, такую, как слева. Сходство игр можно определять по количеству переносимых между ними знаний. Мы утверждаем, что общие концепции можно «переносить» между играми. К примеру, игры «Тетрис» и F1 не будут похожими.

Моими целями были:
— ускоренное окружение (представьте, что Prince of Persia можно пройти в 100 раз быстрее) и одновременный запуск 100 000 игр.
— окружение, более подходящее для исследований (концентрируемся на задачах, но не на предварительных расчётах, имеем доступ к различным играм). Поэтому я решил использовать второй по идеальности подход, избежав изначального замедления, кардинально ускорив систему.

Изначально я считал, что узкое место, связанное с быстродействием, может как-то зависеть от сложности кода эмулятора (к примеру, база кода Stella большая, к тому же, она полагается на абстракции С++ — не лучший выбор для эмуляторов).

Консоли

И всё это было написано на С. Я в сумме работал на нескольких платформах, начиная с одной из самых первых игр из когда-либо созданных (вместе с игрой Pong) – аркадой Space Invaders, Atari 2600, NES и Game Boy.

Чтобы начать получать результаты экспериментов, нам нужны миллионы или миллиарды кадров, поэтому разрыв был огромным. Я сумел достичь максимальной частоты кадров в 2000-3000 в секунду.

Счётчик на FPGA показывает количество прошедших тактовых импульсов.
Space Invaders, работающие в FPGA – режим отладки с низкой скоростью.

К примеру, оригинальные Space Invaders шли на 8080 CPU с частотой 1 МГц. А потом я подумал – что, если бы мы могли ускорить нужное окружение при помощи железа. Неплохо, но после того, как я разместил всё это внутри FPGA, частота поднялась до 400 МГц. Мне удалось эмулировать 8080 CPU частоты 40 МГц на процессоре Xeon частоты 3 ГГц. А я упоминал, что в средний FPGA можно впихнуть 100 процессоров 8080? Это означало 24000 FPS от одного потока – эквивалент Xeon частоты 30 ГГц! Это даёт уже FPS в 2,4 млн.


Space Invaders с хардварным ускорением, 100 МГц, четверть полной скорости


Более сотни ядер внутри Xilinx Kintex 7045 FPGA (обозначены яркими цветами; голубое пятно в середине – это общая логика для демонстрации).


Неровный путь выполнения

Если кратко, то нам нужен параллелизм типа MIMD, а не SIMD. Вы можете спросить, а что насчёт GPU? Студентом я некоторое время работал над реализацией поиска по дереву методом Монте-Карло на GPU (такой поиск использовался в AlphaGo).

Несколько лет назад я начал думать, что было бы неплохо иметь возможность самостоятельно разработать железо, специально предназначенное для решения задач, связанных с обучением с подкреплением. В то время я бесчисленное количество часов провёл, пытаясь заставить GPU и другие железки, работающие по принципу SIMD (IBM Cell, Xeon Phi, AVX CPU) выполнять подобный код, и у меня ничего не вышло.


MIMD-параллелизм

ATARI 2600, NES или Game Boy?

На 8080 я реализовал Space Invaders, NES, 2600 и Game Boy. И вот некоторые факты о них и о преимуществах каждого из них.


NES Pacman

Нам удалось заставить их работать, но это была лишь одна игра, поэтому результат был не очень полезным. Space Invaders были просто разогревом.

Процессор MOS 6507 представляет собой упрощённую версию знаменитого 6502, его дизайн элегантнее и эффективнее, чем у 8080. Atari 2600 – это фактически стандарт в исследованиях обучения с подкреплением. Я выбрал 2600 не только из-за определённых ограничений, связанных с играми и с их графикой.

Там игры гораздо лучше, чем на 2600. Также я реализовал NES (Nintendo Entertainment System), она делит CPU с 2600. Но обе консоли страдают от чрезмерно сложного конвейера обработки графики и нескольких форматов картриджей, которые надо поддерживать.

И это было то, что я искал. А тем временем я заново открыл Nintendo Game Boy.

Почему Game Boy такой классный?

image
1049 классических игр и 576 игр для Game Boy Color

Для решения игры Prince of Persia может понадобиться передача знаний от какой-то другой похожей игры, в которой явно указываются очки (в Prince такого нет). В сумме более 1000 игр, очень большое разнообразие, высокое качество, некоторые из них довольно сложны (Prince), игры можно сгруппировать и назначить сложность для исследований по переносу знания и по обучению (к примеру, есть варианты тетриса, гоночных игр, Mario).

На графике я попытался сгруппировать игры по сложности (субъективно) и похожести (концепции типа гонок, прыжков, стрельбы, различных игр типа тетриса; кто-нибудь играл в HATRIS?).
Nintendo Game Boy – моя любимая платформа для исследований по переносу знаний.

На 2600 даже у простых игр есть много цветов. У классического Game Boy очень простой экран (160х144, 2-битный цвет), благодаря чему предобработка становится простой, и можно сконцентрироваться на важных вещах. Кроме того, на Game Boy объекты демонстрируются гораздо лучше, без мигания и без необходимости брать максимум от двух последовательных кадров.

Большую часть игр можно заставить работать с 2-3 мапперами. Никакой безумной разметки памяти, как у NES или 2600.

Компактный код – у меня получилось уместить весь эмулятор на С не более, чем в 700 строк кода, а моя реализация Verilog умещается в 500 строк.

Есть такая же простая версия Space Invaders, как в аркаде.

И вот он, мой Game Boy с точечной матрицей 1989 года и версия для FPGA, работающая через HDMI на экране с разрешением 4К.

А вот, чего не может мой старый Game Boy:


Тетрис, ускоренный при помощи железа – запись с экрана в реальном времени, скорость равна 1/4 от максимальной.

А есть от этого реальная польза?

Да, есть. Пока что я проверял систему в простых условиях, с внешней сетью правил, взаимодействующей с отдельными Game Boy. Конкретнее, я использовал алгоритм A3C (Advantage Actor Critic), и планирую описать его в отдельном посте. Мой коллега подсоединил его к свёрточной сети на FPGA, и он работает.


Как FGPA общается с нейросетью


Распределенная A3C

Случайное нажатие на клавиши не сможет увести нас далеко.
Mario land: начальное состояние. Если нам повезёт, мы быстро закончим игру после того, как дотронемся до гумбы. В правом верхнем углу показано оставшееся время. Если нет, то на то, чтобы «проиграть», потребуется 400 секунд.


Mario land: после часа игры Марио научился бегать, прыгать и даже открыл тайную комнату, залезши в трубу.


Pac Man: после примерно часовой тренировки нейросеть даже смогла один раз закончить всю игру (съев все точки).

Заключение

Хочется думать, что следующее десятилетие станет периодом, когда суперкомпьютерные вычисления и ИИ найдут друг друга. Мне хотелось бы иметь железо, позволяющее до определённого уровня себя настраивать, чтобы подстраиваться под нужный алгоритм ИИ.


Следующее десятилетие

Код для Game Boy на С.

Отладка

Меня часто спрашивают: что было самым сложным? Всё – весь проект был довольно тягостным. Для начала, нет никакой спецификации для Game Boy. Всё, что мы узнали, мы получили благодаря реверс-инжинирингу, то есть мы запускали промежуточную задачу, например игру, и смотрели, как она выполняется. Это очень отличается от стандартной программной отладки, поскольку тут мы отлаживаем железо, выполняющее программы. Пришлось придумать разные способы для осуществления этого. А я говорил о том, как сложно следить за процессом, когда он выполняется с частотой 100 МГц? А, и никакого printf там нет.

С 6502 это гораздо проще.
Один подход реализации CPU – сгруппировать инструкции по их функциям. Вот эту таблицу я использовал, работая с CPU Game Boy. В LR35092 напихано много всякой «случайной» ерунды и там встречается много исключений. 1/4 инструкций это ALU, 1/4 – загрузка регистров, реализовать которую можно довольно быстро. Я использовал жадную стратегию – брал самый крупный кусок инструкций, реализовывал их и вычёркивал, затем повторял. На другой стороне спектра есть всякие отдельные вещи, типа «загрузить из HL в SP со знаком», которые надо было обрабатывать отдельно.

Потом запускаете diff для логов, чтобы найти несоответствия (голубые).
Отладка: запускаете код на железе, которое вы отлаживаете, записываете лог вашей реализации и дополнительной информации (тут показано сравнение кода Verilog слева с моим С-эмулятором справа). Я пробовал несколько подходов, и этот оказался наиболее эффективным. Одна из причин использования автоматизации – во многих случаях я находил проблемы после миллионов циклов исполнения, когда единственный флажок CPU приводил к эффекту снежного кома.


Вам потребуется очень много кофе!

Удивительно было рыться в них и смотреть на мир компьютеров глазами тогдашних пользователей – я чувствовал себя гостем из будущего.
Этим книжкам по 40 лет.

Запрос на исследования от OpenAI

Сначала я хотел работать с играми с точки зрения памяти, как это описано в посте от OpenAI.

Удивительно, но заставить Q-обучение хорошо работать на входных данных, представляющих собой состояния памяти, было неожиданно трудно.

Было бы неожиданно узнать, что Q-обучение никогда не добьётся успеха на работе с памятью в Atari, но есть шансы на то, что эта задача окажется довольно трудной. Этот проект может не иметь решения.

У меня получались неоднозначные результаты, поэтому я начал с этим разбираться. Учитывая, что игры на Atari использовали всего 128 б памяти, казалось весьма привлекательным обрабатывать эти 128 б вместо полных кадров экрана.

CPU Atari 2600 (6507) использует 128 б памяти, но у него ещё есть доступ к дополнительным регистрам, живущим на отдельном контуре (TIA, адаптер для телевизора, что-то вроде GPU). И хотя я не могу доказать, что обучаться на основе памяти невозможно, я могу показать, что предположение о том, что память отображает полное состояние игры, неверно. Иначе говоря, они будут недоступны, если рассматривать только память. Эти регистры используются для хранения и обработки информации об объектах (ракетка, ракета, мяч, столкновения). Только одна память не отражает полного состояния игры. Также и у NES и Game Boy есть дополнительные регистры, которые используются для управления экраном и прокруткой.

В других случаях регистры «GPU» подключаются между CPU и экранным буфером, находясь вне RAM. Только 8080 впрямую хранит данные в видеопамяти, что позволит вам извлечь полное состояние игры.

Интересный факт: если вы проводите исследования истории GPU, то 8080 может оказаться первым «графическим ускорителем» – у него есть внешний регистр сдвига, позволяющий подвинуть космических захватчиков при помощи одной команды, что разгружает CPU.


EOF


Оставить комментарий

Ваш email нигде не будет показан
Обязательные для заполнения поля помечены *

*

x

Ещё Hi-Tech Интересное!

WebAssembly в продакшне и «минное поле» Smart TV: интервью с Андреем Нагих

Разработка приложений под Smart TV — тоже «нетипичный JavaScript», когда все слышали о чём-то, но немногие лично пробовали. Интерес к WebAssembly велик, но пока что нечасто встретишь людей, использующих эту технологию в рабочем проекте. TV, а в последние месяцы так ...

[Перевод] Ethereum планирует стать на 99% экономичней

Криптовалюта скоро сядет на энергетическую диету, чтобы конкурировать с более эффективными блокчейнами На фоне ажиотажа вокруг Биткоина его «младший брат» Ethereum отошел в тень. Но проект с рыночной капитализацией около 10 млрд долларов вряд ли можно считать незаметным. И объемы ...