автореферат диссертации по информатике, вычислительной технике и управлению, 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. Прямая замена.

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

Финитность.

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

Глава 4. Алгоритмическая универсальность кинетической машины

Кирдина.

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

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

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

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

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

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

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

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

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

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

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

• Применение кинетической машины Кирдина для решения модельных задач.

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

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

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

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

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

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

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

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

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

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

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

Хорошо известна "гипотеза М. Минского" /7/, что производительность параллельной системы растет (примерно) пропорционально логарифму числа процессоров и уж по крайней мере является выпуклой вверх (т.е. вогнутой)

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

Алгоритмы параллельных подстановок (PSA) /8,9/ концептуально происходят от клеточных автоматов фон-Неймана, но имеют более сильные выразительные возможности. PSA способны обрабатывать многомерные массивы данных, представляемые в виде множества клеток (а,х), где а - данное, х -место данного в массиве. Место представляется вектором координат узла целочисленной «-мерной решетки, х-х],.,х„. Множество [а}=А - алфавит состояний клетки, {х}=М -множество имен всех данных массива. Множество М считаем конечным, множество {(a,x)}cixM, в котором нет клеток с одинаковыми именами, называем словом. Результатом применения подстановки П:S,(x)*S2(х)S^x) к слову W с АхМ является слово W', которое получается из слова W путем изъятия всех слов Sl(mj),mj eM,i = \,.h, находящихся в контексте 52(«1,.), и присоединения к оставшейся части всех слов 53 (т1), т.е.

W' = j^HJS, (mjju jys^m, )j. Концепция контекста позволяет выразить управляющие функции прямо в представлении алгоритма. Базируясь на PSA-концепции, разработана теория, содержащая условия корректности, эквивалентные преобразования и ряд методов для синтеза алгоритма и архитектуры. Система, моделирующая вычисления на ПК, позволяет конструировать клеточные алгоритмы и наблюдать процесс вычислений в динамике.

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

Статистический клеточный автомат (SCA) - это кортеж [х,М,{Кт}т=1 где Х- количество возможных состояний для каждого SCA;

Кт}т=1 м,(М > l) - конечный набор элементарных преобразований частичных отображений Кт :X2 -»X2; -начальное состояние решетки Z х Z X .

Машина статистических клеточных автоматов (SCAM) определяется как следующий алгоритм функционирования статистических клеточных автоматов, рассматриваемый вместе с некоторым "генератором" случайных чисел а0,а,,. Реализация процесса £ состоит из последовательности критических моментов времени t0<tx<. и соответствующих функций состояния таких, что (0=0 и £(0)=£0. Функция состояния £ является постоянной в промежутке от одного критического момента ts до следующего tx+l, то есть и если обозначить через ^ состояние функции £ в момент времени t = ts, то = для всех t в интервале ts < t < ts+l. Каждый критический момент ts+i, s<=N, соответствует микрошагу метода Монте-Карло = состоящему в попытке трансформации текущего состояния случайно выбранной пары соседних ячеек при помощи случайно выбранного правилаКт,т = 1 ,.М.

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

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

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

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

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

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

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

- когнитивные иммунные модели,

- искусственные иммунные системы для распознавания образов /20/,

- искусственные иммунные системы для определения аномалий или ошибок/21/,

- многоагентные системы, базирующиеся на принципах иммунных систем,

- системы для самоорганизации, базирующиеся на принципах иммунных систем,

- иммунный подход к коллективному интеллекту,

- иммунные системы для поиска и оптимизации /22/,

- иммунные системы как автономные децентрализованные системы /23/,

- иммунно-базирующийся подход к искусственной жизни /24/,

- иммунный подход к компьютерной и интернет-безопасности,

- иммунная система, как метафора обучающейся системы /20/,

- иммунологические вычисления для информационного анализа данных,

- системы обработки образов и сигналов, базирующиеся на принципах иммунных систем /25/.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Модель ДНК-вычислений состоит в следующем /42,43/. ДНК-цепочка является природным полимером, состоящим из четырех типов нуклеотидов, различающихся по базе, которую они содержат; базы называются А, С, G и Т. Концы ДНК-цепочки различны и соответственно называются 3'end и 5'end. Две ДНК-цепочки могут формировать (при определенных условиях) двойную цепочку, если их соответствующие базы комплементарны друг другу - А согласовывается с Т, а С согласовывается с G.

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

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

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

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

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

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

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

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

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

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

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

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

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

1. Горбань А.Н., Россиев Д.А. Нейронные сети на персональном компьютере-Новосибирск: Наука, 1996.

2. Горбань А.Н. Обучение нейронных сетей. М.: изд. СССР-США СП «ParaGraph», 1990.-160 с.

3. Нейроинформатика / А.Н.Горбань, В.Л.Дунин-Барковский, А.Н.Кир дин, Е.М.Миркес, А.Ю.Новоходько, Д.А.Россиев, С.А.Терехов, М.Ю.Сенашова, В.Г.Царегородцев.-Новосибирск: Наука, Сибирское предприятие РАН, 1998.-296 с.

4. Методы нейроинформатики: Сборник научных трудов / Под ред. А.Н. Горбаня; отв. за вып. М.Г. Доррер. Красноярск; КГТУ. 1998.

5. Миркес Е.М. Нейрокомпьютер. Проект стандарта. Новосибирск: Наука. Сибирское предприятие РАН, 1999.

6. Горбань А.Н. Обобщенная аппроксимационная теорема и вычислительные возможности нейронных сетей // Сибирский журнал вычислительной математики. -1998. Т. 1, № 1. - С. 12-14.

7. Лекции лауреатов премии Тьюринга: Пер. с англ./ Под ред. Р.Эшенхёрста-М.: Мир, 1993,—560с.

8. Ачасова С.М., Бандман О.Л. Корректность параллельных вычислительных процессов-Новосибирск: Наука. Сиб. Отд-ние, 1990 -253с.

9. Achasova S., Bandman О., Markova V. and Piskunov S. Parallel substitution algorithm. Theory and Application.- WORD SCIENTIFIC, 1994.

10. Ю.Латкин Е.И. SCAM: химический компьютер // Теория вычислений и языки спецификаций Новосибирск, 1995 - Вып. 152: Вычислительные системы1. С. 140-151.

11. С.Е.Гилев, А.Н.Горбань, В.И.Быков, Г.С.Яблонский. Имитационное моделирование процессов на поверхности катализатора. Доклады АН СССР, 1982, т.262, № 6.

12. В.И.Быков, С.Е.Гилев, А.Н.Горбань, Г.С.Яблонский. Имитационное моделирование диффузии на поверхности катализатора. Доклады АН СССР, 1985, т.283, № 5.

13. Chua L.O., Yang L. Cellular Neural Networks: Theory and Application. IEEE Trans. Circuits and Systems, CAS-35, 1998. 1257-1290 pp.

14. M. Brucoli, L.Carnimeo, G.Grassi. A Global Approach To The Design of Discrete-Time Cellular Neural Networks For Associative Memories. Int. Journ. Of Circ. Theory and Appl. vol.24, 1997, p.489-510.

15. P.Thiran, K.Crounse, L.O.Chua, M.Hasler. Pattern Formation Propeties of of Autonomous Cellular Neural Networks. IEEE trans. On circ. And syst.-l: fund. Theory and appl., vol.42, No 10, 1995.

16. Селихов A.B. Условия формирования автоволнового процесса в клеточной нейронной сети. Сибирский журнал вычислительной математики, 2000.

17. Короткин А.А., Панкратов А.В. Селекция траекторий клеточно-нейронной сетью. В кн. Тезисы докладов III Всероссийского семинара «Нейроинформатика и ее приложения». Красноярск, 1995. Стр. 28.

18. D.Dasgupta (Ed.). Artificial Immune Systems and Their Applications Springer, 1998. XIV, 310 pp.

19. H.Bersini. The Endogenous Double Plasticity of the Immune Network and the Inspiration to be Drawn for Engineering Artifacts. In the book: Artificial Immune

20. Systems and Their Applications.Edited by D.Dasgupta. Springer, 1998. XIV, p. 22-46.

21. D.J.Smith, S.Forrest, A.S. Perelson. Immunology Memory is Associative. In the book: Artificial Immune Systems and Their Applications.Edited by D.Dasgupta. -Springer, 1998. XIV, p. 105-115.

22. D.Dasgupta, S.Forrest. An Anomaly Detection Algorithm Inspired by the Immune System. In the book: Artificial Immune Systems and Their Applications.Edited by D.Dasgupta. Springer, 1998. XIV, p. 262-278.

23. T.Fukuda, K.Mori, M.Tsukiyama. Parallel Search for Multi-Modal Function Optimization with Diversity and Learning of Immune Algorithm. In the book: Artificial Immune Systems and Their Applications.Edited by D.Dasgupta. -Springer, 1998. XIV, p. 210-221.

24. L.A.Segel, R.L.Bar-Or. Immunology Viewed as the Study of an Autonomous Decentralized System. In the book: Artificial Immune Systems and Their Applications.Edited by D.Dasgupta. Springer, 1998. XIV, p. 65-88.

25. J.O.Kephart, G.B.Sorkin, M.Swimmer. Blueprint for a Computer Immune System. In the book: Artificial Immune Systems and Their Applications.Edited by D.Dasgupta. Springer, 1998. XIV, p. 242-261.

26. J.Hunt, J.Timmis, D.Cooke, M.Neal, C.King. Jisys: The Development of an Artificial Immune System for Real Wopld Applications. In the book: Artificial Immune Systems and Their Applications.Edited by D.Dasgupta. Springer, 1998. XIV, p. 157-186.

27. Е.А.Либерман. Молекулярная вычислительная машина клетки (MBM).l.Общие соображения и гипотезы. Биофизика. Том XVII, выпуск 5,1972. Москва, «Наука». С.932-943.

28. Е.А.Либерман. Молекулярная вычислительная машина клетки (МВМ). IV. «Цена действия» величина, характеризующая «трудность» решения задачи для вычислительного устройства. Биофизика. Том XIX, вып.1, 1974. С. 148150.

29. Е.А.Либерман. Молекулярная вычислительная машина клетки (МВМ). VII.Биофизика клетки и реалистическая или информационная физика. . Биофизика. Том XX, вып.З, 1975. С. 432-435.

30. Е.А. Либерман. Предельный молекулярный квантовый регулятор. Биофизика. Том XXVIII, вып.1, 1983.

31. H.Abelson, D.Allen, D.Coore, C.Hanson, E.Rauch, G.J.Sussman and R.Weiss. Amorthous computing. Communication of the ACM, Vol.43, No 5, 2000.

32. D.Coore, R.Nagpal, R.Weiss, paradigms for Structure in an Amorphous Computer. MIT Artificial Intelligence Laboratory memo no. 1614, 1997.

33. R.Nagpal. Organizing a Global Coordinate System from Local Information on an Amorphous Computer. MIT Artificial Intelligence Laboratory memo no. 1666, 1999.

34. Adleman, L. 1994. Molecular computation of solutions to combinatorial problems. Science 266:1021-1024

35. Leonard M. Adleman. Computing with DNA, Scientific American, August, 1998,54.61.

36. Rambidi NG. Biomolecular computer: roots and promises. Biosystems 1997, 44(1):1-15

37. D. Boneh, C. Dunworth, R. Lipton, and J. Sgall. On the computational power of DNA. Discrete Applied Mathematics, Special Issue on Computational Molecular Biology, Vol. 71 (1996), pp. 79-94.

38. Dove, A. From bits to bases: computing with DNA. Nature Biotechnology, 1998, 16(9): 830-2.

39. Liu Q, Frutos AG, Thiel AJ, Corn RM, Smith LM. DNA computing on surfaces: encoding information at the single base level. Journal of Computational Biology, 1998, 5(2):269-78.

40. Gibbons A, Amos M, Hodgson D. DNA computing. Current Opinion in Biotechnology 1997, 8(1): 103-6

41. G. Paun, G. Rozenberg, A. Salomaa. DNA Computing: New Computing Paradigms. Springer. - 1998, IX, 416 p.

42. D. Boneh, C. Dunworth, and R. Lipton. Breaking DES using a molecular computer. Proceedings of DIMACS workshop on DNA computing, 1995. published by the AMS.

43. D. Boneh, and R. Lipton. Making DNA computers error resistant. Proceedings ofsecond annual DIMACS conference on DNA computing, 1996.

44. E. Baum, and D. Boneh. Running dynamic programming algorithms on a DNA computer. Proceedings second annual DIMACS conference on DNA computing, 1996.

45. Oliver JS. Matrix multiplication with DNA. Journal of Molecular Evolution 1997, 45(2):161-7

46. Кирдин A.H. Идеальная ансамблевая модель параллельных вычислений // Нейроинформатика и ее приложения.Тезисы докладов V Всеросс. семинара. Красноярск, КГТУ, 1997. С. 101.

47. Жаботинский A.M. Концентрированные автоколебания. М.: Наука, 1974.

48. Горбань А.Н., Быков В.И., Яблонский Г.С. Очерки о химической релаксации. Новосибирск: Наука, 1986.

49. Горбань А.Н. Обход равновесия (уравнения химической кинетики и их термодинамический анализ).- Новосибирск: Наука, 1984.

50. Успенский В.А., Семенов A.JI. Теория алгоритмов: основные открытия и приложения М.: Наука. Гл. ред. физ.-мат. лит., 1987 - (Б-чка программиста).

51. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. Москва: Энергоатомиздат, 1988.

52. Марков А.А., Нагорный Н.М. Теория алгорифмов М.: Наука. Гл. ред. физ.-мат. лит., 1984.

53. Мендельсон Э. Введение в математическую логику. Москва: Наука, 1984.

54. Bugaenko N.N., Gorban A.N. and Sadovsky M.G. Maximum entropy method in analysis of genetic text and measurement of its information content Open Sys. and Information Dyn. 5, 1998. -p.265-278.

55. Е.О.Горбунова. Идеальная ансамблевая модель параллельных вычислений // Тез.конф.молодых ученых Института вычислительного моделирования СО РАН. Красноярск, Президиум КНЦ СО РАН,- 1998. - С. 95

56. Е.О.Горбунова. К вопросу об алгоритмической универсальности кинетической машины Кирдина // Нейроинформатика и ее приложения. Тезисы докладов VI Всеросс. семинара-Красноярск, КГТУ, 1998. С.47-48.

57. Е.О.Горбунова. Финитность и детерминированность простых программ для кинетической машины Кирдина // Методы нейроинформатики: Сб. научн. трудов / Под ред. А.Н. Горбаня; отв. за вып. М.Г. Доррер. Красноярск; КГТУ. 1998.-С. 23-40

58. E.О.Горбунова. Алгоритмическая универсальность кинетической машины Кирдина // Методы нейроинформатики: Сб. научн. трудов / Под ред. А.Н. Горбаня; отв. за вып. М.Г. Доррер. Красноярск; КГТУ. 1998. - С. 41-47.

59. Горбунова Е.О. Методы реализации кинетической машины Кирдина // Всероссийская научно-техническая конференция " Нейроинформатика-99". Сборник научных трудов. 4.1. М.: МИФИ 1999. С.48-55.

60. Горбунова Е.О. Алгоритмически универсальная модель бесструктурного параллелизма // Математика. Компьютер. Образование. Тезисы докладов VI Международной конференции-М.: МГУ 1999. С.73.

61. Горбунова Е.О. Формально-кинетическая модель бесструктурногомелкозернистого параллелизма // Сиб. Журн. вычисл. математики / РАН. Сиб. отд.-ние. Новосибирск, 1999. - Т.2, № 3. - С.239-256.

62. Горбунова Е.О. Вычислительная модель бесструктурного параллелизма // Материалы второго научно-практического семинара "Новые информационные технологии"; Московский государственный университет электроники и математики. М.: МГИЭМ, 1999. С. 4-13.

63. Gorbunova К.О. Algorithmically Universal Model of Structureless Parallelism. Book of summaries IEEE/INNS International Joint Conference of Neural Networks, Washington DC, IEEE, 1999, p. 437.

64. Gorbunova K.O. Algorithmically Universal Model of Structureless Parallelism. Proceedings IEEE/INNS International Joint Conference of Neural Networks, Washington DC, IEEE, 1999, #437

65. Горбунова Е.О. "Кинетическая машина Кирдина модель мелкозернистого параллелизма"// "Проблемы нейрокибернетики" (материалы XII Международной конференции по нейрокибернетике). Ростов-на-Дону, 1999, С.130-134.

66. Горбунова Е.О. О подпрограммах в квазихимической модели мелкозернистого параллелизма // Нейроинформатика и ее приложения. Тезисы докладов VII Всеросс. семинара.- Красноярск: КГТУ, 1999 С. 3739.

67. Горбунова E.O. Универсальная модель параллельной обработки данных // Материалы Конференции молодых ученых ИВМ СО РАН. Красноярск: ИВМ СО РАН, 1999. - С. 6-17.

68. Alexander N. Gorban, Katya О. Gorbunova. Liquid Brain: Kinetic Model of Structureless Parallelism. Internation Journal of Computing Anticipatory Systems, Edited by D.M.Dubois, Published by CHAOS, Volume 6, 2000, P.l 17-126.

69. Горбунова E.O. Формальная модель параллельного кинетического компьютера // Материалы конференции молодых ученых КНЦ СО РАН-Красноярск: ИВМ СО РАН, 2000. С. 11-14.

70. A.N.Gorban', K.O.Gorbunova, D.C.Wunsch. Liquid Brain: Kinetic Model of Structureless Parallelism. Advances in Modelling & Analisis. AMSE, V.5, №5, 2000.