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

российская академия наук

вычислительный центр

РГБ од

2 3 о ¡А |0П- На правах рукописи

Шкондин Андрей Иванович

"Инструментальные средства имитации и анализа процессор в окружающей среде".

05.13.18 - Теоретические основы математического моделирования, численные методы и комплексы программ.

Автореферат дисвртации на соискание ученой степени кандидата физико-математических наук.

Москва, 1995 г.

Работа выполнена в Вычислительном, центре РАН.

Научный руководитель: член-корреспондент РАН, доктор

физико-математических наук, проф. Павловский Ю.Н. Официальные опппоненты: доктор физико-математических наук

Юрченко В.В., • кандидат физико-математических наук Сушков Б.Г.

Ведущая организация: МФТИ

/

Защита состоится /,/_1995 г. в //часмин. на

заседании диссертационного совета Д002.32.05 Вычислительного центра РАН по адресу: 117333, Москва, ул. Вавилова, 40.

С диссертацией можно ознакомиться в библиотеке Математического института РАН.

Автореферат разослан " 5" 1995 г.

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

кандидат физико-математкчэских наук В.Л. Бушенков

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

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

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

Цель работы. Выполняя данную работу, автор ставил перед собой следунцие цели:

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

2) разработать методы анализа и проведения численных

экспериментов со сложными имитационными моделями;

3) реализовать предложенную технологию в виде инструментальной системы имитации для ПЭВМ;

4) реализовать в рамках системы имитации, в качестве примера, комплекс простейших климатических моделей.

Научная новизна. В процессе работы получены следующие результаты:

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

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

-разработана Диалоговая Инструментальная Комплексная Система Имитации (ДИКСИ).

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

Апробация работы. Содержание работы обсуждалось на научных семинарах в ВЦ РАН.

Публикации. По теме диссертации опубликованы работы 1-3.

Структура и объем диссертации. Диссертация состоит из введения, трех глав, заключения, списка литературы и приложения. Список литературы содержит 51 название. Объем диссертации без списка литературы и приложений ,113 страниц.

с»

СОДЕРЖАНИЕ

Введение содержит информацию, необходимую для понимания материала диссертации. В первом параграфе описаны различные методологические подходы применяемые в системах имитационного моделирования, рассматриваются два примера существующих инструментальных систем. Во втором параграфе на примера проекта центра обработки информации глобальной системы ^экологического мониторинга (ГСЭМ) рассмотрены задачи имитации,.возникающие на современном уровне научных исследований, сформулированы требования к системам имитации. В третьем параграфе дается описание общей концепции системы имитации ДИКСИ.

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

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

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

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

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

В первой главе описывается организация системы.

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

Система реализована в виде объектной базы данных, с набором системных типов (классов) объектов, причем каждый' системный тип также является объектом систем.

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

Объект "корневая, вершина базы данных" служит отправной точкой разработки базы данных.

Объект "список типов объектов" содержит в качестве подобъектов описание существующих системных типов. Исходная конфигурация системы содержит восемь основных и два вспомогательных системных типа, в том числе, тип "список двумерных массивов" объекта которого содержа? данные в виде последовательности двумерных массивов вещественных чисел и обеспечивает их обр Зотку в виде карт, таблиц и графиков, тип "список • перемени с" объекты которого содержат список переменных - чисел или строк,, тип "текст" объекты которого содержат текстовую

информацию и другие типы.

Объект "очередь активных процессов" содержит в качестве ■подобъектов выполняемые в системе процессы. Изменяя состав списка пользователь может управлять организацией очэреди активных процессов.

Основой описании структуры системы служат объекты "базового системного типа". Объект этого типа описывается набором <Н,3,Р,М,1.,А'»1М;ь,1;в,Ш, где Н - справочная информация об объекте, Б - статус объекта , Р - фаза процесса , М - тип процесса , Ь - последовательность ссылок на подъобъекты нижнего уровня, А - вычислительный алгоритм объекта, временные параметры задаются неотрицательными вещественными числами: г- текущее локальное время объекта, начальное и конечное локальное

время выполнения объекта, At - шаг дискретизации по времени.

Каждый конкретный объект "базового системного типа" задает в системе некоторую структуру вложенных подобъектов данных, которую в свою очередь можно трактовать как некоторый составной объектный тип (далее будем называть его пользовательским объектным типом), конкретный объе т выступает как представитель класса объектов данного пользовательского типа. Определены средства работы с классами объектов пользовательских типов -получение ссылок на объекты, порождение, уничтожение объектов, создание общих подобъектов в классе.

Во втором параграфе описывается общая схема синхронизации процессов.

Обозначим подмножество объектов "базового системного типа" V' с- V. Для конкретного объекта О с V' будем обозначать его параметры в виде -.'обозначение параметра:»(О), например список

ссылок на подъобъекты нижнего уровня объекта 0 обозначим L(O).

Основным принципом задания динамики объектов l. системе является объединение понятий объекта и процесса его изменения -каждый объект О € V' определяет процесс изменения в системном времени своего состояния и состояния иерархии подобъектов, посредством задания алгоритмов и временах параметров для объекта и иерархии его подобъектов. В качестве базового механизма организации выполнения процесса принята иерархическая схема с квантованным шагом по времени - для объекта определено время начала и конца процесса и шаг квантования времени, в начале каждого шага времени выполняется алгоритм процесса (ему соответствует программа на языке высокого уровня), затем на интервале шага выполняются подпроцессы соответствующие подобъектам данного объекта (по той se схеме для всех уровней иерархии), затем текущее время объекта увеличивается на один квант. Синхрониза-

ч

ция подпроцессов происходит во внутрипроцессном времени, при этом текущее время подпроцесса 0' прэделяется как суша локальных текущих времен t подобъекта О' и его надобъектов до объекта О включительно. При этом выполняются только активные подпроцессы.

Характер выполнения подпроцесса О' определяется его фазой Р:

а) в фазе выполнения (Р(О*)=0) алгоритм А(О') подпроцесса О' вызывается в том случае, когда -его текущее время на очередном планируемом шаге времени оказывается минимальным для веек подпроцессов процесса О, при высовэ алгоритма процесса О' все о го подпроцессы (ó"e КО')) переходят в фазу инициализации;

б) б фазе инициализации (Р(0')=1) для подпроцесса О' локальное текуче время устанавливается на начало í(О')=íb(0'), зыполнение процесса 0' происходит также, как в предыдущем случав;

в) в фазе "вызов" (Р(0* )=2) прсйгсходат нема дленный (в локальном времени его надпроцесса) вызов подпроцесса О1, при этом его текущее время t{0,) ле меняется;

г) в фазе ожидание (Р(0*)=3) выполнение подпроцесса О' происходит как в случае а), кроме того подпроцесс О* вызывается ■ при всяком продвижении времени подпроцессов, относящихся к тому

же уровни временной иерархии (имзщих общий надпроцесс О", О'е Ь(0**)), в втом случав его текущее время 1(0*) не меняется. В любой фаза подпроцесса О' непосредственно перед вызовом алгоритма подпроцесс устанавливается в фазу выполнения и(0')=0).

Опишем формальную схему процесса О е V'. Обозначим Е\ множество всех подмножеств множества дуг Е. Объект О' е V* будем называть достижимым из объекта 0 и будем обозначать это в виде 0'= е(0), если существует путь е € Е' от О к О' в виде последовательности дуг ((7,0.^), 1 = 1,..,п, такой что 0± = О, Оп = О', причем подобъекты 01 , I = 2,..,п имеют активный статус - Б (О )=1 и в иерархии объектов пути е отсутствует рекурсия - не существует таких / и к, 1 $ J € п, к й ? п, что 0.= 0к.

Определим Ео(0) как набор всех достижимых из О объектов и множество Ео как {е е Е', е(0)€ Ео(0)}. Введем для путей из Ео отношение порядка: будем говорить что > еа, Ео,если'

существует объект О* € Ео(0) такой, что существуют дуги (О',0**) е и (О',О"') е ег и ссылка на объект 0" предшествует ссылке на объект О* *' в последовательности Ь(0).

Для произвольного пути е с е = (О. ,0.+1), 1 =1 ,..,п, 0^=0, Оп = 0* определим функцию т* '

а* (е) = т£п {("¿4(0.) + 2г=1,..,п),

V -1

задающую минимальное время окончания подпроцесса 0' и функцию % тЛе) - 2 t(04 )+ At(0 ) , если Р(0')=0 или Р(0')=3.

Vt(Ö,)+ t.(0 ), если Р(0*)=1, 1 ъ п

2 t(0.>, если Р(0')=2, •

1 = 1 1

задающую планируемое текущее время вызова подпроцесса О'

о

(здесь предполагается, что 2 0).

t=i

Определим функцию а

= т„(е), если im{e) > t„(e), +00 , иначе,

при этом условие т*(е) > гж(е) означает невыход подпроцесса О' за отведенные ему и его надпроцессам (О = О,,«., 0п1) временные граница.

Выполнение в качестве процесса объекта О происходит следующим образом:

В начале процесса устанавливается Р(0)=1, и текущее время процесса i(0) = tb{0).

На очередном шаге процесса устанавливается f = mtn .Ct(e), е € Ео). Если í = +00 то процесс оканчивается, иначе определяется объект О'- е(0) с. таким путем е с Ео, t(e)*t, что для любого е" € Ео , т(е")=1 выполняется е > е".

Если подпроцесс О' не находится в фазе "вызов" (Р(0*) 2), то для него выполняются следующие действия:

а) пересчитывается текущее локальное время t(0')=■ t(0')+ At(О*);

б) все его. подпроцессы устанавливаются в фазу инициализация Р(0") ч 1, Ь(О');

в) если в наборе ß = W"'t L(0nl), S(l'")=1) объектов, относящихся к тому же уровню иерархии что и объект О" и имеющих активный статус , существует непустое подмножество а объектов, находящихся в фазе ожидание и больше не осталось объектов О"' из а планирующих выполнение на тот же момент времени (таких, что t (0"*)+ At (О'") равно новому значению t(0')), то все процессы, соответствующие объектам из а переводятся в фазу "вызова" (Р=3).

Выполняется алгоритм А(0') подпроцесса О' и происходит переход к следующему шагу процесса О.

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

В третьем параграфе изложены принципы программирования в системе ДИКСИ. Программный интерфейс ДИКСИ организуется с помощью динамически линкуемых библиотек (DLL - универсальный стандарт исполняемого файла фирмы Microsoft). В качестве .основного механизма работы с базой данных используется прямой доступ к объектам в виртуальной памяти системы.

¡Во второй главе (в параграфах с первого по десятый) описы-¡ВЯЖЙЯ существующие типы системных объектов, принципы разработ-да № ¡модификации типов. Т рамкях описания дгется разноплановая ащ&рмэция об организации диалога в ДИКСИ и программирован™ ал-(ГйрйШдаеслих составлявших объектов. Под типом объекта понима-■етялшйЗор свойств, характеризующих объект в системе, а именно:

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

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

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

Третья глава посвяще а применению системы на практике.

В первом и втором параграфе третьей главы рассмотрены возможности расширения системы - описаны варианты реализации различных вычислительных схем имитации, описана технология созда-

V в

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

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

Рассмотривается математическая модель исследуемой систе?ш

в виде (X,(p,i}>,Z,Z0), где X - множество входных, переманных, являющееся компактом с метрикой р(, <р - отображение X в метрическое пространство Z с метрикой рг (элементы Z далее будем называть "траекториями" модели), ф - непрерывное отображение, ставящее в соответствие кавдой траектории z t Z конечный набор характеристик ф(г) в пространстве fi" с метрикой р, Z0 z Z -открытое ограниченное множество допустимых траекторий модели.

Назовем множество Z = ZQ П Ф(Х) множеством допустимых достижимых траекторий, а множество . ifl(Zt) множеством допустимых значений входных переменных. Обобщенным множеством достижимости назовем множество Y = /(X,), где /(•) = ф(ф(•)).

Пусть выполнены предположения:

а)на боралевской о-алгебрэ В(Х) множества X задана конечная мара р. (Л, ц(Х)>0 и способ получения последовательности точек ir) со свойством Pix. е ¿1 = ц(Л)/у.(Х), А € 8(Х);

б) для любого Xtфункция ф непрерывна-' в точка по X.

ß)[x(Xt)>0.

Рассматривается задача (e,rj>- аппроксимации множества Y: найти такой конечный набор точек а с , что

ц(Г'аПг) Пх,) >т].ц(Хд), У'=(/(а))е и задача е-аппроксимации множества У : найти такой конечный набор точек а е.Х, что У с Г, Г * (/(а))£.

Описаны детерминированные ji'вероятностные алгоритмы решения этих задач, основанные на знании верхней оценки константы Липшица функции /. Ошг 'н простой алгорятг получения оценки константы J-тшица в' случае задания модели системой обыкновенных да.^врвнцк¿лышх уравнений: рассматривается система обыкновенных дифференциальных уравнений, включающая исходную систему и

систему уравнений в вариациях по параметрам, строится оценка множества достижимости этой системы семейством множеств некоторой канонической формы, эта оценка используется при вычислении константы Липшица'. Доказательства утверждений, используемых при описании алгоритмов, приведены в приложении I. Описанные алгоритмы часглчно реализованы в системе ДИКСИ.

В четвертом параграфе технология моделирования в ДИКСИ рассматривается на примере разработки комплекса простейших климатических моделей.

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

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

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

2. Шкондин А.И. Макет центра обработки информации глобальной системы экологического контроля. //Моделирование, оптимизация и декомпозиция сложных динамических систем. М.: ВЦ РАН, 1993.

3. Шкондин А.И. Методы аппроксимации обобщенного множества достижимости нелинейных моделей. //Моделирование, оптимизация и декомпозиция сложных динамических систем. М.: ВЦ РАН, 1994.

4. Шкондин А.И. Инструментальная система имитации ДИКСИ. //Моделирование, оптимизация и декомпозиция сложных динамических систем. М.: ВЦ РАН, 1996. Статья находится в т. шти.

Подписано в печать 29.09.95, Формат 60/84/1/16. Объем I п.л. Тира» .00 экг Заказ £ 15.

Учас/ок оперативной полиграфии Института этнологии и антропологии РАН, 117304, Москва, Ленинский просп. 32.