Симулятор на 10 000 NAND-вентилей в реальном времени: как мы сделали его для игры на Rust

Мы — небольшая инди-студия anywaymachines и разрабатываем NAND² — головоломку, в которой всё строится из единственного вентиля NAND. Из него вы последовательно собираете NOT, сумматор, регистры, АЛУ и процессор с подмножеством RISC-V. Затем для этого процессора нужно писать программы на ассемблере — вплоть до 3D-шутера в духе Wolfenstein. Игра пока в разработке: запланировано около 200 уровней, разбитых на шесть эпох — реле, транзисторы, микросхемы, микропроцессоры, скорость и система.

Идея родилась из нашей любви к Turing Complete и курсу nand2tetris: оба проекта в своё время показали, как увлекательно собирать компьютер с нуля собственными руками. Нам захотелось пройти этот путь ещё ближе к реальному железу: построить процессор с настоящей системой команд в духе RISC-V и довести дело до работающей на нём программы — от одного вентиля до картинки на экране.

Эта статья посвящена не геймдизайну, а движку. Разберём, как схема с игрового поля превращается в плоский массив; почему основной режим — это незамысловатый проход по всем вентилям без какой-либо событийности; где событийный режим всё же необходим; и как всё это отрисовывается, когда на поле 10 000 вентилей, а камера отъезжает так далеко, что каждый из них занимает пару пикселей. Весь код ниже — настоящий, из репозитория (Rust: crates/sim — движок, crates/game — игра на egui + wgpu), а скриншоты сделаны прямо в редакторе.

Что именно моделируется

Игрок видит сетку, на которой расставлены детали и проложены провода. Внутри движка всё это сводится к трём сущностям:

• сеть (net) — совокупность проводов и пинов, электрически связанных друг с другом. Значение сети хранится как u32, а её ширина составляет от 1 до 32 бит. Шина — это просто широкая сеть;

• узел — вентиль (NAND, AND, …, NOT, BUF) либо «сложный» узел: разветвитель шины, сборщик шины, поведенческий блок;

• последовательные элементы — D-триггеры и регистры, срабатывающие по фронту тактового сигнала, а также генераторы CLOCK.

Схема компилируется в два этапа. Сначала compile_into обходит поле: для каждой клетки собирает проходящие через неё провода и объединяет сети с помощью union-find. Конец провода, упирающийся в другой провод, образует Т-соединение, а простое пересечение двух проводов без конца в этой точке соединением не считается. Блоки игрока (собственный сумматор, собственный регистр) рекурсивно разворачиваются внутрь. Глубина вложенности ограничена 32 уровнями, чтобы блок, вложенный сам в себя, приводил к понятной ошибке, а не к переполнению стека.

Второй этап — Builder::finish: именно он превращает граф в структуру, которая реально выполняется в цикле.

Плоский массив вентилей

Главный цикл симулятора выглядит так:

Вентиль — это struct Gate { op: u8, a: u32, b: u32, o: u32 }: 16 байт, включающих три индекса в общий массив values и код операции. В горячем пути нет ни указателей, ни Box, ни хеш-таблиц. Восемь простых операций обрабатываются единственным match прямо в цикле. Всё, что не укладывается в схему «два входа — один выход» (сплиттеры шин, ПЗУ, блоки-таблицы), вынесено в отдельный вектор complex, а вентиль с кодом 255 хранит в поле a индекс в этом векторе.

Почему значения хранятся как u32, а не как биты в битсете? В игре множество 8-, 16- и 32-битных шин, и держать каждую в одном слове намного проще, чем управлять 32 отдельными сетями. Однобитные вентили маскируют результат операцией & 1, а вентили на шинах работают побитово как есть. Платим за это памятью: в однобитной схеме из 10 000 вентилей 31 бит из 32 в каждом значении не используется. Пока 10 100 сетей занимают всего 40 КБ, такой расклад нас устраивает.

Порядок вычислений: уровни, петли и алгоритм Тарьяна

Чтобы схема без памяти досчитывалась за один проход, вентили должны стоять в топологическом порядке: драйвер сети — раньше всех её потребителей. Это классическая levelized-симуляция. Сложность в том, что игроки строят петли. Защёлка на двух NAND — петля, генератор из нечётного числа инверторов — тоже петля, и в игре это допустимые конструкции, а не ошибки.

Поэтому перед сортировкой граф сжимается по компонентам сильной связности:

Компоненты находит алгоритм Тарьяна — итеративный, без рекурсии, чтобы не упереться в предел стека на большой схеме. Компонента из одного узла без самопетли — обычный узел. Компонента из нескольких узлов — «супер-узел», то есть петля. Затем по конденсированному графу выполняется обычный алгоритм Кана: на каждом шаге обычные узлы складываются в один уровень, а каждая петля получает собственный уровень следом за ними. В итоге получается массив gates, разрезанный на уровни через level_start, и список уровней, являющихся петлями.

Попутно finish решает ещё две задачи. Если у сети несколько драйверов (игрок соединил два выхода), каждому из них выделяется собственная приватная сеть, а в общую их сводит цепочка вентилей OR. Так монтажное ИЛИ превращается в обычные вентили и не требует отдельной логики в цикле. Кроме того, проверяются ширины: 8-битный выход, подключённый к 1-битному входу, — это ошибка компиляции с подсветкой проводов.

Петли до неподвижной точки и фронт тактового сигнала

Обычный уровень вычисляется за один проход. Уровень-петля считается на месте, в фиксированном порядке узлов (по сути, это метод Гаусса — Зейделя), пока выходы петли не перестанут меняться, но не более 63 итераций. Число нечётное намеренно: генератор из инверторов на каждом проходе меняет значение, и после нечётного количества проходов он оказывается в противоположном состоянии — на экране он мигает, а не залипает. Если петля не сошлась, её сети попадают в unstable, и шейдер подсвечивает их красным: игрок видит «дребезг», а не зависший кадр.

latch отвечает за защёлкивание регистров. Сначала все регистры считывают свой d и записывают пары (q, d) во временный вектор, и лишь затем всё это переносится в values. Две фазы нужны ради соответствия настоящему синхронному регистру: если выход одного регистра подан на вход другого (сдвиговый регистр), второй должен увидеть прежнее значение первого, а не уже обновлённое.

Полный такт — это step(): переключаются все CLOCK, затем вызывается settle() — комбинационный проход и защёлка, и так по кругу, пока защёлка что-то меняет (до 64 раз). Повторы нужны для каскадных фронтов: в асинхронном счётчике выход одного триггера служит тактовым входом следующего.

Стресс-плата и честные цифры

Вот как строится плата с гифки:

Это 100 рядов: в каждом свой CLOCK и цепочка из 100 NAND, у которых оба входа замкнуты (то есть каждый работает как инвертор). На каждом полутакте генератор переключается, и волна пробегает по всей цепочке: значение меняют все 10 000 вентилей. Это худший случай для любой оптимизации вида «считать только изменившееся».

Мы вынесли эту функцию в отдельную программу поверх крейта sim и провели замеры на рабочей машине (AMD EPYC 7402, серверный процессор, сборка --release):

	значение
компиляция платы	29,8 мс
узлов / сетей / уровней	10 000 / 10 100 / 100
полный проход, один step()	16,1 мкс
событийный режим, один step()	144,8 мкс

Иными словами, полный проход по всем 10 000 вентилям занимает около 16 мкс — порядка 600 миллионов вычислений вентиля в секунду на одном ядре. В крейте есть и бенчмарк на сумматорах — cargo run -p sim --release --bin bench: 1000 восьмибитных сумматоров по 120 NAND (123 003 узла, 37 уровней) устаканиваются за 289 мкс. Цифры получены на одной машине, на ноутбуке они будут другими, но порядок величин сохранится.

Событийный режим здесь медленнее в 9 раз, и это закономерно: когда меняется 100% вентилей, учёт того, «кто изменился», превращается в чистые накладные расходы. Поэтому в песочнице работает простой проход, а событийный режим включается там, где он выигрывает, — об этом ниже.

Бюджет кадра

Симуляция выполняется в том же потоке, что и интерфейс, поэтому позволять ей работать «сколько получится» нельзя:

Скорость задаёт игрок (в тактах в секунду), время накапливается в acc, а цикл выполняет столько тактов, сколько набежало, но прерывается, если на это ушло больше 8 мс. Если не успели, долг не копится: acc обнуляется, и симуляция просто идёт медленнее заданной скорости, вместо того чтобы замораживать кадр в попытке догнать. Отсюда же берётся значение step_us в строке состояния редактора — оно измеряется прямо здесь.

В этом же цикле работают и точки останова на проводах: после каждого такта сравниваются значения отмеченных сетей, и если что-то изменилось, симуляция останавливается ровно на этом такте.

Рендер: геометрия один раз, состояние каждый кадр

Теперь о том, что происходит при отъезде камеры. Поле рисуется собственным рендером на wgpu, встроенным в egui через paint callback. Провода и пины — это инстансированные капсулы, которые во фрагментном шейдере отрисовываются через SDF (signed distance field), поэтому провод остаётся гладким при любом масштабе. Ключевая идея — разделение геометрии и состояния.

Геометрия (отрезки проводов, корпуса) загружается в GPU-буфер только при смене версии схемы — когда игрок что-то поставил или удалил. Каждый кадр на GPU отправляется лишь состояние: текстура Rgba32Uint шириной 1024, по одному тексель на сеть — [значение, флаги, время последнего изменения, ширина]. Каждый отрезок провода знает номер своей сети, и вершинный шейдер получает её состояние через textureLoad по координатам (net & 1023, net >> 10). Для стресс-платы это 10 100 текселей по 16 байт, около 160 КБ на кадр — для шины PCIe сущий пустяк.

Отсюда и «живая» картинка: провод светится, когда в сети 1, вспыхивает при смене значения (по времени из третьего канала) и краснеет, если сеть помечена как unstable. Процессор в этом не участвует — он лишь копирует массив values.

Чего здесь нет, так это иерархического LOD — агрегации далёких вентилей в «квадратик среднего цвета». При отдалении камеры работают три более простых механизма:

• корпуса деталей рисуются средствами egui, и каждый проверяется на попадание в видимую область (part_on_screen), так что при приближении отрисовывается только то, что видно;

• сетка поля плавно гаснет через smoothstep в зависимости от масштаба, чтобы на дальнем плане не возникал муар из точек;

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

Масштаб камеры ограничен диапазоном от 2 до 160 пикселей на клетку. Плата 100×100 занимает 600×400 клеток, и при 2,2 пикселя на клетку (кадр из гифки) целиком помещается в окно. Сколько FPS это даёт на конкретном железе, мы здесь называть не станем: проверяли на собственной машине и при записи роликов, а не на парке видеокарт.

Когда выигрывает событийный режим

Процессор — полная противоположность стресс-плате. Вентилей там десятки тысяч, но за такт меняется лишь малая часть: АЛУ выполняет одну операцию, декодер расшифровывает одну команду, большинство регистров простаивает. Для таких случаев в движке предусмотрена «турбо»-симуляция — событийная:

struct Ev {
    fan_at: Vec,   // сеть -> комбинационные узлы-потребители (CSR)
    fan: Vec,
    clk_at: Vec,   // сеть -> регистры, у которых она clk
    clks: Vec,
    loop_of: Vec,  // узел -> номер петли
    dirty: Vec,    // битовая маска «грязных» узлов
    ...
}

Когда сеть меняется, touch выставляет в битовой маске бит каждого её потребителя (список потребителей хранится в формате CSR — это два плоских массива). Дальше следует главный трюк:

Узлы уже отсортированы по уровням, а значит, потребитель всегда находится в массиве правее своего драйвера. Поэтому вместо очереди событий достаточно битовой маски и курсора, движущегося только вперёд: берём слово маски, trailing_zeros() выдаёт номер ближайшего «грязного» узла, вычисляем его, и если выход изменился, помечаем потребителей — они гарантированно окажутся правее курсора. Проход завершается, когда курсор доходит до конца. Никакой приоритетной очереди, никакой сортировки по времени, и каждый узел вычисляется за проход не более одного раза. Пустые слова маски пропускаются сразу по 64 узла.

Петли и здесь — особый случай: если «грязный» узел принадлежит петле, пересчитывается весь её уровень до неподвижной точки, после чего снимаются отметки с её собственных узлов. Петля, которая не сошлась (генератор), помечается как «плохая» и пересчитывается на каждом проходе.

Результат событийного режима обязан совпадать с результатом полного прохода бит в бит. Это проверяют два теста: turbo_matches_settle — на синтетических схемах, и turbo_matches_machines — на настоящих процессорах из игры; после каждого полутакта сравниваются все сети.

Таблицы истинности вместо вентилей

Второе ускорение — поведенческий режим. Блок, который игрок уже собрал и который прошёл свой уровень, можно не разворачивать в вентили, а вычислять готовой функцией. Если у блока нет памяти, а на входе не больше 20 бит, движок просто прогоняет его вентильную схему на всех возможных входах и запоминает ответы:

2^20 строк по 4 байта — это максимум 4 МБ на блок, а восьмибитный сумматор с переносом (17 входных бит) — 128 тысяч строк, которые вычисляются один раз и кэшируются в библиотеке. После этого вычисление блока сводится к склейке входов в индекс и одному чтению из массива. Важнейшее свойство: таблица снимается со схемы самого игрока, а не пишется нами, поэтому поведенческий блок ведёт себя в точности как его вентили — включая ошибки.

Для широких блоков конвейера (16-битный сумматор, мультиплексор, декодер команд, исполнительный блок), которые в 20 бит не укладываются, предусмотрены нативные модели на Rust — около сотни строк в natives.rs. Это осознанная оптимизация: без неё большие схемы поздних глав тормозили бы на компьютерах игроков. Нативные модели включаются только в турбо-прогоне финальных глав, только для блоков без состояния и только после того, как блок прошёл тесты своего уровня; дальше он считается по спецификации, без повторной проверки в рантайме. Цена такого решения известна и прямо указана в комментарии к модулю: поведение блока за пределами тестов не покрывается, то есть блок, верный на тестах и ошибочный вне их, в турбо-режиме посчитается «правильно». Эталоном при этом остаётся обычный режим на вентилях.

Что это даёт на машине из главы «Твоя игра» (замер тестом turbo_matches_machines с NAND2_BENCH=1, тот же EPYC, сборка без LTO):

режим	узлов	тактов в секунду
всё в вентилях, полный проход	44 910	~2 500
всё в вентилях, турбо	44 910	~5 500
блоки таблицами, полный проход	4 005	~5 600
блоки таблицами, турбо	4 005	~16 200
таблицы + нативные блоки, турбо	2 867	~31 500

Разрыв между первой и последней строкой — более чем в 12 раз, и именно он отделяет ситуацию «процессор просто работает» от «на этом процессоре можно играть».

От NAND до шутера

Теперь, когда ясно, на чём всё держится, расскажем, что на этом строится. Путь по эпохам таков: NAND, из него — NOT, AND

 

Источник