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

О 0 о 9

Ленинградский государственный университет

ВОЛЬПЕРТ Александр Борисович

ВЗАИМОДЕЙСТВИЕ ПОСЛЕДОВАТЕЛЬНЫХ АЛГОРИТМОВ: ОПИСАНИЕ, МОДЕЛИРОВАНИЕ И АНАЛИЗ

Специальность 05.T3.II - Математическое и программное обеспечение вычислитепьных машин, комплексов,систем и сетей

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата Физико-математических наук Ленинград - 1991

УДК 681.322.042 На правах рукописи

,, Г <~/ I / ч / / / - V- - ( ^ / и' /

Работа выполнена во Всесоюзном научно-исслг"опатепьском институте электроизмерительных приборов.

Научный руководитель: доктор Физико-математических наук А.О.Списенко

Официальные оппоненты: доктор Физико-математических наук,

доцент В.Л.Тузов

кандидат Физико-математических наук И.Р.Агамирзян

Ведущая организация: Институт аналитического приборостроения АН СССР

•X»

Защита состоится "JJP' IS?9I г.

на заседании специализированного солета K^ii^Xtvo присуждение ученой степени кандидата наук в Ленинградском государственном университете по адресу: '98904, Ленинград, Старый ПетергоФ, Библиотечная ппощадь, д.2.

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

Автореферат разослан " £>3__"______1991 г.

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

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

А.А.Кубенский

Общая характеристика работы

Актуальность j7£o6neMH._ Почти все существурщие вычислительные системы допускагт возможность частичной параллелизации протекающих в них процессов. Уже в однопрессорной вычислительной системе, управляемой однозадачной операционной системой (ОС), имеет уесто параллельное Функционирование процессора и внешних устройств. Разнообразие допустимых видов параллельного функционирования возрастает при переходе к многозадачным ОС. В многопроцессорных системах и сетях ЭВМ параллелизм отдельных процессов становится основным способом Функционирования системы в целом.

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

Упомянутые выие системы процессов с частичной пагаппепизаци-ей являются объектом исследования по крайней мере двух научных дисциплин: теории сетей массового обслуживания ССеНО) и теории

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

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

В приводимых ниже Формулировках вместо неформального понятия "процесс" используется термин "алгоритм" в значении, уточняемом при изложении содержания раздела I.

Ц§НЫ:_Е£бота является описание, качественное, аналитическое и экспериментальное исследование поведения систем взаимодействующих алгоритмов сетевого и программно-аппаратного математического обеспечения, а также создание аппарата дпя численного моделирования поведения таких систем. Дпя достижения поставленной цели в диссертации решались следующие задачи:

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

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

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

- разработка программы моделирования систем взаимодействущих алгоритмов на основе упомянутых алгоритмов моделирования и языка;

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

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

^Г!!!^ ^овизна. ^ процессе решения поставленных задач в диссертации получены следующие основные научные результаты:

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

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

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

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

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

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

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

- разработан язык СОО^С, позволяющий описывать взаимодействие в квазипараллепьных системах последовательных алгоритмов;

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

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

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

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

Все эксперименты и численное моделирование проводились для анализа мини-ОС СПОР, реализующей управление измерительно-вычислительным комплексом ИВК-12, и сетевого математического обеспечения РАНЕТ - 2.

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

- Семинар по теории сложности, Ленинградское отделение

Математического института (ЛОМИ) АН СССР, Ленинград, 1985 г.

- Всесоюзной конференции по применению методов математической логики, Таллин, 1986 г.

- Городском семинаре по программированию, Институт социально-экономических проблем АН СССР, Ленинград, 1967 г.

- IX Всесоюзной конференции по математической логике, Ленинград, 19РВ г.

- Семинаре по переборным задачам, Ленинградский электротехнический институт, 1989 г.

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

Ст££кт££а_и_0бъемработы. Диссертационная работа состоит из введения, пяти разделов с выводами, заключения, списка литературы, включающего 72 наименования. Работа содержит 164 страницы, 25 иллюстраций и Ч таблицы.

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

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

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

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

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

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

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

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

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

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

вводится модель, описывающая системы взаимодействующих последовательных алгоритмов как динамические системы, определенные на кубических комплексах. Вообще говоря, рассматриваемые модели пригодны для описания взаимодействия любого числа поспеюватепьных алгоритмов, однако, строгий анализ поведения таких систем удалось осуществить лишь в случае,когда взаимодействуют два алгоритма. Отметим, что задавать исследуемые нами объекты ппопе всего на языке сетевого типа С таком, например, как язык Сс'-!0), так как последовательные алгоритмы описываются при этом подходе раздельно. Описание механизма взаимодействия, за отсутствием специальных средств, дается в этом случае словесно, без Формализации. Изучаемые во втором разделе квазипараппепьные системы состоят из двух последовательных алгоритмов, каждый из которых является циклическим и имеет два этапа (вершины). В случае, когда отношению разделения ресурса принадлежит ровно одна пара вершин, система монет быть описана как замкнутая сеть массового обслуживания с тремя приборами и двумя заявками. Маршрут какпой заявки (последовательного алгоритма) вкпгчает два из трех приборов, а общим прибором в о^оих маршрутах является только один обслуживающий прибор. Длительности обслуживания заявок в каждом из приборов равны длительностям соответствующих этапов и, таким образом, вырождены (постоянны). В разделе рассматриваются системы со следующими дисциплинами обслуживания в единственном приборе с конкуренцией (в нотации, принятой в теории СеМО): рСРЗСГи^ Соте 5сггкс1 ),

ICFSiUst Comt Filit $trvea/)t PRl (PKlotLiy ¿isdpiiiti), TS (Ti 14« L 3 (Lost if iu sy),

l s (lo%i Serv/ce if Uhxtu/»i ecf) , PL Ь (Priort ¿j -

Lest Sety/'c c).

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

В соответствии с названиями дисциплин динамические системы будут обозначаться ниже выражениями вида AiTJ^ тл1 т(г) 7*^'), где /• - соответствующие длительности с -ой дуги j. -ой заявки ijj G {i,l] t А - название дисциплины. В разделе 2 получены следующие результаты.

Теорема 2.3.1. Лля динамической системы fCFS (Tj'\ f/^ f^'j верно следующее:

- если отношение чисел 7~л + Т^ Tj^T^ U> рационально и их н.о.к.не больше, чем fc^r^)-^J/fr/^* Г/2' . то каждая траектория системы стремится к одной из периодических траекторий ( образующих, вообще говоря, непрерывное семейство) с пери-

-г 'Ч г М -г- U)

одом, равным к.о.к. чисел 7Х +Yt * Тг »'

Ти1 ГШ г(1) т(1)

- если отношение чисел /х*'г Гх иррационально

или если оно рационально, но н.о.к. этих чисел больше, чем

Г®} • то У системы имеется единственная предельная периодическая траектория.

Для системы /ГЛ5 /Гхи>, Г/г\ Г/г) ) указан алгоритм, вычисляющий длину периодической орбиты. Теорема 2.4.1. Для почти всех наборов чисел СТ"/*1,^1,^^,^'**) по мере Лебега на (Х.*)1* поток {в*} на пространстве состояний системы Т^'*1, ) минимален, сохраняет

нормировакнуг) меру Лебега нэ (нормированную плотадь) и строго эр годичен.

Л ля системы Z С Р 5 ( Т/*\ ^^! бУДем начинать

(дискретным) состоянием системы сочетание исполняемых этапов последовательных алгоритмов, дополненных в случае, если эта пара этапов разделяет ресурс порядком, в котором данные алгоритмы вступили в исполнение этих этапов. Таким образом, у данной системы имеется пять состояний. Вероятности пребывания системы в различных состояниях вычисляются по ^орнупам (индексы внизу характеризуют этап, исполняемый алгоритмом в ванном состоянии А - автономный, К - конкурентный;:

Теорема 2.5.1. Для любых наборов попарно несоизмеримых чисел (^'{Ъ.'**, Т^') в динамической системе Р#1 (г/^Г^т/* Т*) имеется единственная периодическая траектория; в системе

РЯ1 Т^) верно первое утверждение теоремы 2.3.1.

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

Цепь третьего_£аздела работы - создать удобные средства формального описания некоторого класса динамических систем, определенных на кубических комплексах и моделирующих временную эволюцию систем взаимодействующих алгоритмов. Динамические системы, рассматривавшиеся в разделе 2, принадлежат упомянутому классу, являясь весьма специальными его представителями. В общем случае наиболее доступным средством изучения таких систем является численное моделирование и именно для его нужд разрабатывалось формальное описание систем указанного класса. Решая задачу формального описания, мы указываем сначала, как описать дискретный остов механизма управления взаимодействием в данной системе взаимодействующих алгоритмов (для этого служит объект, именуемый в работе системой кооперирующихся орграфов), а затем показывем, как перейти к системе с непрерывным пространством состояний и непрерывным временем. Система кооперирующихся орграфов представляет собой семейство циклических или цепных орграфов, называемых базовыми, и орграф, называемый основным, снабженный отображениями в каждый из базовых орграфов данного семейства. Отметим, что семейство базовых орграфов образует квазипараллельнув систему алгоритмов, а основной орграф вместе с отображениями определяет механизм управления взаимодействием алгоритмов. В разделе формулируются ограничения, накладываемые на основной орграф и семейство соответствующих отображений. Затем описывается категория кубических множеств и способ сопоставления системе кооперирующихся орграфов семейства кубических множеств, производится анализ того, какой класс семейств кубических множеств по-

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

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

принятый механизм управления взаимодействием.Для численной реализации модели необходимо Фиксировать карты всех кубов. Оказывается, что достаточно фиксировать карты одномерных базовых комплексов, а карты кубов основного комплекса строятся тогда канонически. Карта каждого одномерного куба отображает его внутренность на отрезок ("О,А), где А - число, выражавшее объем работы, соответствующей этому одномерному кубу, выраженный в некоторых единицах, вообще говоря, сеоих для каждого последовательного алгоритма. Векторное попе (скорость работы) тогда задается в этой карте Функцией. В диссертации рассматриваются только ттостоянные внутри кубов (относительно выбранных карт) векторные попя, поскольку именно такой кпасс систем охватывается разработанной программой моделирования. В соответствии со сказанным выше, на кубах основного комплекса также появляются карты и постоянные векторные поля (мы сохраняем нумерации координат карты совпадающую с нумерацией последовательных алгоритмов). Для нас важны еще .замкнутые дифференциальные 1-Формы на этих кубах, £ -ая из которых равна дигМ^енциапу I -ой координаты. Соответствующую форму мы будем называть формой работы с -го алгоритма (или с -ой работой). Интегрирование ее вдоль отрезка траектории динамической системы дает работу / -го алгоритма вдоль этого отрезка. Состояние нашей динамической системы (то есть точка на ее кубическом комплексе) могут быть заданы посредством указания куба, содержащего эту точку, и ее координат в выбранной карте. Практически при численном моделировании все описанные выще геометрические объекты реализуются с помощью дополнительного оснащения на системе кооперирующихся орграфов.

В разделе даны следующие определения и доказаны приведенные ниже теоремы:

Определение 3.2.1. Пусть ^ , . - квазипараппепьная систе-

ма алгоритмов, М-связный орграф без кратных дуг, {{• :И~* семейство отображений такое, что для любой дуги £ орграфа И, существует единственное 0& ¿а & Н-/ такое, что -дуга

орграФа (¡2 . Семейство [: М -» ^называется системой

О С*0

кооперирующихся орграфов, если:

-Н - сильно связный орграФ;

- - циклический оргра* при всех ол с * Л-/ •

- для всех 4, , £' , где а - вершина орграфа М , t и г£' - его дуги такие, что началом обеих является вершина Л , из того, что ^Ц) - дуга орграфа (Г; следует, что -вершина орграФа (Г^;

- из того, что I а,- С; .... й; I - множество вершин, соответствующих орграфов (¡Т , (ц ,...,(?£ .являющихся компонентами элемента £ -арного отношения нормального ресурса (где (с<Осле-дует, что не существует множества дуг {¿¿4 , ¿¿^ ,..¿-^ , имеющих общую начальную вершину V в орграфе М , переводимую каждым из отображений в вершину Д^ ^ дпя всех и та~ ких, что - ДУга орграФа дпя всех К .

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

рованное множество, на котором заданы дпя всех ¿го отображения граней и вырождений Ы^; ^ -у ) : X^ , /'-/,

С

при </'< <

г^'.ь'1 = ¿е'*' . £ * V Сх СКН V при 1 4 к

Г £С~г ■ ¿с-' н ■ М г'-1 е(*-' при ¿< *

при

\-idi при 4 '

л.-/

о

Предложение 3.3.3. Каждой системе кооперирующихся орграфов

' канонически соответствует семейство кубических

л-/

множеств и отображений | ¡¡¿\)]. . Пги этом Х(М} содержит в размерностях, не равных п., только элементы,совпадающие со значениями композиций отображений граней и вырождений на

-мерных элементах (является однородно ц -мерным множеством \ а кубические однородно одномерные множества.

Лалее рассматривается каноническая конструкция геометрической реализации кубического множества, (кубический комплекс), аналогичная соответствующей симплициапьнок конструкции. Предложение 3.4.5. Системе кооперирующихся орграфов {/¿.'М-* однозначно соответствует система отображений пространств геометрических реализаций { '. |Х(М)|-* (51)1 ^ £_о .

Отображения А- и , о < ¿¿Л-/, Фигурирующие в ниже-

следующем определении, являются средством задания Форм работ и попей скоростей.

_ , к—I

Определение 3.5.3. Следующий набор данных { ^ .' М—,

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

В работе также определяется состояние системы, задаваемое парой (вершина орграФа, вектор остаточных работ). Теорема 3.5.3. Оснащенной системе кооперирующихся орграфов однозначно соответствует динамическая система, канонически определяемая на пространстве основного кубического комплекса. Теорема 3.5.6. Алгоритм поиска замкнутой траектории позволяет рассчитать значение вектора работ на отрезке траектории из заданного начального состояния.

В_^етве^том_2.азде_11е вводится язык, семантикой которого, как показано в работе, является оснащенная система кооперирующихся орграфов с заданным начальным состоянием. Анализ контекстно свободного определения языка позволяет показать, что он определен как Щ!) язык. В разделе формулируются контекстные ограничения на использование идентификаторов, констант и переменных языка. Язык имеет декларативный характер и предназначен для задания динамических систем на кубических комплексах.

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

Выводы

В работе решены следующие задачи:

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

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

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

4. Предложены алгоритмы, вычисляющие характеристики траек-

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

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

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

Публикации по теме диссертации.

1. Вольперт А.Б., Гордин М.И. Об одном классе математических1' моделей динамики аппаратно-программных средств измерительно-вычислительных комплексов. // Процессорные средства измерений. Под ред. Р.Э.Капиева, JL, ВНИИЭП, 1984, с.60-76.

2. Вольперт А.Б., Каган С.М. Анализ динамических характеристик измерительно-вычислительных комплексов методом численного моделирования. // Программное обеспечение измерительно-вычислительных комплексов. Под ред. И.П.Пуцима. J1., ВНИИЭП, 1985, с.20-30.

3. Вольперт А.Б., Гордин М.И. Графовые модели диспетчеризации в процессорно управляемых системах. // Процессорные электроизмерительные средства. Под ред. Р.Э.Капиева. Л., ВНИИЭП,1986, с. 52-63.

Вольперт А.Б., Гордин М.И. Графовая модель диспетчера частичной параллелизации. //Тр. 1У Всесоюзной конференции "При-

менение методов математической погики", Таппип, ЧК Л'1 ТСГ, 1986, т.1, с.32-35.

5. Вопьперт А.Б. Нестандартная модель параллельных вычислений // Тр. D Чсесогзной конференции по математической логике,

Л., Наука, I9R8, с 30.

6. Вопьперт A.B. Качественное изучение одного класса систем vac-сового обслуживания. // !'атегатические методы построения и анализа алгоритмов. Под ред. А.О.Слисенко, С.R.Соловьева. Л., Наука, 1990, с.26-36.

Подписано к печати 12.05.91г. Заказ 73.типаж 100 экз. 197265 Ленинград, пр. Просвещения, 85 РЩ ВНИИЗП. Бесплатно