«Брус-16» — это новая игровая приставка. За полтора месяца мы спроектировали ее архитектуру, а также создали виртуальную машину, компилятор и аппаратную реализацию на FPGA. Специально для «Брус-16» написано более десяти игр. Если вам интересны «серьезные» темы системного программирования, компьютерных архитектур и цифровой схемотехники, а также темы «несерьезные» — разработка игр в духе ретро-инди, демосцена и эстетика минимализма, — то читайте дальше. Кстати, картинка выше состоит ровно из 64 прямоугольников. Это важно. Впрочем, обо всем по порядку!
Введение
Программисты прошлого, писавшие для машин уровня ZX Spectrum, обладали роскошью, почти недоступной сегодня: они понимали машину как единое целое. Это понимание превращало процесс написания кода в удовольствие, которое, увы, сложно ощутить современному прикладному разработчику, вслепую продирающемуся сквозь бесконечные слои абстракций.
Тем не менее целостное понимание машины остается важным для системного программиста и сегодня. Особенно это проявляется в работе с микроконтроллерами и специализированными ускорителями, где нужно жестко экономить аппаратные ресурсы и писать код, выполняющийся без ОС (bare-metal).
Поскольку я преподаю в университете, меня закономерно волнуют вопросы: как заинтересовать новичков специализированными компьютерными архитектурами, как дать «почувствовать вкус» системного программирования?
Здесь мне близка мысль физика Р. Фейнмана: «Чего не могу создать, того не понимаю». В учебных целях разумнее начать не с изучения особенностей промышленного решения, а воссоздать его наглядную, идеализированную, но рабочую модель. Этот подход не нов, и его замечательно иллюстрирует, к примеру, Андрей Карпатый, когда в видеолекциях с нуля реализует нейросети и языковые модели без использования сторонних библиотек.
Известный учебный проект Nand to Tetris демонстрирует, что ключом к целостному пониманию является междисциплинарный подход, объединяющий цифровую схемотехнику, компьютерные архитектуры, системное и низкоуровневое программирование. Nand to Tetris и другие подобные проекты хорошего уровня отличаются использованием компьютерной архитектуры, которая специально спроектирована для задач обучения.
Существенным недостатком «архитектуры из учебника» является небольшое количество прикладных программ, которые можно запустить на реализованной системе. Кроме того, это обычно не слишком интересные и впечатляющие программы. Другое дело, если бы речь шла об играх. Увы, в классических учебниках по системному программированию такое «баловство», как создание игровой приставки, видимо, всерьез даже не рассматривалось.
Разумеется, можно попробовать взять в качестве изучаемой архитектуры одну из реально существовавших в прошлом игровых систем, например, Atari 2600 или NES. В реальности подобные архитектуры оказываются не такими уж простыми и имеют ряд тонких исторических нюансов, которые лишь отвлекают и мешают изучать фундамент. Кроме того, для старых систем уже написаны многие сотни игр, а также известны основные низкоуровневые трюки, поэтому писать что-то свое, пожалуй, уже не так интересно.
Еще один вариант, который я и сам использовал в обучении, — это виртуальная машина CHIP-8. Она имеет по-настоящему простую архитектуру, и для CHIP-8 написаны десятки игр. Но архитектура CHIP-8 слишком примитивна и безнадежно устарела, предполагает разработку на языке ассемблера и плохо приспособлена для современной аппаратной реализации.
По описанным выше причинам, а также чтобы не заскучать на собственных лекциях, я решил спроектировать новую игровую приставку. Оригинальная архитектура здесь используется еще и для того, чтобы побудить молодых системщиков выйти из зоны комфорта в виде запросов к Google и языковым моделям. А «старикам» — помочь выбраться из ностальгического плена привычки к старым моделям компьютеров и восьмибитным игрушкам.
«Брус-16» изначально спроектирована не только для программной, но и для аппаратной реализации. Ведь какая радость для автора игры – увидеть, что его творение успешно работает в «железе»! Хотя речь пока идет о самых недорогих моделях FPGA, но кто знает: быть может, чип «Брус-16» будет когда-нибудь выпущен на заводе.
Архитектура
«Брус-16» — игровая приставка, которая могла появиться при некоторых фантастических допущениях в параллельном мире начала 80-х. По возможностям она ближе не к классическим Sega Mega Drive или TurboGrafx-16, а, скорее, напоминает первую в мире 16-битную приставку Mattel Intellivision.
С аппаратной точки зрения «Брус-16» представляет собой систему реального времени на кристалле, без использования такой дорогой в наше время внешней памяти. В состав «Брус-16» входят:
16-битный двухстековый процессор (CPU) для игровой логики, с разделенными пространствами кода и данных (гарвардская архитектура).
Аппаратный графический ускоритель (GPU), который позволяет одновременно отобразить на экране до 64 закрашенных прямоугольников в разрешении 640x480 с 16-битным цветом и на скорости 60 к/с. Вместо экранного буфера — список команд (display list).
Аппаратный ускоритель для звука (SPU) на основе аддитивного синтезатора с 16 синусоидальными осцилляторами и с выводом 16-битных звуковых семплов.
Контроллер прямого доступа к памяти (DMA), который позволяет автоматически обновлять параметры ускорителей, отображенные в память данных CPU.
Контроллер ввода для двух джойстиков.
Процесс проектирования в основном заключался не в добавлении, а в удалении лишнего — всего, что помешало бы обычному студенту написать игру или виртуальную машину за вечер, компилятор — за неделю, а FPGA-реализацию — за две-три недели.
Отмечу, что проектирование «Брус-16» доставило мне немало удовольствия и, по существу, оказалось метаигрой — игрой в выстраивание правил для создания игр. Хотя «Брус-16» и состоит почти из одних ограничений, здесь уместно вспомнить высказывание Леонардо да Винчи: «Искусство живет ограничениями и умирает от свободы». Поэтому главная трудность оказалась в подборе таких ограничений, которые задают жизнеспособную и оригинальную форму игровых произведений. Минимализм решений «Брус-16» роднит его с демосценой и, как и в случае демосцены, важно было добиться оправданных с аппаратной точки зрения, а не надуманных архитектурных ограничений.
Пожалуй, надо сказать пару слов и о причинах такого названия приставки. Почему брус? Бруски напомнили мне о советском деревянном конструкторе. Так же можно назвать закрашенные прямоугольники, которые рисует GPU. Еще существовали АОНы с созвучным названием в духе «Русь-24». Кстати, число 16 в названии обозначает разрядность приставки, в том же стиле, что и для классической TurboGrafx-16. Наконец, самая очевидная аллюзия — это, конечно, компьютерная архитектура «Эльбрус», которая в своей советской версии тоже являлась стековой.
Программную реализацию «Брус-16» (Windows/Linux/Web) можно найти в github-репозитории. FPGA-реализация, выполненная студентом Кириллом Павловым и успешно проверенная на FPGA-чипах Tang Nano 9K/20K, Tang Primer 25K и Xilinx XC7A200T находится в отдельном репозитории.
Поиграть в игры для «Брус-16» можно с помощью онлайн-эмулятора. Наверное, начать имеет смысл с игры Gerion — нашего «AAA-проекта"»для Брус-16. Оригинальный игровой процесс, десятки уровней, динамическое изменение масштаба камеры, звук и музыка… но лучше об игре расскажет ее автор, Пётр Косых. Обязательно посмотрите также глубоко переработанный порт известной игры Alter Ego от Василия Литвиненко, получивший одобрение автора NES-версии игры, @shiru8bit. Конечно, не стоит забывать и автора оригинала — Дениса Грачёва.
Теперь пришло время подробнее разобрать, почему подсистемы «Брус-16» имеют именно такой вид.
Компилятор и CPU
В названии этого раздела «компилятор» стоит на первом месте неслучайно. В целом программно-аппаратное проектирование процессора можно провести тремя путями:
Сначала разрабатываем аппаратуру, потом отдаем готовый чип компиляторщикам, пусть сами разбираются с ним.
Берем готовую программную инфраструктуру (x86, CUDA, …) и проектируем процессор под нее.
Будем совместно проектировать язык, компилятор и специализированную процессорную архитектуру для поиска компромиссного решения (HW/SW co-design).
В вариантах 2 и 3 именно компиляторщик занимается высокоуровневым проектированием аппаратуры. «У нас есть опыт в области разработки компиляторов. Почему бы нам не подумать о создании процессора?» — это слова Дж. Хеннесси, автора архитектуры MIPS и нескольких классических работ по технологиям компиляции. Компиляторщик Дж. Кок спроектировал архитектуру первого RISC-компьютера IBM 801, опираясь на статистику, полученную с помощью компилятора (при этом аппаратура и компилятор развивались одновременно). Другой компиляторщик, Дж. Фишер, автор архитектуры VLIW, занимался совместным проектированием с оптимизацией аппаратных параметров под конкретные приложения.
Для проектирования CPU выбран самый естественный и поучительный вариант — третий. И раз уж у нас язык, компилятор и архитектура развиваются одновременно, лучше сразу избавить прикладного программиста от необходимости писать на языке ассемблера. Главное, чтобы компилятор вел себя достаточно разумно (и это не неуловимый sufficiently smart compiler, о котором легко говорить, но сложно разработать).
Я задал жесткое ограничение на размер исходного текста учебного компилятора: не более 200 строк (SLOC). Это ограничение сразу направляет на поиск самых простых решений для языка, компилятора и архитектуры.
Языком программирования игр для «Брус-16» является встроенный в Python предметно-ориентированный язык (DSL). Синтаксически это «безобидный» Python — точнее, его подмножество. Однако смысл конструкций языка (семантика) близок к языку C, а местами оказывается даже более низкоуровневым — это плата за простоту реализации компилятора.
Многие современные DSL на Python используют перегрузку операций, при этом декоратором помечаются аппаратно-ориентированные функции, которые необходимо транслировать в код, например, AI-ускорителя. В «Брус-16» используется иной подход: компилятор реализован с использованием модуля ast из стандартной библиотеки.
Этот подход значительно мощнее перегрузки операций. Он позволяет, подобно макросам языка Lisp, задавать новую аппаратную семантику для привычных конструкций Python. В процессе трансляции DSL-программы в дерево абстрактного синтаксиса (ДАС) используется готовый фронтенд компилятора Python. В промышленных решениях подход на основе ast применяют достаточно широко: можно вспомнить, к примеру, реализацию компилятора Triton. Подробнее о создании DSL различной сложности с помощью ast можно узнать из моего доклада на PiterPy.
Вот как выглядит простая программа для изображения круга в псевдографике:
from brus16 import * def send(c): # макроопределение return f'poke(-1, {ord(c)})' # Вывод символа в отладочный порт терминала (адрес -1) save_game('circle.bin', f''' # Функция main может иметь любое другое название, поскольку старт программы начинается # с первой команды, то есть мы сразу попадаем в тело первой определенной функции. def main(): circle(8) while 1: # генерируем пустые кадры wait() def circle(r): y = -r while y < r: x = -r while x < r: if x * x + y * y < r * r: {send('O')} else: {send(' ')} x += 1 {send('\n')} y += 1 ''')
В этом примере f-строка используется для организации препроцессора «для бедных». Подобных нюансов в языке много, и они продиктованы желанием предельно упростить компилятор. Поэтому, например, поддерживается цикл while, но отсутствует for. Разумеется, есть возможность написать код на DSL и в отдельном файле. Подробнее о DSL можно прочитать в документации.
При проектировании CPU я сразу определился с рядом архитектурных ограничений:
Процессор должен быть стековым. Это избавляет компилятор от громоздкой процедуры распределения регистров. Стековые архитектуры сегодня редко встречаются «в кремнии», но для софт-процессоров на FPGA они используются весьма широко.
Разрядность – 16 бит. 8 бит потребовали бы утомительного ручного кодирования или все того же «достаточно умного» компилятора. 16-битные микроконтроллеры используются достаточно широко и сегодня, а 32-битный тракт данных потребовал бы большего числа аппаратных ресурсов. В результате CPU в его FPGA-воплощении оказался в 2 раза компактнее 32-битного RISC-V (PicoTiny).
Фиксированная длина команд и слов данных (16 бит). Это упрощает декодер и делает виртуальную машину «Брус-16» несложной в реализации даже для новичков.
Однотактное выполнение. В отличие от многотактного PicoTiny, CPU выполняет команды за один такт.
Гарвардская архитектура и два стека. Для упрощения однотактного процессора память данных (8192 слова) и память кода (8192 слова) физически разделены. 32 КБ блочной памяти – не проблема для современных FPGA. Аналогично разделены стек данных (32 слова) и стек адресов возврата (16 слов).
Базовое АЛУ + аппаратное умножение. Поддерживаются основные операции базового целочисленного подмножества RISC-V. При этом добавлено умножение, которое легко отображается на аппаратные умножители современных FPGA. Умножение особенно важно для вычислений с фиксированной точкой, на которых строится физика в играх.
Вот простой пример кода:
def is_installed(): return hook_box_pos_y >= {SCREEN_H - BOX_W * 3}
Компилятор транслирует его во вполне предсказуемое стековое представление:
LABEL is_installed PUSH hook_box_pos_y LOAD PUSH 450 GE RET 0
При проектировании удачной системы команд (ISA) важно заранее иметь набор целевых программ, с учетом которых оптимизируется архитектура. Для «Брус-16» такими программами оказались первые игры, написанные на промежуточном представлении (IR) компилятора.
Поверхностный анализ IR привел к явно неоптимальной ISA, показанной ниже.
Здесь мы видим два формата команд: для загрузки литерала и для остальных безоперандных команд. Можно ли сделать лучше?
Для этого я провел детальный анализ часто встречающихся фрагментов кода в наборе программ. Получилась следующая картина:
На основе полученной статистики шаблонные фрагменты удалось «свернуть» в специализированные команды:
Бинарные операции с константным аргументом.
Операции обращения к памяти со смещением-константой.
Однако даже от самых изощренных команд мало толку, если компилятор не умеет ими пользоваться (и нет, ручные intrinsics – не выход!). Поэтому в компилятор «Брус-16» для этих целей добавлено несколько простых правил peephole-оптимизации:
1. PUSH x + binop => binop x 2. ADD 0 | OR 0 | SHL 0 | ... => _ 3. ADD x + LOAD 0 => LOAD x 4. ADD x + STORE 0 => STORE x
С использованием этих правил размер игры Gerion, к примеру, удалось сократить на более чем 900 команд:
В реальности сокращение размера кода оказывается скромнее из-за аппаратных нюансов: при однотактной работе процессора в FPGA результат чтения из памяти доступен не сразу, а на дополнительном такте. Здесь возникает обратная связь со стороны аппаратного проектирования, которая приводит к компромиссу на уровне компилятора: выполняем LOAD только в связке с новой командой PUSH_MR (занести прочитанный результат на стек).
Вот как выглядит финальный вариант ISA:
Что же касается таинственной команды WAIT, которая фигурирует в примере кода для изображения круга, то она используется для реализации аппаратной сопрограммы (да, в духе async/await). Процессор «засыпает», добравшись до WAIT, и его работа возобновляется по внешнему сигналу. Так CPU синхронизируется с другими подсистемами «Брус-16». В частности, WAIT требуется, чтобы сигнализировать GPU, что параметры очередного кадра сформированы и готовы к отправке на экран. И раз уж я заговорил о кадрах, самое время посмотреть, как устроена графика «Брус-16».
GPU
Помните заглавную картинку статьи? Я упомянул, что она состоит ровно из 64 прямоугольников. Это ограничение GPU, больше в одном кадре просто не нарисовать. Теперь пора объяснить, откуда взялось такое странное ограничение.
GPU поддерживает разрешение 640x480 c 16-битным цветом, закодированном в формате RGB565, популярном во встраиваемых системах. Если бы мы захотели использовать классический экранный буфер, то для хранения одного кадра потребовалось бы более 600 КБ блочной памяти. Это за пределами возможностей недорогих FPGA, пришлось бы использовать внешнюю память. Такой вариант «Брус-16» уже нельзя назвать компактной системой на кристалле.
По этой причине вместо экранного буфера в специальной области памяти данных CPU формируется список из 64 команд для рисования закрашенных прямоугольников — ограниченный вариант векторной 2D-графики. Каждый прямоугольник описывается следующими параметрами:
абсолютные или относительные (от предыдущего “абсолютного прямоугольника”) координаты
absиrel,координата
x,координата
y,ширина
w,высота
h,цвет
rgb.
Вот простой пример такого векторного описания спрайта:
Обратите внимание: для перемещения спрайта птицы по экрану достаточно изменить x и y первого прямоугольника. Остальные прямоугольники потянутся за ним, поскольку для них заданы относительные координаты.
Признаюсь, векторная 2D-графика в играх мне нравилась еще со времен старого шедевра Another World от Э. Шайи. Современные игры часто грешат визуальным шумом: слишком много мелких и ненужных деталей, перегруженные интерфейсы, кислотные цвета. Мне же хотелось добиться эстетики минимализма строгих форм. Что может быть проще и лаконичнее прямоугольника? К слову, в современных 2D API зачастую нет функции «нарисовать пиксель», базовым примитивом выступает именно прямоугольник.
Но достаточно ли 64 прямоугольников для создания игр? Честно говоря, ограничение в 64 прямоугольника оказалось тем самым архитектурным решением, которое в «Брус-16» было труднее всего отстаивать. В первую очередь хотелось упростить аппаратную реализацию GPU. Но посмотрите на картинки из игр, ведь получился оригинальный визуальный стиль, этакий «брус-арт»:
Что дальше?
Материал и так получился довольно объемным, а звуковая подсистема все еще не описана. Поэтому я сохраню интригу и не буду сейчас объяснять, почему, к примеру, я заменил в синтезаторе привычную для старых игровых приставок прямоугольную форму волны на синус. Оставлю это для второй части статьи.
Надеюсь, выйдет и статья Кирилла Павлова — взгляд на реализацию Брус-16 в FPGA с точки зрения начинающего RTL-проектировщика.
В репозитории приставки приведен ряд учебных задач, в которых можно попробовать свои силы. Если вас в большей степени интересуют математика и алгоритмы, а не системное программирование, то вот две дополнительные задачи для Брус-16, которые еще ждут своего решения:
Реализуйте аппроксимацию произвольной картинки прямоугольниками GPU. Как насчет видео Bad Apple?
Реализуйте ресинтез произвольного звукового файла с помощью осцилляторов SPU.
Смело создавайте «игры за вечер» для «Брус-16», потому что когда-нибудь мы обязательно проведем игровой конкурс под названием «Брусничный джем»!
Благодарности
Я признателен коллегам-преподавателям и студентам РТУ МИРЭА за интерес к проекту «Брус-16». В частности, хочу сказать спасибо:
Студенту Кириллу Павлову за FPGA-реализацию «Брус-16».
Профессору Илье Евгеньевичу Тарасову за консультации по FPGA.
Студентам Владимиру Миклашевичу и Денису Ананьеву, а также преподавателю Артёму Горчакову за игры.
Отдельное спасибо сторонним разработчикам игр Петру Косых и Василию Литвиненко, а также замечательному художнику pixelrat.