Решил написать свой язык аппаратного синтеза, для Minecraft и что из этого вышло

Мне всегда было интересно, как люди делают в играх сложные инженерные конструкции, и всегда хотелось попробовать повторить. Очень давно я увидел ролик на YouTube о том, как один человек построил процессор на редстоуне. И решил попробовать: чем я хуже? Тогда я собрал несколько прототипов отдельных элементов и понял, что эта задача мне не по плечу. К этому времени я немного освоил Verilog. Родилась мысль: почему никто не пытался использовать языки аппаратного синтеза для построения сложных логических схем в minecraft? Чуть углубившись в различные форумы, я не нашел ни одной похожей утилиты, а свой процессор на редстоуне очень хотелось. Пришлось взяться за написание компилятора самому. Что из этого получилось, читайте под катом.

Проект получился очень большой по объему по этому, его пришлось разбить на отдельные этапы:

Этап 1: Изучить, как работают крупные продукты синтеза микроэлектроники, и ПО для разработки на плис.
Этап 2: Провести обратную инженерию формата хранения нетлистов в популярных продуктах для работы с ПЛИС.
Этап 3: Сделать свою реализацию элементов ПЛИС (LUT ячеек, триггеров)
Этап 4: Сделать свой трассировщик нетлистов, для minecraft.
Этап 5: Внезапно пришлось писать симулятор редстоуна для упрощения процесса отладки, без него у меня процесс дальнейшей разработки сильно забуксовал.
Этап 6: Разработать упрощенный синтаксис для языка аппаратного синтеза.
Этап 7: Написать компилятор.

Итак, приступим. Для начала я опробовал несколько синтезирующих компиляторов Verilog, самым удачным выбором оказался Qartus II, так как поддерживает несколько языков синтеза, таких как Verilog VHDL. Есть хорошая графическая среда для визуального моделирования, есть возможность визуализации нетлистов, есть возможность выгрузить промежуточные нетлисты в удобоваримом виде.

Первой утилитой у меня вышла программа для конвертации файлов в формате VQM в упрошенный формат MNET. VQM представляет собой описатель ячеек, триггеров, их параметров, схемы соединения. В свою очередь MNEТ — это простой список нодов сети и соединений между ними. После пришлось искать способ дальнейшей декомпозиции до уровня гейтов, так как реализация даже одной универсальной 16-битной ячейки LUT получилась слишком громоздкой. Такой способ быстро нашелся в лице логического оптимизатора espresso. И всего за несколько дней я посчитал библиотеку всех возможных реализаций 65 536 логических ячеек.

Затем я начал рисовать отдельные гейты в среде Minecraft, для чего сделал простенький текстовый формат хранения binhl, в котором хранятся все входы и выходы нода и послойная реализация редсоун схемы. Также нашел способ загрузки редстоун схем в Minecraft через worldedit посредством javaScript. Написав кода-генератор для конвертации схем, я приступил к написанию одной из самых сложных частей проекта — трассировщику.

Задач у трассировщика две: размещение элементов и размещение соединений. Размещать элементы несколько сложнее, чем кажется на первый взгляд, так как от их положения зависит длинна соединений и пересечений меду соединениями а, следовательно, количество слоев в схеме. Я опробовал множество вариантов и остановился на следующем алгоритме: размещаем порты ввода вывода, далее размещаем элемент, который имеет больше всего связей к уже размещенным элементам, переходим к следующему элементу, пока не разместим все. Затем пространство разбиваем на слои по 3 блока, в которых размещаем соединения между гейтами. Соединения размещаются с помощью модифицированного A-Star алгоритма, где после размещения каждого соединения обновляется маска. Также, из-за особенностей редстоуна в маинкрафт, максимальная длинна соединения не должна превышать 16 блоков, что вызывает дополнительные сложности в правилах размещения соединений.

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

После того как у меня получилось стабильно собирать редстоун схемы из VQM, я приступил к написанию собственно языка синтеза, за основу я взял Verilog и немного упростил его для удобства использования в minecraft. Для написания компилятора я взял известный лексер и компилятор компиляторов COCO/R. Сделал описание синтаксиса в расширенной форме Бэкуса-Наура, собрал первую версию компилятора.

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

Вот небольшое видео:

Ссылка на GitHub ^[1]

Автор: Gl237man

Источник ^[2]