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

[@mikhanoid]

Интересно. Но не понятно. А как в случаи растущего выражения (цикла) происходит обработка и загрузка дерева?

[@leshabirukov]

Загрузка происходит как обычно, выражение символ за символом поступает извне через корень и слева направо укладывается на аппаратное дерево. Мы в этот момент ещё не знаем что выражение растущее.
Когда начинается обработка, дерево начнёт расти: условно говоря, базовый комбинатор 'S' умеет захватывать свободные поддеревья и копировать туда свой (третий) аргумент. Ну и программисту надо позаботиться об условии выхода из цикла, чтобы не было бесконечного роста.

[@ncix]

А если количество циклов превышает количество свободных поддеревьев? На порядки?

[@leshabirukov]

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

[@Duduka]

может и нет, но Вы привели «слабые» аргументы: «Ваши проблемы сконцентрировались вокруг понятия ВЫЧИСЛЕНИЯ, если формулу вычислять, то это будет фон-Неймоновская система(вид сбоку)», а если формулу Доказывать или Упрощать, то может и есть :)

[@Duduka]

«Неразрешимость планировщика графа» — значит только то, что навернуться на Y-комбинаторе можно, «слабость» в том, что это обязательно делать, если можно ограничится редукцией графа, а мапить уже на других архитектурах. А про вычисления — я имел в виду, что не все вычисления сводятся к NP- полным вычислениям, иногда можно решать и O(n) задачи.

[@Duduka]

Это я и сказал ))) вопрос в том, зачем биться «об стену» не решаемых задач??? инженерное искусство состоит в решении тех задач, которые можно решить на текущем технологическом уровне. Например мы не можем на двоичном компьютере представить число Пи, и поделить его на 3 — не можем, но найти приближение — вполне.

[@Duduka]

Спокойнее, никто Вас не критикует, я с Вами полностью согласен. Все тлен и пепел… и всем — плакать и стенать! А может нет ?!

[@leshabirukov]

Спасибо, посмотрю внимательнее, но по-моему «REDUCERON» это всё-таки не совсем то, «Each G-machine instruction can in turn be translated to a sequence of regular CPU instructions and executed by a PC» то есть, их «графовая память» не самодостаточна.
Понимаю, как неказисто пока всё выглядит, и с какими фундаментальными трудностями придётся иметь дело, но я пока верю в шанс найти подходящую задачку, и сделать под неё решение.

На этом можно было бы закончить, но есть упорные люди, и они столкнулись со следующей проблемой: memory mapping.

Нету у меня памяти, граф самодостаточен, наружу только корень торчит.

[@leshabirukov]

Как не могу? Сделал уже. Граф не лежит в регистрах, он аппаратно реализован, система работает как клеточный автомат, только не «решеткообразный» а древовидный.

[@Duduka]

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

[@leshabirukov]

1 — Я не отказался, просто двоичный аналог нумералов Чёрча мне пока не по зубам, хотя сделать его определённо можно. (Кстати, если кто-нибудь знает готовые работы по теме, напишите пожалуйста.)
2,5 — Спасибо, посмотрю.
3 — Остановить можно: f(f(f(f...) необязательно вычислять полностью, в какой-то момент f просто игнорирует свой аргумент.
4 — не очень понял.

[@Duduka]

1- я думал, что когда CPU получает 'i(...) идет запрос в сопроцессор
3- выше был ворос, куда эти f(f(f...) складываются, и прежде чем игнорить аргумент f(a) в него нужно заглянуть, и ''k(_,_) может быть не первой командой, в результате стек будет рости, а если ''y будет внутри ''y… ой
4- я только предложил, моно не обращать внимания

[@leshabirukov]

1 — нет, вычисляется прямо на месте, без помощи извне.
3 — зависит от стратегии вычисления, при энергичной будет бесконечно расти, при ленивой не будет, но и то и другое — стратегии выполнения на последовательной машине, у меня стратегия смешанная.

[@HDDimon]

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

[@leshabirukov]

Спасибо, посмотрю.

[@Daffodil]

У аппаратчиков эта идея называется Dataflow Architecture, ни один десяток лет уже умы будоражит:
ieeexplore.ieee.org/search/searchresult.jsp?newsearch=true&queryText=dataflow+architecture

ПЛИС сама по сути является Dataflow-процессором: Массив операционных элементов: LUT'ов, DSP-блоков, Памятей, которые соединяются по заданной программе на Verilog. Актуальный вопрос в том, можно ли придумать удобный язык программирования для такой архитектуры, т.к. Verilog и VHDL в каком-то смысле низкоуровневые ассемблеры. Сейчас актуальными являются попытки компиляции из C/C++ и OpenCL для ПЛИС, т.к. эти языки популярны среди программистов.

[@leshabirukov]

По моему представлению, Dataflow это что-то вроде системы конвейеров на заводе, перестройка на лету и движение данных в разных направлениях там не характерны.

[@Daffodil]

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

[@leshabirukov]

Теперь понял. Да, в разделе «реконфигурируемые вычисления» я как раз рассматриваю комбинаторную машину как инфраструктуру для подобной системы, правда пока в теории. Про Wavescalar почитаю, спасибо.

[@Thealik]

Да, похоже на разновидность Dataflow Architecture, мне почему-то вспомнилась transport-triggered architecture и FleetZERO. С другой стороны, автор говорит, что «система работает как клеточный автомат, только не «решеткообразный» а древовидный». Хотелось бы понять, клеточный автомат вообще — это переупрощение железа за счёт переусложнения софта как здесь
en.wikipedia.org/wiki/One_instruction_set_computer
или в придачу к экзотичности программирования ещё и железо будет сложным?

[@leshabirukov]

transport-triggered architecture — возможно, хотя по первому впечатлению там не подразумевается столь полная децентрализация.
FleetZERO -кажется скорее про «самосинхронные схемы» — совсем низкоуровневую асинхронность, без тактового сигнала и триггеров. Но синергия тут возможна, … была бы, выживи проекты :(

переупрощение железа за счёт переусложнения софта

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

[@Thealik]

Если замысел не переусложнять, то может быть использовать что-то более распространенное, чем Chisel HDL? Скажем те немногие встроенные возможности функционального программирования, которые есть в MATLAB? Может оказаться, что для комбинаторного программирования их хватит
en.wikipedia.org/wiki/Function-level_programming
Кстати, Википедия в статье Компьютер_для_операций_с_функциями пишет, что вычислительная машина для операций с функциями была предложена и разработана Карцевым в 1967 году. Реконфигурировать её на лету вряд ли получится, но сама идея использовать двойную сумму в системе счисления интересна…

[@leshabirukov]

Если замысел не переусложнять, то может быть использовать что-то более распространенное, чем Chisel HDL?...

Chisel для описания аппаратуры самой машины, а не программ для неё.

Компьютер_для_операций_с_функциями

Там я так понимаю, ориентировано на перемножение матриц, это другое.

[@Thealik]

Там я так понимаю, ориентировано на перемножение матриц

Да, в компьютере для военных (функционально-операторная М-9), нужно ожидать алгоритмов DSP, в частности, БПФ. Вы упоминали язык Falgol, интересно какая архитектура была бы оптимальной для него? Кстати, вот совсем свежая попытка применить lambda-подобный язык для проектирования самосинхронных схем
www.delayinsensitive.com/download.html

[@32bit_me]

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

[@leshabirukov]

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

[@krufter]

Один из вариантов не-фон неймановской архитектуры реализованный в кристалле habrahabr.ru/post/226773/

[@leshabirukov]

Да, я уже с интересом слежу за этим (Мультиклет) проектом. Но, насколько я понимаю, эта архитектура не любит рекурсию и тяготеет к задачам ЦОС. А у меня упор на плохо предсказуемые вычисления с большим количеством условий и рекурсией.

[@potan]

Вы дерево прямо в ПЛИС помещаете? А из внешней памяти не получится?

[@leshabirukov]

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