Какой код понимает компьютер двоичный троичный
В нашей жизни мы пользуемся определенной логикой. В компьютерной технике применяется булева (бинарная) логика, подразумевающая лишь два возможных состояния - "0" или "1" (истина - ложно, да - нет). Однако, в быту нам этой логики уже не достаточно, - нам нужны дополнительные варианты, кроме белого и черного, да или нет. Как правило, - это дополнительное состояние неопределенности. Голосуя, мы говорим о тех, кто "За", тех кто "Против" и кто "Воздержался". Это более функциональная, близкая к мыслительному процессу логика. Но, проблема с навязыванием двоичной логики - это не порождение нашего компьютерного мира, история с запретом на применение троичной логики насчитывает не одну сотню лет и появилось за долго до того, как возникла задача разработки компьютерной техники. Этот запрет, означенный как "Закон исключения третьего" появился как упрощение интуитивной логики, и являющегося базисом классической бинарной логики.
Мы сегодня работаем на компьютерах, применяющих двоичную логику, но история имеет и иные решения. Были разработки и работающие компьютеры, на основе троичной логики. Одним из таких проектов был компьютер "Сетунь", выпускавшийся в нашей стране в 60-х годах.
Но жизнь этих технологий была ограничена, и, в конечном итого, эти компьютеры не смогли заявить о себе и получить признательность своих потребителей. В мире победили компьютеры с бинарной логикой.
Но в чем проблема, скажет читатель? Победил, - значит таков закон рынка, не смог показать свое преимущество и проиграл.
0+-. Предпосылки
О работе Н. П. Брусенцова я узнал сравнительно недавно. Изучив некоторые материалы по Сетуни я понял, что нет необходимости проделывать весь путь заново и можно использовать знания наших дней. Насколько я знаю, троичная виртуальная машина была так же разработана в МГУ. Но материалов по ней мало, а исходников вообще нет.
Как раз в этот момент Н. Вирт опубликовал первые наработки проекта Оберон 2013.
Собственная система команд RISC-подобного процессора, простой язык и простой компилятор для него натолкнули меня на мысль о том, что неплохо бы соединить концепции двух умных людей в одну.
Так и родился проект TRISC, троичный RISC, в рамках которого были реализованы виртуальная машина и компилятор языка Оберон в троичный код. Так же в рамках этого проекта был реализован симулятор логических троичных вентилей, но об этом в другой раз.
Проект был доведен до стадии альфы и заморожен. И вот в 2015 году в процессе изучения языка Dart возникла идея реализовать порт эмулятора для браузера.
Нетипичный для веба проект, много странных целей, что может быть интереснее?
Емкость
Троичная СС вмещает больший диапазон чисел, т.к. 3^n>2^n (где n-натуральное число). Например, если n=9, то 3^9=19683>2^9=512.
3.
Какие еще преимущества давало применение троичной логики Сетунь?
В первую очередь, такая логика обеспечивает оптимальное построение арифметики чисел со знаком. При этом, не только нет нужды в искусственных и несовершенном дополнительном, прямом либо обратном кодах чисел, но арифметика обретает ряд значительных преимуществ: единообразие кода чисел, варьируемая длина операндов, единственность операции сдвига, трехзначность функции знак числа, оптимальное округление чисел простым отсечением младших разрядов, взаимокомпенсируемость погрешностей округления в процессе вычисления.
При минимальном наборе команд (всего 24 одноадресные команды) “Сетунь” обеспечивала возможность вычислений с фиксированной и с плавающей запятой, обладала индекс-регистром, значение которого можно как прибавлять, так и вычитать при модификации адреса, предоставляла операцию сложения с произведением, оптимизирующую вычисление полиномов, операцию поразрядного умножения и три команды условного перехода по знаку результата. По результатам межведомственных испытаний в 1960 г “Сетунь” была признана первым действующим образцом универсальной вычислительной машины на безламповых элементах, которому свойственны “высокая производительность, достаточная надежность, малые габариты и простота технического обслуживания”.
00+. Теоретические основы
В этой статье рассматривается троичная симметричная система счисления. Цифры в ней положительные и отрицательные, то есть -1/0/1 или более общепринятое -/0/+. Из этого свойства вытекает нативная поддержка нашим будущим компьютером отрицательных чисел.
Есть еще пара аргументов в защиту троичной системы счисления и троичной логики. Экономичность хранения данных для каждого разряда очевидна, экономия линий в шинах, большая емкость привычных типов данных.
Существует формула y = ln(x)/x, физический смысл которой я понимаю как «соотношение объема хранимой информации к сложности ее хранения», где сложность возрастает по оси X.
Главным же недостатком считается отсутствие базового элемента, который способен находиться в трех состояниях и при этом эффективно работать в режимах, пригодных для построения процессоров. Но для эмулятора это не проблема. Более того, схемы составных троичных элементов известны. Если прикинуть, сколько транзисторов в современных процессорах реально отвечают за систему команд, а сколько за оптимизации, то получится, что реализация самого троичного процессора не такая уж проблема.
+--. Железо
Для начала опишем память. Это довольно просто, память это просто массив трайтов. Мы дополним ее только одной функцией в виде дополнительного класса — возможность читать целые слова данных.
Дополнительно, для памяти опишем MMU, устройство для управления доступом к различным областям памяти. Наше MMU простое, оно позволит подключиться к некоторым ячейкам памяти как к пинам ввода/вывода, а так же позволит использовать отрицательные адреса для доступа к этим пинам из исполняемых программ.
Для процессора я использовал асинхронные возможности языка Dart. Каждый цикл процессора планируется на будущее и исполняется асинхронно. При этом я все же схитрил и ускорил исполнение, увеличив тактовую частоту в 100 раз. Получился своеобразный разгон. Итак, основная активность процессора происходит в методе next().
Пришло время разработать систему команд процессора. Как я уже говорил, я основывался на материалах проекта Оберон 2013. Н. Вирт разработал простую систему команд для реализации своего RISC-процессора на ПЛИС. Я модернизировал эту систему команд для троичного кода. Двух- или трех-операндная арифметика, условные переходы, прямая и косвенная адресация памяти.
В процессоре будет 27 регистров общего назначения, дополнительный регистр PC будет обозначать адрес расположения следующей команды в памяти, регистр IR будет содержать текущую команду. Также присутствует дополнительный трит NZ, который будет содержать дополнительный результат выполнения операций над регистрами. Некоторые регистры общего назначения заберет себе система Оберон для размещения адресов возврата, вершины стека и т.д.
Как известно, процессоры RISC обычно используют отдельные команды для загрузки и выгрузки данных в оперативную память, а все операции проводят над регистрами и данными в них.
Итак алгоритм действий процессора такой — из памяти читается слово по адресу PC, значение записывается в IR и отправляется дешифратору команд, который отправляет сигналы тем или иным блокам на выполнение действий. Такие действия могут поменять значение регистра, при этом в регистр NZ записывается информация о том, является ли значение нулем или оно больше нуля. Вот так, одним тритом отвечают на два вопроса. В последствии этот трит может быть использован при исполнении инструкции условного перехода. В результате выполнения команды меняется состояние памяти в местах, которые исполняемый код считает переменными, меняется адрес перехода процессора на следующем шаге, итерация завершается. Завершение работы процессора происходит при переходе на -1 ячейку памяти, так как в ней записана команда с форматом — (-13).
Общение с внешним миром происходит с помощью записи в ячейку памяти с предустановленным адресом значения, которое обработает хост-исполнитель. Например, можно таким образом реализовать примитивную отладочную консоль.
Так как у нас веб-приложение, выведем эту консоль в аутентичном черном окошке с белыми буквами. Для этого воспользуемся готовым компонентом и возможностями стандартной библиотеки Dart по управлению веб-содержимым.
Почему был выбрана троичная логика?
Объяснение столь гениального решения достаточно простое - нужно было получить простое, не дорогое и эффективное решение. Брусенцов предлагает использовать в качестве логических элементов для математических вычислений ферритовые кольца, обладающие возможностью хранения трех своих состояний.
В голове сразу всплывает картинка из учебника по полупроводниковой технике, где показана система хранения информации на магнитных кольцах, через которые проходят по 3 провода.
Эта возможность как раз и легла во основу применяемой троичной логики, кроме того, что троичная логика хорошо подходит под мыслительный процесс человека.
"Сетунь" применяла троичную симметричную логику "-1", "0", "+1". За одно действие можно задать, к примеру, включение двигателя и направление вращения. В случае бинарной логики - это потребовало бы два действия.
Меньше разрядов
(Написано разжевано, чтобы каждый смог понять суть этого пункта)
Возьмем число 10 в десятичной СС и переведем его в двоичную СС, получим 1010, переведем в троичную симметричную СС, получим +0+, ну а если в троичную несимметричную СС, то получим 101. Из этого мы видим, что в некоторых числах в троичной симметричной и несимметричной СС-ах меньше разрядов, чем в двоичной СС.
Возьмем число 5 в десятичной СС и переведем его в двоичную СС, получим 101, переведем в троичную симметричную СС, то получим +--, ну а если в троичную несимметричную СС, то получим 12. Из этого мы видим, что в некоторых числах в троичной несимметричной СС меньше разрядов, чем в двоичной и троичной симметричной СС-ах.
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 тритов, но при этом понадобится вдвое больше триггеров для такого регистра.
Дополнительным типом нашей математической подсистемы будет тип Trits, это аналог типа SET в Обероне. Типу SET посвящена отдельная статья Н. Вирта, где он называет тип SET недооцененным. Мы же оценим его по достоинству.
Если кратко, то тип Trits (SET) представляет собой множество тритов. Он свободно конвертируем в целое число, но к типу Trits применимы все базовые операции над множествами, сложение, умножение и так далее. Поддержка данного типа упростит реализацию обработки некоторых инструкций в процессоре. А еще он поможет преобразовать троичное число в строку.
Кроме троичной записи чисел символами -/0/+ существует также девятеричная форма записи троичных чисел, в ней символами являются ZXYW01234. Реализуем конвертеры для такой записи чисел.
В качестве развлечения, не связанного с основной задачей — реализуем конвертер в троичную симметричную систему счисления с иррациональным основанием.
Основанием выберем квадрат золотого сечения. Подобная система счисления называется фибоначчиевой. У нее есть интересное свойство — запись числа симметрична относительно ее нулевого разряда.
Пример всех конвертеров в одной картинке.
Проведем несколько тестов. Математическая подсистема готова.
Возможно ли сегодня возрождение компьютеров на троичной логике?
Да, возможна. Но, есть неоспоримо несколько моментов в этом:
1. наличие комплектующих для производства таких компьютеров
2. наличие ощутимых задач, которые могли существенно повысить производительность существующих решений (расчетов)
3. наличие специалистов, готовых применять троичную логику в своих разработках
И если с п.1 - уже сегодня ряд производителей готовы наладить выпуск электронных компонентов с троичной и более логикой, то вот с п.2 и, тем более, п.3 не все так однозначно. Проблема в засевшей очень глубоко бинарной логике наших специалистов. В вузах нет преподавания иной логики и "Закон исключения третьего" по прежнему является основой основ. Задачи на сегодня уже есть, - это и обработка изображений и биотехнологии и генная инженерия, где существует как двоичная так и троичная логика. Удивительным свойством переплетаются в кодировании аминокислот двоичное противопоставление Цитозин (Ц) - Гуанин (Г), Аденин (А) - Тимин (Т) и триплетов, кодирующих 21 аминокислоту.
Что же такое бинарный код?
На сегодняшний день компьютер способен понимать лишь специфичный для него язык. В основе такого языка лежит бинарный машинный код. Данный код представляет из себя последовательность битовых чисел 0 и 1 (отсюда название бинарный – значит двоичный – состоит из двух цифр) . Пример кода, 0010111010001011. Любая команда, обрабатываемая процессором компьютера, кодируется двоичным кодовым числом. Такая команда является примитивной с точки зрения пользователя, так как в отдельности команда не может решить хоть какую-нибудь простую его задачу. Например, доступ к ячейке данных, инициация прерывания, обновление регистра процессора… Пользовательские же команды такие, как движение мышки по столу, сохранение документа на диске, просмотр флэш-баннера и прочие разбиваются на миллионы мелких примитивных операций для выполнения процессором.
Есть также известное понятие – разрядность машины. Многие не в курсе что это такое. А это как раз вытекает из бинарного кода. Машина обрабатывает банарный код определнеными порциями, которые именуются «словом» . Как раз длина этого слова соответствует разрядности самой машины.
Почему именно бинарный код использует компьютер?
Двоичный (бинарный) код используется во всех цифровых устройствах за счет простоты и надежности. Двоичная арифметика довольно простая и ее нетрудно реализовать на аппаратном уровне. Компоненты электронных схем надежнее, если они основаны на понятиях «есть ток» и «нет тока» . В цифровой технике одному двоичному коду сопоставлен один логический компонент (элемент) схемы, способный находиться в двух состояниях: пропускать ток по схеме или нет. Примером наиболее простого подобного элемента является двоичный триггер — устройство-переключатель с двумя стабильными рабочими состояниями.
Как же преобразовать пользовательские команды в бинарные?
Машинный бинарный код совершенно непонятен человеку. Такое утверждение заставляет задуматься о том, какой популярностью еще в 60-е годы пользовались компьютерные гуру. На сегодняшний день машинный бинарный код просто-напросто не актуален программисту благодаря тому, что человечество изобрело массу новых языков программирования. Именно языки программирования осуществляют взаимодействие между человеком и компьютером. Суть языка программирования состоит в том, что человек разрабатывает программу для машины на языке, оперирующем естественными широкими функциями, как, например, записать текст в файл, вычислить синус числа и прочие, а затем с помощью специальных программ — компиляторов — происходит преобразование высокоуровневого человеческого языка в в различные виды машинных бинарных команд.
Однажды я прочитал в интернете про троичную систему счисления и заинтересовался. Меня мучил вопрос, а нельзя использовать в основе компьютера симметричную троичную систему счисления (СС), и даже вдруг это увеличит производительность компьютера? Мне казалось, что это возможно, и я жаждал это проверить.
Информация:
Троичная система счисления — позиционная система счисления с целочисленным основанием, равным 3. Существует в двух вариантах: несимметричная и симметричная.
В несимметричной троичной системе счисления чаще применяются цифры , а в симметричной троичной системе счисления знаки , .
У некоторых людей эта логика вызывает затруднения. Они говорят, например, приведите пример подобной логики в жизни.
Человек, немного подумавший над этой логикой поймет, что она более жизненна чем двоичная. Обычный пример троичной логики в жизни связан с постоянным током: ток движется в одну сторону, в другую сторону, его нет.
Оказалось, что симметричная троичная система счисления использовалась давным-давно для решения «задачи о гирях», использовалась в компьютере Сетунь, построенном в 50-е годы в МГУ. С 2008 года в университете « California Polytechnic State University of San Luis Obispo» функционирует цифровая компьютерная система TCA2, основанная на троичной системе счисления.
В чем же плюсы троичной СС над двоичной? Рассмотрим эти плюсы:
Не все так просто
Давайте разберем историю появления и забвения компьютеров "Сетунь", поскольку это ближе к нам, и, возможно, - это еще одно не признанное гениальное изобретение и заслуга наших советских конструкторов.
"Сетунь" создавался в 1954-1955 годах, когда уже были работающие компьютеры на бинарной логике. Руководитель разработки Николай Петрович Брусенцов получил задание разработать свой компьютер, когда для МГУ было отказано в поставке компьютера М-2. Это сегодня кажется нереальным с нуля создать свой компьютер, со своей архитектурой, машинными командами, системой хранения, ввода-вывода и программным обеспечением. Но, на тот момент, как говорится "Сказано - сделано". Работающий прототип появился в очень короткий срок - уже через 20 дней с момента старта команда из 12 человек смогла предоставить свой первый "Сетунь" на троичной архитектуре с 24 машинными командами. Конструкторские работы длились еще 3 года, прежде чем в в 1959 году было начато мелкосерийное производство компьютеров "Сетунь". Цена компьютера "Сетунь" была примерно в 20 раз меньше, чем существующие на тот момент компьютеры и предназначались для учебных заведений и конструкторских бюро.
Экономичность системы счисления
Экономичность системы счисления — запас чисел, который можно записать в данной системе с помощью определенного количества знаков. Чем больше запас тем экономичнее система. По затратам числа знаков (в трёхразрядном десятичном числе 3*10=30 знаков) наиболее экономична из позиционных показательных несимметричных систем счисления. Обозначим p основание системы счисления, n количество требуемых знаков. Тогда получим n/p разрядов требуемых для записи этого набора знаков в заданной системе счисления, а количество чисел которое при этом можно записать будет равно pn/p.
Мы рассмотрели троичную арифметику, теперь затронем логику:
В чем же проблемы двоичной логики?
1.Мощности компьютера, основанного на двоичной логике, не всегда хватает. Приведем пример. Одна из наиболее сложных систем защиты – криптосистема RSA. Вскрытие шифра RSA с длиной ключа 1024 бита (такая длина часто используется в информационных системах) займет в лучшем случае — при проведении распределенных вычислений на тысячах мощных ПК — не менее пятнадцати лет, а к тому времени данная система шифровки перестанет быть востребованной.
Докажем математически какая система счисления будет наилучшей для максимальной мощности и емкости памяти. Для этого рассмотрим функцию f(p)=p^(n/p), в которой p – основание системы счисления, а n – количество требуемых знаков. Тогда получим n/p разрядов требуемых для записи этого набора знаков в заданной системе счисления, а количество чисел, которое при этом можно записать, будет равно pn/p
f(p)=p^(n/p)
Для того, чтобы определить максимальное значение функции, найдем ее производную:
ln f = ln p^(n/p)
ln f =n/p* ln p
. (Я не буду приводить здесь всю математику)
n*p^(n/p-2) никогда не будет равно 0 => (1 — ln p)=0, ln p = 1, p = e
e = 2,71, а ближайшее целое число к нему – это три.
Значит, в этом плане лучшая система с целочисленным основанием — троичная.
Самое вкусненькое — рассмотрим троичные логические операции:
1.Отрицание
2.Конъюнкция — логическое И
3.Дизъюнкция — логическое ИЛИ
4.Операция Выбора. Эта операция существует только для троичной логики. Таблица истинности каждой из этих трёх операций содержит везде „-“, кроме единственного значения, которое ею можно выбрать.
5.Модификация. Полное название этих одноместных операций: увеличение на единицу по модулю три (INC) и уменьшение на единицу по модулю три (DEC). Увеличение на единицу по модулю три – это циклическое прибавление единицы.
Здесь видны и прежде знакомые вам логические операции из двоичной логики, но добавились и новые…
Квантовые компьютеры
Итог:
В конечном итоге видно, что троичная симметричная система лучше двоичной системы в некоторых показателях, но не сильно выигрывает. Но с пришествием квантовых компьютеров троичные вычисления получили новую жизнь. Универсальные квантовые логические вентили — краеугольный камень новорожденных квантовых вычислительных систем — требует сотни вентилей для завершения одной полезной операции. Квантовый компьютер канадской компании D-Wave, анонсированный в прошлом году, состоит всего из 16 квантовых битов — кубитов — минимум, необходимый для управляемого вентиля «NOT». Использование в квантовом компьютере кутритов нужно было бы намного меньше вентилей для завершения одной операции. Я думаю, если бы началось производство и тестирование таких компьютеров, то результаты были бы лучше, чем у обычных компьютеров, вскоре началось бы массовое их производство, и про двоичные компьютеры все бы забыли…
В 1959 году Н. П. Брусенцов разработал для МГУ уникальную вычислительную машину «Сетунь». Она была основана на троичной системе счисления и хотя элементная база была частично двоичной, что приводило к перерасходу деталей, машина зарекомендовала себя как экономичная и надёжная. Сегодня троичную машину можно увидеть разве что в музее, двоичный код победил.
Но, как я говорил ранее, всегда найдутся люди, готовые сохранять технологии прошлого в виде эмуляторов.
В этой статье рассматривается троичная симметричная система счисления. Цифры в ней положительные и отрицательные, то есть -1/0/1 или более общепринятое -/0/+. Из этого свойства вытекает нативная поддержка нашим будущим компьютером отрицательных чисел.
Есть еще пара аргументов в защиту троичной системы счисления и троичной логики. Экономичность хранения данных для каждого разряда очевидна, экономия линий в шинах, большая емкость привычных типов данных.
Существует формула y = ln(x)/x, физический смысл которой я понимаю как «соотношение объема хранимой информации к сложности ее хранения», где сложность возрастает по оси X.
Главным же недостатком считается отсутствие базового элемента, который способен находиться в трех состояниях и при этом эффективно работать в режимах, пригодных для построения процессоров. Но для эмулятора это не проблема. Более того, схемы составных троичных элементов известны. Если прикинуть, сколько транзисторов в современных процессорах реально отвечают за систему команд, а сколько за оптимизации, то получится, что реализация самого троичного процессора не такая уж проблема.
О работе Н. П. Брусенцова я узнал сравнительно недавно. Изучив некоторые материалы по Сетуни я понял, что нет необходимости проделывать весь путь заново и можно использовать знания наших дней. Насколько я знаю, троичная виртуальная машина была так же разработана в МГУ. Но материалов по ней мало, а исходников вообще нет.
Как раз в этот момент Н. Вирт опубликовал первые наработки проекта Оберон 2013.
Собственная система команд RISC-подобного процессора, простой язык и простой компилятор для него натолкнули меня на мысль о том, что неплохо бы соединить концепции двух умных людей в одну.
Так и родился проект TRISC, троичный RISC, в рамках которого были реализованы виртуальная машина и компилятор языка Оберон в троичный код. Так же в рамках этого проекта был реализован симулятор логических троичных вентилей, но об этом в другой раз.
Проект был доведен до стадии альфы и заморожен. И вот в 2015 году в процессе изучения языка Dart возникла идея реализовать порт эмулятора для браузера.
Нетипичный для веба проект, много странных целей, что может быть интереснее?
Так как компилятор в троичный код уже работал, то и троичный код у меня был. Поэтому главной целью проекта является построение эмулятора процессора. Чтобы задача не свелась к примитивному набору свичей, допустим, что виртуальная машина должна быть контролируемой, асинхронной, чтобы страничка не застыла — это же веб.
Так же, ради интереса, можно использовать собственные типы данных, которые будут характерны для троичных машин, а сам процессор реализовать в виде отдельных модулей, примерно соответствующих реальным блокам процессора — регистры, АЛУ и т.д. Плюсом будет использование множества фич Dart, ведь проект нужен для самообучения.
Перед глазами имеется оригинальный интерпретатор, с алгоритмикой особых проблем возникнуть не должно.
Для начала реализуем логику и математику. Сразу интересно.
Основной логический тип троичной системы — 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 тритов, но при этом понадобится вдвое больше триггеров для такого регистра.
Дополнительным типом нашей математической подсистемы будет тип 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).
Общение с внешним миром происходит с помощью записи в ячейку памяти с предустановленным адресом значения, которое обработает хост-исполнитель. Например, можно таким образом реализовать примитивную отладочную консоль.
Так как у нас веб-приложение, выведем эту консоль в аутентичном черном окошке с белыми буквами. Для этого воспользуемся готовым компонентом и возможностями стандартной библиотеки Dart по управлению веб-содержимым.
Так как код из рабочей виртуальной машины у меня уже был, коротко опишу особенности его исполнения.
Итак, для прошивки в память готового кода опишем класс-загрузчик, котовый будет загружать код с сервера и записывать его в память. Код в формате JSON, странно, но факт, ведь любой бинарный формат записи был бы не совсем совместим с троичным кодом.
По канонам системы Оберон, загрузчик выполняет модификацию адресов перехода, простая математика вносит в код поправку на смещение кода загружаемого модуля относительно нулевой позиции, которую задает компилятор при компиляции.
Отдельным модулем идет bootstrap, это несколько команд, которые установят в памяти константы машины (размер памяти, адрес таблицы модулей и др.) и переведет процессор на адрес первой исполняемой команды. Bootstrap был подготовлен вручную.
Модуль Core создан по образу и подобию ядра системы Оберон, модулю Kernel, так как это ядро, в нем много прямых операций с памятью, реализация аллокатора динамических структур (глючит иногда) реализация перехватчика исключений и т.д,
Как раз в модуле Core реализуем самую примитивную консоль. Для вывода строк и чисел будем записывать значения символов в ячейку памяти, как было описано выше. Платформозависимый модуль SYSTEM является виртуальным, его вызовы компилятор переводит непосредственно в машкод.
Невыразительный скриншот.
Проверить работоспособность получившейся виртуальной машины можно вот здесь. Конечно, комплексная отладка и процессора и компилятора одновременно привела к некоторым багам (которые я еще не нашел), но как proof of concept результат работы мне показался достаточным.
В итоге мы получили вполне работоспособный, расширяемый во все стороны аналог процессора Н. Вирта из проекта Оберон 2013 с модификацией для троичной системы счисления и троичного кода и несколько модулей для работы в получившейся системе.
В оригинальном интерпретаторе я предпринял попытку развить успех и реализовать общение с внешним миром по аналогу порта rs232, с файловой системой на основе протокола 9p. И вот с чем я столкнулся. И та и другая технология, хоть и декларируются кроссплатформенными, при вводе в понятие платформы тритов и трайтов стремительно теряют свою кроссплатформенность. Основа в виде байтов и битов делает портирование таких технологий нетривиальной задачей.
Конечно, здесь можно возразить, что значимость и распространенность троичных систем равна нулю, но тут как в анекдоте про Вовочку, троичность есть, а слов про кроссплатформенность для нее нет. Возможно это является некоторым тормозом в распространении троичных систем. Ведь все и так работает.
Лично я увидел только одно оправданное применение троичных машин — это организация защищенных от вторжений каналов связи. Ведь даже при наличии прямого доступа к каналу хакеру потребуется как минимум аппаратный дешифратор сигналов, который еще надо разработать. Таким образом, борьба брони и снаряда может дать жизнь промышленному применению описанных технологий.
В 1959 году Н. П. Брусенцов разработал для МГУ уникальную вычислительную машину «Сетунь». Она была основана на троичной системе счисления и хотя элементная база была частично двоичной, что приводило к перерасходу деталей, машина зарекомендовала себя как экономичная и надёжная. Сегодня троичную машину можно увидеть разве что в музее, двоичный код победил.
Но, как я говорил ранее , всегда найдутся люди, готовые сохранять технологии прошлого в виде эмуляторов.
+-0. Первые шаги
Так как код из рабочей виртуальной машины у меня уже был, коротко опишу особенности его исполнения.
Итак, для прошивки в память готового кода опишем класс-загрузчик, котовый будет загружать код с сервера и записывать его в память. Код в формате JSON, странно, но факт, ведь любой бинарный формат записи был бы не совсем совместим с троичным кодом.
По канонам системы Оберон, загрузчик выполняет модификацию адресов перехода, простая математика вносит в код поправку на смещение кода загружаемого модуля относительно нулевой позиции, которую задает компилятор при компиляции.
Отдельным модулем идет bootstrap, это несколько команд, которые установят в памяти константы машины (размер памяти, адрес таблицы модулей и др.) и переведет процессор на адрес первой исполняемой команды. Bootstrap был подготовлен вручную.
Модуль Core создан по образу и подобию ядра системы Оберон, модулю Kernel, так как это ядро, в нем много прямых операций с памятью, реализация аллокатора динамических структур (глючит иногда) реализация перехватчика исключений и т.д,
Как раз в модуле Core реализуем самую примитивную консоль. Для вывода строк и чисел будем записывать значения символов в ячейку памяти, как было описано выше. Платформозависимый модуль SYSTEM является виртуальным, его вызовы компилятор переводит непосредственно в машкод.
Не все так просто
Давайте разберем историю появления и забвения компьютеров "Сетунь", поскольку это ближе к нам, и, возможно, - это еще одно не признанное гениальное изобретение и заслуга наших советских конструкторов.
"Сетунь" создавался в 1954-1955 годах, когда уже были работающие компьютеры на бинарной логике. Руководитель разработки Николай Петрович Брусенцов получил задание разработать свой компьютер, когда для МГУ было отказано в поставке компьютера М-2. Это сегодня кажется нереальным с нуля создать свой компьютер, со своей архитектурой, машинными командами, системой хранения, ввода-вывода и программным обеспечением. Но, на тот момент, как говорится "Сказано - сделано". Работающий прототип появился в очень короткий срок - уже через 20 дней с момента старта команда из 12 человек смогла предоставить свой первый "Сетунь" на троичной архитектуре с 24 машинными командами. Конструкторские работы длились еще 3 года, прежде чем в в 1959 году было начато мелкосерийное производство компьютеров "Сетунь". Цена компьютера "Сетунь" была примерно в 20 раз меньше, чем существующие на тот момент компьютеры и предназначались для учебных заведений и конструкторских бюро.
0+0. Цели и средства
Так как компилятор в троичный код уже работал, то и троичный код у меня был. Поэтому главной целью проекта является построение эмулятора процессора. Чтобы задача не свелась к примитивному набору свичей, допустим, что виртуальная машина должна быть контролируемой, асинхронной, чтобы страничка не застыла — это же веб.
Так же, ради интереса, можно использовать собственные типы данных, которые будут характерны для троичных машин, а сам процессор реализовать в виде отдельных модулей, примерно соответствующих реальным блокам процессора — регистры, АЛУ и т.д. Плюсом будет использование множества фич Dart, ведь проект нужен для самообучения.
Перед глазами имеется оригинальный интерпретатор, с алгоритмикой особых проблем возникнуть не должно.
Взлет и падение
В интервью с Брусенцововым, его сравнивают с другимми успешными компьютерными руководителями, такими как Стив Джобс. Но это сравнение на мой взгляд совершенно не корректное. Почему так? Полагаю, что это сравнение в корне не верное, и так же являющееся одной из причин неудачного старта производства Сетунь.я, не желающих поддерживать это новое направление, всячески препятствуя какому-либо развитию. В конечном итоге был выпущено всего 50 компьютеров Сетунь и была создана в единичном экземпляре Сетунь-70 - версия более совершенная по сравнению со своим предшественником, но увы так и не принятого для производства.
В интервью с Брусенцововым, его сравнивают с другим успешными компьютерными руководителями, такими как Стив Джобс. Но это сравнение на мой взгляд совершенно не корректное. Почему так? Полагаю, что это сравнение в корне не верное, и так же являющееся одной из причин неудачного старта производства Сетунь.
В СССР Брусенцов делает разработку на заказ, полностью полагаясь на единственного потребителя и финансиста своих разработок - это государство, в лице министерства образования, никак не пытаясь уйти от этого, создать коммерческое предприятие. При такой себестоимости он мог прекрасно продавать свои компьютеры по цене рынка, зарабатывая в прибыли 400-700%. Но этого не произошло. Не было в стране конструкторских бюро компьютерных систем по аналогии с КБ самолетостроения или ракетной техники, которые в первую очередь финансировались для создания военной техники и уже потом как гражданского назначения. Судьба такого государственного сотрудничества на 99% зависит от политических интриг и никак от гениальности разработчика.
Читайте также: