Leonid

Реализация механизма памяти в управляющем клеточном автомате

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

Дальнейшие рассуждения я попробовал изложить в статье.
Leonid

Моделирование процессов клеточными автоматами

Очередная идея. Для обучения управляющих клеточных автоматов я применяю обучающие последовательности. Но, это хорошо работает только в тех случаях, когда обучающая последовательность простая и конечная. Это подходит для релейных (логических) схем процессов. Для временных рядов, когда имеется достаточно длинный временной ряд. А вот для процессов непрерывных, изменяющихся быстро и плохо регулируемых такой подход не годится. Невозможно создать обучающую последовательность для процессов, например таких, какие обычно регулируются ПИД-регуляторами. Настройка таких регуляторов не такое уж простое дело.
Получается, чтобы "научить" мои автоматы управлению динамическими процессами, надо иметь некую математическую модель этого процесса. Если рассмотреть процесс как черный ящик, то можно заметить, что он протекает под управлением каких-то воздействий. Результатом этих воздействий будут основные его технологические характеристики. Тут прослеживается некоторая аналогия с управляющими автоматами. У них тоже есть некоторые управляющие воздействия - значения которых отображаются входными клетками, и технологические характеристики - значения выходных клеток. Следовательно можно применить клеточные автоматы для моделирования сложных технологических процессов. Для того, чтобы вырастить из клеточного автомата модель технологического процесса надо собрать с существующего процесса телеметрию. Эта телеметрия и послужит обучающей последовательностью для моделмрующего клеточного автомата. Идем к объекту регулирования, навешиваем на него кучу разнообразных датчиков. Включаем объект, производим регулирование или управление процессом в ручном режиме. Записываем телеметрию. Затем используем эти записи для обучения моделирующего процесс клеточного автомата. Тут просто - то, что курутили, управляя процессом - то вход, то, что приходило в процесс - то тоже вход. А то, ради чего регулировали - выход. Методика создания моделирующего клеточного автомата ни чем не отличается от методики создания управляющего клеточного автомата. Вырастив моделирующий клеточный автомат на полученной телеметрии, можно его использовать для создания управляющего клеточного автомата. Вот такая вот идея. Пошел творить.
Leonid

144-ядерный процессор Чарльза Мура поступил в продажу по $20

Оригинал взят у Блог им. koroandr
Чарльз Мур, создатель языка программирования Форт (Forth), довёл до стадии промышленного производства уникальную разработку — многоядерный процессор GA144. Чип размером 10х10 мм уже поступил в продажу по цене $20 (при заказе от десяти штук), также доступны материнские платы для него. Фактически, это аппаратное воплощение самого языка программирования Форт.

Крайне необычный процессор по ряду параметров не имеет себе равных среди CPU:
  • 144 независимых ядра, которые активируются только при поступлении инструкции, то есть у этого процессора нет такой характеристики как «тактовая частота»;
  • скорость выполнения инструкций 1400 пикосекунд (эквивалент 700 МГц);
  • энергопотребление 7 пикоджоулей на одну инструкцию;
  • энергопотребление в «спящем» режиме менее 100 нановатт;
Многоуровневое программирование даёт возможность писать очень быстрый и простой микрокод либо использовать высокоуровневый язык программирования, либо сочетать оба этих метода в кластерах вычислительных ядер с указанием среди них «хостов» и «сопроцессоров» на выбор.

Чак разработал этот процессор самостоятельно с помощью им же созданного инструментария OKAD II VLSI. Инструменты для разработки под GA144, включая ассемблер/компилятор и примеры исходных кодов, распространяются бесплатно в пакете под общим названием arrayForth.

Специалисты пытаются понять, каковы целевые области применения GA144. Вариантов много:
  • робототехника (манипуляторы, протезы, автономные подвижные роботы);
  • искусственный интеллект и нейронные сети (классификация, распознавание сигналов/образов);
  • «бортовые системы» (диагностика состояния в реальном времени, контроль движения);
  • «академическое» применение (аппаратное обеспечение курсов цифровой обработки сигналов, параллельного программирования, архитектуры вычислительных систем);
  • распознавание и синтез речи;
  • модуляторы/демодуляторы сигналов.
Сам разработчик процессора дополняет этот список различными энергоэффективными приложениями (модуль беспроводного приёма энергии), портативными устройствами, системами обработки изображений, сложными управляющими системами, криптографией, высокопроизводительной обработкой сигналов, программами симуляции и синтеза и другими приложениями, которые нуждаются в массовом параллелизме.

Мой комментарий: вот и железо уже готово. Наверное, всё-таки придется вернуться к Forth-у.
Leonid

It's evolution, baby!

Оригинал взят у gest в It's evolution, baby!
Сегодня я вдруг подумал, что хочу рассказать вам одну историю. Есть на свете такой исследователь - Адриан Томпсон. Однажды он решил изучить процессы эволюции в неживых системах, на примере FPGA-чипа. Field-Programmable Gate Array - по-русски это будет Программируемая пользователем вентильная матрица, частный случай Программируемых логических интегральных схем. Да, Томпсона интересовала практическая сторона вопроса - можно ли использовать принцип эволюции для разработки более эффективных схем?

По-английски об этом можно прочитать тут:

Evolvable hardware
On the Origin of Circuits

В чём была суть эксперимента? Итак, у нас есть чип, матрица из программируемых ячеек, 64 x 64. Для опыта использовался только один угол матрицы, квадрат из ста ячеек:



Условная схема отдельной ячейки:



Итак, каждая ячейка может получать сигнал с одной из четырёх сторон (по сторонам света - N, S, E, W) и передавать его дальше. Она также может передавать функцию (F) - результат логической операции над одним, двумя или тремя сигналами. Например, слева и справа пришло по "1", передаём вниз "1", слева пришла "1", но справа "0", передаём вниз "0". Поведение каждой ячейки задаётся отдельной программой - что передавать, как и куда.  Естественно, можно настроить ячейку так, чтобы она всегда выдавала одно и то же значение, независимо от того, какой сигнал получен.

Исследователь сформулировал задачу - система из ста ячеек и логических вентилей-переключателей должна "научиться" отличать поступающий на вход (IN) сигнал частотой в 1 герц от сигнала частотой 10 герц. Не используя встроенный таймер! В идеале, система должна была выдавать на выход (OUT) напряжение в 5 вольт, если "слышала" 10 герц, и 0 вольт в остальных случаях.

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

Collapse )

Update: _hellmaus_ подсказал, что про это у нас уже писали - "Эволюция железа".

Leonid

Еще раз о том, что мне хочется получить

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

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

Рассмотрим более сложный пример обучающей последовательности. Клапан. Имеем два входных параметра. Допустим, давление и уставку. Оба параметра измеряются с точностью 4 бита. Клапан работает, если значение давления не превышает уставки. Если превышает, то клапан закрывается. Выходом является сигнал управления клапаном - 0 - клапан закрыт, 1 - клапан открыт. В данном случае имеем 8 входных битов и один выходной. Обучающая последовательность записывается следующим образом:
8:1
0:0:0:0:0:1:0:0:1
0:0:0:1:0:1:0:0:1
....
0:1:0:0:0:1:0:0:1
0:1:0:1:0:1:0:0:0
0:1:1:0:0:1:0:0:0
....
1:1:1:1:0:1:0:0:0
Здесь показана обучающая последовательность для значения уставки 0100 и только. Если надо управление уставкой, то длина обучающей последовательности увеличится всего в 16 раз. Для каждого значения уставки надо написать свою обучающую последовательность из 16 строк. Итого 256 строк + 1 строка-заголовок.

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


Для программирования любой задачи, для которой можно написать однозначную управляющую последовательность, создается только одна программа - программа расчета текущих состояний клеток. Текущие состояния клеток - суть биты. Значит в 10 байтах можно разместить систему с 80-ю клетками. Для хранения прошлого состояния системы надо иметь еще 10 байтов. Для хранения алгоритмов расчета каждой клетки потребуется до 3-х байт в случае автоматов с тремя выходами. Значит, расход памяти флэшки составит для 80-клеточной системы до 240 байт. Плюс программа, выполняющая однотипные расчетные операции, ну, пусть еще сотня байт. Вот насчет программ, обрабатывающих вход и выход пока ничего не могу сказать, но, то, что просматривал в готовых программах для МК могу грубо оценить еще сотней байт. И все! Получается, что можно обходиться весьма "слабыми" в плане памяти микроконтроллерами.
Leonid

Ищу единомышленников

Разместил на разных досках объявлений и в нескольких радио-форумах такое объявление:

Ищу единомышленников (управляющие клеточные автоматы)

В свободное время занимаюсь исследованиями в области управляющих клеточных автоматов.
Похоже, пора заняться воплощением математики в железо.
Проект не коммерческий. Денег не прошу и не предлагаю.
Приглашаю к сотрудничеству. Ознакомиться с вопросом можно в моем ЖЖ: http://legre.pp.ua

Объявление не осталось незамеченным. Некоторые модераторы просто удалили его, о чем любезно сообщили мне.
На форумах объявление вызвало неоднозначную реакцию. Больше всего мне понравилась такая реакция:

Форум "РадиоКот" http://radiokot.ru/forum/viewtopic.php?f=29&t=54675

Бред и реклама ЖЖ.
Сначала бы научился грамотно писать...


На других форумах реакция есть, но тоже не по делу. Даже не знаю, стоит ли тратить время на болтовню там?
 
Leonid

Заканчиваем подсчет

Рассмотрим автоматы релейной схемы "два входа - два выхода". Можно представить их как два сросшихся автомата схемы "два входа - один выход". Оно так и есть, если объеденить входные клетки вух автоматов "2-1", что возможно. В результате получим 254 варианта элементарных клеточных автомата.

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

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

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

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

Рывок триггерных алгоритмов

Рывок

    Рассмотрим элементарные клеточные автоматы, реализующие релейные алгоритмы работы "два входа - один выход". Тут ничего интересного. Согласно Википедии возможны 16 вариантов алгоритмов. Обучающие последовательности приведены в таблице:



In

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

0 0

0

0

0

0

0

0

0

0

1

1

1

1

1

1

1

1

0 1

0

0

0

0

1

1

1

1

0

0

0

0

1

1

1

1

1 0

0

0

1

1

0

0

1

1

0

0

1

1

0

0

1

1

1 1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1


   Для элементарных клеточных автоматов первую последовательность и последнюю использовать нет смысла, так как они не изменяют значения выходной клетки. Остается 14 вариантов.

   Для релейных схем "три входа - один выход" возможно 256 вариантов входных состояний. Первое и последнее не пригодны для нас. Остается 254 варианта разновидностей алгоритмов работы элементарных клеточных автоматов.

   Тепрь посмотрим, как можно применить идею триггерности в схемах "два входа - один выход".
Если в простейшем алгоритме в схеме с одним входом и одним выходом на вход автомата подается единственное значение, которое и управляет работой триггера, то в случае "два входа - один выход" на вход автомата может прийти аж четыре варианта значений. И каждое из них может вызывать триггерный эффект. Если записать действие, выполняемое автоматом таким образом: ( 0 → (2), 1 → (3) ) - то получился триггер, управляемый единицей. При приходе 0 изменений не происходит (2) - функция клетки "оставить как было", а при приходе 1 происходит инверсия значения клетки (3) - функция клетки "инвертировать прошлое состояние клетки".
     Для четырех вариантов входящих состояний элементарного клеточного автомата "два входа - один выход" можно составить, например, такое описание алгоритма:
0 0 → (2)
0 1 → (3)
1 0 → (2)
1 1 → (3)
   Что означает: если на вход клетки поступили первое или третье значения, то никаких изменений прошлого сотояния не будет. А если второе или четвертое - то прошлое состояние будет проинвертировано.
    И таких комбинаций может быть 16. Но, здесь только одна комбинация "не нужна" - (2), (2), (2), (2),  так как не производит никаких изменений в любом случае. А комбинация (3), (3), (3), (3) - полезна - изменения состояния происходят. Получилось 16 вариантов. Уже на 1 больше, чем у релейных схем. По аналогии для автоматов "три входа - один выход" релейных схем алгоритмов возможно 255.
Дозаполним табличку:

Вход

Выход

1

2

3

1

0р + 2т

12р + 6т

56р + 14т

2

14р + 15т

3

254р + 255т

Leonid

на распутье трех дорог

На распутье трех дорог

Продолжаем рассмотрение видов элементарных клеточных автоматов. Сегодня рассмотрим возможное количество автоматов вида "один вход - три выхода". Вариантов для трех битов может быть 8. Если у нас два значения на входе (0 и 1), то на выходе будет 8 х 8 = 64 варианта. Но, так как варианты, не изменяющие значения выхода составляют 8 штук, то остается 56 вариантов элементарных клеточных автоматов релейного типа, которые пригодны для использования.
Например, вариант пригодного для использования алгоритма: 0  → 0 1 0; 1 → 1 0 0;
вариант не пригодного для использования алгоритма 0  → 0 1 1; 1 → 0 1 1.

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

Теперь оценим количество триггерных вариантов элементарных клеточных автоматов вида "один вход - три выхода". По аналогии с "один вход - два выхода" возможно для одного управляющего входа построить 7 альтернативных состояний. В нашем случае, когда управляющим значением является или 1 или 0, общее количество триггерных вариантов элементарных клеточных автоматов состаляет 14. Дозаполним табличку видов:

Вход

Выход

1

2

3

1

0р + 2т

12р + 6т

56р + 14т

2

3


В следующей статье рассмотрим автоматы вида "два входа - один выход".
Leonid

Один вход - два выхода


Один вход - два выхода
Теперь попробуем разобраться с элементарными клеточными автоматами, обладающими одним входом и двумя выходами. Не правда ли, что это напоминает железнодорожную стрелку? Поэтому я их называю "маршрутизаторами". Можно представить себе, что поезд, пришедший на вход такой стрелки может поехать по обному из двух возможных маршрутов - налево или направо. Но клеточный автомат не стрелка и единичка, появившаяся на входе - не поезд.
Сколько же вариантов маршрутизации информации можно создать по такой схеме? Прежде всего надо не зацикливаться на единичке. Будто бы только она одна и есть та самая информация, которая должна куда-то на этой "стрелке" поехать. Возможно несколько вариантов продолжения маршрута после того, как единичка приехала к стрелке. Так как выхода два, то они могут принимать 4 варианта состояний: 00, 01, 10 и 11. То же самое может случиться, если управляющим сигналом будет 0. Если совместить все эти варианты, то получим 16 схем, приведенных в таблице:
Значения выходных клеток

Номер

варианта

Если на

входе 0

Если на

входе 1

1


00


00

2

00

01

3

00

10

4

00

11

5

01


00

6

01

01

7

01

10

8

01

11

9

10


00

10

10

01

11

10

10

12

10

11

13

11


00

14

11

01

15

11

10

16

11

11


Четыре строки таблицы, выделенные желтым цветом, ничего не меняют на выходе элементарного клеточного автомата. Значит они нам не нужны. Остается 12 вариантов элементарных клеточных автоматов релейного типа.

Пример алгоритма 8 варианта приведен ниже:


Глаза
(свойства)

Глаз

Номер клетки

1

2


0

2

1


1

0

0


2

0

0


Клетки
(функции)

Аргумент

Номер клетки

1

2

0

0

1

1

1


Теперь посмотрим каким образом в этой схеме можно задействовать автоматы типа триггеров. Особенностью всех алгоритмов является начальная инициализация клеток элементарного клеточного автомата в 0. Следовательно, начальное состояние всех выходных клеток любого элементарного клеточного автомата всегда 00.
Возможны три варианта различных состояний выходных клеток по приходу управляющего сигнала на вход, отличные от этого значения, это - 01, 10 и 11. Так как такие состояния могут рассматриваться и при управляющей единице и при управляющем нуле, то всего получается 6 триггерных элементарных клеточных автоматов. Управляющий сигнал либо устанавливает одно из этих состояний в выходных клетках, если они имели нулевое состояние, либо сбрасывает их в 00, если состояние отличалось от 00.

Примеры двух вариантов реализации одного и того же триггерного алгоритма с двумя выходными состояниями 00 и 01 и переключающей единицей приведены ниже:

Глаза
(свойства)

Глаз

Номер клетки

1

2

0

1

3

1

0

0

2

0

0

Клетки
(функции)

Аргумент

Номер клетки

1

2

0

3

1

0

2




Глаза
(свойства)

Глаз

Номер клетки

1

2


0

2

2


1

0

0


2

0

0


Клетки
(функции)

Аргумент

Номер клетки

1

2

0

0

2

1

0

3


В результате построения алгоритмов удалось установить, что для схемы "один вход - два выхода" существует 12 релейных и 6 триггерных полезных вариантов элементарных клеточных автоматов. Хотелось бы, что бы читатели предложили еще какие-либо варианты.


Вход

Выход

1

2

3

1

0р + 2т

12р + 6т

2

3


О схемах "один вход - три выхода" будет следующая статья.