Запуск DOOM на собственном CPU

Doom — это выпущенная в 1993 году видеоигра, которую разработала id Software. Она совершила революцию в гейминге и стала определяющей для современных шутеров от первого лица. Благодаря её популярности возникла поговорка «Doom можно запустить на чём угодно». Чтобы доказать это, Doom портировали почти на все платформы, от микроконтроллеров до тостеров и даже бактерий.

Две недели назад мы успешно запустили Doom (тормозной) на созданном с нуля CPU (а потом опубликовали об этом видео, получившее несколько миллионов просмотров). Честно говоря, мне до сих пор в это не верится. Но что же мы создали на самом деле? Спроектировали собственный CPU на уровне логических вентилей, подключили его к периферии, адаптировали исходный код DOOM для запуска на этой машине и развернули всё это на FPGA для исполнения в реальном времени. До запуска Doom мы писали только простые программы, например, Pong и множества Мандельброта. Теперь мы можем запускать завершённые опубликованные игры, но путь к этому был довольно непростым.

Требования

Начав с конвейерной архитектуры, мы поставили задачу исполнения более сложных программ. Pong — это замечательно, но ему уже больше пятидесяти лет. Нам хотелось скакнуть в 90-е, однако у нас возникли две серьёзные проблемы: память и скорость. Чем больше программы, тем больше памяти им нужно, а наша архитектура могла задействовать только BRAM FPGA, которой меньше мегабайта. Урезанная shareware-версия Doom (doom1.wad) занимает 14 МБ. И здесь ещё не учтена память для запуска программы, только для её хранения. Вторая проблема — это скорость. На современных PC Doom летает, но на нашем CPU он едва ползает. Нам просто нужно больше скорости.

Мы с Лиамом решили устранять каждую из проблем по отдельности. Сейчас Лиам закладывает фундамент для исполнения с изменением последовательности, что обеспечит повышение параллелизма и позволит использовать трюки с выполнением конвейера. Я взялся за интеграцию памяти. Хоть это может показаться простым — достаточно подключить ещё один чип памяти, в реальности же всё гораздо сложнее.

Интеграция памяти

В нашей исходной архитектуре CPU память была очень чистой. BRAM FPGA имела задержку в 1 такт и с ней очень легко было взаимодействовать. Благодаря этой согласованности нашему конвейерному процессору никогда не приходилось простаивать в ожидании памяти, потому что постоянная задержка была встроена непосредственно в наш конвейер. Кроме того, BRAM позволяет считывать и изменять память слово за словом.

В отличие от неё, память DDR3 медленная, имеет переменные задержки и большую ширину шины. Из-за этого операции с памятью усложняются и становятся менее предсказуемыми, к тому же они намного медленнее. Если бы каждая операция с памятью отправлялась в память DDR3, то скорость CPU была бы черепашьей. И здесь нам на помощь приходит кэш. Программы не используют постоянно всю память, поэтому для повышения скорости доступа кэш хранит активные области памяти в BRAM. Хорошо оптимизированный кэш может почти полностью устранить задержки, добавляемые DDR3.

Архитектура

В новой версии CPU применён относительно стандартный пятиэтапный конвейер: получение команды (Instruction Fetch), декодирование (Decode), чтение регистров (Register Read), исполнение (Execute), запись (Writeback). Кроме того, такая архитектура абстрагирует операции с памятью в единый интерфейс, упрощающий этапы базового конвейера.

Базовый конвейер

Этап Fetch отслеживает указатель программы и получает из памяти нужную команду при помощи кэша команд (ICache). В отличие от предыдущей архитектуры, он самостоятельно обрабатывает перенаправление и простой. С добавлением памяти DDR перенаправление становится намного сложнее. Раньше память имела задержку в один такт, поэтому можно было получать команды в каждом такте и менять адрес запроса к памяти в такте, в котором поступает запрос на перенаправление.

В новой же архитектуре в момент получения этапом Fetch запроса на перенаправление памяти уже может быть отправлен запрос. Теперь нам нужно отслеживать, что следующий ответ от памяти недопустим, а затем запрашивать правильный адрес. После разрешения этой проблемы этап получения команд начал работать идеально.

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

Этап Read существенно изменился. Проблема нашего предыдущего файла регистров заключалась в том, что он использовал комбинационные операции чтения, замедлявшие CPU. В этой версии операции чтения стали конвейерными, что добавляет цикл задержки, но уменьшает задержки на критическом пути исполнения. Другое изменение заключалось в обработке потенциальной опасности Read-After-Write(RAW). Опасность RAW возникает, когда чтение из регистра выполняется до того, как выполнится ожидающая операция записи, что даёт нам некорректные данные. Этап чтения в предыдущей архитектуре отслеживал несколько прошедших через него последних операций записи в регистры. Такая система была логически эффективной, но хрупкой и работала не всегда. Более строгие тесты показали, что в особых случаях эта опасность не распознавалась. В новой версии применяется Register Usage Map (RUM), вычисляемая ядром и подаваемая на этап чтения. RUM — это 32-битная карта, отслеживающая, используется ли регистр. Она естественным образом масштабируется до переменных длин конвейера, не требуя при этом никаких магических констант. Благодаря использованию RUM этап Read принимает решение о том, нужно ли устанавливать флаг опасности и приостановить предыдущие этапы или пропустить команду дальше.

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

Этап Writeback просто записывает значения обратно в файл регистров.

Работа с памятью

Откровенно говоря, базовый конвейер довольно стандартен, самое интересное связано с памятью. В CPU с идеальным конвейером этап получения команды получает новое слово и выполняет получение новых данных в каждом такте. Для сравнения DDR3 нашей FPGA может возвращать по 2 слова каждые 30-60 тактов. Это намного медленнее, чем нужная нам пропускная способность, так что необходим кэш. На самом деле, даже два: этапы получения и исполнения могут запросить в одном такте два разных адреса, поэтому для обслуживания обоих нам нужны независимо работающие кэш команд (Instruction Cache, ICache) и кэш данных (Data Cache, DCache).

Кэш​

ICache и DCache относительно просты и похожи друг на друга. На самом деле, для ICache используется точно тот же внутренний код, что и для DCache, но с вырезанной логикой записи. Оба представляют собой простые однонаправленные кэши прямого отображения. В текущей версии под каждый из них используется по 2048 линий кэша по 4 слова каждая.

При получении запроса к памяти кэш изолирует адрес слова (устранив два младших бита), а затем вычисляет индекс кэша. Этот индекс представляет собой младшие 10 бит адреса слова. Затем он извлекает эту линию кэша из BRAM. Линия кэша состоит из трёх компонентов: данных, метки, статуса. Данные — это сами четыре слова памяти, которые отслеживает кэш. Метка — это старшие биты адреса слова и меры защиты от алиасинга кэша. Алиасинг — это когда несколько адресов указывают на один индекс кэша, и нам нужно не перепутать их. Два бита статуса обозначают сигналы валидности и загрязнённости. Под валидностью подразумевается, что данные линии на самом деле представляют собой данные, а не случайность инициализации; сигнал загрязнённости позволяет узнать, изменял ли CPU линию после её получения из памяти. Если извлечённая линия кэша валидна и имеет соответствующую метку, то кэш выполняет одно чтение или чтение-изменение-запись (в зависимости от операции), не совершая запрос к памяти.

Однако если метка не совпадает, кэш должен обратиться к памяти DDR3. У валидной линии кэша может быть два возможных состояния: чистое и грязное. Если линия чистая, мы можем просто считать из памяти новую линию кэша и отбросить текущие данные. Если она грязная, то кэш сначала должен выполнить запись изменённой линии, а затем запросить новые данные. Учитывая то, что задержка DDR3 может составлять 30-100 тактов в то время, как попадание в кэш занимает всего 2 такта, это очень медленно.

Честно говоря, это неэффективная архитектура. Более совершенный кэш использовал бы более длинные линии кэша для повышения плотности хранения и многократного использования пространства, однако ширина линии в 4 слова была выбрана для упрощения общения с интерфейсом MIG шириной 128 бит на плате FPGA. Позже мы перешли на другую плату, поэтому эта неэффективность только временная.

Разрешение конфликтов​

Возможно, вы заметили ещё одну трудность. Для поддержки одновременно двух исполняемых запросов к памяти мы использовали два кэша, но таким образом мы лишь перенесли проблему в другое место. Что, если и ICache, и DCache одновременно выполнят запрос к памяти? В 6.191 мы решили эту проблему использованием чипов памяти для каждого кэша, но у нашей платы есть только один чип, так что это невозможно. Здесь нам на помощь приходит блок арбитража памяти. Он притворяется интерфейсом памяти для обоих кэшей и обычно просто передаёт запрос к реальной памяти DDR3, но если запрос выполняется, когда уже обрабатывается другой, он делает вид, что память получила запросы, на самом деле занося их в очередь, ожидающую, пока память освободится для их отправки. Разумеется, при этом возникает вероятность взаимоблокировки: один кэш может ограничить другому весь доступ к памяти. Эта проблема решается повышением приоритета DCache относительно ICache, поскольку он находится дальше по конвейеру; в конечном итоге он очистится и перестанет выполнять запросы к памяти.

Низкий уровень​

После внесения всех описанных выше изменений CPU работает идеально с симулируемой памятью, но с реальным оборудованием он работать не будет. Во-первых, интерфейс памяти DDR3 довольно сложный и требует очень точных таймингов и управления. Здесь нам на помощь приходит Xilinx Memory Interface Generator (MIG). Он превращает крайне сложный интерфейс во «всего лишь» сложный. Вторая проблема заключается в том, что MIG работает с собственными диапазонами тактовых частот, поэтому если бы мы напрямую подключили CPU к MIG, он бы столкнулся с не поддающимися расшифровке проблемами таймингов и вылетел. В-третьих, мне не удалось запустить MIG на исходной плате FPGA (с 128-битной шиной), поэтому я позаимствовал плату моего друга Райана Танга, имеющую чип DDR3 меньшего размера с 64-битной шиной.

Эти проблемы были решены при помощи Clock Domain Crossing (CDC), FIFO и обёрток протоколов, но вдаваться в подробности о них было бы слишком утомительно, поэтому можете изучить всё это на Github. Самое главное, что всё работает.

С новой памятью мы можем запустить «Би Муви»

Интерфейсы и ввод-вывод

Прежде, чем портировать DOOM, нам нужно ещё кое-что реализовать в оборудовании. CPU работает, но не может общаться с внешним миром. Нам нужна периферия: вывод на дисплей, аппаратный таймер, отладочный вывод и клавиатурный ввод. Для этой периферии мы решили использовать Memory Mapped IO (MMIO). Контроллер VGA уже встроен, но я расширил его до 12-битного цвета и подключил к разъёму HDMI. С аппаратным таймером тоже было всё просто: он всего лишь отслеживал время в микросекундах и сохранял его в слово в памяти. С отладочным выводом всё было немного сложнее. Простая версия просто связывает передатчик UART с записываемым значением в памяти. Однако если CPU выводил подряд много символов, то терял некоторые, и вывод превращался в мусор, поэтому чтобы устранить переполнения, я использовал FIFO-буфер. С клавиатурным вводом всё было гораздо хуже. Изначально я планировал общаться с чипом USB Host на плате FPGA Urbana, которую мне одолжил Райан. Однако написав драйвер SPI, я с недоумением увидел, что по шине SPI ничего не поступает. Похоже порт USB не обеспечивает питания, а потому не подходит для запитывания клавиатуры. Вместо этого я подключил UART-приёмник и перенаправлял нажатия клавиш со своего ноутбука на FPGA. Неидеально, но работает. Таким образом, мы подготовили всё для запуска DOOM.

Портирование DOOM и отладка​

Портирование DOOM на новый чип — сложная задача: необходимо научиться загружать программу, обеспечивать доступ к нужной периферии, получать и отправлять ввод, а также привычно устранять проблемы, связанные с особенностями платформы. Портирование DOOM на собственный CPU даже ещё сложнее, потому что когда он ломается, непонятно, то ли ошибка в коде, то ли в CPU. Есть и хорошие новости: Ozkl создал doomgeneric, упрощающий процесс портирования. Несмотря на это упрощение, мы столкнулись со множеством трудностей. Мой друг Лиам занялся процессом портирования и, вероятно, поделится своими открытиями в своём блоге. Среди трудностей были проблемы с файловой системой, рендерингом, почему-то куча проблем с printf, из-за чего мы в конечном итоге написали собственную версию. Иногда printf работала, иногда нет.

Многие из этих багов выявили ошибки CPU. Например, мы часто наблюдали, как система попадает в бесконечный цикл на сотни команд и переходов. Также она как будто по произвольным причинам переходила в совершенно нелогичные места. Однако отладка всей программы DOOM одновременно была неподъёмной задачей, поэтому мы разбили её на части и тестировали постепенно усложняющиеся программы. Временам блок арбитража кэша и CDC MIG сталкивались с проблемами и отбрасывали запрос записи. Иногда неправильно вычислялись непосредственные значения, иногда DCache переписывал данные команд. Источником части проблем стал наш самый первый однотактный процессор, и раньше мы с ними никогда не сталкивались. Постепенно мы заставили весь код работать в симуляции.

Однако в «железе» он работать отказывался. Работали все написанные нами программы, но не DOOM. Он прекращал выполнение в произвольных местах, переходил по случайным адресам и каким-то образом начинал читать команды из половины слова. Это не имело никакого смысла и сбивало меня с толку. Я предположил, что это проблема симуляции MIG, потому что только его сложно было симулировать, но все написанные мной тесты памяти работали идеально и в симуляции, и на оборудовании. Потратив на решение много часов, я решил сделать так, чтобы моя симуляция перед загрузкой программы инициализировала память DDR3 со случайными значениями. Это поломало DOOM, но ни одну другую программу. Похоже, DOOM предполагал, что неинициализированная память обнулена, хотя в оборудовании это было не так. После устранения нескольких ошибок компоновки и сборки DOOM наконец-то загрузился на оборудовании.

Дальнейшая работа была довольно простой и нам удалось запустить DOOM с замечательной частотой 0,7 FPS, то есть больше секунды на кадр. На самом деле, этим я и хотел завершить пост: мы добились того, к чему стремились. Но я не мог смириться с 0,7 FPS. Например, я приступал к изучению линейной алгебры, но вместо этого начинал оптимизировать CPU. Возможно, это помешательство.

Путь к 30 FPS 

DOOM с 1 FPS довольно скучен. Да, это впечатляющее достижение, но он неиграбелен. Мы хотели играть в DOOM, а не смотреть слайд-шоу. Проще всего ускорить игру можно было при помощи увеличения тактовой частоты. Подняв её с 100 МГц до 125МГц, мы получили рост FPS примерно на 20%. Не на 25%, потому что задержки памяти не связаны со скоростью ядра CPU. Следующую оптимизацию мы внесли на этапе получения команд CPU. Его исходная архитектура была крайне неэффективной и делала упор на корректность, а не на скорость. Из-за этого она часто делала два запроса к ICache на команду. Исправив это, мы получили примерно 2,5 FPS, то есть в три с лишним раза быстрее.

После этого повышать производительность стало сложнее. Я решил добавить новые команды, реализовал операторы умножения, но не стал реализовывать деление и остаток от деления, потому что это бы повысило сложность конвейера. Таким образом, процессор превратился в CPU RV32I-ZMMUL. Это снова добавило FPS, подняв частоту до 3,5 FPS. Учитывая нашу цель в 15 FPS, это разочаровывало, но всё равно мы делали шаги в нужном направлении.

После этого я внимательнее изучил, какие функции потребляли время CPU, и осознал, что копирование данных из экранного буфера в BRAM контроллера VGA было очень затратным процессом. Он перегружал пропускную способность памяти и сбрасывал кэш. Я изменил код так, чтобы он выполнял запись напрямую в BRAM VGA. Параллельно я осознал, что можно конвейеризовать обработку попаданий при чтении из кэша, чтобы сократить задержку с двух тактов до одного. Это сочетание обеспечило нам около 6,7 FPS.

После этого я уже не видел простых способов повышения скорости без существенного изменения конвейера. Учитывая то, что сейчас мы работаем надо конвейером с изменением последовательности, который заменит большую часть текущего конвейера, не было смысла вкладывать много времени в этот конвейер. Однако оставалась ещё одна возможность: компиляторная оптимизация. Запускаемая нами версия DOOM компилировалась с флагом O0. Это значит, что компилятор вообще не пытался оптимизировать наш код. Казалось, всё просто, нужно просто заменить 0 на 2, после чего всё заработает, однако каждый раз, когда мы пытались это сделать, происходил вылет, в причинах которого мы не могли разобраться. Изначально мы подумали, что это ошибка CPU. Почему бы компиляторная оптимизация могла ломать наш код? Однако спустя много часов отладки мы обнаружили причину. Мы не пометили указатель аппаратного таймера MMIO, как volatile. Компилятор видел, что мы не выполняем запись в таймер, а потому оптимизацией удалял этот код. При изучении оптимизации мне пригодился пост Barish. После устранения этой проблемы игра заработала идеально.

ДУУУУУУУУУМ!!!!!!!!!

Чего же мы добились? После компиляторной оптимизации DOOM заработал плавно с частотой 15-20 FPS, стал вполне играбельным и интересным. Теперь я понимаю, почему в своё время он был так популярен. Надеюсь, что добавив обработку с изменением последовательности и другие оптимизации, мы наконец достигнем 30 FPS.

В заключение​

Портирование DOOM было интересным, хоть и немного травматичным процессом. Я узнал кучу нового о памяти и кэше, но считаю, что полезнее всего оказалось научиться отлаживать системы такого большого размера. Забавно, что я опубликовал 9-секундное видео с запущенной игрой, и оно уже набрало два миллиона просмотров. Что же касается будущих планов, то сейчас мы работаем над реализацией исполнения с изменением последовательности, а также над улучшением паттернов доступа к памяти. Благодаря этому игра будет работать намного быстрее. Возможно, после этого и после написания простого GPU мы сможем портировать Quake 2. А ещё я надеюсь, что скоро мы сможем запустить его на более крупной FPGA.