Клеточные автоматы с последовательным перебором возможных состояний. Аппаратная реализация и использование для моделирования нейронных сетей и других структур параллельных вычислений.

Введение

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

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

Для моделирования нейронных сетей могли бы подойти аппаратно реализованные клеточные автоматы. Подобную идею развивал проект "эволюционирующей аппаратной части" ("evolving hardvare") CAM-Brain компании Genobyte. Помимо моделирования нейронных сетей, аппаратно реализованные клеточные автоматы могли бы быть использованы в нанотехнологических проектах для управления поведением объектов, состоящих из огромного числа одинаковых наноэлементов, как, например, в проекте Claytronics. Но, к сожалению, при попытках достичь функционального разнообразия и гибкости элемента клеточного автомата, аппаратные реализации клеточных автоматов становятся слишком сложными и очень дорогими, даже при использовании FPGA.

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

Клеточные автоматы. Игра "Жизнь". Использование клеточных автоматов для "выращивания" параллельных вычислительных структур и нейронных сетей.

Клеточный автомат можно представить как матрицу элементов, обладающих следующими свойствами:

Самым известным наглядным примером клеточных автоматов является математическая игра "Жизнь" математика Дж. Конуэя (J. Conway). Давайте вспомним, что она из себя представляет.

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

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

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

Внешнее хранение функции переходов клеточных автоматов. Группирование запросов к функции переходов. Циклический перебор и условный переход состояний.

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

Однако напрямую этого сделать нельзя - разные элементы в один и тот же момент времени могут находиться в разных состояниях и с разными состояниями соседей, поэтому все одновременно обратиться к ЗУ для определения своего нового состояния не могут. Чтобы обойти эту трудность, есть несколько способов. Один из них - последовательное выполнение запросов к ЗУ каждым элементом поочереди. Этот способ самый простой и неэффективный, потому что в данном случае аппаратная реализация клеточного автомата становится практически аналогичной по быстродействию программной реализации на ЭВМ фон Неймана.

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

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

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

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

Реализация численных величин. Маскирование битов. Элемент клеточного автомата как универсальный процессор.

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

Маска образца позволит обобщить условие перехода на целые группы состояний, существенно сокращая описание и реализацию функции переходов.

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

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

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

Взаимодействие с соседними элементами.

Как сказано выше, изменение состояний элементов клеточного автомата зависит не только от их собственных состояний, но и от состояния соседей. Для сравнения комбинации состояний элемента и соседей необходимо (M+1)*N разрядов, где M - количество соседей элемента в матрице, N - разрядность регистра состояния элемента. Конечно же это отражается на размерах и сложности одного элемента, а также на количестве линий шины, передающей сигналы от ЗУ ко всем элементам матрицы.

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

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

Лавинное распространение условия перехода. Взаимодействие на больших расстояниях.

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

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

Пример участка функции переходов:

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

Взаимодействие с внешними системами. Инициализация клеточного автомата.

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

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

Принципиальная схема элемента клеточного автомата.

Предлагаемая схема элемента клеточного автомата спроектирована на основе только одного логического вентиля - И-НЕ, как одного из самых простых.

Для каждого разряда вместо передачи бита состояния и бита маски используется передача унарным кодом по двум линиям:

В случае сравнения с образцом:

Такой выбор кодировки позволяет использовать простой RS-триггер (DN.3, DN.4) со схемой разрешения (DN.1, DN.2) вместо более сложных D-триггеров, а в качестве схем сравнения - пару элементов И-НЕ (DN.5, DN.6), выходы которых от всех разрядов объединяются на одном многовходовом элементе И-НЕ (D2).

По шине ко всем элементам матрицы передаются следующие сигналы:

Помимо этого, для каждого столбца элементов имеется отдельная линия CSEL, а для каждой строки - отдельная линия RSEL, которые используются в режиме непосредственного указания элементов.

Если подан сигнал TRN при установленном триггере (единица на выходе DN.3), или если подан сигнал TSN при сброшенном триггере (единица на выходе DN.4), то на выходе соответствующего элемента схемы сравнения (DN.5 или DN.6) появится 0. У непроверяемых битов или у соответствующих условию перехода на выходе обоих элементов схемы сравнения будет единица. Таким образом, условие перехода формируется только в том случае, если на всех выходах сравнения всех разрядов присутствует единица. Условие перехода подается на элементы разрешения переключения RS-триггеров.

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

Количество коммуникационных битов - один. На схеме в качестве коммуникационного бита изображен бит N. Состояние его триггера передается в схемы сравнения соседних элементов.

Выбор операции "И" или "ИЛИ" для результатов сравнения коммуникационных битов разных соседей осуществляется выбором прямого (D7) или инверсного (D6) выхода отдельной схемы сравнения для коммуникационных битов. Для объединения результатов сравнения коммуникационных битов по "ИЛИ" необходимо производить сравнение c инвертированными значениями и использовать инверсный выход, то есть используется эффект превращения операции "И" в операцию "ИЛИ" при инверсии логических уровней.

Для непосредственного указания элементов, например, в случае инициализации клеточного автомата, предназначены сигналы CSEL и RSEL. Для этого 1 должна быть подана только на те линии CSEL и RSEL, на пересечении которых находится требуемый элемент, на всех остальных линиях СSEL и RSEL должен быть 0. Тогда условие перехода сможет возникнуть только в выбранных элементах. В нормальном режиме работы клеточного автомата 1 должна быть подана на все линии CSEL и RSEL.


Примеры.

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

Каждая строка описания функции переходов будет иметь один из двух форматов:
Sssss, TRBL => Ddddd,
либо
Sssss, ~TRBL => Ddddd,

где Sssss - исходное состояние элемента, S - значение коммуникационного бита, s - значения некоммуникационных битов; T - значение коммуникационного бита верхнего соседа, R - правого, B - нижнего, L - левого; Ddddd - состояние, в которое должен перейти элемент.

Первая форма записи обозначает использование прямого выхода операции "И" над результатами сравнения коммуникационных битов соседей, то есть, если элемент находится в состоянии Sssss и значения коммуникационных битов верхнего/правого/нижнего/левого соседа равны соответственно T/R/B/L, то элемент должен перейти в состояние Ddddd.

Вторая форма записи обозначает использование инверсного выхода операции "И" над результатами сравнения коммуникационных битов соседей, то есть, если элемент находится в состоянии Sssss и значение коммуникационного бита хотя бы одного из соседей НЕ соответствует указанному, то элемент должен перейти в состояние Ddddd. Как уже сказано выше, для того, чтоб получить операцию "ИЛИ" над результатами сравнения коммуникационных битов соседей, необходимо сравнивать с инвертированными значениями. Например, если нас интересует, что хотя бы у одного из соседей коммуникационный бит равен 1, то запись будет выглядеть так Sssss, ~0000 => Ddddd, то есть, элемент перейдет из состояния Sssss в состояние Ddddd в том случе, если хотя бы у одного из соседей коммуникационный бит НЕ равен 0.

Чтобы учесть маскирование, в описании функции переходов помимо символов "1" и "0" будем использовать также символ "X", обозначающий, что значение данного разряда состояния не учитывается (при сравнении), либо, что данный разряд состояния не нужно изменять (при указании нового состояния).

Те шаги , которые должны быть выполнены в тактах лавинного распространения условия перехода, будут помечены как [A].

Имитация роста биологической клетки.

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

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

Пример фрагмента описания функции переходов:

  1. XXX, XXXX => 0XX // сбросить ком. бит у всех элементов
  2. X01, XXXX => 101 // установить ком. бит у "мембран"
  3. X00, ~0000 => 001 // если у "межклеточной среды" хотя бы один из соседей - "мембрана", стать "мембраной"
  4. XXX, XXXX => 0XX // сбросить ком. бит у всех элементов
  5. X00, XXXX => 100 // установить ком. бит у "межклеточной среды"
  6. X01, 0000 => 010 // если у "мембраны" нет ни одного соседа в состоянии "межклеточная среда", стать "внутриклеточной областью"




Пример реализации параллельного сумматора.

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

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

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

Зададим состояния:

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

Пример фрагмента описания функции переходов:

  1. XXXXX, XXXX => 0XXXX // сбросить ком. бит у всех элементов
  2. X0011, XXXX => 1XXXX // если элемент является "верхним слагаемым" и значение разряда числа равно "1", установить коммуникационный бит.
  3. X01XX, XXXX => X010X // сбросим признак модификации у элементов сумматора
  4. X0100, 1XXX => 00111 // если в немодифицированном "сумматоре" значение разряда числа равно "0", а у верхнего слагаемого - "1", то установить в "сумматоре" значение "1", установить признак модификации и сбросить признак переноса.
  5. X0101, 1XXX => 10110 // если в немодифицированном "сумматоре" значение разряда числа равно "1", и у верхнего слагаемого - "1", то установить в "сумматоре" значение "0", установить признак модификации и установить признак переноса.
  6. [A] X01X1, X1XX => 101XX // если в "сумматоре" значение разряда числа равно "1" и признак переноса из предыдущего разряда равен "1", установить признак переноса. Лавинный такт.
  7. X01XX, XXXX => X010X // сбросим признак модификации у элементов сумматора
  8. X0100, X1XX => X0111 // если в немодифицированном "сумматоре" значение разряда числа равно "0", а признак переноса - "1", то установить в "сумматоре" значение "1" и установить признак модификации.
  9. X0101, X1XX => X0110 // если в немодифицированном "сумматоре" значение разряда числа равно "1", и у верхнего слагаемого - "1", то установить в "сумматоре" значение "0", установить признак модификации.
  10. X100X, X0XX => X1000 // если нет признака переноса-переполнения, то в элементе переноса/переполнения записать "0".
  11. X100X, X1XX => X1001 // если есть признак переноса-переполнения, то в элементе переноса/переполнения записать "1".

Пример сложения чисел 11010011 (десятичное 211) и 00111001 (десятичное 57). Результат - 1 00001100 (десятичное 268).



Пример направленного роста.

Смоделируем направленный рост наклонного отрезка любой ориентации (например, это может быть использовано для моделирования роста аксона). Для определенности будем моделировать приближенно прямолинейный отрезок, направленный из правого нижнего угла в левый верхний под углом a к горизонтали.

Зададим A/(1-A)=tan(a), где A - некоторое действительное число 0<=A<1. Будем суммировать число A в накапливающем сумматоре. При возникновении переноса из дробной в целую часть будем надстраивать наклонный отрезок единичным вертикальным, при отсутствии переноса - единичным горизонтальным отрезком. За N повторов данной операции возникнет int(N*A) переносов, то есть будет построено int(N*A) вертикальных отрезков и N-int(N*A)=int(N*(1-A)) горизонтальных. Таким образом мы получим tan(a)=int(N*a)/int(N*(1-A)). При любом достаточно большом N операцией извлечения целой части можно пренебречь и значение tan(a) можно считать приближенно равным N*A/(N*(A-1))=A/(1-A), то есть данный алгоритм приводит к приближению наклонного отрезка из единичных горизонтальных и вертикальных. Реализуем накапливающий сумматор как предложено в предыдущем примере, но будем считать, что в нем представлены только старшие разряды дробной части. Будем "выращивать" отрезок начиная с точки, расположенной над элементом, в котором сохраняется переполнение сумматора. Поскольку точка очередного прироста отрезка не является непосредственным соседом старшего разряда сумматора, воспользуемся самим отрезком как "транспортом", переносящим информацию о наличии/отсутствии переполнения от сумматора к точке очередного прироста. Передачу организуем с помощью лавинного распространения. В каждом цикле точка прироста с помощью лавинного распространения по элементам отрезка будет получать значение признака переполнения сумматора и в зависимости от этого состояние левого или верхнего соседа будем переводить в состояние "точка прироста".

Зададим состояния:

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

  1. // Эта часть описания функции переходов определяет функционирование сумматоров.
  2. XXXXX, XXXX => 0XXXX // сбросить ком. бит у всех элементов
  3. X0011, XXXX => 1XXXX // если элемент является "верхним слагаемым" и значение разряда числа равно "1", установить коммуникационный бит.
  4. X01XX, XXXX => X010X // сбросим признак модификации у элементов сумматора
  5. X0100, 1XXX => 00111 // если в немодифицированном "сумматоре" значение разряда числа равно "0", а у верхнего слагаемого - "1", то установить в "сумматоре" значение "1", установить признак модификации и сбросить признак переноса.
  6. X0101, 1XXX => 10110 // если в немодифицированном "сумматоре" значение разряда числа равно "1", и у верхнего слагаемого - "1", то установить в "сумматоре" значение "0", установить признак модификации и установить признак переноса.
  7. [A] X01X1, X1XX => 101XX // лавинный такт. Если в "сумматоре" значение разряда числа равно "1" и признак переноса из предыдущего разряда равен "1", установить признак переноса.
  8. X01XX, XXXX => X010X // сбросим признак модификации у элементов сумматора
  9. X0100, X1XX => X0111 // если в немодифицированном "сумматоре" значение разряда числа равно "0", а признак переноса - "1", то установить в "сумматоре" значение "1" и установить признак модификации.
  10. X0101, X1XX => X0110 // если в немодифицированном "сумматоре" значение разряда числа равно "1", и у верхнего слагаемого - "1", то установить в "сумматоре" значение "0", установить признак модификации.
  11. X100X, X0XX => X1000 // если нет переноса из самого старшего разряда, то в элементе переноса/переполнения записать "0".
  12. X100X, X1XX => X1001 // если есть перенос из самого старшего разряда, то в элементе переноса/переполнения записать "1".
  13. // Дальнейшая часть описания определяет рост отрезка. Эта часть не обязательно должна быть расположена непосредственно после предыдущей части, описывающей сумматоры.
  14. XXXXX, XXXX => 0XXXX // сбросить ком. бит у всех элементов
  15. X1001, XXXX => 1XXXX // если элемент переноса/переполнения содержит единицу - установить ком. бит.
  16. [A] X1100, ~0000 => 11100 // лавинный такт. Если хотя бы у одного из соседей элемента отрезка установлен ком. бит, установить коммуникационный бит.
  17. X1010, ~0000 => X1011 // если хотя бы у одного из соседей точки горизонтального прироста установлен ком. бит, превратить элемент в точку вертикального прироста.
  18. XXXXX, XXXX => 0XXXX // сбросить ком. бит у всех элементов
  19. X1010, XXXX => 11100 // превратить точку горизонтального прироста в элемент отрезка и установить ком. бит
  20. X0000, X1XX => 01010 // если у элемента пустого пространства элемент справа был точкой горизонтального прироста, превратить элемент в точку горизонтального прироста.
  21. XXXXX, XXXX => 0XXXX // сбросить ком. бит у всех элементов
  22. X1011, XXXX => 11100 // превратить точку вертикального прироста в элемент отрезка и установить ком. бит.
  23. X0000, XX1X => 01010 // если у элемента пустого пространства элемент снизу был точкой вертикального прироста, превратить элемент в точку горизонтального прироста.
Эволюция отрезка

Варианты реализации

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

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

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

Недостатки и преимущества аппаратной реализации клеточных автоматов с последовательным перебором возможных состояний.

Основной недостаток вышеописанной реализации - необходимость разработки и изготовления специализированных чипов, что, к сожалению, под силу только крупным производителям микроэлектроники. Но с другой стороны, разработка данного чипа сильно упрощается тем, что необходимо детально проработать только один элемент и просто "скопировать" его на одном чипе в нужном количестве экземпляров, что конечно же гораздо проще разработки микропроцессоров и других специализированных СБИС. Также можно использовать FPGA, но это на порядок снизит количество элементов на единицу площади кристалла.

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

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

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

Литература.