Компьютерра PDA N151 (24.12.2011-30.12.2011)

А. Самсонов о троичной логике и цифровой археологии

Автор: Андрей Письменный

Опубликовано 29 декабря 2011 года

В шестидесятые годы прошлого столетия в СССР разрабатывали уникальные вычислительные машины "Сетунь". В отличие от обычных компьютеров, они оперировали данными по законам не двоичной, а троичной логики (подробности - в статье Евгения Лебеденко "Tertium Datur"). Хотя исправных троичных ЭВМ не осталось, идея, на которой они были основаны, настолько интересна и необычна, что о "Сетуни" помнят до сих пор.

Александр Самсонов не застал тех времён, но увлекается троичной логикой сегодня. В свободное время он собирает и систематизирует информацию о троичных компьютерах и троичной логике. Помимо этого, он координирует группу, работающую над программным эмулятором "Сетуни-70".

- Как вы наткнулись на эту тему?

- Совершенно случайно. Году в 1998 читал журнал American Scientist, и там была статья о троичной неуравновешенной системе исчисления. Потом, если не ошибаюсь, троичная логика была упомянута во втором томе Дональда Кнута, и каким-то образом мне попалась статья о том, что существовала даже троичная ЭВМ. Я начал интересоваться, ходить по библиотекам, пытаться найти публикации, меня это захватило.

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

- И теперь вы пытаетесь организовать тех, кто интересуется троичной логикой?

- Всего заинтересованных - несколько десятков, но постоянно контактируют и чем-то занимаются человек пять. В России только один человек, все остальные из других стран - Штатов, Швеции и так далее. В Украинском Институте кибернетики серьёзно занимались этой темой, были публикации, патенты, какие-то схемы на уровне того времени. И у нас в Институте прикладной математики Варшавский занимался этим. Но он сконцентрировался на математике, а потом, с его отъездом, исследования прервались.

- Что представляла собой "Сетунь", и откуда она взялась?

- "Сетунь" - это первая и единственная в мире серийно производившаяся троичная вычислительная машина, которая относилась к классу малых. Её создали в лаборатории вычислительных систем МГУ. Работа началась в 1955 году, когда Николаю Петровичу Брусенцову дали задание ознакомиться с разрабатывающимися на то время ЭВМ, чтобы впоследствии приобрести одну их них для нужд университета.

- А Николай Петрович вместо этого сказал, что ему не нравится двоичная логика?

- Не совсем так. Его направили в одно из КБ, которое занималось созданием ЭВМ. Он с большим интересом наблюдал, каким образом производится машина, и обратил внимание на то, что некоторые элементы недостаточно оптимально используются, в частности память. Поскольку было много брака, приходилось устанавливать в два раза больше элементов.

- То есть в машины тогда сразу ставили запасные элементы на случай неисправности?

- Да, поскольку часть элементов была бракованная, то один из них мог сработать, а второй - нет. Так вот, через какое-то время из-за ссоры в верхах университету отказались продавать машину. Сказали: "Разбирайтесь сами, покупайте в другом месте". В итоге в МГУ её решили разработать собственными силами.

У Николая Петровича уже было представление о том, как это делается и что должно получиться. Он обратил внимание на бесполезное удвоение элементов и попробовал реализовать троичные элементы. В результате количество элементов сократилось в семь раз по сравнению с тем, что он видел в КБ. При поддержке академика Соболева решили попробовать реализовать многозначную, полностью троичную машину - "Сетунь".

Конструкторские работы продолжались до 1957 года, и в 1958-59 годах "Сетунь" была запущена. Машина получилась, во-первых, на удивление небольшой, во-вторых, дешёвой, что потом сыграло с ней злую шутку. К тому же она заметно отличалась от всех остальных ЭВМ того времени, поскольку была троичной. Тем не менее, когда опытный образец показали на ВДНХ, он получил приз. Пошли разговоры о серийном производстве. В 1960-61 году на Казанском заводе вычислительных машин начали собирать "Сетунь".

- Тогда и появились те самые пятьдесят экземпляров?

- Да. Их строили очень долго, не больше десяти штук в год. В основном "Сетунь" расходилась по небольшим инженерным КБ, бюро и университетам. Насколько мне известно, одна из них стояла в академии Жуковского в Москве: с её помощью учили программированию и вели расчёты.

- И писали для этого собственный софт?

- Да. В то время это было нормально. Каждый получал машину практически безо всего и самостоятельно решал свои задачи.

- Как примерно выглядел этот агрегат?

- Он был относительно невелик - занимал площадь небольшой комнаты. Четыре небольших шкафа и две стойки: на одной пульт с индикаторами, а на другой - электрическая пишущая машинка, с помощью которой происходил набор данных. Фактически что-то вроде терминала: вводишь текст, и на бумаге остается всё, что набрал.

- Возможно ли описать производительность "Сетуни" в современных терминах?

- В современных получается совсем уж скромно - порядка двадцати тысяч операций в секунду. В своё время она попадала в класс малых машин, не особо требовательных к скорости вычислений.

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

- Какие же преимущества давала троичная логика?

- Двоичная логика по своей сути представляет собой сильно урезанную формальную логику. Из-за своих ограничений она не позволяет произвести некоторые действия. Либо позволяет, но неэкономно, и придётся прилагать значительно больше сил. Впрочем, в первой "Сетуни" самой по себе троичной логики практически не было, а применялось в основном троичное представление данных. Логических же операций как таковых в системе команд, по-моему, не имелось вовсе.

- То есть это была исключительно счётная машина?

- Да, она создавалась именно для выполнения расчётов. А вот в первом варианте "Сетуни-70" уже были некоторые средства для выполнения логических операций.

- "Сетунь-70" начала разрабатываться сразу, как только первая "Сетунь" была закончена?

- Нет. В 1965 году был расцвет первой "Сетуни", когда она производилась, продавалась, поставлялась в университеты и КБ. Ближе к семидесятому году, к столетнему юбилею Ленина, всем институтам предлагали показать свои достижения. Коллектив Николая Петровича решил сделать следующую модель "Сетуни", тоже троичную. ЭВМ назвали "Сетунь-70". Работу начали в 1968 году. Сначала был сделан один вариант и нормально запущен, но потом пришла мысль чуть-чуть поменять архитектуру и лучше приспособить её для стекового программирования, которое сейчас больше известно как структурное. Идею структурного программирования предложил Дейкстра, и "Сетунь-70" прекрасно подошла для такого подхода.

- И после этого появился единственный опытный экземпляр?

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

- Были ли другие исследования, связанные с троичной логикой?

- В семидесятых годах, если не ошибаюсь, в Штатах была сделана попытка построить на большой двоичной ЭВМ эмулируемую троичную ЭВМ для того, чтобы оценить эффективность. По результатам работы опубликовали три документа: два из них можно найти в Сети, а третий неуловим - название книги есть, но найти её нереально. Известно, что выводы были положительными, но всё уперлось в то, что как раз тогда происходил переход на полупроводниковую элементную базу. Реализовать на транзисторах троичную логику гораздо сложнее. В принципе, это и мешает появлению троичных систем. Сейчас они если и существуют, то не распространены.

- Выходит, виноваты транзисторы?

- Да. При реализации троичной логики на транзисторах требуется больше элементов, и на первый взгляд кажется, что это не так эффективно. Но здесь вот какая особенность: чем больше троичных элементов добавляешь, тем меньше соединений требуется. К тому же в определённый момент количество элементов начинает расти нелинейно. Когда число элементов переваливает некоторый порог, для увеличения сложности троичного компьютера требуется всё меньше и меньше элементов. Там, где двоичному компьютеру приходится удваивать количество элементов, троичному достаточно увеличить количество элементов только в полтора раза, потом в 1,3 раза и так далее.

- Существуют ли троичные машины, сопоставимые с "Сетунью-70"?

- Насколько мне известно, нет. Алгоритмов же написано много. Есть множество патентов как на электронику, так и на алгоритмы, которые упоминают и применяют в той или иной степени как классическое троичное представление данных (то есть смещённое от нуля - "один" и "два"), так и уравновешенное - "минус один", "ноль", "плюс один". Но я не слышал, чтобы кто-то пытался их серьёзно применять на практике. Известно, что студенческие коллективы предпринимали попытки построить подобный компьютер в Штатах, во Франции и в Новой Зеландии. В Испании построили троичный процессор с небольшим количеством памяти, но сейчас о нём уже ничего не узнать, кроме названия. Это сделали лет восемь назад, были публикации, но потом всё это пропало.

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

- Зато у вас есть два эмулятора "Сетуни".

- Один есть и доступен уже года три. Он эмулирует первую "Сетунь", ту, которую разработали в 1959 году. Эмулятор интересно устроен - в виде веб-приложения: на страничку заходишь, там перед тобой фактически один в один модель панели той самой "Сетуни". Эмулятор называется "Сетунь ВС". Можно двигать переключатели и всякие ползунки, запускать машину на счёт, переключать режимы. Но для освоения придётся прочесть книжку (которая есть в интернете, кстати) "Малая цифровая вычислительная машина Сетунь".

Второй эмулятор - это уже попытка эмулировать "Сетунь-70". Пока он не подходит для посторонних: тот, кто знает, что делает, может собрать и запустить его, а все остальные, скорее всего, не разберутся. С помощью этого симулятора мы надеемся рано или поздно получить возможность запускать программы для "Сетуни-70", которые сохранились в распечатках, на перфолентах и в других источниках.

- Как я понимаю, сейчас вы восстанавливаете программу из ПЗУ?

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

- После этого можно будет получить готовую "Сетунь-70"?

- Можно будет запускать все доступные алгоритмы, но часть требует разных аппаратных устройств типа терминалов, информации о которых у нас нет. Поскольку "Сетунь-70" существовала в единственном экземпляре, для нее не так много программного обеспеченья, как для первой "Сетуни". Она использовалась по большей части для нужд МГУ.

- Как программировали "Сетунь-70"?

- У программистов "Сетуни-70" был достаточно развитый инструментарий. В нём имелся, по-моему, ассемблер даже и то ли транслятор Фортрана, то ли компилятор Алгола.

- В коде приходилось как-то учитывать троичность?

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

- Какие алгоритмы больше всего выигрывают от троичной логики? Обход бинарного дерева?

- Да, с ними троичные машины работают эффективнее, чем двоичные. В двоичном при обходе можно либо "попасть", либо "не попасть", а тут ты либо "перелетел", либо "попал", либо "не долетел". Так значительно проще понять, что делать дальше.

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

Плюс у уравновешенного троичного кода (его по-разному называют - уравновешенный, сбалансированный) есть преимущество: каждый разряд содержит знак того значения, которое содержится в этом разряде. В данном случае у нас минус один, ноль и плюс один. Для того чтобы выяснить, какой знак у всего числа, содержащегося в ячейке, достаточно взять первый ненулевой разряд и посмотреть, какой у него знак.

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

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

- Говорят ещё про удачное применение в механике, где троичный разряд описывает не только наличие тока, но и направление вращения ротора.

- Да, по своей природе уравновешенная троичная система исчисления позволяет обозначить одним разрядом не только включение и выключение мотора, но и включение со вращением в одну сторону и включение со вращением в другую сторону. Например, минус один - налево, плюс один - направо, ноль - не крутить вообще. Это удобнее, чем в двоичной системе, где сначала надо задать направление, а потом включить двигатель. На одно действие меньше.

- Если бы сегодня было возможно создать троичные процессоры, в какой области они пригодились бы?

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

- Сейчас очень актуален поиск и распознавание образов - в них троичная логика пригодилась бы?

- Да, именно там. В области обработки цифровых сигналов применяется знакоразрядная система, которая по сути своей эмулирует троичное представление просто на двоичных компонентах. Если будет готовое достаточно быстрое "железо", для того чтобы выполнять эти алгоритмы достаточно эффективно, то я думаю, именно троичная реализация окажется предпочтительнее.

- Со стороны это выглядит странно: с одной стороны, делается что-то новое, но речь в основном о старинном, давно не используемом компьютере. Кроме разработки эмулятора есть ли какие-то попытки сделать работающий троичный компьютер?

- Да, элементная база, к сожалению, осталась старая. Это большая проблема, а поиск новых компонентов, пригодных для этого, затруднён: единственное, что можно делать, - рассматривать большое количество элементов и пытаться понять, подходят они или нет. За несколько лет удалось подобрать только два элемента - операционные усилители, КМОП-ключи 403. И ещё некоторые оптические компоненты. На заказ сделать, конечно, можно, но кто будет этим заниматься? Если делать микросхемы, то нужно обращаться в Зеленоград и пытаться оформить какой-нибудь минимальный заказ, чтобы посмотреть. Это можно сделать, но бесплатно никто работать не станет, а будет ли дальнейшее развитие - неясно. К тому же процесс выпуска серии микросхем нас задержит на некоторое время.

- Есть ли шанс, что новые троичные компьютеры окажутся выгоднее обычных?

- Поначалу, конечно, нет. Придётся ведь всё разрабатывать с нуля, начиная с элементной базы. Чтобы это оправдалось, нужен большой прирост эффективности при обработке данных.

- Ну зато можно будет работать на реальном "железе". Или на современных двоичных процессорах эмуляция будет работать быстрее, чем машина на неких малотиражных элементах?

- Здесь вопрос доступности. Если ты выпускаешь элемент, тебе его нужно сначала получить, потом припаять. А эмулятор - собрал и запустил. Не нужно никаких дополнительных усилий для того, чтобы посмотреть, как всё работает.

- Но если вдруг появится какая-то элементная база, которая дает это естественным образом, сразу все старые наработки сразу пригодятся, так?

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

Читайте также:Tertium datur: другие компьютеры. Полвека назад на эволюционном древе вычислительной техники появилась особая ветвь - ЭВМ, в основе которых лежала логика, отличающаяся от двоичной. Их разработали в МГУ.

Полезные ссылки

• Основные русские ресурсы по изучению истории, разработке троичной вычислительной техники, алгоритмов и по троичной логике: ternarycomp.cs.msu.ru, ternary.info, trinary.ru

• История создания "Сетуни" и "Сетуни-70" в "Виртуальном компьютерном музее"

• Попытка создания аппаратной имитации троичной ЭВМ на двоичных компонентах (фактически программная имитация внутри широко распространённой модели микроконтроллера)

• Проект "Тунгуска" - интересное применение архитектурных принципов микропроцессора 6502 и компьютера "Commodore-64", но с использованием симметричного троичного кода

• Симулятор "Сетуни"