Не-фон неймановский компьютер на базе комбинаторной логики

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


    Примерно так работает дерево, только здесь для наглядности вычисляются арифметическое выражение, а не комбинаторное; шаг на рисунке — один такт машины.

    Сейчас готов ранний прототип, существующий как в виде потактового программного симулятора, так и в виде реализации на ПЛИС.

    Идеология


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

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

    //	простая арифметика на языке комбинаторной логики (классический способ представления)
    2+3 = + 2 3 = + ( +1 1 ) ( +1 1 1 ) =
    
               +        (      +1      1 ) (     +1          +1     1 )
    `` ``si`k`s``s`ksk     ``s``s`ksk  i    ``s``s`ksk  ``s``s`ksk  i
    

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

    Архитектура


    Основная идея — разместить дерево программы на аппаратном дереве ячеек, способных применять комбинаторы.
    Зачем аппаратное дерево? Дело в том, что когда мы проецируем дерево программы на привычное нам одномерное адресное пространство, неизбежно возникают нелокальные, «длинные» связи. Вот пример плоской записи древовидного выражения: "(A*B) + (C*D) — E" Здесь "+" является источником данных для "-", но в формуле они разнесены.



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

    где листья — элементарные функции, в случае комбинаторной логики это базовые комбинаторы, например, набор S, K, I:
    Ix   = Ix        = x         - тождественное отображение
    Kxy  = (Kx)y     = x         - конструктор констант
    Sxyz = ((Sx)y)z  = (xz)(yz)  - коннектор
    

    SKI на аппаратном дереве




    Синтаксис для ассемблера позаимствуем у эзотерического функционального языка программирования unlambda (как и было обещано в этой публикации, в самом конце):

    `ix     = Ix
    ``kxy   = (Kx)y
    ```sxyz = ((Sx)y)z
    

    Это решение позволяет использовать интерпретатор unlambda для проверки корректности вычислений.
    Здесь штрих (`) -символ применения функции. Используется префиксная запись, то есть `fx = f(x).
    F( G(X,Y), H(Z,V) ) = ``F``GXY``HZV
    Именно в такой форме выражение подаётся на вход машины. Загрузка происходит через корень дерева, внешнее устройство посимвольно передаёт программу корневому узлу, который первый символ забирает себе, а оставшуюся часть передаёт своим потомкам, каждый из которых выполняет процедуру загрузки рекурсивно. Получив поддерево полностью, узел сообщает об этом предку и начинает выполнять свою часть программы.

    Примеры работы


    Для примера вычислим булевское выражение, "(1|0)&(0|1)". В комбинаторном базисе это можно представить как ````ssk````siik`ki````sii`kik Да, такие выражения невозможно читать, но их можно писать см. учебник. В результате выполнения программы такого вида, состояние машины будет эволюционировать от первоначальной формулы к единственному булевскому значению, либо «1», закодированное как «k», либо значение «0» в виде "`ki". Для данной конкретной формулы получаем именно «k».
    На вычисление уходит 116 тактов. Из них первые 67 тактов продолжается загрузка программы. С точки зрения практической полезности цифры не обнадёживают, но потенциал для оптимизации есть, например использование более богатого набора комбинаторов сократит и размер и время выполнения программы.

    Симулятор и ПЛИС-версия


    Описываемые результаты получены на программном симуляторе. Исходники и исполняемый файл для win здесь. Симулятор — консольное приложение, установки не требует, комбинаторное выражение передаётся как параметр командной строки.
    Краткое описание окна симулятора в интерактивном режиме


    1) Программа на входе
    2) Текущее состояние программы в виде текста
    3) Полное состояние аппаратного дерева
    4) Расшифровка состояния текущего узла

    Здесь небольшой ролик с демонстрацией


    Симулятор точно соответствует реализованной на verilog-е ПЛИС-версии, но с одним принципиальным отличием — он не ограничен по физическим ресурсам. То есть, симулятор обладает потенциально бесконечным деревом, а на ПЛИС дерево ограничено. Дерево из 63 узлов, то есть глубины 6, занимает 16000 Altera LE, это много; если программа в процессе вычисления вырастает больше, то вычисления заканчиваются неудачей. Единственная польза от аппаратной версии — показать принципиальную реализуемость в железе.

    Вернёмся к вычислениям. Теперь посчитаем арифметическое выражение, (2+1). Чтобы перевести это на язык комбинаторной логики используем нумералы Чёрча. Получаем выражение ````si`k`s``s`kski``s``s`kski. Чтобы получить что-то осмысленное, подставим это выражение вот так: ``(2+1)ki. Вычислив это получим `k`k`ki, количество букв к символизирует полученный ответ. На вычисление уходит 124 такта. А вот на вычисление ``(1+2)ki уходит уже 243 такта, на ``(3+3)ki 380 тактов. Увы, пока всё очень медленно, ниже я наметил пути ускорения.
    Приведённые примеры это простые, безусловно «схлопывающиеся» выражения, на практике такие задачи лучше выполнит традиционная машина. Однако, комбинаторная логика будучи полной по Тьюрингу системой, позволяет решать задачи большей вычислительной сложности, соответствующие выражения могут расти в процессе вычисления. Правда, это свойство привносит риск безудержного роста или даже никогда не завершающейся программы, но и преимущество предлагаемая архитектура сможет показать только на таких задачах. Здесь в описании появляются циклы и рекурсия, классическая конструкция для их организации,- комбинатор неподвижной точки:

    `Yx = `x`Yx = `x`x`Yx = `x`x`x`x…
    Y(x)= x(Y(x))= x(x(x(x(...))))


    Гипотетические применения комбинаторной машины на практике


    Логический вывод


    На приведённых выше двух простых примерах видно, что булевские вычисления выглядят интереснее арифметики, машина очень чувствительна к размеру объектов. Но вычисление булевских выражений само по себе малоперспективно: задача даже на последовательной машине выполняется за О(1), то есть, программа будет грузиться дольше чем выполняться.
    Этого «недостатка» лишена задача SAT. Здесь у нас булевское выражение дополняется переменными, и надо определить, выполняется ли формула; это уже NP-полная проблема. Можно добиться значительного ускорения, одновременно проверяя несколько наборов значений переменных. Именно к такого типа задачам я сейчас присматриваюсь. Интересны задачи с непредсказуемыми ветвлениями и без больших чисел, такие как символьные вычисления и автоматическое доказательство теорем.
    Идеальная задача должна формулироваться маленьким выражением, которое сначала растёт как дерево из семечка, формируя как можно больше параллельно вычисляющихся веток, а затем сворачиваться обратно, комбинируя результаты от веток, что-то вроде микро MapReduce:



    Реконфигурируемые вычисления


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

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



    Мы проделали почти то же самое выше, когда применяли Чёрчевское число (3+3) к комбинаторам к и i, которые не выполнялись (в качестве функций) в процессе вычислений, а служили для наглядного представления результата. Заменив к на однобитный сумматор, мы бы получили к моменту завершения вычислений условный сумматор разрядности 6.

    Это потенциальное применение не столь требовательно к производительности, при условии, что переконфигурирование требуется не слишком часто.

    Направления развития, проблемы и их возможные решения


    Эффективное использование узлов


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


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

    Расширение системы команд


    Определённую выгоду в смысле оптимизации можно получить, расширяя набор аппаратно реализованных комбинаторов, сейчас используется базисный набор SKI, возможно будут полезны другие комбинаторы, в том числе
    Bxyz = x(yz)     - композиция х и y 
    Cxyz = xzy       - перестановщик, 
    Wxy = xyy        - удвоитель, 
    Yx = x(Yx)       - комбинатор неподвижной точки.
    (+1)nfx = f(nfx) - инкремент Чёрчевского числа 
    


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

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

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

    О лямбдах


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

    Предыстория


    Идею создать специализированный вычислитель функциональных программ я перенял у своего научного руководителя, Вадима Николаевича Фалька, когда учился в аспирантуре МИРЭА десяток лет назад. Научная работа команды фокусировалась на теоретических исследованиях в области функционального и функционально-логического программирования. В частности, Фальком был разработан язык Falgol, своего рода функциональный ассемблер. Позиционировался он для теоретико-вычислительных целей, вроде доказательства корректности программ, но были и попытки построить на его основе вычислительную машину.

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

    Заключение


    Проект продвигается. Удалось создать прототип не фон неймановского компьютера, сочетающего черты несколько интересных парадигм: функциональное программирование, клеточные автоматы; аналоги мне не известны. ПЛИС-вариант пока малополезен в силу ограничений по ёмкости, но программный симулятор точно соответствующий аппаратной модели позволяет изучать выполнение программ. О практическом использовании в нынешнем виде речи не идёт, но я уже ищу модельную задачу, которая будет взята как цель для будущего применения машины.
    Напоследок ещё раз отмечу, что современное развитие электроники позволяет реализовывать весьма нетривиальные идеи, хотя дело это и трудоёмкое. Спасибо за внимание.

    Ссылки


    Р. В. Душкин aka darkus «Комбинаторы это просто»
    David Madore «The Unlambda Programming Language»
    Интерпретатор языка unlambda
    Share post
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 36

      +3
      Интересно. Но не понятно. А как в случаи растущего выражения (цикла) происходит обработка и загрузка дерева?
        0
        Загрузка происходит как обычно, выражение символ за символом поступает извне через корень и слева направо укладывается на аппаратное дерево. Мы в этот момент ещё не знаем что выражение растущее.
        Когда начинается обработка, дерево начнёт расти: условно говоря, базовый комбинатор 'S' умеет захватывать свободные поддеревья и копировать туда свой (третий) аргумент. Ну и программисту надо позаботиться об условии выхода из цикла, чтобы не было бесконечного роста.
          0
          А если количество циклов превышает количество свободных поддеревьев? На порядки?
            0
            Тогда всё плохо. В перспективе может быть сделано как-то так: при переполнении содержимое дерева замораживается, выгружается во внешнюю память, после чего пытаемся решить задачу по частям, отрывая ветки от замороженного образа.
      • UFO just landed and posted this here
          0
          может и нет, но Вы привели «слабые» аргументы: «Ваши проблемы сконцентрировались вокруг понятия ВЫЧИСЛЕНИЯ, если формулу вычислять, то это будет фон-Неймоновская система(вид сбоку)», а если формулу Доказывать или Упрощать, то может и есть :)
          • UFO just landed and posted this here
              0
              «Неразрешимость планировщика графа» — значит только то, что навернуться на Y-комбинаторе можно, «слабость» в том, что это обязательно делать, если можно ограничится редукцией графа, а мапить уже на других архитектурах. А про вычисления — я имел в виду, что не все вычисления сводятся к NP- полным вычислениям, иногда можно решать и O(n) задачи.
              • UFO just landed and posted this here
                  0
                  Это я и сказал ))) вопрос в том, зачем биться «об стену» не решаемых задач??? инженерное искусство состоит в решении тех задач, которые можно решить на текущем технологическом уровне. Например мы не можем на двоичном компьютере представить число Пи, и поделить его на 3 — не можем, но найти приближение — вполне.
                  • UFO just landed and posted this here
                      0
                      Спокойнее, никто Вас не критикует, я с Вами полностью согласен. Все тлен и пепел… и всем — плакать и стенать! А может нет ?!
            0
            Спасибо, посмотрю внимательнее, но по-моему «REDUCERON» это всё-таки не совсем то, «Each G-machine instruction can in turn be translated to a sequence of regular CPU instructions and executed by a PC» то есть, их «графовая память» не самодостаточна.
            Понимаю, как неказисто пока всё выглядит, и с какими фундаментальными трудностями придётся иметь дело, но я пока верю в шанс найти подходящую задачку, и сделать под неё решение.
            На этом можно было бы закончить, но есть упорные люди, и они столкнулись со следующей проблемой: memory mapping.

            Нету у меня памяти, граф самодостаточен, наружу только корень торчит.
            • UFO just landed and posted this here
                +2
                Как не могу? Сделал уже. Граф не лежит в регистрах, он аппаратно реализован, система работает как клеточный автомат, только не «решеткообразный» а древовидный.
            +1
            1) Почему отказались от двоичных типов (адресное пространство можно былобы разделить; были «машины указателей», для них фон Неймановское «бутылочное горлышко» было не так проблемотично; проблема разреженности могла бы быть уменьшина при отказе от «нумералов», симулировать все типы функционально… очень муторно, и вся эффективность будет потрачена на их симмуляцию)
            2) X-комбинатор можно былобы довавить ()
            3) где Y-комбинатор будет остановлен (где берете память на сохранение дерева)?
            4) многомерность — интересная идея: можно использовать адресное пространство, как код комбинатора: '''s(addr1,addr2,add3) ->S-Base:[...addr1,addr2,add3...]; ''k(addr1,addr2) -> K-Base:[… addr2 ...]; 'i(expression) -> SAA-Base:[… addr-of-sequence-exspression ...]

            ах. да:
            5) а pi-исчисления не будет? хотя бы в форме Linda
              0
              1 — Я не отказался, просто двоичный аналог нумералов Чёрча мне пока не по зубам, хотя сделать его определённо можно. (Кстати, если кто-нибудь знает готовые работы по теме, напишите пожалуйста.)
              2,5 — Спасибо, посмотрю.
              3 — Остановить можно: f(f(f(f...) необязательно вычислять полностью, в какой-то момент f просто игнорирует свой аргумент.
              4 — не очень понял.
                0
                1- я думал, что когда CPU получает 'i(...) идет запрос в сопроцессор
                3- выше был ворос, куда эти f(f(f...) складываются, и прежде чем игнорить аргумент f(a) в него нужно заглянуть, и ''k(_,_) может быть не первой командой, в результате стек будет рости, а если ''y будет внутри ''y… ой
                4- я только предложил, моно не обращать внимания
                  0
                  1 — нет, вычисляется прямо на месте, без помощи извне.
                  3 — зависит от стратегии вычисления, при энергичной будет бесконечно расти, при ленивой не будет, но и то и другое — стратегии выполнения на последовательной машине, у меня стратегия смешанная.
              +1
              Тоже хотел спросить про pi исчисление. Концепция взаимодействующих процессов через канала мне кажется хорошо ляжет на вашу реализацию.
              Так же можно посмотреть на модель акторов.
              Обе эти модели выводимы из ламбды, верифицируемы и полны по тьюрингу.
                0
                Спасибо, посмотрю.
                0
                У аппаратчиков эта идея называется Dataflow Architecture, ни один десяток лет уже умы будоражит:
                ieeexplore.ieee.org/search/searchresult.jsp?newsearch=true&queryText=dataflow+architecture

                ПЛИС сама по сути является Dataflow-процессором: Массив операционных элементов: LUT'ов, DSP-блоков, Памятей, которые соединяются по заданной программе на Verilog. Актуальный вопрос в том, можно ли придумать удобный язык программирования для такой архитектуры, т.к. Verilog и VHDL в каком-то смысле низкоуровневые ассемблеры. Сейчас актуальными являются попытки компиляции из C/C++ и OpenCL для ПЛИС, т.к. эти языки популярны среди программистов.
                  0
                  По моему представлению, Dataflow это что-то вроде системы конвейеров на заводе, перестройка на лету и движение данных в разных направлениях там не характерны.
                    +1
                    Тут главное это идея непосредственного воплощения куска CDFG в аппаратуре. В принципе, современные ПЛИС уже позволяют частичную реконфигурацию на лету.
                    Советую ещё почитать статьи по Wavescalar, у них там даже есть бенчмарки в сравнении с x86 и размышления на тему для каких областей это применимо.
                      0
                      Теперь понял. Да, в разделе «реконфигурируемые вычисления» я как раз рассматриваю комбинаторную машину как инфраструктуру для подобной системы, правда пока в теории. Про Wavescalar почитаю, спасибо.
                    0
                    Да, похоже на разновидность Dataflow Architecture, мне почему-то вспомнилась transport-triggered architecture и FleetZERO. С другой стороны, автор говорит, что «система работает как клеточный автомат, только не «решеткообразный» а древовидный». Хотелось бы понять, клеточный автомат вообще — это переупрощение железа за счёт переусложнения софта как здесь
                    en.wikipedia.org/wiki/One_instruction_set_computer
                    или в придачу к экзотичности программирования ещё и железо будет сложным?
                      0
                      transport-triggered architecture — возможно, хотя по первому впечатлению там не подразумевается столь полная децентрализация.
                      FleetZERO -кажется скорее про «самосинхронные схемы» — совсем низкоуровневую асинхронность, без тактового сигнала и триггеров. Но синергия тут возможна, … была бы, выживи проекты :(
                      переупрощение железа за счёт переусложнения софта
                      Ну, замысел-то не переусложнять, а использовать другую организацию процесса вычислений, да и железо, реализующее потенциально бесконечную сеть может оказаться весьма не простым.
                      У меня в мечтах изучить Chisel HDL и отделить в описании машины уровень сети от логики ноды.
                        0
                        Если замысел не переусложнять, то может быть использовать что-то более распространенное, чем Chisel HDL? Скажем те немногие встроенные возможности функционального программирования, которые есть в MATLAB? Может оказаться, что для комбинаторного программирования их хватит
                        en.wikipedia.org/wiki/Function-level_programming
                        Кстати, Википедия в статье Компьютер_для_операций_с_функциями пишет, что вычислительная машина для операций с функциями была предложена и разработана Карцевым в 1967 году. Реконфигурировать её на лету вряд ли получится, но сама идея использовать двойную сумму в системе счисления интересна…
                          0
                          Если замысел не переусложнять, то может быть использовать что-то более распространенное, чем Chisel HDL?...
                          Chisel для описания аппаратуры самой машины, а не программ для неё.
                          Компьютер_для_операций_с_функциями
                          Там я так понимаю, ориентировано на перемножение матриц, это другое.
                            0
                            Там я так понимаю, ориентировано на перемножение матриц
                            Да, в компьютере для военных (функционально-операторная М-9), нужно ожидать алгоритмов DSP, в частности, БПФ. Вы упоминали язык Falgol, интересно какая архитектура была бы оптимальной для него? Кстати, вот совсем свежая попытка применить lambda-подобный язык для проектирования самосинхронных схем
                            www.delayinsensitive.com/download.html
                    0
                    Компиляция C-кода в HDL не новая идея, реконфигурирование в рантайме поддерживают далеко не все ПЛИС, но тоже бывает.
                    То, то работает в симуляторе с неограниченными ресурсами бесполезно, если это нельзя запустить на реальной ПЛИС.
                    Мне лично было бы более понятно и интересно, если бы вы написали обзор существующих решений подобного рода, их недостатки, а затем бы сосредоточились на новизне именно вашего подхода и его преимуществах по сравнению с существующими.
                      0
                      Чтобы что-то прошить в ПЛИС даже в рантайм, вы прошивку должны подготовить заранее, я надеюсь сделать возможным как реконфигурирование, так и подготовку прошивки из спецификации на лету.
                      На ПЛИС не имеет смысла запускать сейчас, но это совсем простая, не оптимизированная версия. По моему мнению, предложенные в статье меры могут существенно изменить ситуацию.
                      Чукча не читатель, чукча писатель. Обзор решений я не потяну. Могу только повторить, что близкие аналоги (очень простые локально связанные ядра, практически, клеточный автомат, способный выполнять функциональные программы) мне не известны.
                      0
                      Один из вариантов не-фон неймановской архитектуры реализованный в кристалле habrahabr.ru/post/226773/
                        0
                        Да, я уже с интересом слежу за этим (Мультиклет) проектом. Но, насколько я понимаю, эта архитектура не любит рекурсию и тяготеет к задачам ЦОС. А у меня упор на плохо предсказуемые вычисления с большим количеством условий и рекурсией.
                        0
                        Вы дерево прямо в ПЛИС помещаете? А из внешней памяти не получится?
                          0
                          В ПЛИС зашито исполнительное устройство, способное выполнить любую программу в данном комбинаторном базисе, (если хватит ресурсов). Программа грузится извне, и по завершению вычислений результат, то есть нормальная форма выражения, отдаётся наружу. (Если я правильно понял ваш вопрос.)

                        Only users with full accounts can post comments. Log in, please.