000. Предыстория.
В 1959 году Н. П. Бруснецов разработал для МГУ уникальную вычислительную машину «Сетунь. Она была основана на троичной системе счисления и хотя элементная база была частично двоичной, что приволило к перерасходу деталей, машина зарекоменловала себя как экономичная и надёжная. Сегодня троичную машину можно увидеть разве что в музее, двоичный код победил.
Но, как я говорил ранее, всегда найдутся люди, готовые сохранять технологии прошлого в виде эмуляторов.
00+. Теоретические основы.
В этой статье рассматривается троичная симметричная система счисления. Цифры в ней положительные и отрицательные, то есть -1/0/1 или более общепринятое -/0/+. Из этого свойства вытекает нативная поддержка нашим будущим компьютером отрицательных чисел.
Есть еще пара аргументов в защиту троичной системы счисления и троичной логики. Экономичность хранения данных для каждого разряда очевидна, экономия линий в шинах, большая емкость привычных типов данных.
Существует формула y = ln(x)/x, физический смысл которой я понимаю как „соотношение объема хранимой информации к сложности ее хранения“, где сложность возрастает по оси X.
Главным же недостатком считается отсутствие базового элемента, который способен находиться в трех состояниях и при этом эффективно работать в режимах, пригодных для построения процессоров. Но для эмулятора это не проблема. Более того, схемы составных троичных элементов известны. Если прикинуть, сколько транзисторов в современных процессорах реально отвечают за систему команд, а сколько за оптимизации, то получится, что реализация самого троичного процессора не такая уж проблема.
0+-. Предпосылки.
О работе Н. П. Бруснецова я узнал сравнительно недавно. Изучив некоторые материалы по Сетуни я понял, что нет необходимости проделывать весь путь заново и можно использовать знания наших дней. Насколько я знаю, троичная виртуальная машина была так же разработана в МГУ. Но материалов по ней мало, а исходников вообще нет.
Как раз в этот момент Н. Вирт опубликовал первые наработки проекта Оберон 2013.
Собственная система команд RISC-подобного процессора, простой язык и простой компилятор для него натолкнули меня на мысль о том, что неплохо бы соединить концепции двух умных людей в одну.
Так и родился проект TRISC, троичный RISC, в рамках которого были реализованы виртуальная машина и компилятор языка Оберон в троичный код. Так же в рамках этого проекта был реализован симулятор логических троичных вентилей, но об этом в другой раз.
Проект был доведен до стадии альфы и заморожен. И вот в 2015 году в процессе изучения языка Dart возникла идея реализовать порт эмулятора для браузера.
Нетипичный для веба проект, много странных целей, что может быть интереснее?
0+0. Цели и средства.
Так как компилятор в троичный код уже работал, то и троичный код у меня был. Поэтому главной целью проекта является построение эмулятора процессора. Чтобы задача не свелась к примитивному набору свичей, допустим, что виртуальная машина должна быть контролируемой, асинхронной, чтобы страничка не застыла — это же веб.
Так же, ради интереса, можно использовать собственные типы данных, которые будут характерны для троичных машин, а сам процессор реализовать в виде отдельных модулей, примерно соответствующих реальным блокам процессора — регистры, АЛУ и т.д. Плюсом будет использование множества фич Dart, ведь проект нужен для самообучения.
Перед глазами имеется оригинальный интерпретатор, с алгоритмикой особых проблем возникнуть не должно.
0++. Математика.
Для начала реализуем логику и математику. Сразу интересно.
Основной логический тип троичной системы — trilean (по аналогии с boolean). Русского аналога слову я не нашел. Для типа trilean существует три значения, true/null/false. Для этих значений существуют основный логические законы. Их сформулировал Ян Лукасевич в 20-х годах прошлого века. Из двух законов, отрицания и импликации выводятся все основные логические операции.
Описав в Dart тип Tril, используем возможности перегрузки операторов.
Немного тестирования, и тип готов. Используем фабричный конструктор, чтобы не плодить множество копий объектов типа Tril, своеобразная оптимизация.
С целыми числами тоже не все так просто. Минимальной единицей информации является трит (по аналогии с битом). В проекте Сетунь использовался шеститритный трайт (по аналогии с байтом). В своем проекте я использовал девятитритный трайт, чтобы быть ближе к восьмибитному байту по размеру. И хотя на первый взгляд, девять больше восьми, этот факт окупается мощностью получившегося типа данных — 19683 значений. От -9841 до 9841 включительно. Без обратных дополнений, без необходимости отличать арифметический сдвиг от логического.
В альтернативной вселенной у людей в 80-х не было проблем с умещением нужных символов в 256 значений одного байта. Опишем этот тип данных tryte на языке Dart, реализуем для него базовые арифметические операции.
Дополнительно введем тип int27, как можно догадаться, в нем 27 тритов, это будет размером машинного слова в нашей системе. Конечно, 27 тритов умещают больше значений, чем 32 бита. Значения от -3 812 798 742 493 до 3 812 798 742 493. Тут можно сказать, что 64 бита уместят больше значений, чем 27 тритов, но при этом понадобится вдвое больше триггеров для такого регистра.
Для самых требовательных можно ввести тип int81, который зарулит в минуса даже 128-битные числа. Кстати, можно заметить, что количество тритов увеличивается по степеням тройки.
Реализуем тип int27 аналогично tryte.
Дополнительным типом нашей математической подсистемы будет тип Trits, это аналог типа SET в Обероне. Типу SET посвящена отдельная статья Н. Вирта, где он называет тип SET недооцененным. Мы же оценим его по достоинству.
Если кратко, то тип Trits (SET) представляет собой множество тритов. Он свободно конвертируем в целое число, но к типу Trits применимы все базовые операции над множествами, сложение, умножение и так далее. Поддержка данного типа упростит реализацию обработки некоторых инструкций в процессоре. А еще он поможет преобразовать троичное число в строку.
Кроме троичной записи чисел символами -/0/+ существует также девятеричная форма записи троичных чисел, в ней символами являются ZXYW01234. Реализуем конвертеры для такой записи чисел.
В качестве развлечения, не связанного с основной задачей — реализуем конвертер в троичную симметричную систему счисления с иррациональным основанием.
Основанием выберем квадрат золотого сечения. Подобная система счисления /называется фибоначчиевой. У нее есть интересное свойство — запись числа симметрична относительно ее нулевого разряда.
Пример всех конвертеров в одной картинке.
Проведем несколько тестов. Математическая подсистема готова.
+--. Железо.
Для начала опишем память. Это довольно просто, память это просто массив трайтов. Мы дополним ее только одной функцией в виде дополнительного класса — возможность читать целые слова данных.
Дополнительно, для памяти опишем MMU, устройство для управления доступом к различным областям памяти. Наше MMU простое, оно позволит подключиться к некоторым ячейкам памяти как к пинам ввода/вывода, а так же позволит использовать отрицательные адреса для доступа к этим пинам из исполняемых программ.
Для процессора я использовал асинхронные возможности языка Dart. Каждый цикл процессора планируется на будущее и исполняется асинхронно. При этом я все же схитрил и ускорил исполнение, увеличив тактовую частоту в 100 раз. Получился своеобразный разгон. Итак, основная активность процессора происходит в методе next().
Пришло время разработать систему команд процессора. Как я уже говорил, я основывался на материалах проекта Оберон 2013. Н. Вирт разработал простую систему команд для реализации своего RISC-процессора на ПЛИС. Я модернизировал эту систему команд для троичного кода. Двух- или трех-операндная арифметика, условные переходы, прямая и косвенная адресация памяти.
В процессоре будет 27 регистров общего назначения, дополнительный регистр PC будет обозначать адрес расположения следующей команды в памяти, регистр IR будет содержать текущую команду. Также присутствует дополнительный трит NZ, который будет содержать дополнительный результат выполнения операций над регистрами. Некоторые регистры общего назначения заберет себе система Оберон для размещения адресов возврата, вершины стека и т.д.
Как известно, процессоры RISC обычно используют отдельные команды для загрузки и выгрузки данных в оперативную память, а все операции проводят над регистрами и данными в них.
Итак алгоритм действий процессора такой — из памяти читается слово по адресу PC, значение записывается в IR и отправляется дешифратору команд, который отправляет сигналы тем или иным блокам на выполнение действий. Такие действия могут поменять значение регистра, при этом в регистр NZ записывается информация о том, является ли значение нулем или оно больше нуля. Вот так, одним тритом отвечают на два вопроса. В последствии этот трит может быть использован при исполнении инструкции условного перехода. В результате выполнения команды меняется состояние памяти в местах, которые исполняемый код считает переменными, меняется адрес перехода процессора на следующем шаге, итерация завершается. Завершение работы процессора происходит при переходе на -1 ячейку памяти, так как в ней записана команда с форматом — (-13).
Всю систему команд нет смысла расписывать. С ней можно ознакомиться в документе github.com/kpmy/tri/blob/master/doc/trinary-0.pdf.
Общение с внешним миром происходит с помощью записи в ячейку памяти с предустановленным адресом значения, которое обработает хост-исполнитель. Например, можно таким образом реализовать примитивную отладочную консоль.
Так как у нас веб-приложение, выведем эту консоль в аутентичном черном окошке с белыми буквами. Для этого воспользуемся готовым компонентом и возможностями стандартной библиотеки Dart по управлению веб-содержимым.
+-0. Первые шаги.
Так как код из рабочей виртуальной машины у меня уже был, коротко опишу особенности его исполнения.
Итак, для прошивки в память готового кода опишем класс-загрузчик, котовый будет загружать код с сервера и записывать его в память. Код в формате JSON, странно, но факт, ведь любой бинарный формат записи был бы не совсем совместим с троичным кодом.
По канонам системы Оберон, загрузчик выполняет модификацию адресов перехода, простая математика вносит в код поправку на смещение кода загружаемого модуля относительно нулевой позиции, которую задает компилятор при компиляции.
Отдельным модулем идет bootstrap, это несколько команд, которые установят в памяти константы машины (размер памяти, адрес таблицы модулей и др.) и переведет процессор на адрес первой исполняемой команды. Bootstrap был /подготовлен вручную.
Модуль Core создан по образу и подобию ядра системы Оберон, модулю Kernel, так как это ядро, в нем много прямых операций с памятью, реализация аллокатора динамических структур (глючит иногда) реализация перехватчика исключений и т.д,
Как раз в модуле Core реализуем самую примитивную консоль. Для вывода строк и чисел будем записывать значения символов в ячейку памяти, как было описано выше. Платформозависимый модуль SYSTEM является виртуальным, его вызовы компилятор переводит непосредственно в машкод.
Невыразительный скриншот.
Проверить работоспособность получившейся виртуальной машины можно вот здесь. Конечно, комплексная отладка и процессора и компилятора одновременно привела к некоторым багам (которые я еще не нашел), но как proof of concept результат работы мне показался достаточным.
+-+. Итоги.
В итоге мы получили вполне работоспособный, расширяемый во все стороны аналог процессора Н. Вирта из проекта Оберон 2013 с модификацией для троичной системы счисления и троичного кода и несколько модулей для работы в получившейся системе.
В оригинальном интерпретаторе я предпринял попытку развить успех и реализовать общение с внешним миром по аналогу порта rs232, с файловой системой на основе протокола 9p. И вот с чем я столкнулся. И та и другая технология, хоть и декларируются кроссплатформенными, при вводе в понятие платформы тритов и трайтов стремительно теряют свою кроссплатформенность. Основа в виде байтов и битов делает портирование таких технологий нетривиальной задачей.
Конечно, здесь можно возразить, что значимость и распространенность троичных систем равна нулю, но тут как в анекдоте про Вовочку, троичность есть, а слов про кроссплатформенность для нее нет. Возможно это является некоторым тормозом в распространении троичных систем. Ведь все и так работает.
Лично я увидел только одно оправданное применение троичных машин — это организация защищенных от вторжений каналов связи. Ведь даже при наличии прямого доступа к каналу хакеру потребуется как минимум аппаратный дешифратор сигналов, который еще надо разработать. Таким образом, борьба брони и снаряда может дать жизнь промышленному применению описанных технологий.
+0-. Ссылки.
Ну и пожалуй, несколько ссылок для тех, кто заинтересуется.
- trinary.ru/ красивый сайт с калькуляторами, календарями, симулятором ОС оригинальной Сетуни.
- ternarycomp.cs.msu.ru/ более серьезный сайт, с описанием патентов, алгоритмов
- www.inf.ethz.ch/personal/wirth/ProjectOberon/index.html авторская страница проекта Оберон 2013.
- github.com/kpmy/tri репозиторий проекта
- bitbucket.org/petryxa/trisc репозиторий оригинального эмулятора
+00. P.S.
Н.П. Бруснецов скончался 4 декабря 2014 года. Надеюсь, дело его жизни не будет забыто.
Автор: kpmy
