Программирование троичного вычислителя: играем с эмулятором

    Как я и говорил, я потихоньку строю очень простой, но функциональный и при этом бескомпромиссно троичный вычислитель, основанный на сбалансированной троичной системе счисления. В этой статье я описываю эмулятор моего вычислителя, который мне поможет в отладке железа. Если вам интересно, не стесняйтесь писать под него программы, я их обязательно запущу на настоящем железе как только оно будет готово! Это очень просто, Триадор понимает обычный очень примитивный императивный язык, схожий с ассемблером или brainfuck :)



    — Жуткий кошмар! Нули и единицы повсюду. И кажется, я видел двойку.
    — Это просто сон, Бендер. Двоек не бывает.

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



    Описание архитектуры


    Триадор имеет трёхтритную архитектуру, это означает что его регистры могут хранить целые числа от -13 до +13. Он имеет четыре основых регистра R1-R4 и девять дополнительных регистров R5-R13. Обратите внимание, что R13 — это регистр специального назначения, он используется для выбора сегмента памяти программ (подробнее об этом ниже). Таким образом, Триадор может хранить в своей памяти 13 целых чисел из диапазона [-13..+13]. В дополнение к этому, он несёт на себе однотритный флаг переполнения/переноса и шеститритный счётчик команд. Доступная только для чтения память программ состоит из 27 сегментов по 27 инструкций каждый. Таким образом, максимальный объём программы для Триадора составляет 729 инструкций. Вот краткое описание архитектуры Триадора:





    Набор инструкций


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


    Триадор понимает 9 команд простейшего императивного языка, каждая инструкция сопровождается обязательным трёхтритным аргументом. Обратите внимание, что инструкция расширения EX ttt на данный момент интерпретируется как halt and catch fire. Вот полный список доступных команд:





    Компиляция интерпретатора


    git clone https://github.com/ssloy/triador.git
    cd triador
    mkdir build
    cd build
    cmake ..
    make
    ./triador ../prog/add.txt

    Вы также можете открыть проект в гитподе:


    Open in Gitpod


    По открытии, редактор скомпилирует и выполнит программу на одном из примеров. Просто меняйте текст примера в редакторе и перезапускайте программу (используйте историю команд из терминала).




    Спецификация файла программ


    Файл с программой обязан содержать одну инструкцию на каждой строке. Инструкция обязана состоять из шести символов и находиться в начале строки. Все символы после шестого игнорируются. То есть, начало каждой строки должно содержать одну из следующих инструкций, где ttt означает трёхтритное число от NNN (-13) до PPP (+13):


    • EX ttt
    • JP ttt
    • SK ttt
    • OP ttt
    • RR ttt
    • R1 ttt
    • R2 ttt
    • R3 ttt
    • R4 ttt

    Интерпретатор выдаёт на экран полное состояние Триадора для каждого этапа вычислений.




    Примеры программ


    Обратите внимание, что Триадор не имеет интерфейсов типа мышки или даже клавиатуры. Для того, чтобы ввести данные в вычислитель, нужно использовать команды R1-R4.


    Сложение


    Итак, я хочу сложить два числа, записанные в регистры R2 и R3. Но Триадор не умеет складывать числа! Он умеет делать инкремент/декремент. Насколько это страшно? Да ничуть!


    Давайте для начала напишем простейшую программу в знакомой вам обстановке. Я для начала предполагаю, что R2 и R3 неотрицательны. Если я у меня есть операция инкремента/декремента, то мне вполне хватит декрементировать R2 и инкрементировать R3 одновременно до тех пор, пока R2 не достигнет нуля:


    int main() {
        unsigned int R2 = 2;
        unsigned int R3 = 11;
        while (R2!=0) {
            R3++;
            R2--;
        }
        return R3;
    }

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


    int main() {
        int R2 = -2;
        int R3 = 13;
        while (R2!=0) {
            if (R2>0) R3++;
            if (R2<0) R3--;
            if (R2>0) R2--;
            if (R2<0) R2++;
        }
        return R3;
    }

    Ну, собственно, и всё. А теперь переходим непосредственно к Триадору. Добавим последний штрих: Триадор умеет инкрементировать/декрементировать исключительно регистр R1. Ну и ладно, если мы захотим прибавить к R3 единицу, скопируем его в R1, вызовем команду инкремента, и скопируем R1 назад в R3!


    Вот очень простая программа, которая пишет два числа в регистры R2 и R3 и вычисляет их сумму. Результат хранится в R3:



    Левый столбец (первые шесть символов каждой строки) — это непосредственно программа для Триадора. Счётчик команд инициализирован как NNN NNN, что равно -364 в десятичной системе и соответствует первой строке нашего файла программы. Отметим, что все символы после шестого игнорируются интерпретатором, можно считать, что это комментарии.


    Вот лог запуска нашей программы:


    $ ./triador ../prog/add.txt | tail -n 3
     R1  R2  R3  R4  R5  R6  R7  R8  R9 R10 R11 R12 R13  C   PC
     11   0  11   5   0   6 -12  -2  11   8  11 -10 -13  0  -345

    Обратите внимание, что R3 содержит 11, результат операции -2 + 13.


    Разумеется, Триадор не поддерживает циклы типа while напрямую, он использует безусловные джампы, JP, ну а ветвление обеспечивается при помощи операции SK, которая позволяет пропустить следующую за ней операцию.


    Тонкий момент: обратите внимание, что команда безусловного джампа JP ttt имеет трёхтритный аргумент ttt, в то время как программный счётчик у нас шеститритный. Откуда берутся недостатющие три трита? Из регистра R13! Команда JP ttt перепрыгивает на инструкцию номер 27*R13 + ttt. Иными словами, перепрыгивает на команду номер ttt сегмента с номером, взятым из регистра R13. Самый первый сегмент памяти команд имеет номер NNN (-13), и именно поэтому первые две строчки моей программы выглядят как


    R1 NNN # write -13 to R1
    RR NNN # copy R1 to R13

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




    Сложение с контролем переполнения


    Предыдущий код складывает два трёхтритных числа, но ведь сумма двух трёхтритных чисел может не влезть в три трита памяти. Поэтому давайте напишем программу, которая складывает два трёхтритных числа, но результат будет шеститритным. Следующая программа складывает регистры R2 и R3, и записывает результат в регистры R3 и R4: результат равен R3 + R4*27, то есть, R4 может быть равен -1, 0 or 1.



    $ ./triador ../prog/add-with-overflow-control.txt |tail -n 3
     R1  R2  R3  R4  R5  R6  R7  R8  R9 R10 R11 R12 R13  C   PC
    -12   0 -12   1  -9   2 -12  -6   4   5   6   7 -13  0  -338

    Обратите внимание, что R3 + 27 * R4 равно 15, результату операции 2+13. По сравнению с предыдущей программой я всего-навсего добавил запись в регистр R4 флага переполнения C:


    [...]
    SK OOO # skip if C==0        
    JP OPO # overflow ───────┐   
    JP PNO # no overflow ────│─┐ 
    R4 OOP # write 1 to R4 <─┘ │ 
    SK OOP # skip if C==1      │ 
    R4 OON # write -1 to R4    │ 
    RR OPN # copy R2 to R1 <───┘ 
    [...]



    Шеститритное сложение


    Вам кажется, что регистры с диапазоном [-13..+13] недостаточно экспрессивны? Никаких проблем, давайте введём тип данных word (на самом деле, мы его уже ввели в предыдущем примере). Эта программа записывает одно шеститритное число в регистры R1,R2 и другое в регистры R3,R4. Затем считает сумму, сохраняя в шеститритном числе R4,R5.



    $ ./triador ../prog/long-add.txt |tail -n 3
     R1  R2  R3  R4  R5  R6  R7  R8  R9 R10 R11 R12 R13  C   PC
      3   0   0  -6   3 -13   1   3   6   5  13  -2 -13  0  -335

    Обратите внимание, что R4+27 * R5 = 75, а мы попросили наш вычислитель посчитать 331-256. Надо ли объяснять, как работает этот код? Если вы разобрались с предыдущими двумя, думаю, ни к чему. Мы считаем сумму двух старших полуслов, затем сумму младших полуслов. Если при суммировании младших полуслов произошло переполнение, нужно добавить или отнять единицу от суммы старших полуслов. Если все эти слова трудно понимать, смотрите эквивалентный код на C++ :)


    В этом коде только одна тонкость: поскольку мне дважды нужно считать сумму двух трёхтритных чисел, я пытаюсь сымитировать вызов функции. Триадор не знает стеков, триадор не знает сабрутин и адресов возврата. Но мы тоже не лыком шиты! Регистр R7 контролирует, в какое место кода нужно возвратиться из этой эрзац-сабрутины. Если очень грубо, то я храню в регистре R7 адрес возврата из функции:


    [...]
    SK ONO # skip if R1!=0
    JP OON # sub return 1
    JP POP # sub return 2



    Наибольший общий делитель


    Разумеется, наш набор примеров был бы неполон без Евклидова алгоритма. Эта программа вычисляет наибольший общий делитель чисел, записанных в регистры R2 и R3. Результат сохраняется в регистре R2.


    Давайте разберём, как она работает, для начала в привычном мире C++. Если мы предположим, что числа R2 и R3 положительны, то возможная имплементация алгоритма Евклида выглядит следующим образом:


    int main() {
        int R2 = 12, R3 = 8;
    
        while (true) {
            if (R2==R3) break;
            if (R2>R3)
                R2 = R2 - R3;
            else
                R3 = R3 - R2;
        }
    
        return R2;
    }

    Насколько всем очевидно, что эта программа вычисляет наибольший общий делитель? Начнём с того, что она точно останавливается: на каждой итерации мы обновляем либо R2, либо R3; одно из них обязательно уменьшается, оставаясь положительным. Если число m делит R2 и делит R3, как это делает наибольший общий делитель, то вполне очевидно, что оно же делит и разницу R2-R3. Если это неочевидно, то запишите R2 = a m, R3 = b m и убедитесь в том, что R2-R3 = (a-b) m. Как-то так.


    А что делать, если на вход мы можем получить числа со знаком? А просто взять от них модуль :) Посмотрите сами: этот код абсолютно эквивалентен предыдущему, если он на вход получит положительные числа. Ну а если отрицательные, то модуль нам поможет!


    int main() {
        int R2 = 12, R3 = -8;
    
        while (true) {
            if (R2<0) R2 = -R2;
            if (R3>0) R3 = -R3;
    
            if (R2==-R3) break;
    
            int R4 = R2 + R3;
            if (R4>0)
                R2 = R4;
            else
                R3 = R4;
        }
    
        return R2;
    }

    В итоге программа для Триадора работает именно по этому принципу:



    Вот лог исполнения программы:


    $ ./triador ../prog/gcd.txt |tail -n 3
     R1  R2  R3  R4  R5  R6  R7  R8  R9 R10 R11 R12 R13  C   PC
    -13   4  -4   0   4  12  13   1  -7  -9   3   4 -13  0  -338

    Обратите внимание, что R2 хранит 4, наибольший общий делитель 12 и -8.




    Заключение


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




    Stay tuned.
    Реклама
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее

    Комментарии 59

      +1
      Слушайте, я тут посмотрел, у меня слишком много приглашений на хабр. Если у вас положительная карма, ни одной публикации, но вы молодец и хотите инвайт, пишите в эту ветку. Я выдам минимум PNO инвайтов.
        0
        Если так можно, давайте.
        Считаю тему с троичными вычислениями очень интересной. Жду продолжения. Спасибо за статью.
          +1
          У вас она нулевая, а не положительная. Но это мы быстро исправим.

          UPD: Но ведь у вас же уже есть инвайт?
          Приглашён
          28 января 2019 в 18:30 по приглашению пользователя Zaphy


            0
            Я просто хочу голосовать за интересные статьи. А мне сайт не позволяет. Перепутал эту возможность с инвайтом. Простите.
              +1
              Нужно +5 кармы. Я проголосовал, вы на правильном пути. Но сразу +5 я дать не могу, извините.
                0
                А если в р/о пользователь — выше 4 карма не поднимается.
                Так что пятерку добавить без инвайта не получится.
                  0
                  Похоже, что дело уже не в инвайте, а в наличии статей, хотя могу ошибаться, у хабра роботы ломаются часто.
                    0
                    > User without posts can't have more than +4 karma
                  0
                  Ого, а у вас уже +4. Сообщество тут отличное, вас оценило. Похоже, теперь нужна статья, чтобы получить возможность подняться до +5 и выше.
              0
              Можно мне тоже?
                0
                Инвайт номер OPN ушёл.
              0
              тоже прошу инвайт
                0
                инвайт номер OPO ушёл.
                  0
                  Спасибо!
                0
                Могу получить инвайт?
                  0
                  инвайт номер PNP ушёл
                  +1
                  День добрый, интересная статья, только из статьи не понял какие преимущества дает троичная архитектура по сравнению с классической. Помню из лекций что оптимальной системой счисления является та что по основанию e, и что троичная сс ближе к 2,718 чем двоичная, но какие у нее реальные преимущества?

                  Не отказался бы от инвайта, давно хочу захабриться, но даже незнаю с какой стороны подступиться. Насколько я понял без публикации никак?
                    0
                    Я раздал уже все инвайты, пардон. Держите просто плюс. Ну а на тему оптимальности тут есть уже пара топиков.
                      0
                      Вас понял, в любом случае выражаю благодарность :)

                      И тем не менее, если абстрагироваться от этого «оптимального» основания, есть ли то, что может дать троичная сс рядовому программисту? Если например предположить что все мэйнстримные процессоры вдруг станут троичными.

                  0
                  Можно мне, если еще остались?
                    0

                    На меня еще есть?)

                    0

                    Жду 0P0!

                      0
                      Приглашён
                      25 марта 2013 в 00:03 по приглашению НЛО

                      Вам инвайт не нужен, держите просто плюс.
                        0
                        Прямо раздача плюсов=)
                        А по теме, планируется ли развитие в унификацию команд — я например работаю пошагово с неким отечественным железом, но например скады других производителей и их железо позволяют работать с унифицированными блоками и классами операндов… Не то что бы это хорошо — отнимает кусок хлеба за счет упрощения работы, но и не плохо, т.к. в сложных проектах упрощает разработку…
                          0
                          Ой, я надеюсь, вы понимаете, что я не коммерческую железку разрабатываю. Максимум амбиций — реализовать Pong с осциллографом в режиме XY в качестве экрана. Держите плюс, у меня их много.
                            0
                            Да не в плюсах дело, просто работая напрямую с железкой, а особенно с троичной логикой, можно сделать много приятных вещей не извращаясь с командами=) Мне было обидно, что в своё время её забросили…
                              0
                              Я на эту тему уже высказался в другой ветке. Не вижу преимуществ для программиста. Для разработчика железа — дискутировать можно. Но для программиста…
                                0
                                .del
                                  0
                                  На самом деле, интересный вопрос. У меня система команд явно списана с двоичных аналогов. Самый простой (и единственный, приходящий мне в голову) — это ветвление не двоичное, а троичное, мне его изрядно не хватает в столь примитивной системе команд, вполне возможно, что я его введу в командах EX ttt.
                                    0
                                    В этом, на мой взгляд, и проблема троичной логики, что в ней нет четкого ветвления, но в этом и её огромный плюс=)
                                      0
                                      (испуганно) как это нет чёткого ветвления?! Я под троичным ветвлением подразумеваю условный джамп вида:

                                      if A<0 jump AAA;
                                      if A==0 jump BBB;
                                      if A>0 jump CCC;
                                        0
                                        ну а сравните конструкцию с вычислением в двоичной логике=)
                                          0
                                          В троичной логике ветвление как раз самое естественное. Автору троичного компьютера большой респект.
                      0
                      Если можно, давайте.
                      Где-то читал, что самая эффективная система счисления при основе эйлеровой константе е=2.71828
                      Самая близкаяа система не двоичная, а троичная…
                        +1
                        Инвайт номер OPP ушёл. А насчёт числа Непера… Про этот миф написано много где, только мало кто задумывается, что имелось в виду. Вы поймите, что эффективность измеряется в чём-то конкретном, в кубометрах дров в единицу времени, ну или в долларах на худой конец. А откуда взялась целевая функция из доказательства про ту эффективность, что вы цитируете? А с потолка. Я ровно так же могу любое другое основание системы счисления обосновать…
                          0

                          Всё дело в колёсиках. Если представить, что у нас механическая счётная машина. Каждое счётное колесо может находиться в одном из n положений, где n — основание системы. При этом условная трудоёмкость изготовления колеса линейно зависит от n, а общая цена машины — от цены колеса * число колёс.
                          Тогда для того, чтобы представить наибольшее число на наиболее дешёвой машине, нужно основание системы возможно более близкое к e.


                          Очевидно, что на другой элементной базе расклад может быть другой.


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

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

                              Замечательно. В условиях, когда зависимость нелинейная — оптимальное основание будет другим. В чём проблема?


                              Чем больше колёс, тем труднее это всё вращать, и поэтому колёса надо будет делать с меньшими допусками

                              Это зависит от конструкции. В частности, передачу разрядов целесообразно делать раздельной. Допуска колёс… только чтобы не давали ошибку соизмеримую с 1/n оборота.


                              утверждение про число Непера считаю голословным

                              А теорему Пифагора Вы тоже считаете голословной, на том основании, что её применимость ограничена Евклидовым пространством (а, как известно, соответствие реального пространства Евклидову — не доказано)?

                                0
                                Во-первых, не факт, что оптимум будет единым для всех типов вычислителей, это раз. А основная проблема не в оптимуме, а в том, что утверждение про число Непера взято с потолка и почему-то никем не рассматривается критически.
                                  0
                                  Во-первых, не факт, что оптимум будет единым для всех типов вычислителей, это раз.

                                  Это не утверждалось.


                                  а в том, что утверждение про число Непера взято с потолка и почему-то никем не рассматривается критически.

                                  А если я докажу?

                                    0
                                    Докажите, интересно! Но перед доказательством сформулируйте, пожалуйста, задачу, это вам сэкономит время.
                                      0

                                      Так я её уже сформулировал, если Вы не заметили.
                                      n — основание системы, m — разрядность машины;
                                      сложность машины линейно зависит от n*m.

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

                                          Тем не менее, вы не можете утверждать, что решение для этой модели — голословно.

                                            0
                                            Нет, конечно. Я согласен с тем, что число Непера это минимум оптимизационной задачи, не имеющей ни малейшего отношения к реальности (см. сферический конь в вакууме). Например, задачи argmin(x-e)^2

                                            Я не согласен с использованием этой оптимизационной задачи для обоснования превосходства троичной системы счисления над двоичной.
                        0
                        чем троичная арифметика лучше двоичной?
                          0
                          А кто сказал, что она лучше?
                            0
                            компактность по сравнению с двоичной. Ну и необычность.
                            0
                            Насколько планируете развивать данный проект? Перфокарты постоянная память будет? Я в качестве хобби проектирую свой компьютер (вот совпало), правда двоичный, а не троичный, так что интересно посмотреть, что у других получается.
                              0
                              Не, ПЗУ не будет (помимо памяти программ, выполненной джамперами). Собственно, в этом посте полное описание архитектуры.
                              0

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

                                0
                                Спасибо, я старался!
                                  0

                                  *левую сторону.
                                  И ведь даже не move и не load, а логичное copy! :)

                                  0
                                  Здо́рово! Планируете перевести систему с кучи плат на кристалл(ы)? Или это слишком дорого?
                                    0
                                    Я нет, а вот Shaos планирует заказать в виде троичной микросхемы. Причём он троичные микросхемы уже делал!
                                      0
                                      Угу — делал :)
                                      в 2015 году
                                      техпроцесс CMOS 0.5um
                                      троичный мультиплексор работает ;)

                                Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                Самое читаемое