автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.13, диссертация на тему:Автоволновые процессы в однородных клеточных средах

РГб од

] 5 ДЕК 5535

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

• Демидов Александр Васильевич

АВТОВОЛНОВЫЕ ПРОЦЕССЫ В ОДНОРОДНЫХ КЛЕТОЧНЫХ СРЕДАХ

Специальность 05.13.13 - Вычислительные машины,

комплексы, системы и сети

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Санкт-Петербург - 1996

Работа выполнена в Санкт-Петербургском государственном электротехническом университете

Научный руководитель -

доктор технических наук, профессор Герасимов И.В.

доктор технических наук, профессор. Никифоров В. В. .кандидат технических наук, доцент Романцев В.В..

Ведущая организация - Центральный научно-исследовательский институт "Морфиэприбор"

Защита диссертации состоится "^У 11 1996 г. в Ц0^ часов на заседании диссертационного совета К 063.36.12 . Санкт-Петербургского государственного электротехнического университета по адресу: 197376,Санкт-Петербург, ул. Проф. Попова, 5.

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

автореферат разослан "«/^ *// 1996 г.'

Официальные оппоненты:

Ученый секретарь диссертационного совета

ОБЩАЯ.ХАРАКТЕРИСТИКА РАБОТЫ

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

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

Значительно повышается уровень требований к методам анализа и синтеза средств взаимодействия объектов.

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

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

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

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

В последнее время специалисты в. различных областях проявляют постоянно усиливающийся интерес к относительно новому научному направлению под названием теория дискретно-событийных систем (discrete event driven systems'- ДСС). Наиболее распространенным определением ДСС является ее понимание как динамической системы с дискретным пространством состояний и кусочно-постоянной фазовой траекторией. В рамках этого определения разработано большое количество моделей. Однако каждая их них, используя свои средства описания и анализа динамических объектов, не охватывает многих важных для приложений задач. К их числу принадлежат вопросы, связанные с построением управляющих пространств для асинхронных-многокомпонентных процессов, развивающихся в возбудимых однородных средах. Они составляют содержание исследований области распределенных вычислений в рамках так называемой "волновой идеологии" решения многих практически важных задач, которым в настоящее время уделяется практическое внимание многих специалистов,

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

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

с последними работами Р-. Фейнмана, а также С. Уолфрэма и некоторых других авторов, "которые взглянули на физические теории с алгоритмической точки зрения".

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

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

Достижение поставленной цели, предусматривает решение следующих задач:'

1.' Исследование вопросов формального описания автоволнового процесса, развивающегося в однородных клеточных средах.

2. Анализ характеристических свойств автоволнового процесса. .

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

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

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

Н а у ч н а я новизна проведенных исследований состоит в :

1) разработке моделей автоволнового процесса, развивающегося в однородных клеточных средах;

2) выявлении характеристических свойств автоволнового процесса на базе модели фазовых потоков;

3) установлении свойств недетерминированного развития волнового процесса и их влияния,на поведение клеточных сред;

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

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

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

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

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

Ап/обация рабат ы. Основные положения и научные результаты работы докладывались и обсуждались на:

-городском семинаре "теория автоматов" секции вычислительной техники НТО РЭС им.А.С.Попова, Санкт-Петербург, 1992г.

- научно-технических конференциях профессорско-препода-вательскбго состава СПбГЭТУ, 1993-1995гг. .

Реализация результатов. Результаты работы использовались:

- при выполнении НИР по линии Института моделирования и интеллектуализации сложных систем (программно реализованы модели поведения отдельных клеточных автоматов),

- на кафедре Вычислительной техники ЭТУ при выполнении госбюджетной НИР "Теория и методы моделирования сложных систем и информационных процессов".

- при разработке и внедрении отдельных модулей автоматизированной системы управления предприятием на лоот "Октябрьский электровагоноремонтный завод". .

Публикации. Основные результаты диссертационной работы опубликованы в 2 печатных работах,одна из которых написана в соавторстве.

Структура и об-ъем работы .Диссерта-. ция состоит из введения,четырех глав с выводами, заключения, списка литературы . включающего 107 наименований , и одного приложения. Основная часть работы изложена на 110 страницах машинописного текста. Работа содержит 56 рисунков и 9 таблиц.

СОДЕРЖАНИЕ ДИССЕРТАЦИИ

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

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

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

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

данные).

Х0О -> [о]

х01 ' -> 0

10х " •> 0

О0х -> 0

При описании правил использована переменная х , определенная на множестве значений {О,1}.В рамку заключены состояния (в пространстве по данным) тех клеток,которые меняют свое состояние в зависимости от состояний соседей.

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

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

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

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

Пространство по управлению представлено в этом случае

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

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

Здесь х,у - значения фазовой переменной соседей клетки, заключенной в рамку,Г-количество фаз в фазовом цикле клетки.'. ■ '

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

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

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

Предлагается система правил в пространстве по управле-

при х, у е { Г, IГ+11 } той Г

->

— Точка пространства по данным

->

Точка пространства . по управлению(фаза) ,

->...

Ш-^^ШгзЕЬШгзШ

I V

I ;>71 ?а711

* а! Н

Г м 1Г м 11Гл I

] I , J I V . -I I V - -1 I V г -1 IV

>1

->1 кл.

>2 КЛ.

>3 кл.

ГТпГ? IТ;1

-1 I V г 1кг-1 IV

->Ш->Ш~>>Иг->[1]_1Г I ? А Т11 ? * 711 ? А 711

I V т | V г -1 | V г

J 1_>-^ I—>■-^ !->.,

,1

V

->|

ш-

Фазовый.цикл

>4 кл.

>5 кл.

<-

->

Рис.1.Фрагменты.пространства по управлению и пространства по данным для случая децентрализованного управления.

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

Одиночной волной называется направленное распространен

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

Выявлены условия формирования одиночной волны в терминах начальной разметки среды (состояния клеток) по отношению' к источнику. Эта разметка позволяет совместить реализацию локальных правил отдельной клеткой с требованиями, предъявляемыми к одиночной волне в соответствии с ее определением.

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

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

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

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

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

а).

Ii

>1 l 2

-> I

II

2

1 2 II

->'" щ

-> II I

->II I

1 1 1 ¿1

ППГ

1 1 !Ф

2 з|

1 г 1

6).

->2-

->12-

j——>32 ->22—-->223

> U->

->123

->23

Рис.2. Наложение волн в цепочке клеток ■Л. II, III - нумерация волн (снизу вверх).

Вид сбоку (а). Вид сверху (б).

I

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

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

и.

1 0 3 0 3 2 2 1 0 3 2 3

XVIII 0

XVII 3

XVI 2 3 0

XV 1 .2 3

XIV О 1 2 0

XIII 3 0 1 2

XII 2 3 0

XI 1 2 3 0 ■ 3

X с. 1 2 3 0 1

IX 3 0 1 2 3 о 0

VIII 2 3 О 1 2 3 0

VII '1 2 3 0 1 2 3 Е

VI 0 1 2 3 0 1 2 3

V 3 0 1 2 3 0 1 Е

IV 2 3 0 1 2 3 0 1 2

III 1 2 3 0 1 2 3 0 '1 2 3

II 0 1 2 3 О 1 2 3 О 1 2

I 3 0 1 2 3 О 1 2 3 0 1

-> Направление распространения

Рис.3. Разложение обобщенной волновой поверхности в спектр.

Локальные правила поведения клето . о которых говорилось выше,трансформируются в следующие:

а)за каждой волной с номером N при наложении волн следует волна с номером N+1,то есть волна,смещенная относитель-

но предыдущей на единицу фазового цикла;

■ б) количество приращений (или длина волновой поверхности) в любом из направлений волны N не может превышать соответствующую величину волны N-1;

в) если пути, пройденные волнами с соседними номерами N и N+1 равны по длине,то путь, пройденный волной не может быть такой же длины (должен быть обязательно короче).

Показано,что'сформулированные'правила не приведут к тупиковым ситуациям' при развитии процесса.Действительно,для каждой пары волн N и N+1 возможны два состояния друг относительно друга.Либо поверхности равны по длине,либо поверхность N опережает N+1.В первом случае правилами гарантируется, что поверхность N-1 'опережает N. Значит,составляющая N может совершить шаг. Во втором случае не накладывается ограничений на возможность совершить шаг составляющей- N+1.Таким образом в любом состоянии волновой поверхности возможен очередной шаг процесса.

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

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

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

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

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

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

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

Определено взаимодействие главной ЭВМ и клеточной среды в пространствах по управлению и по данным:Выделены функции контроллера клеточной среды,приведены форматы команд,обеспечивающих настройку среды на класс решаемых задач, загрузку данных и обрабатывающих программ.

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

Запуск процесса в пространстве по управлению среды осуществляется путем"создания соответствующих "граничных" условий для первой клетки устройства логическогостробирования (УЛС).что выполняется контроллером посредством связи с УЛС в пространстве по управлению .

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

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

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

Таблица 1. . '

Локальные правила в пространстве по управлению

Фаза Интерпретация Условие перехода в следующую 'фазу

О. Я смотрю и разрешаю смотреть на меня (вычис ляю новое состояние),, . Все 'соседи посмотрели на меня (запомнили мое старое состояние и вычисляют свое новое)

1. Я смотрю, но не разрешаю смотреть на меня Все соседи не разрешают смотреть на себя

2. Я не смотрю и не разрешаю смотреть на себя (меняю старое'состояние на новое) Все соседи не смотрят ' на меня (меняют старое состояние на новое)

3. Я не смотрю, но разрешаю смотреть на меня Все соседи разрешили . смотреть на себя. Могу переходить к фазе 0.

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

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

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

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

ЗАКЛЮЧЕНИЕ

Основные результаты диссертаций состоят в следующем.

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

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

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

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1.Герасимов И.В. .Демидов А.В.,Костичев С.В. Генерация множества возможных решений комбинаторной задачи обработки последовательности символов/СПб.электротехнический ун-т. -СПб.,21 с.-'Деп.в ВИНИТИ 11.01.95, N79-B95. .

2.Демидов А. В. Представление геометрических образов средствами логико-лингвистических моделей/СПб.электротехнический ун-т. - СПб.,20 C.-Деп.В ВИНИТИ И.01.95. N78-B9S.

Подписано в печать13.М.9£>Формат 60*84/16 Печать офсетная. Заказ № ЙОЧ

Печатный лист 4,0__Тираж /ДО экз.

ИПЦ ГЭТУ 197376, Санкт-Петербург, ул. Проф. Попова, 5