«Ижора»: клеточный автомат-компьютер
Хотелось бы поделиться с читателями Хабра довольно необычной разработкой: настоящим компьютером, сделанном в виде клеточного автомата, действующего по простому правилу Fireworld2 с четырьмя состояниями клеток. Текущая базовая версия компьютера называется «Ижора 1». Еще с 1950-х годов существует такая традиция: давать компьютерам географические названия.
Паттерн, состоящий из более 6 миллионов клеток, содержит 256 килобайт памяти и снабжен монохромным экраном 128×64 пикселей, отражающим состояние экранного раздела ОЗУ, примерно как в ZX Spectrum и других популярных исторических моделях персональных компьютеров. Программы можно писать на ассемблере, компилировать в машинный код, тестировать на эмуляторе и вводить специальной утилитой в сам клеточный автомат. Другая утилита позволяет сохранять текущее состояние компьютера. Для запуска компьютера необходима программа Golly — лучшая на сегодня площадка для подобного рода исследований.
Ассемблер и эмулятор написаны на языке Common Lisp, скрипты для ввода программ в сам клеточный автомат и сохранения его состояния — в Python. Компьютер имеет 32-битную архитектуру и на данный момент в нем все один регистр и одна операция: вычитание с условным переходом в случае отрицательного или нулевого результата (Subleq). Несмотря на примитивность такой модели, давно доказана ее универсальность. Существует даже операционная система Dawn OS, написанная для эмулятора Subleq-процессора.
Итак, суммируем: виртуальный компьютер с экзотической моделью программирования и ресурсами уровня древних ПК 1980-х, исполняющий всего около 10 операций в секунду, требующий современный компьютер с несколькими гигабайтами памяти (рекомендуемый минимум — 8 гигабайт), с эмулятором и ассемблером на Лиспе. Зачем и кому это нужно? Очень краткий ответ: ради хака и ретрокомпьютинга. Ниже — более подробно.
О клеточных автоматах
Клеточный автомат состоит из регулярной решетки ячеек, каждая из которых может находиться в нескольких состояниях. На каждом шаге или «поколении» состояние каждой ячейки меняется в соответствии с состояниями ее соседей. Чаще всего рассматриваются двухмерные автоматы с квадратными ячейками, действующие на теоретически бесконечном поле, имеющие небольшое число состояний (обычно не больше 5). Учитываются только ближайшие 8 соседей ячейки, т.н. окрестность Мура ранга 1. Наиболее знаменитый и исследованный автомат — игра «Жизнь» Джона Конуэя.
В целом клеточные автоматы можно рассматривать как обобщение машин Тьюринга с синхронным параллельным вычислением. Любая классическая машина Тьюринга может быть эмулирована клеточным автоматом. При исследовании того или иного клеточного правила, в свою очередь, часто ставится вопрос о полноте или неполноте его по Тьюрингу, то-есть о теоретической возможности использования к качестве универсального компьютера. В частности, полнота «Жизни» по Тьюрингу была доказана еще Конуэем. Я доказал ее для своего правила стандартным способом: путем эмуляции в нем другого, очень простого одномерного автомата, так называемого правила 110, о котором известно, что оно теоретически пригодно для сколь угодно сложных вычислений.Вышеупомянутая программа Golly позволяет определять и запускать также целый ряд других автоматов, включая одномерные и некоторые трехмерные, с большим радиусом окрестностей, с треугольными и шестиугольными ячейками. Можно там задать даже такие правила, в которых соседние ячейки никак не влияют на работу автомата, зато влияют находящиеся на некотором расстоянии (все или некоторые).
Джон фон Нейман еще в начале 1940-х создал сложный клеточный автомат с 29 состояниями, в котором возможно создать виртуального робота-репликатора, бесконечно копирующего самого себя. Надо заметить, что в момент разработки компьютеров еще не было: фон Нейман разработал свой автомат на бумаге! Конуэй показал, что чрезвычайно сложно может себя вести и удивительно простая модель с 2 состояниями.
Клеточные автоматы используются сегодня для моделирования физических, химических, биологических систем, в области искусственного интеллекта. Нейронные сети в принципе тоже могут рассматриваться как специфические обобщения клеточных автоматов, хотя отличаются от последних потенциально бесконечным числом состояний и сложной топологией связей между нейронами. В свою очередь, клеточный автомат можно рассматривать как своего рода упрощенную нейросеть.
В 2001 году я придумал клеточное правило с 4 состояниями, несколько напоминающее известные правила Brian’s Brain и Starwars. Назвал я это правило Computer, но потом переименовал в Fireworld, по аналогии с правилом Wireworld, где еще в конце 1990-х был создан… скажем так, программируемый калькулятор. При всей элегантности этой штуки, 64 адреса программы и данных годятся лишь для демонстрации концепции. Хотя я знаком с человеком, написавшим для этого калькулятора целый язык программирования.
В Fireworld мне удалось еще 20 лет назад создать логические цепи, затем регистры памяти, сумматор, вычитатель, мультиплексоры и демультиплексоры, но что-либо более сложное там соорудить затруднительно из-за проблем синхронизации сигналов. В конце 2020 году, в ходе обсуждений на английском форуме Lifewiki, я попробовал добавить к Fireworld еще одно состояние: «провода», по поверхности которых могут бегать «сигналы». Правило оказалось весьма удачным: где-то за час я в нем, переставляя клетки на экране, нашел простые механизмы для всех побитных логических операций, а также для записи битов информации.
Правила следующие:
А. Fireworld:
«Красная» или живая клетка рождается, когда окружена двумя другими живыми клетками, одна из которых должна находиться рядом по диагонали, а другая — по горизонтали или вертикали. Легко запомнить, по аналогии с родителями обоих полов.
Красная клетка выживает, если у нее нет соседей, либо два соседа по горизонтали/вертикали (в любом положении) и еще один по диагонали.
Если клетка не выживает, на следующем шаге она становится «желтой». Мне не нравится обозначение «мертвая». В Wireworld это состояние именуется «хвостом электрона». Желтая клетка не мешает красным рождаться или выживать в соседних позициях, но предотвращает рождение живой клетки на ее месте. Такие правила называют Generations. В Golly это правило обозначается сегодня »03ajkr/2ak/3».
Б. Fireworld2:
Правила такие же, как в Fireworld, но клетка выживает еще и с 7 соседями. На работу компьютера это никак не влияет, однако позволяет сконструировать некоторые интересные вещи. Синие клетки «проводов» задаются раз и навсегда, работа автомата не может их никак изменить. Если пустая клетка окружена двумя или тремя клетками «провода», а также одной красной клеткой или двумя красными клетками, расположенными рядом по горизонтали или вертикали, на ее месте рождается красная клетка. Это позволяет легко «ловить» так называемые «фотоны» — «летящие» с максимальной скоростью объекты из двух живых и двух желтых клеток, подобные «космическим кораблям» в игре «Жизнь». В моем репозитории Fireworld собрано еще несколько десятков «фотонных» правил и сотни всяких паттернов.
Почему Лисп? Причем тут Ижора?
В некотором смысле, Лисп обладает таким же изяществом, как и клеточные автоматы: крайней простотой синтаксиса, позволяющей создавать сколь угодно сложные конструкции. Можно сказать, что синтаксиса как такового в классических диалектах Лиспа нет вообще: и данные, и программы представляют собой абстрактные деревья, которые на практике выглядят как заключенные в скобки списки элементов. Труда не составляет написать функцию, пишущую или изменяющую код, в том числе и свой собственный. В Common Lisp можно писать программу и тестировать ее «на лету» кусочек за кусочком. Не нужно каждый раз, как в C или Java, компилировать, а затем отдельно запускать: в Лиспе все это интегрировано. Можно даже во время работы программы ее кусками переписывать. Современные версии Лиспа компилируют сразу в машинный код, поэтому работают быстро, примерно как та же Java.
Года 4 года, тоже на Лиспе, я написал виртуальную машину под названием Nutes, в честь советского троичного компьютера «Сетунь». Машина работает тоже на трочной логике и тоже всего с одной операцией симметричного двойного вычитания двух операндов: в одну ячейку записывается a-b, в другую b-a. Операция задана так, что любой код, инвертированный по знаку и записанный задом наперед, работает точно так же, как и оригинал. Поэтому Nutes — это Setun наоборот.
Опыты с той троичной машиной меня убедили, что одной операции вычитания действительно достаточно для практического синтеза всех прочих. Кстати, в одном из древнейших компьютеров, Manchester Baby, было тоже только вычитание. Он был разработан в 1948 году как чисто тестовая модель с крошечной памятью из 32 регистров, но уже позволял, например, вычислять последовательность простых чисел. Множество советских ЭВМ, да и не только советских, были названы в честь местностей, гор и рек, включая Днепр и Раздан. Сетунь — это нижний приток реки Москвы. Поэтому я решил так назвать свое сооружение: Ижора — левый приток Невы.
Краткое техническое описание
Основная память в виртуальном компьютере «Ижора» состоит из сегментов по 256 байт, адресуемых по 32 бита. Биты там упакованы в зацикленную схему из «проводов» и постоянно крутятся по циклу, на манер ранних моделей компьютерной памяти на линиях задержки.
Сами сегменты гибкие и позволяют разные режимы адресации, от побитовых до 64-битных. Каждый сегмент содержит простой контроллер для записи и чтения. Обе операции совмещены: содержимое памяти переписывается логической операцией исключающего «или» (XOR). Таким образом, если послать на запись 0, сегменты просто выводит содержимое памяти, не меняя его, а если послать 0xFFFFFFFF, то содержимое инвертируется. Компьютер автоматически «ксорит» заранее данные операнда при записи, чтобы вписать в память нужную информацию.
Нужный сегмент из 1024 штук (сетка из 32×32 сегментов) выбирается сериями демультиплексеров, которые открывают только один нужный горизонтальный и вертикальный ряд для пропуска информации. Когда информация, посланная вертикально и горизонтально, «встречается» в нужном секторе, запускается механизм ввода/вывода.
Значительную часть схемы составляет общий контроллер памяти, который разбивает адрес на 5, 5 и 6 бит. Нижние 6 бит обозначают момент, когда нужно послать запрос в сегмент для доступа к требуемой ячейке. Они обрабатываются довольно хитрым синхронизатором. Остальные 10 бит указывают на адрес сегмента. В принципе память можно расширять до бесконечности, прицепив сколько угодно сегментов по вертикали и горизонтали.
Еще в схеме памяти присутствуют временные регистры для упаковки и распаковки битов. Внутри сегментов информация запакована вдвое плотнее рабочей частоты процессора и АЛУ (соответственно, 3 и 6 шагов автомата на бит). Упаковка позволяет намного уменьшить размер памяти и ускорить доступ.
Дисплей постоянно получает информацию из 4 сегментов, каждый пискель реагирует на нужный бит. В общей сложности, видеопамять занимает 1 килобайт и начинается с адреса 0×0400. Поскольку адресация 32-битная, 16 бит адреса позволяют адресовать как раз 256 килобайта. Для наиболее часто встречающихся данных и подпрограмм следует использовать нижние адреса, поскольку время обращения к памяти зависит от расстояния между процессором и данным сегментом (NUMA).
Команды одноадресные: старшие 16 бит расшифровываются как адрес условного перехода, младшие — как адрес операнда. Содержимое аккумулятора вычитается из содержимого операнда; результат записывается одновременно в аккумулятор и по адресу операнда. Если результат вычитания нулевой или отрицательный, вычисление переходит на адрес условного перехода; если положительный, счетчик команд увеличивается на единицу (инкрементируется).
Помимо самих сегментов памяти, весь обмен информацией идет по принципу, напоминающему модем: «пилотный» бит сообщает о том, что вслед за ним следуют n бит данных. Таким образом, 0 кодируется как 01, 1 — как 11, 2 — как 101, и так далее. Исключение составляют только T-триггеры, реагирующие на единичный сигнал. Последовательная модель обмена информацией намного упрощает схему: не нужно многобитовых шин. Важно еще заметить, что везде, кроме синхронизатора обмена данными с ОЗУ, используется асинхронный принцип: элементы компьютера содержат генераторы сигналов, которые включаются, как приходит предварительный бит, обрабатывают следующие за ним биты, прицепляют входной бит обратно к результату, если надо, а потом сами же выключаются. Поэтому не нужно каждый раз считать, как часто бывает в клеточных автоматах, когда именно в точности нужно послать тот или иной сигнал. Элементы сцепляются механически, в принципе можно создать и скрипты для автоматической генерации нужных «микросхем» на основе этого правила.
В репозитории приводятся примеры программ на пока еще недоделанном ассемблере: «Hello World» с применением цикла и без, вывод последовательности простых чисел, чисел Фибоначчи и 128-битных факториалов. Вывод пока просто двоичный, пикселями на дисплее.
Практическое назначение
Основное практическое назначение данной разработки — тестирование компьютеров на прочность. В частности, у меня сгорел в процессе исследования блок питания. Впрочем, он был старый и испорченный цементной пылью. Когда сосед затеял ремонт квартиры, он начал гудеть и шипеть. В смысле, блок питания загудел. Хотя, впрочем, и сосед тоже.
Это, конечно, шутка. Подобные разработки могут быть использованы, возможно, в детском образовании: например, в кружке юных электронщиков. Можно не паять и даже не сцеплять схемки на макете с дырочками, но рисовать их мышкой на экране. Как ни странно, ощущение как от пайки, с той существенной разницей, что побитую схему не придется выкидывать, и вообще не нужно закупаться деталями. Тестирование виртуальных устройств в клеточных автоматах не так уж отличается от реальной электроники: часто приходится подключать сигнал-генераторы, следить за выходом сигнала с разных точек, мерить частоту, думать, где плохо припаял ту или иную деталь.
Может такое в принципе заинтересовать и разработчика микроконтроллеров. Уже есть любительские модельки, основанные на операции Subleq. В общем, прошу любить и жаловать. Или тихо ненавидеть за время, потраченное на знакомство с невиданными доселе извращениями.
