Финитность и детерминированность простых программ для кинетической машины кирдина

Е. О. Горбунова

Институт вычислительного моделирования СО РАН,

Красноярский государственный технический университет

660036, Красноярск-36, ивм со ран,

E-mail: [e-mail]

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

1. Введение

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

Предлагается новая абстрактная модель параллельных вычислений – кинетическая машина Кирдина, предложенная А.Н.Кирдиным в октябре 1997 года на конференции «Нейроинформатика и ее приложения» [1]. Ожидается, что эта модель сыграет ту же роль для параллельных вычислений, что и нормальные алгоритмы Маркова, машины Колмогорова и Тьюринга или схемы Поста для последовательных вычислений.

В работе описаны основные способы реализации вычислений и исследованы свойства простейших программ для кинетической машины Кирдина. Часть результатов была ранее аннонсирована на Международном конгрессе по индустриальной и прикладной математике ИНПРИМ-98 [2].

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

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

Обработка состоит в совокупности элементарных событий, которые происходят недетерминированно и параллельно. Элементарное событие S: MM’состоит в том, что из ансамбляMизымается ансамбльK^–(это возможно, если для всехs ) и добавляется ансамбльK⁺, т.е.. АнсамблиK^–иK⁺однозначно задаются правилами или командами, которые объединяются в программу. Команды могут быть только трех видов:

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

1. Распад. uvw  uf + gw

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

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

F_M’(uvw) = F_M(uvw)–1 ,

F_M’(uf) = F_M(uf)+1 ,

F_M’(gw) = F_M(gw)+1.

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

2. Синтез. uk + qw  usw

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

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

F_M’(uk) = F_M(uk)–1 ,

F_M’(qw) = F_M(qw)–1 ,

F_M’(usw) = F_M(usw)+1.

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

3. Прямая замена. uvw  usw

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

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

F_M’(uvw) = F_M(uvw)–1 ,

F_M’(usw) = F_M(usw)+1.

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

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

Таким образом, элементарное событие Sоднозначно определяется правилом p, содержащимся в списке команд программыP, и ансамблемK^–, определяемым этим правилом, таким, чтоF_K^–(s)F_M(s)для любогоs.Допустимоеэлементарное событиеSдля ансамбляMи программыP– это такое, для которого существует правилоp, содержащeeся в списке команд программыP, и значения функцииF_Mдля слов, стоящих в левой части этого правила, положительны.

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

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

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

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

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

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