[Перевод] Реализация «Тетриса» в игре «Жизнь»31.10.2017 14:18

То, что начиналось как приключение, закончилось одиссеей.

Задача по созданию тетрис-процессора размером 2 940 928×10 295 296

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

• PhiNotPi
• El’endia Starman
• K Zhang
• Muddyfish
• Kritixi Lithos
• Mego
• Quartata

Также мы хотим поблагодарить 7H3_H4CK3R, Conor O’Brien и многих других пользователей, вложивших свои труд в решение этой задачи.

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

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

Часть 1: обзор

Этот проект начался как ответ на вопрос со Stackexchange:

Это теоретическая задача — она не имеет ни простого, ни тривиального ответа.

В игре «Жизнь» Конвея существуют такие конструкции, как метапиксели, которые позволяют игре «Жизнь» симулировать любую систему правил, похожую на «Жизнь». Кроме того, известно, что игра «Жизнь» Тьюринг-полная.

Ваша задача заключается в создании клеточного автомата, использующего правила игры «Жизнь» Конвея, который позволяет играть в «Тетрис».

Программа должна получать ввод ручным изменением состояния автомата в определённом поколении, представляющим собой прерывание (т.е. перемещение фигуры влево или вправо, поворот, бросание вниз или случайная генерация новой фигуры для размещения на поле). Определённое количество поколений считается временем ожидания. Результат игры показывается где-нибудь в автомате. Полученный результат должен визуально напоминать поле для настоящего «Тетриса».

Ваша программа будет оцениваться по следующим критериям, в следующем порядке (нижние критерии являются допольнительными по отношению к более высоким):

• Размер граничного прямоугольника — выигрывает прямоугольное поле с наименьшей площадью, полностью содержащее решение.
• Наименьшее количество изменений для ввода — выигрывает решение с наименьшим количеством ячеек (в худшем для вашего автомата случая), необходимых для ручной настройки в качестве прерывания.
• Самое быстрое выполнение — выигрывает решение с наименьшим количеством поколений для продвижения вперёд на один такт симуляции.
• Начальное количество живых клеток — выигрывает наименьшее количество.
• Первое опубликованное — выигрывает самый первый пост с решением.

Основопологающей идеей этого проекта стало абстрагирование. Вместо непосредственной разработки «Тетриса» в игре «Жизнь», мы пошагово расширяли создаваемую абстракцию. На каждом слое мы всё дальше уходили от сложностей «Жизни» и приближались к созданию компьютера, программировать который было бы так же просто, как любой другой.

Во-первых, в качестве основы для компьютера мы использовали OTCA-метапиксели. Эти метапиксели могут эмулировать любые правила игры, похожей на «Жизнь». Важными источниками вдохновения для этого проекта стали Wireworld и компьютер Wireworld, мы стремились создать похожую конструкцию на основе метапикселей. Хотя эмулировать Wireworld с помощью OTCA-метапикселей невозможно, можно установить для разных метапикселей разные правила и создать конструкции из метапикселей, работающие подобно проводам Wireworld.

Следующим шагом стало создание множества фундаментальных логических вентилей, которые можно использовать в качестве основы компьютера. На этом этапе мы уже имеем дело с концепциями, похожими на концепции дизайна процессоров реального мира. Вот пример вентиля OR, каждая ячейка этого изображения на самом деле является целым OTCA-метапикселем. Вы видите, как «электроны» (каждый из которых представляет собой единичный бит данных) входят и выходят из вентиля. Также видны все типы метапикселей, использованные нами для создания компьютера: B/S — чёрный фон, B1/S — синий, B2/S — зелёный, B12/S1 — красный.

Из этого мы разработали архитектуру процессора. Мы потратили много времени на разработку архитектуры, которая была бы одновременно и понятной, и простой в реализации. Компьютер Wireworld использует рудиментарную transport-triggered architecture, в нашем же проекте используется гораздо более гибкая архитектура RISC, имеющая множественные опкоды и режимы адресации. Мы создали язык ассемблера QFTASM (Quest for Tetris Assembly), который управлял изготовлением процессора.

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

Вот иллюстрация архитектуры нашего процессора:

С этого момента нам остаётся только реализовать «Тетрис» в компьютере. Чтобы упростить задачу, мы разработали несколько способов компилирования высокоуровневого языка в QFTASM. У нас есть базовый язык Cogol, второй, более совершенный язык находится в процессе разработки, и, наконец, мы создаём бэкенд GCC. Сейчас программа «Тетриса» пишется на Cogol и компилируется из него.

После того, как конечный код QFTASM «Тетриса» был сгенерирован, следующими шагами были сборка из этого кода в соответствующее ПЗУ, а затем из метапикселей в лежащую в основе игру «Жизнь», на чём наша работа будет закончена.

Запуск «Тетриса»

Те, кто хочет поиграть в «Тетрис» без возни с компилятором, могут запустить исходный код «Тетриса» в интерпретаторе QFTASM. Для просмотра всей игры укажите отображаемые адреса ОЗУ 3–32. Вот постоянная ссылка для удобства: Tetris in QFTASM.

Характеристики игры:

• Все 7 тетромино
• Движение, вращение, плавное опускание фигур
• Очистка линий и подсчёт очков
• Показ следующей фигуры
• Ввод игрока добавляет случайности

Дисплей
Наш компьютер представляет поле «Тетриса» как сетку в памяти. Адреса 10–31 отображают поле, адреса 5–8 — следующую фигуру, адрес 3 содержит счёт.

Ввод
Ввод в игре осуществляется ручным редактированием содержимого адреса 1 в ОЗУ. При использовании интерпретатора QFTASM это означает прямую запись по адресу 1. См. «Direct write to RAM» на странице интепретатора. Каждый ход требует изменения только одного бита ОЗУ, и этот регистр ввода автоматически сбрасывается после считывания события ввода.

value motion
1 вращение против часовой стрелки
2 влево
4 вниз (плавное опускание)
8 вправо
16 вращение по часовой стрелке

Система подсчёта очков
Игрок получает бонус за удаление нескольких линий за один ход.

1 ряд = 1 очко
2 ряда = 2 очка
3 ряда = 4 очка
4 ряда = 8 очков

Часть 2: OTCA-метапиксель и VarLife

OTCA-метапиксель

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

OTCA-метапиксель — это ячейка 2048 × 2048 из 35328 клеток, созданная Брайсом Дью… Она имеет множество преимуществ… в том числе способность эмулировать любой клеточный автомат, похожий на «Жизнь», и очень заметные при уменьшении масштаба клетки в состоянии ON и OFF…

Клеточный автомат, похожий на «Жизнь», в сущности, означает то, что клетки рождаются и выживают на основании того, сколько из восьми соседних с ними клеток живо. Эти правила имеют следующий синтаксис: буква B, за которой следует количество живых соседей, приводящее к рождению, косая черта, буква S, за которой следует количество живых соседей, поддерживающих жизнь клетки. Немного запутанно, так что, думаю, лучше привести пример. Каноничную игру «Жизнь» можно представить в виде правила B3/S23, которое гласит, что мёртвая клетка, окружённая тремя соседями, становится живой, а любая живая клетка с двумя или тремя живыми соседями остаётся живой. В противном случае клетка умирает.

Несмотря на то, что OTCA-метапиксель — это клетка 2048×2048, на самом деле он имеет ограничивающий прямоугольник в 2058×2058 клеток, потому что он перекрывается своими диагональными соседями пятью клетками во всех направлениях. Перекрывающие клетки необходимы для перехвата «глайдеров», которые излучаются, чтобы сообщать соседям-метаклеткам, что он включен. Благодаря этому они не будут влиять на другие метапиксели или бесконтрольно перемещаться. Правила рождения и выживания закодированы в специальной секции клеток в левой части метапикселя присутствием или отсутствием «едоков» в определённых позициях вдоль двух столбцов (один для рождения, другой для выживания). Что касается распознавания состояния соседних клеток, то вот что происходит:

Поток 9-LWSS затем обходит по часовой стрелке вокруг ячейки, теряя LWSS на каждой соседней «включённой» клетке, запускающей ячейку памяти honeybit reaction. Количество отсутствующих LWSS подсчитывается распознаванием положения переднего LWSS с помощью сталкивания с другим LWSS с противоположного направления. Это столкновение выпускает глайдеры, которые запускают ещё одну или две honeybit reaction, если «едоки», определяющие состояние рождения/выживания отсутствуют.

Более подробная схема каждого аспекта OTCA-метапикселя представлена на его веб-сайте: How Does It Work?.

VarLife

Я создал онлайн-симулятор правил Life-подобных игр, в котором можно задать поведение любой клетки в соответствии с любыми правилами, схожими с правилами «Жизни». Я назвал симулятор «Variations of Life». Для краткости потом это название сменилось на «VarLife». Вот его скриншот (ссылка на симулятор: http://play.starmaninnovations.com/varlife/BeeHkfCpNR):

Примечательные особенности:

• Переключает клетки между состояниями «живая»/«мёртвая» и раскрашивает поле по различным правилам.
• Способность запускать и останавливать симуляцию, выполнять по одному шагу за раз. Также возможно выполнять заданное количество шагов с максимальной скоростью или более медленно, со скоростью, устанавливаемой в тактах/с и мс/такт.
• Имеет возможность удалять все живые клетки или полностью сбрасывать поле в пустое состояние.
• Может менять размер поля и клеток, а также включать горизонтальную и/или вертикальную тороидальную свёртку.
• Постоянные ссылки (которые кодируют всю информацию url) и короткие url (потому что иногда бывает слишком много информации, но они всё равно полезны).
• Наборы правил с заданием B/S, цветов и опциональной случайности.
• И последнее — рендеринг gif!

Функция render-to-gif — моя любимая, потому что на её реализацию ушла куча времени. Было очень здорово, когда я наконец доделал её в семь часов утра. С её помощью можно запросто делиться конструкциями VarLife с другими людьми.

Основная схема VarLife

В целом компьютеру VarLife требуется всего четыре типа клеток! Всего восемь состояний, с учётом состояний «мёртвый»/«живой»:

• B/S (чёрный/белый), которое служит в качестве буфера мжеду всеми компонентами, потому что клетки B/S никогда не могут быть живыми.
• B1/S (синие/голубые) — основной тип клеток, используемый для распространения сигналов.
• B2/S (зелёный/жёлтый) — в основном используется для управления сигналами, защищая их от обратного распространения.
• B12/S1 (красный/оранжевый) — используется в некоторых особых ситуациях, например, при пересечении сигналов и хранении бита данных.

Воспользуйтесь этим коротким url, чтобы открыть VarLife с уже закодированными правилами: http://play.starmaninnovations.com/varlife/BeeHkfCpNR.

Проводники

Существует несколько различных конструкций проводников с отличающимися характеристиками.

Это простейший и основной проводник в VarLife, полоса синего, ограниченная полосами зелёного.

Короткий url: http://play.starmaninnovations.com/varlife/WcsGmjLiBF

Это однонаправленный проводник. То есть он будет уничтожать все сигналы, пытающиеся пройти в противоположном направлении. Кроме того, он на одну клетку у́же основного проводника.

Короткий url: http://play.starmaninnovations.com/varlife/ARWgUgPTEJ

Существуют также диагональные проводники, но они почти не используются.

Короткий url: http://play.starmaninnovations.com/varlife/kJotsdSXIj

Шлюзы

На самом деле есть множество способов создания каждого отдельного шлюза, поэтому я покажу только по одному примеру каждого типа. На первом gif показаны, соответственно, шлюзы AND, XOR и OR. Основная идея заключается в том, что зелёная клетка действует как AND, синяя — как XOR, а красная — как OR, а все остальные клетки вокруг них просто обеспечивают правильную передачу.

Короткий url: http://play.starmaninnovations.com/varlife/EGTlKktmeI

Шлюз AND-NOT (сокращённо ANT) оказался жизненно необходимым компонентом. Этот шлюз передаёт сигнал от A тогда и только тогда, когда нет сигнала от B. То есть «A AND NOT B».

Короткий url: http://play.starmaninnovations.com/varlife/RsZBiNqIUy

Хотя это не совсем шлюз, но тайл пересечения проводников очень важен и полезен.

Короткий url: http://play.starmaninnovations.com/varlife/OXMsPyaNTC

Между прочим, здесь нет шлюза NOT. Так получилось потому, что без входящего сигнала должен создаваться постоянный вывод, который не очень хорошо себя проявляет со множеством таймингов, требуемых современным компьютерным оборудованием. Но нам в любом случае удалось обойтись без него.

Кроме того, многие компоненты намеренно создавались таким образом, чтобы умещаться в ограничивающий прямоугольник 11 на 11 (тайл), в котором от момента входа в тайл до выхода из тайла сигналам требуется 11 тактов. Это делает компоненты более модульными и их легче соединять вместе без необходимости регулировки проводников для обеспечения пространства или таймингов.

О других шлюзах, исследованных/созданных в процессе изучения компонентов схем, можно прочитать в посте PhiNotPi: Building Blocks: Logic Gates.

Компоненты задержки

В процессе разработки оборудования компьютера KZhang придумал множество компонентов задержки, показанных ниже.

Задержка на 4 такта:

Короткий url: http://play.starmaninnovations.com/varlife/gebOMIXxdh

Задержка на 5 тактов:

Короткий url: http://play.starmaninnovations.com/varlife/JItNjJvnUB

Задержка на 8 тактов (три отдельных точки входа):

Короткий url: http://play.starmaninnovations.com/varlife/nSTRaVEDvA

Задержка на 11 тактов:

Короткий url: http://play.starmaninnovations.com/varlife/kfoADussXA

Задержка на 12 тактов:

Короткий url: http://play.starmaninnovations.com/varlife/bkamAfUfud

Задержка на 14 тактов:

Короткий url: http://play.starmaninnovations.com/varlife/TkwzYIBWln

Задержка на 15 тактов (проверятся сравнением с этим):

Короткий url: http://play.starmaninnovations.com/varlife/jmgpehYlpT

Итак, вот каковы основные компоненты схем VarLife! Описания основных схем компьютера см. в следующей части, написанной KZhang!

Часть 3: оборудование
Благодаря нашим знаниям логических шлюзов и общей структуры процессора, мы можем начать разработку всех компонентов компьютера.

Демультиплексор

Демультиплексор, или demux — критически важный компонент ПЗУ, ОЗУ и АЛУ. В зависимости от заданных данных селектора он направляет входной сигнал на один из нескольких выходных сигналов. Он состоит из трёх основных частей: последовательно-параллельный преобразователь, устройство контроля сигнала и разделитель тактовых сигналов.

Мы начинаем с преобразования последовательных данных селектора в «параллельные». Это выполняется стратегическим разделением и задержкой данных, чтобы самый левый бит данных пересекал тактовый сигна в самом левом квадрате 11×11, следующий бит данных пересекал тактовый сигнал в следующем квадрате 11×11, и так далее.

Хотя каждый бит данных будет выводиться в каждый квадрат 11×11, каждый бит данных будет пересекаться с тактовым сигналом только один раз.

Далее мы проверяем, соответствуют ли параллельные данные заданному адресу.
Мы осуществляем это с помощью шлюзов AND и ANT, применяемыми для тактовых и параллельных данных. Однако нам нужно убедиться, что параллельные данные тоже выводятся, чтобы их можно было снова сравнить. Вот шлюзы, которые в результате создал я:

Наконец, мы просто разделяем тактовый сигнал, соединяем несколько устройств проверки сигнала (по одному для каждого адреса/вывода), в результате получая мультиплексор!

ПЗУ

ПЗУ должно получать в качестве входных данных адрес, а в качестве вывода отправлять инструкцию по этому адресу. Мы начинаем с того, что используем мультиплексор для направления тактового сигнала на одну из инструкций. Затем нам нужно сгенерировать сигнал с помощью касаний нескольких проводников и шлюзов OR. Касания проводников позволяют тактовому сигналу пройти по всем 58 битам инструкции, а также обеспечивают перемещение сгенерированного сигнала (пока параллельного) по ПЗУ на выход.

Затем нам нужно просто преобразовать параллельный сигнал в последовательный, и на этом ПЗУ будет готово.

В настоящее время ПЗУ генерируется выполнением скрипта на Golly, передающего ассемблерный код из буфера обмена в ПЗУ.

SRL, SL, SRA

Эти три логических шлюза используются для битового сдвига, и они более сложны, чем обычные AND, OR, XOR, и т.п. Чтобы эти шлюзы работали, нам нужно сначала выполнить задержку тактового сигнала на соответствующее время, чтобы выполнить «сдвиг» данных.
Второй аргумент, передаваемый этим шлюзам, сообщает, на столько бит нужно выполнить смещение.

Для SL и SRL нам нужно

1. Убедиться, что 12 самых значимых битов не включены (иначе вывод будет равен 0), и
2. Выполнить задержку данных на нужное время на основании 4 менее значимых битов.

Это можно реализовать с помощью нескольких шлюзов AND/ANT и мультиплексора.

SRA немного отличается, потому что при сдвиге нам нужно копировать знаковый бит. Мы выполняем это, применив AND к тактовому сигналу со знаковым битом, а затем скопировав вывод несколько раз с помощью разделителей проводников и шлюзов OR.

Триггер Set-Reset (SR)

Многие функции процессора зависят от способности хранить данные. Мы можем реализовать её с помощью двух красных клеток B12/S1. Две клетки могут поддерживать друг друга во включенном состоянии или же вместе быть выключенными. С помощью дополнительных схем включения, сброса и чтения мы можем создать простой SR-триггер.

Синхронизатор

Преобразовав последовательные данные в параллельные, а затем включив несколько SR-триггеров, мы можем хранить целое слово данных. Затем, чтобы снова извлечь данные, мы можем просто считать и сбросить все триггеры, и соответствующим образом выполнить задержку данных. Это позволит нам хранить одно (или несколько) слов данных, пока мы ждём другое. Благодаря этому мы сможем синхронизировать два слова данных, полученных в разное время.

Счётчик считывания

Это устройство отслеживает, сколько раз оно должно выполнять адресацию из ОЗУ. Оно решает эту задачу с помощью устройства, похожего на SR-триггер: T-триггера. Каждый раз, когда T-триггер получает входные данные, он меняет состояние: если он был включен, то отключается, и наоборот. Когда T-триггер изменяет своё состояние, он отправляет выходной импульс, который можно передать в другой T-триггер, создав двухбитный счётчик.

Для создания счётчика считывания нам нужно перевести счётчик в подходящий режим адресации с помощью двух шлюзов ANT, и использовать выходной сигнал счётчика для определения того, куда направлять тактовый сигнал: в АЛУ или в ОЗУ.

Очередь считывания

Очередь считывания должна отслеживать, какой из счётчиков считывания отправил входные данные в ОЗУ, чтобы он мог отправить вывод ОЗУ в нужное место. Для этого мы используем несколько SR-триггеров: по одному триггеру на каждый вход. Когда из счётчика считывания передаётся сигнал в ОЗУ, тактовый сигнал разделяется и включает SR-триггер счётчика. Затем вывод ОЗУ проходит вмести с SR-триггером через шлюз AND, а тактовый сигнал из ОЗУ сбрасывает SR-триггер.

АЛУ

АЛУ похожа в работе на очередь считывания в том, что она оно тоже использует SR-триггер для отслеживания того, куда отправлять сигнал. Сначала с помощью мультиплексора включается SR-триггер логической цепи, соответствующей опкоду инструкции. Затем значения первого и второго аргумента вместе с SR-триггером проходят через шлюз AND, а потом передаются в логические цепи. При прохождении тактовый сигнал сбрасывает триггер, так что АЛУ можно использовать снова.

ОЗУ

ОЗУ стало самой сложной частью этого проекта. Оно требовало очень специфического управления каждым SR-триггером, хранящим данные. Для считывания адрес передаётся в мультиплексор и передаётся в сегменты ОЗУ. Сегменты ОЗУ параллельно выводят хранящиеся данные, которые преобразуются в последовательный вид и выводятся. Для записи адрес передаётся в другой мультиплексор, записываемые данные преобразуются из последовательной в параллельную форму, а сегменты ОЗУ распространяют сигнал по ОЗУ.

Метапиксель 22×22 каждого сегмента ОЗУ имеет такую структуру:

Соединив всё ОЗУ, мы получим что-то подобное:

Соединяем всё вместе

С помощью всех этих компонентов и общей архитектуре компьютера, описанной в Части 1, мы можем построить работающий компьютер!

Скачиваемые файлы:
 — Готовый компьютер для «Тетриса»
 — Скрипт создания ПЗУ, пустой компьютер и компьютер для нахождения простых чисел

Часть 4: QFTASM и Cogol

Обзор архитектуры

Если вкратце, то наш компьютер имеет 16-битную асинхронную гарвардскую архитектуру RISC. При создании процессора вручную архитектура RISC (компьютер с сокращённым набором команд) является практически обязательным требованием. В нашем случае это означает, что количество опкодов мало, и, что гораздо более важно — все инструкции обрабатываются очень похожим образом.

Для справки — компьютер Wireworld использует transport-triggered architecture, в которой единственной инструкцией является MOV, а вычисления выполняются записью/считыванием специальных регистров. Хотя эта парадигма позволяет создать очень простую в реализации архитектуру, результат оказывается на грани применимости: все арифметические/логические/условные операции требуют трёх инструкций. Было очевидно, что мы хотим создать более понятную архитектуру.

Чтобы оставить наш процессор простым, в то же время повысив удобство его использования, мы приняли несколько важных решений относительно его конструкции:

• Никаких регистров. Каждый адрес в ОЗУ считается равным и может использоваться как аргумент в любой операции. В каком-то смысле это значит, что всё ОЗУ можно считать регистрами. Это означает отсутствие специальных инструкций загрузки/хранения.
• То же самое касается распределения памяти. Всё, что может записываться или считываться, имеет общую унифицированную схему адресации. Это значит, что счётчик команд (program counter, PC) является адресом 0, а единственная разница между обычными и управляющими инструкциями заключается в том, что управляющие используют адрес 0.
• Данные последовательны при передаче и параллельны при хранении. Из-за «электронной» природы нашего компьютера, сложение и вычитание реализовать значительно проще, когда данные передаются последовательно в порядке little-endian (первым идёт наименее значимый бит). Более того, последовательные данные позволяют избавиться от громоздких шин данных, которые очень широки и неудобны для правильной работы со временем (чтобы данные находились вместе, все «полосы» шины должны иметь одинаковую временную задержку).
• Гарвардская архитектура, то есть существует разделение между памятью программ (ПЗУ) и памятью данных (ОЗУ). Хоть это и снижает гибкость процессора, но помогает оптимизировать размер: длина программы намного больше, чем нужное нам количество ОЗУ, поэтому мы можем разделить программу в ПЗУ и затем сосредоточиться на сжатии ПЗУ, что гораздо проще выполнить, когда она «только для чтения».
• 16-битная разрядность данных. Это наименьшая степень двойки, которая шире стандартного поля для «Тетриса» (10 блоков). Это даёт нам диапазон данных от -32768 до +32767 и максимальную длину программы в 65536 инструкций. (2^8=256 инструкций достаточно для большинства простых вещей, которые можно реализовать в выдуманном процессоре, но никак не для «Тетриса».)
• Асинхронный дизайн. Вместо центрального тактового генератора (или, что аналогично, нескольких генераторов), задающего время компьютера, все данные сопровождаются «тактовым сигналом», передающимся параллельно с данными при их перемещении в компьютере. Некоторые пути могут быть короче других, и это может вызывать сложности в дизайне с центральным тактовым генератором, но асинхронная конструкция может запросто справляться с операциями с переменным временем.
• Все инструкции имеют одинаковый размер. Мы посчитали, что архитектура, в которой каждая инструкция имеет 1 опкод с тремя операндами (значание, значение, целевой адрес) будет наиболее гибким вариантом. Они включают в себя операции с двоичными данными, а также условные переходы.
• Прострая система режимов адресации. Наличие множества режимов адресации очень полезно для поддержки таких вещей, как массивы или рекурсия. Нам удалось с помощью относительно простой системы реализовать несколько важных режимов адресации.

Иллюстрация нашей архитектуры приведена в Части 1.

Работа и операции АЛУ

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

Условные перемещения

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

Мы решили использовать два типа условных перемещений: «переместиться, если не ноль» (MNZ) и «переместиться, если меньше ноля» (MLZ). Функционально MNZ сводится к проверке, является ли любой бит данных равным 1, а MLZ — к проверке, имеет ли знаковый бит значение 1. Соответственно, они полезны для проверок равенства и сравнений. Мы выбрали эти два перемещения потому, что «переместиться, если ноль» (MEZ) должен был создавать из пустого сигнала сигнал TRUE, а «переместиться, если больше ноля» (MGZ) — это более сложная проверка, требующая, чтобы знаковый бит был равен 0 и при этом хотя бы один другой бит был равен 1.

Арифметика

Следующими по важности инструкциями при принятии решения о дизайне процессора стали основные арифметические операции. Как упомянуто выше, мы используем последовательные данные little-endian, а выбор endian определялся простотой операций сложения/вычитания. При получении первым наименее значимого бита арифметические устройства могут легче отслеживать бит переноса.

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

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

Битовые операции

Как можно догадаться, у нашего процессора есть инструкции AND, OR и XOR. Вместо инструкции NOT мы решили использовать инструкцию «and-not» (ANT). Сложность с инструкцией NOT снова в том, что она должна создавать сигнал при его отсутствии, что сложно для клеточных автоматов. Инструкция ANT возвращает 1 только если первый битовый аргумент 1, а первый битовый аргумент — 0. То есть NOT x аналогично ANT -1 x (а также XOR -1 x). Более того, ANT универсальней и имеет основное преимущество при наложении маски: в случае программы для «Тетриса» мы будем использовать её для удаления тетромино.

Битовый сдвиг

Операции битового сдвига — это самые сложные операции, обрабатываемые АЛУ. Они получают два входных значения: сдвигаемое значение и величину сдвига. Несмотря на их сложность (из-за переменной величины сдвига), эти операции критичны для многих важных задач, в том числе для «графических» операций, используемых в «Тетрисе». Битовые сдвиги также служат основой эффективных алгоритмов умножения/деления.

У нашего процессора есть три операции битового сдвига — «сдвиг влево» (SL), «логический сдвиг влево» (SRL) и «арифметический сдвиг вправо» (SRA). Два первых битовых сдвига (SL и SRL) заполняют новые биты нолями (это значит, что сдвинутое вправо отрицательное число больше не будет отрицательным). Если второй аргумент сдвига находится вне интервала от 0 до 15, то, как можно догадаться, результатом будут одни ноли. Для последнего битового сдвига, SRA, битовый сдвиг сохраняет знак входных данных, а потому действует как истинное деление на два.

Конвейер инструкций

Настало время поговорить о некоторых базовых подробностях архитектуры. Каждый цикл ЦП состоит из следующих пяти этапов:

1. Получение текущей инструкции из ПЗУ

Текущее значение PC используется для получения соответствующей инструкции из ПЗУ. Каждая инструкция имеет один опкод и три операнда. Каждый операнд состоит из одного слова данных и одного режима адресации. Эти части при считывании из ПЗУ отделяются друг от друга.

Опкод — это 4 бита, чтобы была возможность поддерживать 16 уникальных опкодов, 11 из которых назначены:

0000 MNZ Move if Not Zero
0001 MLZ Move if Less than Zero
0010 ADD ADDition
0011 SUB SUBtraction
0100 AND bitwise AND
0101 OR bitwise OR
0110 XOR bitwise eXclusive OR
0111 ANT bitwise And-NoT
1000 SL Shift Left
1001 SRL Shift Right Logical
1010 SRA Shift Right Arithmetic
1011 unassigned
1100 unassigned
1101 unassigned
1110 unassigned
1111 unassigned

2. Запись результата (при необходимости) предыдущей инструкции в ОЗУ

Выполнение записи зависит от состояния предыдущей инструкции (например, от значения первого аргумента условного перемещения). Адрес записи определяется третьим операндом предыдущей инструкции.

Важно заметить, что запись выполняется после получения инструкции. Это приводит к созданию слота задержки перехода, в котором инструкция выполняется сразу после инструкции ветвления (любой операции, выполняющей запись в PC) вместо первой инструкции целевого адреса ветвления.

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

Если вкратце, то поскольку вывод предыдущей инструкции записывается в ОЗУ после получения следующей инструкции, после условных переходов должна идти пустая инструкция. В противном случае PC не обновится для перехода правильно.

3. Считывание данных для аргументов текущей инструкции из ОЗУ

Как упомянуто выше, каждый из трёх

© Habrahabr.ru