2

ИНСТИТУТ ВЫЧИСЛИТЕЛЬНОГО МОДЕЛИРОВАНИЯ СО РАН

На правах рукописи

Горбунова Екатерина Олеговна

КИНЕТИЧЕСКАЯ МОДЕЛЬ МЕЛКОЗЕРНИСТОГО

ПАРАЛЛЕЛИЗМА

Специальность 05.13.17 – теоретические основы информатики Диссертация на соискание ученой степени кандидата физико-математических наук

Научные руководители:

доктор физико-математических наук, профессор А.Н. Горбань, кандидат физико-математических наук, доцент Е.М.Миркес Красноярск – Оглавление Введение

Актуальность проблемы

Цель работы

Научная новизна

Практическая значимость

Апробация работы

Структура диссертации

Содержание работы

Глава 1. Известные модели мелкозернистого параллелизма и близкие к ним.

Глава 2. Основные понятия кинетической машины Кирдина. Модели выполнения и методы реализации

1. Понятие кинетической машины Кирдина

2. Модели выполнения программы

2.1. Последовательная модель

2.2. Параллельно-последовательная модель

2.3. Максимальная параллельно-последовательная модель

3. Методы реализации

3.1. Статистический метод реализации.

3.2. Решеточно-процессорный метод реализации.

Глава 3. Свойства программ, состоящих из одной команды

3.1. Распад

Применимость.

Финитность

Детерминированность.

3.2. Синтез

Применимость.

Финитность

Детерминированность.

3.3. Прямая замена

Применимость.

Финитность

Детерминированность.

Кирдина

Глава 5. Примеры применения КМК.

5.1. Бесструктурная память

5.2. Подпрограммы и структурное программирование кинетической машины Кирдина

ЗАКЛЮЧЕНИЕ

Литература

Введение Актуальность проблемы Проблема эффективного программирования при наличии мелкозернистого параллелизма пока еще далека от своего решения. Хорошо известна “гипотеза М. Минского”: производительность параллельной системы растет (примерно) пропорционально логарифму числа процессоров и уж по крайней мере является выпуклой вверх (т.е. вогнутой) функцией. Сейчас все чаще для преодоления этого ограничения применяется следующий подход: для различных классов задач строятся максимально параллельные алгоритмы решения, использующие какую-либо абстрактную архитектуру (парадигму) мелкозернистого параллелизма, а для конкретных параллельных компьютеров создаются средства реализации параллельных процессов заданной абстрактной архитектуры. В результате появляется эффективный аппарат производства параллельных программ. Модели мелкозернистого бесструктурного параллелизма могут использоваться для решения проблемы эффективного параллелизма по следующей схеме (рис 1). Новым перспективным направлением развития мелкозернистого параллелизма считается бесструктурный параллелизм, где вычислительные элементы не взаимосвязаны и хаотически взаимодействуют между собой. В данной работе рассматривается такая абстрактная парадигма параллельных вычислений – кинетическая машина Кирдина. Ожидается, что эта модель сыграет ту же роль для параллельных вычислений, что и нормальные алгоритмы Маркова, машины Колмогорова и Тьюринга или схемы Поста для последовательных вычислений.

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

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

Цель работы Целью работы является:

• Уточнение формулировки понятия кинетической машины Кирдина.

• Рассмотрение основных моделей выполнения программ кинетической машины Кирдина и методов реализации.

• Исследование применимости, детерминированности и финитности простых программ кинетической машины Кирдина и получение соответствующих критериев.

• Исследование алгоритмических возможностей кинетической машины Кирдина. Соотнесение ее со стандартными алгоритмическими формализмами и другими моделями мелкозернистого параллелизма.

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

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

Апробация работы Основные результаты работы докладывались и обсуждались на VI и VII Всероссийских семинарах «Нейроинформатика и её приложения» проходивших в Красноярске в 1998, 1999 годах, на конференциях молодых ученых Красноярского научного центра в 1998, 1999, 2000 гг., на Третьем Сибирском конгрессе по прикладной и индустриальной математике (INPRIM-98), на Первом Всесибирском конгрессе женщин-математиков в г.Красноярске в 2000 г., Всероссийской научно-технической конференции «Нейроинформатика-99» в г.Москве, VI Международной конференции «Математика. Компьютер.

Образование» в г.Пущино в 1999 г., на втором научно-практическом семинаре “Новые информационные технологии” в г.Москве в 1999 г., на XII Международной конференции по нейрокибернетике в г.Ростов-на-Дону в 1999г., на Международной конференции по нейронным сетям в Вашингтоне (США) в 1999 г., на 5 Международной конференции по параллельным компьютерным технологиям (PaCT-99) в г.Санкт-Петербурге, на третьей международной конференции вычислительных опережающих систем CASYS’ в Бельгии в 1999 г.

Структура диссертации Диссертация состоит из введения, пяти глав, заключения и списка цитируемой литературы из 75 наименований, содержит 4 рисунка и 1 таблицу.

Общий объем диссертации составляет 88 страниц.

Содержание работы В первой главе диссертации дан обзор работ по мелкозернистым параллельным вычислениям, а также работ, инспирированных химией и биологией. Показана необходимость появления нового формализма мелкозернистых параллельных вычислений – КМК. Она была предложена А.Н.Кирдиным в 1997 году на конференции «Нейроинформатика и ее приложения». Оптимизм по поводу такой модели основывается на теореме М.Д.Корзухина о том, что закрытые химические системы могут на конечных временах сколь угодно точно имитировать любую динамическую систему и теореме А.Н.Горбаня об аппроксимации химическими системами любых динамических систем.

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

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

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

Пусть L – алфавит символов. L* – множество всех конечных слов или цепочек в алфавите L. Обрабатываемой единицей является ансамбль слов M из алфавита L, который отождествляется с функцией FM с конечным носителем на L*, принимающей неотрицательные целые значения – FM: L* N {0}.

Значение FM(s) интерпретируется как число экземпляров слова s в ансамбле M.

Обработка состоит в совокупности элементарных событий, которые происходят недетерминированно и параллельно. Элементарное событие S:

M a M’ состоит в том, что из ансамбля M изымается ансамбль K– (это возможно, FM ' = FM FK + FK. Ансамбли K– и K+ однозначно задаются правилами или командами, которые объединяются в программу. Команды могут быть только трех видов:

Пусть u, w, v, f, g, k, q, s – подцепочки слов из L*.

где u, w – произвольные, v, f, g – фиксированы. Команда распада применима, если FM(uvw) > 0.

u, w – произвольные, k, q, s – фиксированы. Команда синтеза применима, если FM(uk) > 0, FM(qw) > 0.

3. Прямая замена. uvw usw u, w – произвольные, v, s – фиксированы.

Таким образом, элементарное событие S однозначно определяется правилом p, содержащимся в списке команд программы P, и ансамблем K–, определяемым этим правилом, таким, что FK–(s)FM(s) для любого s.

Допустимое элементарное событие S для ансамбля M и программы P – это такое, для которого существует правило p, содержащееся в списке команд программы P, и значения функции FM для слов, стоящих в левой части этого правила, положительны.

Скажем, что N допустимых событий совместны, если FM Fi 0, где Fi – изымаемый ансамбль для i-го события.

Ансамбль M является финальным для данной программы P, если никакая команда программы к нему не применима.

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

Программа P является детерминированной для ансамбля M, если все финальные ансамбли совпадают.

Ансамбль M будем называть «райским садом» для программы P, если он не может быть получен ни из одного ансамбля применением программы Под обозначением vf будем понимать, что цепочка v включается в слово f в качестве его подцепочки. Под обозначением vf будем понимать, что слово f не содержит цепочки v в качестве своей подцепочки.

Под обозначением vk будем подразумевать цепочку длины k, состоящую из произвольных символов алфавита L. Таким образом, мы можем работать не только с конкретными значениями, но и с переменными конечной длины. При этом в правой части команд не должно возникать неопределенности, то есть в правой части программы возможно появление только тех переменных, которые уже инициированы в левой части. Фактически, команда, содержащая символ vk является сверткой Cn команд, где n – мощность алфавита L.

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

Выделены следующие модели выполнения программ:

• Последовательная. Пусть в один дискретный момент времени происходит только одно элементарное событие из допустимых S1 : M 0 M 1, в следующий момент происходит одно из допустимых событий для ансамбля M Выбор этого события недетерминирован. Получаем ряд элементарных событий:

Если элементарные события S1 и S1 одновременно допустимы для ансамбля M 0, то оба они могут служить продолжением выполнения программы:

различны. Таким образом, для одной программы возможны различные временные ряды ансамблей. Если программа финитна, то все эти ряды конечны.

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

множество совместных событий для данного ансамбля M и программы P. Все события множества Si* происходят параллельно и приводят к ансамблю Mi, далее выполняется некоторый набор совместных событий для ансамбля Mi.

Выделение множества совместных событий S* для данного ансамбля M неоднозначно. Различные события Si* для данного ансамбля M приводят к различным ансамблям Mi. Следовательно, такой временной ряд совместных множеств элементарных событий также неоднозначен.

элементарных событий, к которому нельзя добавить ни одного допустимого события, не теряя совместности, назовем максимальным множеством совместных событий S max. К исходному ансамблю M могут быть применены несколько разных максимальных множеств совместных событий, которые порождают различные ансамбли. Таким образом, максимальная параллельно-последовательная модель также не однозначна. Переход от ансамбля M к некоторому ансамблю M’ однозначно определяется только в следующих случаях:

когда ансамблю M и программе P соответствует ровно одно допустимое событие;

(для максимальной параллельно-последовательной модели) когда весь набор допустимых событий для ансамбля M и программы P является одновременно совместным.

Рассматриваются также статистический и решеточно-процессорный методы реализации для КМК.

Статистический метод реализации в пределе больших ансамблей даст кинетическое поведение, аналогичное поведению сложной системы химических реакций (откуда, собственно, и происходит название “кинетическая машина Кирдина”). При статистической реализации каждой (i-й) команде сопоставляется некоторое неотрицательное число ri – “константа скорости”. Саму реализацию можно представить так: за малое t с вероятностью rit выбирается одна из команд-реакций, а с вероятностью 1-irit – пустая команда (ничего не происходит); вероятность выбора двух или более команд пренебрежимо мала (o(t)). Если выбрана i-я команда-реакция, то из ансамбля случайно и равновероятно выбираются слова в количестве, необходимом для выполнения команды. Если команда применима к этому набору слов, то она исполняется и переходим к следующему t, если же она неприменима, то ансамбль не изменяется, и также переходим к следующему t. В пределе t получаем случайный процесс – статистическую модель КМК.

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

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

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

Рассмотрим программу, состоящую из одной команды вида uvwuf + gw. Эта программа применима к ансамблю M, если существуют такие цепочки u, wL*, что FM(uvw) > 0.

Критерий финитности распада. Для того, чтобы программа Р, состоящая из одной команды распада uvw uf + gw, была финитна для ансамбля M необходимо и достаточно, чтобы II. для любых двух разбиений v=а1b1= а2b2, где возможно a1=a2 и b1=b2, хотя бы одно из трех условий не выполнялось:

1) f=b1b2f1, где f1 – произвольная фиксированная цепочка 2) g=g1a1a2, где g1 – произвольная фиксированная цепочка 3) существует слово uvw, FM(uvw) > 0 такое, что u=u1a1 или w=b2w1, Критерий детерминированности распада Программа распада недетерминирована, если существует разбиение цепочки v=aba и выполняется хотя бы одно из условий:

1. u,w такие, что FM(uababaw)>0;

2. f=xababay или g=xababay, где x, y – фикс. цепочки;

3. f=df1, u1,w такие, что FM(u1cvw) > 0,где cd=ababa;

4. g=g1c, u,w1 такие, что FM(uv dw1) > 0, где cd=ababa.

В остальных случаях распад детерминирован.

Для программ, состоящих из одной команды синтеза вида uk+qwusw получены следующие критерии применимости, финитности и детерминированности. Эта программа применима ко всем ансамблям, содержащим пару слов вида uk и qw. FM(uk) > 0, FM(qw) > Финитность. Очевидно, что программа всегда финитна. Она будет склеивать все пары соответствующих слов до тех пор, пока они не исчерпаются.

Детерминированность.

недетерминирована, так как склеивает произвольные цепочки неоднозначно.

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

Для программ, состоящих из одной команды прямой замены вида uvw детерминированности.

Эта программа применима к ансамблю M, если существуют такие цепочки u, wL*, что FM(uvw) > 0.

Прямая замена не изменяет количества слов в ансамбле, она будет финитна если vs.

Критерий детерминированности прямой замены Прямая замена не детерминирована, если существует разбиение цепочки v=aba и выполняется хотя бы одно из условий:

1. u,w такие, что FM(uababaw)>0;

2. s=xababay, где x, y – фикс. цепочки;

3. s=ds1, u1,w такие, что FM(u1cvw) > 0, где cd=ababa;

4. s=s1c, u,w1 такие, что FM(uv dw1) > 0, где cd=ababa;

5. s=d, u1,w1 такие, что FM(u1c v ew1) > 0, где cde=ababa;

В остальных случаях прямая замена детерминирована.

Неформально, сводя полученные результаты, можно сказать, что команды распада и прямой замены недетерминированы, если выполнены условия 1&2 или 1&3 из следующего списка.

1. Заменяемая цепочка v имеет разложение типа aba, т.е. начало и конец ее совпадают.

2. В словах, к которым применимы эти команды, встречаются цепочки вида ababa, т.е. цепочку v можно выделить двумя способами.

3. В словах, полученных после применения этих команд, встречаются цепочки вида ababa, т.е. цепочку v можно выделить двумя способами.

В четвертой главе формулируется теорема об алгоритмической универсальности КМК и она сопоставляется с другими алгоритмическими формализмами.

эквивалентна любому последовательному стандартному алгоритмическому формализму, такому как машина Тьюринга, нормальные алгоритмы Маркова, порождающие грамматики Хомского типа 0.

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

детерминированной кинетической машины Кирдина при помощи системы машин Тьюринга.

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

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

Список всех слов длины q, входящих в данный текст, называется qносителем данного текста. Рассматриваются слова, начинающиеся с любого места в тексте. Для текста длины N таких слов N-q+1. Если каждому слову qносителя сопоставить частоту его встречаемости в тексте, получим частотный словарь длины q.

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

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

Если словарь длины d содержит все слова только один раз, то по словарю длины d+1 и более текст восстанавливается однозначно. Нас будет интересовать именно этот случай. Следующая программа для кинетической машины Кирдина строит по исходному (длинному) слову его словарь длины k.

Эта программа финитна и детерминирована. Если полученный словарь не содержит полную информацию об исходном слове, то финальный ансамбль будет состоять из единственного слова – ‘!’. Это значит, что такая длина словаря недостаточна для единственного восстановления исходного слова.

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

произвольное слово длины k в исходном алфавите. Все вхождения v k в одно правило обозначают одно и то же слово. Вхождения символа v k в различные правила не связаны между собой.

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

Для этого предназначена следующаяя программа кинетической машины Кирдина.

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

В заключении суммированы основные результаты работы и сделаны выводы.

1. В работе дано формальное определение кинетической машины Кирдина.

Машина Кирдина является моделью бесструктурного мелкозернистого параллелизма. Показаны отличия кинетической машины Кирдина от аморфных и ДНК-вычислений.

2. Исследованы программы для кинетической машины Кирдина, состоящие из однотипных команд. Для таких программ получены критерии применимости программы к ансамблю, финитности и детерминированности.

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

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

Основные результаты диссертации опубликованы в /57-75/.

Глава 1. Известные модели мелкозернистого параллелизма и близкие к ним.

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

Теория нейронных сетей хорошо развитая область науки. С помощью нейронных сетей решаются широкие классы задач /3,4/, для этого используются как имитаторы нейронных сетей на обычных персональных компьютерах, так и специальные нейропроцессоры, сделаны попытки структурно-функциональной стандартизации нейросетей /5/. Широкие вычислительные способности нейросетей подтверждаются теоремой об универсальных аппроксимационных возможностях произвольной нелинейности: с помощью линейных операций и суперпозиций функции одного переменного можно из произвольного нелинейного элемента получить устройство, вычисляющее любую непрерывную функцию многих переменных с любой наперед заданной точностью /6/. Это приближение осуществляется нейронными сетями. Каждая сеть состоит из формальных нейронов. Нейрон получает на входе вектор сигналов x, вычисляет его скалярное произведение на вектор весов и некоторую функцию одного переменного ((x,)). Результат рассылается на входы других нейронов или передается на выход. Таким образом, нейронные сети вычисляют суперпозиции простых функций одного переменного и их линейные комбинации.

Кроме нейронных сетей существуют и другие перспективные идеи и подходы к построению моделей мелкозернистого параллелизма.

Хорошо известна “гипотеза М. Минского” /7/, что производительность параллельной системы растет (примерно) пропорционально логарифму числа процессоров и уж по крайней мере является выпуклой вверх (т.е. вогнутой) функцией. Сейчас все чаще для преодоления этого ограничения применяется следующий подход. Для различных классов задач строятся максимально параллельные алгоритмы решения, использующие какую-либо абстрактную архитектуру (парадигму) мелкозернистого параллелизма, а для конкретных параллельных компьютеров создаются средства реализации параллельных процессов заданной абстрактной архитектуры. В результате появляется мелкозернистого бесструктурного параллелизма могут использоваться для решения проблемы эффективного параллелизма по следующей схеме (рис. 1).

происходят от клеточных автоматов фон-Неймана, но имеют более сильные выразительные возможности. PSA способны обрабатывать многомерные массивы данных, представляемые в виде множества клеток (a,x), где a – данное, x –место данного в массиве. Место представляется вектором координат узла целочисленной n-мерной решетки, x=x1,…,xn. Множество {a}=A – алфавит состояний клетки, {x}=M –множество имен всех данных массива. Множество M считаем конечным, множество одинаковыми именами, называем словом. Результатом применения подстановки П : S1 ( x ) S 2 ( x ) S 3 ( x ) к слову W A M является слово W, которое получается из слова W путем изъятия всех слов S1 (mi ), mi M, i = 1,...h, находящихся в контексте S 2 (mi ), и присоединения к оставшейся части всех слов S 3 (mi ), т.е.

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

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

{K m }m=1,...,M, (M 1) – конечный набор элементарных преобразований частичных отображений K m : X 2 X 2 ; 0 –начальное состояние решетки Z Z X.

Машина статистических клеточных автоматов (SCAM) определяется автоматов, рассматриваемый вместе с некоторым “генератором” случайных состояния (0 ), (1)... таких, что t 0 = 0 и (0 ) = 0. Функция состояния t является постоянной в промежутке от одного критического момента t s до следующего t s +1, то есть и если обозначить через ( s ) состояние функции t в момент времени t = t s, то t = ( s ) для всех t в интервале t s t < t s +1. Каждый критический момент t s +1, s N, соответствует микрошагу метода Монте-Карло ( s ) = = ( s +1), состоящему в попытке трансформации текущего состояния случайно выбранной пары соседних ячеек при помощи случайно выбранного правила K m, m = 1,...M.

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

Теорию клеточных автоматов и некоторых классов нейронных сетей объединили в себе клеточно-нейронные сети /13/. Их применяют в обработке визуальной информации /14/. КНС изучаются для порождения статистических и динамических образов /15/, бегущего фронта, спиральных и круговых волн /16/, пространственно-временного хаоса. КНС представляют собой множество клеток, обычно расположенных в узлах ортогональной или гексагональной решетки, либо в вершинах регулярного графа. Каждая клетка имеет взвешенные связи со своим ближайшим окружением, и характеризуется внутренним состоянием, выходом и, возможно, смещением. На первом этапе все клетки устанавливаются в начальное состояние, после чего начинается процесс вычисления в сети, который может быть как непрерывным по времени, так и дискретным, в зависимости от модели. Существуют дискретные и непрерывные модели. В процессе функционирования дискретной модели все клетки синхронно вычисляют взвешенную сумму от состояния выходов своих соседей, в соответствии с которой меняется их внутреннее состояние. Выход клетки получается как нелинейная функция ее внутреннего состояния. В процессе функционирования непрерывной модели процесс вычисления не разделен на дискретные интервалы времени.

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

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

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

Примером таких исследований, является направление по созданию и изучению искусственных иммунных систем (ИИС) /18/. ИИС – это высоко распределенные системы, базирующиеся на принципах природной системы иммунитета. Это новая и быстро растущая область предоставляет широкие возможности в обработке информации для решения сложных задач. Как и нейронные сети, искусственные иммунные системы могут обучаться, использовать информацию, полученную в процессе обучения и распознавать образы в сильно децентрализованном случае. Естественная иммунная система является сложной адаптивной системой, которая использует различные сложные механизмы для защиты от внешних патогенов. Основная роль иммунной системы состоит в распознавании всех клеток или молекул в теле и классифицируются, чтобы индуцировать подходящий тип защитного механизма.

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

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

- вычислительные методы, базирующиеся на иммунологических принципах /19/, - когнитивные иммунные модели, - искусственные иммунные системы для распознавания образов /20/, - искусственные иммунные системы для определения аномалий или ошибок /21/, - многоагентные системы, базирующиеся на принципах иммунных систем, - системы для самоорганизации, базирующиеся на принципах иммунных систем, - иммунный подход к коллективному интеллекту, - иммунные системы для поиска и оптимизации /22/, - иммунные системы как автономные децентрализованные системы /23/, - иммунно-базирующийся подход к искусственной жизни /24/, - иммунный подход к компьютерной и интернет-безопасности, - иммунная система, как метафора обучающейся системы /20/, - иммунологические вычисления для информационного анализа данных, - системы обработки образов и сигналов, базирующиеся на принципах иммунных систем /25/.

Е.А. Либерман с 1972 года опубликовал ряд статей о молекулярной вычислительной машине клетки (МВМ) /26-29/. Клеткой управляет молекулярная универсальная вычислительная машина параллельнопоследовательного действия. Эта машина производит операции над молекуламисловами (ДНК, РНК, белок) по программе, записанной на РНК и ДНК. Операции производят молекулярные устройства РНК- и ДНК-полимеразы, лигазы, протеиназы и т.д., которые сами состоят из молекул белка и РНК.

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

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

Молекулярная вычислительная машина является «идеальной», так как за каждый шаг направленного вычисления затрачивается минимально необходимая порция свободной энергии (обычно энергия гидролиза химической связи или энергия взаимодействия комплементарных частей молекул), а поиск (перебор) идет без затраты свободной энергии за счет теплового движения молекул. Тепловое движение позволяет комплементарным поверхностям молекул найти друг друга. За ускорение поиска можно «платить», размножая молекулы. Другой важный вид теплового поиска – перебор слов из алфавита полинуклеотидфосфорилазой. Всевозможные комбинации синтезируются этим ферментом из нуклеозиддифосфатов.

«Связь физической энтропии и информации» для молекулярной вычислительной машины имеет реальный физический смысл: вводится понятие «цена действия» D, равная произведению свободной энергии, затраченной на одну операцию, и времени этой операции. Для направленного вычисления в МВМ D=ET1013h. Для перебора D103h, где h – постоянная Планка.

Представляет определенный интерес модель биологической ассоциативной памяти и сознания Н.Г.де Брюйна /30/. Важное свойство модели состоит в том, что задачи ассоциативной памяти распределяются на большое число локальных агентов (таких, как нейроны или локальные нейронные сети) без использования какой-либо адресной системы. Идея состоит в том, что в каждый момент времени t только сравнительно маленькое подмножество A(t) из множества всех агентов бодрствует. Эти агенты сохраняют информацию о данном моменте. В момент t+p пересечение множеств A(t) и A(t+p) может дать ответы на вопросы о том, что случилось в момент t. Если определение множества A(t) сгенерировано надлежаще параметризованным случайным процессом, можно гарантировать, что такое пересечение почти всегда не пусто.

Таким образом, можно видеть, что способность системы должна быть примерно пропорциональна квадратному корню размера системы. Если мы возьмем число агентов порядка 1010,то возможность системы легко может оказаться в 104 раз больше, чем способность одного агента, и система может быть много более надежной, чем единичный агент.

Важная часть этого, названная автором «сознанием», связана с тем, что центральный процессор мозга имеет очень сильно связан с тем, что было запомнено в течение последней секунды. Это может быть понятно из реализации, при которой A(t) меняется очень медленно: если p порядка секунды, то пересечение A(t) и A(t+p) может быть очень большим.

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

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

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

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

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

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

• Отдельные процессоры идентичны и массово производятся.

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

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

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

• Процессоры распределяются плотно и случайно с одним и тем же распределением.

• Процессоры ненадежны. Чтобы производство большого количества процессоров было дешевым, нужно отказаться от тестирования каждого процессора при производстве. Более того, все процессоры неизбежно ошибочны. Нечувствительность к ошибкам достигается избыточностью вместо уверенности в совершенстве аппаратуры.

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

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

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

В /33/ предложены алгоритмы для восстановления координатной системы из локальной информации процессоров аморфного компьютера.

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

В 1994 году Леонард Адлеман /34,35/ использовал фрагменты ДНК для решения задачи теории сложных графов. Метод Адлемана использует последовательности из кусков молекул ДНК для представления вершин графа.

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

Такой тип ДНК-компьютера может рассматривать много решений задачи одновременно, как компьютеры с более, чем одним процессором. Кроме того, число ДНК-цепочек, участвующих в таких вычислениях ( примерно 1023), на много порядков больше и они значительно плотнее упакованы, чем процессоры в современных суперкомпьютерах /36/.

Липтон /37/ при помощи ДНК-компьютера показал, что задача выполнимости для формул в конъюнктивной нормальной форме может быть решена за время, линейно зависящее от размера формулы. Ключевое улучшение его метода состоит в том, что он работает для более общего класса задач, причем число используемых ДНК цепочек 2n, где n – число переменных, в то время, как для Адлеману потребовалось n! ДНК-цепочек для решения более частной задачи.

При помощи ДНК-компьтера предложены также решения других комбинаторных NP-полных задач /38-41/.

Модель ДНК-вычислений состоит в следующем /42,43/. ДНК-цепочка является природным полимером, состоящим из четырех типов нуклеотидов, различающихся по базе, которую они содержат; базы называются A, C, G и T.

Концы ДНК-цепочки различны и соответственно называются 3’end и 5’end. Две ДНК-цепочки могут формировать (при определенных условиях) двойную цепочку, если их соответствующие базы комплементарны друг другу – A согласовывается с T, а С согласовывается с G.

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

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

2. Используя определенные энзимы, можно разрезать ДНК-цепочки в определенном месте.

3. Можно разделить ДНК-цепочки по длине, используя гель-электрофорез.

4. Можно определить, существует ли определенная ДНК-цепочка в тестовой пробирке, т.е. «прочитать» последовательность баз ДНК-цепочки.

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

6. Пусть дана некая одинарная ДНК-цепочка, возможно, нам нужно будет создать ее комплементарную цепочку. Для ее получения используется энзим ДНК полимераза. ДНК-полимераза будет «читать» данную цепочку-шаблон в направлении 3’5’ и строит комплементарную цепочку в направлении 5’3’, один нуклеотид за раз. Для этой операции на самом деле требуется, чтобы небольшая часть шаблона была двойная. В конце этого короткого комплиментарного куска энзим добавляет новый нуклеотид.

7. Репликация. Иногда необходимо создавать копии всех ДНКцепочек в пробирке. Это может быть сделано при помощи прямого прохода цепной реакции полимеразы.

8. Объединение. Иногда нужно удлинить все ДНК-цепочки в пробирке, присоединяя другие короткие цепочки в конец. Эта операция выполняется сложнее, чем другие и для нее также требуются определенные энзимы.

Подобно компьютеру с более, чем одним процессором, такой тип ДНКкомпьютера способен рассматривать много решений задачи одновременно.

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

С помощью ДНК-вычислений предложен также алгоритм взлома 64битного кода /44/, разработаны специальные способы кодирования информации при помощи ДНК-цепочек, которые позволяют быть ДНК вычислениям устойчивыми к ошибкам. С помощью ДНК решают задачи динамического программирования /45/ и линейной алгебры /46/.

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

В этой работе рассматривается идеальная ансамблевая модель мелкозернистого параллелизма, построенная по типу химических реакций в жидкости или газе, – кинетическая машина Кирдина. Она была предложена А.Н.Кирдиным /48/ в 1997 году на конференции «Нейроинформатика и ее приложения». Наш оптимизм по поводу такой модели основывается на теореме М.Д.Корзухина /49/ о том, что закрытые химические системы могут на конечных временах сколь угодно точно имитировать любую динамическую систему и теореме А.Н.Горбаня /50/ об аппроксимации химическими системами любых динамических систем.

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

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

Глава 2. Основные понятия кинетической машины Кирдина. Модели выполнения и методы реализации 1. Понятие кинетической машины Кирдина Впервые кинетическая машина Кирдина была введена А.Н.Кирдиным /48/ в 1997 году в тезисах всероссийского семинара «Нейроинформатика и ее приложения». Были даны понятия ансамбля и программы, финального ансамбля, детерминированности и финитности программы. Причем основными командами были названы только распад и синтез. В данной главе мы даем более формальное определение кинетической машины Кирдина и вводим еще один тип команд – прямая замена.

Определение формального вычислителя состоит в определении объекта обработки и самого процесса обработки.

Пусть L – алфавит символов. L* – множество всех конечных слов или цепочек в алфавите L. Обрабатываемой единицей является ансамбль слов M из алфавита L, который отождествляется с функцией FM с конечным носителем на L*, принимающей неотрицательные целые значения – FM:L* N {0}. Значение FM(v) интерпретируется как число экземпляров слова v в ансамбле M.

Обработка состоит в совокупности элементарных событий, которые происходят недетерминированно и параллельно. Элементарное событие S:

M a M’ состоит в том, что из ансамбля M изымается ансамбль K– (это возможно, FM ' = FM FK + FK. Ансамбли K– и K+ однозначно задаются правилами или командами, которые объединяются в программу. Команды могут быть только трех видов:

Пусть u, w, v, f, g, k, q, s – терминальные символы, обозначающие некоторые цепочки символов из L, являющиеся подцепочками слов из L*.

где u, w – произвольные, v, f, g – фиксированы. Распад однозначно задается тройкой цепочек (v, f, g). Обозначим P1 множество таких троек.

При применении этой команды функция FM изменит свои значения следующим образом:

FM’(uvw) = FM(uvw)–1, FM’(uf) = FM(uf)+1, FM’(gw) = FM(gw)+1.

Команда распада применима, если FM(uvw) > 0.

u, w – произвольные, k, q, s – фиксированы. Синтез однозначно задается тройкой цепочек (k, q, s).Обозначим P2 множество таких троек.

При применении этой команды функция FM изменит свои значения следующим образом:

FM’(uk) = FM(uk)–1, FM’(qw) = FM(qw)–1, FM’(usw) = FM(usw)+1.

Команда синтеза применима, если FM(uk) > 0, FM(qw) > 0.

3. Прямая замена. uvw usw u, w – произвольные, v, s – фиксированы. Прямая замена однозначно задается парой цепочек (v, s). Обозначим P3 множество таких пар.

При применении этой команды функция FM изменит свои значения следующим образом:

FM’(uvw) = FM(uvw)–1, FM’(usw) = FM(usw)+1.

Команда прямой замены применима, если FM(uvw) > 0.

Программа P применима к ансамблю M, если хотя бы одна его команда применима к M. Программа P однозначно определяется множествами P1, P2 и P3.

Таким образом, элементарное событие S однозначно определяется правилом p, содержащимся в списке команд программы P, и ансамблем K–, определяемым этим правилом, таким, что FK–(v)FM(v) для любого v.

Допустимое элементарное событие S для ансамбля M и программы P – это такое, для которого существует правило p, содержащееся в списке команд программы P, и значения функции FM для слов, стоящих в левой части этого правила, положительны.

Скажем, что N допустимых событий совместны, если FM Fi 0, где Fi – изымаемый ансамбль для i-го события.

Ансамбль M является финальным для данной программы P, если никакая команда программы к нему не применима.

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

Программа P является детерминированной для ансамбля M, если все финальные ансамбли совпадают.

Ансамбль M будем называть «райским садом» для программы P, если он не может быть получен ни из одного ансамбля применением программы P.

Под обозначением vf будем понимать, что цепочка v включается в слово f в качестве его подцепочки. Под обозначением vf будем понимать, что слово f не содержит цепочки v в качестве своей подцепочки.

Под обозначением vk будем подразумевать цепочку длины k, состоящую из произвольных символов алфавита L. Таким образом, мы можем работать не только с конкретными значениями, но и с переменными конечной длины. При этом в правой части команд не должно возникать неопределенности, то есть в правой части программы возможно появление только тех переменных, которые уже инициированы в левой части. Фактически, команда, содержащая символ vk является сверткой Cn команд, где n – мощность алфавита L.

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

2. Модели выполнения программы Элементарные события в кинетической машине Кирдина происходят недетерминированно и параллельно. Можно предложить некоторые простые варианты модели выполнения программы P.

2.1. Последовательная модель Пусть в один дискретный момент времени происходит только одно элементарное событие из допустимых S1 : M 0 M 1, в следующий момент происходит одно из допустимых событий для ансамбля M 1 Выбор этого события недетерминирован. Получаем ряд элементарных событий:

Если элементарные события S1 и S1 одновременно допустимы для ансамбля M 0, то оба они могут служить продолжением выполнения программы:

различны. Таким образом, для одной программы возможны различные временные ряды ансамблей. Если программа финитна, то все эти ряды конечны.

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

2.2. Параллельно-последовательная модель Обозначим Si* некоторое множество совместных событий для данного ансамбля M и программы P. Все события множества Si* происходят параллельно и приводят к ансамблю Mi, далее выполняется некоторый набор совместных событий для ансамбля Mi.

Разбиение на множества совместных событий S* для данного ансамбля M неоднозначно. Различные события Si* для данного ансамбля M приводят к различным ансамблям Mi. Следовательно, такой временной ряд совместных множеств элементарных событий также неоднозначен.

Пример. Пусть программа P для кинетической машины Кирдина состоит из одной команды и имеет следующий вид: uK + Qw uXw.

Ансамбль M отождествляем с функцией FM:

FM (AK)=1, FM (BK)=1, FM (QA)=1, FM (QB)=1.

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

1. Слова AK, QA определяют элементарное событие S1;

2. Слова AK, QB определяют элементарное событие S2;

3. Слова BK, QA определяют элементарное событие S3;

4. Слова BK, QB определяют элементарное событие S4.

Нетрудно заметить, что не все из этих допустимых событий совместны.

Выпишем полный список множеств совместных элементарных событий:

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

2.3. Максимальная параллельно-последовательная модель Множество элементарных событий, к которому нельзя добавить ни одного множеством совместных событий S max. В предыдущем примере множества S и S 6 являются максимальными множествами совместных событий. То есть к исходному ансамблю M может быть применено два разных максимальных множества совместных событий, которые порождают различные ансамбли. Мы видим, что максимальная параллельно-последовательная модель также не однозначна. Переход от ансамбля M к некоторому ансамблю M’ однозначно определяется только в следующих случаях:

когда ансамблю M и программе P соответствует ровно одно допустимое событие;

(для максимальной параллельно-последовательной модели) когда весь набор допустимых событий для ансамбля M и программы P является одновременно совместным.

3. Методы реализации 3.1. Статистический метод реализации.

Представляет интерес “ статистический ” метод реализации КМК. В пределе больших ансамблей он даст кинетическое поведение, аналогичное поведению сложной системы химических реакций (откуда, собственно, и происходит название “кинетическая машина Кирдина”). При статистической реализации каждой (i-й) команде сопоставляется некоторое неотрицательное число ri – “константа скорости”. Саму реализацию можно представить так: за малое t с вероятностью rit выбирается одна из команд-реакций, а с вероятностью 1-irit – пустая команда (ничего не происходит); вероятность выбора двух или более команд пренебрежимо мала (o(t)). Если выбрана i-я команда-реакция, то из ансамбля случайно и равновероятно выбираются слова в количестве, необходимом для выполнения команды. Если команда применима к этому набору слов, то она исполняется, и переходим к следующему t, если же она неприменима, то ансамбль не изменяется, и также переходим к следующему t. В пределе t0 получаем случайный процесс – статистическую модель КМК.

3.2. Решеточно-процессорный метод реализации.

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

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

Будет удобно без потери общности разделить временные интервалы движения и взаимодействия. Пусть они чередуются, то есть за интервалом взаимодействия tcomm всегда следует интервал движения ttrans. В начальный момент все слова некоторым заранее заданным или случайным образом размещаются в пространстве. В интервал движения слова ансамбля не изменяются, а только перемещаются. В интервал взаимодействия происходит следующее. Введем некоторый радиус r. Если некоторый набор слов из ансамбля попадает в rокрестность какого-нибудь процессора, то в интервал взаимодействия процессор пытается применить ко всем словам, попавшим в его окрестность команды программы кинетической машины Кирдина, которые приписаны этому процессору. Набор команд для каждого процессора, находящегося в одном из узлов решетки, одинаков. Теперь во взаимодействия могут вступать не все слова ансамбля, а только те, которые оказываются близко друг к другу.

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

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

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

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

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

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

Эта программа применима к ансамблю M, если существуют такие цепочки u, wL*, что FM(uvw) > 0.

Лемма 1. Программа Р, состоящая из одной команды распада uvw uf + gw не будет финитной, если v f или v g.

Доказательство. Пусть v f или v g,т.е. команда программы имеет вид применение программы порождает новую цепочку uf1vf2 или g1vg2w, к которой опять применима программа и т.д. бесконечно. Лемма доказана.

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

Пример. uAwuAB+BAw. Программа применима к любому ансамблю, хотя бы одно слово которого содержит символ А. При каждом распаде такого слова будут порождаться еще два слова, к которым применима эта программа, поэтому такая программа не будет финитной.

Лемма 2. Программа Р, состоящая из одной команды распада uvw uf + gw не будет финитной для ансамбля M, если 1) существует два, возможно одинаковых разбиения цепочки v=a1b1=a2b2;

2) f=b1b2x, g=ya1a2, где x и y– некоторые фиксированные цепочки;

3) Существует слово uvw (FM(uvw) > 0) такое, что u=u1a1 или w=b2w1.

Доказательство. По условиям леммы:

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

Разберем распад слова u1a1vw:

1) {u1a1vw} a {u1a1b1b2x, ya1a2w};

{u1a1b1b2x} a {u1 b1b2x, ya1a2b2x};

{ya1a2b2x} a {ya1b1b2x, ya1a2x}.

4) слово ya1b1b2x содержит цепочку a1b1b2, как и слово u1a1b1b2x, распад которого разбирался в пункте 2). Это слово породит слово, содержащее цепочку a1a2b2, распад которого разбирался в пункте 3). И так бесконечно на каждом шаге распада будут поочередно порождаться слова, содержащие цепочки a1b1b2 или a1a2b2.

Теперь разберем распад слова uvb2w1:

1) { uvb2w1} a {ub1b2x, ya1a2b2w1};

2) слово ya1a2b2w1 содержит цепочку a1a2b2, оно, как и в предыдущем случае, породит слово, содержащее цепочку a1b1b2 и т. д.

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

Критерий финитности распада. Для того, чтобы программа Р, состоящая из одной команды распада uvw uf + gw, была финитна для ансамбля M необходимо и достаточно, чтобы II. для любых двух разбиений v=а1b1= а2b2, где возможно a1=a2 и b1=b2, хотя бы одно из трех условий не выполнялось:

или w=b2w1, где u1 и w1 –произвольные цепочки.

Доказательство.

Построим для него в виде двоичного дерева вывод всех возможных слов. Во второй строчке каждого узла дерева будем обозначать условия, при которых к данному слову применима программа распада, в третьей строчке будет вид данного слова при этих условиях. Потомок наследует условия всех своих предков. Стрелкой влево будем показывать слово вида uf, стрелкой вправо – gw. Правую и левую ветви дерева приведем отдельно.

Дадим пояснения к схемам. Самая левая ветвь максимально будет иметь длину равную u при условии, что подцепочка u имеет вид a1...a1a2, в остальных случаях эта ветвь будет короче. Вправо на каждом шаге она будет порождать слово gf1, условия распада которого аналогичны ветви 1.2. Ветвь 1.2 вправо максимально будет иметь длину равную f при условии, что подцепочка f имеет вид b1b2...b2, в остальных случаях эта ветвь будет короче.

Рис.3. Левая ветвь дерева распада.

Рис.4. Правая ветвь дерева распада.

Дадим пояснения к схемам. Самая левая ветвь максимально будет иметь длину равную u при условии, что подцепочка u имеет вид a1...a1a2, в остальных случаях эта ветвь будет короче. Вправо на каждом шаге она будет порождать слово gf1, условия распада которого аналогичны ветви 1.2. Ветвь 1. вправо максимально будет иметь длину равную f при условии, что подцепочка f имеет вид b1b2...b2, в остальных случаях эта ветвь будет короче.

Влево на каждом шаге ветвь 1.2 будет порождать цепочки вида g1b1b2...b2f, которые получены при условии f=b1b2f2, а их распад возможен только в случае если g=g2a1a2, а это противоречит условиям критерия.

переобозначений.

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

Пример. Нефинитная программа: uabw ubb + aaw Пусть слово aabM.

aab{abb,aa};

abb{bb,aab}.

Получили слово aab, с которого начали. К нему данная программа также применима.

Детерминированность.

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

Пусть цепочка v включена в слово h (FM(h)>0) более одного раза, не пересекаясь. Т.е. слово h можно представить в виде u1v(1)u2v(2)…unv(n)w, где n– число включений v в h. Элементарные события, происходя в любом порядке, разобьют слово h на n+1 слова: u1f, gu2f, …, gunf, gw и тогда программа будет детерминирована на ансамбле, состоящем из данного слова.

Критерий детерминированности распада Программа распада недетерминирована, если существует разбиение цепочки v=aba и выполняется хотя бы одно из условий:

1. u,w такие, что FM(uababaw)>0;

2. f=xababay или g=xababay, где x, y – фикс. цепочки;

3. f=df1, u1,w такие, что FM(u1cvw) > 0,где cd=ababa;

4. g=g1c, u,w1 такие, что FM(uv dw1) > 0, где cd=ababa.

В остальных случаях распад детерминирован.

Доказательство. По условию uabaw uf+gw.

1. u,w такие, что FM(uababaw)>0. К слову uababaw распад применим двумя способами:

uababaw uf+gbaw и uababaw uabf+gw, что приведет к двум различным ансамблям. Следовательно, в этом случае распад недетерминирован.

2. f=xababay или g=xababay, где x, y – фикс. цепочки.

Команда распада имеет один из следующих видов:

uabaw uxababay + gw;

uabaw uf+gxababay;

uabaw uxababay+gx1ababay1.

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

3. f=df1, u1,w такие, что FM(u1cvw) > 0,где cd=ababa.

Здесь cd – это некоторое, возможно, другое разбиение цепочки ababa.

Команда распада принимает вид:

uabaw udf1+gw.

Применением программы к слову u1cvw получаем два слова u1cdf1 и gw.

недетерминированно (см. пункт 1) 4. g=g1c, существуют u,w1 такие, что FM(uvdw1) > 0, где cd=ababa.

Команда распада принимает вид:

uabawuf+g1cw.

Применением программы к слову uvdw1 получаем два слова uf и g1cdw.

недетерминированно (см. пункт 1) Если существует разбиение цепочки v=aba, но не выполняется ни одно из условий 1)-4), то в исходном ансамбле, а также во всех ансамблях, полученных элементарными событиями из исходного, не появляется слова, содержащего цепочку ababa. Следовательно, такой распад также будет детерминирован.

Пусть цепочку v невозможно представить в виде цепочки aba, тогда невозможны пересекающиеся включения v ни в какое слово.

Следовательно, невозможна недетерминированность ни для какого ансамбля.

Критерий детерминированности распада доказан.

Пример. uABABw uf + gw, FM(ABABAB)>0.

Цепочка v представима в виде разбиения aba: a=AB, b– пустая цепочка.

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

FM1(f)=1, FM1(gAB)=1;

FM2(Abf)=1, FM2(g)=1.

Ансамбль «Райский сад» для программы распада не содержит ни одной пары цепочек uf и gw.

Рассмотрим программу, состоящую из одной команды вида Эта программа применима ко всем ансамблям, содержащим пару слов вида uk и qw. FM(uk) > 0, FM(qw) > Очевидно, что программа всегда финитна. Она будет склеивать все пары соответствующих слов до тех пор, пока они не исчерпаются.

Детерминированность.

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

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

Доказательство.

1. Пусть в исходном ансамбле FM(uk)=n, FM(qw)=m, где u и w – некоторые фиксированные цепочки, и других слов вида uk и qw нет. Финальным ансамблем для данного ансамбля будет всегда следующий: