Решил написать свой язык аппаратного синтеза, для 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
Поделиться публикацией

Комментарии 17

    +4
    Хм… очень круто. Но не очень понятно зачем все это.
    А Вы не думали на верилог написать свою ПЛИС к которой потом делать компилятор и трассировщик? Имхо — это более здоровое занятие..
      +1
      Вполне интересная мысль. Можно попробовать сделать что-то вроде OpenFPGA но не думаю что стоимость ее выпуска будет адекватной.
        0
        Я начинал делать кое-что для своей "плис". Сам логический элемент не трудно описать — это только ЛУТ и триггер. И конфигурируемый коммутатор вроде бы сделал. А вот дальше не знаю как быть. Сколько должно быть линий проводов между строками и столбцами логических элементов? Как это рассчитать? Как сделать компилятор?
        Вот мой пример простейшей ПЛИС внутри ПЛИС из четырех логических элементов http://marsohod.org/projects/plata1/166-minicpld
          0
          Точных формул расчетов как я понял нет. Из того что я узнал, в плис от Altera 8*8 используют 32 соединения в каждом столбце и 32 в каждом ряду в большинстве случаев этого оказывается достаточно.В ПЛИС большего размера ячейки обедняются в суперблоки, которые коммутируются отдельно. Когда соединений не хватает компилятор перекидывает соединения сквозь некоторые ячейки LUT. По поводу как написать компилятор, в 2х словах не расскажешь.
          +1
          Посмотрите сколько стоят отечественные ПЛИС производства Воронежского завода (например вот тендер 2 штуки ПЛИС 5576ХС4Т за 100тыс рублей http://www.tenderer.ru/tenders/3/tender16719913.html). Это аналог старой альтеровской микросхемы (EPF10K200E), уже снятой с производства. Правда она там у них с золотыми ногами в керамическом корпусе для военных. Почему они до сих пор делают такую старую ПЛИС?
          Я так понимаю, главная проблема в плисоводстве — это среда разработки для ПЛИС и компилятор — это главное ноу-хау, которого нет у Воронежского завода. Поэтому они продолжают использовать Альтера Max-Plus — но тут честно говоря могу ошибаться.
          Мне кажется ценно не устройство ПЛИС — более или менее оно всем известно, но компилятор, трассировщик, временной анализатор — вот это ценно.
          Я честно говоря думал делать бэк-енд для icarus verilog. Этот компилятор с открытыми исходниками очень качественно анализирует синтаксис и вероятно мог бы использоваться для создания нетлистов.
            0
            Точно не помню но одна из старых версий умела делать нетлисты в edf формате, но в более поздних версиях этот функционал убрали. в моем проекте даже остался модуль для использования в качестве фронтенда edf листов от икаруса. Только как я позднее выяснил, генерация нетлистов в икарусе мягко говоря не доделана.
        +6
        Придётся подумать над оптимизацией размера. По видео хорошо заметно, что вся машина не входит в область расчёта, и поэтому её дальние части работать не будут.
        А вообще большущее спасибо за работу. Сам хотел такое делать, но руки не доходили.
          0
          достаточно всё расположить в области 8x8 чанков (чанки грузятся на все 256 блоков высоты, может быть и хватит, а 8x8 это область загрузки чанков по-дефолту на многих серверах, сам-же minecraft не позволяет загрузить больше 32х32)

            0
            Для minecraft есть множество различных модов чанклодеров, это частично решает проблему. Сейчас работаю для построения многослойных схем в высоту чтоб собирать что-то более сложное.
          0
          Только написать не "свой язык" а "свой компилятор verilog". Вообще идея использовать minecraft как middle-end инструментария моделирования динамических систем в 3D выглядит с одной стороны профанацией CAD-а, но с другой — открытым хабом для соединения всего и вся на тему виртуальной реальности.
            0
            В данном случае у меня компилятор своего языка. Вот пример синтаксиса Git Hub
              0
              А почему не (подмножество) verilog?
                0
                В verilog слишком много конструкций которые будут лишними и возможно плохо реализуемыми в minecraft, не хотелось излишне усложнять проект.
            +2
            Всё правильно сделал. Теперь пусть туда Линукс портирует.
              +6
              Потом развернуть ЦОД и конкурировать с облаком MS Azure изнутри облака MS Azure.
              0
              Как быстро это работает? Сам собирал только простейший сумматор с дешифратором, и то задержка ощутима была.
                0
                16 битный счетчик отрабатывает от 200 до 800 тиков, это от 10 до 40 секунд.

              Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

              Самое читаемое